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;h=7bacfb183585206193f73878fbcb1988fb42abb7;hp=3b98b5e0c636faa8d2e8ab47a20c98fdd737cb70;hb=d517c9171aa7115786ff52fc35f3402e190afce9;hpb=7da27a216a7f4bb3331fe315cdbec69bfcf2c762

diff --git a/include/c++/util/rbtree.h b/include/c++/util/rbtree.h
index 3b98b5e..7bacfb1 100644
--- a/include/c++/util/rbtree.h
+++ b/include/c++/util/rbtree.h
@@ -2,31 +2,15 @@
 //
 // This software is copyright (c) 2006 Scott Wood <scott@buserror.net>.
 // 
-// Permission is hereby granted, free of charge, to any person obtaining a copy of
-// this software and associated documentation files (the "Software"), to deal with
-// the Software without restriction, including without limitation the rights to
-// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
-// of the Software, and to permit persons to whom the Software is furnished to do
-// so, subject to the following conditions:
+// This software is provided 'as-is', without any express or implied warranty.
+// In no event will the authors or contributors be held liable for any damages
+// arising from the use of this software.
 // 
-//     * Redistributions of source code must retain the above copyright notice,
-//       this list of conditions and the following disclaimers.
-// 
-//     * Redistributions in binary form must reproduce the above copyright notice,
-//       this list of conditions and the following disclaimers in the
-//       documentation and/or other materials provided with the distribution.
-// 
-//     * The names of the Software's authors and/or contributors
-//       may not be used to endorse or promote products derived from
-//       this Software without specific prior written permission.
-// 
-// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
-// FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
-// CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
-// SOFTWARE.
+// Permission is hereby granted to everyone, free of charge, to use, copy,
+// modify, prepare derivative works of, publish, distribute, perform,
+// sublicense, and/or sell copies of the Software, provided that the above
+// copyright notice and disclaimer of warranty be included in all copies or
+// substantial portions of this software.
 
 #ifndef _UTIL_RBTREE_H
 #define _UTIL_RBTREE_H
@@ -386,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)
@@ -549,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