The RedBlackTree class has several nested classes. Click on the following links to go straight to the relevant source code.
All source code markup was produced by the excellent CopySourceAsHtml Visual Studio 2005 Add-In.
1 using System;
2 using System.Collections;
3 using Microsoft.VisualBasic.Collections;
4 using System.Threading;
5
6
7 public class RedBlackTree : IEnumerable, ICollection
8 {
9 //// Top-down implementation of a Red-Black Tree data structure (no parent pointers and no recursion).
10
11 //// Full .NET Enumeration support (For Each value In tree... Next)
12 //// Full .NET Sychronization support (thread safety via the RedBlackTree.Synchronized() method)
13 //// Automated unit testing is supported through an embedded class (RedBlackTree.Test)
14
15 //// Adapted by Robert Pinchbeck
16 //// from C source code provided in a tutorial by Julienne Walker
17 //// http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
18
27
28 /////////////////////////////////////////////////////////////////////////
29 //// Tree Node Class
30 /////////////////////////////////////////////////////////////////////////
31 protected class RedBlackTreeNode
32 {
33
34 //// Any class that can be compared with the default comparer can be used as a key.
35 //// This includes most system types (string, integer, date, etc...)
36 //// as well as classes that implement the IComparable interface
37 public object key;
38
39 //// The tree class can also be used as a dictionary class by
40 //// inserting a key/value pair...
41 ////
42 //// By default, value = key
43 public object value;
44
45 //// Link "pointers" to child nodes...
46 ////
47 //// link[0)=left child, link[1)=right child
48 public RedBlackTreeNode[] link = new RedBlackTreeNode[2];
49
50 public bool red;
51
52 public RedBlackTreeNode(object key, RedBlackTreeNode left, RedBlackTreeNode right, bool red, object value)
53 {
54 this.key = key;
55 this.link[LEFT] = left;
56 this.link[RIGHT] = right;
57 this.red = red;
58 this.value = value;
59 }
60
61 }
62
63
64 //// Direction constants for the child of a given node //
65 protected const int LEFT = 0;
66 protected const int RIGHT = 1;
67 //// For debugging //
68 protected const int DIR_NOTSET = -1;
69
70 //// Comparison constant (for clarity) //
71 protected const int EQUAL = 0;
72
73 //// Head node points to actual tree root (via the right link)
74 protected RedBlackTreeNode head;
75
76 //// Sentinel node always points to itself (equivalent to null)
77 //// ...allows reference to the children of leaf nodes without causing exceptions.
78 protected RedBlackTreeNode _sentinel;
79
80 //// By default, duplicate keys are not allowed to be inserted //
81 //// Developer can change this by setting the AllowDuplicateKeys property //
82 protected bool _preventDuplicateKeys;
83
84 //// Enumeration support //
85 protected int _count;
86 protected long lastModified;
87
88 //// Comparer for comparing keys (if not specified, uses the default comparer) //
89 protected IComparer _comparer;
90
91 //// Synchronization wrapper //
92 protected ReaderWriterLock _readerWriterLock;
93
94
95 private void CommonNew(IComparer comparer, bool allowDuplicateKeys)
96 {
97 //// Initialize sentinel node for this tree //
98 _sentinel = new RedBlackTreeNode(null, null, null, false, null);
99 _sentinel.link[LEFT] = _sentinel;
100 _sentinel.link[RIGHT] = _sentinel;
101 _sentinel.red = false;
102
103 //// Initialize head node for this tree //
104 head = new RedBlackTreeNode(null, _sentinel, _sentinel, false, null);
105
106 //// Initialize private members //
107 _preventDuplicateKeys = !allowDuplicateKeys;
108
109 _comparer = comparer;
110 }
111
112 public RedBlackTree()
113 {
114 CommonNew(Comparer.Default, false);
115 }
116
117 public RedBlackTree(bool allowDuplicateKeys)
118 {
119 CommonNew(Comparer.Default, allowDuplicateKeys);
120 }
121
122 public RedBlackTree(IComparer comparer)
123 {
124 CommonNew(comparer, false);
125 }
126
127 public RedBlackTree(IComparer comparer, bool allowDuplicateKeys)
128 {
129 CommonNew(comparer, allowDuplicateKeys);
130 }
131
132 //// Copy Constructor (shallow copy) //
133 public RedBlackTree(RedBlackTree tree)
134 {
135 this.head = tree.head;
136 this._sentinel = tree._sentinel;
137 this._preventDuplicateKeys = tree._preventDuplicateKeys;
138 this._count = tree._count;
139 this.lastModified = tree.lastModified;
140 this._comparer = tree._comparer;
141 }
142
143
144 public bool AllowDuplicateKeys
145 {
146 //// By default, duplicate keys are not allowed
147 //// Developer can change this behavior by setting specifying it in the constructor //
148 get { return !_preventDuplicateKeys; }
149 }
150
151
152 public virtual long LastModified
153 {
154 //// This property is used by enumerators to test for validity //
155 //// A 64-bit integer is incremented whenever the tree changes //
156 //// See IEnumerator interface for more information //
157 get { return lastModified; }
158 }
159
160 public static RedBlackTree Synchronized(RedBlackTree tree)
161 {
162 return new RedBlackTreeSynchronized(tree);
163 }
164
165 protected int Opposite(int direction)
166 {
167 //// Return the opposite of the specified direction //
168
169 if (direction == RIGHT)
170 {
171 return LEFT;
172 }
173
174 return RIGHT;
175 }
176
177
178 protected RedBlackTreeNode RotateSingle(RedBlackTreeNode node, int direction)
179 {
180 //// Rotate the specified node (and its children) in the specified direction //
181
182 RedBlackTreeNode child;
183 RedBlackTreeNode grandChild;
184
185 child = node.link[Opposite(direction)];
186 grandChild = child.link[direction];
187
188 node.link[Opposite(direction)] = grandChild;
189 child.link[direction] = node;
190
191 node.red = true;
192 child.red = false;
193
194 return child;
195 }
196
197
198 protected RedBlackTreeNode RotateDouble(RedBlackTreeNode node, int direction)
199 {
200 //// Rotate the specified node (and its children) in the specified direction... //
201 //// ...but first rotate its opposite child in the opposite direction //
202
203 node.link[Opposite(direction)] = RotateSingle(node.link[Opposite(direction)], Opposite(direction));
204
205 return RotateSingle(node, direction);
206 }
207
208
209 protected int CompareKeys(object key1, object key2)
210 {
211 return _comparer.Compare(key1, key2);
212 }
213
214
215 protected RedBlackTreeNode FindNode(object key)
216 {
217 //// Search for the specified key and return its containing node...
218 //// If the key is not found, then the sentinel node is returned //
219
220 RedBlackTreeNode current;
221 int comparison;
222
223 current = head.link[RIGHT];
224
225 while ((!object.ReferenceEquals(current, _sentinel)))
226 {
227
228 comparison = CompareKeys(key, current.key);
229
230 if (comparison < 0)
231 {
232 current = current.link[LEFT];
233 }
234 else if (comparison > 0)
235 {
236 current = current.link[RIGHT];
237 }
238 else
239 {
240 goto ReturnResult;
241 }
242
243 }
244
245 current = _sentinel;
246 ReturnResult:
247
248 return current;
249 }
250
251
252 protected virtual void IncrementCount()
253 {
254 //// Update count property whenever node is added/deleted //
255 _count = _count + 1;
256 lastModified = lastModified + 1;
257 }
258
259
260 protected virtual void DecrementCount()
261 {
262 //// Update count property whenever node is added/deleted //
263 _count = _count - 1;
264 lastModified = lastModified + 1;
265 }
266
267
268 public virtual void Add(object key)
269 {
270 this.Add(key, key);
271 }
272
273 public virtual void Add(object key, object value)
274 {
275 //// Adds an item/value to the tree //
276
277 RedBlackTreeNode greatGrandParent;
278 RedBlackTreeNode grandParent;
279 RedBlackTreeNode parent;
280 RedBlackTreeNode current;
281
282 int direction;
283 int lastDirection;
284 int grandParentDirection;
285
286 int comparison;
287 bool keepSearching;
288
289 try
290 {
291 //// Initialize search //
292 greatGrandParent = null;
293 grandParent = null;
294 parent = head;
295 current = head.link[RIGHT];
296
297 direction = RIGHT;
298 lastDirection = DIR_NOTSET;
299
300
301 //// Search until node has been inserted //
302 keepSearching = true;
303
304 while (keepSearching)
305 {
306
307 //// Check if insert position found //
308 if (object.ReferenceEquals(current, _sentinel))
309 {
310
311 //// Insert position found, add new node to tree //
312 current = new RedBlackTreeNode(key, _sentinel, _sentinel, true, value);
313 parent.link[direction] = current;
314 IncrementCount();
315 keepSearching = false;
316 }
317
318 else
319 {
320
321 //// Check if both children are red //
322 if (current.link[LEFT].red & current.link[RIGHT].red)
323 {
324
325 //// Both children are red, fix it //
326 current.red = true;
327 current.link[LEFT].red = false;
328 current.link[RIGHT].red = false;
329 }
330
331 }
332
333
334 //// Check for red violation //
335 if (current.red & parent.red)
336 {
337
338 //// Red violation detected, fix it //
339
340 if (lastDirection == DIR_NOTSET)
341 {
342 //// This should never happen, if it does, then halt execution //
343 Throw_OrDebug(new RedBlackTreeException("cannot add item to tree, last direction not set"));
344 }
345
346 if (greatGrandParent == null)
347 {
348 //// This should never happen, if it does, then halt execution //
349 Throw_OrDebug(new RedBlackTreeException("cannot add item to tree, greatgrandparent not set"));
350 }
351
352 if (object.ReferenceEquals(grandParent, greatGrandParent.link[LEFT]))
353 {
354 grandParentDirection = LEFT;
355 }
356 else
357 {
358 grandParentDirection = RIGHT;
359 }
360
361 if (object.ReferenceEquals(current, parent.link[lastDirection]))
362 {
363 greatGrandParent.link[grandParentDirection] = RotateSingle(grandParent, Opposite(lastDirection));
364 }
365 else
366 {
367 greatGrandParent.link[grandParentDirection] = RotateDouble(grandParent, Opposite(lastDirection));
368 }
369
370 }
371
372
373 if (keepSearching)
374 {
375
376 comparison = CompareKeys(key, current.key);
377
378 //// Check if duplicate keys are allowed //
379 if (_preventDuplicateKeys)
380 {
381
382 //// Duplicate keys not allowed, enforce it //
383 if (comparison == EQUAL)
384 {
385 throw new RedBlackTreeDuplicateKeyException("add to tree failed (duplicate key)");
386 }
387 }
388
389 lastDirection = direction;
390
391 if (comparison < 0)
392 {
393 direction = LEFT;
394 }
395 else
396 {
397 direction = RIGHT;
398 }
399
400 greatGrandParent = grandParent;
401 grandParent = parent;
402 parent = current;
403 current = current.link[direction];
404 }
405 }
406 }
407
408 finally
409 {
410 //// Ensure that root node is never red //
411 head.link[RIGHT].red = false;
412 }
413
414 }
415
416
417 public virtual object Remove(object key)
418 {
419 //// Removes the specified key (and value) from the tree //
420 //// If there are duplicate keys in the tree, only the first one found is removed //
421
422 RedBlackTreeNode grandParent;
423 RedBlackTreeNode parent;
424 RedBlackTreeNode current;
425 RedBlackTreeNode found;
426
427 int direction;
428 int parentDirection;
429 int lastDirection;
430 int comparison;
431
432 RedBlackTreeNode newParent;
433 RedBlackTreeNode sibling;
434
435 try
436 {
437 found = _sentinel;
438 grandParent = null;
439 parent = null;
440 current = head;
441
442 direction = RIGHT;
443
444 //// Search and push a red down //
445 while ((!object.ReferenceEquals(current.link[direction], _sentinel)))
446 {
447 lastDirection = direction;
448
449 grandParent = parent;
450 parent = current;
451 current = current.link[direction];
452
453 comparison = CompareKeys(key, current.key);
454
455 if (comparison < 0)
456 {
457 direction = LEFT;
458 }
459 else
460 {
461 direction = RIGHT;
462 }
463
464 if (comparison == EQUAL)
465 {
466 found = current;
467 }
468
469 //// Push the red node down //
470 if (!current.red & !current.link[direction].red)
471 {
472
473 if (current.link[Opposite(direction)].red)
474 {
475
476 newParent = RotateSingle(current, direction);
477 parent.link[lastDirection] = newParent;
478 parent = newParent;
479 }
480
481 else
482 {
483
484 sibling = parent.link[Opposite(lastDirection)];
485
486 if ((!object.ReferenceEquals(sibling, _sentinel)))
487 {
488
489 //// Check if sibling's children are both black //
490 if (!sibling.link[Opposite(lastDirection)].red & !sibling.link[lastDirection].red)
491 {
492
493 //// Sibling's children are both black, color flip will suffice
494 parent.red = false;
495 sibling.red = true;
496 current.red = true;
497 }
498
499 else
500 {
501 //// One of sibling's children is red, balance tree as needed //
502 if (object.ReferenceEquals(grandParent.link[LEFT], parent))
503 {
504 parentDirection = LEFT;
505 }
506 else
507 {
508 parentDirection = RIGHT;
509 }
510
511 if (sibling.link[lastDirection].red)
512 {
513
514 newParent = RotateDouble(parent, lastDirection);
515 }
516 else
517 {
518
519 newParent = RotateSingle(parent, lastDirection);
520 }
521
522 //// Ensure correct coloring after balancing //
523 newParent.red = true;
524 newParent.link[LEFT].red = false;
525 newParent.link[RIGHT].red = false;
526 grandParent.link[parentDirection] = newParent;
527 current.red = true;
528
529 }
530
531 }
532
533 }
534
535 }
536
537 }
538
539 //// Check if key was not found //
540 if (object.ReferenceEquals(found, _sentinel))
541 {
542
543 //// Key was not found, throw exception //
544 throw new RedBlackTreeKeyNotFoundException("remove from tree failed (key not found)");
545 }
546
547 //// Found node is being removed, replace it with current node //
548 found.key = current.key;
549 found.value = current.value;
550
551 if (object.ReferenceEquals(parent.link[LEFT], current))
552 {
553 direction = LEFT;
554 }
555 else
556 {
557 direction = RIGHT;
558 }
559
560 if (object.ReferenceEquals(current.link[LEFT], _sentinel))
561 {
562 parentDirection = RIGHT;
563 }
564 else
565 {
566 parentDirection = LEFT;
567 }
568
569 //// Remove current node from tree
570 parent.link[direction] = current.link[parentDirection];
571
572 //// Update counters //
573 DecrementCount();
574 }
575
576 finally
577 {
578 //// Ensure that root node is never red //
579 head.link[RIGHT].red = false;
580 }
581
582 if (object.ReferenceEquals(found, _sentinel))
583 {
584 return null;
585 }
586 else
587 {
588 return found.value;
589 }
590 }
591
592 public virtual object this[object key]
593 {
594 //// Returns the value of the node with the specified key //
595 //// If duplicate keys exist, then the first one found is returned //
596 get
597 {
598 object result;
599 RedBlackTreeNode node;
600
601 node = FindNode(key);
602
603 if (object.ReferenceEquals(node, _sentinel))
604 {
605 throw new RedBlackTreeKeyNotFoundException("cannot retrieve item from tree (key not found)");
606 }
607
608 result = node.value;
609
610 return result;
611 }
612 }
613
614
615 protected virtual object OuterMostItem(int direction)
616 {
617 //// Returns the leftmost/rightmost value in the tree //
618 //// Depending on direction //
619 object result;
620 RedBlackTreeNode node;
621 RedBlackTreeNode previousNode;
622
623 if (direction == LEFT || direction == RIGHT)
624 {
625 }
626 //// do nothing
627 else
628 {
629 Throw_OrDebug(new ArgumentException("invalid direction (" + direction + ")"));
630 }
631
632 previousNode = head;
633 node = previousNode.link[RIGHT];
634
635 while ((!object.ReferenceEquals(node, _sentinel)))
636 {
637 previousNode = node;
638 node = node.link[direction];
639 }
640
641 if (object.ReferenceEquals(previousNode, head))
642 {
643 throw new RedBlackTreeEmptyException("cannot retrieve item from tree (tree is empty)");
644 }
645
646 result = previousNode.value;
647
648 return result;
649 }
650
651 public object LeftMostItem()
652 {
653 //// Returns the value of the leftmost node //
654 return OuterMostItem(DIR_LEFT);
655 }
656
657 public object RightMostItem()
658 {
659 //// Returns the value of the rightmost node //
660 return OuterMostItem(DIR_RIGHT);
661 }
662
663
664 public virtual bool Contains(object key)
665 {
666 //// Checks if a node with the specified key exists...
667 //// Returns true if it does, otherwise returns false //
668
669 bool result = false;
670 RedBlackTreeNode node;
671
672 node = FindNode(key);
673
674 if ((!object.ReferenceEquals(node, _sentinel)))
675 {
676 result = true;
677 }
678
679 return result;
680 }
681
682
683 static internal void Throw_OrDebug(Exception oException)
684 {
685
686 #if DEBUG
687 //// When debugging, stop execution instead of throwing exception //
688 //// (makes debugging the call stack easier) //
689 System.Diagnostics.Debugger.Break();
690 #else
691 throw oException;
692 #endif
693
694 }
695
696 internal virtual void DebugLock()
697 {
698 //// Do nothing, only synchronized class can be locked //
699 }
700
701 internal virtual void DebugRelease()
702 {
703 //// Do nothing, only synchronized class can be released //
704 }
705
706
707 /////////////////////////////////////////////////////////////////////////
708 //// ICollection Interface //
709 /////////////////////////////////////////////////////////////////////////
710 void System.Collections.ICollection.CopyTo(Array array, int index)
711 {
712 foreach (object value in this)
713 {
714 if (value is ICloneable)
715 {
716 ICloneable oCloneable;
717 object oClone;
718
719 oCloneable = (ICloneable)value;
720 oClone = oCloneable.Clone();
721
722 array.SetValue(oClone, index);
723 }
724 else
725 {
726 array.SetValue(value, index);
727 }
728 index = index + 1;
729 }
730 }
731
732
733 int System.Collections.ICollection.Count
734 {
735 get { return _count; }
736 }
737
738
739 bool System.Collections.ICollection.IsSynchronized
740 {
741 get { return false; }
742 }
743
744
745 object System.Collections.ICollection.SyncRoot
746 {
747 get { return this; }
748 }
749
750
751 /////////////////////////////////////////////////////////////////////////
752 //// Synchronization Wrapper Class
753 /////////////////////////////////////////////////////////////////////////
754
755 protected class RedBlackTreeSynchronized : RedBlackTree, ICollection
756 {
757
758 //// Allow either reads or writes, but not both (favor reads with a ReaderWriterLock)
759 protected RedBlackTree _wrappedTree;
760
761 private RedBlackTreeSynchronized()
762 {
763 //// This class cannot be instantiated... it must be copied from an existing tree //
764 }
765
766 public RedBlackTreeSynchronized(RedBlackTree tree)
767 : base(tree)
768 {
769
770 //// Wrapper class does not track count //
771 _count = 0;
772
773 _wrappedTree = tree;
774
775 if (_wrappedTree._readerWriterLock == null)
776 {
777 _wrappedTree._readerWriterLock = new ReaderWriterLock();
778 }
779 }
780
781 private void BeginWrite()
782 {
783 _wrappedTree._readerWriterLock.AcquireWriterLock(Timeout.Infinite);
784 }
785
786
787 private void EndWrite()
788 {
789 _wrappedTree._readerWriterLock.ReleaseWriterLock();
790 }
791
792
793 private void BeginRead()
794 {
795 _wrappedTree._readerWriterLock.AcquireReaderLock(Timeout.Infinite);
796 }
797
798
799 private void EndRead()
800 {
801 _wrappedTree._readerWriterLock.ReleaseReaderLock();
802 }
803
804
805 public override long LastModified
806 {
807 get
808 {
809 BeginRead();
810 try
811 {
812 return _wrappedTree.LastModified;
813 }
814 finally
815 {
816 EndRead();
817 }
818 }
819 }
820
821
822 public override void Add(object key, object value)
823 {
824 BeginWrite();
825 try
826 {
827 _wrappedTree.Add(key, value);
828 }
829 finally
830 {
831 EndWrite();
832 }
833
834 }
835
836
837 public override object Remove(object key)
838 {
839 BeginWrite();
840 try
841 {
842 return _wrappedTree.Remove(key);
843 }
844 finally
845 {
846 EndWrite();
847 }
848 }
849
850
851 public override object this[object key]
852 {
853 get
854 {
855 BeginRead();
856 try
857 {
858 return _wrappedTree[key];
859 }
860 finally
861 {
862 EndRead();
863 }
864 }
865 }
866
867
868 protected override object OuterMostItem(int direction)
869 {
870 BeginRead();
871 try
872 {
873 return _wrappedTree.OuterMostItem(direction);
874 }
875 finally
876 {
877 EndRead();
878 }
879 }
880
881 public override bool Contains(object key)
882 {
883 BeginRead();
884 try
885 {
886 return _wrappedTree.Contains(key);
887 }
888 finally
889 {
890 EndRead();
891 }
892 }
893
894
895 void System.Collections.ICollection.CopyTo(Array array, int index)
896 {
897 BeginRead();
898 try
899 {
900 ((ICollection)_wrappedTree).CopyTo(array, index);
901 }
902 finally
903 {
904 EndRead();
905 }
906 }
907
908
909 int System.Collections.ICollection.Count
910 {
911 get
912 {
913 BeginRead();
914 try
915 {
916 return ((ICollection)_wrappedTree).Count;
917 }
918 finally
919 {
920 EndRead();
921 }
922 }
923 }
924
925
926 bool System.Collections.ICollection.IsSynchronized
927 {
928 get { return true; }
929 }
930
931
932 object System.Collections.ICollection.SyncRoot
933 {
934 get
935 {
936 return ((ICollection)_wrappedTree).SyncRoot;
937 }
938 }
939
940 internal override void DebugLock()
941 {
942 BeginWrite();
943 }
944
945 internal override void DebugRelease()
946 {
947 EndWrite();
948 }
949
950 }
951
952
953 /////////////////////////////////////////////////////////////////////////
954 //// IEnumerable Interface //
955 /////////////////////////////////////////////////////////////////////////
956 private class RedBlackTreeEnumerator : IEnumerator
957 {
958
959 private RedBlackTree _tree;
960 private System.Collections.Stack _nodeStack;
961 private RedBlackTreeNode _currentNode;
962 private object _currentValue;
963 private object _currentKey;
964 private long _treeLastModified;
965 private int _direction;
966
967
968 public RedBlackTreeEnumerator(RedBlackTree tree, int direction)
969 {
970 _direction = direction;
971
972 _tree = tree;
973 _treeLastModified = tree.LastModified;
974 ((IEnumerator)this).Reset();
975 }
976
977
978 object System.Collections.IEnumerator.Current
979 {
980 get
981 {
982 if ((_currentKey == null))
983 {
984 Throw_OrDebug(new InvalidOperationException("current failed (invalid enumerator)"));
985 }
986
987 return _currentValue;
988 }
989 }
990
991
992
993 bool System.Collections.IEnumerator.MoveNext()
994 {
995 bool result;
996
997 if (_tree.LastModified != _treeLastModified)
998 {
999 Throw_OrDebug(new InvalidOperationException("movenext failed (tree was modified during enumeration)"));
1000 }
1001
1002 if (object.ReferenceEquals(_currentNode, _tree._sentinel))
1003 {
1004 _currentNode = (RedBlackTreeNode)_nodeStack.Pop();
1005
1006 if (_currentNode == null)
1007 {
1008 result = false;
1009 }
1010 else
1011 {
1012 result = true;
1013 }
1014
1015 goto ExitSub;
1016 }
1017
1018 _currentNode = _currentNode.link[_tree.Opposite(_direction)];
1019
1020 if (object.ReferenceEquals(_currentNode, _tree._sentinel))
1021 {
1022 _currentNode = (RedBlackTreeNode)_nodeStack.Pop();
1023
1024 if (_currentNode == null)
1025 {
1026 result = false;
1027 }
1028 else
1029 {
1030 result = true;
1031 }
1032 goto ExitSub;
1033 }
1034
1035 while ((!object.ReferenceEquals(_currentNode, _tree._sentinel)))
1036 {
1037 _nodeStack.Push(_currentNode);
1038 _currentNode = _currentNode.link[_direction];
1039 }
1040
1041 _currentNode = (RedBlackTreeNode)_nodeStack.Pop();
1042
1043 result = true;
1044 ExitSub:
1045
1046 if (_currentNode == null)
1047 {
1048 _currentKey = null;
1049 _currentValue = null;
1050 }
1051
1052 else if (object.ReferenceEquals(_currentNode, _tree._sentinel))
1053 {
1054 _currentKey = null;
1055 _currentValue = null;
1056 }
1057
1058 else
1059 {
1060 _currentKey = _currentNode.key;
1061 _currentValue = _currentNode.value;
1062
1063 }
1064
1065 return result;
1066 }
1067
1068
1069 void System.Collections.IEnumerator.Reset()
1070 {
1071 RedBlackTreeNode nextNode;
1072
1073 if (_tree.LastModified != _treeLastModified)
1074 {
1075 Throw_OrDebug(new InvalidOperationException("reset failed (tree was modified during enumeration)"));
1076 }
1077
1078 _currentKey = null;
1079 _currentValue = null;
1080
1081 _nodeStack = new System.Collections.Stack();
1082 _nodeStack.Push(null);
1083
1084 _currentNode = _tree.head.link[RIGHT];
1085
1086 while ((!object.ReferenceEquals(_currentNode, _tree._sentinel)))
1087 {
1088 _nodeStack.Push(_currentNode);
1089
1090 nextNode = _currentNode.link[_direction];
1091
1092 if (object.ReferenceEquals(nextNode, _tree._sentinel))
1093 {
1094 _currentKey = _currentNode.key;
1095 _currentValue = _currentNode.value;
1096 }
1097
1098 _currentNode = nextNode;
1099 }
1100 }
1101 }
1102
1103
1104 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
1105 {
1106 //// Enumeration is from left to right by default (sorted ascending)
1107 return new RedBlackTreeEnumerator(this, LEFT);
1108 }
1109
1110 System.Collections.IEnumerator GetLeftToRightEnumerator()
1111 {
1112 //// (sorted ascending)
1113 return new RedBlackTreeEnumerator(this, LEFT);
1114 }
1115
1116 System.Collections.IEnumerator GetRightTleftEnumerator()
1117 {
1118 //// (sorted descending)
1119 return new RedBlackTreeEnumerator(this, RIGHT);
1120 }
1121
1122
1123
1124 /////////////////////////////////////////////////////////////////////////
1125 //// Exception Classes
1126 /////////////////////////////////////////////////////////////////////////
1127
1128 public class RedBlackTreeException : Exception
1129 {
1130
1131 public RedBlackTreeException(string message)
1132 : base(message)
1133 {
1134 }
1135 }
1136
1137 public class RedBlackTreeDuplicateKeyException : ArgumentException
1138 {
1139
1140 public RedBlackTreeDuplicateKeyException(string message)
1141 : base(message)
1142 {
1143 }
1144 }
1145
1146 public class RedBlackTreeKeyNotFoundException : ArgumentException
1147 {
1148
1149 public RedBlackTreeKeyNotFoundException(string message)
1150 : base(message)
1151 {
1152 }
1153 }
1154
1155 public class RedBlackTreeEmptyException : RedBlackTreeException
1156 {
1157
1158 public RedBlackTreeEmptyException(string message)
1159 : base(message)
1160 {
1161 }
1162 }
1864 }
1865 }
1866 }