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

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

clayasaurus wrote:
> 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

Walter suggested it in a previous post. I think he wanted the same interface as AAs have.

Walter Bright schrieb:
> Sean Kelly wrote:
> 
>> The C++ set is implemented as a balanced binary tree, and some sort of binary tree is probably your best bet if you want a sorted container with decent lookup performance.
> 
> 
> C++'s balanced binary trees are red-black trees. I had just proposed that someone do a red-black tree implementation for D. It's not hard, the algorithms are well known. It just takes a little time to sit down and do it.
http://www.cs.fiu.edu/~weiss/dsj3/code/weiss/nonstandard/RedBlackTree.java
(a generic implementation)

My roots are in Modula/Oberon, but if somebody is willing to translate the Java sources into D I am willing to help in translating/implementing the *missing* remove-method (-as good as possible-) , and some helper methods from Modula 3 into D.

Björn


// *Java basic impl.*
public class RedBlackTree<AnyType extends Comparable<? super AnyType>>
{
    /**
     * Construct the tree.
     */
    public RedBlackTree( )
    {
        nullNode = new RedBlackNode<AnyType>( null );
        nullNode.left = nullNode.right = nullNode;
        header      = new RedBlackNode<AnyType>( null );
        header.left = header.right = nullNode;
    }

    /**
     * Compare item and t.element, using compareTo, with
     * caveat that if t is header, then item is always larger.
     * This routine is called if is possible that t is header.
     * If it is not possible for t to be header, use compareTo directly.
     */
    private final int compare( AnyType item, RedBlackNode<AnyType> t )
    {
        if( t == header )
            return 1;
        else
            return item.compareTo( t.element );
    }

    /**
     * Insert into the tree.
     * @param item the item to insert.
     * @throws DuplicateItemException if item is already present.
     */
    public void insert( AnyType item )
    {
        current = parent = grand = header;
        nullNode.element = item;

        while( compare( item, current ) != 0 )
        {
            great = grand; grand = parent; parent = current;
            current = compare( item, current ) < 0 ?
                         current.left : current.right;

                // Check if two red children; fix if so
            if( current.left.color == RED && current.right.color == RED )
                 handleReorient( item );
        }

            // Insertion fails if already present
        if( current != nullNode )
            throw new DuplicateItemException( item.toString( ) );
        current = new RedBlackNode<AnyType>( item, nullNode, nullNode );

            // Attach to parent
        if( compare( item, parent ) < 0 )
            parent.left = current;
        else
            parent.right = current;
        handleReorient( item );
    }

    /**
     * Remove from the tree.
     * @param x the item to remove.
     * @throws UnsupportedOperationException if called.
     */
    public void remove( AnyType x )
    {
        throw new UnsupportedOperationException( );
    }

    /**
     * Find the smallest item  the tree.
     * @return the smallest item or null if empty.
     */
    public AnyType findMin( )
    {
        if( isEmpty( ) )
            return null;

        RedBlackNode<AnyType> itr = header.right;

        while( itr.left != nullNode )
            itr = itr.left;

        return itr.element;
    }

    /**
     * Find the largest item in the tree.
     * @return the largest item or null if empty.
     */
    public AnyType findMax( )
    {
        if( isEmpty( ) )
            return null;

        RedBlackNode<AnyType> itr = header.right;

        while( itr.right != nullNode )
            itr = itr.right;

        return itr.element;
    }

    /**
     * Find an item in the tree.
     * @param x the item to search for.
     * @return the matching item or null if not found.
     */
    public AnyType find( AnyType x )
    {
        nullNode.element = x;
        current = header.right;

        for( ; ; )
        {
            if( x.compareTo( current.element ) < 0 )
                current = current.left;
            else if( x.compareTo( current.element ) > 0 )
                current = current.right;
            else if( current != nullNode )
                return current.element;
            else
                return null;
        }
    }

    /**
     * Make the tree logically empty.
     */
    public void makeEmpty( )
    {
        header.right = nullNode;
    }

    /**
     * Print all items.
     */
    public void printTree( )
    {
        printTree( header.right );
    }

    /**
     * Internal method to print a subtree in sorted order.
     * @param t the node that roots the tree.
     */
    private void printTree( RedBlackNode<AnyType> t )
    {
        if( t != nullNode )
        {
            printTree( t.left );
            System.out.println( t.element );
            printTree( t.right );
        }
    }

    /**
     * Test if the tree is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty( )
    {
        return header.right == nullNode;
    }

    /**
     * Internal routine that is called during an insertion
     * if a node has two red children. Performs flip and rotations.
     * @param item the item being inserted.
     */
    private void handleReorient( AnyType item )
    {
            // Do the color flip
        current.color = RED;
        current.left.color = BLACK;
        current.right.color = BLACK;

        if( parent.color == RED )   // Have to rotate
        {
            grand.color = RED;
            if( ( compare( item, grand ) < 0 ) !=
                ( compare( item, parent ) < 0 ) )
                parent = rotate( item, grand );  // Start dbl rotate
            current = rotate( item, great );
            current.color = BLACK;
        }
        header.right.color = BLACK; // Make root black
    }

    /**
     * Internal routine that performs a single or double rotation.
     * Because the result is attached to the parent, there are four cases.
     * Called by handleReorient.
     * @param item the item in handleReorient.
     * @param parent the parent of the root of the rotated subtree.
     * @return the root of the rotated subtree.
     */
    private RedBlackNode<AnyType> rotate( AnyType item, RedBlackNode<AnyType> parent )
    {
        if( compare( item, parent ) < 0 )
            return parent.left = compare( item, parent.left ) < 0 ?
                rotateWithLeftChild( parent.left )  :  // LL
                rotateWithRightChild( parent.left ) ;  // LR
        else
            return parent.right = compare( item, parent.right ) < 0 ?
                rotateWithLeftChild( parent.right ) :  // RL
                rotateWithRightChild( parent.right );  // RR
    }

    /**
     * Rotate binary tree node with left child.
     */
    private static <AnyType> RedBlackNode<AnyType> rotateWithLeftChild( RedBlackNode<AnyType> k2 )
    {
        RedBlackNode<AnyType> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        return k1;
    }

    /**
     * Rotate binary tree node with right child.
     */
    private static <AnyType> RedBlackNode<AnyType> rotateWithRightChild( RedBlackNode<AnyType> k1 )
    {
        RedBlackNode<AnyType> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        return k2;
    }

    private static class RedBlackNode<AnyType>
    {
            // Constructors
        RedBlackNode( AnyType theElement )
        {
            this( theElement, null, null );
        }

        RedBlackNode( AnyType theElement, RedBlackNode<AnyType> lt, RedBlackNode<AnyType> rt )
        {
            element  = theElement;
            left     = lt;
            right    = rt;
            color    = RedBlackTree.BLACK;
        }

        AnyType               element;    // The data in the node
        RedBlackNode<AnyType> left;       // Left child
        RedBlackNode<AnyType> right;      // Right child
        int                   color;      // Color
    }

    private RedBlackNode<AnyType> header;
    private RedBlackNode<AnyType> nullNode;

    private static final int BLACK = 1;    // BLACK must be 1
    private static final int RED   = 0;

        // Used in insert routine and its helpers
    private RedBlackNode<AnyType> current;
    private RedBlackNode<AnyType> parent;
    private RedBlackNode<AnyType> grand;
    private RedBlackNode<AnyType> great;


        // Test program
    public static void main( String [ ] args )
    {
        RedBlackTree<Integer> t = new RedBlackTree<Integer>( );
        final int NUMS = 400000;
        final int GAP  =  35461;

        System.out.println( "Checking... (no more output means success)" );

        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            t.insert( i );

        if( t.findMin( ) != 1 || t.findMax( ) != NUMS - 1 )
            System.out.println( "FindMin or FindMax error!" );

        for( int i = 1; i < NUMS; i++ )
             if( t.find( i ) != i )
                 System.out.println( "Find error1!" );
    }
}


// *Modula 3 Remove*

PROCEDURE Delete (t: T; k: Key.T; VAR (*OUT*) v: Value.T): BOOLEAN =
  VAR
    curr             := t.root;
    rep, repCh: Node;
  BEGIN
    (* find the node to delete (if any *)
    WHILE curr # t.nil DO
      CASE t.keyCompare(k, curr.k) OF
      | -1 => curr := curr.l
      | 1 => curr := curr.r
      | 0 => EXIT
      END
    END;
    IF curr = t.nil THEN RETURN FALSE END;

    (* locate replacement node and one of its children *)
    IF curr.l = t.nil OR curr.r = t.nil THEN
      rep := curr
    ELSE
      rep := Successor(t, curr)
    END;
    IF rep.l # t.nil THEN repCh := rep.l ELSE repCh := rep.r END;

    (* splice out "rep" node *)
    repCh.p := rep.p;
    IF rep.p = t.nil THEN
      t.root := repCh
    ELSE
      IF rep = rep.p.l THEN repCh.p.l := repCh ELSE repCh.p.r := repCh END
    END;

    (* save value of node to be deleted *)
    v := curr.v;

    (* copy "rep" fields into "curr" if they are different *)
    IF rep # curr THEN curr.k := rep.k; curr.v := rep.v END;

    (* rebalance tree if necessary *)
    IF rep.color = Color.Black THEN DeleteFixup(t, repCh) END;
    DEC(t.num);
    RETURN TRUE
  END Delete;

PROCEDURE DeleteFixup (t: T; ch: Node) =
  VAR p, sib: Node;
  BEGIN
    WHILE ch # t.root AND ch.color = Color.Black DO
      p := ch.p;
      IF ch = p.l THEN
        (* "ch" is the left child of "p" *)
        sib := p.r;
        <* ASSERT sib # t.nil *>
        IF sib.color = Color.Red THEN
          (* case 1 *)
          sib.color := Color.Black;
          p.color := Color.Red;
          LeftRotate(t, p, sib);
          sib := p.r
        END;
        <* ASSERT sib.color = Color.Black AND sib # t.nil *>
        IF sib.l.color = Color.Black AND sib.r.color = Color.Black THEN
          (* case 2 *)
          sib.color := Color.Red;
          ch := p
        ELSE
          IF sib.r.color = Color.Black THEN
            (* case 3 *)
            <* ASSERT sib.l.color = Color.Red *>
            sib.l.color := Color.Black;
            sib.color := Color.Red;
            RightRotate(t, sib, sib.l);
            sib := p.r
          END;
          <* ASSERT sib.r.color = Color.Red *>
          (* case 4 *)
          sib.color := p.color;
          p.color := Color.Black;
          sib.r.color := Color.Black;
          LeftRotate(t, p, sib);
          ch := t.root
        END
      ELSE
        (* "ch" is the right child of "p" *)
        sib := p.l;
        <* ASSERT sib # t.nil *>
        IF sib.color = Color.Red THEN
          (* case 1 *)
          sib.color := Color.Black;
          p.color := Color.Red;
          RightRotate(t, p, sib);
          sib := p.l
        END;
        <* ASSERT sib.color = Color.Black AND sib # t.nil *>
        IF sib.r.color = Color.Black AND sib.l.color = Color.Black THEN
          (* case 2 *)
          sib.color := Color.Red;
          ch := p
        ELSE
          IF sib.l.color = Color.Black THEN
            (* case 3 *)
            <* ASSERT sib.r.color = Color.Red *>
            sib.r.color := Color.Black;
            sib.color := Color.Red;
            LeftRotate(t, sib, sib.r);
            sib := p.l
          END;
          <* ASSERT sib.l.color = Color.Red *>
          (* case 4 *)
          sib.color := p.color;
          p.color := Color.Black;
          sib.l.color := Color.Black;
          RightRotate(t, p, sib);
          ch := t.root
        END
      END
    END;
    ch.color := Color.Black
  END DeleteFixup;


Indeed, a wild mixture!!!

Walter Bright schrieb:

> .....that someone do a red-black tree implementation for D. It's not hard, the algorithms are well known. It just takes a little time to sit down and do it.

Hi algorithm fans, maybe you can help a bit. I own  the Algorithms and Data Structures books from Wirth and Sedgewick. (Both antik/antique ... means Pascal, still true! and of course a little bit outdated) If you have a hint what is worth reading now (except C++ books) Thanks in advance. Björn

KlausO wrote:
> clayasaurus wrote:
>> 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
> 
> Walter suggested it in a previous post. I think he wanted the same interface as AAs have.

Oh, alright :)

BLS wrote:
> Walter Bright schrieb:
> 
>> .....that someone do a red-black tree implementation for D. It's not hard, the algorithms are well known. It just takes a little time to sit down and do it.
> 
> Hi algorithm fans, maybe you can help a bit. I own  the Algorithms and Data Structures books from Wirth and Sedgewick. (Both antik/antique ... means Pascal, still true! and of course a little bit outdated) If you have a hint what is worth reading now (except C++ books) Thanks in advance. Björn

Personally, I like Sedgewick's "Algorithms in C++" series the best.  And the "Algorithms in Java" versions appear similar, so I think they're probably just as good.  I find the writing succinct and clear, and performance is discussed thoroughly and supported by actual test numbers.

Also, while I don't like the writing style in M.A. Weiss' first edition "Data Structures and Problem Solving with C++" as much as Sedgewick, it does cover some topics that Sedgewick doesn't.  Weiss' more recent edition for Java (and I assume C++), however, is about half as thick and its clarity has suffered from all the editing.  But it does still cover the same range of topics, so it may be worth a look.


Sean

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)

This is a lot better than returning an empty node, though. If you can tell me why it crashed, then do it :)

> 
>    Using insert like
>      if (foo.insert("Jill", 13))
>    looks better to me.

You could implement both and let the programmer decide.

It also might be neat to implement opIn_r, so you can use...

if (!("Jill" in tree))
   tree.add("Jill");

Sean Kelly schrieb:

> Personally, I like Sedgewick's "Algorithms in C++" series the best.  And the "Algorithms in Java" versions appear similar, so I think they're probably just as good.  I find the writing succinct and clear, and performance is discussed thoroughly and supported by actual test numbers.
> 
> Also, while I don't like the writing style in M.A. Weiss' first edition "Data Structures and Problem Solving with C++" as much as Sedgewick, it does cover some topics that Sedgewick doesn't.  Weiss' more recent edition for Java (and I assume C++), however, is about half as thick and its clarity has suffered from all the editing.  But it does still cover the same range of topics, so it may be worth a look.
> 
> 
> Sean

Thanks for your answere Sean,
Thinking about your answere and the nature of Java (no pointers) I guess that Sedgewick's "Algorithms in Java" could fullfill my needs because I  would like to translate a lot of (pseudo) code like this :

nodepointer is POINTER to node;
node  is record
begin
    d is interger;
    lnode is nodepointer;
    rnode is nodepointer;
    data is Anytype;
end

into D classes.

Maybe you know about the meanwhile dead PM3 Modula 3 efforts ... wish we have such a HUGE lib in D. Hope that comparing pointerless Java examples will help to translate Modula sources into D. Ahem...

Björn
btw :I wonder wether Sedgewick is still using tons of academic terms (means showing how clever he is) or is he meanwhile able to produce some output a human-beeing can read.

BLS wrote:
> btw :I wonder wether Sedgewick is still using tons of academic terms (means showing how clever he is) or is he meanwhile able to produce some output a human-beeing can read.

I find Sedgewick to be quite readable, but his material is a bit more technical than some of the other texts.  I personally like this because it makes for good reference material, but if I were teaching the subject I might choose a book that doesn't jump into the middle of things quite so quickly.

For comparison, my wife took an algorithm analysis course recently that used Weiss' Java book.  She found the descriptions in it confusing, but thought my 1st ed. C++ copy of the same book (same topics but much longer) was excellent.  So I'd be inclined to recommend Weiss except his recent editions don't seem as clear as his earlier editions, as a result of some heavy editing to reduce page count.

I wish I could suggest others, but aside from Knuth those are the only algorithms books I've actually kept.


Sean