//-----------------------------------------------------------------------------
// <copyright>
//   Copyright (c) 2010 Nesterovsky Bros. All rights reserved.
// </copyright>
// <description>
//   An immutable AVL tree imlementation.
// </description>
//-----------------------------------------------------------------------------

namespace NesterovskyBros.Collections.AVL
{
  using System;
  using System.Collections.Generic;
  using System.Runtime.Serialization;
  using System.Security.Permissions;

  /// <summary>
  /// An AVL tree (self-balancing binary search tree).
  /// Lookup, insertion, and deletion all take O(log n) time in both 
  /// the average and worst cases. Additions and deletions may require 
  /// the tree to be rebalanced by one or more tree rotations.
  /// 
  /// The AVL tree is named after its two inventors, G.M. Adelson-Velsky and
  /// E.M. Landis, who published it in their 1962 paper 
  /// "An algorithm for the organization of information."
  /// 
  /// Note that tree nodes are immutable and thread safe.
  /// Position in a tree is defined by a tree navigator, which is mutable and
  /// not safe for threading.
  /// </summary>
  /// <typeparam name="V">A node value type.</typeparam>
  [Serializable]
  public class TreeNavigator<V>: 
    ICloneable, 
    ICollection<V>, 
    IList<V>, 
    ISerializable
  {
    /// <summary>
    /// An immutable AVL tree node.
    /// </summary>
    /// <typeparam name="V">A node value type.</typeparam>
    public class Node
    {
      /// <summary>
      /// Creates a node instance.
      /// </summary>
      /// <param name="value">A node value.</param>
      public Node(V value)
      {
        Size = 1;
        Left = null;
        Right = null;
        Value = value;
      }

      /// <summary>
      /// Creates a node instance.
      /// </summary>
      /// <param name="left">A left child.</param>
      /// <param name="right">A right child.</param>
      /// <param name="value">A node value.</param>
      public Node(Node left, Node right, V value)
      {
        Size = (left != null ? left.Size : 0) + 
          (right != null ? right.Size : 0) + 1;
        Left = left;
        Right = right;
        Value = value;
      }

      /// <summary>
      /// Creates a node instance.
      /// </summary>
      /// <param name="left">A left child.</param>
      /// <param name="right">A right child.</param>
      /// <param name="that">A base node.</param>
      public Node(Node left, Node right, Node that)
      {
        Size = (left != null ? left.Size : 0) +
          (right != null ? right.Size : 0) + 1;
        Left = left;
        Right = right;
        Value = that.Value;
      }

      /// <summary>
      /// A left child node.
      /// </summary>
      public readonly Node Left;

      /// <summary>
      /// A right child node.
      /// </summary>
      public readonly Node Right;

      /// <summary>
      /// A size of subtree, including this node.
      /// </summary>
      public readonly int Size;

      /// <summary>
      /// A node value.
      /// </summary>
      public readonly V Value;
    }

    /// <summary>
    /// Creates a tree navigator instance.
    /// </summary>
    public TreeNavigator()
    {
    }

    /// <summary>
    /// Creates a copy of a tree navigator instance.
    /// </summary>
    /// <param name="that">An instance to copy.</param>
    public TreeNavigator(TreeNavigator<V> that)
    {
      if ((that != null) && !(that.depth == 0))
      {
        int depth = that.depth;

        var path = ReserveDepth(depth);
        var thatPath = that.path;

        this.depth = depth;

        for(int i = 0; i < path.Length; ++i)
        {
          if (i >= depth)
          {
            break;
          }
          
          path[i] = thatPath[i];
        }

        current = that.current;
      }
    }

    /// <summary>
    /// Creates a tree navigator instance.
    /// </summary>
    /// <param name="node">A node.</param>
    public TreeNavigator(Node node)
    {
      if (node != null)
      {
        current = node;
        
        var path = ReserveDepth(1);

        depth = 1;
        path[0] = node;
      }
    }

    /// <summary>
    /// Creates a clone of this map.
    /// </summary>
    /// <param name="info">A serialization info.</param>
    /// <param name="context">A streaming context.</param>
    protected TreeNavigator(SerializationInfo info, StreamingContext context):
      this(Create((V[])info.GetValue("Items", typeof(V[]))))
    {
    }

    #region ICloneable Members

    /// <summary>
    /// Creates a clone of this tree navigator.
    /// </summary>
    /// <returns>A clone of this tree navigator.</returns>
    public TreeNavigator<V> Clone()
    {
      return new TreeNavigator<V>(this);
    }

    /// <summary>
    /// Creates a clone of this tree navigator.
    /// </summary>
    /// <returns>A clone of this tree navigator.</returns>
    object ICloneable.Clone()
    {
      return Clone();
    }

    #endregion

    #region ISerializable Members

    /// <summary>
    /// Populates a SerializationInfo with the data needed to serialize 
    /// the target object.
    /// </summary>
    /// <param name="info">A SerializationInfo to populate with data.</param>
    /// <param name="context">A destination for this serialization.</param>
    [SecurityPermission(SecurityAction.Demand, SerializationFormatter = true)]
    void ISerializable.GetObjectData(
      SerializationInfo info,
      StreamingContext context)
    {
      V[] items = null;

      if (Count > 0)
      {
        items = new V[Count];
        CopyTo(items, 0);
      }

      info.AddValue("Items", items);
    }

    #endregion

    /// <summary>
    /// Gets node depth.
    /// </summary>
    public int Depth
    {
      get { return depth; }
    }

    /// <summary>
    /// Get a root node.
    /// </summary>
    public Node Root
    {
      get { return depth <= 1 ? current : path[0]; }
    }

    /// <summary>
    /// Gets a current node.
    /// </summary>
    public Node Current
    {
      get { return current; }
    }

    /// <summary>
    /// Gets index of the current node in the tree.
    /// </summary>
    public int Index
    {
      get 
      {
        int index;

        if (depth == 0)
        {
          index = -1;
        }
        else
        {
          var path = this.path;
          Node parent = path[0];
          Node left;

          index = 0;

          for(int i = 1; i < depth; ++i)
          {
            Node node = path[i];

            if (parent.Right == node)
            {
              ++index;

              left = parent.Left;

              if (left != null)
              {
                index += left.Size;
              }
            }

            parent = node;
          }

          left = parent.Left;

          if (left != null)
          {
            index += left.Size;
          }
        }

        return index;
      }
    }

    /// <summary>
    /// Indicates whether the current node is null.
    /// </summary>
    public bool IsNull
    {
      get { return depth == 0; }
    }

    /// <summary>
    /// Indicates whether the current node is root of the tree.
    /// </summary>
    public bool IsRoot
    {
      get { return depth == 1; }
    }


    /// <summary>
    /// Indicates whether there is a parent node for the current node.
    /// </summary>
    public bool HasParent
    {
      get { return depth > 1; }
    }

    /// <summary>
    /// Indicates whether there is a left child over the current node.
    /// </summary>
    public bool HasLeft
    {
      get { return (current != null) && (current.Left != null); }
    }

    /// <summary>
    /// Indicates whether there is a right child over the current node.
    /// </summary>
    public bool HasRight
    {
      get { return (current != null) && (current.Right != null); }
    }

    /// <summary>
    /// Indicates whether there is a predecessor node for a current node.
    /// </summary>
    public bool HasPredecessor
    {
      get
      {
        bool succeeds = false;
        
        if (depth != 0)
        {
          var path = this.path;
          Node child = null;

          for(int i = depth; i-- > 0; )
          {
            Node node = path[i];
            Node left = node.Left;

            if ((left != null) && (left != child))
            {
              succeeds = true;

              break;
            }

            child = node;
          }
        }

        return succeeds;
      }
    }

    /// <summary>
    /// Indicates whether there is a successor node for a current node.
    /// </summary>
    public bool HasSuccessor
    {
      get
      {
        bool succeeds = false;
        
        if (depth != 0)
        {
          var path = this.path;
          Node child = null;

          for(int i = depth; i-- > 0; )
          {
            Node node = path[i];
            Node right = node.Right;

            if ((right != null) && (right != child))
            {
              succeeds = true;

              break;
            }

            child = node;
          }
        }

        return succeeds;
      }
    }

    #region ICollection Members

    /// <summary>
    /// Gets a value indicating whether the collection is readonly.
    /// </summary>
    public bool IsReadOnly 
    { 
      get { return false; } 
    }

    /// <summary>
    /// Adds an item to the collection after the current position.
    /// </summary>
    /// <param name="value">A value to add</param>
    public void Add(V value)
    {
      Insert(value, false);
    }

    /// <summary>
    /// Removes all items from the collection.
    /// </summary>
    public void Clear()
    {
      MoveToNull();
    }

    /// <summary>
    /// Determines whether the collection contains a specific value.
    /// </summary>
    /// <param name="value">A value to locate.</param>
    /// <returns>
    /// true if value is found, and false otherwise.
    /// If value is found then navigator is positioned to a node with that value.
    /// </returns>
    public bool Contains(V value)
    {
      bool succeeds = false;

      if (!IsNull)
      {
        var comparer = EqualityComparer<V>.Default;

        MoveToRoot();
        MoveToLeftmost();

        do
        {
          if (comparer.Equals(Current.Value, value))
          {
            succeeds = true;

            break;
          }
        }
        while(MoveToSuccessor());
      }

      return succeeds;
    }

    /// <summary>
    /// Copies the elements of the collection to an array, starting at a 
    /// particular array index.
    /// </summary>
    /// <param name="array">
    /// An array that is the destination of the elements copied 
    /// from the collection.
    /// </param>
    /// <param name="index">
    /// An index in array at which copying begins.
    /// </param>
    public void CopyTo(V[] array, int index)
    {
      if (array == null)
      {
        throw new ArgumentException("array");
      }

      if (index < 0)
      {
        throw new ArgumentException("index");
      }

      if ((array.Length - index) < Count)
      {
        throw new ArgumentException("array");
      }

      if (!IsNull)
      {
        var navigator = Root.Navigator();
        
        navigator.MoveToLeftmost();

        do
        {
          array[index++] = navigator.Current.Value;
        }
        while(navigator.MoveToSuccessor());
      }
    }

    /// <summary>
    /// Removes the first occurrence of a specific value from the collection.
    /// </summary>
    /// <param name="value">A value to remove.</param>
    /// <returns>
    /// true if item was successfully removed from the collection, and false otherwise.
    /// This method also returns false if value is not found in the original collection.
    /// </returns>
    public bool Remove(V value)
    {
      bool succeed = false;

      if (Contains(value))
      {
        Remove();
        succeed = true;
      }

      return succeed;
    }

    /// <summary>
    /// Gets node enumerator.
    /// </summary>
    /// <returns>A node enumerator.</returns>
    public IEnumerator<V> GetEnumerator()
    {
      if (!IsNull)
      {
        var navigator = Root.Navigator();

        navigator.MoveToLeftmost();

        do
        {
          yield return navigator.Current.Value;
        }
        while(navigator.MoveToSuccessor());
      }
    }

    /// <summary>
    /// Gets a node enumerator.
    /// </summary>
    /// <returns>A node enumerator.</returns>
    System.Collections.IEnumerator
      System.Collections.IEnumerable.GetEnumerator()
    {
      return GetEnumerator();
    }

    #endregion

    #region IList<V> Members

    /// <summary>
    /// Gets count of nodes in the tree.
    /// </summary>
    public int Count
    {
      get { return depth == 0 ? 0 : path[0].Size; }
    }

    /// <summary>
    /// Gets or sets the element at the specified index.
    /// </summary>
    /// <param name="index">
    /// A zero-based index of the element to get or set.
    /// </param>
    /// <returns>An element at the specified index.</returns>
    public V this[int index]
    {
      get
      {
        if (!MoveToIndex(index))
        {
          throw new ArgumentOutOfRangeException("index");
        }

        return Current.Value;
      }
      set
      {
        if (!MoveToIndex(index))
        {
          throw new ArgumentOutOfRangeException("index");
        }

        Replace(value);
      }
    }

    /// <summary>
    /// Determines the index of a specific item in the list.
    /// </summary>
    /// <param name="item">An item to locate.</param>
    /// <returns>
    /// An index of item if found in the list, or -1 otherwise.
    /// </returns>
    public int IndexOf(V value)
    {
      return !Contains(value) ? -1 : Index;
    }

    /// <summary>
    /// Inserts an item to the list at the specified index.
    /// Note that index is not accounted but key only.
    /// </summary>
    /// <param name="index">
    /// A zero-based index at which item should be inserted.
    /// </param>
    /// <param name="item">An item to insert.</param>
    public void Insert(int index, V item)
    {
      if (index == Count)
      {
        if (index > 0)
        {
          MoveToIndex(index - 1);
        }

        Insert(item, false);
      }
      else
      {
        if (!MoveToIndex(index - 1))
        {
          throw new ArgumentOutOfRangeException("index");
        }

        Insert(item, true);
      }
    }

    /// <summary>
    /// Removes a list item at the specified index.
    /// </summary>
    /// <param name="index">
    /// An index of item to remove.
    /// </param>
    public void RemoveAt(int index)
    {
      if (!MoveToIndex(index))
      {
        throw new IndexOutOfRangeException("index");
      }

      Remove();
    }

    #endregion

    /// <summary>
    /// Gets a node in the path.
    /// </summary>
    /// <param name="index">A node depth.</param>
    /// <returns>A node in the node path.</returns>
    public Node GetPath(int index)
    {
      return (index >= 0) && (index <= depth) ? path[index] : null;
    }

    /// <summary>
    /// Moves to the null node.
    /// </summary>
    /// <returns>always returns true.</returns>
    public bool MoveToNull()
    {
      var path = this.path;

      for(int i = 0; i < path.Length; ++i)
      {
        if (i >= depth)
        {
          break;
        }

        path[i] = null;
      }

      depth = 0;
      current = null;

      return false;
    }

    /// <summary>
    /// Moves to a tree root, if any.
    /// </summary>
    /// <returns>
    /// true if after navigation succeeds, and false otherwise.
    /// If navigation succeeds then Current is changed to a new node, otherwise
    /// Current is not changed.
    /// </returns>
    public bool MoveToRoot()
    {
      bool succeeds = false;
      int depth = this.depth;

      if (depth == 1)
      {
        succeeds = true;
      }
      else if (depth > 1)
      {
        var path = this.path;

        for(int i = 1; i < path.Length; ++i)
        {
          if (i >= depth)
          {
            break;
          }

          path[i] = null;
        }

        current = path[0];
        this.depth = 1;
        succeeds = true;
      }

      return succeeds;
    }

    /// <summary>
    /// Moves to a parent node, if any.
    /// </summary>
    /// <returns>
    /// true if after navigation succeeds, and false otherwise.
    /// If navigation succeeds then Current is changed to a new node, otherwise
    /// Current is not changed.
    /// </returns>
    public bool MoveToParent()
    {
      bool succeeds = false;

      if (depth > 1)
      {
        var path = this.path;

        path[--depth] = null;
        current = path[depth - 1];
        succeeds = true;
      }

      return succeeds;
    }

    /// <summary>
    /// Moves to a left child node, if any.
    /// </summary>
    /// <returns>
    /// true if after navigation succeeds, and false otherwise.
    /// If navigation succeeds then Current is changed to a new node, otherwise
    /// Current is not changed.
    /// </returns>
    public bool MoveToLeft()
    {
      bool succeeds = false;
      Node node = current;

      if (node != null)
      {
        node = node.Left;

        if (node != null)
        {
          var path = this.path;

          if (path.Length <= depth)
          {
            path = ReserveDepth(depth + 1);
          }

          path[depth++] = node;
          current = node;
          succeeds = true;
        }
      }

      return succeeds;
    }

    /// <summary>
    /// Moves to a right child node, if any.
    /// </summary>
    /// <returns>
    /// true if after navigation succeeds, and false otherwise.
    /// If navigation succeeds then Current is changed to a new node, otherwise
    /// Current is not changed.
    /// </returns>
    public bool MoveToRight()
    {
      bool succeeds = false;
      Node node = current;

      if (node != null)
      {
        node = node.Right;

        if (node != null)
        {
          var path = this.path;

          if (path.Length <= depth)
          {
            path = ReserveDepth(depth + 1);
          }

          path[depth++] = node;
          current = node;
          succeeds = true;
        }
      }

      return succeeds;
    }

    /// <summary>
    /// Moves to the leftmost node of the subtree rooted by the current node, 
    /// if any.
    /// </summary>
    /// <returns>
    /// true if after navigation succeeds, and false otherwise.
    /// If navigation succeeds then Current is changed to a new node, otherwise
    /// Current is not changed.
    /// </returns>
    public bool MoveToLeftmost()
    {
      bool succeeds = false;
      Node node = current;

      if (node != null)
      {
        Node left = node.Left;

        if (left != null)
        {
          var path = this.path;

          do
          {
            node = left;
            left = node.Left;

            if (path.Length <= depth)
            {
              path = ReserveDepth(depth + 1);
            }

            path[depth++] = node;
          }
          while(left != null);

          current = node;
        }

        succeeds = true;
      }

      return succeeds;
    }

    /// <summary>
    /// Moves to the rightmost node of the subtree rooted by the current node,
    /// if any.
    /// </summary>
    /// <returns>
    /// true if after navigation succeeds, and false otherwise.
    /// If navigation succeeds then Current is changed to a new node, otherwise
    /// Current is not changed.
    /// </returns>
    public bool MoveToRightmost()
    {
      bool succeeds = false;
      Node node = current;

      if (node != null)
      {
        Node right = node.Right;

        if (right != null)
        {
          var path = this.path;

          do
          {
            node = right;
            right = node.Right;

            if (path.Length <= depth)
            {
              path = ReserveDepth(depth + 1);
            }

            path[depth++] = node;
          }
          while(right != null);

          current = node;
        }

        succeeds = true;
      }

      return succeeds;
    }

    /// <summary>
    /// Moves to the predecessor node, if any.
    /// </summary>
    /// <returns>
    /// true if after navigation succeeds, and false otherwise.
    /// If navigation succeeds then Current is changed to a new node, otherwise
    /// Current is not changed.
    /// </returns>
    public bool MoveToPredecessor()
    {
      bool succeeds = false;
      Node node = current;

      if (node != null)
      {
        Node next = node.Left;
        var path = this.path;

        if (next != null)
        {
          if (path.Length <= depth)
          {
            path = ReserveDepth(depth + 1);
          }

          path[depth++] = next;
          node = next;
          next = node.Right;

          while(next != null)
          {
            if (path.Length <= depth)
            {
              path = ReserveDepth(depth + 1);
            }

            path[depth++] = next;
            node = next;
            next = next.Right;
          }
        }
        else
        {
          int i = depth;

          do
          {
            if (--i == 0)
            {
              goto End;
            }

            next = node;
            node = path[i - 1];
          }
          while(next == node.Left);

          while(depth > i)
          {
            path[--depth] = null;
          }
        }

        current = node;
        succeeds = true;
      }

    End:
      return succeeds;
    }

    /// <summary>
    /// Moves to the successor node, if any.
    /// </summary>
    /// <returns>
    /// true if after navigation succeeds, and false otherwise.
    /// If navigation succeeds then Current is changed to a new node, otherwise
    /// Current is not changed.
    /// </returns>
    public bool MoveToSuccessor()
    {
      bool succeeds = false;
      Node node = current;

      if (node != null)
      {
        Node next = node.Right;
        var path = this.path;

        if (next != null)
        {
          if (path.Length <= depth)
          {
            path = ReserveDepth(depth + 1);
          }

          path[depth++] = next;
          node = next;
          next = node.Left;

          while(next != null)
          {
            if (path.Length <= depth)
            {
              path = ReserveDepth(depth + 1);
            }

            path[depth++] = next;
            node = next;
            next = next.Left;
          }
        }
        else
        {
          int i = depth;

          do
          {
            if (--i == 0)
            {
              goto End;
            }

            next = node;
            node = path[i - 1];
          }
          while(next == node.Right);

          while(depth > i)
          {
            path[--depth] = null;
          }
        }

        current = node;
        succeeds = true;
      }

    End:
      return succeeds;
    }

    /// <summary>
    /// Moves to a node with a specified index.
    /// </summary>
    /// <param name="index">A node index.</param>
    /// <returns>
    /// true if after navigation succeeds, and false otherwise.
    /// If navigation succeeds then Current is changed to a new node, otherwise
    /// Current is not changed.
    /// </returns>
    public bool MoveToIndex(int index)
    {
      bool succeeds = false;

      if ((index >= 0) && (index < Count))
      {
        MoveToRoot();

        var path = this.path;
        Node node = current;
        Node next = node.Left;
        int i = next != null ? next.Size : 0;

        while(index != i)
        {
          if (index > i)
          {
            node = node.Right;
            next = node.Left;
            i += next != null ? next.Size + 1 : 1;
          }
          else
          {
            node = node.Left;
            next = node.Right;
            i -= next != null ? next.Size + 1 : 1;
          }

          if (path.Length <= depth)
          {
            path = ReserveDepth(depth + 1);
          }

          path[depth++] = node;
        }

        current = node;
        succeeds = true;
      }

      return succeeds;
    }

    /// <summary>
    /// Insert a new node before or after a specified node.
    /// After insertion navigator points to the root of the tree.
    /// Use Index property and MoveToIndex() method to navigate to the 
    /// inserted property.
    /// </summary>
    /// <param name="value">A value to insert.</param>
    /// <param name="before">
    /// true to insert before, and false to insert after.
    /// </param>
    /// <remarks>
    /// If node has children then tree may be disbalanced.
    /// </remarks>
    public void Insert(V value, bool before)
    {
      var path = this.path;
      Node node;

      if (depth == 0)
      {
        if (path.Length < 1)
        {
          path = ReserveDepth(1);
        }

        node = new Node(value);
        path[0] = node;
        current = node;
        depth = 1; 

        return;
      }

      Node parent = current;

      if (before)
      {
        if (parent.Left != null)
        {
          MoveToPredecessor();
          parent = current;
          before = false;
        }
      }
      else
      {
        if (parent.Right != null)
        {
          MoveToSuccessor();
          parent = current;
          before = true;
        }
      }

      Node left;
      Node right;

      if (parent.Size == 1)
      {
        // This branch is pure allocation optimization.
        if (depth == 1)
        {
          node = before ?
            new Node(null, parent, value) :
            new Node(parent, null, value);

          path[0] = node;
          current = node;

          return;
        }

        path[--depth] = null;

        Node grand = path[depth - 1];

        if (grand.Size == 2)
        {
          node = new Node(null, null, grand);

          node = grand.Left == parent ?
            before ?
              new Node(new Node(value), node, parent) :
              new Node(parent, node, value) :
            before ?
              new Node(node, parent, value) :
              new Node(node, new Node(value), parent);

          if (depth == 1)
          {
            path[0] = node;
            current = node;

            return;
          }

          parent = grand;
          path[--depth] = null;
          grand = path[depth - 1];
        }
        else
        {
          node = before ?
            new Node(null, parent, value) :
            new Node(parent, null, value);
        }

        current = grand;
        left = grand.Left;

        if (left == parent)
        {
          left = node;
          right = grand.Right;
        }
        else
        {
          right = node;
        }
      }
      else
      {
        node = new Node(value);

        if (before)
        {
          left = node;
          right = parent.Right;
        }
        else
        {
          left = parent.Left;
          right = node;
        }
      }

      Balance(left, right);
    }

    /// <summary>
    /// Replaces the current value.
    /// </summary>
    /// <param name="value">A new value.</param>
    /// <returns>
    /// true if after navigation succeeds, and false otherwise.
    /// If navigation succeeds then Current is changed to a new node, otherwise
    /// Current is not changed.
    /// </returns>
    public bool Replace(V value)
    {
      bool succeeds = false;
      Node node = current;

      if (node != null)
      {
        Replace(new Node(node.Left, node.Right, value));
        succeeds = true;
      }

      return succeeds;
    }

    /// <summary>
    /// Removes current node from the tree.
    /// After remove navigator points to the root of the tree.
    /// Use Index property and MoveToIndex() method to navigate to the 
    /// inserted property.
    /// </summary>
    /// <returns>
    /// true if after operation, Current is not null, and false otherwise.
    /// </returns>
    public bool Remove()
    {
      bool succeeds = false;
      Node node = current;

      if (node != null)
      {
        Node left = node.Left;
        Node right = node.Right;

        if ((left != null) && (right != null))
        {
          RemoveAndBalance();
          succeeds = true;
        }
        else if (depth == 1)
        {
          // Delete root node.
          if (left == null)
          {
            if (right == null)
            {
              // Remove last node.
              MoveToNull();
            }
            else
            {
              path[0] = right;
              current = right;
              succeeds = true;
            }
          }
          else
          {
            path[0] = left;
            current = left;
            succeeds = true;
          }
        }
        else
        {
          Node parent = path[depth - 2];

          if (left == null)
          {
            if (right == null)
            {
              // Remove leaf node.
              left = parent.Left;

              if (left == node)
              {
                left = null;
                right = parent.Right;
              }
              else
              {
                right = null;
              }
            }
            else
            {
              // There is only a right child.
              left = parent.Left;

              if (left == node)
              {
                left = right;
                right = parent.Right;
              }
            }
          }
          else
          {
            // There is only a left child.
            right = parent.Right;

            if (right == node)
            {
              right = left;
              left = parent.Left;
            }
          }

          Balance(left, right);
          succeeds = true;
        }
      }

      return succeeds;
    }

    /// <summary>
    /// Creates a well balanced tree from a collection of values.
    /// </summary>
    /// <param name="values">Values collection.</param>
    /// <returns>Well balanced tree, or null if values is null.</returns>
    public static Node Create(ICollection<V> values)
    {
      Node result = null;

      if (values != null)
      {
        using (IEnumerator<V> enumerator = values.GetEnumerator())
        {
          result = Create(enumerator, values.Count);
        }
      }

      return result;
    }

    /// <summary>
    /// Creates a well balanced tree from a collection of values.
    /// </summary>
    /// <param name="values">Values collection.</param>
    /// <returns>Well balanced tree, or null if values is null.</returns>
    public static Node Create(IEnumerator<V> values, int count)
    {
      Node result = null;

      if ((values != null) && (count > 0))
      {
        int leftCount = count / 2;
        int rightCount = count - leftCount - 1;

        Node left = leftCount > 0 ? Create(values, leftCount) : null;

        values.MoveNext();

        V value = values.Current;

        Node right = rightCount > 0 ? Create(values, rightCount) : null;

        result = new Node(left, right, value);
      }

      return result;
    }


    /// <summary>
    /// Gets subtree height for the balanced subtree size.
    /// </summary>
    /// <param name="size">Subtree size</param>
    /// <returns>Subtree height</returns>
    public static int Height(int size)
    {
      int result = 0;

      if (size != 0)
      {
        if ((size & 0xffff0000) == 0)
        {
          result -= 16;
          size <<= 16;
        }

        if ((size & 0xff000000) == 0)
        {
          result -= 8;
          size <<= 8;
        }

        if ((size & 0xf0000000) == 0)
        {
          result -= 4;
          size <<= 4;
        }

        if ((size & 0xc0000000) == 0)
        {
          result -= 2;
          size <<= 2;
        }

        result += (int)((uint)size >> 31) + 31;
      }

      return result;
    }


    /// <summary>
    /// Reserves path for the depth.
    /// </summary>
    /// <param name="length">A required length.</param>
    /// <returns>
    /// A new path.
    /// </returns>
    private Node[] ReserveDepth(int length)
    {
      if (length < 8)
      {
        length = 8;
      }
      else if (length < 16)
      {
        length = 16;
      }
      else if (length < 24)
      {
        length = 24;
      }
      else if (length < 32)
      {
        length = 32;
      }
      // No more cases.

      var newPath = new Node[length];
      var path = this.path;

      for(int i = 0; i < path.Length; ++i)
      {
        if (i >= depth)
        {
          break;
        }

        newPath[i] = path[i];
      }

      this.path = newPath;

      return newPath;
    }

    /// <summary>
    /// Replaces the current node.
    /// </summary>
    /// <param name="newNode">A new node.</param>
    private void Replace(Node newNode)
    {
      Node node = current;
      var path = this.path;

      path[depth - 1] = newNode;
      current = newNode;

      for(int i = depth - 1; i-- > 0;)
      {
        Node parent = path[i];
        Node left = parent.Left;
        Node right;

        if (left == node)
        {
          left = newNode;
          right = parent.Right;
        }
        else
        {
          right = newNode;
        }

        node = parent;
        newNode = new Node(left, right, parent);
        path[i] = newNode;
      }
    }

    /// <summary>
    /// Removes node with two children and balances the tree.
    /// </summary>
    private void RemoveAndBalance()
    {
      int i = depth - 1;
      Node node = current;
      Node parent;
      Node newParent;
      Node left;
      Node right;
      Node newNode;

      if (node.Left.Size >= node.Right.Size)
      {
        MoveToPredecessor();
        MoveToParent();

        parent = current;

        if (i == depth - 1)
        {
          newParent = parent.Left;
          left = parent.Left.Left;
          right = parent.Right;
        }
        else
        {
          node = parent;
          newParent = parent.Right;
          left = parent.Left;
          right = parent.Right.Left;
        }
      }
      else
      {
        MoveToSuccessor();
        MoveToParent();

        parent = current;

        if (i == depth - 1)
        {
          newParent = parent.Right;
          left = parent.Left;
          right = parent.Right.Right;
        }
        else
        {
          node = parent;
          newParent = parent.Left;
          left = parent.Left.Right;
          right = parent.Right;
        }
      }

      int j = depth - 1;
      var path = this.path;

      while(j > i)
      {
        newNode = new Node(left, right, node);
        path[j] = null;
        parent = path[--j];
        left = parent.Left;

        if (left == node)
        {
          left = newNode;
          right = parent.Right;
        }
        else
        {
          right = newNode;
        }

        node = parent;
      }

      depth = i + 1;
      newNode = new Node(left, right, newParent);
      Replace(newNode);
      Balance(newNode.Left, newNode.Right);
    }

    /// <summary>Balances the tree.</summary>
    /// <param name="left">A left child.</param>
    /// <param name="right">A right child.</param>
    private void Balance(Node left, Node right)
    {
      Node node = current;
      int i = depth;
      var path = this.path;

      while(true)
      {
        path[--i] = null;

        Node newNode;
        Node leftLeft;
        Node leftRight;
        Node rightRight;
        Node rightLeft;
        int l;
        int r;
        int ll;
        int lr;
        int rr;
        int rl;

        if (left != null)
        {
          l = left.Size;
          leftLeft = left.Left;
          leftRight = left.Right;
          ll = leftLeft != null ? leftLeft.Size : 0;
          lr = leftRight != null ? leftRight.Size : 0;
        }
        else
        {
          leftLeft = null;
          leftRight = null;
          l = 0;
          ll = 0;
          lr = 0;
        }

        if (right != null)
        {
          rightRight = right.Right;
          rightLeft = right.Left;
          r = right.Size;
          rr = rightRight != null ? rightRight.Size : 0;
          rl = rightLeft != null ? rightLeft.Size : 0;
        }
        else
        {
          rightRight = null;
          rightLeft = null;
          r = 0;
          rr = 0;
          rl = 0;
        }

        if ((ll > r) && (ll > lr))
        {
          // LL
          newNode = new Node(
            leftLeft,
            new Node(leftRight, right, node),
            left);
        }
        else if ((lr > r) ||
          ((ll == r) && (leftRight != null) && (leftRight.Left != null)))
        {
          // LR
          newNode = new Node(
            new Node(leftLeft, leftRight.Left, left),
            new Node(leftRight.Right, right, node),
            leftRight);
        }
        else if ((rr > l) && (rr > rl))
        {
          // RR
          newNode = new Node(
            new Node(left, rightLeft, node),
            rightRight,
            right);
        }
        else if ((rl > l) ||
          ((rr == l) && (rightLeft != null) && (rightLeft.Right != null)))
        {
          // RL
          newNode = new Node(
            new Node(left, rightLeft.Left, node),
            new Node(rightLeft.Right, rightRight, right),
            rightLeft);
        }
        else
        {
          newNode = (node.Left == left) && (node.Right == right) ?
            node : new Node(left, right, node);
        }

        if (i == 0)
        {
          current = newNode;
          path[0] = newNode;
          depth = 1;
          
          break;
        }

        Node next = path[i - 1];

        left = next.Left;

        if (left == node)
        {
          left = newNode;
          right = next.Right;
        }
        else
        {
          right = newNode;
        }

        node = next;
      }
    }

    /// <summary>
    /// A current node.
    /// </summary>
    private Node current;

    /// <summary>
    /// A node path.
    /// </summary>
    private Node[] path = empty;

    /// <summary>
    /// A depth of path.
    /// </summary>
    private int depth;

    /// <summary>
    /// Empty path.
    /// </summary>
    private static readonly Node[] empty = {};
  }

  /// <summary>
  /// An API to work with tree.
  /// </summary>
  public static class API
  {
    /// <summary>
    /// Gets a tree navigator for a node.
    /// </summary>
    /// <param name="node">A node to get a tree navigator for.</param>
    /// <returns>A tree navigator.</returns>
    public static TreeNavigator<V> Navigator<V>(
      this TreeNavigator<V>.Node node)
    {
      return new TreeNavigator<V>(node);
    }

    /// <summary>
    /// Navigates to a node within a tree, which is equal or closest to
    /// a specified key.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key of a find.</param>
    /// <returns>
    /// 0 when current node is equal to, 
    /// -1 when found node is less than, and
    /// 1 when found node is greater than the searched one.
    /// 
    /// If tree is empty then 1 is returned.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <remarks>
    /// Method works properly wheNode nodes in the tree are ordered 
    /// according to the key.
    /// </remarks>
    public static int Find<K>(this TreeNavigator<K> navigator, K key)
    {
      return Find(navigator, key, Comparer<K>.Default);
    }

    /// <summary>
    /// Navigates to a node within a tree, which is equal or closest to
    /// a specified key. Comparer is used to test equality.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key of a find.</param>
    /// <param name="comparer">A key comparer.</param>
    /// <returns>
    /// 0 when current node is equal to,
    /// -1 when found node is less than, and
    /// 1 when found node is greater than the searched one.
    /// 
    /// If tree is empty then 1 is returned.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <remarks>
    /// Method works properly wheNode nodes in the tree are ordered 
    /// according to the comparer.
    /// </remarks>
    public static int Find<K>(
      this TreeNavigator<K> navigator,
      K key,
      IComparer<K> comparer)
    {
      int c;

      if (!navigator.MoveToRoot())
      {
        c = -1;
      }
      else
      {
        while(true)
        {
          c = comparer.Compare(navigator.Current.Value, key);

          if ((c == 0) ||
            (c < 0 ? !navigator.MoveToRight() : !navigator.MoveToLeft()))
          {
            break;
          }
        }
      }

      return c;
    }

    /// <summary>
    /// Navigates to a node within a tree, which is equal or closest to
    /// a specified value.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key value of a find.</param>
    /// <returns>
    /// 0 when current node is equal to, 
    /// -1 when found node is less than, and
    /// 1 when found node is greater than the searched one.
    /// 
    /// If tree is empty then 1 is returned.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <typeparam name="V">A value type.</typeparam>
    /// <remarks>
    /// Method works properly wheNode nodes in the tree are ordered 
    /// according to the key.
    /// </remarks>
    public static int Find<K, V>(
      this TreeNavigator<KeyValuePair<K, V>> navigator,
      K key)
    {
      return Find(navigator, key, Comparer<K>.Default);
    }

    /// <summary>
    /// Navigates to a node within a tree, which is equal or closest to
    /// a specified value. Comparer is used to test equality.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key value of a find.</param>
    /// <param name="comparer">A key comparer.</param>
    /// <returns>
    /// 0 when current node is equal to, 
    /// -1 when found node is less than, and
    /// 1 when found node is greater than the searched one.
    /// 
    /// If tree is empty then 1 is returned.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <typeparam name="V">A value type.</typeparam>
    /// <remarks>
    /// Method works properly wheNode nodes in the tree are ordered 
    /// according to the comparer.
    /// </remarks>
    public static int Find<K, V>(
      this TreeNavigator<KeyValuePair<K, V>> navigator,
      K key,
      IComparer<K> comparer)
    {
      int c;

      if (!navigator.MoveToRoot())
      {
        c = -1;
      }
      else
      {
        while(true)
        {
          c = comparer.Compare(navigator.Current.Value.Key, key);

          if ((c == 0) ||
            (c < 0 ? !navigator.MoveToRight() : !navigator.MoveToLeft()))
          {
            break;
          }
        }
      }

      return c;
    }

    /// <summary>
    /// Navigates to a node within a tree, which is equal to a specified value. 
    /// Comparer is used to test equality.
    /// </summary>
    /// <param name="node">A node.</param>
    /// <param name="key">A key of a find.</param>
    /// <returns>Found node or null if node is not found.</returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <remarks>
    /// Method works properly wheNode nodes in the tree are ordered 
    /// according to the key.
    /// </remarks>
    public static TreeNavigator<K>.Node Find<K>(
      this TreeNavigator<K>.Node node, 
      K key)
    {
      return Find(node, key, Comparer<K>.Default);
    }

    /// <summary>
    /// Navigates to a node within a tree, which is equal to a specified value. 
    /// Comparer is used to test equality.
    /// </summary>
    /// <param name="node">A node.</param>
    /// <param name="key">A key of a find.</param>
    /// <param name="comparer">A key comparer.</param>
    /// <returns>Found node or null if node is not found.</returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <remarks>
    /// Method works properly wheNode nodes in the tree are ordered 
    /// according to the comparer.
    /// </remarks>
    public static TreeNavigator<K>.Node Find<K>(
      this TreeNavigator<K>.Node node,
      K key,
      IComparer<K> comparer)
    {
      while(node != null)
      {
        int c = comparer.Compare(node.Value, key);

        if (c == 0)
        {
          break;
        }

        node = c < 0 ? node.Right : node.Left;
      }

      return node;
    }

    /// <summary>
    /// Navigates to a node within a tree, which is equal to a specified value. 
    /// Comparer is used to test equality.
    /// </summary>
    /// <param name="node">A node.</param>
    /// <param name="key">A key value of a find.</param>
    /// <returns>Found node or null if node is not found.</returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <typeparam name="V">A value type.</typeparam>
    /// <remarks>
    /// Method works properly wheNode nodes in the tree are ordered 
    /// according to the key.
    /// </remarks>
    public static TreeNavigator<KeyValuePair<K, V>>.Node Find<K, V>(
      this TreeNavigator<KeyValuePair<K, V>>.Node node,
      K key)
    {
      return Find(node, key, Comparer<K>.Default);
    }

    /// <summary>
    /// Navigates to a node within a tree, which is equal to a specified value. 
    /// Comparer is used to test equality.
    /// </summary>
    /// <param name="node">A node.</param>
    /// <param name="key">A key value of a find.</param>
    /// <param name="comparer">A key comparer.</param>
    /// <returns>Found node or null if node is not found.</returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <typeparam name="V">A value type.</typeparam>
    /// <remarks>
    /// Method works properly wheNode nodes in the tree are ordered 
    /// according to the comparer.
    /// </remarks>
    public static TreeNavigator<KeyValuePair<K, V>>.Node Find<K, V>(
      this TreeNavigator<KeyValuePair<K, V>>.Node node,
      K key,
      IComparer<K> comparer)
    {
      while(node != null)
      {
        int c = comparer.Compare(node.Value.Key, key);

        if (c == 0)
        {
          break;
        }

        node = c < 0 ? node.Right : node.Left;
      }

      return node;
    }

    /// <summary>
    /// Inserts a node with a specified key into the tree.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key to insert.</param>
    /// <param name="comparer">A key comparer.</param>
    /// <returns>
    /// Index of inserted node, or negative index of node 
    /// if no node is not inserted due to duplicate.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    public static int Insert<K>(
      this TreeNavigator<K> navigator,
      K key,
      IComparer<K> comparer)
    {
      return Insert(navigator, key, comparer, false);
    }

    /// <summary>
    /// Inserts a node with a specified key into the tree.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key to insert.</param>
    /// <param name="comparer">A key comparer.</param>
    /// <returns>
    /// Index of inserted node, or negative index of node 
    /// if no node is not inserted due to duplicate.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    public static int Insert<K>(this TreeNavigator<K> navigator, K key)
    {
      return Insert(navigator, key, Comparer<K>.Default, false);
    }

    /// <summary>
    /// Inserts a node with a specified key into the tree.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key to insert.</param>
    /// <param name="insertDuplicate">
    /// true to insert duplicate, and false otherwise.
    /// </param>
    /// <returns>
    /// Index of inserted node, or negative index of node 
    /// if no node is not inserted due to duplicate.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    public static int Insert<K>(
      this TreeNavigator<K> navigator,
      K key,
      bool insertDuplicate)
    {
      return Insert(navigator, key, Comparer<K>.Default, insertDuplicate);
    }

    /// <summary>
    /// Inserts a node with a specified key into the tree.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key to insert.</param>
    /// <param name="comparer">A key comparer.</param>
    /// <param name="insertDuplicate">
    /// true to insert duplicate, and false otherwise.
    /// </param>
    /// <returns>
    /// Index of inserted node, or negative index of node 
    /// if no node is not inserted due to duplicate.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    public static int Insert<K>(
      this TreeNavigator<K> navigator,
      K key,
      IComparer<K> comparer,
      bool insertDuplicate)
    {
      int c = Find(navigator, key, comparer);
      int index = navigator.Index;

      if ((c == 0) && !insertDuplicate)
      {
        index = -index;
      }
      else
      {
        if (c <= 0)
        {
          ++index;
        }

        navigator.Insert(key, c > 0);
      }

      return index;
    }

    /// <summary>
    /// Inserts a node with a specified key into the tree.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="value">A value to insert.</param>
    /// <param name="comparer">A key comparer.</param>
    /// <returns>
    /// Index of inserted node, or negative index of node 
    /// if no node is not inserted due to duplicate.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <typeparam name="V">A value type.</typeparam>
    public static int Insert<K, V>(
      this TreeNavigator<KeyValuePair<K, V>> navigator,
      KeyValuePair<K, V> value,
      IComparer<K> comparer)
    {
      return Insert(navigator, value, comparer, false);
    }

    /// <summary>
    /// Inserts a node with a specified key into the tree.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="value">A value to insert.</param>
    /// <returns>
    /// Index of inserted node, or negative index of node 
    /// if no node is not inserted due to duplicate.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <typeparam name="V">A value type.</typeparam>
    public static int Insert<K, V>(
      this TreeNavigator<KeyValuePair<K, V>> navigator,
      KeyValuePair<K, V> value)
    {
      return Insert(navigator, value, Comparer<K>.Default, false);
    }

    /// <summary>
    /// Inserts a node with a specified key into the tree.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="value">A value to insert.</param>
    /// <param name="insertDuplicate">
    /// true to insert duplicate, and false otherwise.
    /// </param>
    /// <returns>
    /// Index of inserted node, or negative index of node 
    /// if no node is not inserted due to duplicate.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <typeparam name="V">A value type.</typeparam>
    public static int Insert<K, V>(
      this TreeNavigator<KeyValuePair<K, V>> navigator,
      KeyValuePair<K, V> value,
      bool insertDuplicate)
    {
      return Insert(navigator, value, Comparer<K>.Default, insertDuplicate);
    }

    /// <summary>
    /// Inserts a node with a specified key into the tree.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="value">A value to insert.</param>
    /// <param name="comparer">A key comparer.</param>
    /// <param name="insertDuplicate">
    /// true to insert duplicate, and false otherwise.
    /// </param>
    /// <returns>
    /// Index of inserted node, or negative index of node 
    /// if no node is not inserted due to duplicate.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <typeparam name="V">A value type.</typeparam>
    public static int Insert<K, V>(
      this TreeNavigator<KeyValuePair<K, V>> navigator,
      KeyValuePair<K, V> value,
      IComparer<K> comparer,
      bool insertDuplicate)
    {
      int c = Find(navigator, value.Key, comparer);
      int index = navigator.Index;

      if ((c == 0) && !insertDuplicate)
      {
        index = -index;
      }
      else
      {
        if (c <= 0)
        {
          ++index;
        }

        navigator.Insert(value, c > 0);
      }

      return index;
    }

    /// <summary>
    /// Removes a node with a specified key.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key to remove.</param>
    /// <returns>
    /// Index of removed nore, or -1 if no node is removed.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    public static int Remove<K>(this TreeNavigator<K> navigator, K key)
    {
      return Remove(navigator, key, Comparer<K>.Default);
    }

    /// <summary>
    /// Removes a node with a specified key.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key to remove.</param>
    /// <param name="comparer">A key comparer.</param>
    /// <returns>
    /// Index of removed nore, or -1 if no node is removed.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    public static int Remove<K>(
      this TreeNavigator<K> navigator,
      K key,
      IComparer<K> comparer)
    {
      int index;
      int c = Find(navigator, key, comparer);

      if (c != 0)
      {
        index = -1;
      }
      else
      {
        index = navigator.Index;
        navigator.Remove();
      }

      return index;
    }

    /// <summary>
    /// Removes a node with a specified key.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key to remove.</param>
    /// <returns>
    /// Index of removed nore, or -1 if no node is removed.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <typeparam name="V">A value type.</typeparam>
    public static int Remove<K, V>(
      this TreeNavigator<KeyValuePair<K, V>> navigator,
      K key)
    {
      return Remove(navigator, key, Comparer<K>.Default);
    }

    /// <summary>
    /// Removes a node with a specified key.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key to remove.</param>
    /// <param name="comparer">A key comparer.</param>
    /// <returns>
    /// Index of removed nore, or -1 if no node is removed.
    /// </returns>
    /// <typeparam name="K">A key type.</typeparam>
    public static int Remove<K, V>(
      this TreeNavigator<KeyValuePair<K, V>> navigator,
      K key,
      IComparer<K> comparer)
    {
      int index;
      int c = Find(navigator, key, comparer);

      if (c != 0)
      {
        index = -1;
      }
      else
      {
        index = navigator.Index;
        navigator.Remove();
      }

      return index;
    }

    /// <summary>
    /// Enumerates values for a specified key.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key to get values for.</param>
    /// <returns>An enumerator.</returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <typeparam name="V">A value type.</typeparam>
    public static IEnumerable<KeyValuePair<K, V>> GetValues<K, V>(
      this TreeNavigator<KeyValuePair<K, V>> navigator,
      K key)
    {
      return GetValues(navigator, key, Comparer<K>.Default);
    }

    /// <summary>
    /// Enumerates values for a specified key.
    /// </summary>
    /// <param name="navigator">A tree navigator.</param>
    /// <param name="key">A key to get values for.</param>
    /// <param name="comparer">A key comparer.</param>
    /// <returns>An enumerator.</returns>
    /// <typeparam name="K">A key type.</typeparam>
    /// <typeparam name="V">A value type.</typeparam>
    public static IEnumerable<KeyValuePair<K, V>> GetValues<K, V>(
      this TreeNavigator<KeyValuePair<K, V>> navigator,
      K key,
      IComparer<K> comparer)
    {
      navigator = navigator.Root.Navigator();

      int c = Find(navigator, key, comparer);

      if (c == 0)
      {
        while(navigator.MoveToPredecessor())
        {
          if (comparer.Compare(navigator.Current.Value.Key, key) != 0)
          {
            navigator.MoveToSuccessor();

            break;
          }
        }

        do
        {
          yield return navigator.Current.Value;
        }
        while(navigator.MoveToSuccessor() &&
          (comparer.Compare(navigator.Current.Value.Key, key) != 0));
      }
    }
  }
}