Restoring authorship annotation for Anton Samokhvalov <pg83@yandex.ru>. Commit 1 of 2.

1 files changed, 631 insertions, 631 deletions

diff --git a/library/cpp/containers/intrusive_rb_tree/rb_tree.h b/library/cpp/containers/intrusive_rb_tree/rb_tree.h
index 0259452a14..ed94b1794d 100644
--- a/library/cpp/containers/intrusive_rb_tree/rb_tree.h
+++ b/library/cpp/containers/intrusive_rb_tree/rb_tree.h
@@ -1,48 +1,48 @@
 #pragma once
-
-#include <util/generic/utility.h>
-#include <util/generic/yexception.h>
-
+ 
+#include <util/generic/utility.h> 
+#include <util/generic/yexception.h> 
+ 
 using TRbTreeColorType = bool;
-
-#define RBTreeRed false
-#define RBTreeBlack true
-
-struct TRbTreeNodeBase {
+ 
+#define RBTreeRed false 
+#define RBTreeBlack true 
+ 
+struct TRbTreeNodeBase { 
     using TColorType = TRbTreeColorType;
     using TBasePtr = TRbTreeNodeBase*;
-
-    TColorType Color_;
-    TBasePtr Parent_;
-    TBasePtr Left_;
-    TBasePtr Right_;
+ 
+    TColorType Color_; 
+    TBasePtr Parent_; 
+    TBasePtr Left_; 
+    TBasePtr Right_; 
     size_t Children_;
-
+ 
     inline TRbTreeNodeBase() noexcept {
-        ReInitNode();
-    }
-
+        ReInitNode(); 
+    } 
+ 
     inline void ReInitNode() noexcept {
-        Color_ = RBTreeBlack;
+        Color_ = RBTreeBlack; 
         Parent_ = nullptr;
         Left_ = nullptr;
         Right_ = nullptr;
         Children_ = 1;
-    }
-
-    static TBasePtr MinimumNode(TBasePtr x) {
+    } 
+ 
+    static TBasePtr MinimumNode(TBasePtr x) { 
         while (x->Left_ != nullptr)
-            x = x->Left_;
-
-        return x;
-    }
-
-    static TBasePtr MaximumNode(TBasePtr x) {
+            x = x->Left_; 
+ 
+        return x; 
+    } 
+ 
+    static TBasePtr MaximumNode(TBasePtr x) { 
         while (x->Right_ != nullptr)
-            x = x->Right_;
-
-        return x;
-    }
+            x = x->Right_; 
+ 
+        return x; 
+    } 
 
     static TBasePtr ByIndex(TBasePtr x, size_t index) {
         if (x->Left_ != nullptr) {
@@ -56,300 +56,300 @@ struct TRbTreeNodeBase {
             ythrow yexception() << "index not found";
         return ByIndex(x->Right_, index - 1);
     }
-};
-
-struct TRbTreeBaseIterator;
-
-template <class TDummy>
-class TRbGlobal {
-public:
+}; 
+ 
+struct TRbTreeBaseIterator; 
+ 
+template <class TDummy> 
+class TRbGlobal { 
+public: 
     using TBasePtr = TRbTreeNodeBase*;
-
-    static void Rebalance(TBasePtr x, TBasePtr& root);
-    static TBasePtr RebalanceForErase(TBasePtr z, TBasePtr& root, TBasePtr& leftmost, TBasePtr& rightmost);
+ 
+    static void Rebalance(TBasePtr x, TBasePtr& root); 
+    static TBasePtr RebalanceForErase(TBasePtr z, TBasePtr& root, TBasePtr& leftmost, TBasePtr& rightmost); 
     static void DecrementChildrenUntilRoot(TBasePtr x, TBasePtr root);
     static void RecalcChildren(TBasePtr x);
-
-    static TBasePtr IncrementNode(TBasePtr);
-    static TBasePtr DecrementNode(TBasePtr);
-    static void RotateLeft(TBasePtr x, TBasePtr& root);
-    static void RotateRight(TBasePtr x, TBasePtr& root);
-};
-
+ 
+    static TBasePtr IncrementNode(TBasePtr); 
+    static TBasePtr DecrementNode(TBasePtr); 
+    static void RotateLeft(TBasePtr x, TBasePtr& root); 
+    static void RotateRight(TBasePtr x, TBasePtr& root); 
+}; 
+ 
 using TRbGlobalInst = TRbGlobal<bool>;
-
-struct TRbTreeBaseIterator {
+ 
+struct TRbTreeBaseIterator { 
     using TBasePtr = TRbTreeNodeBase*;
-    TBasePtr Node_;
-
+    TBasePtr Node_; 
+ 
     inline TRbTreeBaseIterator(TBasePtr x = nullptr) noexcept
-        : Node_(x)
-    {
-    }
-};
-
-template <class TValue, class TTraits>
-struct TRbTreeIterator: public TRbTreeBaseIterator {
+        : Node_(x) 
+    { 
+    } 
+}; 
+ 
+template <class TValue, class TTraits> 
+struct TRbTreeIterator: public TRbTreeBaseIterator { 
     using TReference = typename TTraits::TReference;
     using TPointer = typename TTraits::TPointer;
     using TSelf = TRbTreeIterator<TValue, TTraits>;
     using TBasePtr = TRbTreeNodeBase*;
-
+ 
     inline TRbTreeIterator() noexcept = default;
-
-    template <class T1>
+ 
+    template <class T1> 
     inline TRbTreeIterator(const T1& x) noexcept
-        : TRbTreeBaseIterator(x)
-    {
-    }
-
+        : TRbTreeBaseIterator(x) 
+    { 
+    } 
+ 
     inline TReference operator*() const noexcept {
-        return *static_cast<TValue*>(Node_);
-    }
-
+        return *static_cast<TValue*>(Node_); 
+    } 
+ 
     inline TPointer operator->() const noexcept {
-        return static_cast<TValue*>(Node_);
-    }
-
+        return static_cast<TValue*>(Node_); 
+    } 
+ 
     inline TSelf& operator++() noexcept {
-        Node_ = TRbGlobalInst::IncrementNode(Node_);
-        return *this;
-    }
-
+        Node_ = TRbGlobalInst::IncrementNode(Node_); 
+        return *this; 
+    } 
+ 
     inline TSelf operator++(int) noexcept {
-        TSelf tmp = *this;
-        ++(*this);
-        return tmp;
-    }
-
+        TSelf tmp = *this; 
+        ++(*this); 
+        return tmp; 
+    } 
+ 
     inline TSelf& operator--() noexcept {
-        Node_ = TRbGlobalInst::DecrementNode(Node_);
-        return *this;
-    }
-
+        Node_ = TRbGlobalInst::DecrementNode(Node_); 
+        return *this; 
+    } 
+ 
     inline TSelf operator--(int) noexcept {
-        TSelf tmp = *this;
-        --(*this);
-        return tmp;
-    }
-
-    template <class T1>
+        TSelf tmp = *this; 
+        --(*this); 
+        return tmp; 
+    } 
+ 
+    template <class T1> 
     inline bool operator==(const T1& rhs) const noexcept {
-        return Node_ == rhs.Node_;
-    }
-
-    template <class T1>
+        return Node_ == rhs.Node_; 
+    } 
+ 
+    template <class T1> 
     inline bool operator!=(const T1& rhs) const noexcept {
-        return Node_ != rhs.Node_;
-    }
-};
-
-template <class TValue, class TCmp>
-class TRbTree {
-    struct TCmpAdaptor: public TCmp {
+        return Node_ != rhs.Node_; 
+    } 
+}; 
+ 
+template <class TValue, class TCmp> 
+class TRbTree { 
+    struct TCmpAdaptor: public TCmp { 
         inline TCmpAdaptor() noexcept = default;
-
+ 
         inline TCmpAdaptor(const TCmp& cmp) noexcept
-            : TCmp(cmp)
-        {
-        }
-
-        template <class T1, class T2>
-        inline bool operator()(const T1& l, const T2& r) const {
-            return TCmp::Compare(l, r);
-        }
-    };
-
-    struct TNonConstTraits {
+            : TCmp(cmp) 
+        { 
+        } 
+ 
+        template <class T1, class T2> 
+        inline bool operator()(const T1& l, const T2& r) const { 
+            return TCmp::Compare(l, r); 
+        } 
+    }; 
+ 
+    struct TNonConstTraits { 
         using TReference = TValue&;
         using TPointer = TValue*;
-    };
-
-    struct TConstTraits {
+    }; 
+ 
+    struct TConstTraits { 
         using TReference = const TValue&;
         using TPointer = const TValue*;
-    };
-
+    }; 
+ 
     using TNodeBase = TRbTreeNodeBase;
     using TBasePtr = TRbTreeNodeBase*;
     using TColorType = TRbTreeColorType;
-
-public:
-    class TRealNode: public TNodeBase {
-    public:
-        inline TRealNode()
+ 
+public: 
+    class TRealNode: public TNodeBase { 
+    public: 
+        inline TRealNode() 
             : Tree_(nullptr)
-        {
-        }
-
+        { 
+        } 
+ 
         inline ~TRealNode() {
-            UnLink();
-        }
-
+            UnLink(); 
+        } 
+ 
         inline void UnLink() noexcept {
-            if (Tree_) {
-                Tree_->EraseImpl(this);
-                ReInitNode();
+            if (Tree_) { 
+                Tree_->EraseImpl(this); 
+                ReInitNode(); 
                 Tree_ = nullptr;
-            }
-        }
-
+            } 
+        } 
+ 
         inline void SetRbTreeParent(TRbTree* parent) noexcept {
-            Tree_ = parent;
-        }
-
+            Tree_ = parent; 
+        } 
+ 
         inline TRbTree* ParentTree() const noexcept {
-            return Tree_;
-        }
-
-    private:
-        TRbTree* Tree_;
-    };
-
+            return Tree_; 
+        } 
+ 
+    private: 
+        TRbTree* Tree_; 
+    }; 
+ 
     using TIterator = TRbTreeIterator<TValue, TNonConstTraits>;
     using TConstIterator = TRbTreeIterator<TValue, TConstTraits>;
-
+ 
     inline TRbTree() noexcept {
-        Init();
-    }
-
+        Init(); 
+    } 
+ 
     inline TRbTree(const TCmp& cmp) noexcept
-        : KeyCompare_(cmp)
-    {
-        Init();
-    }
-
+        : KeyCompare_(cmp) 
+    { 
+        Init(); 
+    } 
+ 
     inline void Init() noexcept {
-        Data_.Color_ = RBTreeRed;
+        Data_.Color_ = RBTreeRed; 
         Data_.Parent_ = nullptr;
-        Data_.Left_ = &Data_;
-        Data_.Right_ = &Data_;
-        Data_.Children_ = 0;
-    }
-
-    struct TDestroy {
+        Data_.Left_ = &Data_; 
+        Data_.Right_ = &Data_; 
+        Data_.Children_ = 0; 
+    } 
+ 
+    struct TDestroy { 
         inline void operator()(TValue& v) const noexcept {
             v.SetRbTreeParent(nullptr);
-            v.ReInitNode();
-        }
-    };
-
+            v.ReInitNode(); 
+        } 
+    }; 
+ 
     inline ~TRbTree() {
-        ForEachNoOrder(TDestroy());
-    }
-
+        ForEachNoOrder(TDestroy()); 
+    } 
+ 
     inline void Clear() noexcept {
-        ForEachNoOrder(TDestroy());
-        Init();
-    }
-
-    template <class F>
-    inline void ForEachNoOrder(const F& f) {
-        ForEachNoOrder(Root(), f);
-    }
-
-    template <class F>
-    inline void ForEachNoOrder(TNodeBase* n, const F& f) {
-        if (n && n != &Data_) {
-            ForEachNoOrder(n->Left_, f);
-            ForEachNoOrder(n->Right_, f);
-            f(ValueNode(n));
-        }
-    }
-
+        ForEachNoOrder(TDestroy()); 
+        Init(); 
+    } 
+ 
+    template <class F> 
+    inline void ForEachNoOrder(const F& f) { 
+        ForEachNoOrder(Root(), f); 
+    } 
+ 
+    template <class F> 
+    inline void ForEachNoOrder(TNodeBase* n, const F& f) { 
+        if (n && n != &Data_) { 
+            ForEachNoOrder(n->Left_, f); 
+            ForEachNoOrder(n->Right_, f); 
+            f(ValueNode(n)); 
+        } 
+    } 
+ 
     inline TIterator Begin() noexcept {
-        return LeftMost();
-    }
-
+        return LeftMost(); 
+    } 
+ 
     inline TConstIterator Begin() const noexcept {
-        return LeftMost();
-    }
-
+        return LeftMost(); 
+    } 
+ 
     inline TIterator End() noexcept {
-        return &this->Data_;
-    }
-
+        return &this->Data_; 
+    } 
+ 
     inline TConstIterator End() const noexcept {
-        return const_cast<TBasePtr>(&this->Data_);
-    }
-
+        return const_cast<TBasePtr>(&this->Data_); 
+    } 
+ 
     inline bool Empty() const noexcept {
-        return this->Begin() == this->End();
-    }
-
+        return this->Begin() == this->End(); 
+    } 
+ 
     inline explicit operator bool() const noexcept {
-        return !this->Empty();
-    }
-
-    inline TIterator Insert(TValue* val) {
-        return Insert(*val);
-    }
-
-    inline TIterator Insert(TValue& val) {
-        val.UnLink();
-
-        TBasePtr y = &this->Data_;
-        TBasePtr x = Root();
-
+        return !this->Empty(); 
+    } 
+ 
+    inline TIterator Insert(TValue* val) { 
+        return Insert(*val); 
+    } 
+ 
+    inline TIterator Insert(TValue& val) { 
+        val.UnLink(); 
+ 
+        TBasePtr y = &this->Data_; 
+        TBasePtr x = Root(); 
+ 
         while (x != nullptr) {
-            ++(x->Children_);
-            y = x;
-
-            if (KeyCompare_(ValueNode(&val), ValueNode(x))) {
-                x = LeftNode(x);
-            } else {
-                x = RightNode(x);
-            }
-        }
-
-        return InsertImpl(y, &val, x);
-    }
-
-    template <class F>
-    inline void ForEach(F& f) {
-        TIterator it = Begin();
-
-        while (it != End()) {
-            f(*it++);
-        }
-    }
-
+            ++(x->Children_); 
+            y = x; 
+ 
+            if (KeyCompare_(ValueNode(&val), ValueNode(x))) { 
+                x = LeftNode(x); 
+            } else { 
+                x = RightNode(x); 
+            } 
+        } 
+ 
+        return InsertImpl(y, &val, x); 
+    } 
+ 
+    template <class F> 
+    inline void ForEach(F& f) { 
+        TIterator it = Begin(); 
+ 
+        while (it != End()) { 
+            f(*it++); 
+        } 
+    } 
+ 
     inline void Erase(TValue& val) noexcept {
-        val.UnLink();
-    }
-
+        val.UnLink(); 
+    } 
+ 
     inline void Erase(TValue* val) noexcept {
-        Erase(*val);
-    }
-
+        Erase(*val); 
+    } 
+ 
     inline void Erase(TIterator pos) noexcept {
-        Erase(*pos);
-    }
-
+        Erase(*pos); 
+    } 
+ 
     inline void EraseImpl(TNodeBase* val) noexcept {
-        TRbGlobalInst::RebalanceForErase(val, this->Data_.Parent_, this->Data_.Left_, this->Data_.Right_);
-    }
-
-    template <class T1>
-    inline TValue* Find(const T1& k) const {
+        TRbGlobalInst::RebalanceForErase(val, this->Data_.Parent_, this->Data_.Left_, this->Data_.Right_); 
+    } 
+ 
+    template <class T1> 
+    inline TValue* Find(const T1& k) const { 
         TBasePtr y = nullptr;
-        TBasePtr x = Root(); // Current node.
-
+        TBasePtr x = Root(); // Current node. 
+ 
         while (x != nullptr)
-            if (!KeyCompare_(ValueNode(x), k))
-                y = x, x = LeftNode(x);
-            else
-                x = RightNode(x);
-
-        if (y) {
-            if (KeyCompare_(k, ValueNode(y))) {
+            if (!KeyCompare_(ValueNode(x), k)) 
+                y = x, x = LeftNode(x); 
+            else 
+                x = RightNode(x); 
+ 
+        if (y) { 
+            if (KeyCompare_(k, ValueNode(y))) { 
                 y = nullptr;
-            }
-        }
-
-        return static_cast<TValue*>(y);
-    }
-
+            } 
+        } 
+ 
+        return static_cast<TValue*>(y); 
+    } 
+ 
     size_t GetIndex(TBasePtr x) const {
         size_t index = 0;
 
@@ -370,33 +370,33 @@ public:
         return index;
     }
 
-    template <class T1>
-    inline TBasePtr LowerBound(const T1& k) const {
-        TBasePtr y = const_cast<TBasePtr>(&this->Data_); /* Last node which is not less than k. */
-        TBasePtr x = Root();                             /* Current node. */
-
+    template <class T1> 
+    inline TBasePtr LowerBound(const T1& k) const { 
+        TBasePtr y = const_cast<TBasePtr>(&this->Data_); /* Last node which is not less than k. */ 
+        TBasePtr x = Root();                             /* Current node. */ 
+ 
         while (x != nullptr)
-            if (!KeyCompare_(ValueNode(x), k))
-                y = x, x = LeftNode(x);
-            else
-                x = RightNode(x);
-
-        return y;
-    }
-
-    template <class T1>
-    inline TBasePtr UpperBound(const T1& k) const {
-        TBasePtr y = const_cast<TBasePtr>(&this->Data_); /* Last node which is greater than k. */
-        TBasePtr x = Root();                             /* Current node. */
-
+            if (!KeyCompare_(ValueNode(x), k)) 
+                y = x, x = LeftNode(x); 
+            else 
+                x = RightNode(x); 
+ 
+        return y; 
+    } 
+ 
+    template <class T1> 
+    inline TBasePtr UpperBound(const T1& k) const { 
+        TBasePtr y = const_cast<TBasePtr>(&this->Data_); /* Last node which is greater than k. */ 
+        TBasePtr x = Root();                             /* Current node. */ 
+ 
         while (x != nullptr)
-            if (KeyCompare_(k, ValueNode(x)))
-                y = x, x = LeftNode(x);
-            else
-                x = RightNode(x);
-
-        return y;
-    }
+            if (KeyCompare_(k, ValueNode(x))) 
+                y = x, x = LeftNode(x); 
+            else 
+                x = RightNode(x); 
+ 
+        return y; 
+    } 
 
     template <class T1>
     inline size_t LessCount(const T1& k) const {
@@ -432,184 +432,184 @@ public:
         return Root()->Children_ - GreaterCount<T1>(k);
     }
 
-    TValue* ByIndex(size_t index) {
-        return static_cast<TValue*>(TRbTreeNodeBase::ByIndex(Root(), index));
-    }
-
-private:
-    // CRP 7/10/00 inserted argument on_right, which is another hint (meant to
-    // act like on_left and ignore a portion of the if conditions -- specify
+    TValue* ByIndex(size_t index) { 
+        return static_cast<TValue*>(TRbTreeNodeBase::ByIndex(Root(), index)); 
+    } 
+ 
+private: 
+    // CRP 7/10/00 inserted argument on_right, which is another hint (meant to 
+    // act like on_left and ignore a portion of the if conditions -- specify 
     // on_right != nullptr to bypass comparison as false or on_left != nullptr to bypass
-    // comparison as true)
+    // comparison as true) 
     TIterator InsertImpl(TRbTreeNodeBase* parent, TRbTreeNodeBase* val, TRbTreeNodeBase* on_left = nullptr, TRbTreeNodeBase* on_right = nullptr) {
-        ValueNode(val).SetRbTreeParent(this);
-        TBasePtr new_node = val;
-
-        if (parent == &this->Data_) {
-            LeftNode(parent) = new_node;
-            // also makes LeftMost() = new_node
-            Root() = new_node;
-            RightMost() = new_node;
+        ValueNode(val).SetRbTreeParent(this); 
+        TBasePtr new_node = val; 
+ 
+        if (parent == &this->Data_) { 
+            LeftNode(parent) = new_node; 
+            // also makes LeftMost() = new_node 
+            Root() = new_node; 
+            RightMost() = new_node; 
         } else if (on_right == nullptr &&
                    // If on_right != nullptr, the remainder fails to false
                    (on_left != nullptr ||
                     // If on_left != nullptr, the remainder succeeds to true
-                    KeyCompare_(ValueNode(val), ValueNode(parent))))
- {
-            LeftNode(parent) = new_node;
-            if (parent == LeftMost())
-                // maintain LeftMost() pointing to min node
-                LeftMost() = new_node;
-        } else {
-            RightNode(parent) = new_node;
-            if (parent == RightMost())
-                // maintain RightMost() pointing to max node
-                RightMost() = new_node;
-        }
-        ParentNode(new_node) = parent;
-        TRbGlobalInst::Rebalance(new_node, this->Data_.Parent_);
-        return new_node;
-    }
-
-    TBasePtr Root() const {
-        return this->Data_.Parent_;
-    }
-
-    TBasePtr LeftMost() const {
-        return this->Data_.Left_;
-    }
-
-    TBasePtr RightMost() const {
-        return this->Data_.Right_;
-    }
-
-    TBasePtr& Root() {
-        return this->Data_.Parent_;
-    }
-
-    TBasePtr& LeftMost() {
-        return this->Data_.Left_;
-    }
-
-    TBasePtr& RightMost() {
-        return this->Data_.Right_;
-    }
-
-    static TBasePtr& LeftNode(TBasePtr x) {
-        return x->Left_;
-    }
-
-    static TBasePtr& RightNode(TBasePtr x) {
-        return x->Right_;
-    }
-
-    static TBasePtr& ParentNode(TBasePtr x) {
-        return x->Parent_;
-    }
-
-    static TValue& ValueNode(TBasePtr x) {
-        return *static_cast<TValue*>(x);
-    }
-
-    static TBasePtr MinimumNode(TBasePtr x) {
-        return TRbTreeNodeBase::MinimumNode(x);
-    }
-
-    static TBasePtr MaximumNode(TBasePtr x) {
-        return TRbTreeNodeBase::MaximumNode(x);
-    }
-
-private:
-    TCmpAdaptor KeyCompare_;
-    TNodeBase Data_;
-};
-
-template <class TValue, class TCmp>
-class TRbTreeItem: public TRbTree<TValue, TCmp>::TRealNode {
-};
-
-template <class TDummy>
-void TRbGlobal<TDummy>::RotateLeft(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) {
-    TRbTreeNodeBase* y = x->Right_;
-    x->Right_ = y->Left_;
+                    KeyCompare_(ValueNode(val), ValueNode(parent)))) 
+ { 
+            LeftNode(parent) = new_node; 
+            if (parent == LeftMost()) 
+                // maintain LeftMost() pointing to min node 
+                LeftMost() = new_node; 
+        } else { 
+            RightNode(parent) = new_node; 
+            if (parent == RightMost()) 
+                // maintain RightMost() pointing to max node 
+                RightMost() = new_node; 
+        } 
+        ParentNode(new_node) = parent; 
+        TRbGlobalInst::Rebalance(new_node, this->Data_.Parent_); 
+        return new_node; 
+    } 
+ 
+    TBasePtr Root() const { 
+        return this->Data_.Parent_; 
+    } 
+ 
+    TBasePtr LeftMost() const { 
+        return this->Data_.Left_; 
+    } 
+ 
+    TBasePtr RightMost() const { 
+        return this->Data_.Right_; 
+    } 
+ 
+    TBasePtr& Root() { 
+        return this->Data_.Parent_; 
+    } 
+ 
+    TBasePtr& LeftMost() { 
+        return this->Data_.Left_; 
+    } 
+ 
+    TBasePtr& RightMost() { 
+        return this->Data_.Right_; 
+    } 
+ 
+    static TBasePtr& LeftNode(TBasePtr x) { 
+        return x->Left_; 
+    } 
+ 
+    static TBasePtr& RightNode(TBasePtr x) { 
+        return x->Right_; 
+    } 
+ 
+    static TBasePtr& ParentNode(TBasePtr x) { 
+        return x->Parent_; 
+    } 
+ 
+    static TValue& ValueNode(TBasePtr x) { 
+        return *static_cast<TValue*>(x); 
+    } 
+ 
+    static TBasePtr MinimumNode(TBasePtr x) { 
+        return TRbTreeNodeBase::MinimumNode(x); 
+    } 
+ 
+    static TBasePtr MaximumNode(TBasePtr x) { 
+        return TRbTreeNodeBase::MaximumNode(x); 
+    } 
+ 
+private: 
+    TCmpAdaptor KeyCompare_; 
+    TNodeBase Data_; 
+}; 
+ 
+template <class TValue, class TCmp> 
+class TRbTreeItem: public TRbTree<TValue, TCmp>::TRealNode { 
+}; 
+ 
+template <class TDummy> 
+void TRbGlobal<TDummy>::RotateLeft(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) { 
+    TRbTreeNodeBase* y = x->Right_; 
+    x->Right_ = y->Left_; 
     if (y->Left_ != nullptr)
-        y->Left_->Parent_ = x;
-    y->Parent_ = x->Parent_;
-
-    if (x == root)
-        root = y;
-    else if (x == x->Parent_->Left_)
-        x->Parent_->Left_ = y;
-    else
-        x->Parent_->Right_ = y;
-    y->Left_ = x;
-    x->Parent_ = y;
+        y->Left_->Parent_ = x; 
+    y->Parent_ = x->Parent_; 
+ 
+    if (x == root) 
+        root = y; 
+    else if (x == x->Parent_->Left_) 
+        x->Parent_->Left_ = y; 
+    else 
+        x->Parent_->Right_ = y; 
+    y->Left_ = x; 
+    x->Parent_ = y; 
     y->Children_ = x->Children_;
     x->Children_ = ((x->Left_) ? x->Left_->Children_ : 0) + ((x->Right_) ? x->Right_->Children_ : 0) + 1;
-}
-
-template <class TDummy>
-void TRbGlobal<TDummy>::RotateRight(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) {
-    TRbTreeNodeBase* y = x->Left_;
-    x->Left_ = y->Right_;
+} 
+ 
+template <class TDummy> 
+void TRbGlobal<TDummy>::RotateRight(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) { 
+    TRbTreeNodeBase* y = x->Left_; 
+    x->Left_ = y->Right_; 
     if (y->Right_ != nullptr)
-        y->Right_->Parent_ = x;
-    y->Parent_ = x->Parent_;
-
-    if (x == root)
-        root = y;
-    else if (x == x->Parent_->Right_)
-        x->Parent_->Right_ = y;
-    else
-        x->Parent_->Left_ = y;
-    y->Right_ = x;
-    x->Parent_ = y;
+        y->Right_->Parent_ = x; 
+    y->Parent_ = x->Parent_; 
+ 
+    if (x == root) 
+        root = y; 
+    else if (x == x->Parent_->Right_) 
+        x->Parent_->Right_ = y; 
+    else 
+        x->Parent_->Left_ = y; 
+    y->Right_ = x; 
+    x->Parent_ = y; 
     y->Children_ = x->Children_;
     x->Children_ = ((x->Left_) ? x->Left_->Children_ : 0) + ((x->Right_) ? x->Right_->Children_ : 0) + 1;
-}
-
-template <class TDummy>
-void TRbGlobal<TDummy>::Rebalance(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) {
-    x->Color_ = RBTreeRed;
-    while (x != root && x->Parent_->Color_ == RBTreeRed) {
-        if (x->Parent_ == x->Parent_->Parent_->Left_) {
-            TRbTreeNodeBase* y = x->Parent_->Parent_->Right_;
-            if (y && y->Color_ == RBTreeRed) {
-                x->Parent_->Color_ = RBTreeBlack;
-                y->Color_ = RBTreeBlack;
-                x->Parent_->Parent_->Color_ = RBTreeRed;
-                x = x->Parent_->Parent_;
-            } else {
-                if (x == x->Parent_->Right_) {
-                    x = x->Parent_;
-                    RotateLeft(x, root);
-                }
-                x->Parent_->Color_ = RBTreeBlack;
-                x->Parent_->Parent_->Color_ = RBTreeRed;
-                RotateRight(x->Parent_->Parent_, root);
-            }
-        } else {
-            TRbTreeNodeBase* y = x->Parent_->Parent_->Left_;
-            if (y && y->Color_ == RBTreeRed) {
-                x->Parent_->Color_ = RBTreeBlack;
-                y->Color_ = RBTreeBlack;
-                x->Parent_->Parent_->Color_ = RBTreeRed;
-                x = x->Parent_->Parent_;
-            } else {
-                if (x == x->Parent_->Left_) {
-                    x = x->Parent_;
-                    RotateRight(x, root);
-                }
-                x->Parent_->Color_ = RBTreeBlack;
-                x->Parent_->Parent_->Color_ = RBTreeRed;
-                RotateLeft(x->Parent_->Parent_, root);
-            }
-        }
-    }
-    root->Color_ = RBTreeBlack;
-}
-
-template <class TDummy>
+} 
+ 
+template <class TDummy> 
+void TRbGlobal<TDummy>::Rebalance(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) { 
+    x->Color_ = RBTreeRed; 
+    while (x != root && x->Parent_->Color_ == RBTreeRed) { 
+        if (x->Parent_ == x->Parent_->Parent_->Left_) { 
+            TRbTreeNodeBase* y = x->Parent_->Parent_->Right_; 
+            if (y && y->Color_ == RBTreeRed) { 
+                x->Parent_->Color_ = RBTreeBlack; 
+                y->Color_ = RBTreeBlack; 
+                x->Parent_->Parent_->Color_ = RBTreeRed; 
+                x = x->Parent_->Parent_; 
+            } else { 
+                if (x == x->Parent_->Right_) { 
+                    x = x->Parent_; 
+                    RotateLeft(x, root); 
+                } 
+                x->Parent_->Color_ = RBTreeBlack; 
+                x->Parent_->Parent_->Color_ = RBTreeRed; 
+                RotateRight(x->Parent_->Parent_, root); 
+            } 
+        } else { 
+            TRbTreeNodeBase* y = x->Parent_->Parent_->Left_; 
+            if (y && y->Color_ == RBTreeRed) { 
+                x->Parent_->Color_ = RBTreeBlack; 
+                y->Color_ = RBTreeBlack; 
+                x->Parent_->Parent_->Color_ = RBTreeRed; 
+                x = x->Parent_->Parent_; 
+            } else { 
+                if (x == x->Parent_->Left_) { 
+                    x = x->Parent_; 
+                    RotateRight(x, root); 
+                } 
+                x->Parent_->Color_ = RBTreeBlack; 
+                x->Parent_->Parent_->Color_ = RBTreeRed; 
+                RotateLeft(x->Parent_->Parent_, root); 
+            } 
+        } 
+    } 
+    root->Color_ = RBTreeBlack; 
+} 
+ 
+template <class TDummy> 
 void TRbGlobal<TDummy>::RecalcChildren(TRbTreeNodeBase* x) {
     x->Children_ = ((x->Left_) ? x->Left_->Children_ : 0) + ((x->Right_) ? x->Right_->Children_ : 0) + 1;
 }
@@ -625,46 +625,46 @@ void TRbGlobal<TDummy>::DecrementChildrenUntilRoot(TRbTreeNodeBase* x, TRbTreeNo
 }
 
 template <class TDummy>
-TRbTreeNodeBase* TRbGlobal<TDummy>::RebalanceForErase(TRbTreeNodeBase* z,
-                                                      TRbTreeNodeBase*& root,
-                                                      TRbTreeNodeBase*& leftmost,
-                                                      TRbTreeNodeBase*& rightmost) {
-    TRbTreeNodeBase* y = z;
-    TRbTreeNodeBase* x;
-    TRbTreeNodeBase* x_parent;
-
+TRbTreeNodeBase* TRbGlobal<TDummy>::RebalanceForErase(TRbTreeNodeBase* z, 
+                                                      TRbTreeNodeBase*& root, 
+                                                      TRbTreeNodeBase*& leftmost, 
+                                                      TRbTreeNodeBase*& rightmost) { 
+    TRbTreeNodeBase* y = z; 
+    TRbTreeNodeBase* x; 
+    TRbTreeNodeBase* x_parent; 
+ 
     if (y->Left_ == nullptr) // z has at most one non-null child. y == z.
-        x = y->Right_;       // x might be null.
-    else {
-        if (y->Right_ == nullptr)                        // z has exactly one non-null child. y == z.
-            x = y->Left_;                                // x is not null.
-        else {                                           // z has two non-null children.  Set y to
-            y = TRbTreeNodeBase::MinimumNode(y->Right_); //   z's successor.  x might be null.
-            x = y->Right_;
-        }
-    }
-
-    if (y != z) {
-        // relink y in place of z.  y is z's successor
-        z->Left_->Parent_ = y;
-        y->Left_ = z->Left_;
-        if (y != z->Right_) {
-            x_parent = y->Parent_;
-            if (x)
-                x->Parent_ = y->Parent_;
-            y->Parent_->Left_ = x; // y must be a child of mLeft
-            y->Right_ = z->Right_;
-            z->Right_->Parent_ = y;
-        } else
-            x_parent = y;
-        if (root == z)
-            root = y;
-        else if (z->Parent_->Left_ == z)
-            z->Parent_->Left_ = y;
-        else
-            z->Parent_->Right_ = y;
-        y->Parent_ = z->Parent_;
-        DoSwap(y->Color_, z->Color_);
+        x = y->Right_;       // x might be null. 
+    else { 
+        if (y->Right_ == nullptr)                        // z has exactly one non-null child. y == z. 
+            x = y->Left_;                                // x is not null. 
+        else {                                           // z has two non-null children.  Set y to 
+            y = TRbTreeNodeBase::MinimumNode(y->Right_); //   z's successor.  x might be null. 
+            x = y->Right_; 
+        } 
+    } 
+ 
+    if (y != z) { 
+        // relink y in place of z.  y is z's successor 
+        z->Left_->Parent_ = y; 
+        y->Left_ = z->Left_; 
+        if (y != z->Right_) { 
+            x_parent = y->Parent_; 
+            if (x) 
+                x->Parent_ = y->Parent_; 
+            y->Parent_->Left_ = x; // y must be a child of mLeft 
+            y->Right_ = z->Right_; 
+            z->Right_->Parent_ = y; 
+        } else 
+            x_parent = y; 
+        if (root == z) 
+            root = y; 
+        else if (z->Parent_->Left_ == z) 
+            z->Parent_->Left_ = y; 
+        else 
+            z->Parent_->Right_ = y; 
+        y->Parent_ = z->Parent_; 
+        DoSwap(y->Color_, z->Color_); 
 
         RecalcChildren(y);
         if (x_parent != y) {
@@ -673,146 +673,146 @@ TRbTreeNodeBase* TRbGlobal<TDummy>::RebalanceForErase(TRbTreeNodeBase* z,
         if (x_parent != root) {
             DecrementChildrenUntilRoot(x_parent->Parent_, root);
         }
-        y = z;
-        // y now points to node to be actually deleted
-    } else {
-        // y == z
-        x_parent = y->Parent_;
-        if (x)
-            x->Parent_ = y->Parent_;
-        if (root == z)
-            root = x;
-        else {
-            if (z->Parent_->Left_ == z)
-                z->Parent_->Left_ = x;
-            else
-                z->Parent_->Right_ = x;
-            DecrementChildrenUntilRoot(z->Parent_, root); // we lost y
-        }
-
-        if (leftmost == z) {
+        y = z; 
+        // y now points to node to be actually deleted 
+    } else { 
+        // y == z 
+        x_parent = y->Parent_; 
+        if (x) 
+            x->Parent_ = y->Parent_; 
+        if (root == z) 
+            root = x; 
+        else { 
+            if (z->Parent_->Left_ == z) 
+                z->Parent_->Left_ = x; 
+            else 
+                z->Parent_->Right_ = x; 
+            DecrementChildrenUntilRoot(z->Parent_, root); // we lost y 
+        } 
+ 
+        if (leftmost == z) { 
             if (z->Right_ == nullptr) // z->mLeft must be null also
-                leftmost = z->Parent_;
-            // makes leftmost == _M_header if z == root
-            else
-                leftmost = TRbTreeNodeBase::MinimumNode(x);
-        }
-        if (rightmost == z) {
+                leftmost = z->Parent_; 
+            // makes leftmost == _M_header if z == root 
+            else 
+                leftmost = TRbTreeNodeBase::MinimumNode(x); 
+        } 
+        if (rightmost == z) { 
             if (z->Left_ == nullptr) // z->mRight must be null also
-                rightmost = z->Parent_;
-            // makes rightmost == _M_header if z == root
-            else // x == z->mLeft
-                rightmost = TRbTreeNodeBase::MaximumNode(x);
-        }
-    }
-
-    if (y->Color_ != RBTreeRed) {
+                rightmost = z->Parent_; 
+            // makes rightmost == _M_header if z == root 
+            else // x == z->mLeft 
+                rightmost = TRbTreeNodeBase::MaximumNode(x); 
+        } 
+    } 
+ 
+    if (y->Color_ != RBTreeRed) { 
         while (x != root && (x == nullptr || x->Color_ == RBTreeBlack))
-            if (x == x_parent->Left_) {
-                TRbTreeNodeBase* w = x_parent->Right_;
-                if (w->Color_ == RBTreeRed) {
-                    w->Color_ = RBTreeBlack;
-                    x_parent->Color_ = RBTreeRed;
-                    RotateLeft(x_parent, root);
-                    w = x_parent->Right_;
-                }
+            if (x == x_parent->Left_) { 
+                TRbTreeNodeBase* w = x_parent->Right_; 
+                if (w->Color_ == RBTreeRed) { 
+                    w->Color_ = RBTreeBlack; 
+                    x_parent->Color_ = RBTreeRed; 
+                    RotateLeft(x_parent, root); 
+                    w = x_parent->Right_; 
+                } 
                 if ((w->Left_ == nullptr ||
-                     w->Left_->Color_ == RBTreeBlack) &&
+                     w->Left_->Color_ == RBTreeBlack) && 
                     (w->Right_ == nullptr ||
-                     w->Right_->Color_ == RBTreeBlack))
-                {
-                    w->Color_ = RBTreeRed;
-                    x = x_parent;
-                    x_parent = x_parent->Parent_;
-                } else {
-                    if (w->Right_ == nullptr || w->Right_->Color_ == RBTreeBlack) {
-                        if (w->Left_)
-                            w->Left_->Color_ = RBTreeBlack;
-                        w->Color_ = RBTreeRed;
-                        RotateRight(w, root);
-                        w = x_parent->Right_;
-                    }
-                    w->Color_ = x_parent->Color_;
-                    x_parent->Color_ = RBTreeBlack;
-                    if (w->Right_)
-                        w->Right_->Color_ = RBTreeBlack;
-                    RotateLeft(x_parent, root);
-                    break;
-                }
-            } else {
-                // same as above, with mRight <-> mLeft.
-                TRbTreeNodeBase* w = x_parent->Left_;
-                if (w->Color_ == RBTreeRed) {
-                    w->Color_ = RBTreeBlack;
-                    x_parent->Color_ = RBTreeRed;
-                    RotateRight(x_parent, root);
-                    w = x_parent->Left_;
-                }
+                     w->Right_->Color_ == RBTreeBlack)) 
+                { 
+                    w->Color_ = RBTreeRed; 
+                    x = x_parent; 
+                    x_parent = x_parent->Parent_; 
+                } else { 
+                    if (w->Right_ == nullptr || w->Right_->Color_ == RBTreeBlack) { 
+                        if (w->Left_) 
+                            w->Left_->Color_ = RBTreeBlack; 
+                        w->Color_ = RBTreeRed; 
+                        RotateRight(w, root); 
+                        w = x_parent->Right_; 
+                    } 
+                    w->Color_ = x_parent->Color_; 
+                    x_parent->Color_ = RBTreeBlack; 
+                    if (w->Right_) 
+                        w->Right_->Color_ = RBTreeBlack; 
+                    RotateLeft(x_parent, root); 
+                    break; 
+                } 
+            } else { 
+                // same as above, with mRight <-> mLeft. 
+                TRbTreeNodeBase* w = x_parent->Left_; 
+                if (w->Color_ == RBTreeRed) { 
+                    w->Color_ = RBTreeBlack; 
+                    x_parent->Color_ = RBTreeRed; 
+                    RotateRight(x_parent, root); 
+                    w = x_parent->Left_; 
+                } 
                 if ((w->Right_ == nullptr ||
-                     w->Right_->Color_ == RBTreeBlack) &&
+                     w->Right_->Color_ == RBTreeBlack) && 
                     (w->Left_ == nullptr ||
-                     w->Left_->Color_ == RBTreeBlack))
-                {
-                    w->Color_ = RBTreeRed;
-                    x = x_parent;
-                    x_parent = x_parent->Parent_;
-                } else {
-                    if (w->Left_ == nullptr || w->Left_->Color_ == RBTreeBlack) {
-                        if (w->Right_)
-                            w->Right_->Color_ = RBTreeBlack;
-                        w->Color_ = RBTreeRed;
-                        RotateLeft(w, root);
-                        w = x_parent->Left_;
-                    }
-                    w->Color_ = x_parent->Color_;
-                    x_parent->Color_ = RBTreeBlack;
-                    if (w->Left_)
-                        w->Left_->Color_ = RBTreeBlack;
-                    RotateRight(x_parent, root);
-                    break;
-                }
-            }
-        if (x)
-            x->Color_ = RBTreeBlack;
-    }
-    return y;
-}
-
-template <class TDummy>
-TRbTreeNodeBase* TRbGlobal<TDummy>::DecrementNode(TRbTreeNodeBase* Node_) {
-    if (Node_->Color_ == RBTreeRed && Node_->Parent_->Parent_ == Node_)
-        Node_ = Node_->Right_;
+                     w->Left_->Color_ == RBTreeBlack)) 
+                { 
+                    w->Color_ = RBTreeRed; 
+                    x = x_parent; 
+                    x_parent = x_parent->Parent_; 
+                } else { 
+                    if (w->Left_ == nullptr || w->Left_->Color_ == RBTreeBlack) { 
+                        if (w->Right_) 
+                            w->Right_->Color_ = RBTreeBlack; 
+                        w->Color_ = RBTreeRed; 
+                        RotateLeft(w, root); 
+                        w = x_parent->Left_; 
+                    } 
+                    w->Color_ = x_parent->Color_; 
+                    x_parent->Color_ = RBTreeBlack; 
+                    if (w->Left_) 
+                        w->Left_->Color_ = RBTreeBlack; 
+                    RotateRight(x_parent, root); 
+                    break; 
+                } 
+            } 
+        if (x) 
+            x->Color_ = RBTreeBlack; 
+    } 
+    return y; 
+} 
+ 
+template <class TDummy> 
+TRbTreeNodeBase* TRbGlobal<TDummy>::DecrementNode(TRbTreeNodeBase* Node_) { 
+    if (Node_->Color_ == RBTreeRed && Node_->Parent_->Parent_ == Node_) 
+        Node_ = Node_->Right_; 
     else if (Node_->Left_ != nullptr) {
-        Node_ = TRbTreeNodeBase::MaximumNode(Node_->Left_);
-    } else {
-        TBasePtr y = Node_->Parent_;
-        while (Node_ == y->Left_) {
-            Node_ = y;
-            y = y->Parent_;
-        }
-        Node_ = y;
-    }
-    return Node_;
-}
-
-template <class TDummy>
-TRbTreeNodeBase* TRbGlobal<TDummy>::IncrementNode(TRbTreeNodeBase* Node_) {
+        Node_ = TRbTreeNodeBase::MaximumNode(Node_->Left_); 
+    } else { 
+        TBasePtr y = Node_->Parent_; 
+        while (Node_ == y->Left_) { 
+            Node_ = y; 
+            y = y->Parent_; 
+        } 
+        Node_ = y; 
+    } 
+    return Node_; 
+} 
+ 
+template <class TDummy> 
+TRbTreeNodeBase* TRbGlobal<TDummy>::IncrementNode(TRbTreeNodeBase* Node_) { 
     if (Node_->Right_ != nullptr) {
-        Node_ = TRbTreeNodeBase::MinimumNode(Node_->Right_);
-    } else {
-        TBasePtr y = Node_->Parent_;
-        while (Node_ == y->Right_) {
-            Node_ = y;
-            y = y->Parent_;
-        }
-        // check special case: This is necessary if mNode is the
-        // _M_head and the tree contains only a single node y. In
-        // that case parent, left and right all point to y!
-        if (Node_->Right_ != y)
-            Node_ = y;
-    }
-    return Node_;
-}
-
-#undef RBTreeRed
-#undef RBTreeBlack
+        Node_ = TRbTreeNodeBase::MinimumNode(Node_->Right_); 
+    } else { 
+        TBasePtr y = Node_->Parent_; 
+        while (Node_ == y->Right_) { 
+            Node_ = y; 
+            y = y->Parent_; 
+        } 
+        // check special case: This is necessary if mNode is the 
+        // _M_head and the tree contains only a single node y. In 
+        // that case parent, left and right all point to y! 
+        if (Node_->Right_ != y) 
+            Node_ = y; 
+    } 
+    return Node_; 
+} 
+ 
+#undef RBTreeRed 
+#undef RBTreeBlack