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