//
// 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 condition:
+// 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.
//
-// The above copyright notice and this permission notice shall be
-// included in all copies or substantial portions of the Software.
-//
-// 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
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)
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