source: branches/PersistentDataStructures/HeuristicLab.ExtLibs/HeuristicLab.AvalonEdit/5.0.1/AvalonEdit-5.0.1/Utils/CompressingTreeList.cs

// Copyright (c) 2014 AlphaSierraPapa for the SharpDevelop Team
// 
// 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 System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace ICSharpCode.AvalonEdit.Utils
{
  /// <summary>
  /// A IList{T} implementation that has efficient insertion and removal (in O(lg n) time)
  /// and that saves memory by allocating only one node when a value is repeated in adjacent indices.
  /// Based on this "compression", it also supports efficient InsertRange/SetRange/RemoveRange operations.
  /// </summary>
  /// <remarks>
  /// Current memory usage: 5*IntPtr.Size + 12 + sizeof(T) per node.
  /// Use this class only if lots of adjacent values are identical (can share one node).
  /// </remarks>
  [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix",
                                                   Justification = "It's an IList<T> implementation")]
  public sealed class CompressingTreeList<T> : IList<T>
  {
    // Further memory optimization: this tree could work without parent pointers. But that
    // requires changing most of tree manipulating logic.
    // Also possible is to remove the count field and calculate it as totalCount-left.totalCount-right.totalCount
    // - but that would make tree manipulations more difficult to handle.
    
    #region Node definition
    sealed class Node
    {
      internal Node left, right, parent;
      internal bool color;
      internal int count, totalCount;
      internal T value;
      
      public Node(T value, int count)
      {
        this.value = value;
        this.count = count;
        this.totalCount = count;
      }
      
      internal Node LeftMost {
        get {
          Node node = this;
          while (node.left != null)
            node = node.left;
          return node;
        }
      }
      
      internal Node RightMost {
        get {
          Node node = this;
          while (node.right != null)
            node = node.right;
          return node;
        }
      }
      
      /// <summary>
      /// Gets the inorder predecessor of the node.
      /// </summary>
      internal Node Predecessor {
        get {
          if (left != null) {
            return left.RightMost;
          } else {
            Node node = this;
            Node oldNode;
            do {
              oldNode = node;
              node = node.parent;
              // go up until we are coming out of a right subtree
            } while (node != null && node.left == oldNode);
            return node;
          }
        }
      }
      
      /// <summary>
      /// Gets the inorder successor of the node.
      /// </summary>
      internal Node Successor {
        get {
          if (right != null) {
            return right.LeftMost;
          } else {
            Node node = this;
            Node oldNode;
            do {
              oldNode = node;
              node = node.parent;
              // go up until we are coming out of a left subtree
            } while (node != null && node.right == oldNode);
            return node;
          }
        }
      }
      
      public override string ToString()
      {
        return "[TotalCount=" + totalCount + " Count=" + count + " Value=" + value + "]";
      }
    }
    #endregion
    
    #region Fields and Constructor
    readonly Func<T, T, bool> comparisonFunc;
    Node root;
    
    /// <summary>
    /// Creates a new CompressingTreeList instance.
    /// </summary>
    /// <param name="equalityComparer">The equality comparer used for comparing consequtive values.
    /// A single node may be used to store the multiple values that are considered equal.</param>
    public CompressingTreeList(IEqualityComparer<T> equalityComparer)
    {
      if (equalityComparer == null)
        throw new ArgumentNullException("equalityComparer");
      this.comparisonFunc = equalityComparer.Equals;
    }
    
    /// <summary>
    /// Creates a new CompressingTreeList instance.
    /// </summary>
    /// <param name="comparisonFunc">A function that checks two values for equality. If this
    /// function returns true, a single node may be used to store the two values.</param>
    public CompressingTreeList(Func<T, T, bool> comparisonFunc)
    {
      if (comparisonFunc == null)
        throw new ArgumentNullException("comparisonFunc");
      this.comparisonFunc = comparisonFunc;
    }
    #endregion
    
    #region InsertRange
    /// <summary>
    /// Inserts <paramref name="item"/> <paramref name="count"/> times at position
    /// <paramref name="index"/>.
    /// </summary>
    public void InsertRange(int index, int count, T item)
    {
      if (index < 0 || index > this.Count)
        throw new ArgumentOutOfRangeException("index", index, "Value must be between 0 and " + this.Count);
      if (count < 0)
        throw new ArgumentOutOfRangeException("count", count, "Value must not be negative");
      if (count == 0)
        return;
      unchecked {
        if (this.Count + count < 0)
          throw new OverflowException("Cannot insert elements: total number of elements must not exceed int.MaxValue.");
      }
      
      if (root == null) {
        root = new Node(item, count);
      } else {
        Node n = GetNode(ref index);
        // check if we can put the value into the node n:
        if (comparisonFunc(n.value, item)) {
          n.count += count;
          UpdateAugmentedData(n);
        } else if (index == n.count) {
          // this can only happen when appending at the end
          Debug.Assert(n == root.RightMost);
          InsertAsRight(n, new Node(item, count));
        } else if (index == 0) {
          // insert before:
          // maybe we can put the value in the previous node?
          Node p = n.Predecessor;
          if (p != null && comparisonFunc(p.value, item)) {
            p.count += count;
            UpdateAugmentedData(p);
          } else {
            InsertBefore(n, new Node(item, count));
          }
        } else {
          Debug.Assert(index > 0 && index < n.count);
          // insert in the middle:
          // split n into a new node and n
          n.count -= index;
          InsertBefore(n, new Node(n.value, index));
          // then insert the new item in between
          InsertBefore(n, new Node(item, count));
          UpdateAugmentedData(n);
        }
      }
      CheckProperties();
    }
    
    void InsertBefore(Node node, Node newNode)
    {
      if (node.left == null) {
        InsertAsLeft(node, newNode);
      } else {
        InsertAsRight(node.left.RightMost, newNode);
      }
    }
    #endregion
    
    #region RemoveRange
    /// <summary>
    /// Removes <paramref name="count"/> items starting at position
    /// <paramref name="index"/>.
    /// </summary>
    public void RemoveRange(int index, int count)
    {
      if (index < 0 || index > this.Count)
        throw new ArgumentOutOfRangeException("index", index, "Value must be between 0 and " + this.Count);
      if (count < 0 || index + count > this.Count)
        throw new ArgumentOutOfRangeException("count", count, "0 <= length, index(" + index + ")+count <= " + this.Count);
      if (count == 0)
        return;
      
      Node n = GetNode(ref index);
      if (index + count < n.count) {
        // just remove inside a single node
        n.count -= count;
        UpdateAugmentedData(n);
      } else {
        // keep only the part of n from 0 to index
        Node firstNodeBeforeDeletedRange;
        if (index > 0) {
          count -= (n.count - index);
          n.count = index;
          UpdateAugmentedData(n);
          firstNodeBeforeDeletedRange = n;
          n = n.Successor;
        } else {
          Debug.Assert(index == 0);
          firstNodeBeforeDeletedRange = n.Predecessor;
        }
        while (n != null && count >= n.count) {
          count -= n.count;
          Node s = n.Successor;
          RemoveNode(n);
          n = s;
        }
        if (count > 0) {
          Debug.Assert(n != null && count < n.count);
          n.count -= count;
          UpdateAugmentedData(n);
        }
        if (n != null) {
          Debug.Assert(n.Predecessor == firstNodeBeforeDeletedRange);
          if (firstNodeBeforeDeletedRange != null && comparisonFunc(firstNodeBeforeDeletedRange.value, n.value)) {
            firstNodeBeforeDeletedRange.count += n.count;
            RemoveNode(n);
            UpdateAugmentedData(firstNodeBeforeDeletedRange);
          }
        }
      }
      
      CheckProperties();
    }
    #endregion
    
    #region SetRange
    /// <summary>
    /// Sets <paramref name="count"/> indices starting at <paramref name="index"/> to
    /// <paramref name="item"/>
    /// </summary>
    public void SetRange(int index, int count, T item)
    {
      RemoveRange(index, count);
      InsertRange(index, count, item);
    }
    #endregion
    
    #region GetNode
    Node GetNode(ref int index)
    {
      Node node = root;
      while (true) {
        if (node.left != null && index < node.left.totalCount) {
          node = node.left;
        } else {
          if (node.left != null) {
            index -= node.left.totalCount;
          }
          if (index < node.count || node.right == null)
            return node;
          index -= node.count;
          node = node.right;
        }
      }
    }
    #endregion
    
    #region UpdateAugmentedData
    void UpdateAugmentedData(Node node)
    {
      int totalCount = node.count;
      if (node.left != null) totalCount += node.left.totalCount;
      if (node.right != null) totalCount += node.right.totalCount;
      if (node.totalCount != totalCount) {
        node.totalCount = totalCount;
        if (node.parent != null)
          UpdateAugmentedData(node.parent);
      }
    }
    #endregion
    
    #region IList<T> implementation
    /// <summary>
    /// Gets or sets an item by index.
    /// </summary>
    public T this[int index] {
      get {
        if (index < 0 || index >= this.Count)
          throw new ArgumentOutOfRangeException("index", index, "Value must be between 0 and " + (this.Count - 1));
        return GetNode(ref index).value;
      }
      set {
        RemoveAt(index);
        Insert(index, value);
      }
    }
    
    /// <summary>
    /// Gets the number of items in the list.
    /// </summary>
    public int Count {
      get {
        if (root != null)
          return root.totalCount;
        else
          return 0;
      }
    }
    
    bool ICollection<T>.IsReadOnly {
      get {
        return false;
      }
    }
    
    /// <summary>
    /// Gets the index of the specified <paramref name="item"/>.
    /// </summary>
    public int IndexOf(T item)
    {
      int index = 0;
      if (root != null) {
        Node n = root.LeftMost;
        while (n != null) {
          if (comparisonFunc(n.value, item))
            return index;
          index += n.count;
          n = n.Successor;
        }
      }
      Debug.Assert(index == this.Count);
      return -1;
    }
    
    /// <summary>
    /// Gets the the first index so that all values from the result index to <paramref name="index"/>
    /// are equal.
    /// </summary>
    public int GetStartOfRun(int index)
    {
      if (index < 0 || index >= this.Count)
        throw new ArgumentOutOfRangeException("index", index, "Value must be between 0 and " + (this.Count - 1));
      int indexInRun = index;
      GetNode(ref indexInRun);
      return index - indexInRun;
    }

    /// <summary>
    /// Gets the first index after <paramref name="index"/> so that the value at the result index is not
    /// equal to the value at <paramref name="index"/>.
    /// That is, this method returns the exclusive end index of the run of equal values.
    /// </summary>
    public int GetEndOfRun(int index)
    {
      if (index < 0 || index >= this.Count)
        throw new ArgumentOutOfRangeException("index", index, "Value must be between 0 and " + (this.Count - 1));
      int indexInRun = index;
      int runLength = GetNode(ref indexInRun).count;
      return index - indexInRun + runLength;
    }

    /// <summary>
    /// Gets the number of elements after <paramref name="index"/> that have the same value as each other.
    /// </summary>
    [Obsolete("This method may be confusing as it returns only the remaining run length after index. " +
              "Use GetStartOfRun/GetEndOfRun instead.")]
    public int GetRunLength(int index)
    {
      if (index < 0 || index >= this.Count)
        throw new ArgumentOutOfRangeException("index", index, "Value must be between 0 and " + (this.Count - 1));
      return GetNode(ref index).count - index;
    }
    
    /// <summary>
    /// Applies the conversion function to all elements in this CompressingTreeList.
    /// </summary>
    public void Transform(Func<T, T> converter)
    {
      if (root == null)
        return;
      Node prevNode = null;
      for (Node n = root.LeftMost; n != null; n = n.Successor) {
        n.value = converter(n.value);
        if (prevNode != null && comparisonFunc(prevNode.value, n.value)) {
          n.count += prevNode.count;
          UpdateAugmentedData(n);
          RemoveNode(prevNode);
        }
        prevNode = n;
      }
      CheckProperties();
    }
    
    /// <summary>
    /// Applies the conversion function to the elements in the specified range.
    /// </summary>
    public void TransformRange(int index, int length, Func<T, T> converter)
    {
      if (root == null)
        return;
      int endIndex = index + length;
      int pos = index;
      while (pos < endIndex) {
        int endPos = Math.Min(endIndex, GetEndOfRun(pos));
        T oldValue = this[pos];
        T newValue = converter(oldValue);
        SetRange(pos, endPos - pos, newValue);
        pos = endPos;
      }
    }
    
    /// <summary>
    /// Inserts the specified <paramref name="item"/> at <paramref name="index"/>
    /// </summary>
    public void Insert(int index, T item)
    {
      InsertRange(index, 1, item);
    }
    
    /// <summary>
    /// Removes one item at <paramref name="index"/>
    /// </summary>
    public void RemoveAt(int index)
    {
      RemoveRange(index, 1);
    }
    
    /// <summary>
    /// Adds the specified <paramref name="item"/> to the end of the list.
    /// </summary>
    public void Add(T item)
    {
      InsertRange(this.Count, 1, item);
    }
    
    /// <summary>
    /// Removes all items from this list.
    /// </summary>
    public void Clear()
    {
      root = null;
    }
    
    /// <summary>
    /// Gets whether this list contains the specified item.
    /// </summary>
    public bool Contains(T item)
    {
      return IndexOf(item) >= 0;
    }
    
    /// <summary>
    /// Copies all items in this list to the specified array.
    /// </summary>
    public void CopyTo(T[] array, int arrayIndex)
    {
      if (array == null)
        throw new ArgumentNullException("array");
      if (array.Length < this.Count)
        throw new ArgumentException("The array is too small", "array");
      if (arrayIndex < 0 || arrayIndex + this.Count > array.Length)
        throw new ArgumentOutOfRangeException("arrayIndex", arrayIndex, "Value must be between 0 and " + (array.Length - this.Count));
      foreach (T v in this) {
        array[arrayIndex++] = v;
      }
    }
    
    /// <summary>
    /// Removes the specified item from this list.
    /// </summary>
    public bool Remove(T item)
    {
      int index = IndexOf(item);
      if (index >= 0) {
        RemoveAt(index);
        return true;
      } else {
        return false;
      }
    }
    #endregion
    
    #region IEnumerable<T>
    /// <summary>
    /// Gets an enumerator for this list.
    /// </summary>
    public IEnumerator<T> GetEnumerator()
    {
      if (root != null) {
        Node n = root.LeftMost;
        while (n != null) {
          for (int i = 0; i < n.count; i++) {
            yield return n.value;
          }
          n = n.Successor;
        }
      }
    }
    
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
      return GetEnumerator();
    }
    #endregion
    
    #region Red/Black Tree
    internal const bool RED = true;
    internal const bool BLACK = false;
    
    void InsertAsLeft(Node parentNode, Node newNode)
    {
      Debug.Assert(parentNode.left == null);
      parentNode.left = newNode;
      newNode.parent = parentNode;
      newNode.color = RED;
      UpdateAugmentedData(parentNode);
      FixTreeOnInsert(newNode);
    }
    
    void InsertAsRight(Node parentNode, Node newNode)
    {
      Debug.Assert(parentNode.right == null);
      parentNode.right = newNode;
      newNode.parent = parentNode;
      newNode.color = RED;
      UpdateAugmentedData(parentNode);
      FixTreeOnInsert(newNode);
    }
    
    void FixTreeOnInsert(Node node)
    {
      Debug.Assert(node != null);
      Debug.Assert(node.color == RED);
      Debug.Assert(node.left == null || node.left.color == BLACK);
      Debug.Assert(node.right == null || node.right.color == BLACK);
      
      Node parentNode = node.parent;
      if (parentNode == null) {
        // we inserted in the root -> the node must be black
        // since this is a root node, making the node black increments the number of black nodes
        // on all paths by one, so it is still the same for all paths.
        node.color = BLACK;
        return;
      }
      if (parentNode.color == BLACK) {
        // if the parent node where we inserted was black, our red node is placed correctly.
        // since we inserted a red node, the number of black nodes on each path is unchanged
        // -> the tree is still balanced
        return;
      }
      // parentNode is red, so there is a conflict here!
      
      // because the root is black, parentNode is not the root -> there is a grandparent node
      Node grandparentNode = parentNode.parent;
      Node uncleNode = Sibling(parentNode);
      if (uncleNode != null && uncleNode.color == RED) {
        parentNode.color = BLACK;
        uncleNode.color = BLACK;
        grandparentNode.color = RED;
        FixTreeOnInsert(grandparentNode);
        return;
      }
      // now we know: parent is red but uncle is black
      // First rotation:
      if (node == parentNode.right && parentNode == grandparentNode.left) {
        RotateLeft(parentNode);
        node = node.left;
      } else if (node == parentNode.left && parentNode == grandparentNode.right) {
        RotateRight(parentNode);
        node = node.right;
      }
      // because node might have changed, reassign variables:
      parentNode = node.parent;
      grandparentNode = parentNode.parent;
      
      // Now recolor a bit:
      parentNode.color = BLACK;
      grandparentNode.color = RED;
      // Second rotation:
      if (node == parentNode.left && parentNode == grandparentNode.left) {
        RotateRight(grandparentNode);
      } else {
        // because of the first rotation, this is guaranteed:
        Debug.Assert(node == parentNode.right && parentNode == grandparentNode.right);
        RotateLeft(grandparentNode);
      }
    }
    
    void RemoveNode(Node removedNode)
    {
      if (removedNode.left != null && removedNode.right != null) {
        // replace removedNode with it's in-order successor
        
        Node leftMost = removedNode.right.LeftMost;
        RemoveNode(leftMost); // remove leftMost from its current location
        
        // and overwrite the removedNode with it
        ReplaceNode(removedNode, leftMost);
        leftMost.left = removedNode.left;
        if (leftMost.left != null) leftMost.left.parent = leftMost;
        leftMost.right = removedNode.right;
        if (leftMost.right != null) leftMost.right.parent = leftMost;
        leftMost.color = removedNode.color;
        
        UpdateAugmentedData(leftMost);
        if (leftMost.parent != null) UpdateAugmentedData(leftMost.parent);
        return;
      }
      
      // now either removedNode.left or removedNode.right is null
      // get the remaining child
      Node parentNode = removedNode.parent;
      Node childNode = removedNode.left ?? removedNode.right;
      ReplaceNode(removedNode, childNode);
      if (parentNode != null) UpdateAugmentedData(parentNode);
      if (removedNode.color == BLACK) {
        if (childNode != null && childNode.color == RED) {
          childNode.color = BLACK;
        } else {
          FixTreeOnDelete(childNode, parentNode);
        }
      }
    }
    
    void FixTreeOnDelete(Node node, Node parentNode)
    {
      Debug.Assert(node == null || node.parent == parentNode);
      if (parentNode == null)
        return;
      
      // warning: node may be null
      Node sibling = Sibling(node, parentNode);
      if (sibling.color == RED) {
        parentNode.color = RED;
        sibling.color = BLACK;
        if (node == parentNode.left) {
          RotateLeft(parentNode);
        } else {
          RotateRight(parentNode);
        }
        
        sibling = Sibling(node, parentNode); // update value of sibling after rotation
      }
      
      if (parentNode.color == BLACK
          && sibling.color == BLACK
          && GetColor(sibling.left) == BLACK
          && GetColor(sibling.right) == BLACK)
      {
        sibling.color = RED;
        FixTreeOnDelete(parentNode, parentNode.parent);
        return;
      }
      
      if (parentNode.color == RED
          && sibling.color == BLACK
          && GetColor(sibling.left) == BLACK
          && GetColor(sibling.right) == BLACK)
      {
        sibling.color = RED;
        parentNode.color = BLACK;
        return;
      }
      
      if (node == parentNode.left &&
          sibling.color == BLACK &&
          GetColor(sibling.left) == RED &&
          GetColor(sibling.right) == BLACK)
      {
        sibling.color = RED;
        sibling.left.color = BLACK;
        RotateRight(sibling);
      }
      else if (node == parentNode.right &&
               sibling.color == BLACK &&
               GetColor(sibling.right) == RED &&
               GetColor(sibling.left) == BLACK)
      {
        sibling.color = RED;
        sibling.right.color = BLACK;
        RotateLeft(sibling);
      }
      sibling = Sibling(node, parentNode); // update value of sibling after rotation
      
      sibling.color = parentNode.color;
      parentNode.color = BLACK;
      if (node == parentNode.left) {
        if (sibling.right != null) {
          Debug.Assert(sibling.right.color == RED);
          sibling.right.color = BLACK;
        }
        RotateLeft(parentNode);
      } else {
        if (sibling.left != null) {
          Debug.Assert(sibling.left.color == RED);
          sibling.left.color = BLACK;
        }
        RotateRight(parentNode);
      }
    }
    
    void ReplaceNode(Node replacedNode, Node newNode)
    {
      if (replacedNode.parent == null) {
        Debug.Assert(replacedNode == root);
        root = newNode;
      } else {
        if (replacedNode.parent.left == replacedNode)
          replacedNode.parent.left = newNode;
        else
          replacedNode.parent.right = newNode;
      }
      if (newNode != null) {
        newNode.parent = replacedNode.parent;
      }
      replacedNode.parent = null;
    }
    
    void RotateLeft(Node p)
    {
      // let q be p's right child
      Node q = p.right;
      Debug.Assert(q != null);
      Debug.Assert(q.parent == p);
      // set q to be the new root
      ReplaceNode(p, q);
      
      // set p's right child to be q's left child
      p.right = q.left;
      if (p.right != null) p.right.parent = p;
      // set q's left child to be p
      q.left = p;
      p.parent = q;
      UpdateAugmentedData(p);
      UpdateAugmentedData(q);
    }
    
    void RotateRight(Node p)
    {
      // let q be p's left child
      Node q = p.left;
      Debug.Assert(q != null);
      Debug.Assert(q.parent == p);
      // set q to be the new root
      ReplaceNode(p, q);
      
      // set p's left child to be q's right child
      p.left = q.right;
      if (p.left != null) p.left.parent = p;
      // set q's right child to be p
      q.right = p;
      p.parent = q;
      UpdateAugmentedData(p);
      UpdateAugmentedData(q);
    }
    
    static Node Sibling(Node node)
    {
      if (node == node.parent.left)
        return node.parent.right;
      else
        return node.parent.left;
    }
    
    static Node Sibling(Node node, Node parentNode)
    {
      Debug.Assert(node == null || node.parent == parentNode);
      if (node == parentNode.left)
        return parentNode.right;
      else
        return parentNode.left;
    }
    
    static bool GetColor(Node node)
    {
      return node != null ? node.color : BLACK;
    }
    #endregion
    
    #region CheckProperties
    [Conditional("DATACONSISTENCYTEST")]
    internal void CheckProperties()
    {
      #if DEBUG
      if (root != null) {
        CheckProperties(root);
        
        // check red-black property:
        int blackCount = -1;
        CheckNodeProperties(root, null, RED, 0, ref blackCount);
        
        // ensure that the tree is compressed:
        Node p = root.LeftMost;
        Node n = p.Successor;
        while (n != null) {
          Debug.Assert(!comparisonFunc(p.value, n.value));
          p = n;
          n = p.Successor;
        }
      }
      #endif
    }
    
    #if DEBUG
    void CheckProperties(Node node)
    {
      Debug.Assert(node.count > 0);
      int totalCount = node.count;
      if (node.left != null) {
        CheckProperties(node.left);
        totalCount += node.left.totalCount;
      }
      if (node.right != null) {
        CheckProperties(node.right);
        totalCount += node.right.totalCount;
      }
      Debug.Assert(node.totalCount == totalCount);
    }
    
    /*
    1. A node is either red or black.
    2. The root is black.
    3. All leaves are black. (The leaves are the NIL children.)
    4. Both children of every red node are black. (So every red node must have a black parent.)
    5. Every simple path from a node to a descendant leaf contains the same number of black nodes. (Not counting the leaf node.)
     */
    void CheckNodeProperties(Node node, Node parentNode, bool parentColor, int blackCount, ref int expectedBlackCount)
    {
      if (node == null) return;
      
      Debug.Assert(node.parent == parentNode);
      
      if (parentColor == RED) {
        Debug.Assert(node.color == BLACK);
      }
      if (node.color == BLACK) {
        blackCount++;
      }
      if (node.left == null && node.right == null) {
        // node is a leaf node:
        if (expectedBlackCount == -1)
          expectedBlackCount = blackCount;
        else
          Debug.Assert(expectedBlackCount == blackCount);
      }
      CheckNodeProperties(node.left, node, node.color, blackCount, ref expectedBlackCount);
      CheckNodeProperties(node.right, node, node.color, blackCount, ref expectedBlackCount);
    }
    #endif
    #endregion
    
    #region GetTreeAsString
    internal string GetTreeAsString()
    {
      #if DEBUG
      if (root == null)
        return "<empty tree>";
      StringBuilder b = new StringBuilder();
      AppendTreeToString(root, b, 0);
      return b.ToString();
      #else
      return "Not available in release build.";
      #endif
    }
    
    #if DEBUG
    static void AppendTreeToString(Node node, StringBuilder b, int indent)
    {
      if (node.color == RED)
        b.Append("RED   ");
      else
        b.Append("BLACK ");
      b.AppendLine(node.ToString());
      indent += 2;
      if (node.left != null) {
        b.Append(' ', indent);
        b.Append("L: ");
        AppendTreeToString(node.left, b, indent);
      }
      if (node.right != null) {
        b.Append(' ', indent);
        b.Append("R: ");
        AppendTreeToString(node.right, b, indent);
      }
    }
    #endif
    #endregion
  }
}