context: /* --------------------------------------------------------------------------
   * Copyrights
   *
   * Portions created by or assigned to Cursive Systems, Inc. are
   * Copyright (c) 2002-2008 Cursive Systems, Inc.  All Rights Reserved.  Contact
   * information for Cursive Systems, Inc. is available at
   * http://www.cursive.net/.
   *
   * License
   *
   * Jabber-Net is licensed under the LGPL.
   * See LICENSE.txt for details.
   * --------------------------------------------------------------------------*/
  using System;
  
  using System.Collections;
  namespace Bedrock.Collections
  {
      /// <summary>
      /// A basic balanced tree implementation.
      /// </summary>
      public class Tree : IEnumerable, IDictionary
      {
          private Node      root       = null;
          private int       size       = 0;
          private int       modCount   = 0;
          private IComparer comparator = System.Collections.Comparer.Default;
          //private bool      readOnly   = false;
          //private bool      synch      = false;
          /// <summary>
          /// Construct an empty tree
          /// </summary>
          public Tree()
          {
              //
              // TODO: Add Constructor Logic here
              //
          }
          #region IEnumerable
          /// <summary>
          /// Iterate over the tree
          /// </summary>
          /// <returns></returns>
          IEnumerator IEnumerable.GetEnumerator()
          {
              return new TreeEnumerator(this);
          }
          #endregion
          #region ICollection
          /// <summary>
          /// The number of items in the tree.
          /// </summary>
          public int Count
          {
              get
              {
                  return size;
              }
          }
  
          /// <summary>
          /// Gets a value indicating whether access to the tree is synchronized in thread-safe mode.
          /// Currently, it only returns false.
          /// </summary>
          public bool IsSynchronized
          {
              get
              {
                  return false;
              }
          }
  
          /// <summary>
          ///  Copies the values from the tree to the specified array in the order of the keys.
          /// </summary>
          /// <param name="array">The array to copy into</param>
          /// <param name="index">The index to start at</param>
          public void CopyTo(System.Array array, int index)
          {
              int i = index;
              foreach (DictionaryEntry o in this)
              {
                  array.SetValue(o.Value, i++);
              }
          }
  
          /// <summary>
          /// Gets an object that can be used to sychronize access to the tree. For now, it returns null.
          /// </summary>
          public object SyncRoot
          {
              get
              {
                  return null;
              }
          }
  
          #endregion
          #region IDictionary
          /// <summary>
          /// Add an item to the tree
          /// </summary>
          /// <param name="key">The key for the item</param>
          /// <param name="value">The data to store with this key</param>
          /// <exception cref="ArgumentException">Thrown if the same key is added twice</exception>
          /// <exception cref="ArgumentNullException">Thrown if key is null</exception>
          public void Add(object key,object value)
          {
              if (key == null)
                  throw new ArgumentNullException("key");
  
              Node n = root;
  
              if (n == null)
              {
                  sizeUp();
                  root = new Node(key, value, null);
                  return;
              }
  
              while (true)
              {
                  int cmp = comparator.Compare(key, n.key);
                  if (cmp == 0)
                  {
                      //n.value = value;
                      //return;
                      throw new ArgumentException("Can't add the same key twice", "key");
                  }
                  else if (cmp < 0)
                  {
                      if (n.left != null)
                      {
                          n = n.left;
                      }
                      else
                      {
                          sizeUp();
                          n.left = new Node(key, value, n);
                          fixAfterInsertion(n.left);
                          return;
                      }
                  }
                  else // cmp > 0
                  {
                      if (n.right != null) {
                          n = n.right;
                      }
                      else
                      {
                          sizeUp();
                          n.right = new Node(key, value, n);
                          fixAfterInsertion(n.right);
                          return;
                      }
                  }
              }
  
          }
  
          /// <summary>
          /// Remove all values from the tree.
          /// </summary>
          public void Clear()
          {
              modCount++;
              size = 0;
              root = null;
          }
  
          /// <summary>
          /// Determines if the specified key exists in the tree.
          /// </summary>
          /// <param name="key">The key to search for</param>
          /// <returns>True if the key exists in the tree; otherwise false.</returns>
          public bool Contains(object key)
          {
              return getNode(key) != null;
          }
  
          /// <summary>
          /// Returns a dictionary enumerator.
          /// </summary>
          /// <returns>A dictionary enumerator</returns>
          public IDictionaryEnumerator GetEnumerator()
          {
              return new TreeEnumerator(this);
          }
  
          /// <summary>
          /// Remove the element from the tree associated
          /// with this key, possibly rebalancing.
          /// </summary>
          /// <param name="key"></param>
          public void Remove(object key)
          {
              Node n = getNode(key);
              if (n == null)
              {
                  return;
              }
              sizeDown();
  
              // If strictly internal, first swap position with successor.
              if ((n.left != null) && (n.right != null))
              {
                  Node s = successor(n);
                  swapPosition(s, n);
              }
  
              // Start fixup at replacement node, if it exists.
              Node replacement = ((n.left != null) ? n.left : n.right);
  
              if (replacement != null)
              {
                  // Link replacement to parent
                  replacement.parent = n.parent;
                  if (n.parent == null)
                      root = replacement;
                  else if (n == n.parent.left)
                      n.parent.left = replacement;
                  else
                      n.parent.right = replacement;
  
                  // Null out links so they are OK to use by fixAfterDeletion.
                  n.left = n.right = n.parent = null;
  
                  // Fix replacement
                  if (n.color == NodeColor.BLACK)
                  fixAfterDeletion(replacement);
              }
              else if (n.parent == null)
              {
                  root = null;
              }
              else
              {
                  if (n.color == NodeColor.BLACK)
                      fixAfterDeletion(n);
  
                  if (n.parent != null)
                  {
                      if (n == n.parent.left)
                          n.parent.left = null;
                      else if (n == n.parent.right)
                          n.parent.right = null;
                      n.parent = null;
                  }
              }
          }
  
          /// <summary>
          /// Retrieves the value associated with the given key.
          /// </summary>
          public object this[object key]
          {
              get
              {
                  Node n = getNode(key);
                  if (n == null)
                      return null;
                  return n.value;
              }
              set
              {
                  Add(key, value);
              }
          }
  
          /// <summary>
          /// Retrieve a list of keys.
          /// </summary>
          public ICollection Keys
          {
              get
              {
                  object[] keys = new object[Count];
                  int i=0;
                  if (root == null)
                      return keys;
                  Node n = first(root);
                  while (n != null)
                  {
                      keys[i++] = n.key;
                      n = successor(n);
                  }
                  return keys;
              }
          }
  
          /// <summary>
          /// Retrieves a list of values.
          /// </summary>
          public ICollection Values
          {
              get
              {
                  object[] vals = new object[Count];
                  int i=0;
                  Node n = first(root);
                  while (n != null)
                  {
                      vals[i++] = n.value;
                      n = successor(n);
                  }
                  return vals;
              }
          }
  
          /// <summary>
          /// Always returns false for now.
          /// </summary>
          public bool IsFixedSize
          {
              get
              {
                  return false;
              }
          }
  
          /// <summary>
          /// Always returns false for now.
          /// </summary>
          public bool IsReadOnly
          {
              get
              {
                  return false;
              }
          }
          #endregion
          #region Object
          /// <summary>
          /// Retrieves a string representation of the tree.
          /// </summary>
          /// <returns>string in the format '{key1}={value1}, {key2}={value2}, ...'</returns>
          public override string ToString()
          {
  
gt:             System.Text.StringBuilder sb = new System.Text.StringBuilder();