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