OoasTools

/*

 Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft

 Permission is hereby granted, free of charge, to any person obtaining a copy

 of this software and associated documentation files (the "Software"), to deal

 in the Software without restriction, including without limitation the rights

 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

 copies of the Software, and to permit persons to whom the Software is

 furnished to do so, subject to the following conditions:

 The above copyright notice and this permission notice shall be included in

 all copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

 SOFTWARE.

*/

#define MAINTAIN_SIZE

#define BAG

#define NCP

#if BAG

#if !MAINTAIN_SIZE

#error  BAG defined without MAINTAIN_SIZE!

#endif

#endif

using System;

using SCG = System.Collections.Generic;

// NOTE NOTE NOTE NOTE

// This source file is used to produce both TreeBag<T> and TreeBag<T>

// It should be copied to a file called TreeBag.cs in which all code mentions of 

// TreeBag is changed to TreeBag and the preprocessor symbol BAG is defined.

// NOTE: there may be problems with documentation comments.

namespace C5

{

#if BAG

  /// <summary>

  /// An implementation of Red-Black trees as an indexed, sorted collection with bag semantics,

  /// cf. <a href="litterature.htm#CLRS">CLRS</a>. (<see cref="T:C5.TreeBag`1"/> for an 

  /// implementation with set semantics).

  /// <br/>

  /// The comparer (sorting order) may be either natural, because the item type is comparable 

  /// (generic: <see cref="T:C5.IComparable`1"/> or non-generic: System.IComparable) or it can

  /// be external and supplied by the user in the constructor.

  /// <br/>

  /// Each distinct item is only kept in one place in the tree - together with the number

  /// of times it is a member of the bag. Thus, if two items that are equal according

  /// </summary>

#else

  /// <summary>

  /// An implementation of Red-Black trees as an indexed, sorted collection with set semantics,

  /// cf. <a href="litterature.htm#CLRS">CLRS</a>. <see cref="T:C5.TreeBag`1"/> for a version 

  /// with bag semantics. <see cref="T:C5.TreeDictionary`2"/> for a sorted dictionary 

  /// based on this tree implementation.

  /// <i>

  /// The comparer (sorting order) may be either natural, because the item type is comparable 

  /// (generic: <see cref="T:C5.IComparable`1"/> or non-generic: System.IComparable) or it can

  /// be external and supplied by the user in the constructor.</i>

  ///

  /// <i>TODO: describe performance here</i>

  /// <i>TODO: discuss persistence and its useful usage modes. Warn about the space

  /// leak possible with other usage modes.</i>

  /// </summary>

#endif

  [Serializable]

  public class TreeBag<T> : SequencedBase<T>, IIndexedSorted<T>, IPersistentSorted<T>

  {

    #region Fields

    SCG.IComparer<T> comparer;

    Node root;

    //TODO: wonder if we should remove that

    int blackdepth = 0;

    //We double these stacks for the iterative add and remove on demand

    //TODO: refactor dirs[] into bool fields on Node (?)

    private int[] dirs = new int[2];

    private Node[] path = new Node[2];

#if NCP

    //TODO: refactor into separate class

    bool isSnapShot = false;

    int generation;

    bool isValid = true;

    SnapRef snapList;

#endif

    #endregion

    #region Events

    /// <summary>

    /// 

    /// </summary>

    /// <value></value>

    public override EventTypeEnum ListenableEvents { get { return EventTypeEnum.Basic; } }

    #endregion

    #region Util

    /// <summary>

    /// Fetch the left child of n taking node-copying persistence into

    /// account if relevant. 

    /// </summary>

    /// <param name="n"></param>

    /// <returns></returns>

    private Node left(Node n)

    {

#if NCP

      if (isSnapShot)

      {

#if SEPARATE_EXTRA

				Node.Extra e = n.extra;

				if (e != null && e.lastgeneration >= treegen && e.leftnode)

					return e.oldref;

#else

        if (n.lastgeneration >= generation && n.leftnode)

          return n.oldref;

#endif

      }

#endif

      return n.left;

    }

    private Node right(Node n)

    {

#if NCP

      if (isSnapShot)

      {

#if SEPARATE_EXTRA

				Node.Extra e = n.extra;

				if (e != null && e.lastgeneration >= treegen && !e.leftnode)

					return e.oldref;

#else

        if (n.lastgeneration >= generation && !n.leftnode)

          return n.oldref;

#endif

      }

#endif

      return n.right;

    }

    //This method should be called by methods that use the internal 

    //traversal stack, unless certain that there is room enough

    private void stackcheck()

    {

      while (dirs.Length < 2 * blackdepth)

      {

        dirs = new int[2 * dirs.Length];

        path = new Node[2 * dirs.Length];

      }

    }

    #endregion

    #region Node nested class

    /// <summary>

    /// The type of node in a Red-Black binary tree

    /// </summary>

    [Serializable]

    class Node

    {

      public bool red = true;

      public T item;

      public Node left;

      public Node right;

#if MAINTAIN_SIZE

      public int size = 1;

#endif

#if BAG

      public int items = 1;

#endif

#if NCP

      //TODO: move everything into (separate) Extra

      public int generation;

#if SEPARATE_EXTRA

			internal class Extra

			{

				public int lastgeneration;

				public Node oldref;

				public bool leftnode;

				//public Node next;

			}

			public Extra extra;

#else

      public int lastgeneration = -1;

      public Node oldref;

      public bool leftnode;

#endif

      /// <summary>

      /// Update a child pointer

      /// </summary>

      /// <param name="cursor"></param>

      /// <param name="leftnode"></param>

      /// <param name="child"></param>

      /// <param name="maxsnapid"></param>

      /// <param name="generation"></param>

      /// <returns>True if node was *copied*</returns>

      internal static bool update(ref Node cursor, bool leftnode, Node child, int maxsnapid, int generation)

      {

        Node oldref = leftnode ? cursor.left : cursor.right;

        if (child == oldref)

          return false;

        bool retval = false;

        if (cursor.generation <= maxsnapid)

        {

#if SEPARATE_EXTRA

					if (cursor.extra == null)

					{

						Extra extra = cursor.extra = new Extra();	

						extra.leftnode = leftnode;

						extra.lastgeneration = maxsnapid;

						extra.oldref = oldref;

					}

					else if (cursor.extra.leftnode != leftnode || cursor.extra.lastgeneration < maxsnapid)

#else

          if (cursor.lastgeneration == -1)

          {

            cursor.leftnode = leftnode;

            cursor.lastgeneration = maxsnapid;

            cursor.oldref = oldref;

          }

          else if (cursor.leftnode != leftnode || cursor.lastgeneration < maxsnapid)

#endif

          {

            CopyNode(ref cursor, maxsnapid, generation);

            retval = true;

          }

        }

        if (leftnode)

          cursor.left = child;

        else

          cursor.right = child;

        return retval;

      }

      //If cursor.extra.lastgeneration==maxsnapid, the extra pointer will 

      //always be used in the old copy of cursor. Therefore, after 

      //making the clone, we should update the old copy by restoring

      //the child pointer and setting extra to null.

      //OTOH then we cannot clean up unused Extra objects unless we link

      //them together in a doubly linked list.

      public static bool CopyNode(ref Node cursor, int maxsnapid, int generation)

      {

        if (cursor.generation <= maxsnapid)

        {

          cursor = (Node)(cursor.MemberwiseClone());

          cursor.generation = generation;

#if SEPARATE_EXTRA

					cursor.extra = null;

#else

          cursor.lastgeneration = -1;

#endif

          return true;

        }

        else

          return false;

      }

#endif

    }

    #endregion

    #region Constructors

    /// <summary>

    /// Create a red-black tree collection with natural comparer and item equalityComparer.

    /// We assume that if <code>T</code> is comparable, its default equalityComparer 

    /// will be compatible with the comparer.

    /// </summary>

    /// <exception cref="NotComparableException">If <code>T</code> is not comparable.

    /// </exception>

    public TreeBag() : this(Comparer<T>.Default, EqualityComparer<T>.Default) { }

    /// <summary>

    /// Create a red-black tree collection with an external comparer. 

    /// <para>The itemequalityComparer will be a compatible 

    /// <see cref="T:C5.ComparerZeroHashCodeEqualityComparer`1"/> since the 

    /// default equalityComparer for T (<see cref="P:C5.EqualityComparer`1.Default"/>)

    /// is unlikely to be compatible with the external comparer. This makes the

    /// tree inadequate for use as item in a collection of unsequenced or sequenced sets or bags

    /// (<see cref="T:C5.ICollection`1"/> and <see cref="T:C5.ISequenced`1"/>)

    /// </para>

    /// </summary>

    /// <param name="comparer">The external comparer</param>

    public TreeBag(SCG.IComparer<T> comparer) : this(comparer, new ComparerZeroHashCodeEqualityComparer<T>(comparer)) { }

    /// <summary>

    /// Create a red-black tree collection with an external comparer and an external

    /// item equalityComparer, assumed consistent.

    /// </summary>

    /// <param name="comparer">The external comparer</param>

    /// <param name="equalityComparer">The external item equalityComparer</param>

    public TreeBag(SCG.IComparer<T> comparer, SCG.IEqualityComparer<T> equalityComparer)

      : base(equalityComparer)

    {

      if (comparer == null)

        throw new NullReferenceException("Item comparer cannot be null");

      this.comparer = comparer;

    }

    #endregion

    #region TreeBag.Enumerator nested class

    /// <summary>

    /// An enumerator for a red-black tree collection. Based on an explicit stack

    /// of subtrees waiting to be enumerated. Currently only used for the tree set 

    /// enumerators (tree bag enumerators use an iterator block based enumerator).

    /// </summary>

    internal class Enumerator : SCG.IEnumerator<T>

    {

      #region Private Fields

      TreeBag<T> tree;

      bool valid = false;

      int stamp;

      T current;

      Node cursor;

      Node[] path; // stack of nodes

      int level = 0;

      #endregion

      /// <summary>

      /// Create a tree enumerator

      /// </summary>

      /// <param name="tree">The red-black tree to enumerate</param>

      public Enumerator(TreeBag<T> tree)

      {

        this.tree = tree;

        stamp = tree.stamp;

        path = new Node[2 * tree.blackdepth];

        cursor = new Node();

        cursor.right = tree.root;

      }

      /// <summary>

      /// Undefined if enumerator is not valid (MoveNext hash been called returning true)

      /// </summary>

      /// <value>The current item of the enumerator.</value>

      [Tested]

      public T Current

      {

        [Tested]

        get

        {

          if (valid)

            return current;

          else

            throw new InvalidOperationException();

        }

      }

      //Maintain a stack of nodes that are roots of

      //subtrees not completely exported yet. Invariant:

      //The stack nodes together with their right subtrees

      //consists of exactly the items we have not passed

      //yet (the top of the stack holds current item).

      /// <summary>

      /// Move enumerator to next item in tree, or the first item if

      /// this is the first call to MoveNext. 

      /// <exception cref="CollectionModifiedException"/> if underlying tree was modified.

      /// </summary>

      /// <returns>True if enumerator is valid now</returns>

      [Tested]

      public bool MoveNext()

      {

        tree.modifycheck(stamp);

        if (cursor.right != null)

        {

          path[level] = cursor = cursor.right;

          while (cursor.left != null)

            path[++level] = cursor = cursor.left;

        }

        else if (level == 0)

          return valid = false;

        else

          cursor = path[--level];

        current = cursor.item;

        return valid = true;

      }

      #region IDisposable Members for Enumerator

      bool disposed;

      /// <summary>

      /// Call Dispose(true) and then suppress finalization of this enumerator.

      /// </summary>

      [Tested]

      public void Dispose()

      {

        Dispose(true);

        GC.SuppressFinalize(this);

      }

      /// <summary>

      /// Remove the internal data (notably the stack array).

      /// </summary>

      /// <param name="disposing">True if called from Dispose(),

      /// false if called from the finalizer</param>

      protected virtual void Dispose(bool disposing)

      {

        if (!disposed)

        {

          if (disposing)

          {

          }

          current = default(T);

          cursor = null;

          path = null;

          disposed = true;

        }

      }

      /// <summary>

      /// Finalizer for enumerator

      /// </summary>

      ~Enumerator()

      {

        Dispose(false);

      }

      #endregion

      #region IEnumerator Members

      object System.Collections.IEnumerator.Current

      {

        get { return Current; }

      }

      bool System.Collections.IEnumerator.MoveNext()

      {

        return MoveNext();

      }

      void System.Collections.IEnumerator.Reset()

      {

        throw new Exception("The method or operation is not implemented.");

      }

      #endregion

    }

#if NCP

    /// <summary>

    /// An enumerator for a snapshot of a node copy persistent red-black tree

    /// collection.

    /// </summary>

    internal class SnapEnumerator : SCG.IEnumerator<T>

    {

      #region Private Fields

      TreeBag<T> tree;

      bool valid = false;

      int stamp;

#if BAG

      int togo;

#endif

      T current;

      Node cursor;

      Node[] path; // stack of nodes

      int level;

      #endregion

      /// <summary>

      /// Creta an enumerator for a snapshot of a node copy persistent red-black tree

      /// collection

      /// </summary>

      /// <param name="tree">The snapshot</param>

      public SnapEnumerator(TreeBag<T> tree)

      {

        this.tree = tree;

        stamp = tree.stamp;

        path = new Node[2 * tree.blackdepth];

        cursor = new Node();

        cursor.right = tree.root;

      }

      #region SCG.IEnumerator<T> Members

      /// <summary>

      /// Move enumerator to next item in tree, or the first item if

      /// this is the first call to MoveNext. 

      /// <exception cref="CollectionModifiedException"/> if underlying tree was modified.

      /// </summary>

      /// <returns>True if enumerator is valid now</returns>

      [Tested]

      public bool MoveNext()

      {

        tree.modifycheck(stamp);//???

#if BAG

        if (--togo > 0)

          return true;

#endif

        Node next = tree.right(cursor);

        if (next != null)

        {

          path[level] = cursor = next;

          next = tree.left(cursor);

          while (next != null)

          {

            path[++level] = cursor = next;

            next = tree.left(cursor);

          }

        }

        else if (level == 0)

          return valid = false;

        else

          cursor = path[--level];

#if BAG

        togo = cursor.items;

#endif

        current = cursor.item;

        return valid = true;

      }

      /// <summary>

      /// Undefined if enumerator is not valid (MoveNext hash been called returning true)

      /// </summary>

      /// <value>The current value of the enumerator.</value>

      [Tested]

      public T Current

      {

        [Tested]

        get

        {

          if (valid)

            return current;

          else

            throw new InvalidOperationException();

        }

      }

      #endregion

      #region IDisposable Members

      [Tested]

      void System.IDisposable.Dispose()

      {

        tree = null;

        valid = false;

        current = default(T);

        cursor = null;

        path = null;

      }

      #endregion

      #region IEnumerator Members

      object System.Collections.IEnumerator.Current

      {

        get { return Current; }

      }

      bool System.Collections.IEnumerator.MoveNext()

      {

        return MoveNext();

      }

      void System.Collections.IEnumerator.Reset()

      {

        throw new Exception("The method or operation is not implemented.");

      }

      #endregion

    }

#endif

    #endregion

    #region IEnumerable<T> Members

    private SCG.IEnumerator<T> getEnumerator(Node node, int origstamp)

    {

      if (node == null)

        yield break;

      if (node.left != null)

      {

        SCG.IEnumerator<T> child = getEnumerator(node.left, origstamp);

        while (child.MoveNext())

        {

          modifycheck(origstamp);

          yield return child.Current;

        }

      }

#if BAG

      int togo = node.items;

      while (togo-- > 0)

      {

        modifycheck(origstamp);

        yield return node.item;

      }

#else

      modifycheck(origstamp);

      yield return node.item;

#endif

      if (node.right != null)

      {

        SCG.IEnumerator<T> child = getEnumerator(node.right, origstamp);

        while (child.MoveNext())

        {

          modifycheck(origstamp);

          yield return child.Current;

        }

      }

    }

    /// <summary>

    /// 

    /// </summary>

    /// <exception cref="NoSuchItemException">If tree is empty</exception>

    /// <returns></returns>

    [Tested]

    public override T Choose()

    {

      if (!isValid)

        throw new ViewDisposedException("Snapshot has been disposed");

      if (size == 0)

        throw new NoSuchItemException();

      return root.item;

    }

    /// <summary>

    /// Create an enumerator for this tree

    /// </summary>

    /// <returns>The enumerator</returns>

    [Tested]

    public override SCG.IEnumerator<T> GetEnumerator()

    {

      if (!isValid)

        throw new ViewDisposedException("Snapshot has been disposed");

#if NCP

      if (isSnapShot)

        return new SnapEnumerator(this);

#endif

#if BAG

      return getEnumerator(root, stamp);

#else

      return new Enumerator(this);

#endif

    }

    #endregion

    #region ISink<T> Members

    /// <summary>

    /// Add item to tree. If already there, return the found item in the second argument.

    /// </summary>

    /// <param name="item">Item to add</param>

    /// <param name="founditem">item found</param>

    /// <param name="update">whether item in node should be updated</param>

    /// <param name="wasfound">true if found in bag, false if not found or tre is a set</param>

    /// <returns>True if item was added</returns>

    bool addIterative(T item, ref T founditem, bool update, out bool wasfound)

    {

      wasfound = false;

      if (root == null)

      {

        root = new Node();

        root.red = false;

        blackdepth = 1;

        root.item = item;

#if NCP

        root.generation = generation;

#endif

        return true;

      }

      stackcheck();

      int level = 0;

      Node cursor = root;

      while (true)

      {

        int comp = comparer.Compare(cursor.item, item);

        if (comp == 0)

        {

          founditem = cursor.item;

#if BAG

          wasfound = true;

          bool nodeWasUpdated = true;

#if NCP

          Node.CopyNode(ref cursor, maxsnapid, generation);

#endif

          if (update)

            cursor.item = item;

          else

          {

            cursor.items++;

            cursor.size++;

          }

#else

          bool nodeWasUpdated = update;

          if (update)

          {

#if NCP

            Node.CopyNode(ref cursor, maxsnapid, generation);

#endif

            cursor.item = item;

          }

#endif

          while (level-- > 0)

          {

            if (nodeWasUpdated)

            {

              Node kid = cursor;

              cursor = path[level];

#if NCP

              Node.update(ref cursor, dirs[level] > 0, kid, maxsnapid, generation);

#endif

#if BAG

              if (!update)

                cursor.size++;

#endif

            }

            path[level] = null;

          }

#if BAG

          return !update;

#else

          if (update)

            root = cursor;

          return false;

#endif

        }

        //else

        Node child = comp > 0 ? cursor.left : cursor.right;

        if (child == null)

        {

          child = new Node();

          child.item = item;

#if NCP

          child.generation = generation;

          Node.update(ref cursor, comp > 0, child, maxsnapid, generation);

#else

					if (comp > 0) { cursor.left = child; }

					else { cursor.right = child; }

#endif

#if MAINTAIN_SIZE

          cursor.size++;

#endif

          dirs[level] = comp;

          break;

        }

        else

        {

          dirs[level] = comp;

          path[level++] = cursor;

          cursor = child;

        }

      }

      //We have just added the red node child to "cursor"

      while (cursor.red)

      {

        //take one step up:

        Node child = cursor;

        cursor = path[--level];

        path[level] = null;

#if NCP

        Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);

#endif

#if MAINTAIN_SIZE

        cursor.size++;

#endif

        int comp = dirs[level];

        Node childsibling = comp > 0 ? cursor.right : cursor.left;

        if (childsibling != null && childsibling.red)

        {

          //Promote

          child.red = false;

#if NCP

          Node.update(ref cursor, comp < 0, childsibling, maxsnapid, generation);

#endif

          childsibling.red = false;

          //color cursor red & take one step up the tree unless at root

          if (level == 0)

          {

            root = cursor;

            blackdepth++;

            return true;

          }

          else

          {

            cursor.red = true;

#if NCP

            child = cursor;

            cursor = path[--level];

            Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);

#endif

            path[level] = null;

#if MAINTAIN_SIZE

            cursor.size++;

#endif

          }

        }

        else

        {

          //ROTATE!!!

          int childcomp = dirs[level + 1];

          cursor.red = true;

          if (comp > 0)

          {

            if (childcomp > 0)

            {//zagzag

#if NCP

              Node.update(ref cursor, true, child.right, maxsnapid, generation);

              Node.update(ref child, false, cursor, maxsnapid, generation);

#else

							cursor.left = child.right;

							child.right = cursor;

#endif

              cursor = child;

            }

            else

            {//zagzig

              Node badgrandchild = child.right;

#if NCP

              Node.update(ref cursor, true, badgrandchild.right, maxsnapid, generation);

              Node.update(ref child, false, badgrandchild.left, maxsnapid, generation);

              Node.CopyNode(ref badgrandchild, maxsnapid, generation);

#else

							cursor.left = badgrandchild.right;

							child.right = badgrandchild.left;

#endif

              badgrandchild.left = child;

              badgrandchild.right = cursor;

              cursor = badgrandchild;

            }

          }

          else

          {//comp < 0

            if (childcomp < 0)

            {//zigzig

#if NCP

              Node.update(ref cursor, false, child.left, maxsnapid, generation);

              Node.update(ref child, true, cursor, maxsnapid, generation);

#else

							cursor.right = child.left;

							child.left = cursor;

#endif

              cursor = child;

            }

            else

            {//zigzag

              Node badgrandchild = child.left;

#if NCP

              Node.update(ref cursor, false, badgrandchild.left, maxsnapid, generation);

              Node.update(ref child, true, badgrandchild.right, maxsnapid, generation);

              Node.CopyNode(ref badgrandchild, maxsnapid, generation);

#else

							cursor.right = badgrandchild.left;

							child.left = badgrandchild.right;

#endif

              badgrandchild.right = child;

              badgrandchild.left = cursor;

              cursor = badgrandchild;

            }

          }

          cursor.red = false;

#if MAINTAIN_SIZE

          Node n;

#if BAG

          n = cursor.right;

          cursor.size = n.size = (n.left == null ? 0 : n.left.size) + (n.right == null ? 0 : n.right.size) + n.items;

          n = cursor.left;

          n.size = (n.left == null ? 0 : n.left.size) + (n.right == null ? 0 : n.right.size) + n.items;

          cursor.size += n.size + cursor.items;

#else

          n = cursor.right;

          cursor.size = n.size = (n.left == null ? 0 : n.left.size) + (n.right == null ? 0 : n.right.size) + 1;

          n = cursor.left;

          n.size = (n.left == null ? 0 : n.left.size) + (n.right == null ? 0 : n.right.size) + 1;

          cursor.size += n.size + 1;

#endif

#endif

          if (level == 0)

          {

            root = cursor;

            return true;

          }

          else

          {

            child = cursor;

            cursor = path[--level];

            path[level] = null;

#if NCP

            Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);

#else

						if (dirs[level] > 0)

							cursor.left = child;

						else

							cursor.right = child;

#endif

#if MAINTAIN_SIZE

            cursor.size++;

#endif

            break;

          }

        }

      }

#if NCP

      bool stillmore = true;

#endif

      while (level > 0)

      {

        Node child = cursor;

        cursor = path[--level];

        path[level] = null;

#if NCP

        if (stillmore)

          stillmore = Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);

#endif

#if MAINTAIN_SIZE

        cursor.size++;

#endif

      }

      root = cursor;

      return true;

    }

    /// <summary>

    /// Add an item to this collection if possible. If this collection has set

    /// semantics, the item will be added if not already in the collection. If

    /// bag semantics, the item will always be added.

    /// </summary>

    /// <param name="item">The item to add.</param>

    /// <returns>True if item was added.</returns>

    [Tested]

    public bool Add(T item)

    {

      if (!isValid)

        throw new ViewDisposedException("Snapshot has been disposed");

      updatecheck();

      //Note: blackdepth of the tree is set inside addIterative

      T jtem = default(T);

      if (!add(item, ref jtem))

        return false;

      if (ActiveEvents != 0)

        raiseForAdd(jtem);

      return true;

    }

    /// <summary>

    /// Add an item to this collection if possible. If this collection has set

    /// semantics, the item will be added if not already in the collection. If

    /// bag semantics, the item will always be added.

    /// </summary>

    /// <param name="item">The item to add.</param>

    [Tested]

    void SCG.ICollection<T>.Add(T item)

    {

        Add(item);

    }

    private bool add(T item, ref T j)

    {

      bool wasFound;

      if (addIterative(item, ref j, false, out wasFound))

      {

        size++;

        if (!wasFound)

          j = item;

        return true;

      }

      else

        return false;

    }

    /// <summary>

    /// Add the elements from another collection with a more specialized item type 

    /// to this collection. If this

    /// collection has set semantics, only items not already in the collection

    /// will be added.

    /// </summary>

    /// <typeparam name="U">The type of items to add</typeparam>

    /// <param name="items">The items to add</param>

    [Tested]

    public void AddAll<U>(SCG.IEnumerable<U> items) where U : T

    {

      if (!isValid)

        throw new ViewDisposedException("Snapshot has been disposed");

      updatecheck();

      int c = 0;

      T j = default(T);

      bool tmp;

      bool raiseAdded = (ActiveEvents & EventTypeEnum.Added) != 0;

      CircularQueue<T> wasAdded = raiseAdded ? new CircularQueue<T>() : null;

      foreach (T i in items)

        if (addIterative(i, ref j, false, out tmp))

        {

          c++;

          if (raiseAdded)

            wasAdded.Enqueue(tmp ? j : i);

        }

      if (c == 0)

        return;

      size += c;

      //TODO: implement a RaiseForAddAll() method

      if (raiseAdded)

        foreach (T item in wasAdded)

          raiseItemsAdded(item, 1);

      if (((ActiveEvents & EventTypeEnum.Changed) != 0))

        raiseCollectionChanged();

    }

    /// <summary>

    /// Add all the items from another collection with an enumeration order that 

    /// is increasing in the items. <para>The idea is that the implementation may use

    /// a faster algorithm to merge the two collections.</para>

    /// <exception cref="ArgumentException"/> if the enumerated items turns out

    /// not to be in increasing order.

    /// </summary>

    /// <param name="items">The collection to add.</param>

    /// <typeparam name="U"></typeparam>

    [Tested]

    public void AddSorted<U>(SCG.IEnumerable<U> items) where U : T

    {

      if (size > 0)

        AddAll(items);

      else

      {

        if (!isValid)

          throw new ViewDisposedException("Snapshot has been disposed");

        updatecheck();

        addSorted(items, true, true);

      }

    }

    #region add-sorted helpers

    //Create a RB tree from x+2^h-1  (x < 2^h, h>=1) nodes taken from a

    //singly linked list of red nodes using only the right child refs.

    //The x nodes at depth h+1 will be red, the rest black.

    //(h is the blackdepth of the resulting tree)

    static Node maketreer(ref Node rest, int blackheight, int maxred, int red)

    {

      if (blackheight == 1)

      {

        Node top = rest;

        rest = rest.right;

        if (red > 0)

        {

          top.right = null;

          rest.left = top;

          top = rest;

#if BAG

          top.size += top.left.size;

#elif MAINTAIN_SIZE

          top.size = 1 + red;

#endif

          rest = rest.right;

          red--;

        }

        if (red > 0)

        {

#if BAG

          top.size += rest.size;

#endif

          top.right = rest;

          rest = rest.right;

          top.right.right = null;

        }

        else

          top.right = null;

        top.red = false;

        return top;

      }

      else

      {

        maxred >>= 1;

        int lred = red > maxred ? maxred : red;

        Node left = maketreer(ref rest, blackheight - 1, maxred, lred);

        Node top = rest;

        rest = rest.right;

        top.left = left;

        top.red = false;

        top.right = maketreer(ref rest, blackheight - 1, maxred, red - lred);

#if BAG

        top.size = top.items + top.left.size + top.right.size;

#elif MAINTAIN_SIZE

        top.size = (maxred << 1) - 1 + red;

#endif

        return top;

      }

    }

    void addSorted<U>(SCG.IEnumerable<U> items, bool safe, bool raise) where U : T

    {

      SCG.IEnumerator<U> e = items.GetEnumerator(); ;

      if (size > 0)

        throw new InternalException("This can't happen");

      if (!e.MoveNext())

        return;

      //To count theCollect 

      Node head = new Node(), tail = head;

      int z = 1;

      T lastitem = tail.item = e.Current;

#if BAG

      int ec = 0;

#endif

      while (e.MoveNext())

      {

#if BAG

        T thisitem = e.Current;

        int comp = comparer.Compare(lastitem, thisitem);

        if (comp > 0)

          throw new ArgumentException("Argument not sorted");

        if (comp == 0)

        {

          tail.items++;

          ec++;

        }

        else

        {

          tail.size = tail.items;

          z++;

          tail.right = new Node();

          tail = tail.right;

          lastitem = tail.item = thisitem;

#if NCP

          tail.generation = generation;

#endif

        }

#else

        z++;

        tail.right = new Node();

        tail = tail.right;

        tail.item = e.Current;

        if (safe)

        {

          if (comparer.Compare(lastitem, tail.item) >= 0)

            throw new ArgumentException("Argument not sorted");

          lastitem = tail.item;

        }

#if NCP

        tail.generation = generation;

#endif

#endif

      }

#if BAG

      tail.size = tail.items;

#endif

      int blackheight = 0, red = z, maxred = 1;

      while (maxred <= red)

      {

        red -= maxred;

        maxred <<= 1;

        blackheight++;

      }

      root = TreeBag<T>.maketreer(ref head, blackheight, maxred, red);

      blackdepth = blackheight;

      size = z;

#if BAG

      size += ec;

#endif

      if (raise)

      {

        if ((ActiveEvents & EventTypeEnum.Added) != 0)

        {

          CircularQueue<T> wasAdded = new CircularQueue<T>();

          foreach (T item in this)

            wasAdded.Enqueue(item);

          foreach (T item in wasAdded)

            raiseItemsAdded(item, 1);

        }

        if ((ActiveEvents & EventTypeEnum.Changed) != 0)

          raiseCollectionChanged();

      }

      return;

    }

    #endregion

#if BAG

    /// <summary></summary>

    /// <value>True since this collection has bag semantics.</value>

    [Tested]

    public bool AllowsDuplicates { [Tested]get { return true; } }

#else

    /// <summary></summary>

    /// <value>False since this tree has set semantics.</value>

    [Tested]

    public bool AllowsDuplicates { [Tested]get { return false; } }

#endif

    /// <summary>

    /// By convention this is true for any collection with set semantics.

    /// </summary>

    /// <value>True if only one representative of a group of equal items 

    /// is kept in the collection together with the total count.</value>

    public virtual bool DuplicatesByCounting { get { return true; } }

    #endregion

    #region IEditableCollection<T> Members

    /// <summary>

    /// The value is symbolic indicating the type of asymptotic complexity

    /// in terms of the size of this collection (worst-case or amortized as

    /// relevant).

    /// </summary>

    /// <value>Speed.Log</value>

    [Tested]

    public Speed ContainsSpeed { [Tested]get { return Speed.Log; } }

    /// <summary>

    /// Check if this collection contains (an item equivalent to according to the

    /// itemequalityComparer) a particular value.

    /// </summary>

    /// <param name="item">The value to check for.</param>

    /// <returns>True if the items is in this collection.</returns>

    [Tested]

    public bool Contains(T item)

    {

      if (!isValid)

        throw new ViewDisposedException("Snapshot has been disposed");

      Node next; int comp = 0;

      next = root;

      while (next != null)

      {

        comp = comparer.Compare(next.item, item);

        if (comp == 0)

          return true;

        next = comp < 0 ? right(next) : left(next);

      }

      return false;

    }

    //Variant for dictionary use

    //Will return the actual matching item in the ref argument.

    /// <summary>

    /// Check if this collection contains an item equivalent according to the

    /// itemequalityComparer to a particular value. If so, return in the ref argument (a

    /// binary copy of) the actual value found.

    /// </summary>

    /// <param name="item">The value to look for.</param>

    /// <returns>True if the items is in this collection.</returns>

    [Tested]

    public bool Find(ref T item)

    {

      if (!isValid)

        throw new ViewDisposedException("Snapshot has been disposed");

      Node next; int comp = 0;

      next = root;

      while (next != null)

      {

        comp = comparer.Compare(next.item, item);

        if (comp == 0)

        {

          item = next.item;

          return true;

        }

        next = comp < 0 ? right(next) : left(next);

      }

      return false;

    }

    /// <summary>

    /// Find or add the item to the tree. If the tree does not contain

    /// an item equivalent to this item add it, else return the exisiting

    /// one in the ref argument. 

    ///

    /// </summary>

    /// <param name="item"></param>

    /// <returns>True if item was found</returns>

    [Tested]

    public bool FindOrAdd(ref T item)

    {

      if (!isValid)

        throw new ViewDisposedException("Snapshot has been disposed");

      updatecheck();

      bool wasfound;

      //Note: blackdepth of the tree is set inside addIterative

      if (addIterative(item, ref item, false, out wasfound))

      {

        size++;

        if (ActiveEvents != 0 && !wasfound)

          raiseForAdd(item);

        return wasfound;

      }

      else

        return true;

    }

    //For dictionary use. 

    //If found, the matching entry will be updated with the new item.

    /// <summary>

    /// Check if this collection contains an item equivalent according to the

    /// itemequalityComparer to a particular value. If so, update the item in the collection 

    /// to with a binary copy of the supplied value. If the collection has bag semantics,

    /// this updates all equivalent copies in

    /// the collection.

    /// </summary>

    /// <param name="item">Value to update.</param>

    /// <returns>True if the item was found and hence updated.</returns>

    [Tested]

    public bool Update(T item)

    {

      T olditem = item;

      return Update(item, out olditem);

    }

    /// <summary>

    /// Check if this collection contains an item equivalent according to the

    /// itemequalityComparer to a particular value. If so, update the item in the collection 

    /// with a binary copy of the supplied value. If the collection has bag semantics,

    /// this updates all equivalent copies in

    /// the collection.

    /// </summary>

    /// <param name="item"></param>

    /// <param name="olditem"></param>

    /// <returns></returns>

    public bool Update(T item, out T olditem)

    {

      if (!isValid)

        throw new ViewDisposedException("Snapshot has been disposed");

      updatecheck();

#if NCP

      stackcheck();

      int level = 0;

#endif

      Node cursor = root;

      int comp = 0;

      while (cursor != null)

      {

        comp = comparer.Compare(cursor.item, item);

        if (comp == 0)

        {

#if NCP

          Node.CopyNode(ref cursor, maxsnapid, generation);

#endif

          olditem = cursor.item;

#if BAG

          int items = cursor.items;

#endif

          cursor.item = item;

#if NCP

          while (level > 0)

          {

            Node child = cursor;

            cursor = path[--level];

            path[level] = null;

#if NCP

            Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);

#else

						if (Node.CopyNode(maxsnapid, ref cursor, generation))

						{

							if (dirs[level] > 0)

								cursor.left = child;

							else

								cursor.right = child;

						}

#endif

          }

          root = cursor;

#endif

#if BAG

          if (ActiveEvents != 0)

            raiseForUpdate(item, olditem, items);

#else

          if (ActiveEvents != 0)

            raiseForUpdate(item, olditem);

#endif

          return true;

        }

#if NCP

        dirs[level] = comp;

        path[level++] = cursor;

#endif

        cursor = comp < 0 ? cursor.right : cursor.left;

      }

      olditem = default(T);

      return false;

    }

    /// <summary>

    /// Check if this collection contains an item equivalent according to the

    /// itemequalityComparer to a particular value. If so, update the item in the collection 

    /// with a binary copy of the supplied value; else add the value to the collection. 

    ///

    /// <i>NOTE: the bag implementation is currently wrong! ?????</i>

    /// </summary>

    /// <param name="item">Value to add or update.</param>

    /// <returns>True if the item was found and updated (hence not added).</returns>

    [Tested]

    public bool UpdateOrAdd(T item)

    { T olditem; return UpdateOrAdd(item, out olditem); }

    /// <summary>

    /// 

    /// </summary>

    /// <param name="item"></param>

    /// <param name="olditem"></param>

    /// <returns></returns>

    public bool UpdateOrAdd(T item, out T olditem)

    {

      if (!isValid)

        throw new ViewDisposedException("Snapshot has been disposed");

      updatecheck();

      bool wasfound;

      olditem = default(T);

      //Note: blackdepth of the tree is set inside addIterative

      if (addIterative(item, ref olditem, true, out wasfound))

      {

        size++;

        if (ActiveEvents != 0)

          raiseForAdd(wasfound ? olditem : item);

        return wasfound;

      }

      else

      {

#warning for bag implementation: count is wrong

        if (ActiveEvents != 0)

          raiseForUpdate(item, olditem, 1);

        return true;

      }

    }

    /// <summary>

    /// Remove a particular item from this collection. If the collection has bag

    /// semantics only one copy equivalent to the supplied item is removed. 

    /// </summary>

    /// <param name="item">The value to remove.</param>

    /// <returns>True if the item was found (and removed).</returns>

    [Tested]

    public bool Remove(T item)

    {

      if (!isValid)

        throw new ViewDisposedException("Snapshot has been disposed");

      updatecheck();

      if (root == null)

        return false;

      int junk;

      bool retval = removeIterative(ref item, false, out junk);

      if (ActiveEvents != 0 && retval)

        raiseForRemove(item);

      return retval;

    }

    /// <summary>

    /// Remove a particular item from this collection if found. If the collection

    /// has bag semantics only one copy equivalent to the supplied item is removed,

    /// which one is implementation dependent. 

    /// If an item was removed, report a binary copy of the actual item removed in 

    /// the argument.

    /// </summary>

    /// <param name="item">The value to remove.</param>

    /// <param name="removeditem">The removed value.</param>