Equivilent of STL Set in D ? ...
clayasaurus
clayasaurus at gmail.com
Mon Oct 23 06:38:41 PDT 2006
KlausO wrote:
> KlausO wrote:
>>
>> Seems to be an interesting task to get used to the new foreach
>> features. I'll give it a try.
>>
>> Klaus
>
> Ok, I rewrote the intrusive version to a nonintrusive one.
> It has almost the interface you mentioned.
>
> Please note: IMHO, there are some points where the template
> needs some refinement.
>
> 1. A third template parameter "bool duplicatesAllowed" should be
> added and handled in insert/remove via "static if". Then you
> have multisets at hand !
>
> 2. Sometimes it exposes an interface to the internally used nodes
> to be able to access the key/value pairs. A special iterator
> class which could encapsulate the "not found/not inserted"
> state would be better.
>
> 3. The insert via opIndexAssign/find via opIndex is IMHO not
> optimal because you could not return the "not found/not inserted"
> state. There are some possibilities to resolve this:
>
> a) Throw an exception (IMHO, ugly)
> b) Return an empty node
> c) ... any ideas ?
>
> Using insert like
> if (foo.insert("Jill", 13))
> looks better to me.
>
> Ok, thats it for now. Maybe I find some spare time next week
> to adress some of the issues.
> Greets
>
> Klaus
>
>
> ------------------------------------------------------------------------
>
> //////////////////////////////////////////////////////////////////////////
> /**
>
> Autors: Klaus Oberhofer
>
> License: use it for your own purpose
>
> */////////////////////////////////////////////////////////////////////////
> module redblacktree;
>
> enum NodeColor
> {
> RedNode = 0,
> BlackNode = 1
> };
>
> //////////////////////////////////////////////////////////////////////////
> /**
>
> Red/black tree implementation.
>
> */////////////////////////////////////////////////////////////////////////
> class RedBlackTree(KeyType, ValueType)
> {
> public:
> /// TreeNode type used to form red/black tree
> static class TreeNode
> {
> package:
> TreeNode left;
> TreeNode right;
> NodeColor color;
>
> KeyType key;
> ValueType value;
>
> package:
> this(KeyType key, ValueType value)
> {
> this.key = key;
> this.value = value;
>
> left = right = null;
> color = NodeColor.RedNode;
> }
>
> public:
> KeyType nkey() { return this.key; }
> ValueType nvalue() { return this.value; }
> }
>
> private:
> // The PtrPack struct is used to to save function-calling overhead
> struct PtrPack
> {
> TreeNode t; // The current node
> TreeNode p; // Parent
> TreeNode g; // Grandparent
> TreeNode gg; // Great Grandparent
> TreeNode s; // Sibling
> TreeNode rs; // Right children of s
> TreeNode ls; // Left children of s
> TreeNode m; // Matching node
> TreeNode pm; // Parent of matching node
> };
>
> // the tree root
> TreeNode root;
>
>
> // Helper functions
> static TreeNode InsBalance (TreeNode tree, PtrPack pp)
> {
> TreeNode cofgg; // New child of great-grandparent
> int side;
>
> side = pp.gg && pp.gg.right is pp.g;
>
> if (pp.g.left is pp.p)
> {
> if (pp.p.right is pp.t)
> { // Do double rotate
> pp.g.left = pp.t.right;
> pp.t.right = pp.g;
> pp.p.right = pp.t.left;
> pp.t.left = pp.p;
> pp.p = pp.gg;
> cofgg = pp.t;
> }
> else
> { // Do single rotate right
> pp.g.left = pp.p.right;
> pp.p.right = pp.g;
> cofgg = pp.p;
> }
> }
> else
> { // pp.g.right is pp.p
> if (pp.p.left is pp.t)
> { // Do double rotate
> pp.g.right = pp.t.left;
> pp.t.left = pp.g;
> pp.p.left = pp.t.right;
> pp.t.right = pp.p;
> pp.p = pp.gg;
> cofgg = pp.t;
> }
> else
> { // Do single rotate left
> pp.g.right = pp.p.left;
> pp.p.left = pp.g;
> cofgg = pp.p;
> }
> }
>
> cofgg.color = NodeColor.BlackNode;
> pp.g.color = NodeColor.RedNode;
>
> if (pp.gg)
> {
> if (side)
> pp.gg.right = cofgg;
> else
> pp.gg.left = cofgg;
> }
> else tree = cofgg;
>
> return tree;
> }
>
> static TreeNode DoReplacement(TreeNode tree, PtrPack pp)
> {
> // At this point, pp.m is the node to delete, pp.pm is it's parent,
> // pp.p is the replacement node, pp.g is it's parent. If pp.m has no
> // successor, pp.p will = pp.m, and replacement is the non-null
> // child of pp.m.
>
> if (pp.m)
> { // Matching node was found
> if (pp.p is pp.m ||
> pp.m.left is null ||
> pp.m.right is null)
> {
> // No successor, and/or at least one child null
> // Get non-null child, if any, else pp.p will be null
> pp.p = (pp.m.left) ? pp.m.left : pp.m.right;
> }
> else
> {
> // pp.m has a successor to use as a replacement
> if (pp.g !is pp.m)
> {
> // Successor is not immediate child of pp.m, so detach
> // from where it is, attach to where pp.m is
> pp.g.left = pp.p.right;
> pp.p.right = pp.m.right;
> }
> // Finish attaching where pp.m is.
> pp.p.left = pp.m.left;
> }
> // pp.p should have same color as pp.m since it's going where pp.m was
> if (pp.p)
> pp.p.color = pp.m.color;
> }
>
> // Fixup pp.pm child link to be pp.p
> if (pp.m)
> {
> if (pp.pm)
> {
> if (pp.pm.left is pp.m)
> pp.pm.left = pp.p;
> else
> pp.pm.right = pp.p;
> }
> else
> tree = pp.p; // New root, possibly null
> }
> return tree;
> }
>
> static TreeNode DelBalance (TreeNode tree, PtrPack pp)
> {
> if ((pp.t is null ||
> pp.t.color == NodeColor.BlackNode) &&
> pp.s !is null &&
> pp.s.color == NodeColor.RedNode)
> {
> // Case: pp.t is black, pp.s red. pp.t might be null,
> // but pp.s and pp.p must not be.
>
> // Fix pp.g child to be pp.s. Also pp.s may become pp.p of pp.m
> if (pp.g)
> {
> if (pp.g.left is pp.p)
> pp.g.left = pp.s;
> else
> pp.g.right = pp.s;
> }
> else
> tree = pp.s;
>
> if (pp.p is pp.m)
> pp.pm = pp.s;
>
> // Finish rotating
> if (pp.p.left is pp.t)
> {
> // RotateLeft(pp.p);
> pp.p.right = pp.ls;
> pp.s.left = pp.p;
> pp.g = pp.s;
> pp.s = pp.ls;
> }
> else
> {
> // RotateRight(pp.p);
> pp.p.left = pp.rs;
> pp.s.right = pp.p;
> pp.g = pp.s;
> pp.s = pp.rs;
> }
>
> // Fixup children of pp.s
> if (pp.s)
> {
> pp.ls = pp.s.left;
> pp.rs = pp.s.right;
> }
>
> // Fixup colors
> pp.p.color = NodeColor.RedNode;
> pp.g.color = NodeColor.BlackNode;
> }
>
> if (pp.t &&
> pp.t.color == NodeColor.BlackNode &&
> (pp.t.left is null ||
> pp.t.left.color == NodeColor.BlackNode) &&
> (pp.t.right is null ||
> pp.t.right.color == NodeColor.BlackNode))
> {
> // Case: pp.t is a single binary node with two black children.
> if (pp.s &&
> pp.s.color == NodeColor.BlackNode &&
> (pp.s.left is null ||
> pp.s.left.color == NodeColor.BlackNode) &&
> (pp.s.right is null ||
> pp.s.right.color == NodeColor.BlackNode))
> {
>
> // Case: pp.t and pp.s are single binary nodes with two black children..
> pp.p.color = NodeColor.BlackNode;
> pp.t.color = NodeColor.RedNode;
> pp.s.color = NodeColor.RedNode;
>
> }
> else if (pp.ls && pp.ls.color == NodeColor.RedNode)
> {
>
> // Case: Tree is a single binary node with two black children.
> // pp.s is pair of binary nodes-one red, one black or pp.s is a set
> // of three binary nodes with a black parent and red child nodes.
> // pp.ls is red or pp.rs might be red.
>
> if (pp.p.left is pp.t)
> {
> // Fix colors
> pp.ls.color = pp.p.color;
> pp.p.color = NodeColor.BlackNode;
> pp.t.color = NodeColor.RedNode;
> // Fix pp.g child to be pp.ls. ALSo pp.ls may become pp.p of pp.m
> if (pp.g)
> {
> if (pp.g.left is pp.p)
> pp.g.left = pp.ls;
> else
> pp.g.right = pp.ls;
> }
> else tree = pp.ls;
> if (pp.p is pp.m) pp.pm = pp.ls;
>
> // Finish: DoubleRotateLeft(pp.s, pp.p);
> pp.p.right = pp.ls.left;
> pp.ls.left = pp.p;
> pp.s.left = pp.ls.right;
> pp.ls.right= pp.s;
> pp.g = pp.ls;
> // Do not fix pp.s or pp.ls since they get reassigned
> // at the top of next loop
> }
> else
> {
> // Fix colors
> pp.s.color = pp.p.color;
> pp.ls.color = NodeColor.BlackNode;
> pp.p.color = NodeColor.BlackNode;
> pp.t.color = NodeColor.RedNode;
> // Fix pp.g child to be pp.s. Also pp.s may become pp.p of pp.m
> if (pp.g)
> {
> if (pp.g.left is pp.p)
> pp.g.left = pp.s;
> else
> pp.g.right = pp.s;
> }
> else tree = pp.s;
> if (pp.p is pp.m) pp.pm = pp.s;
> // Finish: RotateRight(pp.p);
> pp.p.left = pp.rs;
> pp.s.right = pp.p;
> pp.g = pp.s;
> // Do not fix pp.s or pp.ls since they get reassigned
> // at the top of next loop
> }
> }
> else if (pp.rs && pp.rs.color == NodeColor.RedNode)
> {
> // Case: pp.t is a single binary node with two black children.
> // pp.s is a pair of binary nodes-one red, one black.
> // pp.ls is black, pp.rs is red.
>
> if (pp.p.left is pp.t)
> {
> // Fix colors
> pp.rs.color = NodeColor.BlackNode;
> pp.s.color = pp.p.color;
> pp.p.color = NodeColor.BlackNode;
> pp.t.color = NodeColor.RedNode;
> // Fix pp.g child to be pp.s. Also, pp.s may become pp.p of pp.m
> if (pp.g)
> {
> if (pp.g.left is pp.p)
> pp.g.left = pp.s;
> else
> pp.g.right = pp.s;
> }
> else tree = pp.s;
> if (pp.p is pp.m) pp.pm = pp.s;
> // Finish: RotateLeft(pp.p);
> pp.p.right = pp.ls;
> pp.s.left = pp.p;
> pp.g = pp.s;
> // Do not fix pp.s or pp.ls since they get reassigned
> // at the top of next loop
> }
> else
> {
> // Fix colors
> pp.rs.color = pp.p.color;
> pp.p.color = NodeColor.BlackNode;
> pp.t.color = NodeColor.RedNode;
> // Fix pp.g child to become pp.rs. ALSo, pp.rs may become pp.p of pp.m.
> if (pp.g)
> {
> if (pp.g.left is pp.p)
> pp.g.left = pp.rs;
> else
> pp.g.right = pp.rs;
> }
> else tree = pp.rs;
> if (pp.p is pp.m) pp.pm = pp.rs;
> // Finish: DoubleRotateRight(pp.s, pp.p);
> pp.p.left = pp.rs.right;
> pp.rs.right = pp.p;
> pp.s.right = pp.rs.left;
> pp.rs.left = pp.s;
> pp.g = pp.rs;
> // Do not fix pp.s or pp.ls since they get reassigned
> // at the top of next loop
> }
> }
> }
> return tree;
> }
>
> /// returns height of tree at node root
> int height(TreeNode tree)
> {
> int h = 0;
> if (tree !is null)
> {
> int lh = height(tree.left);
> int rh = height(tree.right);
> h = ((lh > rh) ? lh : rh) + 1;
> }
> return h;
> }
>
> /// returns number of nodes within tree
> int count (TreeNode tree)
> {
> int n = 0;
> if (tree !is null)
> {
> ++n;
> n += count(tree.left);
> n += count(tree.right);
> }
> return n;
> }
>
> /// get child node with "minimum" value
> TreeNode getMin(TreeNode tree)
> {
> if (tree !is null)
> {
> while(tree.right) tree = tree.right;
> }
> return tree;
> }
>
> /// get child node with "maximum" value
> TreeNode getMax (TreeNode tree)
> {
> if (tree !is null)
> {
> while(tree.left) tree = tree.left;
> }
> return tree;
> }
>
> /// insert child node into tree
> bool insert(TreeNode node)
> in
> {
> assert(node);
>
> // add only new nodes
> assert(node.left is null);
> assert(node.right is null);
> }
> body
> {
> bool bInserted = false;
>
> PtrPack pp;
> int side;
>
> pp.t = root;
> pp.p = null;
> pp.g = null;
> pp.gg = null;
>
> while ((pp.t !is null) && (node.key != pp.t.key))
> {
> // If on a set of three binary nodes with a black
> // parent node and red child nodes, split it into
> // two single binary nodes with two black children.
> if (((pp.t.left !is null) && (pp.t.left.color == NodeColor.RedNode)) &&
> ((pp.t.right !is null) && (pp.t.right.color == NodeColor.RedNode)))
> {
> pp.t.color = NodeColor.RedNode;
> pp.t.left.color = NodeColor.BlackNode;
> pp.t.right.color = NodeColor.BlackNode;
>
> // Check for two reds in a row, and adjust if so
> if ((pp.p !is null) && (pp.p.color == NodeColor.RedNode))
> {
> root = InsBalance(root, pp);
> }
> }
> pp.gg = pp.g;
> pp.g = pp.p;
> pp.p = pp.t;
>
> // go to left if node < current node
> if (node.key < pp.t.key)
> {
> pp.t = pp.t.left;
> side = 0;
> }
> else
> {
> pp.t = pp.t.right;
> side = 1;
> }
> }
>
> // Reached the bottom, with no matching node
> if (pp.t is null)
> {
> bInserted = true;
>
> // now insert node
> //
> pp.t = node;
> pp.t.color = NodeColor.RedNode;
>
> if (pp.t is null) return 0; // Couldn't add
> if (pp.p)
> {
> if (side)
> {
> pp.p.right = pp.t;
> }
> else
> {
> pp.p.left = pp.t;
> }
> }
> else
> root = pp.t;
>
> // Check for two reds in a row, and adjust if so
> if (pp.p && pp.p.color == NodeColor.RedNode)
> {
> root = InsBalance(root, pp);
> }
> }
>
> // root always made black
> root.color = NodeColor.BlackNode;
>
> return bInserted;
> }
>
> // traverse tree in ascending order
> int applyForward(TreeNode tree, int delegate(inout TreeNode) dg)
> {
> int result = 0;
> while(tree)
> {
> result = applyForward(tree.left, dg);
> if (result) return result;
>
> result = dg(tree);
> if (result) return result;
>
> tree = tree.right;
> }
>
> return result;
> }
>
> // traverse tree in descending order
> int applyReverse(TreeNode tree, int delegate(inout TreeNode) dg)
> {
> int result = 0;
> while(tree)
> {
> result = applyReverse(tree.right, dg);
> if (result) return result;
>
> result = dg(tree);
> if (result) return result;
>
> tree = tree.left;
> }
>
> return result;
> }
>
> // public interface
> public:
> // insert value at position of key
> bool insert(KeyType key, ValueType value)
> {
> // create a new node
> TreeNode node = new TreeNode(key, value);
>
> return insert(node);
> }
>
> // support insertion via operator
> // e.g. persons["Mary"] = 30;
> ValueType opIndexAssign(ValueType value, KeyType key)
> {
> insert(key, value);
>
> return value;
> }
>
> // support find via operator
> // e.g. int age = persons["Mary"];
> ValueType opIndex(KeyType key)
> {
> TreeNode node = find(key);
> return node.value;
> }
>
> /// remove child node which matches key from the tree
> TreeNode remove(in KeyType compare)
> {
> PtrPack pp;
>
> if (root is null) return null;
>
> pp.t = root;
> pp.p = null;
> pp.g = null;
> pp.m = null;
> pp.pm = null;
>
> while (pp.t)
> {
> // Go down the tree one level, searching for node to delete
> if (pp.t.key == compare)
> {
> pp.m = pp.t; // Record matching node
> pp.pm = pp.p; // And it's parent
> }
>
> // Update ancestor pointers
> pp.g = pp.p;
> pp.p = pp.t;
>
> if (pp.t.key > compare)
> {
> pp.t = pp.p.left;
> pp.s = pp.p.right;
> }
> else
> {
> // Walk down even if it matches, to look for successor
> pp.t = pp.p.right;
> pp.s = pp.p.left;
> }
>
> if (pp.s)
> {
> pp.ls = pp.s.left;
> pp.rs = pp.s.right;
> }
> else
> {
> pp.ls = null;
> pp.rs = null;
> }
> root = DelBalance(root, pp);
> }
>
> root = DoReplacement(root, pp);
> if (root)
> root.color = NodeColor.BlackNode;
>
> // clear connection to tree
> if (pp.m)
> {
> pp.m.left = null;
> pp.m.right = null;
> }
>
> return pp.m; // TreeNode to delete
> }
>
> /// find child node which matches key
> TreeNode find(in KeyType compare)
> {
> TreeNode t = root;
> while (t)
> {
> if (t.key == compare)
> break;
>
> t = ((t.key > compare) ? t.left : t.right);
> }
> return t;
> }
>
> /// find child node which is "above" given key
> TreeNode findUpper(in KeyType compare)
> {
> TreeNode t = root;
> TreeNode erg = null;
> while (t)
> {
> if (t.key > compare)
> {
> // if (t > key) -> remember it
> // and descend left subtree
> erg = t;
> t = t.left;
> }
> else
> {
> // if (t < key) descend right subtree
> t = t.right;
> }
> }
> return erg;
> }
>
> /// find child node which is "below" given key
> TreeNode findLower (in KeyType compare)
> {
> TreeNode t = root;
> TreeNode erg = null;
> while (t)
> {
> if (t.key < compare)
> {
> // if (t < key) -> remember it
> // and descend right subtree
> erg = t;
> t = t.right;
> }
> else
> {
> // if (t >= key) descend left subtree
> t = t.left;
> }
> }
> return erg;
> }
>
> /// find child node which is above or equal to the given key
> TreeNode findUpperOrEq (in KeyType compare)
> {
> TreeNode t = root;
> TreeNode erg = null;
> while (t)
> {
> if (t.key < compare)
> {
> // if (t < key) descend right subtree
> t = t.right;
> }
> else
> {
> // if (t >= key) -> remember it
> // and descend left subtree
> erg = t;
> t = t.left;
> }
> }
> return erg;
> }
>
> /// find child node which is below or equal to the given key
> TreeNode findLowerOrEq (in KeyType compare)
> {
> TreeNode t = root;
> TreeNode erg = null;
> while (t)
> {
> if (t.key > compare)
> {
> // if t > key descend left subtree
> t = t.left;
> }
> else
> {
> // if (t <= key) -> remember it
> // and descend right subtree
> erg = t;
> t = t.right;
> }
> }
> return erg;
> }
>
> /// clear tree
> void clear()
> {
> root = null;
> }
>
> /// returns true when tree is empty
> bool isEmpty()
> {
> return (root is null);
> }
>
> /// determine height of tree
> int height()
> {
> return height(root);
> }
>
> /// return number of nodes maintained by tree
> int count()
> {
> return count(root);
> }
>
> /// return node with minimum key
> TreeNode getMin()
> {
> return getMin(root);
> }
>
> /// return node with maximum key
> TreeNode getMax()
> {
> return getMax(root);
> }
>
> int opApply(int delegate(inout TreeNode) dg)
> {
> return applyForward(root, dg);
> }
>
> int opApplyReverse(int delegate(inout TreeNode) dg)
> {
> return applyReverse(root, dg);
> }
>
> /// debug output; prints tree sideways
> void PrintSideWays()
> {
> _PrintSideWays(root, 0);
> }
>
> void _PrintSideWays (in TreeNode child, in int space)
> {
> while(child)
> {
> space += 2;
> _PrintSideWays(child.left, space);
> for (int idx=0; idx < space; ++idx) printf(" ");
> printf("%*s\n", child.key);
> child = child.right;
> }
> }
>
> }
>
> import std.stdio;
>
> void main()
> {
> RedBlackTree!(char[], int) foo = new RedBlackTree!(char[], int);
>
> foo["Sally"]= 11;
> foo["Joe"] = 12;
> foo["Jill"] = 13;
> foo["Mary"] = 14;
> foo["Jack"] = 15;
> foo["Carl"] = 16;
> foo["Nina"] = 17;
> foo["Tim"] = 18;
> foo.PrintSideWays();
>
> foreach(v; foo)
> {
> writefln(v.key, " ", v.value);
> }
>
> writefln(" ");
>
> foreach_reverse(v; foo)
> {
> writefln(v.key, " ", v.value);
> }
>
> foo.remove("Mary");
>
> writefln(" ");
>
> foreach(v; foo)
> {
> writefln(v.key, " ", v.value);
> }
>
> writefln(" ");
>
> writefln("Age of Jill: ", foo.find("Jill").value);
>
> writefln("Upper(James): ", foo.findUpper("James").key);
> writefln("Lower(James): ", foo.findLower("James").key);
>
> writefln("findUpperOrEq(Nino): ", foo.findUpperOrEq("Nino").key);
> writefln("findUpperOrEq(Nina): ", foo.findUpperOrEq("Nina").key);
>
> writefln("findLowerOrEq(Nino): ", foo.findLowerOrEq("Nino").key);
> writefln("findLowerOrEq(Nina): ", foo.findLowerOrEq("Nina").key);
>
> }
Yes, thank you! I'll give it a try when I get the chance. I really
didn't want an intrusive tree. Looks like you have an interesting
interface too, although why not have an interface like...
RedBlackTree!(int) tree;
tree.add(4);
tree.add(3);
tree.add(7);
tree.remove(7);
int b = tree.find(7);
? Just wondering how you came up with the interface :)
~ Clay
More information about the Digitalmars-d-learn
mailing list