diff options
| author | denplusplus <denplusplus@yandex-team.ru> | 2022-02-10 16:47:34 +0300 |
|---|---|---|
| committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:47:34 +0300 |
| commit | 57c20d143e8a438cd76b9fdc3ca2e8ee3ac1f32a (patch) | |
| tree | cc63639f8e502db19a82c20e2861c6d1edbf9fea /library/cpp/containers/intrusive_rb_tree/rb_tree.h | |
| parent | 464ba3814a83db4f2d5327393b0b6eaf0c86bfd7 (diff) | |
| download | ydb-57c20d143e8a438cd76b9fdc3ca2e8ee3ac1f32a.tar.gz | |
Restoring authorship annotation for <denplusplus@yandex-team.ru>. Commit 1 of 2.
Diffstat (limited to 'library/cpp/containers/intrusive_rb_tree/rb_tree.h')
| -rw-r--r-- | library/cpp/containers/intrusive_rb_tree/rb_tree.h | 38 |
1 files changed, 19 insertions, 19 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..0a833ae223 100644 --- a/library/cpp/containers/intrusive_rb_tree/rb_tree.h +++ b/library/cpp/containers/intrusive_rb_tree/rb_tree.h @@ -16,7 +16,7 @@ struct TRbTreeNodeBase { TBasePtr Parent_; TBasePtr Left_; TBasePtr Right_; - size_t Children_; + size_t Children_; inline TRbTreeNodeBase() noexcept { ReInitNode(); @@ -27,7 +27,7 @@ struct TRbTreeNodeBase { Parent_ = nullptr; Left_ = nullptr; Right_ = nullptr; - Children_ = 1; + Children_ = 1; } static TBasePtr MinimumNode(TBasePtr x) { @@ -43,19 +43,19 @@ struct TRbTreeNodeBase { return x; } - - static TBasePtr ByIndex(TBasePtr x, size_t index) { + + static TBasePtr ByIndex(TBasePtr x, size_t index) { if (x->Left_ != nullptr) { - if (index < x->Left_->Children_) - return ByIndex(x->Left_, index); - index -= x->Left_->Children_; - } - if (0 == index) - return x; - if (!x->Right_) - ythrow yexception() << "index not found"; - return ByIndex(x->Right_, index - 1); - } + if (index < x->Left_->Children_) + return ByIndex(x->Left_, index); + index -= x->Left_->Children_; + } + if (0 == index) + return x; + if (!x->Right_) + ythrow yexception() << "index not found"; + return ByIndex(x->Right_, index - 1); + } }; struct TRbTreeBaseIterator; @@ -397,7 +397,7 @@ public: return y; } - + template <class T1> inline size_t LessCount(const T1& k) const { auto x = LowerBound(k); @@ -544,8 +544,8 @@ void TRbGlobal<TDummy>::RotateLeft(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) { 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; + y->Children_ = x->Children_; + x->Children_ = ((x->Left_) ? x->Left_->Children_ : 0) + ((x->Right_) ? x->Right_->Children_ : 0) + 1; } template <class TDummy> @@ -564,8 +564,8 @@ void TRbGlobal<TDummy>::RotateRight(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) 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; + y->Children_ = x->Children_; + x->Children_ = ((x->Left_) ? x->Left_->Children_ : 0) + ((x->Right_) ? x->Right_->Children_ : 0) + 1; } template <class TDummy> |