Changeset 4071
- Timestamp:
- Aug 18, 2021, 4:31:29 AM (18 months ago)
- Location:
- branches/kendall-score/yat/utility
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/kendall-score/yat/utility/Ranking.h
r4070 r4071 234 234 bool empty(void) const 235 235 { 236 return size()==0;236 return root_node() == nullptr; 237 237 } 238 238 … … 346 346 size_t ranking(const_iterator it) const 347 347 { 348 // FIXME 349 return std::distance(cbegin(), it); 348 return impl_.ranking(it.node_); 350 349 } 351 350 … … 356 355 size_t size(void) const 357 356 { 358 return impl_.node_count_;357 return root_node() ? root_node()->size_ : 0; 359 358 } 360 359 … … 363 362 ranking::Impl impl_; 364 363 365 void print(const ranking::NodeBase* p ) const364 void print(const ranking::NodeBase* p, std::ostream& os) const 366 365 { 367 366 if (p) { 368 367 if (p->is_head_node()==false) { 369 print(p->right_ );370 } 371 std::cerr<< std::string(p->generation()*4, ' ');368 print(p->right_, os); 369 } 370 os << std::string(p->generation()*4, ' '); 372 371 if (!p->is_head_node()) 373 std::cerr << static_cast<const ranking::NodeValue<T>*>(p)->value();372 os << value(p); 374 373 else 375 std::cerr<< "H";376 std::cerr<< ": "374 os << "H"; 375 os << ": " 377 376 << p->parent_ << " " 378 377 << p << " " … … 380 379 << p->right_ << "\n"; 381 380 if (p->is_head_node()==false) { 382 print(p->left_ );381 print(p->left_, os); 383 382 } 384 383 if (p->parent_ && !p->is_left_node() && !p->is_right_node()) { 385 std::cerr<< "print error: " << p << "\n";384 os << "print error: " << p << "\n"; 386 385 exit(1); 387 386 } … … 495 494 root_node() = element.release(); 496 495 root_node()->right_ = &impl_.head_; 496 root_node()->height_ = 1; 497 root_node()->size_ = 1; 497 498 impl_.head_.left_ = root_node(); 498 ++impl_.node_count_; 499 499 500 YAT_ASSERT(root_node()->validate()); 500 501 YAT_ASSERT(impl_.head_.validate()); … … 508 509 509 510 // element right of root 510 if (!compare_(element->value(), 511 static_cast<ranking::NodeValue<T>*>(x)->value())) { 511 if (!compare_(element->value(), value(x))) { 512 512 // make new root parent of head 513 513 impl_.head_.parent_ = element.release(); … … 518 518 impl_.head_.parent_->left_ = x; 519 519 x->parent_ = impl_.head_.parent_; 520 521 ++impl_.node_count_; 520 YAT_ASSERT(x->size_ > 0); 521 522 impl_.head_.parent_->size_ = x->size_ + 1; 523 impl_.head_.parent_->height_ = x->height_ + 1; 524 522 525 YAT_ASSERT(x->validate()); 523 526 YAT_ASSERT(impl_.head_.parent_); … … 533 536 while (true) { 534 537 parent = x; 535 if (compare_(element->value(), 536 static_cast<ranking::NodeValue<T>*>(x)->value())) { 538 if (compare_(element->value(), value(x))) { 537 539 x = x->left_; 538 540 if (x == nullptr) { 539 541 element->parent_ = parent; 540 542 parent->left_ = element.release(); 543 parent->increment_size(); 544 parent->update_height(); 541 545 if (impl_.head_.left_ == parent) 542 546 impl_.head_.left_ = parent->left_; 543 ++impl_.node_count_;544 547 YAT_ASSERT(validate()); 545 548 return result; … … 551 554 element->parent_ = parent; 552 555 parent->right_ = element.release(); 553 ++impl_.node_count_; 556 parent->increment_size(); 557 parent->update_height(); 554 558 YAT_ASSERT(validate()); 555 559 return result; … … 667 671 668 672 673 const T& value(const ranking::NodeBase* p) const 674 { 675 YAT_ASSERT(p); 676 YAT_ASSERT(!p->is_head_node()); 677 return static_cast<const ranking::NodeValue<T>*>(p)->value(); 678 } 679 680 669 681 bool validate(void) const 670 682 { 671 683 #ifdef YAT_DEBUG_RANKING 672 return impl_.validate(); 684 if (!impl_.validate()) 685 return false; 686 bool ok = true; 687 size_t rank = 0; 688 for (auto it = cbegin(); it!=cend(); ++it) { 689 size_t r = ranking(it); 690 if (r != rank) { 691 std::cerr << "ranking: " << r << "; expected: " << rank << "\n"; 692 std::cerr << "size: " << it.node_->size_ << "\n"; 693 std::cerr << it.node_->parent_ << " " 694 << it.node_->is_left_node() << " " 695 << it.node_->is_right_node() << "\n---\n"; 696 ok = false; 697 } 698 ++rank; 699 } 700 return ok; 673 701 #else 674 702 return true; … … 733 761 last_node()->left_ = root->left_most(); 734 762 last_node()->parent_ = root; 735 impl_.node_count_ = other.size();736 763 YAT_ASSERT(validate()); 737 764 return root; … … 745 772 YAT_ASSERT(x); 746 773 ranking::NodeValue<T>* root = clone_node(x); 774 root->height_ = x->height_; 775 root->size_ = x->size_; 747 776 YAT_ASSERT(root); 748 777 root->parent_ = parent; … … 758 787 while (x) { 759 788 ranking::NodeValue<T>* y = clone_node(x); 789 y->height_ = x->height_; 790 y->size_ = x->size_; 760 791 parent->left_ = y; 761 792 y->parent_ = parent; … … 795 826 YAT_ASSERT(p != end()); 796 827 const ranking::NodeBase* node = p.node_; 828 // std::cerr << "erase_node: " << node << "\n"; 797 829 YAT_ASSERT(node); 798 830 799 831 // two children 800 832 if (node->left_ && node->right_) { 833 // When node has two branches, we take the most leftmost node in 834 // the right branch and place in nodes place. 801 835 ranking::NodeBase* leftmost = node->right_->left_most(); 802 836 YAT_ASSERT(leftmost->left_ == nullptr); 803 if (leftmost->parent_ != node) 837 838 // If the leftmost node has a kid, we need to relink the kid 839 // with its grand parent 840 if (leftmost->parent_ != node) { 804 841 impl_.relink(leftmost, leftmost->right_); 842 } 805 843 impl_.relink(node, leftmost); 844 YAT_ASSERT(leftmost->left_ == node->left_); 845 YAT_ASSERT(!leftmost->left_ || leftmost->left_->parent_==leftmost); 846 leftmost->update_height(); 847 leftmost->size_ = 848 1 + ranking::size(leftmost->left_) + ranking::size(leftmost->right_); 849 leftmost->parent_->decrement_size(); 850 YAT_ASSERT(validate()); 806 851 } 807 852 else { 808 853 // single child node is simple, the child takes the node's place 809 854 impl_.relink(node, node->left_ ? node->left_ : node->right_); 855 node->parent_->decrement_size(); 856 node->parent_->update_height(); 857 YAT_ASSERT(validate()); 810 858 } 811 859 // FIXME we need to delete the node, but be careful to not delete 812 860 // any of ots children; perhaps const_cast first? 813 861 814 --impl_.node_count_;815 YAT_ASSERT(validate());816 862 } 817 863 -
branches/kendall-score/yat/utility/ranking/Impl.cc
r4070 r4071 63 63 assert(head_.right_ == &head_); 64 64 head_.parent_->right_ = &head_; 65 node_count_ = from.node_count_; 65 head_.height_ = from.head_.height_; 66 head_.size_ = from.head_.size_; 66 67 from.reset(); 67 68 assert(validate()); … … 90 91 assert(!child->left_); 91 92 child->left_ = node->left_; 93 if (node->left_) 94 node->left_->parent_ = child; 92 95 } 93 96 if (node->right_ && node->right_!=child) { 94 97 assert(!child->right_); 95 98 child->right_ = node->right_; 99 if (node->right_) 100 node->right_->parent_ = child; 96 101 } 97 102 } … … 105 110 106 111 112 size_t Impl::ranking(const NodeBase* node) const 113 { 114 if (node->is_head_node()) 115 return size(node->parent_); 116 117 // root node 118 if (node->parent_ == nullptr) 119 return size(node->left_); 120 121 // The rank of the parent is the sum of the rank of the 122 // left->child, the child itself, and the size of the child's 123 // right branch. 124 if (node->is_left_node()) 125 return ranking(node->parent_) - (1 + size(node->right_)); 126 127 // right node 128 return ranking(node->parent_) + 1 + size(node->left_); 129 } 130 131 107 132 void Impl::reset(void) 108 133 { … … 111 136 head_.left_ = &head_; 112 137 head_.right_ = &head_; 113 node_count_ = 0; 138 // we don't count the head node 139 head_.height_ = 0; 140 head_.size_ = 0; 114 141 assert(validate()); 115 142 } … … 118 145 bool Impl::validate(void) const 119 146 { 120 if (node_count_ == 0) { 121 assert(head_.parent_ == nullptr); 147 if (head_.parent_ == nullptr) { 122 148 assert(head_.left_ == &head_); 123 149 assert(head_.right_ == &head_); -
branches/kendall-score/yat/utility/ranking/Impl.h
r4070 r4071 52 52 // corresponds to begin() 53 53 NodeBase head_; 54 size_t node_count_;55 54 // typically only called with assert, YAT_ASSERT or similar 56 55 bool validate(void) const; 56 // return number of nodes left of node, i.e., number of nodes 57 // with value less than node->value. 58 size_t ranking(const NodeBase* node) const; 57 59 void reset(void); 58 60 /* -
branches/kendall-score/yat/utility/ranking/NodeBase.h
r4070 r4071 25 25 // This is a private file used by yat/utility/Ranking.h 26 26 27 #include <cstddef> 28 27 29 namespace theplu { 28 30 namespace yat { … … 42 44 NodeBase* left_; 43 45 NodeBase* right_; 46 unsigned int height_; // max distance to leaf (plus 1) 47 // number of total offsprings including myself 48 size_t size_; 44 49 45 50 // return 0 for root, 1 for its children, etc 46 51 int generation(void) const; 52 53 // increase size of node and parent node, recursively. 54 void increment_size(void); 55 // decrease size of node and parent node, recursively. 56 void decrement_size(void); 57 58 void update_height(void); 47 59 48 60 // return true if head node … … 66 78 bool recursive_validate(void) const; 67 79 }; 80 81 size_t height(const NodeBase* node); 82 size_t size(const NodeBase* node); 83 68 84 } // end of namespace ranking 69 85
Note: See TracChangeset
for help on using the changeset viewer.