Contract 0xd07ce4329b27...98a0e4c0394c

{
  "language": "Solidity",
  "sources": {
    "GroveLib.sol": {
      "content": "// Grove v0.2\r\n\r\n\r\n/// @title GroveLib - Library for queriable indexed ordered data.\r\n/// @author PiperMerriam - <pipermerriam@gmail.com>\r\nlibrary GroveLib {\r\n        /*\r\n         *  Indexes for ordered data\r\n         *\r\n         *  Address: 0xd07ce4329b27eb8896c51458468d98a0e4c0394c\r\n         */\r\n        struct Index {\r\n                bytes32 id;\r\n                bytes32 name;\r\n                bytes32 root;\r\n                mapping (bytes32 => Node) nodes;\r\n        }\r\n\r\n        struct Node {\r\n                bytes32 nodeId;\r\n                bytes32 indexId;\r\n                bytes32 id;\r\n                int value;\r\n                bytes32 parent;\r\n                bytes32 left;\r\n                bytes32 right;\r\n                uint height;\r\n        }\r\n\r\n        /// @dev This is merely a shortcut for `sha3(owner, indexName)`\r\n        /// @param owner The address of the owner of this index.\r\n        /// @param indexName The human readable name for this index.\r\n        function computeIndexId(address owner, bytes32 indexName) constant returns (bytes32) {\r\n                return sha3(owner, indexName);\r\n        }\r\n\r\n        /// @dev This is merely a shortcut for `sha3(indexId, id)`\r\n        /// @param indexId The id for the index the node belongs to.\r\n        /// @param id The unique identifier for the data this node represents.\r\n        function computeNodeId(bytes32 indexId, bytes32 id) constant returns (bytes32) {\r\n                return sha3(indexId, id);\r\n        }\r\n\r\n        function max(uint a, uint b) internal returns (uint) {\r\n            if (a >= b) {\r\n                return a;\r\n            }\r\n            return b;\r\n        }\r\n\r\n        /*\r\n         *  Node getters\r\n         */\r\n        /// @dev Retrieve the unique identifier for the node.\r\n        /// @param index The index that the node is part of.\r\n        /// @param nodeId The id for the node to be looked up.\r\n        function getNodeId(Index storage index, bytes32 nodeId) constant returns (bytes32) {\r\n            return index.nodes[nodeId].id;\r\n        }\r\n\r\n        /// @dev Retrieve the index id for the node.\r\n        /// @param index The index that the node is part of.\r\n        /// @param nodeId The id for the node to be looked up.\r\n        function getNodeIndexId(Index storage index, bytes32 nodeId) constant returns (bytes32) {\r\n            return index.nodes[nodeId].indexId;\r\n        }\r\n\r\n        /// @dev Retrieve the value for the node.\r\n        /// @param index The index that the node is part of.\r\n        /// @param nodeId The id for the node to be looked up.\r\n        function getNodeValue(Index storage index, bytes32 nodeId) constant returns (int) {\r\n            return index.nodes[nodeId].value;\r\n        }\r\n\r\n        /// @dev Retrieve the height of the node.\r\n        /// @param index The index that the node is part of.\r\n        /// @param nodeId The id for the node to be looked up.\r\n        function getNodeHeight(Index storage index, bytes32 nodeId) constant returns (uint) {\r\n            return index.nodes[nodeId].height;\r\n        }\r\n\r\n        /// @dev Retrieve the parent id of the node.\r\n        /// @param index The index that the node is part of.\r\n        /// @param nodeId The id for the node to be looked up.\r\n        function getNodeParent(Index storage index, bytes32 nodeId) constant returns (bytes32) {\r\n            return index.nodes[nodeId].parent;\r\n        }\r\n\r\n        /// @dev Retrieve the left child id of the node.\r\n        /// @param index The index that the node is part of.\r\n        /// @param nodeId The id for the node to be looked up.\r\n        function getNodeLeftChild(Index storage index, bytes32 nodeId) constant returns (bytes32) {\r\n            return index.nodes[nodeId].left;\r\n        }\r\n\r\n        /// @dev Retrieve the right child id of the node.\r\n        /// @param index The index that the node is part of.\r\n        /// @param nodeId The id for the node to be looked up.\r\n        function getNodeRightChild(Index storage index, bytes32 nodeId) constant returns (bytes32) {\r\n            return index.nodes[nodeId].right;\r\n        }\r\n\r\n        /// @dev Retrieve the node id of the next node in the tree.\r\n        /// @param index The index that the node is part of.\r\n        /// @param nodeId The id for the node to be looked up.\r\n        function getPreviousNode(Index storage index, bytes32 nodeId) constant returns (bytes32) {\r\n            Node storage currentNode = index.nodes[nodeId];\r\n\r\n            if (currentNode.nodeId == 0x0) {\r\n                // Unknown node, just return 0x0;\r\n                return 0x0;\r\n            }\r\n\r\n            Node memory child;\r\n\r\n            if (currentNode.left != 0x0) {\r\n                // Trace left to latest child in left tree.\r\n                child = index.nodes[currentNode.left];\r\n\r\n                while (child.right != 0) {\r\n                    child = index.nodes[child.right];\r\n                }\r\n                return child.nodeId;\r\n            }\r\n\r\n            if (currentNode.parent != 0x0) {\r\n                // Now we trace back up through parent relationships, looking\r\n                // for a link where the child is the right child of it's\r\n                // parent.\r\n                Node storage parent = index.nodes[currentNode.parent];\r\n                child = currentNode;\r\n\r\n                while (true) {\r\n                    if (parent.right == child.nodeId) {\r\n                        return parent.nodeId;\r\n                    }\r\n\r\n                    if (parent.parent == 0x0) {\r\n                        break;\r\n                    }\r\n                    child = parent;\r\n                    parent = index.nodes[parent.parent];\r\n                }\r\n            }\r\n\r\n            // This is the first node, and has no previous node.\r\n            return 0x0;\r\n        }\r\n\r\n        /// @dev Retrieve the node id of the previous node in the tree.\r\n        /// @param index The index that the node is part of.\r\n        /// @param nodeId The id for the node to be looked up.\r\n        function getNextNode(Index storage index, bytes32 nodeId) constant returns (bytes32) {\r\n            Node storage currentNode = index.nodes[nodeId];\r\n\r\n            if (currentNode.nodeId == 0x0) {\r\n                // Unknown node, just return 0x0;\r\n                return 0x0;\r\n            }\r\n\r\n            Node memory child;\r\n\r\n            if (currentNode.right != 0x0) {\r\n                // Trace right to earliest child in right tree.\r\n                child = index.nodes[currentNode.right];\r\n\r\n                while (child.left != 0) {\r\n                    child = index.nodes[child.left];\r\n                }\r\n                return child.nodeId;\r\n            }\r\n\r\n            if (currentNode.parent != 0x0) {\r\n                // if the node is the left child of it's parent, then the\r\n                // parent is the next one.\r\n                Node storage parent = index.nodes[currentNode.parent];\r\n                child = currentNode;\r\n\r\n                while (true) {\r\n                    if (parent.left == child.nodeId) {\r\n                        return parent.nodeId;\r\n                    }\r\n\r\n                    if (parent.parent == 0x0) {\r\n                        break;\r\n                    }\r\n                    child = parent;\r\n                    parent = index.nodes[parent.parent];\r\n                }\r\n\r\n                // Now we need to trace all the way up checking to see if any parent is the \r\n            }\r\n\r\n            // This is the final node.\r\n            return 0x0;\r\n        }\r\n\r\n\r\n        /// @dev Updates or Inserts the id into the index at its appropriate location based on the value provided.\r\n        /// @param index The index that the node is part of.\r\n        /// @param id The unique identifier of the data element the index node will represent.\r\n        /// @param value The value of the data element that represents it's total ordering with respect to other elementes.\r\n        function insert(Index storage index, bytes32 id, int value) public {\r\n                bytes32 nodeId = computeNodeId(index.id, id);\r\n\r\n                if (index.nodes[nodeId].nodeId == nodeId) {\r\n                    // A node with this id already exists.  If the value is\r\n                    // the same, then just return early, otherwise, remove it\r\n                    // and reinsert it.\r\n                    if (index.nodes[nodeId].value == value) {\r\n                        return;\r\n                    }\r\n                    remove(index, id);\r\n                }\r\n\r\n                uint leftHeight;\r\n                uint rightHeight;\r\n\r\n                bytes32 previousNodeId = 0x0;\r\n\r\n                bytes32 rootNodeId = index.root;\r\n\r\n                if (rootNodeId == 0x0) {\r\n                    rootNodeId = nodeId;\r\n                    index.root = nodeId;\r\n                }\r\n                Node storage currentNode = index.nodes[rootNodeId];\r\n\r\n                // Do insertion\r\n                while (true) {\r\n                    if (currentNode.indexId == 0x0) {\r\n                        // This is a new unpopulated node.\r\n                        currentNode.nodeId = nodeId;\r\n                        currentNode.parent = previousNodeId;\r\n                        currentNode.indexId = index.id;\r\n                        currentNode.id = id;\r\n                        currentNode.value = value;\r\n                        break;\r\n                    }\r\n\r\n                    // Set the previous node id.\r\n                    previousNodeId = currentNode.nodeId;\r\n\r\n                    // The new node belongs in the right subtree\r\n                    if (value >= currentNode.value) {\r\n                        if (currentNode.right == 0x0) {\r\n                            currentNode.right = nodeId;\r\n                        }\r\n                        currentNode = index.nodes[currentNode.right];\r\n                        continue;\r\n                    }\r\n\r\n                    // The new node belongs in the left subtree.\r\n                    if (currentNode.left == 0x0) {\r\n                        currentNode.left = nodeId;\r\n                    }\r\n                    currentNode = index.nodes[currentNode.left];\r\n                }\r\n\r\n                // Rebalance the tree\r\n                _rebalanceTree(index, currentNode.nodeId);\r\n        }\r\n\r\n        /// @dev Checks whether a node for the given unique identifier exists within the given index.\r\n        /// @param index The index that should be searched\r\n        /// @param id The unique identifier of the data element to check for.\r\n        function exists(Index storage index, bytes32 id) constant returns (bool) {\r\n            bytes32 nodeId = computeNodeId(index.id, id);\r\n            return (index.nodes[nodeId].nodeId == nodeId);\r\n        }\r\n\r\n        /// @dev Remove the node for the given unique identifier from the index.\r\n        /// @param index The index that should be removed\r\n        /// @param id The unique identifier of the data element to remove.\r\n        function remove(Index storage index, bytes32 id) public {\r\n            bytes32 nodeId = computeNodeId(index.id, id);\r\n            \r\n            Node storage replacementNode;\r\n            Node storage parent;\r\n            Node storage child;\r\n            bytes32 rebalanceOrigin;\r\n\r\n            Node storage nodeToDelete = index.nodes[nodeId];\r\n\r\n            if (nodeToDelete.id != id) {\r\n                // The id does not exist in the tree.\r\n                return;\r\n            }\r\n\r\n            if (nodeToDelete.left != 0x0 || nodeToDelete.right != 0x0) {\r\n                // This node is not a leaf node and thus must replace itself in\r\n                // it's tree by either the previous or next node.\r\n                if (nodeToDelete.left != 0x0) {\r\n                    // This node is guaranteed to not have a right child.\r\n                    replacementNode = index.nodes[getPreviousNode(index, nodeToDelete.nodeId)];\r\n                }\r\n                else {\r\n                    // This node is guaranteed to not have a left child.\r\n                    replacementNode = index.nodes[getNextNode(index, nodeToDelete.nodeId)];\r\n                }\r\n                // The replacementNode is guaranteed to have a parent.\r\n                parent = index.nodes[replacementNode.parent];\r\n\r\n                // Keep note of the location that our tree rebalancing should\r\n                // start at.\r\n                rebalanceOrigin = replacementNode.nodeId;\r\n\r\n                // Join the parent of the replacement node with any subtree of\r\n                // the replacement node.  We can guarantee that the replacement\r\n                // node has at most one subtree because of how getNextNode and\r\n                // getPreviousNode are used.\r\n                if (parent.left == replacementNode.nodeId) {\r\n                    parent.left = replacementNode.right;\r\n                    if (replacementNode.right != 0x0) {\r\n                        child = index.nodes[replacementNode.right];\r\n                        child.parent = parent.nodeId;\r\n                    }\r\n                }\r\n                if (parent.right == replacementNode.nodeId) {\r\n                    parent.right = replacementNode.left;\r\n                    if (replacementNode.left != 0x0) {\r\n                        child = index.nodes[replacementNode.left];\r\n                        child.parent = parent.nodeId;\r\n                    }\r\n                }\r\n\r\n                // Now we replace the nodeToDelete with the replacementNode.\r\n                // This includes parent/child relationships for all of the\r\n                // parent, the left child, and the right child.\r\n                replacementNode.parent = nodeToDelete.parent;\r\n                if (nodeToDelete.parent != 0x0) {\r\n                    parent = index.nodes[nodeToDelete.parent];\r\n                    if (parent.left == nodeToDelete.nodeId) {\r\n                        parent.left = replacementNode.nodeId;\r\n                    }\r\n                    if (parent.right == nodeToDelete.nodeId) {\r\n                        parent.right = replacementNode.nodeId;\r\n                    }\r\n                }\r\n                else {\r\n                    // If the node we are deleting is the root node so update\r\n                    // the indexId to root node mapping.\r\n                    index.root = replacementNode.nodeId;\r\n                }\r\n\r\n                replacementNode.left = nodeToDelete.left;\r\n                if (nodeToDelete.left != 0x0) {\r\n                    child = index.nodes[nodeToDelete.left];\r\n                    child.parent = replacementNode.nodeId;\r\n                }\r\n\r\n                replacementNode.right = nodeToDelete.right;\r\n                if (nodeToDelete.right != 0x0) {\r\n                    child = index.nodes[nodeToDelete.right];\r\n                    child.parent = replacementNode.nodeId;\r\n                }\r\n            }\r\n            else if (nodeToDelete.parent != 0x0) {\r\n                // The node being deleted is a leaf node so we only erase it's\r\n                // parent linkage.\r\n                parent = index.nodes[nodeToDelete.parent];\r\n\r\n                if (parent.left == nodeToDelete.nodeId) {\r\n                    parent.left = 0x0;\r\n                }\r\n                if (parent.right == nodeToDelete.nodeId) {\r\n                    parent.right = 0x0;\r\n                }\r\n\r\n                // keep note of where the rebalancing should begin.\r\n                rebalanceOrigin = parent.nodeId;\r\n            }\r\n            else {\r\n                // This is both a leaf node and the root node, so we need to\r\n                // unset the root node pointer.\r\n                index.root = 0x0;\r\n            }\r\n\r\n            // Now we zero out all of the fields on the nodeToDelete.\r\n            nodeToDelete.id = 0x0;\r\n            nodeToDelete.nodeId = 0x0;\r\n            nodeToDelete.indexId = 0x0;\r\n            nodeToDelete.value = 0;\r\n            nodeToDelete.parent = 0x0;\r\n            nodeToDelete.left = 0x0;\r\n            nodeToDelete.right = 0x0;\r\n\r\n            // Walk back up the tree rebalancing\r\n            if (rebalanceOrigin != 0x0) {\r\n                _rebalanceTree(index, rebalanceOrigin);\r\n            }\r\n        }\r\n\r\n        bytes2 constant GT = \">\";\r\n        bytes2 constant LT = \"<\";\r\n        bytes2 constant GTE = \">=\";\r\n        bytes2 constant LTE = \"<=\";\r\n        bytes2 constant EQ = \"==\";\r\n\r\n        function _compare(int left, bytes2 operator, int right) internal returns (bool) {\r\n            if (operator == GT) {\r\n                return (left > right);\r\n            }\r\n            if (operator == LT) {\r\n                return (left < right);\r\n            }\r\n            if (operator == GTE) {\r\n                return (left >= right);\r\n            }\r\n            if (operator == LTE) {\r\n                return (left <= right);\r\n            }\r\n            if (operator == EQ) {\r\n                return (left == right);\r\n            }\r\n\r\n            // Invalid operator.\r\n            throw;\r\n        }\r\n\r\n        function _getMaximum(Index storage index, bytes32 nodeId) internal returns (int) {\r\n                Node storage currentNode = index.nodes[nodeId];\r\n\r\n                while (true) {\r\n                    if (currentNode.right == 0x0) {\r\n                        return currentNode.value;\r\n                    }\r\n                    currentNode = index.nodes[currentNode.right];\r\n                }\r\n        }\r\n\r\n        function _getMinimum(Index storage index, bytes32 nodeId) internal returns (int) {\r\n                Node storage currentNode = index.nodes[nodeId];\r\n\r\n                while (true) {\r\n                    if (currentNode.left == 0x0) {\r\n                        return currentNode.value;\r\n                    }\r\n                    currentNode = index.nodes[currentNode.left];\r\n                }\r\n        }\r\n\r\n\r\n        /** @dev Query the index for the edge-most node that satisfies the\r\n         *  given query.  For >, >=, and ==, this will be the left-most node\r\n         *  that satisfies the comparison.  For < and <= this will be the\r\n         *  right-most node that satisfies the comparison.\r\n         */\r\n        /// @param index The index that should be queried\r\n        /** @param operator One of '>', '>=', '<', '<=', '==' to specify what\r\n         *  type of comparison operator should be used.\r\n         */\r\n        function query(Index storage index, bytes2 operator, int value) public returns (bytes32) {\r\n                bytes32 rootNodeId = index.root;\r\n                \r\n                if (rootNodeId == 0x0) {\r\n                    // Empty tree.\r\n                    return 0x0;\r\n                }\r\n\r\n                Node storage currentNode = index.nodes[rootNodeId];\r\n\r\n                while (true) {\r\n                    if (_compare(currentNode.value, operator, value)) {\r\n                        // We have found a match but it might not be the\r\n                        // *correct* match.\r\n                        if ((operator == LT) || (operator == LTE)) {\r\n                            // Need to keep traversing right until this is no\r\n                            // longer true.\r\n                            if (currentNode.right == 0x0) {\r\n                                return currentNode.nodeId;\r\n                            }\r\n                            if (_compare(_getMinimum(index, currentNode.right), operator, value)) {\r\n                                // There are still nodes to the right that\r\n                                // match.\r\n                                currentNode = index.nodes[currentNode.right];\r\n                                continue;\r\n                            }\r\n                            return currentNode.nodeId;\r\n                        }\r\n\r\n                        if ((operator == GT) || (operator == GTE) || (operator == EQ)) {\r\n                            // Need to keep traversing left until this is no\r\n                            // longer true.\r\n                            if (currentNode.left == 0x0) {\r\n                                return currentNode.nodeId;\r\n                            }\r\n                            if (_compare(_getMaximum(index, currentNode.left), operator, value)) {\r\n                                currentNode = index.nodes[currentNode.left];\r\n                                continue;\r\n                            }\r\n                            return currentNode.nodeId;\r\n                        }\r\n                    }\r\n\r\n                    if ((operator == LT) || (operator == LTE)) {\r\n                        if (currentNode.left == 0x0) {\r\n                            // There are no nodes that are less than the value\r\n                            // so return null.\r\n                            return 0x0;\r\n                        }\r\n                        currentNode = index.nodes[currentNode.left];\r\n                        continue;\r\n                    }\r\n\r\n                    if ((operator == GT) || (operator == GTE)) {\r\n                        if (currentNode.right == 0x0) {\r\n                            // There are no nodes that are greater than the value\r\n                            // so return null.\r\n                            return 0x0;\r\n                        }\r\n                        currentNode = index.nodes[currentNode.right];\r\n                        continue;\r\n                    }\r\n\r\n                    if (operator == EQ) {\r\n                        if (currentNode.value < value) {\r\n                            if (currentNode.right == 0x0) {\r\n                                return 0x0;\r\n                            }\r\n                            currentNode = index.nodes[currentNode.right];\r\n                            continue;\r\n                        }\r\n\r\n                        if (currentNode.value > value) {\r\n                            if (currentNode.left == 0x0) {\r\n                                return 0x0;\r\n                            }\r\n                            currentNode = index.nodes[currentNode.left];\r\n                            continue;\r\n                        }\r\n                    }\r\n                }\r\n        }\r\n\r\n        function _rebalanceTree(Index storage index, bytes32 nodeId) internal {\r\n            // Trace back up rebalancing the tree and updating heights as\r\n            // needed..\r\n            Node storage currentNode = index.nodes[nodeId];\r\n\r\n            while (true) {\r\n                int balanceFactor = _getBalanceFactor(index, currentNode.nodeId);\r\n\r\n                if (balanceFactor == 2) {\r\n                    // Right rotation (tree is heavy on the left)\r\n                    if (_getBalanceFactor(index, currentNode.left) == -1) {\r\n                        // The subtree is leaning right so it need to be\r\n                        // rotated left before the current node is rotated\r\n                        // right.\r\n                        _rotateLeft(index, currentNode.left);\r\n                    }\r\n                    _rotateRight(index, currentNode.nodeId);\r\n                }\r\n\r\n                if (balanceFactor == -2) {\r\n                    // Left rotation (tree is heavy on the right)\r\n                    if (_getBalanceFactor(index, currentNode.right) == 1) {\r\n                        // The subtree is leaning left so it need to be\r\n                        // rotated right before the current node is rotated\r\n                        // left.\r\n                        _rotateRight(index, currentNode.right);\r\n                    }\r\n                    _rotateLeft(index, currentNode.nodeId);\r\n                }\r\n\r\n                if ((-1 <= balanceFactor) && (balanceFactor <= 1)) {\r\n                    _updateNodeHeight(index, currentNode.nodeId);\r\n                }\r\n\r\n                if (currentNode.parent == 0x0) {\r\n                    // Reached the root which may be new due to tree\r\n                    // rotation, so set it as the root and then break.\r\n                    break;\r\n                }\r\n\r\n                currentNode = index.nodes[currentNode.parent];\r\n            }\r\n        }\r\n\r\n        function _getBalanceFactor(Index storage index, bytes32 nodeId) internal returns (int) {\r\n                Node storage node = index.nodes[nodeId];\r\n\r\n                return int(index.nodes[node.left].height) - int(index.nodes[node.right].height);\r\n        }\r\n\r\n        function _updateNodeHeight(Index storage index, bytes32 nodeId) internal {\r\n                Node storage node = index.nodes[nodeId];\r\n\r\n                node.height = max(index.nodes[node.left].height, index.nodes[node.right].height) + 1;\r\n        }\r\n\r\n        function _rotateLeft(Index storage index, bytes32 nodeId) internal {\r\n            Node storage originalRoot = index.nodes[nodeId];\r\n\r\n            if (originalRoot.right == 0x0) {\r\n                // Cannot rotate left if there is no right originalRoot to rotate into\r\n                // place.\r\n                throw;\r\n            }\r\n\r\n            // The right child is the new root, so it gets the original\r\n            // `originalRoot.parent` as it's parent.\r\n            Node storage newRoot = index.nodes[originalRoot.right];\r\n            newRoot.parent = originalRoot.parent;\r\n\r\n            // The original root needs to have it's right child nulled out.\r\n            originalRoot.right = 0x0;\r\n\r\n            if (originalRoot.parent != 0x0) {\r\n                // If there is a parent node, it needs to now point downward at\r\n                // the newRoot which is rotating into the place where `node` was.\r\n                Node storage parent = index.nodes[originalRoot.parent];\r\n\r\n                // figure out if we're a left or right child and have the\r\n                // parent point to the new node.\r\n                if (parent.left == originalRoot.nodeId) {\r\n                    parent.left = newRoot.nodeId;\r\n                }\r\n                if (parent.right == originalRoot.nodeId) {\r\n                    parent.right = newRoot.nodeId;\r\n                }\r\n            }\r\n\r\n\r\n            if (newRoot.left != 0) {\r\n                // If the new root had a left child, that moves to be the\r\n                // new right child of the original root node\r\n                Node storage leftChild = index.nodes[newRoot.left];\r\n                originalRoot.right = leftChild.nodeId;\r\n                leftChild.parent = originalRoot.nodeId;\r\n            }\r\n\r\n            // Update the newRoot's left node to point at the original node.\r\n            originalRoot.parent = newRoot.nodeId;\r\n            newRoot.left = originalRoot.nodeId;\r\n\r\n            if (newRoot.parent == 0x0) {\r\n                index.root = newRoot.nodeId;\r\n            }\r\n\r\n            // TODO: are both of these updates necessary?\r\n            _updateNodeHeight(index, originalRoot.nodeId);\r\n            _updateNodeHeight(index, newRoot.nodeId);\r\n        }\r\n\r\n        function _rotateRight(Index storage index, bytes32 nodeId) internal {\r\n            Node storage originalRoot = index.nodes[nodeId];\r\n\r\n            if (originalRoot.left == 0x0) {\r\n                // Cannot rotate right if there is no left node to rotate into\r\n                // place.\r\n                throw;\r\n            }\r\n\r\n            // The left child is taking the place of node, so we update it's\r\n            // parent to be the original parent of the node.\r\n            Node storage newRoot = index.nodes[originalRoot.left];\r\n            newRoot.parent = originalRoot.parent;\r\n\r\n            // Null out the originalRoot.left\r\n            originalRoot.left = 0x0;\r\n\r\n            if (originalRoot.parent != 0x0) {\r\n                // If the node has a parent, update the correct child to point\r\n                // at the newRoot now.\r\n                Node storage parent = index.nodes[originalRoot.parent];\r\n\r\n                if (parent.left == originalRoot.nodeId) {\r\n                    parent.left = newRoot.nodeId;\r\n                }\r\n                if (parent.right == originalRoot.nodeId) {\r\n                    parent.right = newRoot.nodeId;\r\n                }\r\n            }\r\n\r\n            if (newRoot.right != 0x0) {\r\n                Node storage rightChild = index.nodes[newRoot.right];\r\n                originalRoot.left = newRoot.right;\r\n                rightChild.parent = originalRoot.nodeId;\r\n            }\r\n\r\n            // Update the new root's right node to point to the original node.\r\n            originalRoot.parent = newRoot.nodeId;\r\n            newRoot.right = originalRoot.nodeId;\r\n\r\n            if (newRoot.parent == 0x0) {\r\n                index.root = newRoot.nodeId;\r\n            }\r\n\r\n            // Recompute heights.\r\n            _updateNodeHeight(index, originalRoot.nodeId);\r\n            _updateNodeHeight(index, newRoot.nodeId);\r\n        }\r\n}\r\n\r\n\r\n/// @title Grove - queryable indexes for ordered data.\r\n/// @author Piper Merriam <pipermerriam@gmail.com>\r\ncontract Grove {\r\n        /*\r\n         *  Indexes for ordered data\r\n         *\r\n         *  Address: 0x8017f24a47c889b1ee80501ff84beb3c017edf0b\r\n         */\r\n        // Map index_id to index\r\n        mapping (bytes32 => GroveLib.Index) index_lookup;\r\n\r\n        // Map node_id to index_id.\r\n        mapping (bytes32 => bytes32) node_to_index;\r\n\r\n        /// @notice Computes the id for a Grove index which is sha3(owner, indexName)\r\n        /// @param owner The address of the index owner.\r\n        /// @param indexName The name of the index.\r\n        function computeIndexId(address owner, bytes32 indexName) constant returns (bytes32) {\r\n                return GroveLib.computeIndexId(owner, indexName);\r\n        }\r\n\r\n        /// @notice Computes the id for a node in a given Grove index which is sha3(indexId, id)\r\n        /// @param indexId The id for the index the node belongs to.\r\n        /// @param id The unique identifier for the data this node represents.\r\n        function computeNodeId(bytes32 indexId, bytes32 id) constant returns (bytes32) {\r\n                return GroveLib.computeNodeId(indexId, id);\r\n        }\r\n\r\n        /*\r\n         *  Node getters\r\n         */\r\n        /// @notice Retrieves the name of an index.\r\n        /// @param indexId The id of the index.\r\n        function getIndexName(bytes32 indexId) constant returns (bytes32) {\r\n            return index_lookup[indexId].name;\r\n        }\r\n\r\n        /// @notice Retrieves the id of the root node for this index.\r\n        /// @param indexId The id of the index.\r\n        function getIndexRoot(bytes32 indexId) constant returns (bytes32) {\r\n            return index_lookup[indexId].root;\r\n        }\r\n\r\n\r\n        /// @dev Retrieve the unique identifier this node represents.\r\n        /// @param nodeId The id for the node\r\n        function getNodeId(bytes32 nodeId) constant returns (bytes32) {\r\n            return GroveLib.getNodeId(index_lookup[node_to_index[nodeId]], nodeId);\r\n        }\r\n\r\n        /// @dev Retrieve the index id for the node.\r\n        /// @param nodeId The id for the node\r\n        function getNodeIndexId(bytes32 nodeId) constant returns (bytes32) {\r\n            return GroveLib.getNodeIndexId(index_lookup[node_to_index[nodeId]], nodeId);\r\n        }\r\n\r\n        /// @dev Retrieve the value of the node.\r\n        /// @param nodeId The id for the node\r\n        function getNodeValue(bytes32 nodeId) constant returns (int) {\r\n            return GroveLib.getNodeValue(index_lookup[node_to_index[nodeId]], nodeId);\r\n        }\r\n\r\n        /// @dev Retrieve the height of the node.\r\n        /// @param nodeId The id for the node\r\n        function getNodeHeight(bytes32 nodeId) constant returns (uint) {\r\n            return GroveLib.getNodeHeight(index_lookup[node_to_index[nodeId]], nodeId);\r\n        }\r\n\r\n        /// @dev Retrieve the parent id of the node.\r\n        /// @param nodeId The id for the node\r\n        function getNodeParent(bytes32 nodeId) constant returns (bytes32) {\r\n            return GroveLib.getNodeParent(index_lookup[node_to_index[nodeId]], nodeId);\r\n        }\r\n\r\n        /// @dev Retrieve the left child id of the node.\r\n        /// @param nodeId The id for the node\r\n        function getNodeLeftChild(bytes32 nodeId) constant returns (bytes32) {\r\n            return GroveLib.getNodeLeftChild(index_lookup[node_to_index[nodeId]], nodeId);\r\n        }\r\n\r\n        /// @dev Retrieve the right child id of the node.\r\n        /// @param nodeId The id for the node\r\n        function getNodeRightChild(bytes32 nodeId) constant returns (bytes32) {\r\n            return GroveLib.getNodeRightChild(index_lookup[node_to_index[nodeId]], nodeId);\r\n        }\r\n\r\n        /** @dev Retrieve the id of the node that comes immediately before this\r\n         *  one.  Returns 0x0 if there is no previous node.\r\n         */\r\n        /// @param nodeId The id for the node\r\n        function getPreviousNode(bytes32 nodeId) constant returns (bytes32) {\r\n            return GroveLib.getPreviousNode(index_lookup[node_to_index[nodeId]], nodeId);\r\n        }\r\n\r\n        /** @dev Retrieve the id of the node that comes immediately after this\r\n         *  one.  Returns 0x0 if there is no previous node.\r\n         */\r\n        /// @param nodeId The id for the node\r\n        function getNextNode(bytes32 nodeId) constant returns (bytes32) {\r\n            return GroveLib.getNextNode(index_lookup[node_to_index[nodeId]], nodeId);\r\n        }\r\n\r\n        /** @dev Update or Insert a data element represented by the unique\r\n         *  identifier `id` into the index.\r\n         */\r\n        /// @param indexName The human readable name for the index that the node should be upserted into.\r\n        /// @param id The unique identifier that the index node represents.\r\n        /// @param value The number which represents this data elements total ordering.\r\n        function insert(bytes32 indexName, bytes32 id, int value) public {\r\n                bytes32 indexId = computeIndexId(msg.sender, indexName);\r\n                var index = index_lookup[indexId];\r\n\r\n                if (index.name != indexName) {\r\n                        // If this is a new index, store it's name and id\r\n                        index.name = indexName;\r\n                        index.id = indexId;\r\n                }\r\n\r\n                // Store the mapping from nodeId to the indexId\r\n                node_to_index[computeNodeId(indexId, id)] = indexId;\r\n\r\n                GroveLib.insert(index, id, value);\r\n        }\r\n\r\n        /// @dev Query whether a node exists within the specified index for the unique identifier.\r\n        /// @param indexId The id for the index.\r\n        /// @param id The unique identifier of the data element.\r\n        function exists(bytes32 indexId, bytes32 id) constant returns (bool) {\r\n            return GroveLib.exists(index_lookup[indexId], id);\r\n        }\r\n\r\n        /// @dev Remove the index node for the given unique identifier.\r\n        /// @param indexName The name of the index.\r\n        /// @param id The unique identifier of the data element.\r\n        function remove(bytes32 indexName, bytes32 id) public {\r\n            GroveLib.remove(index_lookup[computeIndexId(msg.sender, indexName)], id);\r\n        }\r\n\r\n        /** @dev Query the index for the edge-most node that satisfies the\r\n         * given query.  For >, >=, and ==, this will be the left-most node\r\n         * that satisfies the comparison.  For < and <= this will be the\r\n         * right-most node that satisfies the comparison.\r\n         */\r\n        /// @param indexId The id of the index that should be queried\r\n        /** @param operator One of '>', '>=', '<', '<=', '==' to specify what\r\n         *  type of comparison operator should be used.\r\n         */\r\n        function query(bytes32 indexId, bytes2 operator, int value) public returns (bytes32) {\r\n                return GroveLib.query(index_lookup[indexId], operator, value);\r\n        }\r\n}"
    }
  },
  "settings": {
    "libraries": {},
    "optimizer": {
      "runs": 200,
      "enabled": true
    },
    "compilationTarget": {
      "GroveLib.sol": "GroveLib"
    }
  }
}