--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tango/tango/util/collection/TreeBag.d	Fri Jan 11 17:57:40 2008 +0100
@@ -0,0 +1,493 @@
+/*
+ File: TreeBag.d
+
+ Originally written by Doug Lea and released into the public domain. 
+ Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
+ Inc, Loral, and everyone contributing, testing, and using this code.
+
+ History:
+ Date     Who                What
+ 24Sep95  dl@cs.oswego.edu   Create from tango.util.collection.d  working file
+ 13Oct95  dl                 Changed protection statuses
+
+*/
+
+
+module tango.util.collection.TreeBag;
+
+private import  tango.util.collection.model.Iterator,
+                tango.util.collection.model.Comparator,
+                tango.util.collection.model.SortedValues,
+                tango.util.collection.model.GuardIterator;
+
+private import  tango.util.collection.impl.RBCell,
+                tango.util.collection.impl.BagCollection,
+                tango.util.collection.impl.AbstractIterator,
+                tango.util.collection.impl.DefaultComparator;
+
+/**
+ * RedBlack trees.
+ * author: Doug Lea
+**/
+
+public class TreeBag(T) : BagCollection!(T), SortedValues!(T)
+{
+        alias RBCell!(T)        RBCellT;
+        alias Comparator!(T)    ComparatorT;
+
+        alias BagCollection!(T).remove     remove;
+        alias BagCollection!(T).removeAll  removeAll;
+
+
+        // instance variables
+
+        /**
+         * The root of the tree. Null if empty.
+        **/
+
+        package RBCellT tree;
+
+        /**
+         * The comparator to use for ordering.
+        **/
+        protected ComparatorT cmp_;
+
+        // constructors
+
+        /**
+         * Make an empty tree.
+         * Initialize to use DefaultComparator for ordering
+        **/
+        public this ()
+        {
+                this(null, null, null, 0);
+        }
+
+        /**
+         * Make an empty tree, using the supplied element screener.
+         * Initialize to use DefaultComparator for ordering
+        **/
+
+        public this (Predicate s)
+        {
+                this(s, null, null, 0);
+        }
+
+        /**
+         * Make an empty tree, using the supplied element comparator for ordering.
+        **/
+        public this (ComparatorT c)
+        {
+                this(null, c, null, 0);
+        }
+
+        /**
+         * Make an empty tree, using the supplied element screener and comparator
+        **/
+        public this (Predicate s, ComparatorT c)
+        {
+                this(s, c, null, 0);
+        }
+
+        /**
+         * Special version of constructor needed by clone()
+        **/
+
+        protected this (Predicate s, ComparatorT cmp, RBCellT t, int n)
+        {
+                super(s);
+                count = n;
+                tree = t;
+                if (cmp !is null)
+                    cmp_ = cmp;
+                else
+                   cmp_ = new DefaultComparator!(T);
+        }
+
+        /**
+         * Make an independent copy of the tree. Does not clone elements.
+        **/ 
+
+        public TreeBag duplicate()
+        {
+                if (count is 0)
+                    return new TreeBag!(T)(screener, cmp_);
+                else
+                   return new TreeBag!(T)(screener, cmp_, tree.copyTree(), count);
+        }
+
+
+
+        // Collection methods
+
+        /**
+         * Implements tango.util.collection.impl.Collection.Collection.contains
+         * Time complexity: O(log n).
+         * See_Also: tango.util.collection.impl.Collection.Collection.contains
+        **/
+        public final bool contains(T element)
+        {
+                if (!isValidArg(element) || count is 0)
+                     return false;
+
+                return tree.find(element, cmp_) !is null;
+        }
+
+        /**
+         * Implements tango.util.collection.impl.Collection.Collection.instances
+         * Time complexity: O(log n).
+         * See_Also: tango.util.collection.impl.Collection.Collection.instances
+        **/
+        public final uint instances(T element)
+        {
+                if (!isValidArg(element) || count is 0)
+                     return 0;
+
+                return tree.count(element, cmp_);
+        }
+
+        /**
+         * Implements tango.util.collection.impl.Collection.Collection.elements
+         * Time complexity: O(1).
+         * See_Also: tango.util.collection.impl.Collection.Collection.elements
+        **/
+        public final GuardIterator!(T) elements()
+        {
+                return new CellIterator!(T)(this);
+        }
+
+        /**
+         * Implements tango.util.collection.model.View.View.opApply
+         * Time complexity: O(n).
+         * See_Also: tango.util.collection.model.View.View.opApply
+        **/
+        int opApply (int delegate (inout T value) dg)
+        {
+                auto scope iterator = new CellIterator!(T)(this);
+                return iterator.opApply (dg);
+        }
+
+
+        // ElementSortedCollection methods
+
+
+        /**
+         * Implements tango.util.collection.ElementSortedCollection.comparator
+         * Time complexity: O(1).
+         * See_Also: tango.util.collection.ElementSortedCollection.comparator
+        **/
+        public final ComparatorT comparator()
+        {
+                return cmp_;
+        }
+
+        /**
+         * Reset the comparator. Will cause a reorganization of the tree.
+         * Time complexity: O(n log n).
+        **/
+        public final void comparator(ComparatorT cmp)
+        {
+                if (cmp !is cmp_)
+                   {
+                   if (cmp !is null)
+                       cmp_ = cmp;
+                   else
+                      cmp_ = new DefaultComparator!(T);
+
+                   if (count !is 0)
+                      {       // must rebuild tree!
+                      incVersion();
+                      RBCellT t = tree.leftmost();
+                      tree = null;
+                      count = 0;
+                      while (t !is null)
+                            {
+                            add_(t.element(), false);
+                            t = t.successor();
+                            }
+                      }
+                   }
+        }
+
+
+        // MutableCollection methods
+
+        /**
+         * Implements tango.util.collection.impl.Collection.Collection.clear.
+         * Time complexity: O(1).
+         * See_Also: tango.util.collection.impl.Collection.Collection.clear
+        **/
+        public final void clear()
+        {
+                setCount(0);
+                tree = null;
+        }
+
+        /**
+         * Implements tango.util.collection.impl.Collection.Collection.removeAll.
+         * Time complexity: O(log n * instances(element)).
+         * See_Also: tango.util.collection.impl.Collection.Collection.removeAll
+        **/
+        public final void removeAll(T element)
+        {
+                remove_(element, true);
+        }
+
+
+        /**
+         * Implements tango.util.collection.impl.Collection.Collection.removeOneOf.
+         * Time complexity: O(log n).
+         * See_Also: tango.util.collection.impl.Collection.Collection.removeOneOf
+        **/
+        public final void remove(T element)
+        {
+                remove_(element, false);
+        }
+
+        /**
+         * Implements tango.util.collection.impl.Collection.Collection.replaceOneOf
+         * Time complexity: O(log n).
+         * See_Also: tango.util.collection.impl.Collection.Collection.replaceOneOf
+        **/
+        public final void replace(T oldElement, T newElement)
+        {
+                replace_(oldElement, newElement, false);
+        }
+
+        /**
+         * Implements tango.util.collection.impl.Collection.Collection.replaceAllOf.
+         * Time complexity: O(log n * instances(oldElement)).
+         * See_Also: tango.util.collection.impl.Collection.Collection.replaceAllOf
+        **/
+        public final void replaceAll(T oldElement, T newElement)
+        {
+                replace_(oldElement, newElement, true);
+        }
+
+        /**
+         * Implements tango.util.collection.impl.Collection.Collection.take.
+         * Time complexity: O(log n).
+         * Takes the least element.
+         * See_Also: tango.util.collection.impl.Collection.Collection.take
+        **/
+        public final T take()
+        {
+                if (count !is 0)
+                   {
+                   RBCellT p = tree.leftmost();
+                   T v = p.element();
+                   tree = p.remove(tree);
+                   decCount();
+                   return v;
+                   }
+
+                checkIndex(0);
+                return T.init; // not reached
+        }
+
+
+        // MutableBag methods
+
+        /**
+         * Implements tango.util.collection.MutableBag.addIfAbsent
+         * Time complexity: O(log n).
+         * See_Also: tango.util.collection.MutableBag.addIfAbsent
+        **/
+        public final void addIf (T element)
+        {
+                add_(element, true);
+        }
+
+
+        /**
+         * Implements tango.util.collection.MutableBag.add.
+         * Time complexity: O(log n).
+         * See_Also: tango.util.collection.MutableBag.add
+        **/
+        public final void add (T element)
+        {
+                add_(element, false);
+        }
+
+
+        // helper methods
+
+        private final void add_(T element, bool checkOccurrence)
+        {
+                checkElement(element);
+
+                if (tree is null)
+                   {
+                   tree = new RBCellT(element);
+                   incCount();
+                   }
+                else
+                   {
+                   RBCellT t = tree;
+
+                   for (;;)
+                       {
+                       int diff = cmp_.compare(element, t.element());
+                       if (diff is 0 && checkOccurrence)
+                           return ;
+                       else
+                          if (diff <= 0)
+                             {
+                             if (t.left() !is null)
+                                 t = t.left();
+                             else
+                                {
+                                tree = t.insertLeft(new RBCellT(element), tree);
+                                incCount();
+                                return ;
+                                }
+                             }
+                          else
+                             {
+                             if (t.right() !is null)
+                                 t = t.right();
+                              else
+                                 {
+                                 tree = t.insertRight(new RBCellT(element), tree);
+                                 incCount();
+                                 return ;
+                                 }
+                              }
+                          }
+                   }
+        }
+
+
+        private final void remove_(T element, bool allOccurrences)
+        {
+                if (!isValidArg(element))
+                    return ;
+
+                while (count > 0)
+                      {
+                      RBCellT p = tree.find(element, cmp_);
+
+                      if (p !is null)
+                         {
+                         tree = p.remove(tree);
+                         decCount();
+                         if (!allOccurrences)
+                             return ;
+                         }
+                      else
+                         break;
+                      }
+        }
+
+        private final void replace_(T oldElement, T newElement, bool allOccurrences)
+        {
+                if (!isValidArg(oldElement) || count is 0 || oldElement == newElement)
+                    return ;
+
+                while (contains(oldElement))
+                      {
+                      remove(oldElement);
+                      add (newElement);
+                      if (!allOccurrences)
+                          return ;
+                      }
+        }
+
+        // ImplementationCheckable methods
+
+        /**
+         * Implements tango.util.collection.model.View.View.checkImplementation.
+         * See_Also: tango.util.collection.model.View.View.checkImplementation
+        **/
+        public override void checkImplementation()
+        {
+
+                super.checkImplementation();
+                assert(cmp_ !is null);
+                assert(((count is 0) is (tree is null)));
+                assert((tree is null || tree.size() is count));
+
+                if (tree !is null)
+                   {
+                   tree.checkImplementation();
+                   T last = T.init;
+                   RBCellT t = tree.leftmost();
+                   while (t !is null)
+                         {
+                         T v = t.element();
+                         if (last !is T.init)
+                             assert(cmp_.compare(last, v) <= 0);
+                         last = v;
+                         t = t.successor();
+                         }
+                   }
+        }
+
+
+        /***********************************************************************
+
+                opApply() has migrated here to mitigate the virtual call
+                on method get()
+                
+        ************************************************************************/
+
+        private static class CellIterator(T) : AbstractIterator!(T)
+        {
+                private RBCellT cell;
+
+                public this (TreeBag bag)
+                {
+                        super(bag);
+
+                        if (bag.tree)
+                            cell = bag.tree.leftmost;
+                }
+
+                public final T get()
+                {
+                        decRemaining();
+                        auto v = cell.element();
+                        cell = cell.successor();
+                        return v;
+                }
+
+                int opApply (int delegate (inout T value) dg)
+                {
+                        int result;
+
+                        for (auto i=remaining(); i--;)
+                            {
+                            auto value = get();
+                            if ((result = dg(value)) != 0)
+                                 break;
+                            }
+                        return result;
+                }
+        }
+}
+
+
+
+debug (Test)
+{
+        import tango.io.Console;
+        
+        void main()
+        {
+                auto bag = new TreeBag!(char[]);
+                bag.add ("bar");
+                bag.add ("barrel");
+                bag.add ("foo");
+
+                foreach (value; bag.elements) {}
+
+                auto elements = bag.elements();
+                while (elements.more)
+                       auto v = elements.get();
+
+                foreach (value; bag.elements)
+                         Cout (value).newline;
+                     
+                bag.checkImplementation();
+        }
+}