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