rbtree: silence parentheses warning

[polintos/scott/priv.git] / include / c++ / util / rbtree.h

diff --git a/include/c++/util/rbtree.h b/include/c++/util/rbtree.h
index 7f835bf9490b3a7b37c03f3afde8f5489569ac36..7bacfb183585206193f73878fbcb1988fb42abb7 100644 (file)
--- a/include/c++/util/rbtree.h
+++ b/include/c++/util/rbtree.h
@@ -370,7 +370,8 @@ public:
                        return;
                }
                
-               assert(n->parent->value < n->value != n->value < n->parent->value);
+               assert((n->parent->value < n->value) != 
+                      (n->value < n->parent->value));
                n->red = true;
 
                if (!n->parent->red)
@@ -533,6 +534,95 @@ public:
                        rotate_left(parent);
                }
        }
+
+       // RBPtr is a Pointer->Value associative array, and RBInt is an
+       // Integer->Value associative array.
+
+       template<typename Ptr, typename Val>
+       struct RBPtrNode {
+               typedef RBTree<RBPtrNode, Ptr, Ptr> Tree;
+               typename Tree::Node rbtree_node;
+               Val value;
+               
+               intptr_t operator < (RBPtrNode &other)
+               {
+                       return (intptr_t)other.rbtree_node.value -
+                              (intptr_t)rbtree_node.value;
+               }
+
+               intptr_t operator > (RBPtrNode &other)
+               {
+                       return (intptr_t)rbtree_node.value -
+                              (intptr_t)other.rbtree_node.value;
+               }
+
+               operator Val &()
+               {
+                       return value;
+               }
+       };
+
+       template<typename Ptr, typename Val>
+       struct RBPtr : public RBTree<RBPtrNode<Ptr, Val>, Ptr, Ptr>
+       {
+               typedef RBPtrNode<Ptr, Val> Node;
+               typedef RBTree<Node, Ptr, Ptr> Tree;
+       
+               void add(Ptr ptr, Val &val)
+               {
+                       Node *node = new Node;
+                       node->value = val;
+                       node->rbtree_node.value = ptr;
+                       Tree::add(node);
+               }
+               
+               void del(Ptr ptr)
+               {
+                       delete find(ptr);
+               }
+       };
+
+       template<typename Int, typename Val>
+       struct RBIntNode {
+               typedef RBTree<RBIntNode, Int, Int> Tree;
+               typename Tree::Node rbtree_node;
+               Val value;
+               
+               intptr_t operator < (RBIntNode &other)
+               {
+                       return other.rbtree_node.value - rbtree_node.value;
+               }
+
+               intptr_t operator > (RBIntNode &other)
+               {
+                       return rbtree_node.value - other.rbtree_node.value;
+               }
+               
+               operator Val &()
+               {
+                       return value;
+               }
+       };
+
+       template<typename Int, typename Val>
+       struct RBInt : public RBTree<RBIntNode<Int, Val>, Int, Int>
+       {
+               typedef RBIntNode<Int, Val> Node;
+               typedef RBTree<Node, Int, Int> Tree;
+       
+               void add(Int key, Val &val)
+               {
+                       Node *node = new Node;
+                       node->value = val;
+                       node->rbtree_node.value = key;
+                       Tree::add(node);
+               }
+               
+               void del(Int key)
+               {
+                       delete find(key);
+               }
+       };
 }
 
 #endif