Changeset 4075
- Timestamp:
- Aug 20, 2021, 8:54:37 AM (18 months ago)
- Location:
- branches/kendall-score/yat/utility/ranking
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/kendall-score/yat/utility/ranking/Impl.cc
r4072 r4075 70 70 void Impl::move_data(Impl&& from) 71 71 { 72 // FIXME we need to clean up before the move72 assert(empty()); 73 73 74 74 head_.parent_ = from.head_.parent_; … … 147 147 void Impl::reset(void) 148 148 { 149 // FIXME do we need to destruct parent and rest of tree?150 149 head_.parent_ = nullptr; 151 150 head_.left_ = nullptr; … … 355 354 356 355 357 NodeBase* Impl::rebalance_old_root(NodeBase* node)358 {359 if (node->balance() > 1) {360 // height(y) > height(T4) + 1361 // i.e. height(x) > height(T4)362 363 // left left case364 if (node->left_->balance() >= 0) {365 assert(height(node->left_) > height(node->right_) + 1);366 // height(x) > height(T4)367 assert(height(node->left_->left_) > height(node->right_));368 // y is balanced, so:369 // height(T3) <= height(x) <= height(T3)+1370 assert(height(node->left_->left_) >= height(node->left_->right_));371 assert(height(node->left_->left_) <= height(node->left_->right_)+1);372 // x is balanced, so |height(T1)-height(T2)| <= 1373 374 node = right_rotate(node);375 }376 else { // left right case377 left_rotate(node->left_);378 node = right_rotate(node);379 }380 return rebalance_old_root(node);381 }382 383 if (node->balance() >= -1)384 return node;385 386 assert(0);387 return node;388 }389 390 391 356 NodeBase* Impl::right_rotate(NodeBase* y) 392 357 { -
branches/kendall-score/yat/utility/ranking/Impl.h
r4072 r4075 48 48 Impl& operator=(Impl&& rhs); 49 49 50 // FIXME51 // Head is the only node with no value. Its parent is the root52 // node and the rest of the tree is in the left branch from the53 // root. Also, it holds a link to the leftmost node, which54 // corresponds to begin()50 // Head is the only node with no parent; it is also the node 51 // with no value. All other nodes are NodeValue<T> pointers. Its 52 // left child is the root node and it also holds a short cut to 53 // the leftmost node to allow constant access and creating of 54 // the begin() iterator. 55 55 NodeBase head_; 56 56 … … 62 62 NodeBase*& left_most(void); 63 63 const NodeBase* left_most(void) const; 64 65 66 /*67 68 */69 NodeBase* rebalance_old_root(NodeBase* node);70 64 71 65 /*
Note: See TracChangeset
for help on using the changeset viewer.