Changeset 4079
- Timestamp:
- Aug 26, 2021, 10:38:04 AM (18 months ago)
- Location:
- branches/kendall-score/yat/utility
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/kendall-score/yat/utility/Ranking.h
r4077 r4079 523 523 impl_.head_.left_ = impl_.root_node(); 524 524 impl_.head_.right_ = impl_.root_node(); 525 impl_.right_most() = impl_.root_node(); 525 526 impl_.head_.update_height(); 526 527 impl_.head_.update_size(); … … 806 807 head_node()->update_height(); 807 808 head_node()->update_size(); 809 if (root_node()) 810 impl_.right_most() = root_node()->right_most(); 811 else 812 impl_.right_most() = head_node(); 808 813 YAT_ASSERT(validate()); 809 814 return root; -
branches/kendall-score/yat/utility/ranking/Impl.cc
r4077 r4079 77 77 head_.left_->parent_ = &head_; 78 78 head_.right_ = from.head_.right_; 79 } 80 else 79 right_most_ = root_node()->right_most(); 80 } 81 else { 81 82 head_.right_ = &head_; 83 right_most() = &head_; 84 } 82 85 head_.height_ = from.head_.height_; 83 86 head_.size_ = from.head_.size_; … … 120 123 121 124 // update pointer to left_most node 122 if (head_.left_ == node) { 123 head_.left_ = child ? child : node->parent_; 124 } 125 if (left_most() == node) 126 left_most() = child ? child : node->parent_; 127 if (right_most() == node) 128 right_most() = child ? child : node->parent_; 125 129 assert(child==nullptr || child->is_left_node() || child->is_right_node()); 126 130 } … … 150 154 head_.left_ = nullptr; 151 155 head_.right_ = &head_; // most left node 156 right_most_ = &head_; 152 157 head_.update_height(); 153 158 head_.update_size(); … … 201 206 parent.right_ = element.release(); 202 207 child = parent.right_; 208 if (&parent == right_most()) 209 right_most() = child; 203 210 } 204 211 … … 426 433 } 427 434 435 if (root_node()) { 436 if (left_most() != root_node()->left_most()) { 437 std::cerr << "leftmost incorrect\n"; 438 return false; 439 } 440 if (right_most() != root_node()->right_most()) { 441 std::cerr << "rightmost incorrect\n"; 442 return false; 443 } 444 } 445 428 446 429 447 /* … … 467 485 468 486 469 NodeBase* Impl::right_most(void) 470 { 471 // FIXME this scaled logN, make it constant time 472 return root_node()->right_most(); 487 NodeBase*& Impl::right_most(void) 488 { 489 return right_most_; 473 490 } 474 491 … … 476 493 const NodeBase* Impl::right_most(void) const 477 494 { 478 // FIXME this scaled logN, make it constant time 479 return root_node()->right_most(); 495 return right_most_; 480 496 } 481 497 -
branches/kendall-score/yat/utility/ranking/Impl.h
r4077 r4079 62 62 NodeBase*& left_most(void); 63 63 const NodeBase* left_most(void) const; 64 NodeBase* right_most(void);64 NodeBase*& right_most(void); 65 65 const NodeBase* right_most(void) const; 66 66 … … 126 126 NodeBase* right_rotate(NodeBase* y); 127 127 private: 128 NodeBase* right_most_; 128 129 void move_data(Impl&&); 129 130 void erase_rebalance(NodeBase* node);
Note: See TracChangeset
for help on using the changeset viewer.