X-Git-Url: http://git.buserror.net/cgi-bin/gitweb.cgi?p=polintos%2Fscott%2Fpriv.git;a=blobdiff_plain;f=include%2Fc%2B%2B%2Futil%2Frbtree.h;fp=include%2Fc%2B%2B%2Futil%2Frbtree.h;h=8885e1238dc78320b711a63e01f29dc33b042754;hp=7f835bf9490b3a7b37c03f3afde8f5489569ac36;hb=1ac390fe1e18444008857b056c947710be9621a8;hpb=6e64b28821757af60447c790ae52a91831a9d4f0

diff --git a/include/c++/util/rbtree.h b/include/c++/util/rbtree.h
index 7f835bf..8885e12 100644
--- a/include/c++/util/rbtree.h
+++ b/include/c++/util/rbtree.h
@@ -533,6 +533,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