//****************************** // Written by Peter Golde // Copyright (c) 2004-2005, Wintellect // // Use and restribution of this code is subject to the license agreement // contained in the file "License.txt" accompanying this file. //****************************** using System; using System.Diagnostics; using System.Collections.Generic; namespace Wintellect.PowerCollections { /// /// Describes what to do if a key is already in the tree when doing an /// insertion. /// internal enum DuplicatePolicy { InsertFirst, // Insert a new node before duplicates InsertLast, // Insert a new node after duplicates ReplaceFirst, // Replace the first of the duplicate nodes ReplaceLast, // Replace the last of the duplicate nodes DoNothing // Do nothing to the tree }; /// /// The base implementation for various collections classes that use Red-Black trees /// as part of their implementation. This class should not (and can not) be /// used directly by end users; it's only for internal use by the collections package. /// /// /// The Red-Black tree manages items of type T, and uses a IComparer<T> that /// compares items to sort the tree. Multiple items can compare equal and be stored /// in the tree. Insert, Delete, and Find operations are provided in their full generality; /// all operations allow dealing with either the first or last of items that compare equal. /// [Serializable] internal class RedBlackTree: IEnumerable { private IComparer comparer; // interface for comparing elements, only Compare is used. private Node root; // The root of the tree. Can be null when tree is empty. private int count; // The count of elements in the tree. private int changeStamp; // An integer that is changed every time the tree structurally changes. // Used so that enumerations throw an exception if the tree is changed // during enumeration. private Node[] stack; // A stack of nodes. This is cached locally to avoid constant re-allocated it. /// /// Create an array of Nodes big enough for any path from top /// to bottom. This is cached, and reused from call-to-call, so only one /// can be around at a time per tree. /// /// The node stack. private Node[] GetNodeStack() { // Maximum depth needed is 2 * lg count + 1. int maxDepth; if (count < 0x400) maxDepth = 21; else if (count < 0x10000) maxDepth = 41; else maxDepth = 65; if (stack == null || stack.Length < maxDepth) stack = new Node[maxDepth]; return stack; } /// /// The class that is each node in the red-black tree. /// [Serializable] private class Node { public Node left, right; public T item; private const uint REDMASK = 0x80000000; private uint count; /// /// Is this a red node? /// public bool IsRed { get { return (count & REDMASK) != 0; } set { if (value) count |= REDMASK; else count &= ~REDMASK; } } /// /// Get or set the Count field -- a 31-bit field /// that holds the number of nodes at or below this /// level. /// public int Count { get { return (int)(count & ~REDMASK); } set { count = (count & REDMASK) | (uint)value; } } /// /// Add one to the Count. /// public void IncrementCount() { ++count; } /// /// Subtract one from the Count. The current /// Count must be non-zero. /// public void DecrementCount() { Debug.Assert(Count != 0); --count; } /// /// Clones a node and all its descendants. /// /// The cloned node. public Node Clone() { Node newNode = new Node(); newNode.item = item; newNode.count = count; if (left != null) newNode.left = left.Clone(); if (right != null) newNode.right = right.Clone(); return newNode; } } /// /// Must be called whenever there is a structural change in the tree. Causes /// changeStamp to be changed, which causes any in-progress enumerations /// to throw exceptions. /// internal void StopEnumerations() { ++changeStamp; } /// /// Checks the given stamp against the current change stamp. If different, the /// collection has changed during enumeration and an InvalidOperationException /// must be thrown /// /// changeStamp at the start of the enumeration. private void CheckEnumerationStamp(int startStamp) { if (startStamp != changeStamp) { throw new InvalidOperationException(Strings.ChangeDuringEnumeration); } } /// /// Initialize a red-black tree, using the given interface instance to compare elements. Only /// Compare is used on the IComparer interface. /// /// The IComparer<T> used to sort keys. public RedBlackTree(IComparer comparer) { this.comparer = comparer; this.count = 0; this.root = null; } /// /// Returns the number of elements in the tree. /// public int ElementCount { get { return count; } } /// /// Clone the tree, returning a new tree containing the same items. Should /// take O(N) take. /// /// Clone version of this tree. public RedBlackTree Clone() { RedBlackTree newTree = new RedBlackTree(comparer); newTree.count = this.count; if (this.root != null) newTree.root = this.root.Clone(); return newTree; } /// /// Finds the key in the tree. If multiple items in the tree have /// compare equal to the key, finds the first or last one. Optionally replaces the item /// with the one searched for. /// /// Key to search for. /// If true, find the first of duplicates, else finds the last of duplicates. /// If true, replaces the item with key (if function returns true) /// Returns the found item, before replacing (if function returns true). /// True if the key was found. public bool Find(T key, bool findFirst, bool replace, out T item) { Node current = root; // current search location in the tree Node found = null; // last node found with the key, or null if none. while (current != null) { int compare = comparer.Compare(key, current.item); if (compare < 0) { current = current.left; } else if (compare > 0) { current = current.right; } else { // Go left/right on equality to find first/last of elements with this key. Debug.Assert(compare == 0); found = current; if (findFirst) current = current.left; else current = current.right; } } if (found != null) { item = found.item; if (replace) found.item = key; return true; } else { item = default(T); return false; } } /// /// Finds the index of the key in the tree. If multiple items in the tree have /// compare equal to the key, finds the first or last one. /// /// Key to search for. /// If true, find the first of duplicates, else finds the last of duplicates. /// Index of the item found if the key was found, -1 if not found. public int FindIndex(T key, bool findFirst) { T dummy; if (findFirst) return FirstItemInRange(EqualRangeTester(key), out dummy); else return LastItemInRange(EqualRangeTester(key), out dummy); } /// /// Find the item at a particular index in the tree. /// /// The zero-based index of the item. Must be >= 0 and < Count. /// The item at the particular index. public T GetItemByIndex(int index) { if (index < 0 || index >= count) throw new ArgumentOutOfRangeException("index"); Node current = root; // current search location in the tree for (; ; ) { int leftCount; if (current.left != null) leftCount = current.left.Count; else leftCount = 0; if (leftCount > index) current = current.left; else if (leftCount == index) return current.item; else { index -= leftCount + 1; current = current.right; } } } /// /// Insert a new node into the tree, maintaining the red-black invariants. /// /// Algorithm from Sedgewick, "Algorithms". /// The new item to insert /// What to do if equal item is already present. /// If false, returned, the previous item. /// false if duplicate exists, otherwise true. public bool Insert(T item, DuplicatePolicy dupPolicy, out T previous) { Node node = root; Node parent = null, gparent = null, ggparent = null; // parent, grand, a great-grantparent of node. bool wentLeft = false, wentRight = false; // direction from parent to node. bool rotated; Node duplicateFound = null; // The tree may be changed. StopEnumerations(); // We increment counts on the way down the tree. If we end up not inserting an items due // to a duplicate, we need a stack to adjust the counts back. We don't need the stack if the duplicate // policy means that we will always do an insertion. bool needStack = !((dupPolicy == DuplicatePolicy.InsertFirst) || (dupPolicy == DuplicatePolicy.InsertLast)); Node[] nodeStack = null; int nodeStackPtr = 0; // first free item on the stack. if (needStack) nodeStack = GetNodeStack(); while (node != null) { // If we find a node with two red children, split it so it doesn't cause problems // when inserting a node. if (node.left != null && node.left.IsRed && node.right != null && node.right.IsRed) { node = InsertSplit(ggparent, gparent, parent, node, out rotated); if (needStack && rotated) { nodeStackPtr -= 2; if (nodeStackPtr < 0) nodeStackPtr = 0; } } // Keep track of parent, grandparent, great-grand parent. ggparent = gparent; gparent = parent; parent = node; // Compare the key and the node. int compare = comparer.Compare(item, node.item); if (compare == 0) { // Found a node with the data already. Check duplicate policy. if (dupPolicy == DuplicatePolicy.DoNothing) { previous = node.item; // Didn't insert after all. Return counts back to their previous value. for (int i = 0; i < nodeStackPtr; ++i) nodeStack[i].DecrementCount(); return false; } else if (dupPolicy == DuplicatePolicy.InsertFirst || dupPolicy == DuplicatePolicy.ReplaceFirst) { // Insert first by treating the key as less than nodes in the tree. duplicateFound = node; compare = -1; } else { Debug.Assert(dupPolicy == DuplicatePolicy.InsertLast || dupPolicy == DuplicatePolicy.ReplaceLast); // Insert last by treating the key as greater than nodes in the tree. duplicateFound = node; compare = 1; } } Debug.Assert(compare != 0); node.IncrementCount(); if (needStack) nodeStack[nodeStackPtr++] = node; // Move to the left or right as needed to find the insertion point. if (compare < 0) { node = node.left; wentLeft = true; wentRight = false; } else { node = node.right; wentRight = true; wentLeft = false; } } if (duplicateFound != null) { previous = duplicateFound.item; // Are we replacing instread of inserting? if (duplicateFound != null && (dupPolicy == DuplicatePolicy.ReplaceFirst || dupPolicy == DuplicatePolicy.ReplaceLast)) { duplicateFound.item = item; // Didn't insert after all. Return counts back to their previous value. for (int i = 0; i < nodeStackPtr; ++i) nodeStack[i].DecrementCount(); return false; } } else { previous = default(T); } // Create a new node. node = new Node(); node.item = item; node.Count = 1; // Link the node into the tree. if (wentLeft) parent.left = node; else if (wentRight) parent.right = node; else { Debug.Assert(root == null); root = node; } // Maintain the red-black policy. InsertSplit(ggparent, gparent, parent, node, out rotated); // We've added a node to the tree, so update the count. count += 1; return (duplicateFound == null); } /// /// Split a node with two red children (a 4-node in the 2-3-4 tree formalism), as /// part of an insert operation. /// /// great grand-parent of "node", can be null near root /// grand-parent of "node", can be null near root /// parent of "node", can be null near root /// Node to split, can't be null /// Indicates that rotation(s) occurred in the tree. /// Node to continue searching from. private Node InsertSplit(Node ggparent, Node gparent, Node parent, Node node, out bool rotated) { if (node != root) node.IsRed = true; if (node.left != null) node.left.IsRed = false; if (node.right != null) node.right.IsRed = false; if (parent != null && parent.IsRed) { // Since parent is red, gparent can't be null (root is always black). ggparent // might be null, however. Debug.Assert(gparent != null); // if links from gparent and parent are opposite (left/right or right/left), // then rotate. if ((gparent.left == parent) != (parent.left == node)) { Rotate(gparent, parent, node); parent = node; } gparent.IsRed = true; // Do a rotate to prevent two red links in a row. Rotate(ggparent, gparent, parent); parent.IsRed = false; rotated = true; return parent; } else { rotated = false; return node; } } /// /// Performs a rotation involving the node, it's child and grandchild. The counts of /// childs and grand-child are set the correct values from their children; this is important /// if they have been adjusted on the way down the try as part of an insert/delete. /// /// Top node of the rotation. Can be null if child==root. /// One child of "node". Not null. /// One child of "child". Not null. private void Rotate(Node node, Node child, Node gchild) { if (gchild == child.left) { child.left = gchild.right; gchild.right = child; } else { Debug.Assert(gchild == child.right); child.right = gchild.left; gchild.left = child; } // Restore the counts. child.Count = (child.left != null ? child.left.Count : 0) + (child.right != null ? child.right.Count : 0) + 1; gchild.Count = (gchild.left != null ? gchild.left.Count : 0) + (gchild.right != null ? gchild.right.Count : 0) + 1; if (node == null) { Debug.Assert(child == root); root = gchild; } else if (child == node.left) { node.left = gchild; } else { Debug.Assert(child == node.right); node.right = gchild; } } /// /// Deletes a key from the tree. If multiple elements are equal to key, /// deletes the first or last. If no element is equal to the key, /// returns false. /// /// Top-down algorithm from Weiss. Basic plan is to move down in the tree, /// rotating and recoloring along the way to always keep the current node red, which /// ensures that the node we delete is red. The details are quite complex, however! /// Key to delete. /// Which item to delete if multiple are equal to key. True to delete the first, false to delete last. /// Returns the item that was deleted, if true returned. /// True if an element was deleted, false if no element had /// specified key. public bool Delete(T key, bool deleteFirst, out T item) { return DeleteItemFromRange(EqualRangeTester(key), deleteFirst, out item); } /// /// /// Enumerate all the items in-order /// /// An enumerator for all the items, in order. /// The tree has an item added or deleted during the enumeration. public IEnumerator GetEnumerator() { return EnumerateRange(EntireRangeTester).GetEnumerator(); } /// /// Enumerate all the items in-order /// /// An enumerator for all the items, in order. /// The tree has an item added or deleted during the enumeration. System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); } #region Ranges /// /// A delegate that tests if an item is within a custom range. The range must be a contiguous /// range of items with the ordering of this tree. The range test function must test /// if an item is before, withing, or after the range. /// /// Item to test against the range. /// Returns negative if item is before the range, zero if item is withing the range, /// and positive if item is after the range. public delegate int RangeTester(T item); /// /// Gets a range tester that defines a range by first and last items. /// /// If true, bound the range on the bottom by first. /// If useFirst is true, the inclusive lower bound. /// If true, bound the range on the top by last. /// If useLast is true, the exclusive upper bound. /// A RangeTester delegate that tests for an item in the given range. public RangeTester BoundedRangeTester(bool useFirst, T first, bool useLast, T last) { return delegate(T item) { if (useFirst && comparer.Compare(first, item) > 0) return -1; // item is before first. else if (useLast && comparer.Compare(last, item) <= 0) return 1; // item is after or equal to last. else return 0; // item is greater or equal to first, and less than last. }; } /// /// Gets a range tester that defines a range by first and last items. /// /// The lower bound. /// True if the lower bound is inclusive, false if exclusive. /// The upper bound. /// True if the upper bound is inclusive, false if exclusive. /// A RangeTester delegate that tests for an item in the given range. public RangeTester DoubleBoundedRangeTester(T first, bool firstInclusive, T last, bool lastInclusive) { return delegate(T item) { if (firstInclusive) { if (comparer.Compare(first, item) > 0) return -1; // item is before first. } else { if (comparer.Compare(first, item) >= 0) return -1; // item is before or equal to first. } if (lastInclusive) { if (comparer.Compare(last, item) < 0) return 1; // item is after last. } else { if (comparer.Compare(last, item) <= 0) return 1; // item is after or equal to last } return 0; // item is between first and last. }; } /// /// Gets a range tester that defines a range by a lower bound. /// /// The lower bound. /// True if the lower bound is inclusive, false if exclusive. /// A RangeTester delegate that tests for an item in the given range. public RangeTester LowerBoundedRangeTester(T first, bool inclusive) { return delegate(T item) { if (inclusive) { if (comparer.Compare(first, item) > 0) return -1; // item is before first. else return 0; // item is after or equal to first } else { if (comparer.Compare(first, item) >= 0) return -1; // item is before or equal to first. else return 0; // item is after first } }; } /// /// Gets a range tester that defines a range by upper bound. /// /// The upper bound. /// True if the upper bound is inclusive, false if exclusive. /// A RangeTester delegate that tests for an item in the given range. public RangeTester UpperBoundedRangeTester(T last, bool inclusive) { return delegate(T item) { if (inclusive) { if (comparer.Compare(last, item) < 0) return 1; // item is after last. else return 0; // item is before or equal to last. } else { if (comparer.Compare(last, item) <= 0) return 1; // item is after or equal to last else return 0; // item is before last. } }; } /// /// Gets a range tester that defines a range by all items equal to an item. /// /// The item that is contained in the range. /// A RangeTester delegate that tests for an item equal to . public RangeTester EqualRangeTester(T equalTo) { return delegate(T item) { return comparer.Compare(item, equalTo); }; } /// /// A range tester that defines a range that is the entire tree. /// /// Item to test. /// Always returns 0. public int EntireRangeTester(T item) { return 0; } /// /// Enumerate the items in a custom range in the tree. The range is determined by /// a RangeTest delegate. /// /// Tests an item against the custom range. /// An IEnumerable<T> that enumerates the custom range in order. /// The tree has an item added or deleted during the enumeration. public IEnumerable EnumerateRange(RangeTester rangeTester) { return EnumerateRangeInOrder(rangeTester, root); } /// /// Enumerate all the items in a custom range, under and including node, in-order. /// /// Tests an item against the custom range. /// Node to begin enumeration. May be null. /// An enumerable of the items. /// The tree has an item added or deleted during the enumeration. private IEnumerable EnumerateRangeInOrder(RangeTester rangeTester, Node node) { int startStamp = changeStamp; if (node != null) { int compare = rangeTester(node.item); if (compare >= 0) { // At least part of the range may lie to the left. foreach (T item in EnumerateRangeInOrder(rangeTester, node.left)) { yield return item; CheckEnumerationStamp(startStamp); } } if (compare == 0) { // The item is within the range. yield return node.item; CheckEnumerationStamp(startStamp); } if (compare <= 0) { // At least part of the range lies to the right. foreach (T item in EnumerateRangeInOrder(rangeTester, node.right)) { yield return item; CheckEnumerationStamp(startStamp); } } } } /// /// Enumerate the items in a custom range in the tree, in reversed order. The range is determined by /// a RangeTest delegate. /// /// Tests an item against the custom range. /// An IEnumerable<T> that enumerates the custom range in reversed order. /// The tree has an item added or deleted during the enumeration. public IEnumerable EnumerateRangeReversed(RangeTester rangeTester) { return EnumerateRangeInReversedOrder(rangeTester, root); } /// /// Enumerate all the items in a custom range, under and including node, in reversed order. /// /// Tests an item against the custom range. /// Node to begin enumeration. May be null. /// An enumerable of the items, in reversed oreder. /// The tree has an item added or deleted during the enumeration. private IEnumerable EnumerateRangeInReversedOrder(RangeTester rangeTester, Node node) { int startStamp = changeStamp; if (node != null) { int compare = rangeTester(node.item); if (compare <= 0) { // At least part of the range lies to the right. foreach (T item in EnumerateRangeInReversedOrder(rangeTester, node.right)) { yield return item; CheckEnumerationStamp(startStamp); } } if (compare == 0) { // The item is within the range. yield return node.item; CheckEnumerationStamp(startStamp); } if (compare >= 0) { // At least part of the range may lie to the left. foreach (T item in EnumerateRangeInReversedOrder(rangeTester, node.left)) { yield return item; CheckEnumerationStamp(startStamp); } } } } /// /// Deletes either the first or last item from a range, as identified by a RangeTester /// delegate. If the range is empty, returns false. /// /// Top-down algorithm from Weiss. Basic plan is to move down in the tree, /// rotating and recoloring along the way to always keep the current node red, which /// ensures that the node we delete is red. The details are quite complex, however! /// Range to delete from. /// If true, delete the first item from the range, else the last. /// Returns the item that was deleted, if true returned. /// True if an element was deleted, false if the range is empty. public bool DeleteItemFromRange(RangeTester rangeTester, bool deleteFirst, out T item) { Node node; // The current node. Node parent; // Parent of the current node. Node gparent; // Grandparent of the current node. Node sib; // Sibling of the current node. Node keyNode; // Node with the key that is being removed. // The tree may be changed. StopEnumerations(); if (root == null) { // Nothing in the tree. Go home now. item = default(T); return false; } // We decrement counts on the way down the tree. If we end up not finding an item to delete // we need a stack to adjust the counts back. Node[] nodeStack = GetNodeStack(); int nodeStackPtr = 0; // first free item on the stack. // Start at the root. node = root; sib = parent = gparent = null; keyNode = null; // Proceed down the tree, making the current node red so it can be removed. for (; ; ) { Debug.Assert(parent == null || parent.IsRed); Debug.Assert(sib == null || !sib.IsRed); Debug.Assert(!node.IsRed); if ((node.left == null || !node.left.IsRed) && (node.right == null || !node.right.IsRed)) { // node has two black children (null children are considered black). if (parent == null) { // Special case for the root. Debug.Assert(node == root); node.IsRed = true; } else if ((sib.left == null || !sib.left.IsRed) && (sib.right == null || !sib.right.IsRed)) { // sib has two black children. node.IsRed = true; sib.IsRed = true; parent.IsRed = false; } else { if (parent.left == node && (sib.right == null || !sib.right.IsRed)) { // sib has a black child on the opposite side as node. Node tleft = sib.left; Rotate(parent, sib, tleft); sib = tleft; } else if (parent.right == node && (sib.left == null || !sib.left.IsRed)) { // sib has a black child on the opposite side as node. Node tright = sib.right; Rotate(parent, sib, tright); sib = tright; } // sib has a red child. Rotate(gparent, parent, sib); node.IsRed = true; sib.IsRed = true; sib.left.IsRed = false; sib.right.IsRed = false; sib.DecrementCount(); nodeStack[nodeStackPtr - 1] = sib; parent.DecrementCount(); nodeStack[nodeStackPtr++] = parent; } } // Compare the key and move down the tree to the correct child. do { Node nextNode, nextSib; // Node we've moving to, and it's sibling. node.DecrementCount(); nodeStack[nodeStackPtr++] = node; // Determine which way to move in the tree by comparing the // current item to what we're looking for. int compare = rangeTester(node.item); if (compare == 0) { // We've found the node to remove. Remember it, then keep traversing the // tree to either find the first/last of equal keys, and if needed, the predecessor // or successor (the actual node to be removed). keyNode = node; if (deleteFirst) { nextNode = node.left; nextSib = node.right; } else { nextNode = node.right; nextSib = node.left; } } else if (compare > 0) { nextNode = node.left; nextSib = node.right; } else { nextNode = node.right; nextSib = node.left; } // Have we reached the end of our tree walk? if (nextNode == null) goto FINISHED; // Move down the tree. gparent = parent; parent = node; node = nextNode; sib = nextSib; } while (!parent.IsRed && node.IsRed); if (!parent.IsRed) { Debug.Assert(!node.IsRed); // moved to a black child. Rotate(gparent, parent, sib); sib.DecrementCount(); nodeStack[nodeStackPtr - 1] = sib; parent.DecrementCount(); nodeStack[nodeStackPtr++] = parent; sib.IsRed = false; parent.IsRed = true; gparent = sib; sib = (parent.left == node) ? parent.right : parent.left; } } FINISHED: if (keyNode == null) { // We never found a node to delete. // Return counts back to their previous value. for (int i = 0; i < nodeStackPtr; ++i) nodeStack[i].IncrementCount(); // Color the root black, in case it was colored red above. if (root != null) root.IsRed = false; item = default(T); return false; } // Return the item from the node we're deleting. item = keyNode.item; // At a leaf or a node with one child which is a leaf. Remove the node. if (keyNode != node) { // The node we want to delete is interior. Move the item from the // node we're actually deleting to the key node. keyNode.item = node.item; } // If we have one child, replace the current with the child, otherwise, // replace the current node with null. Node replacement; if (node.left != null) { replacement = node.left; Debug.Assert(!node.IsRed && replacement.IsRed); replacement.IsRed = false; } else if (node.right != null) { replacement = node.right; Debug.Assert(!node.IsRed && replacement.IsRed); replacement.IsRed = false; } else replacement = null; if (parent == null) { Debug.Assert(root == node); root = replacement; } else if (parent.left == node) parent.left = replacement; else { Debug.Assert(parent.right == node); parent.right = replacement; } // Color the root black, in case it was colored red above. if (root != null) root.IsRed = false; // Update item count. count -= 1; // And we're done. return true; } /// /// Delete all the items in a range, identified by a RangeTester delegate. /// /// The delegate that defines the range to delete. /// The number of items deleted. public int DeleteRange(RangeTester rangeTester) { bool deleted; int count = 0; T dummy; do { deleted = DeleteItemFromRange(rangeTester, true, out dummy); if (deleted) ++count; } while (deleted); return count; } /// /// Count the items in a custom range in the tree. The range is determined by /// a RangeTester delegate. /// /// The delegate that defines the range. /// The number of items in the range. public int CountRange(RangeTester rangeTester) { return CountRangeUnderNode(rangeTester, root, false, false); } /// /// Count all the items in a custom range, under and including node. /// /// The delegate that defines the range. /// Node to begin enumeration. May be null. /// This node and all under it are either in the range or below it. /// This node and all under it are either in the range or above it. /// The number of items in the range, under and include node. private int CountRangeUnderNode(RangeTester rangeTester, Node node, bool belowRangeTop, bool aboveRangeBottom) { if (node != null) { if (belowRangeTop && aboveRangeBottom) { // This node and all below it must be in the range. Use the predefined count. return node.Count; } int compare = rangeTester(node.item); int count; if (compare == 0) { count = 1; // the node itself count += CountRangeUnderNode(rangeTester, node.left, true, aboveRangeBottom); count += CountRangeUnderNode(rangeTester, node.right, belowRangeTop, true); } else if (compare < 0) { count = CountRangeUnderNode(rangeTester, node.right, belowRangeTop, aboveRangeBottom); } else { // compare > 0 count = CountRangeUnderNode(rangeTester, node.left, belowRangeTop, aboveRangeBottom); } return count; } else { return 0; } } /// /// Find the first item in a custom range in the tree, and it's index. The range is determined /// by a RangeTester delegate. /// /// The delegate that defines the range. /// Returns the item found, if true was returned. /// Index of first item in range if range is non-empty, -1 otherwise. public int FirstItemInRange(RangeTester rangeTester, out T item) { Node node = root, found = null; int curCount = 0, foundIndex = -1; while (node != null) { int compare = rangeTester(node.item); if (compare == 0) { found = node; if (node.left != null) foundIndex = curCount + node.left.Count; else foundIndex = curCount; } if (compare >= 0) node = node.left; else { if (node.left != null) curCount += node.left.Count + 1; else curCount += 1; node = node.right; } } if (found != null) { item = found.item; return foundIndex; } else { item = default(T); return -1; } } /// /// Find the last item in a custom range in the tree, and it's index. The range is determined /// by a RangeTester delegate. /// /// The delegate that defines the range. /// Returns the item found, if true was returned. /// Index of the item if range is non-empty, -1 otherwise. public int LastItemInRange(RangeTester rangeTester, out T item) { Node node = root, found = null; int curCount = 0, foundIndex = -1; while (node != null) { int compare = rangeTester(node.item); if (compare == 0) { found = node; if (node.left != null) foundIndex = curCount + node.left.Count; else foundIndex = curCount; } if (compare <= 0) { if (node.left != null) curCount += node.left.Count + 1; else curCount += 1; node = node.right; } else node = node.left; } if (found != null) { item = found.item; return foundIndex; } else { item = default(T); return foundIndex; } } #endregion Ranges #if DEBUG /// /// Prints out the tree. /// public void Print() { PrintSubTree(root, "", ""); Console.WriteLine(); } /// /// Prints a sub-tree. /// /// Node to print from /// Prefix for the node /// Prefix for the node's children private void PrintSubTree(Node node, string prefixNode, string prefixChildren) { if (node == null) return; // Red nodes marked as "@@", black nodes as "..". Console.WriteLine("{0}{1} {2,4} {3}", prefixNode, node.IsRed ? "@@" : "..", node.Count, node.item.ToString()); PrintSubTree(node.left, prefixChildren + "|-L-", prefixChildren + "| "); PrintSubTree(node.right, prefixChildren + "|-R-", prefixChildren + " "); } /// /// Validates that the tree is correctly sorted, and meets the red-black tree /// axioms. /// public void Validate() { Debug.Assert(comparer != null, "Comparer should not be null"); if (root == null) { Debug.Assert(0 == count, "Count in empty tree should be 0."); } else { Debug.Assert(! root.IsRed, "Root is not black"); int blackHeight; int nodeCount = ValidateSubTree(root, out blackHeight); Debug.Assert(nodeCount == this.count, "Node count of tree is not correct."); } } /// /// Validates a sub-tree and returns the count and black height. /// /// Sub-tree to validate. May be null. /// Returns the black height of the tree. /// Returns the number of nodes in the sub-tree. 0 if node is null. private int ValidateSubTree(Node node, out int blackHeight) { if (node == null) { blackHeight = 0; return 0; } // Check that this node is sorted with respect to any children. if (node.left != null) Debug.Assert(comparer.Compare(node.left.item, node.item) <= 0, "Left child is not less than or equal to node"); if (node.right != null) Debug.Assert(comparer.Compare(node.right.item, node.item) >= 0, "Right child is not greater than or equal to node"); // Check that the two-red rule is not violated. if (node.IsRed) { if (node.left != null) Debug.Assert(! node.left.IsRed, "Node and left child both red"); if (node.right != null) Debug.Assert(! node.right.IsRed, "Node and right child both red"); } // Validate sub-trees and get their size and heights. int leftCount, leftBlackHeight; int rightCount, rightBlackHeight; int ourCount; leftCount = ValidateSubTree(node.left, out leftBlackHeight); rightCount = ValidateSubTree(node.right, out rightBlackHeight); ourCount = leftCount + rightCount + 1; Debug.Assert(ourCount == node.Count); // Validate the equal black-height rule. Debug.Assert(leftBlackHeight == rightBlackHeight, "Black heights are not equal"); // Calculate our black height and return the count blackHeight = leftBlackHeight; if (! node.IsRed) blackHeight += 1; return ourCount; } #endif //DEBUG } }