Contract 0x7c1eb207c07e...3d0fa478d034

{
  "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: 0x7c1eb207c07e7ab13cf245585bd03d0fa478d034\r\n         */\r\n        struct Index {\r\n                bytes32 root;\r\n                mapping (bytes32 => Node) nodes;\r\n        }\r\n\r\n        struct Node {\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        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 id The id for the node to be looked up.\r\n        function getNodeId(Index storage index, bytes32 id) constant returns (bytes32) {\r\n            return index.nodes[id].id;\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 id The id for the node to be looked up.\r\n        function getNodeValue(Index storage index, bytes32 id) constant returns (int) {\r\n            return index.nodes[id].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 id The id for the node to be looked up.\r\n        function getNodeHeight(Index storage index, bytes32 id) constant returns (uint) {\r\n            return index.nodes[id].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 id The id for the node to be looked up.\r\n        function getNodeParent(Index storage index, bytes32 id) constant returns (bytes32) {\r\n            return index.nodes[id].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 id The id for the node to be looked up.\r\n        function getNodeLeftChild(Index storage index, bytes32 id) constant returns (bytes32) {\r\n            return index.nodes[id].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 id The id for the node to be looked up.\r\n        function getNodeRightChild(Index storage index, bytes32 id) constant returns (bytes32) {\r\n            return index.nodes[id].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 id The id for the node to be looked up.\r\n        function getPreviousNode(Index storage index, bytes32 id) constant returns (bytes32) {\r\n            Node storage currentNode = index.nodes[id];\r\n\r\n            if (currentNode.id == 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.id;\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.id) {\r\n                        return parent.id;\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 id The id for the node to be looked up.\r\n        function getNextNode(Index storage index, bytes32 id) constant returns (bytes32) {\r\n            Node storage currentNode = index.nodes[id];\r\n\r\n            if (currentNode.id == 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.id;\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.id) {\r\n                        return parent.id;\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                if (index.nodes[id].id == id) {\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[id].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                if (index.root == 0x0) {\r\n                    index.root = id;\r\n                }\r\n                Node storage currentNode = index.nodes[index.root];\r\n\r\n                // Do insertion\r\n                while (true) {\r\n                    if (currentNode.id == 0x0) {\r\n                        // This is a new unpopulated node.\r\n                        currentNode.id = id;\r\n                        currentNode.parent = previousNodeId;\r\n                        currentNode.value = value;\r\n                        break;\r\n                    }\r\n\r\n                    // Set the previous node id.\r\n                    previousNodeId = currentNode.id;\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 = id;\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 = id;\r\n                    }\r\n                    currentNode = index.nodes[currentNode.left];\r\n                }\r\n\r\n                // Rebalance the tree\r\n                _rebalanceTree(index, currentNode.id);\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            return (index.nodes[id].height > 0);\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            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[id];\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.id)];\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.id)];\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.id;\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.id) {\r\n                    parent.left = replacementNode.right;\r\n                    if (replacementNode.right != 0x0) {\r\n                        child = index.nodes[replacementNode.right];\r\n                        child.parent = parent.id;\r\n                    }\r\n                }\r\n                if (parent.right == replacementNode.id) {\r\n                    parent.right = replacementNode.left;\r\n                    if (replacementNode.left != 0x0) {\r\n                        child = index.nodes[replacementNode.left];\r\n                        child.parent = parent.id;\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.id) {\r\n                        parent.left = replacementNode.id;\r\n                    }\r\n                    if (parent.right == nodeToDelete.id) {\r\n                        parent.right = replacementNode.id;\r\n                    }\r\n                }\r\n                else {\r\n                    // If the node we are deleting is the root node update the\r\n                    // index root node pointer.\r\n                    index.root = replacementNode.id;\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.id;\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.id;\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.id) {\r\n                    parent.left = 0x0;\r\n                }\r\n                if (parent.right == nodeToDelete.id) {\r\n                    parent.right = 0x0;\r\n                }\r\n\r\n                // keep note of where the rebalancing should begin.\r\n                rebalanceOrigin = parent.id;\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.value = 0;\r\n            nodeToDelete.parent = 0x0;\r\n            nodeToDelete.left = 0x0;\r\n            nodeToDelete.right = 0x0;\r\n            nodeToDelete.height = 0;\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 id) internal returns (int) {\r\n                Node storage currentNode = index.nodes[id];\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 id) internal returns (int) {\r\n                Node storage currentNode = index.nodes[id];\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.id;\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.id;\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.id;\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.id;\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 id) internal {\r\n            // Trace back up rebalancing the tree and updating heights as\r\n            // needed..\r\n            Node storage currentNode = index.nodes[id];\r\n\r\n            while (true) {\r\n                int balanceFactor = _getBalanceFactor(index, currentNode.id);\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.id);\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.id);\r\n                }\r\n\r\n                if ((-1 <= balanceFactor) && (balanceFactor <= 1)) {\r\n                    _updateNodeHeight(index, currentNode.id);\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 id) internal returns (int) {\r\n                Node storage node = index.nodes[id];\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 id) internal {\r\n                Node storage node = index.nodes[id];\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 id) internal {\r\n            Node storage originalRoot = index.nodes[id];\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.id) {\r\n                    parent.left = newRoot.id;\r\n                }\r\n                if (parent.right == originalRoot.id) {\r\n                    parent.right = newRoot.id;\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.id;\r\n                leftChild.parent = originalRoot.id;\r\n            }\r\n\r\n            // Update the newRoot's left node to point at the original node.\r\n            originalRoot.parent = newRoot.id;\r\n            newRoot.left = originalRoot.id;\r\n\r\n            if (newRoot.parent == 0x0) {\r\n                index.root = newRoot.id;\r\n            }\r\n\r\n            // TODO: are both of these updates necessary?\r\n            _updateNodeHeight(index, originalRoot.id);\r\n            _updateNodeHeight(index, newRoot.id);\r\n        }\r\n\r\n        function _rotateRight(Index storage index, bytes32 id) internal {\r\n            Node storage originalRoot = index.nodes[id];\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.id) {\r\n                    parent.left = newRoot.id;\r\n                }\r\n                if (parent.right == originalRoot.id) {\r\n                    parent.right = newRoot.id;\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.id;\r\n            }\r\n\r\n            // Update the new root's right node to point to the original node.\r\n            originalRoot.parent = newRoot.id;\r\n            newRoot.right = originalRoot.id;\r\n\r\n            if (newRoot.parent == 0x0) {\r\n                index.root = newRoot.id;\r\n            }\r\n\r\n            // Recompute heights.\r\n            _updateNodeHeight(index, originalRoot.id);\r\n            _updateNodeHeight(index, newRoot.id);\r\n        }\r\n}"
    }
  },
  "settings": {
    "libraries": {},
    "optimizer": {
      "runs": 200,
      "enabled": true
    },
    "compilationTarget": {
      "GroveLib.sol": "GroveLib"
    }
  }
}