?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
2010-06-21 Marek Habersack <mhabersack@novell.com>
[mcs.git] / class / System / System.Collections.Generic / RBTree.cs
blobde0fe796fef9a9f52e95728f8024ee8681abc454
1 //
2 // System.Collections.Generic.RBTree
3 //
4 // Authors:
5 // Raja R Harinath <rharinath@novell.com>
6 //
7
8 //
9 // Copyright (C) 2007, Novell, Inc.
10 //
11 // Permission is hereby granted, free of charge, to any person obtaining
12 // a copy of this software and associated documentation files (the
13 // "Software"), to deal in the Software without restriction, including
14 // without limitation the rights to use, copy, modify, merge, publish,
15 // distribute, sublicense, and/or sell copies of the Software, and to
16 // permit persons to whom the Software is furnished to do so, subject to
17 // the following conditions:
18 //
19 // The above copyright notice and this permission notice shall be
20 // included in all copies or substantial portions of the Software.
21 //
22 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
23 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
24 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
25 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
26 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
27 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
28 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
29 //
30
31 #define ONE_MEMBER_CACHE
32
33 #if NET_2_0
34 using System;
35 using System.Collections;
36
37 namespace System.Collections.Generic
38 {
39 [Serializable]
40 internal class RBTree : IEnumerable, IEnumerable<RBTree.Node> {
41 public interface INodeHelper<T> {
42 int Compare (T key, Node node);
43 Node CreateNode (T key);
44 }
45
46 public abstract class Node {
47 public Node left, right;
48 uint size_black;
49
50 const uint black_mask = 1;
51 const int black_shift = 1;
52 public bool IsBlack {
53 get { return (size_black & black_mask) == black_mask; }
54 set { size_black = value ? (size_black | black_mask) : (size_black & ~black_mask); }
55 }
56
57 public uint Size {
58 get { return size_black >> black_shift; }
59 set { size_black = (value << black_shift) | (size_black & black_mask); }
60 }
61
62 public uint FixSize ()
63 {
64 Size = 1;
65 if (left != null)
66 Size += left.Size;
67 if (right != null)
68 Size += right.Size;
69 return Size;
70 }
71
72 public Node ()
73 {
74 size_black = 2; // Size == 1, IsBlack = false
75 }
76
77 public abstract void SwapValue (Node other);
78
79 #if TEST
80 public int VerifyInvariants ()
81 {
82 int black_depth_l = 0;
83 int black_depth_r = 0;
84 uint size = 1;
85 bool child_is_red = false;
86 if (left != null) {
87 black_depth_l = left.VerifyInvariants ();
88 size += left.Size;
89 child_is_red |= !left.IsBlack;
90 }
91
92 if (right != null) {
93 black_depth_r = right.VerifyInvariants ();
94 size += right.Size;
95 child_is_red |= !right.IsBlack;
96 }
97
98 if (black_depth_l != black_depth_r)
99 throw new SystemException ("Internal error: black depth mismatch");
100
101 if (!IsBlack && child_is_red)
102 throw new SystemException ("Internal error: red-red conflict");
103 if (Size != size)
104 throw new SystemException ("Internal error: metadata error");
105
106 return black_depth_l + (IsBlack ? 1 : 0);
107 }
108
109 public abstract void Dump (string indent);
110 #endif
111 }
112
113 Node root;
114 object hlp;
115 uint version;
116
117 #if ONE_MEMBER_CACHE
118 #if TARGET_JVM
119 static readonly LocalDataStoreSlot _cachedPathStore = System.Threading.Thread.AllocateDataSlot ();
120
121 static List<Node> cached_path {
122 get { return (List<Node>) System.Threading.Thread.GetData (_cachedPathStore); }
123 set { System.Threading.Thread.SetData (_cachedPathStore, value); }
124 }
125 #else
126 [ThreadStatic]
127 static List<Node> cached_path;
128 #endif
129
130 static List<Node> alloc_path ()
131 {
132 if (cached_path == null)
133 return new List<Node> ();
134
135 List<Node> path = cached_path;
136 cached_path = null;
137 return path;
138 }
139
140 static void release_path (List<Node> path)
141 {
142 if (cached_path == null || cached_path.Capacity < path.Capacity) {
143 path.Clear ();
144 cached_path = path;
145 }
146 }
147 #else
148 static List<Node> alloc_path ()
149 {
150 return new List<Node> ();
151 }
152
153 static void release_path (List<Node> path)
154 {
155 }
156 #endif
157
158 public RBTree (object hlp)
159 {
160 // hlp is INodeHelper<T> for some T
161 this.hlp = hlp;
162 }
163
164 public void Clear ()
165 {
166 root = null;
167 ++version;
168 }
169
170 // if key is already in the tree, return the node associated with it
171 // if not, insert new_node into the tree, and return it
172 public Node Intern<T> (T key, Node new_node)
173 {
174 if (root == null) {
175 if (new_node == null)
176 new_node = ((INodeHelper<T>) hlp).CreateNode (key);
177 root = new_node;
178 root.IsBlack = true;
179 ++version;
180 return root;
181 }
182
183 List<Node> path = alloc_path ();
184 int in_tree_cmp = find_key (key, path);
185 Node retval = path [path.Count - 1];
186 if (retval == null) {
187 if (new_node == null)
188 new_node = ((INodeHelper<T>) hlp).CreateNode (key);
189 retval = do_insert (in_tree_cmp, new_node, path);
190 }
191 // no need for a try .. finally, this is only used to mitigate allocations
192 release_path (path);
193 return retval;
194 }
195
196 // returns the just-removed node (or null if the value wasn't in the tree)
197 public Node Remove<T> (T key)
198 {
199 if (root == null)
200 return null;
201
202 List<Node> path = alloc_path ();
203 int in_tree_cmp = find_key (key, path);
204 Node retval = null;
205 if (in_tree_cmp == 0)
206 retval = do_remove (path);
207 // no need for a try .. finally, this is only used to mitigate allocations
208 release_path (path);
209 return retval;
210 }
211
212 public Node Lookup<T> (T key)
213 {
214 INodeHelper<T> hlp = (INodeHelper<T>) this.hlp;
215 Node current = root;
216 while (current != null) {
217 int c = hlp.Compare (key, current);
218 if (c == 0)
219 break;
220 current = c < 0 ? current.left : current.right;
221 }
222 return current;
223 }
224
225 public void Bound<T> (T key, ref Node lower, ref Node upper)
226 {
227 INodeHelper<T> hlp = (INodeHelper<T>) this.hlp;
228 Node current = root;
229 while (current != null) {
230 int c = hlp.Compare (key, current);
231 if (c <= 0)
232 upper = current;
233 if (c >= 0)
234 lower = current;
235 if (c == 0)
236 break;
237 current = c < 0 ? current.left : current.right;
238 }
239 }
240
241 public int Count {
242 get { return root == null ? 0 : (int) root.Size; }
243 }
244
245 public Node this [int index] {
246 get {
247 if (index < 0 || index >= Count)
248 throw new IndexOutOfRangeException ("index");
249
250 Node current = root;
251 while (current != null) {
252 int left_size = current.left == null ? 0 : (int) current.left.Size;
253 if (index == left_size)
254 return current;
255 if (index < left_size) {
256 current = current.left;
257 } else {
258 index -= left_size + 1;
259 current = current.right;
260 }
261 }
262 throw new SystemException ("Internal Error: index calculation");
263 }
264 }
265
266 public NodeEnumerator GetEnumerator ()
267 {
268 return new NodeEnumerator (this);
269 }
270
271 // Get an enumerator that starts at 'key' or the next higher element in the tree
272 public NodeEnumerator GetSuffixEnumerator<T> (T key)
273 {
274 var pennants = new Stack<Node> ();
275 INodeHelper<T> hlp = (INodeHelper<T>) this.hlp;
276 Node current = root;
277 while (current != null) {
278 int c = hlp.Compare (key, current);
279 if (c <= 0)
280 pennants.Push (current);
281 if (c == 0)
282 break;
283 current = c < 0 ? current.left : current.right;
284 }
285 return new NodeEnumerator (this, pennants);
286 }
287
288 IEnumerator<Node> IEnumerable<Node>.GetEnumerator ()
289 {
290 return GetEnumerator ();
291 }
292
293 IEnumerator IEnumerable.GetEnumerator ()
294 {
295 return GetEnumerator ();
296 }
297
298 #if TEST
299 public void VerifyInvariants ()
300 {
301 if (root != null) {
302 if (!root.IsBlack)
303 throw new SystemException ("Internal Error: root is not black");
304 root.VerifyInvariants ();
305 }
306 }
307
308 public void Dump ()
309 {
310 if (root != null)
311 root.Dump ("");
312 }
313 #endif
314
315 // Pre-condition: root != null
316 int find_key<T> (T key, List<Node> path)
317 {
318 INodeHelper<T> hlp = (INodeHelper<T>) this.hlp;
319 int c = 0;
320 Node sibling = null;
321 Node current = root;
322
323 if (path != null)
324 path.Add (root);
325
326 while (current != null) {
327 c = hlp.Compare (key, current);
328 if (c == 0)
329 return c;
330
331 if (c < 0) {
332 sibling = current.right;
333 current = current.left;
334 } else {
335 sibling = current.left;
336 current = current.right;
337 }
338
339 if (path != null) {
340 path.Add (sibling);
341 path.Add (current);
342 }
343 }
344
345 return c;
346 }
347
348 Node do_insert (int in_tree_cmp, Node current, List<Node> path)
349 {
350 path [path.Count - 1] = current;
351 Node parent = path [path.Count - 3];
352
353 if (in_tree_cmp < 0)
354 parent.left = current;
355 else
356 parent.right = current;
357 for (int i = 0; i < path.Count - 2; i += 2)
358 ++ path [i].Size;
359
360 if (!parent.IsBlack)
361 rebalance_insert (path);
362
363 if (!root.IsBlack)
364 throw new SystemException ("Internal error: root is not black");
365
366 ++version;
367 return current;
368 }
369
370 Node do_remove (List<Node> path)
371 {
372 int curpos = path.Count - 1;
373
374 Node current = path [curpos];
375 if (current.left != null) {
376 Node pred = right_most (current.left, current.right, path);
377 current.SwapValue (pred);
378 if (pred.left != null) {
379 Node ppred = pred.left;
380 path.Add (null); path.Add (ppred);
381 pred.SwapValue (ppred);
382 }
383 } else if (current.right != null) {
384 Node succ = current.right;
385 path.Add (null); path.Add (succ);
386 current.SwapValue (succ);
387 }
388
389 curpos = path.Count - 1;
390 current = path [curpos];
391
392 if (current.Size != 1)
393 throw new SystemException ("Internal Error: red-black violation somewhere");
394
395 // remove it from our data structures
396 path [curpos] = null;
397 node_reparent (curpos == 0 ? null : path [curpos-2], current, 0, null);
398
399 for (int i = 0; i < path.Count - 2; i += 2)
400 -- path [i].Size;
401
402 if (current.IsBlack) {
403 current.IsBlack = false;
404 if (curpos != 0)
405 rebalance_delete (path);
406 }
407
408 if (root != null && !root.IsBlack)
409 throw new SystemException ("Internal Error: root is not black");
410
411 ++version;
412 return current;
413 }
414
415 // Pre-condition: current is red
416 void rebalance_insert (List<Node> path)
417 {
418 int curpos = path.Count - 1;
419 do {
420 // parent == curpos-2, uncle == curpos-3, grandpa == curpos-4
421 if (path [curpos-3] == null || path [curpos-3].IsBlack) {
422 rebalance_insert__rotate_final (curpos, path);
423 return;
424 }
425
426 path [curpos-2].IsBlack = path [curpos-3].IsBlack = true;
427
428 curpos -= 4; // move to the grandpa
429
430 if (curpos == 0) // => current == root
431 return;
432 path [curpos].IsBlack = false;
433 } while (!path [curpos-2].IsBlack);
434 }
435
436 // Pre-condition: current is black
437 void rebalance_delete (List<Node> path)
438 {
439 int curpos = path.Count - 1;
440 do {
441 Node sibling = path [curpos-1];
442 // current is black => sibling != null
443 if (!sibling.IsBlack) {
444 // current is black && sibling is red
445 // => both sibling.left and sibling.right are black, and are not null
446 curpos = ensure_sibling_black (curpos, path);
447 // one of the nephews became the new sibling -- in either case, sibling != null
448 sibling = path [curpos-1];
449 }
450
451 if ((sibling.left != null && !sibling.left.IsBlack) ||
452 (sibling.right != null && !sibling.right.IsBlack)) {
453 rebalance_delete__rotate_final (curpos, path);
454 return;
455 }
456
457 sibling.IsBlack = false;
458
459 curpos -= 2; // move to the parent
460
461 if (curpos == 0)
462 return;
463 } while (path [curpos].IsBlack);
464 path [curpos].IsBlack = true;
465 }
466
467 void rebalance_insert__rotate_final (int curpos, List<Node> path)
468 {
469 Node current = path [curpos];
470 Node parent = path [curpos-2];
471 Node grandpa = path [curpos-4];
472
473 uint grandpa_size = grandpa.Size;
474
475 Node new_root;
476
477 bool l1 = parent == grandpa.left;
478 bool l2 = current == parent.left;
479 if (l1 && l2) {
480 grandpa.left = parent.right; parent.right = grandpa;
481 new_root = parent;
482 } else if (l1 && !l2) {
483 grandpa.left = current.right; current.right = grandpa;
484 parent.right = current.left; current.left = parent;
485 new_root = current;
486 } else if (!l1 && l2) {
487 grandpa.right = current.left; current.left = grandpa;
488 parent.left = current.right; current.right = parent;
489 new_root = current;
490 } else { // (!l1 && !l2)
491 grandpa.right = parent.left; parent.left = grandpa;
492 new_root = parent;
493 }
494
495 grandpa.FixSize (); grandpa.IsBlack = false;
496 if (new_root != parent)
497 parent.FixSize (); /* parent is red already, so no need to set it */
498
499 new_root.IsBlack = true;
500 node_reparent (curpos == 4 ? null : path [curpos-6], grandpa, grandpa_size, new_root);
501 }
502
503 // Pre-condition: sibling is black, and one of sibling.left and sibling.right is red
504 void rebalance_delete__rotate_final (int curpos, List<Node> path)
505 {
506 //Node current = path [curpos];
507 Node sibling = path [curpos-1];
508 Node parent = path [curpos-2];
509
510 uint parent_size = parent.Size;
511 bool parent_was_black = parent.IsBlack;
512
513 Node new_root;
514 if (parent.right == sibling) {
515 // if far nephew is black
516 if (sibling.right == null || sibling.right.IsBlack) {
517 // => near nephew is red, move it up
518 Node nephew = sibling.left;
519 parent.right = nephew.left; nephew.left = parent;
520 sibling.left = nephew.right; nephew.right = sibling;
521 new_root = nephew;
522 } else {
523 parent.right = sibling.left; sibling.left = parent;
524 sibling.right.IsBlack = true;
525 new_root = sibling;
526 }
527 } else {
528 // if far nephew is black
529 if (sibling.left == null || sibling.left.IsBlack) {
530 // => near nephew is red, move it up
531 Node nephew = sibling.right;
532 parent.left = nephew.right; nephew.right = parent;
533 sibling.right = nephew.left; nephew.left = sibling;
534 new_root = nephew;
535 } else {
536 parent.left = sibling.right; sibling.right = parent;
537 sibling.left.IsBlack = true;
538 new_root = sibling;
539 }
540 }
541
542 parent.FixSize (); parent.IsBlack = true;
543 if (new_root != sibling)
544 sibling.FixSize (); /* sibling is already black, so no need to set it */
545
546 new_root.IsBlack = parent_was_black;
547 node_reparent (curpos == 2 ? null : path [curpos-4], parent, parent_size, new_root);
548 }
549
550 // Pre-condition: sibling is red (=> parent, sibling.left and sibling.right are black)
551 int ensure_sibling_black (int curpos, List<Node> path)
552 {
553 Node current = path [curpos];
554 Node sibling = path [curpos-1];
555 Node parent = path [curpos-2];
556
557 bool current_on_left;
558 uint parent_size = parent.Size;
559
560 if (parent.right == sibling) {
561 parent.right = sibling.left; sibling.left = parent;
562 current_on_left = true;
563 } else {
564 parent.left = sibling.right; sibling.right = parent;
565 current_on_left = false;
566 }
567
568 parent.FixSize (); parent.IsBlack = false;
569
570 sibling.IsBlack = true;
571 node_reparent (curpos == 2 ? null : path [curpos-4], parent, parent_size, sibling);
572
573 // accomodate the rotation
574 if (curpos+1 == path.Count) {
575 path.Add (null);
576 path.Add (null);
577 }
578
579 path [curpos-2] = sibling;
580 path [curpos-1] = current_on_left ? sibling.right : sibling.left;
581 path [curpos] = parent;
582 path [curpos+1] = current_on_left ? parent.right : parent.left;
583 path [curpos+2] = current;
584
585 return curpos + 2;
586 }
587
588 void node_reparent (Node orig_parent, Node orig, uint orig_size, Node updated)
589 {
590 if (updated != null && updated.FixSize () != orig_size)
591 throw new SystemException ("Internal error: rotation");
592
593 if (orig == root)
594 root = updated;
595 else if (orig == orig_parent.left)
596 orig_parent.left = updated;
597 else if (orig == orig_parent.right)
598 orig_parent.right = updated;
599 else
600 throw new SystemException ("Internal error: path error");
601 }
602
603 // Pre-condition: current != null
604 static Node right_most (Node current, Node sibling, List<Node> path)
605 {
606 for (;;) {
607 path.Add (sibling);
608 path.Add (current);
609 if (current.right == null)
610 return current;
611 sibling = current.left;
612 current = current.right;
613 }
614 }
615
616 [Serializable]
617 public struct NodeEnumerator : IEnumerator, IEnumerator<Node> {
618 RBTree tree;
619 uint version;
620
621 Stack<Node> pennants, init_pennants;
622
623 internal NodeEnumerator (RBTree tree)
624 : this ()
625 {
626 this.tree = tree;
627 version = tree.version;
628 }
629
630 internal NodeEnumerator (RBTree tree, Stack<Node> init_pennants)
631 : this (tree)
632 {
633 this.init_pennants = init_pennants;
634 }
635
636 public void Reset ()
637 {
638 check_version ();
639 pennants = null;
640 }
641
642 public Node Current {
643 get { return pennants.Peek (); }
644 }
645
646 object IEnumerator.Current {
647 get {
648 check_current ();
649 return Current;
650 }
651 }
652
653 public bool MoveNext ()
654 {
655 check_version ();
656
657 Node next;
658 if (pennants == null) {
659 if (tree.root == null)
660 return false;
661 if (init_pennants != null) {
662 pennants = init_pennants;
663 init_pennants = null;
664 return pennants.Count != 0;
665 }
666 pennants = new Stack<Node> ();
667 next = tree.root;
668 } else {
669 if (pennants.Count == 0)
670 return false;
671 Node current = pennants.Pop ();
672 next = current.right;
673 }
674 for (; next != null; next = next.left)
675 pennants.Push (next);
676
677 return pennants.Count != 0;
678 }
679
680 public void Dispose ()
681 {
682 tree = null;
683 pennants = null;
684 }
685
686 void check_version ()
687 {
688 if (tree == null)
689 throw new ObjectDisposedException ("enumerator");
690 if (version != tree.version)
691 throw new InvalidOperationException ("tree modified");
692 }
693
694 internal void check_current ()
695 {
696 check_version ();
697 if (pennants == null)
698 throw new InvalidOperationException ("state invalid before the first MoveNext()");
699 }
700 }
701 }
702 }
703
704 #if TEST
705 namespace Mono.ValidationTest {
706 using System.Collections.Generic;
707
708 internal class TreeSet<T> : IEnumerable<T>, IEnumerable
709 {
710 public class Node : RBTree.Node {
711 public T value;
712
713 public Node (T v)
714 {
715 value = v;
716 }
717
718 public override void SwapValue (RBTree.Node other)
719 {
720 Node o = (Node) other;
721 T v = value;
722 value = o.value;
723 o.value = v;
724 }
725
726 public override void Dump (string indent)
727 {
728 Console.WriteLine ("{0}{1} {2}({3})", indent, value, IsBlack ? "*" : "", Size);
729 if (left != null)
730 left.Dump (indent + " /");
731 if (right != null)
732 right.Dump (indent + " \\");
733 }
734 }
735
736 public class NodeHelper : RBTree.INodeHelper<T> {
737 IComparer<T> cmp;
738
739 public int Compare (T value, RBTree.Node node)
740 {
741 return cmp.Compare (value, ((Node) node).value);
742 }
743
744 public RBTree.Node CreateNode (T value)
745 {
746 return new Node (value);
747 }
748
749 private NodeHelper (IComparer<T> cmp)
750 {
751 this.cmp = cmp;
752 }
753 static NodeHelper Default = new NodeHelper (Comparer<T>.Default);
754 public static NodeHelper GetHelper (IComparer<T> cmp)
755 {
756 if (cmp == null || cmp == Comparer<T>.Default)
757 return Default;
758 return new NodeHelper (cmp);
759 }
760 }
761
762 public struct Enumerator : IDisposable, IEnumerator, IEnumerator<T> {
763 RBTree.NodeEnumerator host;
764
765 internal Enumerator (TreeSet<T> tree)
766 {
767 host = new RBTree.NodeEnumerator (tree.tree);
768 }
769
770 void IEnumerator.Reset ()
771 {
772 host.Reset ();
773 }
774
775 public T Current {
776 get { return ((Node) host.Current).value; }
777 }
778
779 object IEnumerator.Current {
780 get { return Current; }
781 }
782
783 public bool MoveNext ()
784 {
785 return host.MoveNext ();
786 }
787
788 public void Dispose ()
789 {
790 host.Dispose ();
791 }
792 }
793
794 RBTree tree;
795
796 public TreeSet () : this (null)
797 {
798 }
799
800 public TreeSet (IComparer<T> cmp)
801 {
802 tree = new RBTree (NodeHelper.GetHelper (cmp));
803 }
804
805 IEnumerator IEnumerable.GetEnumerator ()
806 {
807 return GetEnumerator ();
808 }
809
810 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
811 {
812 return GetEnumerator ();
813 }
814
815 public Enumerator GetEnumerator ()
816 {
817 return new Enumerator (this);
818 }
819
820 // returns true if the value was inserted, false if the value already existed in the tree
821 public bool Insert (T value)
822 {
823 RBTree.Node n = new Node (value);
824 return tree.Intern (value, n) == n;
825 }
826
827 // returns true if the value was removed, false if the value didn't exist in the tree
828 public bool Remove (T value)
829 {
830 return tree.Remove (value) != null;
831 }
832
833 public bool Contains (T value)
834 {
835 return tree.Lookup (value) != null;
836 }
837
838 public T this [int index] {
839 get { return ((Node) tree [index]).value; }
840 }
841
842 public int Count {
843 get { return (int) tree.Count; }
844 }
845
846 public void VerifyInvariants ()
847 {
848 tree.VerifyInvariants ();
849 }
850
851 public void Dump ()
852 {
853 tree.Dump ();
854 }
855 }
856
857 class Test {
858 static void Main (string [] args)
859 {
860 Random r = new Random ();
861 Dictionary<int, int> d = new Dictionary<int, int> ();
862 TreeSet<int> t = new TreeSet<int> ();
863 int iters = args.Length == 0 ? 100000 : Int32.Parse (args [0]);
864 int watermark = 1;
865
866 for (int i = 0; i < iters; ++i) {
867 if (i >= watermark) {
868 watermark += 1 + watermark/4;
869 t.VerifyInvariants ();
870 }
871
872 int n = r.Next ();
873 if (d.ContainsKey (n))
874 continue;
875 d [n] = n;
876
877 try {
878 if (t.Contains (n))
879 throw new Exception ("tree says it has a number it shouldn't");
880 if (!t.Insert (n))
881 throw new Exception ("tree says it has a number it shouldn't");
882 } catch {
883 Console.Error.WriteLine ("Exception while inserting {0} in iteration {1}", n, i);
884 throw;
885 }
886 }
887 t.VerifyInvariants ();
888 if (d.Count != t.Count)
889 throw new Exception ("tree count is wrong?");
890
891 Console.WriteLine ("Tree has {0} elements", t.Count);
892
893 foreach (int n in d.Keys)
894 if (!t.Contains (n))
895 throw new Exception ("tree says it doesn't have a number it should");
896
897 Dictionary<int, int> d1 = new Dictionary<int, int> (d);
898
899 int prev = -1;
900 foreach (int n in t) {
901 if (n < prev)
902 throw new Exception ("iteration out of order");
903 if (!d1.Remove (n))
904 throw new Exception ("tree has a number it shouldn't");
905 prev = n;
906 }
907
908 if (d1.Count != 0)
909 throw new Exception ("tree has numbers it shouldn't");
910
911 for (int i = 0; i < iters; ++i) {
912 int n = r.Next ();
913 if (!d.ContainsKey (n)) {
914 if (t.Contains (n))
915 throw new Exception ("tree says it doesn't have a number it should");
916 } else if (!t.Contains (n)) {
917 throw new Exception ("tree says it has a number it shouldn't");
918 }
919 }
920
921 int count = t.Count;
922 foreach (int n in d.Keys) {
923 if (count <= watermark) {
924 watermark -= watermark/4;
925 t.VerifyInvariants ();
926 }
927 try {
928 if (!t.Remove (n))
929 throw new Exception ("tree says it doesn't have a number it should");
930 --count;
931 if (t.Count != count)
932 throw new Exception ("Remove didn't remove exactly one element");
933 } catch {
934 Console.Error.WriteLine ("While trying to remove {0} from tree of size {1}", n, t.Count);
935 t.Dump ();
936 t.VerifyInvariants ();
937 throw;
938 }
939 if (t.Contains (n))
940 throw new Exception ("tree says it has a number it shouldn't");
941 }
942 t.VerifyInvariants ();
943
944 if (t.Count != 0)
945 throw new Exception ("tree claims to have elements");
946 }
947 }
948 }
949 #endif
950
951 #endif
git-svn mirror of mcs