context: /*
   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.
  */
  
  using System;
  using SCG = System.Collections.Generic;
  
  namespace C5
  {
      /// <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>
      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];
  
          //TODO: refactor into separate class
          bool isSnapShot = false;
  
          int generation;
  
          bool isValid = true;
  
          SnapRef snapList;
  
          #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 (isSnapShot)
              {
  
                  if (n.lastgeneration >= generation && n.leftnode)
                      return n.oldref;
              }
              return n.left;
          }
  
  
          private Node right(Node n)
          {
              if (isSnapShot)
              {
  
                  if (n.lastgeneration >= generation && !n.leftnode)
                      return n.oldref;
              }
              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>
          class Node
          {
              public bool red = true;
  
              public T item;
  
              public Node left;
  
              public Node right;
  
              public int size = 1;
  
              public int items = 1;
  
  
              //TODO: move everything into (separate) Extra
              public int generation;
  
              public int lastgeneration = -1;
  
              public Node oldref;
  
              public bool leftnode;
  
              /// <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 (cursor.lastgeneration == -1)
                      {
                          cursor.leftnode = leftnode;
                          cursor.lastgeneration = maxsnapid;
                          cursor.oldref = oldref;
                      }
                      else if (cursor.leftnode != leftnode || cursor.lastgeneration < maxsnapid)
                      {
                          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;
                      cursor.lastgeneration = -1;
                      return true;
                  }
  
                  return false;
              }
          }
  
          #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(SCG.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 equalitySCG.Comparer</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>
              public T Current
              {
                  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>
              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>
              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 NotImplementedException();
              }
  
              #endregion
          }
  
          /// <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;
  
              int togo;
  
  
              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>
              public bool MoveNext()
              {
                  tree.modifycheck(stamp);//???
  
  
                  if (--togo > 0)
                      return true;
                  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];
  
  
                  togo = cursor.items;
  
                  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>
              public T Current
              {
                  get
                  {
                      if (valid)
                          return current;
                      else
                          throw new InvalidOperationException();
                  }
              }
  
              #endregion
  
              #region IDisposable Members
  
              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 NotImplementedException();
              }
  
              #endregion
          }
  
          #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;
                  }
              }
  
              int togo = node.items;
              while (togo-- > 0)
              {
                  modifycheck(origstamp);
                  yield return node.item;
              }
  
              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>
          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>
          public override SCG.IEnumerator<T> GetEnumerator()
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
  
              if (isSnapShot)
                  return new SnapEnumerator(this);
  
              return getEnumerator(root, stamp);
  
          }
  
          #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;
                  root.generation = generation;
                  return true;
              }
  
              stackcheck();
  
              int level = 0;
              Node cursor = root;
  
              while (true)
              {
                  int comp = comparer.Compare(cursor.item, item);
  
                  if (comp == 0)
                  {
                      founditem = cursor.item;
  
                      wasfound = true;
                      bool nodeWasUpdated = true;
                      Node.CopyNode(ref cursor, maxsnapid, generation);
                      if (update)
                          cursor.item = item;
                      else
                      {
                          cursor.items++;
                          cursor.size++;
                      }
  
  
                      while (level-- > 0)
                      {
                          if (nodeWasUpdated)
                          {
                              Node kid = cursor;
  
                              cursor = path[level];
                              Node.update(ref cursor, dirs[level] > 0, kid, maxsnapid, generation);
  
                              if (!update)
                                  cursor.size++;
  
                          }
  
                          path[level] = null;
                      }
  
                      return !update;
  
                  }
  
                  //else
                  Node child = comp > 0 ? cursor.left : cursor.right;
  
                  if (child == null)
                  {
                      child = new Node();
                      child.item = item;
                      child.generation = generation;
                      Node.update(ref cursor, comp > 0, child, maxsnapid, generation);
  
  
                      cursor.size++;
  
                      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;
                  Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);
  
                  cursor.size++;
  
                  int comp = dirs[level];
                  Node childsibling = comp > 0 ? cursor.right : cursor.left;
  
                  if (childsibling != null && childsibling.red)
                  {
                      //Promote
                      child.red = false;
                      Node.update(ref cursor, comp < 0, childsibling, maxsnapid, generation);
                      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;
                          child = cursor;
                          cursor = path[--level];
                          Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);
                          path[level] = null;
  
                          cursor.size++;
  
                      }
                  }
                  else
                  {
                      //ROTATE!!!
                      int childcomp = dirs[level + 1];
  
                      cursor.red = true;
                      if (comp > 0)
                      {
                          if (childcomp > 0)
                          {//zagzag
                              Node.update(ref cursor, true, child.right, maxsnapid, generation);
                              Node.update(ref child, false, cursor, maxsnapid, generation);
  
                              cursor = child;
                          }
                          else
                          {//zagzig
                              Node badgrandchild = child.right;
                              Node.update(ref cursor, true, badgrandchild.right, maxsnapid, generation);
                              Node.update(ref child, false, badgrandchild.left, maxsnapid, generation);
                              Node.CopyNode(ref badgrandchild, maxsnapid, generation);
  
                              badgrandchild.left = child;
                              badgrandchild.right = cursor;
                              cursor = badgrandchild;
                          }
                      }
                      else
                      {//comp < 0
                          if (childcomp < 0)
                          {//zigzig
                              Node.update(ref cursor, false, child.left, maxsnapid, generation);
                              Node.update(ref child, true, cursor, maxsnapid, generation);
  
                              cursor = child;
                          }
                          else
                          {//zigzag
                              Node badgrandchild = child.left;
                              Node.update(ref cursor, false, badgrandchild.left, maxsnapid, generation);
                              Node.update(ref child, true, badgrandchild.right, maxsnapid, generation);
                              Node.CopyNode(ref badgrandchild, maxsnapid, generation);
  
                              badgrandchild.right = child;
                              badgrandchild.left = cursor;
                              cursor = badgrandchild;
                          }
                      }
  
                      cursor.red = false;
  
                      Node n;
  
                      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;
  
                      if (level == 0)
                      {
                          root = cursor;
                          return true;
                      }
                      else
                      {
                          child = cursor;
                          cursor = path[--level];
                          path[level] = null;
                          Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);
  
  
                          cursor.size++;
                          break;
                      }
                  }
              }
              bool stillmore = true;
              while (level > 0)
              {
                  Node child = cursor;
  
                  cursor = path[--level];
                  path[level] = null;
                  if (stillmore)
                      stillmore = Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);
                  cursor.size++;
  
              }
  
              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>
          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>
          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>
          /// <param name="items">The items to add</param>
          public void AddAll(SCG.IEnumerable<T> items)
          {
              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>
          public void AddSorted(SCG.IEnumerable<T> items)
          {
              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;
  
                      top.size += top.left.size;
  
                      rest = rest.right;
                      red--;
                  }
  
                  if (red > 0)
                  {
  
                      top.size += rest.size;
  
                      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);
  
                  top.size = top.items + top.left.size + top.right.size;
  
                  return top;
              }
          }
  
  
          void addSorted(SCG.IEnumerable<T> items, bool safe, bool raise)
          {
              SCG.IEnumerator<T> 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;
  
              int ec = 0;
  
              while (e.MoveNext())
              {
  
                  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;
                      tail.generation = generation;
                  }
  
              }
  
              tail.size = tail.items;
  
              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;
  
              size += ec;
  
              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
  
  
          /// <summary></summary>
          /// <value>True since this collection has bag semantics.</value>
          public bool AllowsDuplicates { get { return true; } }
  
          /// <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>
          public Speed ContainsSpeed { 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>
          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>
          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>
          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>
          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();
              stackcheck();
  
              int level = 0;
              Node cursor = root;
              int comp = 0;
  
              while (cursor != null)
              {
                  comp = comparer.Compare(cursor.item, item);
                  if (comp == 0)
                  {
                      Node.CopyNode(ref cursor, maxsnapid, generation);
                      olditem = cursor.item;
  
                      int items = cursor.items;
  
                      cursor.item = item;
                      while (level > 0)
                      {
                          Node child = cursor;
  
                          cursor = path[--level];
                          path[level] = null;
                          Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);
  
                      }
  
                      root = cursor;
  
                      if (ActiveEvents != 0)
                          raiseForUpdate(item, olditem, items);
  
                      return true;
                  }
                  dirs[level] = comp;
                  path[level++] = cursor;
                  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>
          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>
          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>
          /// <returns>True if the item was found (and removed).</returns>
          public bool Remove(T item, out T removeditem)
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
              updatecheck();
              removeditem = item;
              if (root == null)
                  return false;
  
              int junk;
              bool retval = removeIterative(ref removeditem, false, out junk);
              if (ActiveEvents != 0 && retval)
                  raiseForRemove(item);
              return retval;
          }
  
          /// <summary>
          /// 
          /// </summary>
          /// <param name="item">input: item to remove; output: item actually removed</param>
          /// <param name="all">If true, remove all copies</param>
          /// <param name="wasRemoved"></param>
          /// <returns></returns>
          private bool removeIterative(ref T item, bool all, out int wasRemoved)
          {
              wasRemoved = 0;
              //Stage 1: find item
              stackcheck();
  
              int level = 0, comp;
              Node cursor = root;
  
              while (true)
              {
                  comp = comparer.Compare(cursor.item, item);
                  if (comp == 0)
                  {
                      item = cursor.item;
  
                      if (!all && cursor.items > 1)
                      {
                          Node.CopyNode(ref cursor, maxsnapid, generation);
                          cursor.items--;
                          cursor.size--;
                          while (level-- > 0)
                          {
                              Node kid = cursor;
  
                              cursor = path[level];
                              Node.update(ref cursor, dirs[level] > 0, kid, maxsnapid, generation);
                              cursor.size--;
                              path[level] = null;
                          }
                          size--;
                          wasRemoved = 1;
                          return true;
                      }
                      wasRemoved = cursor.items;
  
                      break;
                  }
  
                  Node child = comp > 0 ? cursor.left : cursor.right;
  
                  if (child == null)
                      return false;
  
                  dirs[level] = comp;
                  path[level++] = cursor;
                  cursor = child;
              }
  
              return removeIterativePhase2(cursor, level);
          }
  
  
          private bool removeIterativePhase2(Node cursor, int level)
          {
              if (size == 1)
              {
                  clear();
                  return true;
              }
  
  
              size -= cursor.items;
  
              //Stage 2: if item's node has no null child, find predecessor
              int level_of_item = level;
  
              if (cursor.left != null && cursor.right != null)
              {
                  dirs[level] = 1;
                  path[level++] = cursor;
                  cursor = cursor.left;
                  while (cursor.right != null)
                  {
                      dirs[level] = -1;
                      path[level++] = cursor;
                      cursor = cursor.right;
                  }
                  Node.CopyNode(ref path[level_of_item], maxsnapid, generation);
                  path[level_of_item].item = cursor.item;
  
                  path[level_of_item].items = cursor.items;
  
              }
  
              //Stage 3: splice out node to be removed
              Node newchild = cursor.right == null ? cursor.left : cursor.right;
              bool demote_or_rotate = newchild == null && !cursor.red;
  
              //assert newchild.red 
              if (newchild != null)
              {
                  newchild.red = false;
              }
  
              if (level == 0)
              {
                  root = newchild;
                  return true;
              }
  
              level--;
              cursor = path[level];
              path[level] = null;
  
              int comp = dirs[level];
              Node childsibling;
              Node.update(ref cursor, comp > 0, newchild, maxsnapid, generation);
  
              childsibling = comp > 0 ? cursor.right : cursor.left;
  
              cursor.size = cursor.items + (newchild == null ? 0 : newchild.size) + (childsibling == null ? 0 : childsibling.size);
  
  
              //Stage 4: demote till we must rotate
              Node farnephew = null, nearnephew = null;
  
              while (demote_or_rotate)
              {
                  if (childsibling.red)
                      break; //rotate 2+?
  
                  farnephew = comp > 0 ? childsibling.right : childsibling.left;
                  if (farnephew != null && farnephew.red)
                      break; //rotate 1b
  
                  nearnephew = comp > 0 ? childsibling.left : childsibling.right;
                  if (nearnephew != null && nearnephew.red)
                      break; //rotate 1c
  
                  //demote cursor
                  childsibling.red = true;
                  if (level == 0)
                  {
                      cursor.red = false;
                      blackdepth--;
                      root = cursor;
                      return true;
                  }
                  else if (cursor.red)
                  {
                      cursor.red = false;
                      demote_or_rotate = false;
                      break; //No rotation
                  }
                  else
                  {
                      Node child = cursor;
  
                      cursor = path[--level];
                      path[level] = null;
                      comp = dirs[level];
                      childsibling = comp > 0 ? cursor.right : cursor.left;
                      Node.update(ref cursor, comp > 0, child, maxsnapid, generation);
  
                      cursor.size = cursor.items + (child == null ? 0 : child.size) + (childsibling == null ? 0 : childsibling.size);
  
                  }
              }
  
              //Stage 5: rotate 
              if (demote_or_rotate)
              {
                  //At start:
                  //parent = cursor (temporary for swapping nodes)
                  //childsibling is the sibling of the updated child (x)
                  //cursor is always the top of the subtree
                  Node parent = cursor;
  
                  if (childsibling.red)
                  {//Case 2 and perhaps more. 
                      //The y.rank == px.rank >= x.rank+2 >=2 so both nephews are != null 
                      //(and black). The grandnephews are children of nearnephew
                      Node neargrandnephew, fargrandnephew;
  
                      if (comp > 0)
                      {
                          nearnephew = childsibling.left;
                          farnephew = childsibling.right;
                          neargrandnephew = nearnephew.left;
                          fargrandnephew = nearnephew.right;
                      }
                      else
                      {
                          nearnephew = childsibling.right;
                          farnephew = childsibling.left;
                          neargrandnephew = nearnephew.right;
                          fargrandnephew = nearnephew.left;
                      }
  
                      if (fargrandnephew != null && fargrandnephew.red)
                      {//Case 2+1b
                          Node.CopyNode(ref nearnephew, maxsnapid, generation);
  
                          //The end result of this will always be e copy of parent
                          Node.update(ref parent, comp < 0, neargrandnephew, maxsnapid, generation);
                          Node.update(ref childsibling, comp > 0, nearnephew, maxsnapid, generation);
                          if (comp > 0)
                          {
                              nearnephew.left = parent;
                              parent.right = neargrandnephew;
                          }
                          else
                          {
                              nearnephew.right = parent;
                              parent.left = neargrandnephew;
                          }
  
                          cursor = childsibling;
                          childsibling.red = false;
                          nearnephew.red = true;
                          fargrandnephew.red = false;
  
                          cursor.size = parent.size;
                          nearnephew.size = cursor.size - cursor.items - farnephew.size;
                          parent.size = nearnephew.size - nearnephew.items - fargrandnephew.size;
  
                      }
                      else if (neargrandnephew != null && neargrandnephew.red)
                      {//Case 2+1c
                          Node.CopyNode(ref neargrandnephew, maxsnapid, generation);
                          if (comp > 0)
                          {
                              Node.update(ref childsibling, true, neargrandnephew, maxsnapid, generation);
                              Node.update(ref nearnephew, true, neargrandnephew.right, maxsnapid, generation);
                              Node.update(ref parent, false, neargrandnephew.left, maxsnapid, generation);
                              neargrandnephew.left = parent;
                              neargrandnephew.right = nearnephew;
                          }
                          else
                          {
                              Node.update(ref childsibling, false, neargrandnephew, maxsnapid, generation);
                              Node.update(ref nearnephew, false, neargrandnephew.left, maxsnapid, generation);
                              Node.update(ref parent, true, neargrandnephew.right, maxsnapid, generation);
                              neargrandnephew.right = parent;
                              neargrandnephew.left = nearnephew;
                          }
  
                          cursor = childsibling;
                          childsibling.red = false;
  
                          cursor.size = parent.size;
                          parent.size = parent.items + (parent.left == null ? 0 : parent.left.size) + (parent.right == null ? 0 : parent.right.size);
                          nearnephew.size = nearnephew.items + (nearnephew.left == null ? 0 : nearnephew.left.size) + (nearnephew.right == null ? 0 : nearnephew.right.size);
                          neargrandnephew.size = neargrandnephew.items + parent.size + nearnephew.size;
  
                      }
                      else
                      {//Case 2 only
                          Node.update(ref parent, comp < 0, nearnephew, maxsnapid, generation);
                          Node.update(ref childsibling, comp > 0, parent, maxsnapid, generation);
  
                          cursor = childsibling;
                          childsibling.red = false;
                          nearnephew.red = true;
  
                          cursor.size = parent.size;
                          parent.size -= farnephew.size + cursor.items;
  
                      }
                  }
                  else if (farnephew != null && farnephew.red)
                  {//Case 1b
                      nearnephew = comp > 0 ? childsibling.left : childsibling.right;
                      Node.update(ref parent, comp < 0, nearnephew, maxsnapid, generation);
                      Node.CopyNode(ref childsibling, maxsnapid, generation);
                      if (comp > 0)
                      {
                          childsibling.left = parent;
                          childsibling.right = farnephew;
                      }
                      else
                      {
                          childsibling.right = parent;
                          childsibling.left = farnephew;
                      }
  
                      cursor = childsibling;
                      cursor.red = parent.red;
                      parent.red = false;
                      farnephew.red = false;
  
  
                      cursor.size = parent.size;
                      parent.size -= farnephew.size + cursor.items;
  
                  }
                  else if (nearnephew != null && nearnephew.red)
                  {//Case 1c
                      Node.CopyNode(ref nearnephew, maxsnapid, generation);
                      if (comp > 0)
                      {
                          Node.update(ref childsibling, true, nearnephew.right, maxsnapid, generation);
                          Node.update(ref parent, false, nearnephew.left, maxsnapid, generation);
  
                          nearnephew.left = parent;
                          nearnephew.right = childsibling;
                      }
                      else
                      {
                          Node.update(ref childsibling, false, nearnephew.left, maxsnapid, generation);
                          Node.update(ref parent, true, nearnephew.right, maxsnapid, generation);
  
                          nearnephew.right = parent;
                          nearnephew.left = childsibling;
                      }
  
                      cursor = nearnephew;
                      cursor.red = parent.red;
                      parent.red = false;
  
                      cursor.size = parent.size;
                      parent.size = parent.items + (parent.left == null ? 0 : parent.left.size) + (parent.right == null ? 0 : parent.right.size);
                      childsibling.size = childsibling.items + (childsibling.left == null ? 0 : childsibling.left.size) + (childsibling.right == null ? 0 : childsibling.right.size);
  
                  }
                  else
                  {//Case 1a can't happen
                      throw new InternalException("Case 1a can't happen here");
                  }
  
                  //Resplice cursor:
                  if (level == 0)
                  {
                      root = cursor;
                  }
                  else
                  {
                      Node swap = cursor;
  
                      cursor = path[--level];
                      path[level] = null;
                      Node.update(ref cursor, dirs[level] > 0, swap, maxsnapid, generation);
  
  
                      cursor.size = cursor.items + (cursor.right == null ? 0 : cursor.right.size) + (cursor.left == null ? 0 : cursor.left.size);
  
                  }
              }
  
              //Stage 6: fixup to the root
              while (level > 0)
              {
                  Node child = cursor;
  
                  cursor = path[--level];
                  path[level] = null;
                  if (child != (dirs[level] > 0 ? cursor.left : cursor.right))
                      Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);
  
  
                  cursor.size = cursor.items + (cursor.right == null ? 0 : cursor.right.size) + (cursor.left == null ? 0 : cursor.left.size);
  
              }
  
              root = cursor;
              return true;
          }
  
  
          /// <summary>
          /// Remove all items from this collection.
          /// </summary>
          public void Clear()
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
              updatecheck();
              if (size == 0)
                  return;
              int oldsize = size;
              clear();
              if ((ActiveEvents & EventTypeEnum.Cleared) != 0)
                  raiseCollectionCleared(true, oldsize);
              if ((ActiveEvents & EventTypeEnum.Changed) != 0)
                  raiseCollectionChanged();
          }
  
  
          private void clear()
          {
              size = 0;
              root = null;
              blackdepth = 0;
          }
  
  
          /// <summary>
          /// Remove all items in another collection from this one. If this collection
          /// has bag semantics, take multiplicities into account.
          /// </summary>
          /// <param name="items">The items to remove.</param>
          public void RemoveAll(SCG.IEnumerable<T> items)
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
              updatecheck();
  
              T jtem;
  
              bool mustRaise = (ActiveEvents & (EventTypeEnum.Removed | EventTypeEnum.Changed)) != 0;
              RaiseForRemoveAllHandler raiseHandler = mustRaise ? new RaiseForRemoveAllHandler(this) : null;
  
              foreach (T item in items)
              {
                  if (root == null)
                      break;
  
                  jtem = item;
                  int junk;
                  if (removeIterative(ref jtem, false, out junk) && mustRaise)
                      raiseHandler.Remove(jtem);
              }
              if (mustRaise)
                  raiseHandler.Raise();
          }
  
          /// <summary>
          /// Remove all items not in some other collection from this one. If this collection
          /// has bag semantics, take multiplicities into account.
          /// </summary>
          /// <param name="items">The items to retain.</param>
          public void RetainAll(SCG.IEnumerable<T> items)
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
              updatecheck();
  
              //A much more efficient version is possible if items is sorted like this.
              //Well, it is unclear how efficient it would be.
              //We could use a marking method!?
  #warning how does this work together with persistence?
              TreeBag<T> t = (TreeBag<T>)MemberwiseClone();
  
              T jtem = default(T);
              t.clear();
              foreach (T item in items)
                  if (ContainsCount(item) > t.ContainsCount(item))
                  {
                      t.add(item, ref jtem);
                  }
              if (size == t.size)
                  return;
  
  #warning improve (mainly for bag) by using a Node iterator instead of ItemMultiplicities()
              CircularQueue<KeyValuePair<T, int>> wasRemoved = null;
              if ((ActiveEvents & EventTypeEnum.Removed) != 0)
              {
                  wasRemoved = new CircularQueue<KeyValuePair<T, int>>();
                  SCG.IEnumerator<KeyValuePair<T, int>> ie = ItemMultiplicities().GetEnumerator();
                  foreach (KeyValuePair<T, int> p in t.ItemMultiplicities())
                  {
                      //We know p.Key is in this!
                      while (ie.MoveNext())
                      {
                          if (comparer.Compare(ie.Current.Key, p.Key) == 0)
                          {
  
                              int removed = ie.Current.Value - p.Value;
                              if (removed > 0)
                                  wasRemoved.Enqueue(new KeyValuePair<T, int>(p.Key, removed));
  
                              break;
                          }
                          else
                              wasRemoved.Enqueue(ie.Current);
                      }
                  }
                  while (ie.MoveNext())
                      wasRemoved.Enqueue(ie.Current);
              }
  
              root = t.root;
              size = t.size;
              blackdepth = t.blackdepth;
              if (wasRemoved != null)
                  foreach (KeyValuePair<T, int> p in wasRemoved)
                      raiseItemsRemoved(p.Key, p.Value);
              if ((ActiveEvents & EventTypeEnum.Changed) != 0)
                  raiseCollectionChanged();
          }
  
          /// <summary>
          /// Check if this collection contains all the values in another collection.
          /// If this collection has bag semantics (<code>AllowsDuplicates==true</code>)
          /// the check is made with respect to multiplicities, else multiplicities
          /// are not taken into account.
          /// </summary>
          /// <param name="items">The </param>
          /// <returns>True if all values in <code>items</code>is in this collection.</returns>
          public bool ContainsAll(SCG.IEnumerable<T> items)
          {
              //TODO: fix bag implementation
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
              //This is worst-case O(m*logn)
              foreach (T item in items)
                  if (!Contains(item)) return false;
  
              return true;
          }
  
  
          //Higher order:
          /// <summary>
          /// Create a new indexed sorted collection consisting of the items of this
          /// indexed sorted collection satisfying a certain predicate.
          /// </summary>
          /// <param name="filter">The filter delegate defining the predicate.</param>
          /// <returns>The new indexed sorted collection.</returns>
          public IIndexedSorted<T> FindAll(Func<T, bool> filter)
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
              TreeBag<T> res = new TreeBag<T>(comparer);
              SCG.IEnumerator<T> e = GetEnumerator();
              Node head = null, tail = null;
              int z = 0;
  
              int ec = 0;
  
              while (e.MoveNext())
              {
                  T thisitem = e.Current;
  
                  //We could document that filter will only be called 
                  //once on each unique item. That might even be good for the user!
                  if (tail != null && comparer.Compare(thisitem, tail.item) == 0)
                  {
                      tail.items++;
                      ec++;
                      continue;
                  }
  
                  if (filter(thisitem))
                  {
                      if (head == null)
                      {
                          head = tail = new Node();
                      }
                      else
                      {
  
                          tail.size = tail.items;
                          tail.right = new Node();
                          tail = tail.right;
                      }
  
                      tail.item = thisitem;
                      z++;
                  }
              }
  
              if (tail != null)
                  tail.size = tail.items;
  
  
              if (z == 0)
                  return res;
  
              int blackheight = 0, red = z, maxred = 1;
  
              while (maxred <= red)
              {
                  red -= maxred;
                  maxred <<= 1;
                  blackheight++;
              }
  
              res.root = TreeBag<T>.maketreer(ref head, blackheight, maxred, red);
              res.blackdepth = blackheight;
              res.size = z;
  
              res.size += ec;
  
              return res;
          }
  
  
          /// <summary>
          /// Create a new indexed sorted collection consisting of the results of
          /// mapping all items of this list.
          /// <exception cref="ArgumentException"/> if the map is not increasing over 
          /// the items of this collection (with respect to the two given comparison 
          /// relations).
          /// </summary>
          /// <param name="mapper">The delegate definging the map.</param>
          /// <param name="c">The comparion relation to use for the result.</param>
          /// <returns>The new sorted collection.</returns>
          public IIndexedSorted<V> Map<V>(Func<T, V> mapper, SCG.IComparer<V> c)
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
              TreeBag<V> res = new TreeBag<V>(c);
  
              if (size == 0)
                  return res;
  
              SCG.IEnumerator<T> e = GetEnumerator();
              TreeBag<V>.Node head = null, tail = null;
              V oldv = default(V);
              int z = 0;
  
              T lastitem = default(T);
  
              while (e.MoveNext())
              {
                  T thisitem = e.Current;
  
                  //We could document that mapper will only be called 
                  //once on each unique item. That might even be good for the user!
                  if (tail != null && comparer.Compare(thisitem, lastitem) == 0)
                  {
                      tail.items++;
                      continue;
                  }
  
                  V newv = mapper(thisitem);
  
                  if (head == null)
                  {
                      head = tail = new TreeBag<V>.Node();
                      z++;
                  }
                  else
                  {
                      int comp = c.Compare(oldv, newv);
  
                      if (comp == 0)
                      {
                          tail.items++;
                          continue;
                      }
                      if (comp > 0)
  
                          throw new ArgumentException("mapper not monotonic");
  
                      tail.size = tail.items;
  
                      tail.right = new TreeBag<V>.Node();
                      tail = tail.right;
                      z++;
                  }
  
                  lastitem = thisitem;
  
                  tail.item = oldv = newv;
              }
  
  
              tail.size = tail.items;
  
  
              int blackheight = 0, red = z, maxred = 1;
  
              while (maxred <= red)
              {
                  red -= maxred;
                  maxred <<= 1;
                  blackheight++;
              }
  
              res.root = TreeBag<V>.maketreer(ref head, blackheight, maxred, red);
              res.blackdepth = blackheight;
              res.size = size;
              return res;
          }
  
  
          //below is the bag utility stuff
          /// <summary>
          /// Count the number of items of the collection equal to a particular value.
          /// Returns 0 if and only if the value is not in the collection.
          /// </summary>
          /// <param name="item">The value to count.</param>
          /// <returns>The number of copies found.</returns>
          public int ContainsCount(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 next.items;
  
                  next = comp < 0 ? right(next) : left(next);
              }
  
              return 0;
  
          }
  
  
          //TODO: make work with snapshots
          class Multiplicities : CollectionValueBase<KeyValuePair<T, int>>, ICollectionValue<KeyValuePair<T, int>>
          {
              TreeBag<T> treebag;
              int origstamp;
              internal Multiplicities(TreeBag<T> treebag) { this.treebag = treebag; this.origstamp = treebag.stamp; }
              public override KeyValuePair<T, int> Choose() { return new KeyValuePair<T, int>(treebag.root.item, treebag.root.items); }
  
              public override SCG.IEnumerator<KeyValuePair<T, int>> GetEnumerator()
              {
                  return getEnumerator(treebag.root, origstamp); //TODO: NBNBNB
              }
  
              private SCG.IEnumerator<KeyValuePair<T, int>> getEnumerator(Node node, int origstamp)
              {
                  if (node == null)
                      yield break;
  
                  if (node.left != null)
                  {
                      SCG.IEnumerator<KeyValuePair<T, int>> child = getEnumerator(node.left, origstamp);
  
                      while (child.MoveNext())
                      {
                          treebag.modifycheck(origstamp);
                          yield return child.Current;
                      }
                  }
                  yield return new KeyValuePair<T, int>(node.item, node.items);
                  if (node.right != null)
                  {
                      SCG.IEnumerator<KeyValuePair<T, int>> child = getEnumerator(node.right, origstamp);
  
                      while (child.MoveNext())
                      {
                          treebag.modifycheck(origstamp);
                          yield return child.Current;
                      }
                  }
              }
  
              public override bool IsEmpty { get { return treebag.IsEmpty; } }
              public override int Count { get { int i = 0; foreach (KeyValuePair<T, int> p in this) i++; return i; } } //TODO: make better
              public override Speed CountSpeed { get { return Speed.Linear; } } //TODO: make better
          }
  
  
          /// <summary>
          /// 
          /// </summary>
          /// <returns></returns>
          public virtual ICollectionValue<T> UniqueItems()
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
  
              return new DropMultiplicity<T>(ItemMultiplicities());
  
          }
  
  
          /// <summary>
          /// 
          /// </summary>
          /// <returns></returns>
          public virtual ICollectionValue<KeyValuePair<T, int>> ItemMultiplicities()
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
  
              return new Multiplicities(this);
  
          }
  
          /// <summary>
          /// Remove all items equivalent to a given value.
          /// </summary>
          /// <param name="item">The value to remove.</param>
          public void RemoveAllCopies(T item)
          {
  
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
              updatecheck();
              int removed;
              if (removeIterative(ref item, true, out removed) && ActiveEvents != 0)
              {
                  raiseForRemove(item, removed);
              }
  
          }
  
  
          #endregion
  
          #region IIndexed<T> Members
  
          private Node findNode(int i)
          {
              if (isSnapShot)
                  throw new NotSupportedException("Indexing not supported for snapshots");
  
              Node next = root;
  
              if (i >= 0 && i < size)
                  while (true)
                  {
                      int j = next.left == null ? 0 : next.left.size;
  
                      if (i > j)
                      {
  
                          i -= j + next.items;
                          if (i < 0)
                              return next;
  
                          next = next.right;
                      }
                      else if (i == j)
                          return next;
                      else
                          next = next.left;
                  }
  
              throw new IndexOutOfRangeException();
  
          }
  
  
          /// <summary>
          /// <exception cref="IndexOutOfRangeException"/> if i is negative or
          /// &gt;= the size of the collection.
          /// </summary>
          /// <value>The i'th item of this list.</value>
          /// <param name="i">the index to lookup</param>
          public T this[int i] { get { return findNode(i).item; } }
  
          /// <summary>
          /// 
          /// </summary>
          /// <value></value>
          public virtual Speed IndexingSpeed { get { return Speed.Log; } }
  
  
          //TODO: return -upper instead of -1 in case of not found
          /// <summary>
          /// Searches for an item in this indexed collection going forwards from the start.
          /// </summary>
          /// <param name="item">Item to search for.</param>
          /// <returns>Index of first occurrence from start of the item
          /// if found, else the two-complement 
          /// (always negative) of the index at which the item would be put if it was added.</returns>
          public int IndexOf(T item)
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
              int upper;
              return indexOf(item, out upper);
          }
  
  
          private int indexOf(T item, out int upper)
          {
              if (isSnapShot)
                  throw new NotSupportedException("Indexing not supported for snapshots");
  
              int ind = 0; Node next = root;
  
              while (next != null)
              {
                  int comp = comparer.Compare(item, next.item);
  
                  if (comp < 0)
                      next = next.left;
                  else
                  {
                      int leftcnt = next.left == null ? 0 : next.left.size;
  
                      if (comp == 0)
                      {
  
                          upper = ind + leftcnt + next.items - 1;
                          return ind + leftcnt;
  
                      }
                      else
                      {
  
                          ind = ind + next.items + leftcnt;
  
                          next = next.right;
                      }
                  }
              }
  
              upper = ~ind;
              return ~ind;
          }
  
  
          /// <summary>
          /// Searches for an item in the tree going backwords from the end.
          /// </summary>
          /// <param name="item">Item to search for.</param>
          /// <returns>Index of last occurrence from the end of item if found, 
          /// else the two-complement (always negative) of the index at which 
          /// the item would be put if it was added.</returns>
          public int LastIndexOf(T item)
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
  
              int res;
              indexOf(item, out res);
              return res;
  
          }
  
  
          /// <summary>
          /// Remove the item at a specific position of the list.
          /// <exception cref="IndexOutOfRangeException"/> if i is negative or
          /// &gt;= the size of the collection.
          /// </summary>
          /// <param name="i">The index of the item to remove.</param>
          /// <returns>The removed item.</returns>
          public T RemoveAt(int i)
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
              updatecheck();
              T retval = removeAt(i);
              if (ActiveEvents != 0)
                  raiseForRemove(retval);
              return retval;
          }
  
          T removeAt(int i)
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
              updatecheck();
  
              if (i < 0 || i >= size)
                  throw new IndexOutOfRangeException("Index out of range for sequenced collectionvalue");
  
              //We must follow the pattern of removeIterative()
              while (dirs.Length < 2 * blackdepth)
              {
                  dirs = new int[2 * dirs.Length];
                  path = new Node[2 * dirs.Length];
              }
  
              int level = 0;
              Node cursor = root;
  
              while (true)
              {
                  int j = cursor.left == null ? 0 : cursor.left.size;
  
                  if (i > j)
                  {
  
                      i -= j + cursor.items;
                      if (i < 0)
                          break;
  
                      dirs[level] = -1;
                      path[level++] = cursor;
                      cursor = cursor.right;
                  }
                  else if (i == j)
                      break;
                  else
                  {
                      dirs[level] = 1;
                      path[level++] = cursor;
                      cursor = cursor.left;
                  }
              }
  
              T retval = cursor.item;
  
  
              if (cursor.items > 1)
              {
                  resplicebag(level, cursor);
                  size--;
                  return retval;
              }
  
              removeIterativePhase2(cursor, level);
              return retval;
  
          }
  
  
          private void resplicebag(int level, Node cursor)
          {
              Node.CopyNode(ref cursor, maxsnapid, generation);
              cursor.items--;
              cursor.size--;
              while (level-- > 0)
              {
                  Node kid = cursor;
  
                  cursor = path[level];
                  Node.update(ref cursor, dirs[level] > 0, kid, maxsnapid, generation);
                  cursor.size--;
                  path[level] = null;
              }
          }
  
          /// <summary>
          /// Remove all items in an index interval.
          /// <exception cref="IndexOutOfRangeException"/>???. 
          /// </summary>
          /// <param name="start">The index of the first item to remove.</param>
          /// <param name="count">The number of items to remove.</param>
          public void RemoveInterval(int start, int count)
          {
              if (!isValid)
                  throw new ViewDisposedException("Snapshot has been disposed");
              if (start < 0 || count < 0 || start + count > this.size)
                  throw new ArgumentOutOfRangeException();
  
              updatecheck();
  
  
gt:             if (count == 0)