source: trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/PowerCollections/RedBlack.cs @ 1927

Last change on this file since 1927 was 1927, checked in by matkovic, 11 years ago

-added PowerCollection library
-added QuadTree
-improved path finding performance

File size: 48.7 KB
Line 
1//******************************
2// Written by Peter Golde
3// Copyright (c) 2004-2007, Wintellect
4//
5// Use and restribution of this code is subject to the license agreement
6// contained in the file "License.txt" accompanying this file.
7//******************************
8
9using System;
10using System.Diagnostics;
11using System.Collections.Generic;
12
13
14namespace Wintellect.PowerCollections 
15{
16    /// <summary>
17    /// Describes what to do if a key is already in the tree when doing an
18    /// insertion.
19    /// </summary>
20    internal enum DuplicatePolicy { 
21        InsertFirst,               // Insert a new node before duplicates
22        InsertLast,               // Insert a new node after duplicates
23        ReplaceFirst,            // Replace the first of the duplicate nodes
24        ReplaceLast,            // Replace the last of the duplicate nodes
25        DoNothing                // Do nothing to the tree
26    };
27
28        /// <summary>
29        /// The base implementation for various collections classes that use Red-Black trees
30        /// as part of their implementation. This class should not (and can not) be
31        /// used directly by end users; it's only for internal use by the collections package.
32        /// </summary>
33        /// <remarks>
34        /// The Red-Black tree manages items of type T, and uses a IComparer&lt;T&gt; that
35        /// compares items to sort the tree. Multiple items can compare equal and be stored
36        /// in the tree. Insert, Delete, and Find operations are provided in their full generality;
37        /// all operations allow dealing with either the first or last of items that compare equal.
38        ///</remarks>
39    [Serializable]
40        internal class RedBlackTree<T>: IEnumerable<T> {
41                private readonly IComparer<T> comparer;                 // interface for comparing elements, only Compare is used.
42                private Node root;                                      // The root of the tree. Can be null when tree is empty.
43                private int count;                                              // The count of elements in the tree.
44
45        private int changeStamp;        // An integer that is changed every time the tree structurally changes.
46                                                        // Used so that enumerations throw an exception if the tree is changed
47                                                        // during enumeration.
48
49        private Node[] stack;               // A stack of nodes. This is cached locally to avoid constant re-allocated it.
50
51        /// <summary>
52        /// Create an array of Nodes big enough for any path from top
53        /// to bottom. This is cached, and reused from call-to-call, so only one
54        /// can be around at a time per tree.
55        /// </summary>
56        /// <returns>The node stack.</returns>
57        private Node[] GetNodeStack()
58        {
59            // Maximum depth needed is 2 * lg count + 1.
60            int maxDepth;
61            if (count < 0x400)
62                maxDepth = 21;
63            else if (count < 0x10000)
64                maxDepth = 41;
65            else
66                maxDepth = 65;
67
68            if (stack == null || stack.Length < maxDepth)
69                stack = new Node[maxDepth];
70
71            return stack;
72        }
73
74        /// <summary>
75                /// The class that is each node in the red-black tree.
76                /// </summary>
77        [Serializable]
78                private class Node {
79                        public Node left, right;
80                        public T item;
81
82            private const uint REDMASK = 0x80000000;
83            private uint count;
84
85            /// <summary>
86            /// Is this a red node?
87            /// </summary>
88            public bool IsRed {
89                get { return (count & REDMASK) != 0; }
90                set { 
91                    if (value) 
92                        count |= REDMASK; 
93                    else
94                        count &= ~REDMASK;
95                }
96            }
97
98            /// <summary>
99            /// Get or set the Count field -- a 31-bit field
100            /// that holds the number of nodes at or below this
101            /// level.
102            /// </summary>
103            public int Count
104            {
105                get { return (int)(count & ~REDMASK); }
106                set { count = (count & REDMASK) | (uint)value; }
107            }
108
109            /// <summary>
110            /// Add one to the Count.
111            /// </summary>
112            public void IncrementCount()
113            {
114                ++count;
115            }
116
117            /// <summary>
118            /// Subtract one from the Count. The current
119            /// Count must be non-zero.
120            /// </summary>
121            public void DecrementCount()
122            {
123                Debug.Assert(Count != 0);
124                --count;
125            }
126
127            /// <summary>
128            /// Clones a node and all its descendants.
129            /// </summary>
130            /// <returns>The cloned node.</returns>
131            public Node Clone()
132            {
133                Node newNode = new Node();
134                newNode.item = item;
135
136                newNode.count = count;
137
138                if (left != null)
139                    newNode.left = left.Clone();
140
141                if (right != null)
142                    newNode.right = right.Clone();
143
144                return newNode;
145            }
146        }
147
148        /// <summary>
149        /// Must be called whenever there is a structural change in the tree. Causes
150        /// changeStamp to be changed, which causes any in-progress enumerations
151        /// to throw exceptions.
152        /// </summary>
153        internal void StopEnumerations()
154        {
155            ++changeStamp;
156        }
157
158        /// <summary>
159        /// Checks the given stamp against the current change stamp. If different, the
160        /// collection has changed during enumeration and an InvalidOperationException
161        /// must be thrown
162        /// </summary>
163        /// <param name="startStamp">changeStamp at the start of the enumeration.</param>
164        private void CheckEnumerationStamp(int startStamp)
165        {
166            if (startStamp != changeStamp) {
167                throw new InvalidOperationException(Strings.ChangeDuringEnumeration);
168            }
169        }
170
171        /// <summary>
172                /// Initialize a red-black tree, using the given interface instance to compare elements. Only
173                /// Compare is used on the IComparer interface.
174                /// </summary>
175                /// <param name="comparer">The IComparer&lt;T&gt; used to sort keys.</param>
176                public RedBlackTree(IComparer<T> comparer) {
177                        this.comparer = comparer;
178                        this.count = 0;
179                        this.root = null;
180                }
181
182                /// <summary>
183                /// Returns the number of elements in the tree.
184                /// </summary>
185                public int ElementCount {
186                        get {
187                                return count;
188                        }
189                }
190
191        /// <summary>
192        /// Clone the tree, returning a new tree containing the same items. Should
193        /// take O(N) take.
194        /// </summary>
195        /// <returns>Clone version of this tree.</returns>
196        public RedBlackTree<T> Clone()
197        {
198            RedBlackTree<T> newTree = new RedBlackTree<T>(comparer);
199            newTree.count = this.count;
200            if (this.root != null)
201                newTree.root = this.root.Clone();
202            return newTree;
203        }
204
205                /// <summary>
206                /// Finds the key in the tree. If multiple items in the tree have
207                /// compare equal to the key, finds the first or last one. Optionally replaces the item
208                /// with the one searched for.
209                /// </summary>
210                /// <param name="key">Key to search for.</param>
211                /// <param name="findFirst">If true, find the first of duplicates, else finds the last of duplicates.</param>
212        /// <param name="replace">If true, replaces the item with key (if function returns true)</param>
213        /// <param name="item">Returns the found item, before replacing (if function returns true).</param>
214        /// <returns>True if the key was found.</returns>
215                public bool Find(T key, bool findFirst, bool replace, out T item) {
216                        Node current = root;                    // current search location in the tree
217                        Node found = null;                      // last node found with the key, or null if none.
218                       
219                        while (current != null) {
220                                int compare = comparer.Compare(key, current.item);
221
222                                if (compare < 0) {
223                                        current = current.left;
224                                }
225                                else if (compare > 0) {
226                                        current = current.right;
227                                }
228                                else {
229                                        // Go left/right on equality to find first/last of elements with this key.
230                                        Debug.Assert(compare == 0);
231                                        found = current;
232                                        if (findFirst)
233                                                current = current.left;
234                                        else
235                                                current = current.right;
236                                }
237                        }
238
239                        if (found != null) {
240                                item = found.item;
241                if (replace)
242                    found.item = key;
243                return true;
244                        }
245                        else {
246                                item = default(T);     
247                                return false;
248                        }
249                }
250
251        /// <summary>
252        /// Finds the index of the key in the tree. If multiple items in the tree have
253        /// compare equal to the key, finds the first or last one.
254        /// </summary>
255        /// <param name="key">Key to search for.</param>
256        /// <param name="findFirst">If true, find the first of duplicates, else finds the last of duplicates.</param>
257        /// <returns>Index of the item found if the key was found, -1 if not found.</returns>
258        public int FindIndex(T key, bool findFirst)
259        {
260            T dummy;
261            if (findFirst)
262                return FirstItemInRange(EqualRangeTester(key), out dummy);
263            else
264                return LastItemInRange(EqualRangeTester(key), out dummy);
265        }
266
267        /// <summary>
268        /// Find the item at a particular index in the tree.
269        /// </summary>
270        /// <param name="index">The zero-based index of the item. Must be &gt;= 0 and &lt; Count.</param>
271        /// <returns>The item at the particular index.</returns>
272        public T GetItemByIndex(int index)
273        {
274            if (index < 0 || index >= count)
275                throw new ArgumentOutOfRangeException("index");
276
277                        Node current = root;                    // current search location in the tree
278
279            for (; ; ) {
280                int leftCount;
281
282                if (current.left != null) 
283                    leftCount = current.left.Count;
284                else 
285                    leftCount = 0;
286
287                if (leftCount > index)
288                    current = current.left;
289                else if (leftCount == index)
290                    return current.item;
291                else {
292                    index -= leftCount + 1;
293                    current = current.right;
294                }
295            }
296                }
297
298                /// <summary>
299                /// Insert a new node into the tree, maintaining the red-black invariants.
300                /// </summary>
301                /// <remarks>Algorithm from Sedgewick, "Algorithms".</remarks>
302                /// <param name="item">The new item to insert</param>
303                /// <param name="dupPolicy">What to do if equal item is already present.</param>
304                /// <param name="previous">If false, returned, the previous item.</param>
305                /// <returns>false if duplicate exists, otherwise true.</returns>
306                public bool Insert(T item, DuplicatePolicy dupPolicy, out T previous) {
307                        Node node = root;
308                        Node parent = null, gparent = null, ggparent = null;    // parent, grand, a great-grantparent of node.
309                        bool wentLeft = false, wentRight = false;                               // direction from parent to node.
310            bool rotated;
311                        Node duplicateFound = null;
312
313            // The tree may be changed.
314            StopEnumerations();
315
316            // We increment counts on the way down the tree. If we end up not inserting an items due
317            // to a duplicate, we need a stack to adjust the counts back. We don't need the stack if the duplicate
318            // policy means that we will always do an insertion.
319            bool needStack = !((dupPolicy == DuplicatePolicy.InsertFirst) || (dupPolicy == DuplicatePolicy.InsertLast));
320            Node[] nodeStack = null;
321            int nodeStackPtr = 0;  // first free item on the stack.
322            if (needStack) 
323                nodeStack = GetNodeStack();
324
325            while (node != null) {
326                // If we find a node with two red children, split it so it doesn't cause problems
327                                // when inserting a node.
328                if (node.left != null && node.left.IsRed && node.right != null && node.right.IsRed) {
329                    node = InsertSplit(ggparent, gparent, parent, node, out rotated);
330
331                    if (needStack && rotated) {
332                        nodeStackPtr -= 2;
333                        if (nodeStackPtr < 0)
334                            nodeStackPtr = 0;
335                    }
336                }
337
338                                // Keep track of parent, grandparent, great-grand parent.
339                                ggparent = gparent; gparent = parent; parent = node;
340
341                                // Compare the key and the node.
342                                int compare = comparer.Compare(item, node.item);
343
344                                if (compare == 0) {
345                                        // Found a node with the data already. Check duplicate policy.
346                                        if (dupPolicy == DuplicatePolicy.DoNothing) {
347                        previous = node.item;
348
349                        // Didn't insert after all. Return counts back to their previous value.
350                        for (int i = 0; i < nodeStackPtr; ++i)
351                            nodeStack[i].DecrementCount();
352
353                        return false;
354                                        }
355                                        else if (dupPolicy == DuplicatePolicy.InsertFirst || dupPolicy == DuplicatePolicy.ReplaceFirst) {
356                                                // Insert first by treating the key as less than nodes in the tree.
357                                                duplicateFound = node;
358                                                compare = -1;
359                                        }
360                                        else {
361                                                Debug.Assert(dupPolicy == DuplicatePolicy.InsertLast || dupPolicy == DuplicatePolicy.ReplaceLast);
362                                                // Insert last by treating the key as greater than nodes in the tree.
363                                                duplicateFound = node;
364                                                compare = 1;
365                                        }
366                                }
367
368                                Debug.Assert(compare != 0);
369
370                node.IncrementCount();
371                if (needStack)
372                    nodeStack[nodeStackPtr++] = node;
373
374                                // Move to the left or right as needed to find the insertion point.
375                                if (compare < 0) {
376                                        node = node.left;
377                                        wentLeft = true; wentRight = false;
378                                }
379                                else {
380                                        node = node.right;
381                                        wentRight = true; wentLeft = false;
382                                }
383                        }
384
385            if (duplicateFound != null) {
386                previous = duplicateFound.item;
387
388                // Are we replacing instread of inserting?
389                if (dupPolicy == DuplicatePolicy.ReplaceFirst || dupPolicy == DuplicatePolicy.ReplaceLast) {
390                    duplicateFound.item = item;
391
392                    // Didn't insert after all. Return counts back to their previous value.
393                    for (int i = 0; i < nodeStackPtr; ++i)
394                        nodeStack[i].DecrementCount();
395
396                    return false;
397                }
398            }
399            else {
400                previous = default(T);
401            }
402
403            // Create a new node.
404                        node = new Node();
405                        node.item = item;
406            node.Count = 1;
407
408                        // Link the node into the tree.
409                        if (wentLeft) 
410                                parent.left = node;
411                        else if (wentRight)
412                                parent.right = node;
413                        else {
414                                Debug.Assert(root == null);
415                                root = node;
416                        }
417
418                        // Maintain the red-black policy.
419                        InsertSplit(ggparent, gparent, parent, node, out rotated);
420
421                        // We've added a node to the tree, so update the count.
422                        count += 1;
423
424            return (duplicateFound == null);
425                }
426
427                /// <summary>
428                /// Split a node with two red children (a 4-node in the 2-3-4 tree formalism), as
429                /// part of an insert operation.
430                /// </summary>
431                /// <param name="ggparent">great grand-parent of "node", can be null near root</param>
432                /// <param name="gparent">grand-parent of "node", can be null near root</param>
433                /// <param name="parent">parent of "node", can be null near root</param>
434                /// <param name="node">Node to split, can't be null</param>
435        /// <param name="rotated">Indicates that rotation(s) occurred in the tree.</param>
436                /// <returns>Node to continue searching from.</returns>
437                private Node InsertSplit(Node ggparent, Node gparent, Node parent, Node node, out bool rotated) {
438                        if (node != root)
439                                node.IsRed = true;
440                        if (node.left != null)
441                                node.left.IsRed = false;
442                        if (node.right != null)
443                                node.right.IsRed = false;
444
445                        if (parent != null && parent.IsRed) {
446                                // Since parent is red, gparent can't be null (root is always black). ggparent
447                                // might be null, however.
448                                Debug.Assert(gparent != null);
449
450                                // if links from gparent and parent are opposite (left/right or right/left),
451                                // then rotate.
452                                if ((gparent.left == parent) != (parent.left == node)) {
453                                        Rotate(gparent, parent, node);
454                                        parent = node;
455                                }
456
457                                gparent.IsRed = true;
458
459                                // Do a rotate to prevent two red links in a row.
460                                Rotate(ggparent, gparent, parent);
461
462                                parent.IsRed = false;
463                rotated = true;
464                                return parent;
465                        }
466                        else {
467                rotated = false;
468                                return node;
469                        }
470                }
471
472                /// <summary>
473                /// Performs a rotation involving the node, it's child and grandchild. The counts of
474        /// childs and grand-child are set the correct values from their children; this is important
475        /// if they have been adjusted on the way down the try as part of an insert/delete.
476                /// </summary>
477                /// <param name="node">Top node of the rotation. Can be null if child==root.</param>
478                /// <param name="child">One child of "node". Not null.</param>
479                /// <param name="gchild">One child of "child". Not null.</param>
480                private void Rotate(Node node, Node child, Node gchild) {
481                        if (gchild == child.left) {
482                                child.left = gchild.right;
483                                gchild.right = child;
484                        }
485                        else {
486                                Debug.Assert(gchild == child.right);
487                                child.right = gchild.left;
488                                gchild.left = child;
489                        }
490
491            // Restore the counts.
492            child.Count = (child.left != null ? child.left.Count : 0) + (child.right != null ? child.right.Count : 0) + 1;
493            gchild.Count = (gchild.left != null ? gchild.left.Count : 0) + (gchild.right != null ? gchild.right.Count : 0) + 1;
494
495                        if (node == null) {
496                                Debug.Assert(child == root);
497                                root = gchild;
498                        }
499                        else if (child == node.left) {
500                                node.left = gchild;
501                        }
502                        else {
503                                Debug.Assert(child == node.right);
504                                node.right = gchild;
505                        }
506                }
507
508                /// <summary>
509                /// Deletes a key from the tree. If multiple elements are equal to key,
510                /// deletes the first or last. If no element is equal to the key,
511                /// returns false.
512                /// </summary>
513                /// <remarks>Top-down algorithm from Weiss. Basic plan is to move down in the tree,
514                /// rotating and recoloring along the way to always keep the current node red, which
515                /// ensures that the node we delete is red. The details are quite complex, however! </remarks>
516                /// <param name="key">Key to delete.</param>
517                /// <param name="deleteFirst">Which item to delete if multiple are equal to key. True to delete the first, false to delete last.</param>
518                /// <param name="item">Returns the item that was deleted, if true returned.</param>
519                /// <returns>True if an element was deleted, false if no element had
520                /// specified key.</returns>
521        public bool Delete(T key, bool deleteFirst, out T item)
522        {
523            return DeleteItemFromRange(EqualRangeTester(key), deleteFirst, out item);
524        }
525
526        ///
527                /// <summary>
528                /// Enumerate all the items in-order
529                /// </summary>
530                /// <returns>An enumerator for all the items, in order.</returns>
531        /// <exception cref="InvalidOperationException">The tree has an item added or deleted during the enumeration.</exception>
532        public IEnumerator<T> GetEnumerator()
533        {
534                        return EnumerateRange(EntireRangeTester).GetEnumerator();
535                }
536
537                /// <summary>
538                /// Enumerate all the items in-order
539                /// </summary>
540                /// <returns>An enumerator for all the items, in order.</returns>
541        /// <exception cref="InvalidOperationException">The tree has an item added or deleted during the enumeration.</exception>
542        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
543        {
544            return GetEnumerator();
545        }
546
547        #region Ranges
548
549        /// <summary>
550        /// A delegate that tests if an item is within a custom range. The range must be a contiguous
551        /// range of items with the ordering of this tree. The range test function must test
552        /// if an item is before, withing, or after the range.
553        /// </summary>
554        /// <param name="item">Item to test against the range.</param>
555        /// <returns>Returns negative if item is before the range, zero if item is withing the range,
556        /// and positive if item is after the range.</returns>
557        public delegate int RangeTester(T item);
558
559        /// <summary>
560        /// Gets a range tester that defines a range by first and last items.
561        /// </summary>
562        /// <param name="useFirst">If true, bound the range on the bottom by first.</param>
563        /// <param name="first">If useFirst is true, the inclusive lower bound.</param>
564        /// <param name="useLast">If true, bound the range on the top by last.</param>
565        /// <param name="last">If useLast is true, the exclusive upper bound.</param>
566        /// <returns>A RangeTester delegate that tests for an item in the given range.</returns>
567        public RangeTester BoundedRangeTester(bool useFirst, T first, bool useLast, T last)
568        {
569            return delegate(T item) {
570                if (useFirst && comparer.Compare(first, item) > 0)
571                    return -1;     // item is before first.
572                else if (useLast && comparer.Compare(last, item) <= 0)
573                    return 1;      // item is after or equal to last.
574                else
575                    return 0;      // item is greater or equal to first, and less than last.
576            };
577        }
578
579        /// <summary>
580        /// Gets a range tester that defines a range by first and last items.
581        /// </summary>
582        /// <param name="first">The lower bound.</param>
583        /// <param name="firstInclusive">True if the lower bound is inclusive, false if exclusive.</param>
584        /// <param name="last">The upper bound.</param>
585        /// <param name="lastInclusive">True if the upper bound is inclusive, false if exclusive.</param>
586        /// <returns>A RangeTester delegate that tests for an item in the given range.</returns>
587        public RangeTester DoubleBoundedRangeTester(T first, bool firstInclusive, T last, bool lastInclusive)
588        {
589            return delegate(T item) {
590                if (firstInclusive) {
591                    if (comparer.Compare(first, item) > 0)
592                        return -1;     // item is before first.
593                }
594                else {
595                    if (comparer.Compare(first, item) >= 0)
596                        return -1;     // item is before or equal to first.
597                }
598
599                if (lastInclusive) {
600                    if (comparer.Compare(last, item) < 0)
601                        return 1;      // item is after last.
602                }
603                else {
604                    if (comparer.Compare(last, item) <= 0)
605                        return 1;      // item is after or equal to last
606                }
607
608                return 0;      // item is between first and last.
609            };
610        }
611
612
613        /// <summary>
614        /// Gets a range tester that defines a range by a lower bound.
615        /// </summary>
616        /// <param name="first">The lower bound.</param>
617        /// <param name="inclusive">True if the lower bound is inclusive, false if exclusive.</param>
618        /// <returns>A RangeTester delegate that tests for an item in the given range.</returns>
619        public RangeTester LowerBoundedRangeTester(T first, bool inclusive)
620        {
621            return delegate(T item) {
622                if (inclusive) {
623                    if (comparer.Compare(first, item) > 0)
624                        return -1;     // item is before first.
625                    else
626                        return 0;      // item is after or equal to first
627                }
628                else {
629                    if (comparer.Compare(first, item) >= 0)
630                        return -1;     // item is before or equal to first.
631                    else
632                        return 0;      // item is after first
633                }
634            };
635        }
636
637
638        /// <summary>
639        /// Gets a range tester that defines a range by upper bound.
640        /// </summary>
641        /// <param name="last">The upper bound.</param>
642        /// <param name="inclusive">True if the upper bound is inclusive, false if exclusive.</param>
643        /// <returns>A RangeTester delegate that tests for an item in the given range.</returns>
644        public RangeTester UpperBoundedRangeTester(T last, bool inclusive)
645        {
646            return delegate(T item) {
647                if (inclusive) {
648                    if (comparer.Compare(last, item) < 0)
649                        return 1;      // item is after last.
650                    else
651                        return 0;      // item is before or equal to last.
652                }
653                else {
654                    if (comparer.Compare(last, item) <= 0)
655                        return 1;      // item is after or equal to last
656                    else
657                        return 0;      // item is before last.
658                }
659            };
660        }
661
662        /// <summary>
663        /// Gets a range tester that defines a range by all items equal to an item.
664        /// </summary>
665        /// <param name="equalTo">The item that is contained in the range.</param>
666        /// <returns>A RangeTester delegate that tests for an item equal to <paramref name="equalTo"/>.</returns>
667        public RangeTester EqualRangeTester(T equalTo)
668        {
669            return delegate(T item) {
670                return comparer.Compare(item, equalTo);
671            };
672        }
673
674        /// <summary>
675        /// A range tester that defines a range that is the entire tree.
676        /// </summary>
677        /// <param name="item">Item to test.</param>
678        /// <returns>Always returns 0.</returns>
679        public int EntireRangeTester(T item)
680        {
681            return 0;
682        }
683
684        /// <summary>
685        /// Enumerate the items in a custom range in the tree. The range is determined by
686        /// a RangeTest delegate.
687        /// </summary>
688        /// <param name="rangeTester">Tests an item against the custom range.</param>
689        /// <returns>An IEnumerable&lt;T&gt; that enumerates the custom range in order.</returns>
690        /// <exception cref="InvalidOperationException">The tree has an item added or deleted during the enumeration.</exception>
691        public IEnumerable<T> EnumerateRange(RangeTester rangeTester)
692        {
693            return EnumerateRangeInOrder(rangeTester, root);
694        }
695
696        /// <summary>
697        /// Enumerate all the items in a custom range, under and including node, in-order.
698        /// </summary>
699        /// <param name="rangeTester">Tests an item against the custom range.</param>
700        /// <param name="node">Node to begin enumeration. May be null.</param>
701        /// <returns>An enumerable of the items.</returns>
702        /// <exception cref="InvalidOperationException">The tree has an item added or deleted during the enumeration.</exception>
703        private IEnumerable<T> EnumerateRangeInOrder(RangeTester rangeTester, Node node)
704        {
705            int startStamp = changeStamp;
706
707            if (node != null) {
708                int compare = rangeTester(node.item);
709
710                if (compare >= 0) {
711                    // At least part of the range may lie to the left.
712                    foreach (T item in EnumerateRangeInOrder(rangeTester, node.left)) {
713                        yield return item;
714                        CheckEnumerationStamp(startStamp);
715                    }
716                }
717
718                if (compare == 0) {
719                    // The item is within the range.
720                    yield return node.item;
721                    CheckEnumerationStamp(startStamp);
722                }
723
724                if (compare <= 0) {
725                    // At least part of the range lies to the right.
726                    foreach (T item in EnumerateRangeInOrder(rangeTester, node.right)) {
727                        yield return item;
728                        CheckEnumerationStamp(startStamp);
729                    }
730                }
731            }
732        }
733
734        /// <summary>
735        /// Enumerate the items in a custom range in the tree, in reversed order. The range is determined by
736        /// a RangeTest delegate.
737        /// </summary>
738        /// <param name="rangeTester">Tests an item against the custom range.</param>
739        /// <returns>An IEnumerable&lt;T&gt; that enumerates the custom range in reversed order.</returns>
740        /// <exception cref="InvalidOperationException">The tree has an item added or deleted during the enumeration.</exception>
741        public IEnumerable<T> EnumerateRangeReversed(RangeTester rangeTester)
742        {
743            return EnumerateRangeInReversedOrder(rangeTester, root);
744        }
745
746        /// <summary>
747        /// Enumerate all the items in a custom range, under and including node, in reversed order.
748        /// </summary>
749        /// <param name="rangeTester">Tests an item against the custom range.</param>
750        /// <param name="node">Node to begin enumeration. May be null.</param>
751        /// <returns>An enumerable of the items, in reversed oreder.</returns>
752        /// <exception cref="InvalidOperationException">The tree has an item added or deleted during the enumeration.</exception>
753        private IEnumerable<T> EnumerateRangeInReversedOrder(RangeTester rangeTester, Node node)
754        {
755            int startStamp = changeStamp;
756
757            if (node != null) {
758                int compare = rangeTester(node.item);
759
760                if (compare <= 0) {
761                    // At least part of the range lies to the right.
762                    foreach (T item in EnumerateRangeInReversedOrder(rangeTester, node.right)) {
763                        yield return item;
764                        CheckEnumerationStamp(startStamp);
765                    }
766                }
767
768                if (compare == 0) {
769                    // The item is within the range.
770                    yield return node.item;
771                    CheckEnumerationStamp(startStamp);
772                }
773
774                if (compare >= 0) {
775                    // At least part of the range may lie to the left.
776                    foreach (T item in EnumerateRangeInReversedOrder(rangeTester, node.left)) {
777                        yield return item;
778                        CheckEnumerationStamp(startStamp);
779                    }
780                }
781            }
782        }
783
784
785        /// <summary>
786        /// Deletes either the first or last item from a range, as identified by a RangeTester
787        /// delegate. If the range is empty, returns false.
788        /// </summary>
789        /// <remarks>Top-down algorithm from Weiss. Basic plan is to move down in the tree,
790        /// rotating and recoloring along the way to always keep the current node red, which
791        /// ensures that the node we delete is red. The details are quite complex, however! </remarks>
792        /// <param name="rangeTester">Range to delete from.</param>
793        /// <param name="deleteFirst">If true, delete the first item from the range, else the last.</param>
794        /// <param name="item">Returns the item that was deleted, if true returned.</param>
795        /// <returns>True if an element was deleted, false if the range is empty.</returns>
796        public bool DeleteItemFromRange(RangeTester rangeTester, bool deleteFirst, out T item)
797        {
798            Node node;                  // The current node.
799            Node parent;                // Parent of the current node.
800            Node gparent;               // Grandparent of the current node.
801            Node sib;                   // Sibling of the current node.
802            Node keyNode;               // Node with the key that is being removed.
803
804            // The tree may be changed.
805            StopEnumerations();
806
807            if (root == null) {
808                // Nothing in the tree. Go home now.
809                item = default(T);
810                return false;
811            }
812
813            // We decrement counts on the way down the tree. If we end up not finding an item to delete
814            // we need a stack to adjust the counts back.
815            Node[] nodeStack = GetNodeStack();
816            int nodeStackPtr = 0;  // first free item on the stack.
817
818            // Start at the root.
819            node = root;
820            sib = parent = gparent = null;
821            keyNode = null;
822
823            // Proceed down the tree, making the current node red so it can be removed.
824            for (; ; ) {
825                Debug.Assert(parent == null || parent.IsRed);
826                Debug.Assert(sib == null || !sib.IsRed);
827                Debug.Assert(!node.IsRed);
828
829                if ((node.left == null || !node.left.IsRed) && (node.right == null || !node.right.IsRed)) {
830                    // node has two black children (null children are considered black).
831                    if (parent == null) {
832                        // Special case for the root.
833                        Debug.Assert(node == root);
834                        node.IsRed = true;
835                    }
836                    else if ((sib.left == null || !sib.left.IsRed) && (sib.right == null || !sib.right.IsRed)) {
837                        // sib has two black children.
838                        node.IsRed = true;
839                        sib.IsRed = true;
840                        parent.IsRed = false;
841                    }
842                    else {
843                        if (parent.left == node && (sib.right == null || !sib.right.IsRed)) {
844                            // sib has a black child on the opposite side as node.
845                            Node tleft = sib.left;
846                            Rotate(parent, sib, tleft);
847                            sib = tleft;
848                        }
849                        else if (parent.right == node && (sib.left == null || !sib.left.IsRed)) {
850                            // sib has a black child on the opposite side as node.
851                            Node tright = sib.right;
852                            Rotate(parent, sib, tright);
853                            sib = tright;
854                        }
855
856                        // sib has a red child.
857                        Rotate(gparent, parent, sib);
858                        node.IsRed = true;
859                        sib.IsRed = true;
860                        sib.left.IsRed = false;
861                        sib.right.IsRed = false;
862
863                        sib.DecrementCount();
864                        nodeStack[nodeStackPtr - 1] = sib;
865                        parent.DecrementCount();
866                        nodeStack[nodeStackPtr++] = parent;
867                    }
868                }
869
870                // Compare the key and move down the tree to the correct child.
871                do {
872                    Node nextNode, nextSib;             // Node we've moving to, and it's sibling.
873
874                    node.DecrementCount();
875                    nodeStack[nodeStackPtr++] = node;
876
877                    // Determine which way to move in the tree by comparing the
878                    // current item to what we're looking for.
879                    int compare = rangeTester(node.item);
880
881                    if (compare == 0) {
882                        // We've found the node to remove. Remember it, then keep traversing the
883                        // tree to either find the first/last of equal keys, and if needed, the predecessor
884                        // or successor (the actual node to be removed).
885                        keyNode = node;
886                        if (deleteFirst) {
887                            nextNode = node.left; nextSib = node.right;
888                        }
889                        else {
890                            nextNode = node.right; nextSib = node.left;
891                        }
892                    }
893                    else if (compare > 0) {
894                        nextNode = node.left; nextSib = node.right;
895                    }
896                    else {
897                        nextNode = node.right; nextSib = node.left;
898                    }
899
900                    // Have we reached the end of our tree walk?
901                    if (nextNode == null)
902                        goto FINISHED;
903
904                    // Move down the tree.
905                    gparent = parent;
906                    parent = node;
907                    node = nextNode;
908                    sib = nextSib;
909                } while (!parent.IsRed && node.IsRed);
910
911                if (!parent.IsRed) {
912                    Debug.Assert(!node.IsRed);
913                    // moved to a black child.
914                    Rotate(gparent, parent, sib);
915
916                    sib.DecrementCount();
917                    nodeStack[nodeStackPtr - 1] = sib;
918                    parent.DecrementCount();
919                    nodeStack[nodeStackPtr++] = parent;
920
921                    sib.IsRed = false;
922                    parent.IsRed = true;
923                    gparent = sib;
924                    sib = (parent.left == node) ? parent.right : parent.left;
925                }
926            }
927
928        FINISHED:
929            if (keyNode == null) {
930                // We never found a node to delete.
931
932                // Return counts back to their previous value.
933                for (int i = 0; i < nodeStackPtr; ++i)
934                    nodeStack[i].IncrementCount();
935
936                // Color the root black, in case it was colored red above.
937                if (root != null)
938                    root.IsRed = false;
939
940                item = default(T);
941                return false;
942            }
943
944            // Return the item from the node we're deleting.
945            item = keyNode.item;
946
947            // At a leaf or a node with one child which is a leaf. Remove the node.
948            if (keyNode != node) {
949                // The node we want to delete is interior. Move the item from the
950                // node we're actually deleting to the key node.
951                keyNode.item = node.item;
952            }
953
954            // If we have one child, replace the current with the child, otherwise,
955            // replace the current node with null.
956            Node replacement;
957            if (node.left != null) {
958                replacement = node.left;
959                Debug.Assert(!node.IsRed && replacement.IsRed);
960                replacement.IsRed = false;
961            }
962            else if (node.right != null) {
963                replacement = node.right;
964                Debug.Assert(!node.IsRed && replacement.IsRed);
965                replacement.IsRed = false;
966            }
967            else
968                replacement = null;
969
970            if (parent == null) {
971                Debug.Assert(root == node);
972                root = replacement;
973            }
974            else if (parent.left == node)
975                parent.left = replacement;
976            else {
977                Debug.Assert(parent.right == node);
978                parent.right = replacement;
979            }
980
981            // Color the root black, in case it was colored red above.
982            if (root != null)
983                root.IsRed = false;
984
985            // Update item count.
986            count -= 1;
987
988            // And we're done.
989            return true;
990        }
991
992        /// <summary>
993        /// Delete all the items in a range, identified by a RangeTester delegate.
994        /// </summary>
995        /// <param name="rangeTester">The delegate that defines the range to delete.</param>
996        /// <returns>The number of items deleted.</returns>
997        public int DeleteRange(RangeTester rangeTester)
998        {
999            bool deleted;
1000            int counter = 0;
1001            T dummy;
1002
1003            do {
1004                deleted = DeleteItemFromRange(rangeTester, true, out dummy);
1005                if (deleted)
1006                    ++counter;
1007            } while (deleted);
1008
1009            return counter;
1010        }
1011
1012        /// <summary>
1013        /// Count the items in a custom range in the tree. The range is determined by
1014        /// a RangeTester delegate.
1015        /// </summary>
1016        /// <param name="rangeTester">The delegate that defines the range.</param>
1017        /// <returns>The number of items in the range.</returns>
1018        public int CountRange(RangeTester rangeTester)
1019        {
1020            return CountRangeUnderNode(rangeTester, root, false, false);
1021        }
1022
1023        /// <summary>
1024        /// Count all the items in a custom range, under and including node.
1025        /// </summary>
1026        /// <param name="rangeTester">The delegate that defines the range.</param>
1027        /// <param name="node">Node to begin enumeration. May be null.</param>
1028        /// <param name="belowRangeTop">This node and all under it are either in the range or below it.</param>
1029        /// <param name="aboveRangeBottom">This node and all under it are either in the range or above it.</param>
1030        /// <returns>The number of items in the range, under and include node.</returns>
1031        private int CountRangeUnderNode(RangeTester rangeTester, Node node, bool belowRangeTop, bool aboveRangeBottom)
1032        {
1033            if (node != null) {
1034                if (belowRangeTop && aboveRangeBottom) {
1035                    // This node and all below it must be in the range. Use the predefined count.
1036                    return node.Count;
1037                }
1038
1039                int compare = rangeTester(node.item);
1040                int counter;
1041
1042                if (compare == 0) {
1043                    counter = 1;  // the node itself
1044                    counter += CountRangeUnderNode(rangeTester, node.left, true, aboveRangeBottom);
1045                    counter += CountRangeUnderNode(rangeTester, node.right, belowRangeTop, true);
1046                }
1047                else if (compare < 0) {
1048                    counter = CountRangeUnderNode(rangeTester, node.right, belowRangeTop, aboveRangeBottom);
1049                }
1050                else { // compare > 0
1051                    counter = CountRangeUnderNode(rangeTester, node.left, belowRangeTop, aboveRangeBottom);
1052                }
1053
1054                return counter;
1055            }
1056            else {
1057                return 0;
1058            }
1059        }
1060
1061        /// <summary>
1062        /// Find the first item in a custom range in the tree, and it's index. The range is determined
1063        /// by a RangeTester delegate.
1064        /// </summary>
1065        /// <param name="rangeTester">The delegate that defines the range.</param>
1066        /// <param name="item">Returns the item found, if true was returned.</param>
1067        /// <returns>Index of first item in range if range is non-empty, -1 otherwise.</returns>
1068        public int FirstItemInRange(RangeTester rangeTester, out T item)
1069        {
1070            Node node = root, found = null;
1071            int curCount = 0, foundIndex = -1;
1072
1073            while (node != null) {
1074                int compare = rangeTester(node.item);
1075
1076                if (compare == 0) {
1077                    found = node;
1078                    if (node.left != null)
1079                        foundIndex = curCount + node.left.Count;
1080                    else
1081                        foundIndex = curCount;
1082                }
1083
1084                if (compare >= 0)
1085                    node = node.left;
1086                else {
1087                    if (node.left != null)
1088                        curCount += node.left.Count + 1;
1089                    else
1090                        curCount += 1;
1091                    node = node.right;
1092                }
1093            }
1094
1095            if (found != null) {
1096                item = found.item;
1097                return foundIndex;
1098            }
1099            else {
1100                item = default(T);
1101                return -1;
1102            }
1103        }
1104
1105        /// <summary>
1106        /// Find the last item in a custom range in the tree, and it's index. The range is determined
1107        /// by a RangeTester delegate.
1108        /// </summary>
1109        /// <param name="rangeTester">The delegate that defines the range.</param>
1110        /// <param name="item">Returns the item found, if true was returned.</param>
1111        /// <returns>Index of the item if range is non-empty, -1 otherwise.</returns>
1112        public int LastItemInRange(RangeTester rangeTester, out T item)
1113        {
1114            Node node = root, found = null;
1115            int curCount = 0, foundIndex = -1;
1116
1117            while (node != null) {
1118                int compare = rangeTester(node.item);
1119
1120                if (compare == 0) {
1121                    found = node;
1122                    if (node.left != null)
1123                        foundIndex = curCount + node.left.Count;
1124                    else
1125                        foundIndex = curCount;
1126                }
1127
1128                if (compare <= 0) {
1129                    if (node.left != null)
1130                        curCount += node.left.Count + 1;
1131                    else
1132                        curCount += 1;
1133                    node = node.right;
1134                }
1135                else
1136                    node = node.left;
1137            }
1138
1139            if (found != null) {
1140                item = found.item;
1141                return foundIndex;
1142            }
1143            else {
1144                item = default(T);
1145                return foundIndex;
1146            }
1147        }
1148
1149        #endregion Ranges
1150
1151#if DEBUG
1152                /// <summary>
1153                /// Prints out the tree.
1154                /// </summary>
1155                public void Print() {
1156                        PrintSubTree(root, "", "");
1157                        Console.WriteLine();
1158                }
1159
1160                /// <summary>
1161                /// Prints a sub-tree.
1162                /// </summary>
1163                /// <param name="node">Node to print from</param>
1164                /// <param name="prefixNode">Prefix for the node</param>
1165                /// <param name="prefixChildren">Prefix for the node's children</param>
1166                private void PrintSubTree(Node node, string prefixNode, string prefixChildren) {
1167                        if (node == null)
1168                                return;
1169
1170                        // Red nodes marked as "@@", black nodes as "..".
1171            Console.WriteLine("{0}{1} {2,4} {3}", prefixNode, node.IsRed ? "@@" : "..", node.Count, node.item);
1172
1173                        PrintSubTree(node.left, prefixChildren + "|-L-", prefixChildren + "|  ");
1174                        PrintSubTree(node.right, prefixChildren + "|-R-", prefixChildren + "   ");
1175                }
1176
1177                /// <summary>
1178                /// Validates that the tree is correctly sorted, and meets the red-black tree
1179                /// axioms.
1180                /// </summary>
1181                public void Validate() {
1182                        Debug.Assert(comparer != null, "Comparer should not be null");
1183
1184                        if (root == null) {
1185                                Debug.Assert(0 == count, "Count in empty tree should be 0.");
1186                       
1187                        }
1188                        else {
1189                                Debug.Assert(! root.IsRed, "Root is not black");
1190                                int blackHeight;
1191                                int nodeCount = ValidateSubTree(root, out blackHeight);
1192                                Debug.Assert(nodeCount == this.count, "Node count of tree is not correct.");
1193                        }
1194                }
1195
1196                /// <summary>
1197                /// Validates a sub-tree and returns the count and black height.
1198                /// </summary>
1199                /// <param name="node">Sub-tree to validate. May be null.</param>
1200                /// <param name="blackHeight">Returns the black height of the tree.</param>
1201        /// <returns>Returns the number of nodes in the sub-tree. 0 if node is null.</returns>
1202                private int ValidateSubTree(Node node, out int blackHeight) {
1203                        if (node == null) {
1204                                blackHeight = 0;
1205                                return 0;
1206                        }
1207
1208                        // Check that this node is sorted with respect to any children.
1209                        if (node.left != null)
1210                Debug.Assert(comparer.Compare(node.left.item, node.item) <= 0, "Left child is not less than or equal to node");
1211            if (node.right != null)
1212                Debug.Assert(comparer.Compare(node.right.item, node.item) >= 0, "Right child is not greater than or equal to node");
1213
1214            // Check that the two-red rule is not violated.
1215                        if (node.IsRed) {
1216                                if (node.left != null)
1217                                        Debug.Assert(! node.left.IsRed, "Node and left child both red");
1218                                if (node.right != null) 
1219                                        Debug.Assert(! node.right.IsRed, "Node and right child both red");
1220                        }
1221
1222                        // Validate sub-trees and get their size and heights.
1223                        int leftCount, leftBlackHeight;
1224                        int rightCount, rightBlackHeight;
1225            int ourCount;
1226
1227                        leftCount = ValidateSubTree(node.left, out leftBlackHeight);
1228                        rightCount = ValidateSubTree(node.right, out rightBlackHeight);
1229            ourCount = leftCount + rightCount + 1;
1230
1231            Debug.Assert(ourCount == node.Count);
1232
1233                        // Validate the equal black-height rule.
1234                        Debug.Assert(leftBlackHeight == rightBlackHeight, "Black heights are not equal");
1235
1236                        // Calculate our black height and return the count
1237                        blackHeight = leftBlackHeight;
1238                        if (! node.IsRed)
1239                                blackHeight += 1;
1240            return ourCount;
1241                }
1242#endif //DEBUG
1243
1244    }
1245
1246}
Note: See TracBrowser for help on using the repository browser.