1 // =================================
   2 // Copyright (c) 2022 Seppo Laakko
   3 // Distributed under the MIT license
   4 // =================================
   5 
   6 using System;
   7 using System.Concepts;
   8 
   9 namespace System.Collections
  10 {
  11     public class RedBlackTreeNodeBase
  12     {
  13         public enum Color { red, black }
  14         
  15         public nothrow RedBlackTreeNodeBase(RedBlackTreeNodeBase* parent_) : color(Color.black), parent(parent_), left(null), right(null)
  16         {
  17         }
  18         public virtual ~RedBlackTreeNodeBase()
  19         {
  20             if (left != null && left != this)
  21             {
  22                 delete left;
  23             }
  24             if (right != null && right != this)
  25             {
  26                 delete right;
  27             }
  28         }
  29         public inline nothrow Color GetColor() const
  30         {
  31             return color;
  32         }
  33         public inline nothrow void SetColor(Color color_)
  34         {
  35             color = color_;
  36         }
  37         public inline nothrow RedBlackTreeNodeBase* Parent() const
  38         {
  39             return parent;
  40         }
  41         public inline nothrow RedBlackTreeNodeBase*& ParentRef()
  42         {
  43             return parent;
  44         }
  45         public inline nothrow void SetParent(RedBlackTreeNodeBase* parent_)
  46         {
  47             parent = parent_;
  48         }
  49         public inline nothrow RedBlackTreeNodeBase* Left() const
  50         {
  51             return left;
  52         }
  53         public inline nothrow RedBlackTreeNodeBase*& LeftRef()
  54         {
  55             return left;
  56         }
  57         public inline nothrow void SetLeft(RedBlackTreeNodeBase* left_)
  58         {
  59             left = left_;
  60         }
  61         public inline nothrow RedBlackTreeNodeBase* Right() const
  62         {
  63             return right;
  64         }
  65         public inline nothrow RedBlackTreeNodeBase*& RightRef()
  66         {
  67             return right;
  68         }
  69         public inline nothrow void SetRight(RedBlackTreeNodeBase* right_)
  70         {
  71             right = right_;
  72         }
  73         public inline nothrow bool IsHeaderNode() const
  74         {
  75             return color == Color.red && parent != null && parent->parent == this;
  76         }
  77         public static inline nothrow RedBlackTreeNodeBase* Min(RedBlackTreeNodeBase* n)
  78         {
  79             if (n == null)
  80             {
  81                 ThrowInvalidParameterException();
  82             }
  83             while (n->left != null)
  84             {
  85                 n = n->left;
  86             }
  87             return n;
  88         }
  89         public static inline nothrow RedBlackTreeNodeBase* Max(RedBlackTreeNodeBase* n)
  90         {
  91             if (n == null)
  92             {
  93                 ThrowInvalidParameterException();
  94             }
  95             while (n->right != null)
  96             {
  97                 n = n->right;
  98             }
  99             return n;
 100         }
 101         public static inline nothrow RedBlackTreeNodeBase* Prev(RedBlackTreeNodeBase* n)
 102         {
 103             if (n == null)
 104             {
 105                 ThrowInvalidParameterException();
 106             }
 107             if (n->IsHeaderNode())
 108             {
 109                 return n->right;
 110             }
 111             else if (n->left != null)
 112             {
 113                 return Max(n->left);
 114             }
 115             else
 116             {
 117                 RedBlackTreeNodeBase* u = n->parent;
 118                 while (n == u->left)
 119                 {
 120                     n = u;
 121                     u = u->parent;
 122                 }
 123                 return u;
 124             }
 125         }
 126         public static inline nothrow RedBlackTreeNodeBase* Next(RedBlackTreeNodeBase* n)
 127         {
 128             if (n == null)
 129             {
 130                 ThrowInvalidParameterException();
 131             }
 132             if (n->right != null)
 133             {
 134                 return Min(n->right);
 135             }
 136             else
 137             {
 138                 RedBlackTreeNodeBase* u = n->parent;
 139                 while (n == u->right)
 140                 {
 141                     n = u;
 142                     u = u->parent;
 143                 }
 144                 if (n->right != u)
 145                 {
 146                     return u;
 147                 }
 148                 return n;
 149             }
 150         }
 151         /*
 152             REBALANCE-AFTER-INSERT:
 153 
 154                  g            g
 155                 /  \         /  \
 156                p    u   OR  u    p
 157               /                   \
 158              n                     n
 159 
 160         */
 161         public static nothrow void RebalanceAfterInsert(RedBlackTreeNodeBase* n, RedBlackTreeNodeBase*& root)
 162         {
 163             if (n == null)
 164             {
 165                 ThrowInvalidParameterException();
 166             }
 167             n->color = Color.red;
 168             while (n != root && n->parent->color == Color.red)
 169             {
 170                 if (n->parent == n->parent->parent->left)
 171                 {
 172                     RedBlackTreeNodeBase* u = n->parent->parent->right;
 173                     if (u != null && u->color == Color.red)
 174                     {
 175                         n->parent->color = Color.black;
 176                         u->color = Color.black;
 177                         n->parent->parent->color = Color.red;
 178                         n = n->parent->parent;
 179                     }
 180                     else
 181                     {
 182                         if (n == n->parent->right)
 183                         {
 184                             n = n->parent;
 185                             RotateLeft(n, root);
 186                         }
 187                         n->parent->color = Color.black;
 188                         n->parent->parent->color = Color.red;
 189                         RotateRight(n->parent->parent, root);
 190                     }
 191                 }
 192                 else
 193                 {
 194                     RedBlackTreeNodeBase* u = n->parent->parent->left;
 195                     if (u != null && u->color == Color.red)
 196                     {
 197                         n->parent->color = Color.black;
 198                         u->color = Color.black;
 199                         n->parent->parent->color = Color.red;
 200                         n = n->parent->parent;
 201                     }
 202                     else
 203                     {
 204                         if (n == n->parent->left)
 205                         {
 206                             n = n->parent;
 207                             RotateRight(n, root);
 208                         }
 209                         n->parent->color = Color.black;
 210                         n->parent->parent->color = Color.red;
 211                         RotateLeft(n->parent->parent, root);
 212                     }
 213                 }
 214             }
 215             root->color = Color.black;
 216         }
 217         /*
 218             REBALANCE-FOR-REMOVE:
 219         */
 220         public static nothrow RedBlackTreeNodeBase* RebalanceForRemove(RedBlackTreeNodeBase* z, RedBlackTreeNodeBase*& root, RedBlackTreeNodeBase*& leftmost, RedBlackTreeNodeBase*& rightmost)
 221         {
 222             if (z == null)
 223             {
 224                 ThrowInvalidParameterException();
 225             }
 226             RedBlackTreeNodeBase* y = z;
 227             RedBlackTreeNodeBase* x = null;
 228             RedBlackTreeNodeBase* p = null;
 229             if (y->left == null)
 230             {
 231                 x = y->right;
 232             }
 233             else
 234             {
 235                 if (y->right == null)
 236                 {
 237                     x = y->left;
 238                 }
 239                 else
 240                 {
 241                     y = y->right;
 242                     while (y->left != null)
 243                     {
 244                         y = y->left;
 245                     }
 246                     x = y->right;
 247                 }
 248             }
 249             if (y != z)
 250             {
 251                 z->left->parent = y;
 252                 y->left = z->left;
 253                 if (y != z->right)
 254                 {
 255                     p = y->parent;
 256                     if (x != null)
 257                     {
 258                         x->parent = y->parent;
 259                     }
 260                     y->parent->left = x;
 261                     y->right = z->right;
 262                     z->right->parent = y;
 263                 }
 264                 else
 265                 {
 266                     p = y;
 267                 }
 268                 if (root == z)
 269                 {
 270                     root = y;
 271                 }
 272                 else if (z->parent->left == z)
 273                 {
 274                     z->parent->left = y;
 275                 }
 276                 else
 277                 {
 278                     z->parent->right = y;
 279                 }
 280                 y->parent = z->parent;
 281                 Color c = y->color;
 282                 y->color = z->color;
 283                 z->color = c;
 284                 y = z;
 285                 // y now points to node to be actually deleted
 286             }
 287             else
 288             {
 289                 p = y->parent;
 290                 if (x != null)
 291                 {
 292                     x->parent = y->parent;
 293                 }
 294                 if (root == z)
 295                 {
 296                     root = x;
 297                 }
 298                 else
 299                 {
 300                     if (z->parent->left == z)
 301                     {
 302                         z->parent->left = x;
 303                     }
 304                     else
 305                     {
 306                         z->parent->right = x;
 307                     }
 308                 }
 309                 if (leftmost == z)
 310                 {
 311                     if (z->right == null)
 312                     {
 313                         leftmost = z->parent;
 314                     }
 315                     else
 316                     {
 317                         leftmost = Min(x);
 318                     }
 319                 }
 320                 if (rightmost == z)
 321                 {
 322                     if (z->left == null)
 323                     {
 324                         rightmost = z->parent;
 325                     }
 326                     else
 327                     {
 328                         rightmost = Max(x);
 329                     }
 330                 }
 331             }
 332             if (y->color != Color.red)
 333             {
 334                 while (x != root && (x == null || x->color == Color.black))
 335                 {
 336                     if (x == p->left)
 337                     {
 338                         RedBlackTreeNodeBase* w = p->right;
 339                         if (w->color == Color.red)
 340                         {
 341                             w->color = Color.black;
 342                             p->color = Color.red;
 343                             RotateLeft(p, root);
 344                             w = p->right;
 345                         }
 346                         if ((w->left == null || w->left->color == Color.black) && 
 347                             (w->right == null || w->right->color == Color.black))
 348                         {
 349                             w->color = Color.red;
 350                             x = p;
 351                             p = p->parent;
 352                         }
 353                         else
 354                         {
 355                             if (w->right == null || w->right->color == Color.black)
 356                             {
 357                                 if (w->left != null)
 358                                 {
 359                                     w->left->color = Color.black;
 360                                 }
 361                                 w->color = Color.red;
 362                                 RotateRight(w, root);
 363                                 w = p->right;
 364                             }
 365                             w->color = p->color;
 366                             p->color = Color.black;
 367                             if (w->right != null)
 368                             {
 369                                 w->right->color = Color.black;
 370                             }
 371                             RotateLeft(p, root);
 372                             break;
 373                         }
 374                     }
 375                     else
 376                     {
 377                         RedBlackTreeNodeBase* w = p->left;
 378                         if (w->color == Color.red)
 379                         {
 380                             w->color = Color.black;
 381                             p->color = Color.red;
 382                             RotateRight(p, root);
 383                             w = p->left;
 384                         }
 385                         if ((w->right == null || w->right->color == Color.black) && 
 386                             (w->left == null || w->left->color == Color.black))
 387                         {
 388                             w->color = Color.red;
 389                             x = p;
 390                             p = p->parent;
 391                         }
 392                         else
 393                         {
 394                             if (w->left == null || w->left->color == Color.black)
 395                             {
 396                                 if (w->right != null)
 397                                 {
 398                                     w->right->color = Color.black;
 399                                 }
 400                                 w->color = Color.red;
 401                                 RotateLeft(w, root);
 402                                 w = p->left;
 403                             }
 404                             w->color = p->color;
 405                             p->color = Color.black;
 406                             if (w->left != null)
 407                             {
 408                                 w->left->color = Color.black;
 409                             }
 410                             RotateRight(p, root);
 411                             break;
 412                         }
 413                     }
 414                 }
 415             }
 416             if (x != null)
 417             {
 418                 x->color = Color.black;
 419             }
 420             return y;
 421         }
 422         /*  ROTATE LEFT:
 423                   n              u
 424                  / \            / \
 425                 a   u    =>    n   c
 426                    / \        / \
 427                   b   c      a   b
 428         */
 429         private static inline nothrow void RotateLeft(RedBlackTreeNodeBase* n, RedBlackTreeNodeBase*& root)
 430         {
 431             if (n == null)
 432             {
 433                 ThrowInvalidParameterException();
 434             }
 435             RedBlackTreeNodeBase* u = n->right;
 436             if (u == null)
 437             {
 438                 ThrowInvalidParameterException();
 439             }
 440             n->right = u->left;
 441             if (u->left != null)
 442             {
 443                 u->left->parent = n;
 444             }
 445             u->parent = n->parent;
 446             if (n == root)
 447             {
 448                 root = u;
 449             }
 450             else if (n == n->parent->left)
 451             {
 452                 n->parent->left = u;
 453             }
 454             else
 455             {
 456                 n->parent->right = u;
 457             }
 458             u->left = n;
 459             n->parent = u;
 460         }
 461         /*  ROTATE RIGHT:
 462                 n                u
 463                / \              / \
 464               u   c     =>     a   n
 465              / \                  / \
 466             a   b               b    c
 467         */
 468         private static inline nothrow void RotateRight(RedBlackTreeNodeBase* n, RedBlackTreeNodeBase*& root)
 469         {
 470             if (n == null)
 471             {
 472                 ThrowInvalidParameterException();
 473             }
 474             RedBlackTreeNodeBase* u = n->left;
 475             if (u == null)
 476             {
 477                 ThrowInvalidParameterException();
 478             }
 479             n->left = u->right;
 480             if (u->right != null)
 481             {
 482                 u->right->parent = n;
 483             }
 484             u->parent = n->parent;
 485             if (n == root)
 486             {
 487                 root = u;
 488             }
 489             else if (n == n->parent->right)
 490             {
 491                 n->parent->right = u;
 492             }
 493             else
 494             {
 495                 n->parent->left = u;
 496             }
 497             u->right = n;
 498             n->parent = u;
 499         }
 500         private Color color;
 501         private RedBlackTreeNodeBase* parent;
 502         private RedBlackTreeNodeBase* left;
 503         private RedBlackTreeNodeBase* right;
 504     }
 505 
 506     public class RedBlackTreeNode<T> : RedBlackTreeNodeBase
 507     {
 508         public typedef T ValueType;
 509 
 510         public RedBlackTreeNode(const ValueType& value_, RedBlackTreeNode<T>* parent_) : base(parent_), value(value_)
 511         {
 512         }
 513         public inline nothrow const ValueType& Value() const
 514         {
 515             return value;
 516         }
 517         public inline nothrow ValueType& Value()
 518         {
 519             return value;
 520         }
 521         private ValueType value;
 522     }
 523 
 524     public class RedBlackTreeNodeIterator<T, R, P>
 525     {
 526         public typedef T ValueType;
 527         public typedef R ReferenceType;
 528         public typedef P PointerType;
 529         private typedef RedBlackTreeNodeIterator<ValueType, ReferenceType, PointerType> Self;
 530 
 531         public nothrow RedBlackTreeNodeIterator() : node(null)
 532         {
 533         }
 534         public nothrow RedBlackTreeNodeIterator(RedBlackTreeNode<ValueType>* node_) : node(node_)
 535         {
 536         }
 537         public inline nothrow ReferenceType operator*()
 538         {
 539             if (node == null)
 540             {
 541                 ThrowInvalidParameterException();
 542             }
 543             return node->Value();
 544         }
 545         public inline nothrow PointerType operator->()
 546         {
 547             if (node == null)
 548             {
 549                 ThrowInvalidParameterException();
 550             }
 551             return &(node->Value());
 552         }
 553         public inline nothrow Self& operator++()
 554         {
 555             if (node == null)
 556             {
 557                 ThrowInvalidParameterException();
 558             }
 559             node = cast<RedBlackTreeNode<ValueType>*>(RedBlackTreeNodeBase.Next(node));
 560             return *this;
 561         }
 562         public inline nothrow Self& operator--()
 563         {
 564             if (node == null)
 565             {
 566                 ThrowInvalidParameterException();
 567             }
 568             node = cast<RedBlackTreeNode<ValueType>*>(RedBlackTreeNodeBase.Prev(node));
 569             return *this;
 570         }
 571         public inline nothrow RedBlackTreeNode<ValueType>* Node() const
 572         {
 573             return node;
 574         }
 575         private RedBlackTreeNode<ValueType>* node;
 576     }
 577 
 578     public inline nothrow bool operator==<T, R, P>(const RedBlackTreeNodeIterator<T, R, P>& left, const RedBlackTreeNodeIterator<T, R, P>& right)
 579     {
 580         return left.Node() == right.Node();
 581     }
 582 
 583     public class RedBlackTree<KeyType, ValueType, KeyOfValue, Compare>
 584         where KeyType is Semiregular and ValueType is Semiregular and KeySelectionFunction<KeyOfValue, KeyType, ValueType> and Compare is Relation and Compare.Domain is KeyType
 585     {
 586         public typedef RedBlackTreeNodeIterator<ValueType, const ValueType&, const ValueType*> ConstIterator;
 587         public typedef RedBlackTreeNodeIterator<ValueType, ValueType&, ValueType*> Iterator;
 588         private typedef RedBlackTree<KeyType, ValueType, KeyOfValue, Compare> Self;
 589 
 590         public RedBlackTree() : header(), count(0), keyOf(), comp()
 591         {
 592             Init();
 593         }
 594         public RedBlackTree(const Self& that) : header(), count(0), keyOf(), comp()
 595             where ValueType is Copyable
 596         {
 597             Init();
 598             CopyFrom(that);
 599         }
 600         public nothrow RedBlackTree(Self&& that) : header(Rvalue(that.header)), count(that.count), keyOf(that.keyOf), comp(that.comp)
 601             where ValueType is Movable
 602         {
 603             that.count = 0;
 604         }
 605         public void operator=(const Self& that)
 606             where ValueType is Copyable
 607         {
 608             Clear();
 609             Init();
 610             CopyFrom(that);
 611         }
 612         public nothrow void operator=(Self&& that)
 613             where ValueType is Movable
 614         {
 615             Swap(header, that.header);
 616             Swap(count, that.count);
 617             Swap(keyOf, that.keyOf);
 618             Swap(comp, that.comp);
 619         }
 620         public ~RedBlackTree()
 621         {
 622             Clear();
 623         }
 624         public inline nothrow ConstIterator Begin() const
 625         {
 626             if (header.IsNull())
 627             {
 628                 return CEnd();
 629             }
 630             else
 631             {
 632                 return ConstIterator(Leftmost());
 633             }
 634         }
 635         public inline nothrow Iterator Begin()
 636         {
 637             if (header.IsNull())
 638             {
 639                 return End();
 640             }
 641             else
 642             {
 643                 return Iterator(Leftmost());
 644             }
 645         }
 646         public inline nothrow ConstIterator CBegin() const
 647         {
 648             if (header.IsNull())
 649             {
 650                 return CEnd();
 651             }
 652             else
 653             {
 654                 return ConstIterator(Leftmost());
 655             }
 656         }
 657         public inline nothrow ConstIterator End() const
 658         {
 659             return ConstIterator(header.Get());
 660         }
 661         public inline nothrow Iterator End()
 662         {
 663             return Iterator(header.Get());
 664         }
 665         public inline nothrow ConstIterator CEnd() const
 666         {
 667             return ConstIterator(header.Get());
 668         }
 669         public inline nothrow long Count() const
 670         {
 671             if (count < 0)
 672             {
 673                 ThrowPreconditionViolationException();
 674             }
 675             return count;
 676         }
 677         public inline nothrow bool IsEmpty() const
 678         {
 679             if (count < 0)
 680             {
 681                 ThrowPreconditionViolationException();
 682             }
 683             return count == 0;
 684         }
 685         public nothrow void Clear()
 686         {
 687             if (header.IsNull())
 688             {
 689                 return;
 690             }
 691             RedBlackTreeNode<ValueType>* root = Root();
 692             if (root != null)
 693             {
 694                 delete root;
 695                 SetRoot(null);
 696             }
 697             SetLeftmost(header.Get());
 698             SetRightmost(header.Get());
 699             count = 0;
 700         }
 701         public nothrow Iterator Find(const KeyType& key)
 702         {
 703             if (IsEmpty())
 704             {
 705                 return End();
 706             }
 707             RedBlackTreeNode<ValueType>* x = Root();
 708             while (x != null)
 709             {
 710                 if (Comp(key, KeyOf(x->Value())))
 711                 {
 712                     x = cast<RedBlackTreeNode<ValueType>*>(x->Left());
 713                 }
 714                 else if (Comp(KeyOf(x->Value()), key))
 715                 {
 716                     x = cast<RedBlackTreeNode<ValueType>*>(x->Right());
 717                 }
 718                 else
 719                 {
 720                     return Iterator(x);
 721                 }
 722             }
 723             return End();
 724         }
 725         public nothrow ConstIterator Find(const KeyType& key) const
 726         {
 727             if (IsEmpty())
 728             {
 729                 return CEnd();
 730             }
 731             RedBlackTreeNode<ValueType>* x = Root();
 732             while (x != null)
 733             {
 734                 if (Comp(key, KeyOf(x->Value())))
 735                 {
 736                     x = cast<RedBlackTreeNode<ValueType>*>(x->Left());
 737                 }
 738                 else if (Comp(KeyOf(x->Value()), key))
 739                 {
 740                     x = cast<RedBlackTreeNode<ValueType>*>(x->Right());
 741                 }
 742                 else
 743                 {
 744                     return ConstIterator(x);
 745                 }
 746             }
 747             return CEnd();
 748         }
 749         public nothrow ConstIterator CFind(const KeyType& key) const
 750         {
 751             if (IsEmpty())
 752             {
 753                 return CEnd();
 754             }
 755             RedBlackTreeNode<ValueType>* x = Root();
 756             while (x != null)
 757             {
 758                 if (Comp(key, KeyOf(x->Value())))
 759                 {
 760                     x = cast<RedBlackTreeNode<ValueType>*>(x->Left());
 761                 }
 762                 else if (Comp(KeyOf(x->Value()), key))
 763                 {
 764                     x = cast<RedBlackTreeNode<ValueType>*>(x->Right());
 765                 }
 766                 else
 767                 {
 768                     return ConstIterator(x);
 769                 }
 770             }
 771             return CEnd();
 772         }
 773         public Pair<Iterator, bool> Insert(const ValueType& value)
 774             where ValueType is Copyable
 775         {
 776             if (header.IsNull())
 777             {
 778                 Init();
 779             }
 780             RedBlackTreeNode<ValueType>* x = Root();
 781             RedBlackTreeNode<ValueType>* p = header.Get();
 782             bool comp = true;
 783             while (x != null)
 784             {
 785                 p = x;
 786                 comp = Comp(KeyOf(value), KeyOf(x->Value()));
 787                 if (comp)
 788                 {
 789                     x = cast<RedBlackTreeNode<ValueType>*>(x->Left());
 790                 }
 791                 else
 792                 {
 793                     x = cast<RedBlackTreeNode<ValueType>*>(x->Right());
 794                 }
 795             }
 796             Iterator j = p;
 797             if (comp)
 798             {
 799                 if (j == Begin())
 800                 {
 801                     return MakePair(Insert(x, p, value), true);
 802                 }
 803                 else
 804                 {
 805                     --j;
 806                 }
 807             }
 808             if (Comp(KeyOf(j.Node()->Value()), KeyOf(value)))
 809             {
 810                 return MakePair(Insert(x, p, value), true);
 811             }
 812             return MakePair(j, false);
 813         }
 814         private Iterator Insert(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p, const ValueType& value)
 815             where ValueType is Copyable
 816         {
 817             if (header.IsNull())
 818             {
 819                 Init();
 820             }
 821             RedBlackTreeNode<ValueType>* n = new RedBlackTreeNode<ValueType>(value, p);
 822             if (p == header.Get() || x != null || Comp(KeyOf(value), KeyOf(p->Value())))
 823             {
 824                 p->SetLeft(n);
 825                 if (p == header.Get())
 826                 {
 827                     SetRoot(n);
 828                     SetRightmost(n);
 829                 }
 830                 else if (p == Leftmost())
 831                 {
 832                     SetLeftmost(n);
 833                 }
 834             }
 835             else
 836             {
 837                 p->SetRight(n);
 838                 if (p == Rightmost())
 839                 {
 840                     SetRightmost(n);
 841                 }
 842             }
 843             RedBlackTreeNodeBase.RebalanceAfterInsert(n, RootRef());
 844             ++count;
 845             return Iterator(n);
 846         }
 847         public nothrow bool Remove(const KeyType& key)
 848         {
 849             if (IsEmpty())
 850             {
 851                 return false;
 852             }
 853             RedBlackTreeNode<ValueType>* n = Root();
 854             while (n != null)
 855             {
 856                 if (Comp(key, KeyOf(n->Value())))
 857                 {
 858                     n = cast<RedBlackTreeNode<ValueType>*>(n->Left());
 859                 }
 860                 else if (Comp(KeyOf(n->Value()), key))
 861                 {
 862                     n = cast<RedBlackTreeNode<ValueType>*>(n->Right());
 863                 }
 864                 else
 865                 {
 866                     break;
 867                 }
 868             }
 869             if (n != null)
 870             {
 871                 if (count == 1)
 872                 {
 873                     Clear();
 874                 }
 875                 else
 876                 {
 877                     Remove(Iterator(n));
 878                 }
 879                 return true;
 880             }
 881             return false;
 882         }
 883         public nothrow void Remove(Iterator pos)
 884         {
 885             RedBlackTreeNode<ValueType>* toRemove = cast<RedBlackTreeNode<ValueType>*>(RedBlackTreeNodeBase.RebalanceForRemove(pos.Node(), RootRef(), LeftmostRef(), RightmostRef()));
 886             toRemove->SetLeft(null);
 887             toRemove->SetRight(null);
 888             delete toRemove;
 889             --count;
 890         }
 891         private void Init()
 892         {
 893             header.Reset(new RedBlackTreeNode<ValueType>(ValueType(), null));
 894             header->SetColor(RedBlackTreeNodeBase.Color.red);
 895             SetLeftmost(header.Get());
 896             SetRightmost(header.Get());
 897         }
 898         private void CopyFrom(const Self& that)
 899             where ValueType is Copyable
 900         {
 901             if (that.Root() != null)
 902             {
 903                 SetRoot(Copy(that.Root(), header.Get()));
 904                 SetLeftmost(cast<RedBlackTreeNode<ValueType>*>(RedBlackTreeNodeBase.Min(Root())));
 905                 SetRightmost(cast<RedBlackTreeNode<ValueType>*>(RedBlackTreeNodeBase.Max(Root())));
 906                 count = that.Count();
 907             }
 908         }
 909         private RedBlackTreeNode<ValueType>* Copy(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p)
 910         {
 911             if (x == null)
 912             {
 913                 ThrowInvalidParameterException();
 914             }
 915             if (p == null)
 916             {
 917                 ThrowInvalidParameterException();
 918             }
 919             RedBlackTreeNode<ValueType>* top = CloneNode(x, p);
 920             if (x->Right() != null)
 921             {
 922                 top->SetRight(Copy(cast<RedBlackTreeNode<ValueType>*>(x->Right()), top));
 923             }
 924             p = top;
 925             x = cast<RedBlackTreeNode<ValueType>*>(x->Left());
 926             while (x != null)
 927             {
 928                 RedBlackTreeNode<ValueType>* y = CloneNode(x, p);
 929                 p->SetLeft(y);
 930                 if (x->Right() != null)
 931                 {
 932                     y->SetRight(Copy(cast<RedBlackTreeNode<ValueType>*>(x->Right()), y));
 933                 }
 934                 p = y;
 935                 x = cast<RedBlackTreeNode<ValueType>*>(x->Left());
 936             }
 937             return top;
 938         }
 939         private RedBlackTreeNode<ValueType>* CloneNode(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p) const
 940         {
 941             if (x == null)
 942             {
 943                 ThrowInvalidParameterException();
 944             }
 945             if (p == null)
 946             {
 947                 ThrowInvalidParameterException();
 948             }
 949             RedBlackTreeNode<ValueType>* clone = new RedBlackTreeNode<ValueType>(x->Value(), p);
 950             clone->SetColor(x->GetColor());
 951             return clone;
 952         }
 953         private inline nothrow const KeyType& KeyOf(const ValueType& value) const
 954         {
 955             return keyOf(value);
 956         }
 957         private inline nothrow bool Comp(const KeyType& left, const KeyType& right) const
 958         {
 959             return comp(left, right);
 960         }
 961         private inline nothrow RedBlackTreeNode<ValueType>* Root()
 962         {
 963             return cast<RedBlackTreeNode<ValueType>*>(header->Parent());
 964         }
 965         private inline nothrow RedBlackTreeNodeBase*& RootRef()
 966         {
 967             return header->ParentRef();
 968         }
 969         private inline nothrow void SetRoot(RedBlackTreeNode<ValueType>* root)
 970         {
 971             header->SetParent(root);
 972         }
 973         private inline nothrow RedBlackTreeNode<ValueType>* Leftmost()
 974         {
 975             return cast<RedBlackTreeNode<ValueType>*>(header->Left());
 976         }
 977         private inline nothrow RedBlackTreeNodeBase*& LeftmostRef()
 978         {
 979             return header->LeftRef();
 980         }
 981         private inline nothrow void SetLeftmost(RedBlackTreeNode<ValueType>* lm)
 982         {
 983             header->SetLeft(lm);
 984         }
 985         private inline nothrow RedBlackTreeNode<ValueType>* Rightmost()
 986         {
 987             return cast<RedBlackTreeNode<ValueType>*>(header->Right());
 988         }
 989         private inline nothrow RedBlackTreeNodeBase*& RightmostRef()
 990         {
 991             return header->RightRef();
 992         }
 993         private inline nothrow void SetRightmost(RedBlackTreeNode<ValueType>* rm)
 994         {
 995             header->SetRight(rm);
 996         }
 997         private UniquePtr<RedBlackTreeNode<ValueType>> header;
 998         private long count;
 999         private KeyOfValue keyOf;
1000         private Compare comp;
1001     }
1002 }