Provides an implementation of the Interval tree data structure, as a library for use in smart contracts.

A deployed version of this library is available at address 0xa7aCE3440fD2D6Afa37d12F18E3A9F25C55D1E47.

File contracts/intervals/TreeLib.sol

Usage: import library and use for TreeLib.Tree data structure.

contract HasTree {
  using TreeLib for TreeLib.Tree;

  TreeLib.Tree tree;

  function HasTree() {
    tree.addInterval(5, 9, 0xDEADBEEF);
  }
}

See Example.sol for a contract that maintains a global collection of interval trees.

• internal

Adds an interval [begin, end) with data.

• constant
• internal
• returns (uint[] memory matchingIDs)

Searches the tree for intervals containing point.

Returns memory array of interval IDs, to retrieve with tree.getInterval()

• constant
• internal
• returns (uint begin, uint end, bytes32 data)

Retrieves interval information for a given interval ID.

Use in conjunction with tree.search().

• Supports adding new intervals and finding intervals containing a point
• No support currently for interval search
• Creates unbalanced trees

This project uses @pipermerriam's Grove data structure for some underlying behavior.