1 // =================================
   2 // Copyright (c) 2021 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 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 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 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 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 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 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 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                 ThrowPreconditionViolationException();
 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 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                 ThrowPreconditionViolationException();
 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 ReferenceType operator*()
 538         {
 539             if (node == null)
 540             {
 541                 ThrowNullPointerException();
 542             }
 543             return node->Value();
 544         }
 545         public inline PointerType operator->()
 546         {
 547             if (node == null)
 548             {
 549                 ThrowNullPointerException();
 550             }
 551             return &(node->Value());
 552         }
 553         public inline Self& operator++()
 554         {
 555             if (node == null)
 556             {
 557                 ThrowNullPointerException();
 558             }
 559             node = cast<RedBlackTreeNode<ValueType>*>(RedBlackTreeNodeBase.Next(node));
 560             return *this;
 561         }
 562         public inline Self& operator--()
 563         {
 564             if (node == null)
 565             {
 566                 ThrowNullPointerException();
 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 long Count() const
 670         {
 671             if (count < 0)
 672             {
 673                 ThrowPreconditionViolationException();
 674             }
 675             return count;
 676         }
 677         public inline 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 nothrow Iterator LowerBound(const KeyType& key)
 774         {
 775             if (IsEmpty())
 776             {
 777                 return End();
 778             }
 779             RedBlackTreeNode<ValueType>* y = header.Get();
 780             RedBlackTreeNode<ValueType>* x = Root();
 781             while (x != null)
 782             {
 783                 if (!Comp(KeyOf(x->Value()), key))
 784                 {
 785                     y = x;
 786                     x = cast<RedBlackTreeNode<ValueType>*>(x->Left());
 787                 }
 788                 else
 789                 {
 790                      x = cast<RedBlackTreeNode<ValueType>*>(x->Right());
 791                 }
 792             }
 793             return Iterator(y);
 794         }
 795         public nothrow ConstIterator LowerBound(const KeyType& key) const
 796         {
 797             if (IsEmpty())
 798             {
 799                 return CEnd();
 800             }
 801             RedBlackTreeNode<ValueType>* y = header.Get();
 802             RedBlackTreeNode<ValueType>* x = Root();
 803             while (x != null)
 804             {
 805                 if (!Comp(KeyOf(x->Value()), key))
 806                 {
 807                     y = x;
 808                     x = cast<RedBlackTreeNode<ValueType>*>(x->Left());
 809                 }
 810                 else
 811                 {
 812                      x = cast<RedBlackTreeNode<ValueType>*>(x->Right());
 813                 }
 814             }
 815             return ConstIterator(y);
 816         }
 817         public nothrow ConstIterator CLowerBound(const KeyType& key) const
 818         {
 819             if (IsEmpty())
 820             {
 821                 return CEnd();
 822             }
 823             RedBlackTreeNode<ValueType>* y = header.Get();
 824             RedBlackTreeNode<ValueType>* x = Root();
 825             while (x != null)
 826             {
 827                 if (!Comp(KeyOf(x->Value()), key))
 828                 {
 829                     y = x;
 830                     x = cast<RedBlackTreeNode<ValueType>*>(x->Left());
 831                 }
 832                 else
 833                 {
 834                      x = cast<RedBlackTreeNode<ValueType>*>(x->Right());
 835                 }
 836             }
 837             return ConstIterator(y);
 838         }
 839         public Pair<Iterator, bool> Insert(const ValueType& value)
 840             where ValueType is Copyable
 841         {
 842             if (header.IsNull())
 843             {
 844                 Init();
 845             }
 846             RedBlackTreeNode<ValueType>* x = Root();
 847             RedBlackTreeNode<ValueType>* p = header.Get();
 848             bool comp = true;
 849             while (x != null)
 850             {
 851                 p = x;
 852                 comp = Comp(KeyOf(value), KeyOf(x->Value()));
 853                 if (comp)
 854                 {
 855                     x = cast<RedBlackTreeNode<ValueType>*>(x->Left());
 856                 }
 857                 else
 858                 {
 859                     x = cast<RedBlackTreeNode<ValueType>*>(x->Right());
 860                 }
 861             }
 862             Iterator j = p;
 863             if (comp)
 864             {
 865                 if (j == Begin())
 866                 {
 867                     return MakePair(Insert(x, p, value), true);
 868                 }
 869                 else
 870                 {
 871                     --j;
 872                 }
 873             }
 874             if (Comp(KeyOf(j.Node()->Value()), KeyOf(value)))
 875             {
 876                 return MakePair(Insert(x, p, value), true);
 877             }
 878             return MakePair(j, false);
 879         }
 880         private Iterator Insert(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p, const ValueType& value)
 881             where ValueType is Copyable
 882         {
 883             if (header.IsNull())
 884             {
 885                 Init();
 886             }
 887             RedBlackTreeNode<ValueType>* n = new RedBlackTreeNode<ValueType>(value, p);
 888             if (p == header.Get() || x != null || Comp(KeyOf(value), KeyOf(p->Value())))
 889             {
 890                 p->SetLeft(n);
 891                 if (p == header.Get())
 892                 {
 893                     SetRoot(n);
 894                     SetRightmost(n);
 895                 }
 896                 else if (p == Leftmost())
 897                 {
 898                     SetLeftmost(n);
 899                 }
 900             }
 901             else
 902             {
 903                 p->SetRight(n);
 904                 if (p == Rightmost())
 905                 {
 906                     SetRightmost(n);
 907                 }
 908             }
 909             RedBlackTreeNodeBase.RebalanceAfterInsert(n, RootRef());
 910             ++count;
 911             return Iterator(n);
 912         }
 913         public nothrow bool Remove(const KeyType& key)
 914         {
 915             if (IsEmpty())
 916             {
 917                 return false;
 918             }
 919             RedBlackTreeNode<ValueType>* n = Root();
 920             while (n != null)
 921             {
 922                 if (Comp(key, KeyOf(n->Value())))
 923                 {
 924                     n = cast<RedBlackTreeNode<ValueType>*>(n->Left());
 925                 }
 926                 else if (Comp(KeyOf(n->Value()), key))
 927                 {
 928                     n = cast<RedBlackTreeNode<ValueType>*>(n->Right());
 929                 }
 930                 else
 931                 {
 932                     break;
 933                 }
 934             }
 935             if (n != null)
 936             {
 937                 if (count == 1)
 938                 {
 939                     Clear();
 940                 }
 941                 else
 942                 {
 943                     Remove(Iterator(n));
 944                 }
 945                 return true;
 946             }
 947             return false;
 948         }
 949         public nothrow void Remove(Iterator pos)
 950         {
 951             RedBlackTreeNode<ValueType>* toRemove = cast<RedBlackTreeNode<ValueType>*>(RedBlackTreeNodeBase.RebalanceForRemove(pos.Node(), RootRef(), LeftmostRef(), RightmostRef()));
 952             toRemove->SetLeft(null);
 953             toRemove->SetRight(null);
 954             delete toRemove;
 955             --count;
 956         }
 957         private void Init()
 958         {
 959             header.Reset(new RedBlackTreeNode<ValueType>(ValueType(), null));
 960             header->SetColor(RedBlackTreeNodeBase.Color.red);
 961             SetLeftmost(header.Get());
 962             SetRightmost(header.Get());
 963         }
 964         private void CopyFrom(const Self& that)
 965             where ValueType is Copyable
 966         {
 967             if (that.Root() != null)
 968             {
 969                 SetRoot(Copy(that.Root(), header.Get()));
 970                 SetLeftmost(cast<RedBlackTreeNode<ValueType>*>(RedBlackTreeNodeBase.Min(Root())));
 971                 SetRightmost(cast<RedBlackTreeNode<ValueType>*>(RedBlackTreeNodeBase.Max(Root())));
 972                 count = that.Count();
 973             }
 974         }
 975         private RedBlackTreeNode<ValueType>* Copy(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p)
 976         {
 977             if (x == null || p == null)
 978             {
 979                 ThrowInvalidParameterException();
 980             }
 981             RedBlackTreeNode<ValueType>* top = CloneNode(x, p);
 982             if (x->Right() != null)
 983             {
 984                 top->SetRight(Copy(cast<RedBlackTreeNode<ValueType>*>(x->Right()), top));
 985             }
 986             p = top;
 987             x = cast<RedBlackTreeNode<ValueType>*>(x->Left());
 988             while (x != null)
 989             {
 990                 RedBlackTreeNode<ValueType>* y = CloneNode(x, p);
 991                 p->SetLeft(y);
 992                 if (x->Right() != null)
 993                 {
 994                     y->SetRight(Copy(cast<RedBlackTreeNode<ValueType>*>(x->Right()), y));
 995                 }
 996                 p = y;
 997                 x = cast<RedBlackTreeNode<ValueType>*>(x->Left());
 998             }
 999             return top;
1000         }
1001         private RedBlackTreeNode<ValueType>* CloneNode(RedBlackTreeNode<ValueType>* x, RedBlackTreeNode<ValueType>* p) const
1002         {
1003             if (x == null || p == null)
1004             {
1005                 ThrowInvalidParameterException();
1006             }
1007             RedBlackTreeNode<ValueType>* clone = new RedBlackTreeNode<ValueType>(x->Value(), p);
1008             clone->SetColor(x->GetColor());
1009             return clone;
1010         }
1011         private inline nothrow const KeyType& KeyOf(const ValueType& value) const
1012         {
1013             return keyOf(value);
1014         }
1015         private inline nothrow bool Comp(const KeyType& left, const KeyType& right) const
1016         {
1017             return comp(left, right);
1018         }
1019         private inline nothrow RedBlackTreeNode<ValueType>* Root()
1020         {
1021             return cast<RedBlackTreeNode<ValueType>*>(header->Parent());
1022         }
1023         private inline nothrow RedBlackTreeNodeBase*& RootRef()
1024         {
1025             return header->ParentRef();
1026         }
1027         private inline nothrow void SetRoot(RedBlackTreeNode<ValueType>* root)
1028         {
1029             header->SetParent(root);
1030         }
1031         private inline nothrow RedBlackTreeNode<ValueType>* Leftmost()
1032         {
1033             return cast<RedBlackTreeNode<ValueType>*>(header->Left());
1034         }
1035         private inline nothrow RedBlackTreeNodeBase*& LeftmostRef()
1036         {
1037             return header->LeftRef();
1038         }
1039         private inline nothrow void SetLeftmost(RedBlackTreeNode<ValueType>* lm)
1040         {
1041             header->SetLeft(lm);
1042         }
1043         private inline nothrow RedBlackTreeNode<ValueType>* Rightmost()
1044         {
1045             return cast<RedBlackTreeNode<ValueType>*>(header->Right());
1046         }
1047         private inline nothrow RedBlackTreeNodeBase*& RightmostRef()
1048         {
1049             return header->RightRef();
1050         }
1051         private inline nothrow void SetRightmost(RedBlackTreeNode<ValueType>* rm)
1052         {
1053             header->SetRight(rm);
1054         }
1055         private UniquePtr<RedBlackTreeNode<ValueType>> header;
1056         private long count;
1057         private KeyOfValue keyOf;
1058         private Compare comp;
1059     }
1060 }