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 using System;
  34 using System.Collections;
  35
  36 namespace System.Collections.Generic
  37 {
  38         [Serializable]
  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 void Bound<T> (T key, ref Node lower, ref Node upper)
 225                 {
 226                         INodeHelper<T> hlp = (INodeHelper<T>) this.hlp;
 227                         Node current = root;
 228                         while (current != null) {
 229                                 int c = hlp.Compare (key, current);
 230                                 if (c <= 0)
 231                                         upper = current;
 232                                 if (c >= 0)
 233                                         lower = current;
 234                                 if (c == 0)
 235                                         break;
 236                                 current = c < 0 ? current.left : current.right;
 237                         }
 238                 }
 239
 240                 public int Count {
 241                         get { return root == null ? 0 : (int) root.Size; }
 242                 }
 243
 244                 public Node this [int index] {
 245                         get {
 246                                 if (index < 0 || index >= Count)
 247                                         throw new IndexOutOfRangeException ("index");
 248
 249                                 Node current = root;
 250                                 while (current != null) {
 251                                         int left_size = current.left == null ? 0 : (int) current.left.Size;
 252                                         if (index == left_size)
 253                                                 return current;
 254                                         if (index < left_size) {
 255                                                 current = current.left;
 256                                         } else {
 257                                                 index -= left_size + 1;
 258                                                 current = current.right;
 259                                         }
 260                                 }
 261                                 throw new SystemException ("Internal Error: index calculation");
 262                         }
 263                 }
 264
 265                 public NodeEnumerator GetEnumerator ()
 266                 {
 267                         return new NodeEnumerator (this);
 268                 }
 269
 270                 // Get an enumerator that starts at 'key' or the next higher element in the tree
 271                 public NodeEnumerator GetSuffixEnumerator<T> (T key)
 272                 {
 273                         var pennants = new Stack<Node> ();
 274                         INodeHelper<T> hlp = (INodeHelper<T>) this.hlp;
 275                         Node current = root;
 276                         while (current != null) {
 277                                 int c = hlp.Compare (key, current);
 278                                 if (c <= 0)
 279                                         pennants.Push (current);
 280                                 if (c == 0)
 281                                         break;
 282                                 current = c < 0 ? current.left : current.right;
 283                         }
 284                         return new NodeEnumerator (this, pennants);
 285                 }
 286
 287                 IEnumerator<Node> IEnumerable<Node>.GetEnumerator ()
 288                 {
 289                         return GetEnumerator ();
 290                 }
 291
 292                 IEnumerator IEnumerable.GetEnumerator ()
 293                 {
 294                         return GetEnumerator ();
 295                 }
 296
 297 #if TEST
 298                 public void VerifyInvariants ()
 299                 {
 300                         if (root != null) {
 301                                 if (!root.IsBlack)
 302                                         throw new SystemException ("Internal Error: root is not black");
 303                                 root.VerifyInvariants ();
 304                         }
 305                 }
 306
 307                 public void Dump ()
 308                 {
 309                         if (root != null)
 310                                 root.Dump ("");
 311                 }
 312 #endif
 313
 314                 // Pre-condition: root != null
 315                 int find_key<T> (T key, List<Node> path)
 316                 {
 317                         INodeHelper<T> hlp = (INodeHelper<T>) this.hlp;
 318                         int c = 0;
 319                         Node sibling = null;
 320                         Node current = root;
 321
 322                         if (path != null)
 323                                 path.Add (root);
 324
 325                         while (current != null) {
 326                                 c = hlp.Compare (key, current);
 327                                 if (c == 0)
 328                                         return c;
 329
 330                                 if (c < 0) {
 331                                         sibling = current.right;
 332                                         current = current.left;
 333                                 } else {
 334                                         sibling = current.left;
 335                                         current = current.right;
 336                                 }
 337
 338                                 if (path != null) {
 339                                         path.Add (sibling);
 340                                         path.Add (current);
 341                                 }
 342                         }
 343
 344                         return c;
 345                 }
 346
 347                 Node do_insert (int in_tree_cmp, Node current, List<Node> path)
 348                 {
 349                         path [path.Count - 1] = current;
 350                         Node parent = path [path.Count - 3];
 351
 352                         if (in_tree_cmp < 0)
 353                                 parent.left = current;
 354                         else
 355                                 parent.right = current;
 356                         for (int i = 0; i < path.Count - 2; i += 2)
 357                                 ++ path [i].Size;
 358
 359                         if (!parent.IsBlack)
 360                                 rebalance_insert (path);
 361
 362                         if (!root.IsBlack)
 363                                 throw new SystemException ("Internal error: root is not black");
 364
 365                         ++version;
 366                         return current;
 367                 }
 368
 369                 Node do_remove (List<Node> path)
 370                 {
 371                         int curpos = path.Count - 1;
 372
 373                         Node current = path [curpos];
 374                         if (current.left != null) {
 375                                 Node pred = right_most (current.left, current.right, path);
 376                                 current.SwapValue (pred);
 377                                 if (pred.left != null) {
 378                                         Node ppred = pred.left;
 379                                         path.Add (null); path.Add (ppred);
 380                                         pred.SwapValue (ppred);
 381                                 }
 382                         } else if (current.right != null) {
 383                                 Node succ = current.right;
 384                                 path.Add (null); path.Add (succ);
 385                                 current.SwapValue (succ);
 386                         }
 387
 388                         curpos = path.Count - 1;
 389                         current = path [curpos];
 390
 391                         if (current.Size != 1)
 392                                 throw new SystemException ("Internal Error: red-black violation somewhere");
 393
 394                         // remove it from our data structures
 395                         path [curpos] = null;
 396                         node_reparent (curpos == 0 ? null : path [curpos-2], current, 0, null);
 397
 398                         for (int i = 0; i < path.Count - 2; i += 2)
 399                                 -- path [i].Size;
 400
 401                         if (current.IsBlack) {
 402                                 current.IsBlack = false;
 403                                 if (curpos != 0)
 404                                         rebalance_delete (path);
 405                         }
 406
 407                         if (root != null && !root.IsBlack)
 408                                 throw new SystemException ("Internal Error: root is not black");
 409
 410                         ++version;
 411                         return current;
 412                 }
 413
 414                 // Pre-condition: current is red
 415                 void rebalance_insert (List<Node> path)
 416                 {
 417                         int curpos = path.Count - 1;
 418                         do {
 419                                 // parent == curpos-2, uncle == curpos-3, grandpa == curpos-4
 420                                 if (path [curpos-3] == null || path [curpos-3].IsBlack) {
 421                                         rebalance_insert__rotate_final (curpos, path);
 422                                         return;
 423                                 }
 424
 425                                 path [curpos-2].IsBlack = path [curpos-3].IsBlack = true;
 426
 427                                 curpos -= 4; // move to the grandpa
 428
 429                                 if (curpos == 0) // => current == root
 430                                         return;
 431                                 path [curpos].IsBlack = false;
 432                         } while (!path [curpos-2].IsBlack);
 433                 }
 434
 435                 // Pre-condition: current is black
 436                 void rebalance_delete (List<Node> path)
 437                 {
 438                         int curpos = path.Count - 1;
 439                         do {
 440                                 Node sibling = path [curpos-1];
 441                                 // current is black => sibling != null
 442                                 if (!sibling.IsBlack) {
 443                                         // current is black && sibling is red
 444                                         // => both sibling.left and sibling.right are black, and are not null
 445                                         curpos = ensure_sibling_black (curpos, path);
 446                                         // one of the nephews became the new sibling -- in either case, sibling != null
 447                                         sibling = path [curpos-1];
 448                                 }
 449
 450                                 if ((sibling.left != null && !sibling.left.IsBlack) ||
 451                                     (sibling.right != null && !sibling.right.IsBlack)) {
 452                                         rebalance_delete__rotate_final (curpos, path);
 453                                         return;
 454                                 }
 455
 456                                 sibling.IsBlack = false;
 457
 458                                 curpos -= 2; // move to the parent
 459
 460                                 if (curpos == 0)
 461                                         return;
 462                         } while (path [curpos].IsBlack);
 463                         path [curpos].IsBlack = true;
 464                 }
 465
 466                 void rebalance_insert__rotate_final (int curpos, List<Node> path)
 467                 {
 468                         Node current = path [curpos];
 469                         Node parent = path [curpos-2];
 470                         Node grandpa = path [curpos-4];
 471
 472                         uint grandpa_size = grandpa.Size;
 473
 474                         Node new_root;
 475
 476                         bool l1 = parent == grandpa.left;
 477                         bool l2 = current == parent.left;
 478                         if (l1 && l2) {
 479                                 grandpa.left = parent.right; parent.right = grandpa;
 480                                 new_root = parent;
 481                         } else if (l1 && !l2) {
 482                                 grandpa.left = current.right; current.right = grandpa;
 483                                 parent.right = current.left; current.left = parent;
 484                                 new_root = current;
 485                         } else if (!l1 && l2) {
 486                                 grandpa.right = current.left; current.left = grandpa;
 487                                 parent.left = current.right; current.right = parent;
 488                                 new_root = current;
 489                         } else { // (!l1 && !l2)
 490                                 grandpa.right = parent.left; parent.left = grandpa;
 491                                 new_root = parent;
 492                         }
 493
 494                         grandpa.FixSize (); grandpa.IsBlack = false;
 495                         if (new_root != parent)
 496                                 parent.FixSize (); /* parent is red already, so no need to set it */
 497
 498                         new_root.IsBlack = true;
 499                         node_reparent (curpos == 4 ? null : path [curpos-6], grandpa, grandpa_size, new_root);
 500                 }
 501
 502                 // Pre-condition: sibling is black, and one of sibling.left and sibling.right is red
 503                 void rebalance_delete__rotate_final (int curpos, List<Node> path)
 504                 {
 505                         //Node current = path [curpos];
 506                         Node sibling = path [curpos-1];
 507                         Node parent = path [curpos-2];
 508
 509                         uint parent_size = parent.Size;
 510                         bool parent_was_black = parent.IsBlack;
 511
 512                         Node new_root;
 513                         if (parent.right == sibling) {
 514                                 // if far nephew is black
 515                                 if (sibling.right == null || sibling.right.IsBlack) {
 516                                         // => near nephew is red, move it up
 517                                         Node nephew = sibling.left;
 518                                         parent.right = nephew.left; nephew.left = parent;
 519                                         sibling.left = nephew.right; nephew.right = sibling;
 520                                         new_root = nephew;
 521                                 } else {
 522                                         parent.right = sibling.left; sibling.left = parent;
 523                                         sibling.right.IsBlack = true;
 524                                         new_root = sibling;
 525                                 }
 526                         } else {
 527                                 // if far nephew is black
 528                                 if (sibling.left == null || sibling.left.IsBlack) {
 529                                         // => near nephew is red, move it up
 530                                         Node nephew = sibling.right;
 531                                         parent.left = nephew.right; nephew.right = parent;
 532                                         sibling.right = nephew.left; nephew.left = sibling;
 533                                         new_root = nephew;
 534                                 } else {
 535                                         parent.left = sibling.right; sibling.right = parent;
 536                                         sibling.left.IsBlack = true;
 537                                         new_root = sibling;
 538                                 }
 539                         }
 540
 541                         parent.FixSize (); parent.IsBlack = true;
 542                         if (new_root != sibling)
 543                                 sibling.FixSize (); /* sibling is already black, so no need to set it */
 544
 545                         new_root.IsBlack = parent_was_black;
 546                         node_reparent (curpos == 2 ? null : path [curpos-4], parent, parent_size, new_root);
 547                 }
 548
 549                 // Pre-condition: sibling is red (=> parent, sibling.left and sibling.right are black)
 550                 int ensure_sibling_black (int curpos, List<Node> path)
 551                 {
 552                         Node current = path [curpos];
 553                         Node sibling = path [curpos-1];
 554                         Node parent = path [curpos-2];
 555
 556                         bool current_on_left;
 557                         uint parent_size = parent.Size;
 558
 559                         if (parent.right == sibling) {
 560                                 parent.right = sibling.left; sibling.left = parent;
 561                                 current_on_left = true;
 562                         } else {
 563                                 parent.left = sibling.right; sibling.right = parent;
 564                                 current_on_left = false;
 565                         }
 566
 567                         parent.FixSize (); parent.IsBlack = false;
 568
 569                         sibling.IsBlack = true;
 570                         node_reparent (curpos == 2 ? null : path [curpos-4], parent, parent_size, sibling);
 571
 572                         // accomodate the rotation
 573                         if (curpos+1 == path.Count) {
 574                                 path.Add (null);
 575                                 path.Add (null);
 576                         }
 577
 578                         path [curpos-2] = sibling;
 579                         path [curpos-1] = current_on_left ? sibling.right : sibling.left;
 580                         path [curpos] = parent;
 581                         path [curpos+1] = current_on_left ? parent.right : parent.left;
 582                         path [curpos+2] = current;
 583
 584                         return curpos + 2;
 585                 }
 586
 587                 void node_reparent (Node orig_parent, Node orig, uint orig_size, Node updated)
 588                 {
 589                         if (updated != null && updated.FixSize () != orig_size)
 590                                 throw new SystemException ("Internal error: rotation");
 591
 592                         if (orig == root)
 593                                 root = updated;
 594                         else if (orig == orig_parent.left)
 595                                 orig_parent.left = updated;
 596                         else if (orig == orig_parent.right)
 597                                 orig_parent.right = updated;
 598                         else
 599                                 throw new SystemException ("Internal error: path error");
 600                 }
 601
 602                 // Pre-condition: current != null
 603                 static Node right_most (Node current, Node sibling, List<Node> path)
 604                 {
 605                         for (;;) {
 606                                 path.Add (sibling);
 607                                 path.Add (current);
 608                                 if (current.right == null)
 609                                         return current;
 610                                 sibling = current.left;
 611                                 current = current.right;
 612                         }
 613                 }
 614
 615                 [Serializable]
 616                 public struct NodeEnumerator : IEnumerator, IEnumerator<Node> {
 617                         RBTree tree;
 618                         uint version;
 619
 620                         Stack<Node> pennants, init_pennants;
 621
 622                         internal NodeEnumerator (RBTree tree)
 623                                 : this ()
 624                         {
 625                                 this.tree = tree;
 626                                 version = tree.version;
 627                         }
 628
 629                         internal NodeEnumerator (RBTree tree, Stack<Node> init_pennants)
 630                                 : this (tree)
 631                         {
 632                                 this.init_pennants = init_pennants;
 633                         }
 634
 635                         public void Reset ()
 636                         {
 637                                 check_version ();
 638                                 pennants = null;
 639                         }
 640
 641                         public Node Current {
 642                                 get { return pennants.Peek (); }
 643                         }
 644
 645                         object IEnumerator.Current {
 646                                 get {
 647                                         check_current ();
 648                                         return Current;
 649                                 }
 650                         }
 651
 652                         public bool MoveNext ()
 653                         {
 654                                 check_version ();
 655
 656                                 Node next;
 657                                 if (pennants == null) {
 658                                         if (tree.root == null)
 659                                                 return false;
 660                                         if (init_pennants != null) {
 661                                                 pennants = init_pennants;
 662                                                 init_pennants = null;
 663                                                 return pennants.Count != 0;
 664                                         }
 665                                         pennants = new Stack<Node> ();
 666                                         next = tree.root;
 667                                 } else {
 668                                         if (pennants.Count == 0)
 669                                                 return false;
 670                                         Node current = pennants.Pop ();
 671                                         next = current.right;
 672                                 }
 673                                 for (; next != null; next = next.left)
 674                                         pennants.Push (next);
 675
 676                                 return pennants.Count != 0;
 677                         }
 678
 679                         public void Dispose ()
 680                         {
 681                                 tree = null;
 682                                 pennants = null;
 683                         }
 684
 685                         void check_version ()
 686                         {
 687                                 if (tree == null)
 688                                         throw new ObjectDisposedException ("enumerator");
 689                                 if (version != tree.version)
 690                                         throw new InvalidOperationException ("tree modified");
 691                         }
 692
 693                         internal void check_current ()
 694                         {
 695                                 check_version ();
 696                                 if (pennants == null)
 697                                         throw new InvalidOperationException ("state invalid before the first MoveNext()");
 698                         }
 699                 }
 700         }
 701 }
 702
 703 #if TEST
 704 namespace Mono.ValidationTest {
 705         using System.Collections.Generic;
 706
 707         internal class TreeSet<T> : IEnumerable<T>, IEnumerable
 708         {
 709                 public class Node : RBTree.Node {
 710                         public T value;
 711
 712                         public Node (T v)
 713                         {
 714                                 value = v;
 715                         }
 716
 717                         public override void SwapValue (RBTree.Node other)
 718                         {
 719                                 Node o = (Node) other;
 720                                 T v = value;
 721                                 value = o.value;
 722                                 o.value = v;
 723                         }
 724
 725                         public override void Dump (string indent)
 726                         {
 727                                 Console.WriteLine ("{0}{1} {2}({3})", indent, value, IsBlack ? "*" : "", Size);
 728                                 if (left != null)
 729                                         left.Dump (indent + "  /");
 730                                 if (right != null)
 731                                         right.Dump (indent + "  \\");
 732                         }
 733                 }
 734
 735                 public class NodeHelper : RBTree.INodeHelper<T> {
 736                         IComparer<T> cmp;
 737
 738                         public int Compare (T value, RBTree.Node node)
 739                         {
 740                                 return cmp.Compare (value, ((Node) node).value);
 741                         }
 742
 743                         public RBTree.Node CreateNode (T value)
 744                         {
 745                                 return new Node (value);
 746                         }
 747
 748                         private NodeHelper (IComparer<T> cmp)
 749                         {
 750                                 this.cmp = cmp;
 751                         }
 752                         static NodeHelper Default = new NodeHelper (Comparer<T>.Default);
 753                         public static NodeHelper GetHelper (IComparer<T> cmp)
 754                         {
 755                                 if (cmp == null || cmp == Comparer<T>.Default)
 756                                         return Default;
 757                                 return new NodeHelper (cmp);
 758                         }
 759                 }
 760
 761                 public struct Enumerator : IDisposable, IEnumerator, IEnumerator<T> {
 762                         RBTree.NodeEnumerator host;
 763
 764                         internal Enumerator (TreeSet<T> tree)
 765                         {
 766                                 host = new RBTree.NodeEnumerator (tree.tree);
 767                         }
 768
 769                         void IEnumerator.Reset ()
 770                         {
 771                                 host.Reset ();
 772                         }
 773
 774                         public T Current {
 775                                 get { return ((Node) host.Current).value; }
 776                         }
 777
 778                         object IEnumerator.Current {
 779                                 get { return Current; }
 780                         }
 781
 782                         public bool MoveNext ()
 783                         {
 784                                 return host.MoveNext ();
 785                         }
 786
 787                         public void Dispose ()
 788                         {
 789                                 host.Dispose ();
 790                         }
 791                 }
 792
 793                 RBTree tree;
 794
 795                 public TreeSet () : this (null)
 796                 {
 797                 }
 798
 799                 public TreeSet (IComparer<T> cmp)
 800                 {
 801                         tree = new RBTree (NodeHelper.GetHelper (cmp));
 802                 }
 803
 804                 IEnumerator IEnumerable.GetEnumerator ()
 805                 {
 806                         return GetEnumerator ();
 807                 }
 808
 809                 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 810                 {
 811                         return GetEnumerator ();
 812                 }
 813
 814                 public Enumerator GetEnumerator ()
 815                 {
 816                         return new Enumerator (this);
 817                 }
 818
 819                 // returns true if the value was inserted, false if the value already existed in the tree
 820                 public bool Insert (T value)
 821                 {
 822                         RBTree.Node n = new Node (value);
 823                         return tree.Intern (value, n) == n;
 824                 }
 825
 826                 // returns true if the value was removed, false if the value didn't exist in the tree
 827                 public bool Remove (T value)
 828                 {
 829                         return tree.Remove (value) != null;
 830                 }
 831
 832                 public bool Contains (T value)
 833                 {
 834                         return tree.Lookup (value) != null;
 835                 }
 836
 837                 public T this [int index] {
 838                         get { return ((Node) tree [index]).value; }
 839                 }
 840
 841                 public int Count {
 842                         get { return (int) tree.Count; }
 843                 }
 844
 845                 public void VerifyInvariants ()
 846                 {
 847                         tree.VerifyInvariants ();
 848                 }
 849
 850                 public void Dump ()
 851                 {
 852                         tree.Dump ();
 853                 }
 854         }
 855
 856         class Test {
 857                 static void Main (string [] args)
 858                 {
 859                         Random r = new Random ();
 860                         Dictionary<int, int> d = new Dictionary<int, int> ();
 861                         TreeSet<int> t = new TreeSet<int> ();
 862                         int iters = args.Length == 0 ? 100000 : Int32.Parse (args [0]);
 863                         int watermark = 1;
 864
 865                         for (int i = 0; i < iters; ++i) {
 866                                 if (i >= watermark) {
 867                                         watermark += 1 + watermark/4;
 868                                         t.VerifyInvariants ();
 869                                 }
 870
 871                                 int n = r.Next ();
 872                                 if (d.ContainsKey (n))
 873                                         continue;
 874                                 d [n] = n;
 875
 876                                 try {
 877                                         if (t.Contains (n))
 878                                                 throw new Exception ("tree says it has a number it shouldn't");
 879                                         if (!t.Insert (n))
 880                                                 throw new Exception ("tree says it has a number it shouldn't");
 881                                 } catch {
 882                                         Console.Error.WriteLine ("Exception while inserting {0} in iteration {1}", n, i);
 883                                         throw;
 884                                 }
 885                         }
 886                         t.VerifyInvariants ();
 887                         if (d.Count != t.Count)
 888                                 throw new Exception ("tree count is wrong?");
 889
 890                         Console.WriteLine ("Tree has {0} elements", t.Count);
 891
 892                         foreach (int n in d.Keys)
 893                                 if (!t.Contains (n))
 894                                         throw new Exception ("tree says it doesn't have a number it should");
 895
 896                         Dictionary<int, int> d1 = new Dictionary<int, int> (d);
 897
 898                         int prev = -1;
 899                         foreach (int n in t) {
 900                                 if (n < prev)
 901                                         throw new Exception ("iteration out of order");
 902                                 if (!d1.Remove (n))
 903                                         throw new Exception ("tree has a number it shouldn't");
 904                                 prev = n;
 905                         }
 906
 907                         if (d1.Count != 0)
 908                                 throw new Exception ("tree has numbers it shouldn't");
 909
 910                         for (int i = 0; i < iters; ++i) {
 911                                 int n = r.Next ();
 912                                 if (!d.ContainsKey (n)) {
 913                                         if (t.Contains (n))
 914                                                 throw new Exception ("tree says it doesn't have a number it should");
 915                                 } else if (!t.Contains (n)) {
 916                                         throw new Exception ("tree says it has a number it shouldn't");
 917                                 }
 918                         }
 919
 920                         int count = t.Count;
 921                         foreach (int n in d.Keys) {
 922                                 if (count <= watermark) {
 923                                         watermark -= watermark/4;
 924                                         t.VerifyInvariants ();
 925                                 }
 926                                 try {
 927                                         if (!t.Remove (n))
 928                                                 throw new Exception ("tree says it doesn't have a number it should");
 929                                         --count;
 930                                         if (t.Count != count)
 931                                                 throw new Exception ("Remove didn't remove exactly one element");
 932                                 } catch {
 933                                         Console.Error.WriteLine ("While trying to remove {0} from tree of size {1}", n, t.Count);
 934                                         t.Dump ();
 935                                         t.VerifyInvariants ();
 936                                         throw;
 937                                 }
 938                                 if (t.Contains (n))
 939                                         throw new Exception ("tree says it has a number it shouldn't");
 940                         }
 941                         t.VerifyInvariants ();
 942
 943                         if (t.Count != 0)
 944                                 throw new Exception ("tree claims to have elements");
 945                 }
 946         }
 947 }
 948 #endif
 949