mcs/class/System/System.Collections.Generic/RBTree.cs

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