+
+ // 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);
+ }
+ };