summaryrefslogtreecommitdiffstatshomepage
path: root/src/lib/util/simple_set.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/util/simple_set.h')
-rw-r--r--src/lib/util/simple_set.h1780
1 files changed, 890 insertions, 890 deletions
diff --git a/src/lib/util/simple_set.h b/src/lib/util/simple_set.h
index 1a1615f5d4e..b0e2793cd76 100644
--- a/src/lib/util/simple_set.h
+++ b/src/lib/util/simple_set.h
@@ -31,656 +31,656 @@ template <class T> class simple_set_iterator;
// PUBLIC OPERATIONS:
// size, empty, clear, insert, remove, find, contains, merge, & assignment.
//
-
+
template <class T>
class simple_set
{
- friend class simple_set_iterator<T>;
- typedef avl_tree_node<T> tree_node;
+ friend class simple_set_iterator<T>;
+ typedef avl_tree_node<T> tree_node;
public:
- // Construction
- simple_set(resource_pool &pool = global_resource_pool())
- : m_root(NULL),
- m_pool(pool)
- { }
+ // Construction
+ simple_set(resource_pool &pool = global_resource_pool())
+ : m_root(NULL),
+ m_pool(pool)
+ { }
- simple_set(const simple_set& rhs)
- : m_root(NULL)
- {
- *this = rhs;
- }
+ simple_set(const simple_set& rhs)
+ : m_root(NULL)
+ {
+ *this = rhs;
+ }
- ~simple_set()
- {
- clear();
- }
+ ~simple_set()
+ {
+ clear();
+ }
- // A reference to the resource pool
+ // A reference to the resource pool
resource_pool &pool() const { return m_pool; }
- // Returns number of elements in the tree -- O(n)
- int size() const
- {
- if (empty()) return 0;
-
- const tree_node* currentNode = m_root;
- const int nodeCount = sizeRecurse(currentNode);
- return nodeCount;
- }
-
-
- // Test for emptiness -- O(1).
- bool empty() const
- {
- return m_root == NULL;
- }
-
-
- // Empty the tree -- O(n).
- void clear()
- {
- clearRecurse(m_root);
- }
-
-
- // Insert x into the avl tree; duplicates are ignored -- O(log n).
- bool insert(const T& x)
- {
- bool retVal = insert(x, m_root);
-
- // Whether the node was successfully inserted or not (i.e. wasn't a duplicate)
- return retVal;
- }
-
-
- // Remove x from the tree. Nothing is done if x is not found -- O(n).
- bool remove(const T& x)
- {
- // First find the node in the tree
- tree_node* currNode = find(x, m_root);
-
- // Only do this when the current node is valid
- if (currNode)
- {
- // See if it's a leaf
- if (currNode->isLeaf())
- {
- // If we're a leaf and we have no parent, then the tree will be emptied
- if (!currNode->parent)
- {
- m_root = NULL;
- }
-
- // If it's a leaf node, simply remove it
- removeNode(currNode);
- pool_free(m_pool, currNode);
- }
- else
- {
- // Get the parent object
- tree_node* parentNode = currNode->parent;
-
- // Remove the child and reconnect the smallest node in the right sub tree
- // (in order successor)
- tree_node* replaceNode = findMin(currNode->right);
-
- // See if there's even a right-most node
- if (!replaceNode)
- {
- // Get the largest node on the left (because the right doesn't exist)
- replaceNode = findMax(currNode->left);
- }
-
- // Disconnect the replacement node's branch
- removeNode(replaceNode);
-
- // Disconnect the current node
- removeNode(currNode);
-
- // Get the current node's left and right branches
- tree_node* left = currNode->left;
- tree_node* right = currNode->right;
-
- // We no longer need this node
- pool_free(m_pool, currNode);
-
- // Check to see if we removed the root node
- if (!parentNode)
- {
- // Merge the branches into the parent node of what we deleted
- merge(replaceNode, parentNode);
- merge(left, parentNode);
- merge(right, parentNode);
-
- // Now we're the the root
- m_root = parentNode;
- }
- else
- {
- // Merge the branches into the parent node of what we
- // deleted, we let the merge algorithm decide where to
- // put the branches
- merge(replaceNode, parentNode);
- merge(left, parentNode);
- merge(right, parentNode);
- }
- }
-
- // Balance the tree
- balanceTree();
-
- // The node was found and removed successfully
- return true;
- }
- else
- {
- // The node was not found
- return false;
- }
- }
-
-
- // Find item x in the tree. Returns a pointer to the matching item
- // or NULL if not found -- O(log n)
- T* find(const T& x) const
- {
- tree_node* found = find(x, m_root);
- if (found == NULL) return NULL;
- return &found->element;
- }
-
-
- // Is the data present in the set? -- O(log n)
- bool contains(const T& x) const
- {
- if (find(x) != NULL)
- return true;
- else
- return false;
- }
-
-
- // Merge a different tree with ours -- O(n).
- bool merge(const simple_set<T>& b)
- {
- tree_node* c = b->clone();
- bool retVal = merge(c->m_root, m_root);
-
- // Re-balance the tree if the merge was successful
- if (retVal)
- {
- balanceTree();
- }
- else
- {
- pool_free(m_pool, c);
- }
-
- return retVal;
- }
-
-
- // Replace this set with another -- O(n)
- const simple_set& operator=(const simple_set& rhs)
- {
- // Don't clone if it's the same pointer
- if (this != &rhs)
- {
- clear();
-
- m_root = clone(rhs.m_root);
- }
-
- return *this;
- }
+ // Returns number of elements in the tree -- O(n)
+ int size() const
+ {
+ if (empty()) return 0;
+
+ const tree_node* currentNode = m_root;
+ const int nodeCount = sizeRecurse(currentNode);
+ return nodeCount;
+ }
+
+
+ // Test for emptiness -- O(1).
+ bool empty() const
+ {
+ return m_root == NULL;
+ }
+
+
+ // Empty the tree -- O(n).
+ void clear()
+ {
+ clearRecurse(m_root);
+ }
+
+
+ // Insert x into the avl tree; duplicates are ignored -- O(log n).
+ bool insert(const T& x)
+ {
+ bool retVal = insert(x, m_root);
+
+ // Whether the node was successfully inserted or not (i.e. wasn't a duplicate)
+ return retVal;
+ }
+
+
+ // Remove x from the tree. Nothing is done if x is not found -- O(n).
+ bool remove(const T& x)
+ {
+ // First find the node in the tree
+ tree_node* currNode = find(x, m_root);
+
+ // Only do this when the current node is valid
+ if (currNode)
+ {
+ // See if it's a leaf
+ if (currNode->isLeaf())
+ {
+ // If we're a leaf and we have no parent, then the tree will be emptied
+ if (!currNode->parent)
+ {
+ m_root = NULL;
+ }
+
+ // If it's a leaf node, simply remove it
+ removeNode(currNode);
+ pool_free(m_pool, currNode);
+ }
+ else
+ {
+ // Get the parent object
+ tree_node* parentNode = currNode->parent;
+
+ // Remove the child and reconnect the smallest node in the right sub tree
+ // (in order successor)
+ tree_node* replaceNode = findMin(currNode->right);
+
+ // See if there's even a right-most node
+ if (!replaceNode)
+ {
+ // Get the largest node on the left (because the right doesn't exist)
+ replaceNode = findMax(currNode->left);
+ }
+
+ // Disconnect the replacement node's branch
+ removeNode(replaceNode);
+
+ // Disconnect the current node
+ removeNode(currNode);
+
+ // Get the current node's left and right branches
+ tree_node* left = currNode->left;
+ tree_node* right = currNode->right;
+
+ // We no longer need this node
+ pool_free(m_pool, currNode);
+
+ // Check to see if we removed the root node
+ if (!parentNode)
+ {
+ // Merge the branches into the parent node of what we deleted
+ merge(replaceNode, parentNode);
+ merge(left, parentNode);
+ merge(right, parentNode);
+
+ // Now we're the the root
+ m_root = parentNode;
+ }
+ else
+ {
+ // Merge the branches into the parent node of what we
+ // deleted, we let the merge algorithm decide where to
+ // put the branches
+ merge(replaceNode, parentNode);
+ merge(left, parentNode);
+ merge(right, parentNode);
+ }
+ }
+
+ // Balance the tree
+ balanceTree();
+
+ // The node was found and removed successfully
+ return true;
+ }
+ else
+ {
+ // The node was not found
+ return false;
+ }
+ }
+
+
+ // Find item x in the tree. Returns a pointer to the matching item
+ // or NULL if not found -- O(log n)
+ T* find(const T& x) const
+ {
+ tree_node* found = find(x, m_root);
+ if (found == NULL) return NULL;
+ return &found->element;
+ }
+
+
+ // Is the data present in the set? -- O(log n)
+ bool contains(const T& x) const
+ {
+ if (find(x) != NULL)
+ return true;
+ else
+ return false;
+ }
+
+
+ // Merge a different tree with ours -- O(n).
+ bool merge(const simple_set<T>& b)
+ {
+ tree_node* c = b->clone();
+ bool retVal = merge(c->m_root, m_root);
+
+ // Re-balance the tree if the merge was successful
+ if (retVal)
+ {
+ balanceTree();
+ }
+ else
+ {
+ pool_free(m_pool, c);
+ }
+
+ return retVal;
+ }
+
+
+ // Replace this set with another -- O(n)
+ const simple_set& operator=(const simple_set& rhs)
+ {
+ // Don't clone if it's the same pointer
+ if (this != &rhs)
+ {
+ clear();
+
+ m_root = clone(rhs.m_root);
+ }
+
+ return *this;
+ }
#ifdef SIMPLE_SET_DEBUG
- // Debug -- O(n log n)
- void printTree(std::ostream& out = std::cout) const
- {
- if(empty())
- {
- out << "Empty tree" << std::endl;
- }
- else
- {
- printTree(out, m_root);
- }
- }
+ // Debug -- O(n log n)
+ void printTree(std::ostream& out = std::cout) const
+ {
+ if(empty())
+ {
+ out << "Empty tree" << std::endl;
+ }
+ else
+ {
+ printTree(out, m_root);
+ }
+ }
#endif
private:
- // The AVL tree's root
- tree_node* m_root;
-
- // Resource pool where objects are freed
- resource_pool& m_pool;
-
-
- // Find a node in the tree
- tree_node* findNode(const T& x) const
- {
- tree_node* node = find(x, m_root);
- if (node)
- {
- return node;
- }
- else
- {
- return NULL;
- }
- }
-
-
- // Insert item x into a subtree t (root) -- O(log n)
- bool insert(const T& x, tree_node*& t)
- {
- if (t == NULL)
- {
- t = pool_alloc(m_pool, tree_node(x, NULL, NULL, NULL));
-
- // An empty sub-tree here, insertion successful
- return true;
- }
- else if (x < t->element)
- {
- // O(log n)
- bool retVal = insert(x, t->left);
-
- if (retVal)
- {
- t->left->setParent(t);
- if(t->balanceFactor() < -1)
- {
- // See if it went left of the left
- if(x < t->left->element)
- {
- rotateWithLeftChild(t);
- }
- else
- {
- // The element goes on the right of the left
- doubleWithLeftChild(t);
- }
- }
- }
-
- return retVal;
- }
- else if (t->element < x)
- {
- bool retVal = insert(x, t->right);
-
- // Only do this if the insertion was successful
- if (retVal)
- {
- t->right->setParent(t);
-
- if (t->balanceFactor() > 1)
- {
- // See if it went right of the right
- if(t->right->element < x)
- {
- rotateWithRightChild(t);
- }
- else
- {
- // The element goes on the left of the right
- doubleWithRightChild(t);
- }
- }
- }
-
- return retVal;
- }
- else
- {
- return false; // Duplicate
- }
- }
-
-
- // Recursively free all nodes in the tree -- O(n).
- void clearRecurse(tree_node*& t) const
- {
- if(t != NULL)
- {
- clearRecurse(t->left);
- clearRecurse(t->right);
-
- pool_free(m_pool, t);
- }
- t = NULL;
- }
-
-
- // Merge a tree with this one. Private because external care is required.
- bool merge(tree_node* b, tree_node*& t)
- {
- if (!b)
- {
- return false;
- }
- else
- {
- bool retVal = false;
-
- if (t == NULL)
- {
- // Set this element to that subtree
- t = b;
-
- // The parent here should be NULL anyway, but we
- // set it just to be sure. This pointer will be
- // used as a flag to indicate where in the call
- // stack the tree was actually set.
- //
- // The middle layers of this method's call will
- // all have their parent references in tact since
- // no operations took place there.
- //
- //t->parent = NULL;
- t->setParent(NULL);
-
- // We were successful in merging
- retVal = true;
- }
- else if (b->element < t->element)
- {
- retVal = merge(b, t->left);
-
- // Only do this if the insertion actually took place
- if (retVal && !t->left->parent)
- {
- t->left->setParent(t);
- }
- }
- else if (t->element < b->element)
- {
- retVal = merge(b, t->right);
-
- // Only do this if the insertion was successful
- if (retVal && !t->right->parent)
- {
- t->right->setParent(t);
- }
-
- return retVal;
- }
-
- return retVal;
- }
- }
-
-
- // Find the smallest item's node in a subtree t -- O(log n).
- tree_node* findMin(tree_node* t) const
- {
- if(t == NULL)
- {
- return t;
- }
-
- while(t->left != NULL)
- {
- t = t->left;
- }
-
- return t;
- }
-
-
- // Find the smallest item's node in a subtree t -- O(log n).
- tree_node* findMax(tree_node* t) const
- {
- if(t == NULL)
- {
- return t;
- }
-
- while(t->right != NULL)
- {
- t = t->right;
- }
-
- return t;
- }
-
-
- // Find item x's node in subtree t -- O(log n)
- tree_node* find(const T& x, tree_node* t) const
- {
- while(t != NULL)
- {
- if (x < t->element)
- {
- t = t->left;
- }
- else if (t->element < x)
- {
- t = t->right;
- }
- else
- {
- return t; // Match
- }
- }
-
- return NULL; // No match
- }
-
-
- // Clone a subtree -- O(n)
- tree_node* clone(const tree_node* t) const
- {
- if(t == NULL)
- {
- return NULL;
- }
- else
- {
- // Create a node with the left and right nodes and a parent set to NULL
- tree_node* retVal = pool_alloc(m_pool, tree_node(t->element, NULL, clone(t->left), clone(t->right)));
-
- // Now set our children's parent node reference
- if (retVal->left) { retVal->left->setParent(retVal); }
- if (retVal->right) { retVal->right->setParent(retVal); }
-
- return retVal;
- }
- }
-
-
- // Rotate binary tree node with left child.
- // Single rotation for case 1 -- O(1).
- void rotateWithLeftChild(tree_node*& k2) const
- {
- tree_node* k1 = k2->left;
- tree_node* k2Parent = k2->parent;
-
- k2->setLeft(k1->right);
- if (k2->left) { k2->left->setParent(k2); }
-
- k1->setRight(k2);
- if (k1->right) { k1->right->setParent(k1); }
-
- k2 = k1;
- k2->setParent(k2Parent);
- }
-
-
- // Rotate binary tree node with right child.
- // Single rotation for case 4 -- O(1).
- void rotateWithRightChild(tree_node*& k1) const
- {
- tree_node* k2 = k1->right;
- tree_node* k1Parent = k1->parent;
-
- k1->setRight(k2->left);
- if (k1->right) { k1->right->setParent(k1); }
-
- k2->setLeft(k1);
- if (k2->left) { k2->left->setParent(k2); }
-
- k1 = k2;
- k1->setParent(k1Parent);
- }
-
-
- // Double rotate binary tree node: first left child
- // with its right child; then node k3 with new left child.
- // Double rotation for case 2 -- O(1).
- void doubleWithLeftChild(tree_node*& k3) const
- {
- rotateWithRightChild(k3->left);
- rotateWithLeftChild(k3);
- }
-
-
- // Double rotate binary tree node: first right child
- // with its left child; then node k1 with new right child.
- // Double rotation for case 3 -- O(1).
- void doubleWithRightChild(tree_node*& k1) const
- {
- rotateWithLeftChild(k1->right);
- rotateWithRightChild(k1);
- }
-
-
- // Removes a node. Returns true if the node was on the left side of its parent -- O(1).
- void removeNode(tree_node*& node)
- {
- // It is a leaf, simply remove the item and disconnect the parent
- if (node->isLeft())
- {
- node->parent->setLeft(NULL);
- }
- else // (node == node->parent->right)
- {
- if (node->parent) { node->parent->setRight(NULL); }
- }
-
- node->setParent(NULL);
- }
-
-
- // Swap one node with another -- O(1).
- void replaceNode(tree_node*& node1, tree_node*& node2)
- {
- // Save both parent references
- simple_set<T>* node1Parent = node1->parent;
- simple_set<T>* node2Parent = node2->parent;
-
- // First move node2 into node1's place
- if (node1Parent)
- {
- if (isLeft(node1))
- {
- node1Parent->setLeft(node2);
- }
- else // node1 is on the right
- {
- node1Parent->setRight(node2);
- }
- }
- node2->setParent(node1Parent);
-
- // Now move node1 into node2's place
- if (node2Parent)
- {
- if (isLeft(node2))
- {
- node2Parent->setLeft(node1);
- }
- else // node2 is on the right
- {
- node2Parent->setRight(node1);
- }
- }
- node1->setParent(node2Parent);
- }
-
-
- // Balances the tree starting at the root node
- void balanceTree() { balanceTree(m_root); }
-
-
- // Balance the tree starting at the given node -- O(n).
- void balanceTree(tree_node*& node)
- {
- if (node)
- {
- // First see what the balance factor for this node is
- int balFactor = node->balanceFactor();
-
- if (balFactor < -1)
- {
- // See if we're heavy left of the left
- if(node->left->balanceFactor() < 0)
- {
- rotateWithLeftChild(node);
- }
- else // if (node->left->balanceFactor() > 0)
- {
- // We're heavy on the right of the left
- doubleWithLeftChild(node);
- }
- }
- else if (balFactor > 1)
- {
- // See if it we're heavy right of the right
- if(node->right->balanceFactor() > 0)
- {
- rotateWithRightChild(node);
- }
- else // if (node->right->balanceFactor() < 0)
- {
- // The element goes on the left of the right
- doubleWithRightChild(node);
- }
- }
- else // if (balFactor >= -1 && balFactor <= 1)
- {
- // We're balanced here, but are our children balanced?
- balanceTree(node->left);
- balanceTree(node->right);
- }
- }
- }
-
-
- // Recursive helper function for public size()
- int sizeRecurse(const tree_node* currentNode) const
- {
- int nodeCount = 1;
- if (currentNode->left != NULL)
- nodeCount += sizeRecurse(currentNode->left);
- if (currentNode->right != NULL)
- nodeCount += sizeRecurse(currentNode->right);
- return nodeCount;
- }
+ // The AVL tree's root
+ tree_node* m_root;
+
+ // Resource pool where objects are freed
+ resource_pool& m_pool;
+
+
+ // Find a node in the tree
+ tree_node* findNode(const T& x) const
+ {
+ tree_node* node = find(x, m_root);
+ if (node)
+ {
+ return node;
+ }
+ else
+ {
+ return NULL;
+ }
+ }
+
+
+ // Insert item x into a subtree t (root) -- O(log n)
+ bool insert(const T& x, tree_node*& t)
+ {
+ if (t == NULL)
+ {
+ t = pool_alloc(m_pool, tree_node(x, NULL, NULL, NULL));
+
+ // An empty sub-tree here, insertion successful
+ return true;
+ }
+ else if (x < t->element)
+ {
+ // O(log n)
+ bool retVal = insert(x, t->left);
+
+ if (retVal)
+ {
+ t->left->setParent(t);
+ if(t->balanceFactor() < -1)
+ {
+ // See if it went left of the left
+ if(x < t->left->element)
+ {
+ rotateWithLeftChild(t);
+ }
+ else
+ {
+ // The element goes on the right of the left
+ doubleWithLeftChild(t);
+ }
+ }
+ }
+
+ return retVal;
+ }
+ else if (t->element < x)
+ {
+ bool retVal = insert(x, t->right);
+
+ // Only do this if the insertion was successful
+ if (retVal)
+ {
+ t->right->setParent(t);
+
+ if (t->balanceFactor() > 1)
+ {
+ // See if it went right of the right
+ if(t->right->element < x)
+ {
+ rotateWithRightChild(t);
+ }
+ else
+ {
+ // The element goes on the left of the right
+ doubleWithRightChild(t);
+ }
+ }
+ }
+
+ return retVal;
+ }
+ else
+ {
+ return false; // Duplicate
+ }
+ }
+
+
+ // Recursively free all nodes in the tree -- O(n).
+ void clearRecurse(tree_node*& t) const
+ {
+ if(t != NULL)
+ {
+ clearRecurse(t->left);
+ clearRecurse(t->right);
+
+ pool_free(m_pool, t);
+ }
+ t = NULL;
+ }
+
+
+ // Merge a tree with this one. Private because external care is required.
+ bool merge(tree_node* b, tree_node*& t)
+ {
+ if (!b)
+ {
+ return false;
+ }
+ else
+ {
+ bool retVal = false;
+
+ if (t == NULL)
+ {
+ // Set this element to that subtree
+ t = b;
+
+ // The parent here should be NULL anyway, but we
+ // set it just to be sure. This pointer will be
+ // used as a flag to indicate where in the call
+ // stack the tree was actually set.
+ //
+ // The middle layers of this method's call will
+ // all have their parent references in tact since
+ // no operations took place there.
+ //
+ //t->parent = NULL;
+ t->setParent(NULL);
+
+ // We were successful in merging
+ retVal = true;
+ }
+ else if (b->element < t->element)
+ {
+ retVal = merge(b, t->left);
+
+ // Only do this if the insertion actually took place
+ if (retVal && !t->left->parent)
+ {
+ t->left->setParent(t);
+ }
+ }
+ else if (t->element < b->element)
+ {
+ retVal = merge(b, t->right);
+
+ // Only do this if the insertion was successful
+ if (retVal && !t->right->parent)
+ {
+ t->right->setParent(t);
+ }
+
+ return retVal;
+ }
+
+ return retVal;
+ }
+ }
+
+
+ // Find the smallest item's node in a subtree t -- O(log n).
+ tree_node* findMin(tree_node* t) const
+ {
+ if(t == NULL)
+ {
+ return t;
+ }
+
+ while(t->left != NULL)
+ {
+ t = t->left;
+ }
+
+ return t;
+ }
+
+
+ // Find the smallest item's node in a subtree t -- O(log n).
+ tree_node* findMax(tree_node* t) const
+ {
+ if(t == NULL)
+ {
+ return t;
+ }
+
+ while(t->right != NULL)
+ {
+ t = t->right;
+ }
+
+ return t;
+ }
+
+
+ // Find item x's node in subtree t -- O(log n)
+ tree_node* find(const T& x, tree_node* t) const
+ {
+ while(t != NULL)
+ {
+ if (x < t->element)
+ {
+ t = t->left;
+ }
+ else if (t->element < x)
+ {
+ t = t->right;
+ }
+ else
+ {
+ return t; // Match
+ }
+ }
+
+ return NULL; // No match
+ }
+
+
+ // Clone a subtree -- O(n)
+ tree_node* clone(const tree_node* t) const
+ {
+ if(t == NULL)
+ {
+ return NULL;
+ }
+ else
+ {
+ // Create a node with the left and right nodes and a parent set to NULL
+ tree_node* retVal = pool_alloc(m_pool, tree_node(t->element, NULL, clone(t->left), clone(t->right)));
+
+ // Now set our children's parent node reference
+ if (retVal->left) { retVal->left->setParent(retVal); }
+ if (retVal->right) { retVal->right->setParent(retVal); }
+
+ return retVal;
+ }
+ }
+
+
+ // Rotate binary tree node with left child.
+ // Single rotation for case 1 -- O(1).
+ void rotateWithLeftChild(tree_node*& k2) const
+ {
+ tree_node* k1 = k2->left;
+ tree_node* k2Parent = k2->parent;
+
+ k2->setLeft(k1->right);
+ if (k2->left) { k2->left->setParent(k2); }
+
+ k1->setRight(k2);
+ if (k1->right) { k1->right->setParent(k1); }
+
+ k2 = k1;
+ k2->setParent(k2Parent);
+ }
+
+
+ // Rotate binary tree node with right child.
+ // Single rotation for case 4 -- O(1).
+ void rotateWithRightChild(tree_node*& k1) const
+ {
+ tree_node* k2 = k1->right;
+ tree_node* k1Parent = k1->parent;
+
+ k1->setRight(k2->left);
+ if (k1->right) { k1->right->setParent(k1); }
+
+ k2->setLeft(k1);
+ if (k2->left) { k2->left->setParent(k2); }
+
+ k1 = k2;
+ k1->setParent(k1Parent);
+ }
+
+
+ // Double rotate binary tree node: first left child
+ // with its right child; then node k3 with new left child.
+ // Double rotation for case 2 -- O(1).
+ void doubleWithLeftChild(tree_node*& k3) const
+ {
+ rotateWithRightChild(k3->left);
+ rotateWithLeftChild(k3);
+ }
+
+
+ // Double rotate binary tree node: first right child
+ // with its left child; then node k1 with new right child.
+ // Double rotation for case 3 -- O(1).
+ void doubleWithRightChild(tree_node*& k1) const
+ {
+ rotateWithLeftChild(k1->right);
+ rotateWithRightChild(k1);
+ }
+
+
+ // Removes a node. Returns true if the node was on the left side of its parent -- O(1).
+ void removeNode(tree_node*& node)
+ {
+ // It is a leaf, simply remove the item and disconnect the parent
+ if (node->isLeft())
+ {
+ node->parent->setLeft(NULL);
+ }
+ else // (node == node->parent->right)
+ {
+ if (node->parent) { node->parent->setRight(NULL); }
+ }
+
+ node->setParent(NULL);
+ }
+
+
+ // Swap one node with another -- O(1).
+ void replaceNode(tree_node*& node1, tree_node*& node2)
+ {
+ // Save both parent references
+ simple_set<T>* node1Parent = node1->parent;
+ simple_set<T>* node2Parent = node2->parent;
+
+ // First move node2 into node1's place
+ if (node1Parent)
+ {
+ if (isLeft(node1))
+ {
+ node1Parent->setLeft(node2);
+ }
+ else // node1 is on the right
+ {
+ node1Parent->setRight(node2);
+ }
+ }
+ node2->setParent(node1Parent);
+
+ // Now move node1 into node2's place
+ if (node2Parent)
+ {
+ if (isLeft(node2))
+ {
+ node2Parent->setLeft(node1);
+ }
+ else // node2 is on the right
+ {
+ node2Parent->setRight(node1);
+ }
+ }
+ node1->setParent(node2Parent);
+ }
+
+
+ // Balances the tree starting at the root node
+ void balanceTree() { balanceTree(m_root); }
+
+
+ // Balance the tree starting at the given node -- O(n).
+ void balanceTree(tree_node*& node)
+ {
+ if (node)
+ {
+ // First see what the balance factor for this node is
+ int balFactor = node->balanceFactor();
+
+ if (balFactor < -1)
+ {
+ // See if we're heavy left of the left
+ if(node->left->balanceFactor() < 0)
+ {
+ rotateWithLeftChild(node);
+ }
+ else // if (node->left->balanceFactor() > 0)
+ {
+ // We're heavy on the right of the left
+ doubleWithLeftChild(node);
+ }
+ }
+ else if (balFactor > 1)
+ {
+ // See if it we're heavy right of the right
+ if(node->right->balanceFactor() > 0)
+ {
+ rotateWithRightChild(node);
+ }
+ else // if (node->right->balanceFactor() < 0)
+ {
+ // The element goes on the left of the right
+ doubleWithRightChild(node);
+ }
+ }
+ else // if (balFactor >= -1 && balFactor <= 1)
+ {
+ // We're balanced here, but are our children balanced?
+ balanceTree(node->left);
+ balanceTree(node->right);
+ }
+ }
+ }
+
+
+ // Recursive helper function for public size()
+ int sizeRecurse(const tree_node* currentNode) const
+ {
+ int nodeCount = 1;
+ if (currentNode->left != NULL)
+ nodeCount += sizeRecurse(currentNode->left);
+ if (currentNode->right != NULL)
+ nodeCount += sizeRecurse(currentNode->right);
+ return nodeCount;
+ }
#ifdef SIMPLE_SET_DEBUG
- // Debug. Print from the start node, down -- O(n log n).
- void printTree(std::ostream& out, tree_node* t=NULL, int numTabs=0, char lr='_') const
- {
- if(t != NULL)
- {
- for (int i =0; i < numTabs; i++) { out << " "; } out << "|_" << lr << "__ ";
- out << t->element << " {h = " << t->height() << ", b = " << t->balanceFactor() << "} ";
- // TODO: Reinstate out << std::hex << t << " (p = " << t->parent << ")" << std::dec;
- out << std::endl;
-
- printTree(out, t->left, numTabs + 1, '<');
- printTree(out, t->right, numTabs + 1, '>');
- }
- }
+ // Debug. Print from the start node, down -- O(n log n).
+ void printTree(std::ostream& out, tree_node* t=NULL, int numTabs=0, char lr='_') const
+ {
+ if(t != NULL)
+ {
+ for (int i =0; i < numTabs; i++) { out << " "; } out << "|_" << lr << "__ ";
+ out << t->element << " {h = " << t->height() << ", b = " << t->balanceFactor() << "} ";
+ // TODO: Reinstate out << std::hex << t << " (p = " << t->parent << ")" << std::dec;
+ out << std::endl;
+
+ printTree(out, t->left, numTabs + 1, '<');
+ printTree(out, t->right, numTabs + 1, '>');
+ }
+ }
#endif
};
@@ -692,149 +692,149 @@ private:
template <class T> class avl_tree_node
{
- friend class simple_set<T>;
- friend class simple_set_iterator<T>;
- typedef avl_tree_node<T> tree_node;
+ friend class simple_set<T>;
+ friend class simple_set_iterator<T>;
+ typedef avl_tree_node<T> tree_node;
public:
- // Construction
- avl_tree_node(const T& theElement, avl_tree_node* p, avl_tree_node* lt, avl_tree_node* rt)
- : element(theElement),
- parent(p),
- left(lt),
- right(rt),
- m_height(1),
- m_balanceFactor(0)
- { }
-
-
- // Are we to our parent's left?
- bool isLeft()
- {
- if (parent && this == parent->left)
- {
- return true;
- }
- else
- {
- return false;
- }
- }
-
-
- // Are we a leaf node?
- bool isLeaf() { return !left && !right; }
-
-
- // Set the parent pointer
- void setParent(tree_node* p)
- {
- // Set our new parent
- parent = p;
-
- // If we have a valid parent, set its height
- if (parent)
- {
- // Set the parent's height to include this tree. If the parent
- // already has a tree that is taller than the one we're attaching
- // then the parent's height remains unchanged
- int rightHeight = (parent->right ? parent->right->m_height : 0);
- int leftHeight = (parent->left ? parent->left->m_height : 0);
-
- // The height of the tallest branch + 1
- parent->m_height = maxInt(rightHeight, leftHeight) + 1;
-
- // Also set the balance factor
- parent->m_balanceFactor = rightHeight - leftHeight;
- }
- }
-
-
- // Set the left child pointer
- void setLeft(tree_node* l)
- {
- // Set our new left node
- left = l;
-
- // Set the height and balance factor
- int rightHeight = (right ? right->m_height : 0);
- int leftHeight = (left ? left->m_height : 0);
-
- m_height = maxInt(rightHeight, leftHeight) + 1;
- m_balanceFactor = (right ? right->m_height : 0) - (left ? left->m_height : 0);
- }
-
-
- // Set the right child pointer
- void setRight(tree_node* r)
- {
- // Set our new right node
- right = r;
-
- // Set the height and balance factor
- int rightHeight = (right ? right->m_height : 0);
- int leftHeight = (left ? left->m_height : 0);
-
- m_height = maxInt(rightHeight, leftHeight) + 1;
- m_balanceFactor = (right ? right->m_height : 0) - (left ? left->m_height : 0);
- }
-
-
- // Recover the height
- int height() const
- {
- // The height is equal to the maximum of the right or left side's height plus 1
- // Trading memory for operation time can be done O(n) like this =>
- // return max(left ? left->height() : 0, right ? right->height() : 0) + 1;
- return m_height;
- }
-
-
- // Recover the balance factor
- int balanceFactor() const
- {
- // The weight of a node is equal to the difference between
- // the weight of the left subtree and the weight of the
- // right subtree
- //
- // O(n) version =>
- // return (right ? right->height() : 0) - (left ? left->height() : 0);
- //
- return m_balanceFactor;
- }
+ // Construction
+ avl_tree_node(const T& theElement, avl_tree_node* p, avl_tree_node* lt, avl_tree_node* rt)
+ : element(theElement),
+ parent(p),
+ left(lt),
+ right(rt),
+ m_height(1),
+ m_balanceFactor(0)
+ { }
+
+
+ // Are we to our parent's left?
+ bool isLeft()
+ {
+ if (parent && this == parent->left)
+ {
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+ }
+
+
+ // Are we a leaf node?
+ bool isLeaf() { return !left && !right; }
+
+
+ // Set the parent pointer
+ void setParent(tree_node* p)
+ {
+ // Set our new parent
+ parent = p;
+
+ // If we have a valid parent, set its height
+ if (parent)
+ {
+ // Set the parent's height to include this tree. If the parent
+ // already has a tree that is taller than the one we're attaching
+ // then the parent's height remains unchanged
+ int rightHeight = (parent->right ? parent->right->m_height : 0);
+ int leftHeight = (parent->left ? parent->left->m_height : 0);
+
+ // The height of the tallest branch + 1
+ parent->m_height = maxInt(rightHeight, leftHeight) + 1;
+
+ // Also set the balance factor
+ parent->m_balanceFactor = rightHeight - leftHeight;
+ }
+ }
+
+
+ // Set the left child pointer
+ void setLeft(tree_node* l)
+ {
+ // Set our new left node
+ left = l;
+
+ // Set the height and balance factor
+ int rightHeight = (right ? right->m_height : 0);
+ int leftHeight = (left ? left->m_height : 0);
+
+ m_height = maxInt(rightHeight, leftHeight) + 1;
+ m_balanceFactor = (right ? right->m_height : 0) - (left ? left->m_height : 0);
+ }
+
+
+ // Set the right child pointer
+ void setRight(tree_node* r)
+ {
+ // Set our new right node
+ right = r;
+
+ // Set the height and balance factor
+ int rightHeight = (right ? right->m_height : 0);
+ int leftHeight = (left ? left->m_height : 0);
+
+ m_height = maxInt(rightHeight, leftHeight) + 1;
+ m_balanceFactor = (right ? right->m_height : 0) - (left ? left->m_height : 0);
+ }
+
+
+ // Recover the height
+ int height() const
+ {
+ // The height is equal to the maximum of the right or left side's height plus 1
+ // Trading memory for operation time can be done O(n) like this =>
+ // return max(left ? left->height() : 0, right ? right->height() : 0) + 1;
+ return m_height;
+ }
+
+
+ // Recover the balance factor
+ int balanceFactor() const
+ {
+ // The weight of a node is equal to the difference between
+ // the weight of the left subtree and the weight of the
+ // right subtree
+ //
+ // O(n) version =>
+ // return (right ? right->height() : 0) - (left ? left->height() : 0);
+ //
+ return m_balanceFactor;
+ }
private:
- // Calculates all of the heights for this node and its ancestors -- O(log n).
- void calcHeights()
- {
- // Calculate our own height -- O(1)
- m_height = maxInt(left ? left->m_height : 0, right ? right->m_height : 0) + 1;
+ // Calculates all of the heights for this node and its ancestors -- O(log n).
+ void calcHeights()
+ {
+ // Calculate our own height -- O(1)
+ m_height = maxInt(left ? left->m_height : 0, right ? right->m_height : 0) + 1;
- // And our parent's height (and recurse) -- O(log n)
- if (parent)
- {
- parent->calcHeights();
- }
- }
+ // And our parent's height (and recurse) -- O(log n)
+ if (parent)
+ {
+ parent->calcHeights();
+ }
+ }
- // Utility function - TODO replace
- int maxInt(const int& lhs, const int& rhs) const
- {
- return lhs > rhs ? lhs : rhs;
- }
+ // Utility function - TODO replace
+ int maxInt(const int& lhs, const int& rhs) const
+ {
+ return lhs > rhs ? lhs : rhs;
+ }
private:
- T element;
+ T element;
- avl_tree_node* parent;
- avl_tree_node* left;
- avl_tree_node* right;
+ avl_tree_node* parent;
+ avl_tree_node* left;
+ avl_tree_node* right;
- int m_height;
- int m_balanceFactor;
+ int m_height;
+ int m_balanceFactor;
};
@@ -850,146 +850,146 @@ private:
template <class T>
class simple_set_iterator
{
- typedef avl_tree_node<T> tree_node;
+ typedef avl_tree_node<T> tree_node;
public:
- enum TraversalType { PRE_ORDER, IN_ORDER, POST_ORDER, LEVEL_ORDER };
+ enum TraversalType { PRE_ORDER, IN_ORDER, POST_ORDER, LEVEL_ORDER };
public:
- // construction
- simple_set_iterator(simple_set<T>& set, const TraversalType& tt=IN_ORDER)
- : m_set(&set),
- m_traversalType(tt),
- m_currentNode(NULL),
- m_endNode(NULL) { }
-
- ~simple_set_iterator() { }
-
-
- // getters
- T* current() const { return m_currentNode; }
-
-
- // reset and return first item
- T* first()
- {
- m_currentNode = m_set->m_root;
- switch (m_traversalType)
- {
- case IN_ORDER:
- {
- // The current node is the smallest value
- m_currentNode = m_set->findMin(m_set->m_root);
-
- // The end case is the largest value
- m_endNode = m_set->findMax(m_set->m_root);
-
- return &m_currentNode->element;
- }
-
- default:
- {
- // TODO (better error message):
- printf("simple_set_iterator: Traversal type not yet supported.\n");
- return NULL;
- }
- }
- return NULL;
- }
-
-
- T* last()
- {
- return NULL;
- }
-
-
- // advance according to current state and traversal type
- T* next()
- {
- if (m_currentNode == NULL) return NULL;
-
- switch (m_traversalType)
- {
- case IN_ORDER:
- {
- // You are at the end
- if (m_currentNode == m_endNode)
- return NULL;
-
- if (m_currentNode->right != NULL)
- {
- // Gather the furthest left node of right subtree
- m_currentNode = m_currentNode->right;
- while (m_currentNode->left != NULL)
- {
- m_currentNode = m_currentNode->left;
- }
- }
- else
- {
- // No right subtree? Move up the tree, looking for a left child link.
- tree_node* p = m_currentNode->parent;
- while (p != NULL && m_currentNode == p->right)
- {
- m_currentNode = p;
- p = p->parent;
- }
- m_currentNode = p;
- }
-
- return &m_currentNode->element;
- }
-
- default:
- {
- // TODO (better error message):
- printf("simple_set_iterator: Traversal type not yet supported.\n");
- return NULL;
- }
- }
-
- return NULL;
- }
-
-
- // return the number of items available
- int count()
- {
- return m_set->size();
- }
-
-
- // return the index of a given item in the virtual list
- // note: this function is destructive to any in-progress iterations!
- int indexof(T inData)
- {
- int index = 0;
- for (T* data = first(); data != last(); data = next(), index++)
- if (!(*data < inData) && !(inData < *data))
- return index;
- return -1;
- }
-
-
- // return the indexed item in the list
- // note: this function is destructive to any in-progress iterations!
- T* byindex(int index)
- {
- int count = 0;
- for (T* data = first(); data != last(); data = next(), count++)
- if (count == index)
- return data;
- return NULL;
- }
+ // construction
+ simple_set_iterator(simple_set<T>& set, const TraversalType& tt=IN_ORDER)
+ : m_set(&set),
+ m_traversalType(tt),
+ m_currentNode(NULL),
+ m_endNode(NULL) { }
+
+ ~simple_set_iterator() { }
+
+
+ // getters
+ T* current() const { return m_currentNode; }
+
+
+ // reset and return first item
+ T* first()
+ {
+ m_currentNode = m_set->m_root;
+ switch (m_traversalType)
+ {
+ case IN_ORDER:
+ {
+ // The current node is the smallest value
+ m_currentNode = m_set->findMin(m_set->m_root);
+
+ // The end case is the largest value
+ m_endNode = m_set->findMax(m_set->m_root);
+
+ return &m_currentNode->element;
+ }
+
+ default:
+ {
+ // TODO (better error message):
+ printf("simple_set_iterator: Traversal type not yet supported.\n");
+ return NULL;
+ }
+ }
+ return NULL;
+ }
+
+
+ T* last()
+ {
+ return NULL;
+ }
+
+
+ // advance according to current state and traversal type
+ T* next()
+ {
+ if (m_currentNode == NULL) return NULL;
+
+ switch (m_traversalType)
+ {
+ case IN_ORDER:
+ {
+ // You are at the end
+ if (m_currentNode == m_endNode)
+ return NULL;
+
+ if (m_currentNode->right != NULL)
+ {
+ // Gather the furthest left node of right subtree
+ m_currentNode = m_currentNode->right;
+ while (m_currentNode->left != NULL)
+ {
+ m_currentNode = m_currentNode->left;
+ }
+ }
+ else
+ {
+ // No right subtree? Move up the tree, looking for a left child link.
+ tree_node* p = m_currentNode->parent;
+ while (p != NULL && m_currentNode == p->right)
+ {
+ m_currentNode = p;
+ p = p->parent;
+ }
+ m_currentNode = p;
+ }
+
+ return &m_currentNode->element;
+ }
+
+ default:
+ {
+ // TODO (better error message):
+ printf("simple_set_iterator: Traversal type not yet supported.\n");
+ return NULL;
+ }
+ }
+
+ return NULL;
+ }
+
+
+ // return the number of items available
+ int count()
+ {
+ return m_set->size();
+ }
+
+
+ // return the index of a given item in the virtual list
+ // note: this function is destructive to any in-progress iterations!
+ int indexof(T inData)
+ {
+ int index = 0;
+ for (T* data = first(); data != last(); data = next(), index++)
+ if (!(*data < inData) && !(inData < *data))
+ return index;
+ return -1;
+ }
+
+
+ // return the indexed item in the list
+ // note: this function is destructive to any in-progress iterations!
+ T* byindex(int index)
+ {
+ int count = 0;
+ for (T* data = first(); data != last(); data = next(), count++)
+ if (count == index)
+ return data;
+ return NULL;
+ }
private:
- simple_set<T>* m_set;
+ simple_set<T>* m_set;
- TraversalType m_traversalType;
- tree_node* m_currentNode;
- tree_node* m_endNode;
+ TraversalType m_traversalType;
+ tree_node* m_currentNode;
+ tree_node* m_endNode;
};
#endif