1 #ifndef theplu_yat_utility_ranking 2 #define theplu_yat_utility_ranking 25 #include "ranking/Impl.h" 26 #include "ranking/Iterator.h" 27 #include "ranking/NodeBase.h" 28 #include "ranking/NodeValue.h" 30 #include "yat_assert.h" 48 template<
typename T,
class Compare = std::less<T> >
94 YAT_ASSERT(validate());
234 YAT_ASSERT(root_node() != head_node());
255 return impl_.empty();
306 std::unique_ptr<ranking::NodeValue<T>>
307 newnode(
new ranking::NodeValue<T>(element));
308 return insert(std::move(newnode));
320 std::unique_ptr<ranking::NodeValue<T>>
321 newnode(
new ranking::NodeValue<T>(std::move(element)));
322 return insert(std::move(newnode));
335 std::unique_ptr<ranking::NodeValue<T>>
336 newnode(
new ranking::NodeValue<T>(element));
337 return insert(hint, std::move(newnode));
349 std::unique_ptr<ranking::NodeValue<T>>
350 newnode(
new ranking::NodeValue<T>(std::move(element)));
351 return insert(hint, std::move(newnode));
362 template<
typename InputIterator>
363 void insert(InputIterator first, InputIterator last)
365 for (; first!=last; ++first)
403 YAT_ASSERT(it.node_);
404 return impl_.ranking(it.node_);
424 insert_and_rebalance(std::unique_ptr<ranking::NodeValue<T>>&& element,
425 ranking::NodeBase& parent,
bool left)
428 impl_.insert_and_rebalance(std::move(element), parent, left);
429 YAT_ASSERT(validate());
435 void print(
const ranking::NodeBase* p, std::ostream& os)
const 438 if (p->is_head_node()==
false) {
439 print(p->right_, os);
441 os << std::string(p->generation()*4,
' ');
442 if (!p->is_head_node())
446 os <<
", H=" << ranking::height(p) <<
", S=" << ranking::size(p);
451 << p->right_ <<
"\n";
452 if (p->is_head_node()==
false) {
455 if (p->parent_ && !p->is_left_node() && !p->is_right_node()) {
456 os <<
"print error: " << p <<
"\n";
463 ranking::NodeValue<T>*
464 clone_node(
const ranking::NodeValue<T>* x)
const;
472 ranking::NodeValue<T>* copy(
const Ranking& other);
477 ranking::NodeValue<T>* copy(
const ranking::NodeValue<T>* root)
const;
485 const ranking::NodeValue<T>* root_node(
void)
const 487 return static_cast<const ranking::NodeValue<T>*
>(impl_.root_node());
491 ranking::NodeValue<T>* root_node(
void)
493 return static_cast<ranking::NodeValue<T>*
>(impl_.root_node());
497 const ranking::NodeBase* head_node(
void)
const 503 ranking::NodeBase* head_node(
void)
509 const ranking::NodeValue<T>*
510 left(
const ranking::NodeBase* x)
const 512 YAT_ASSERT(x->left_ != &impl_.head_);
513 return static_cast<const ranking::NodeValue<T>*
>(x->left_);
517 ranking::NodeValue<T>*
518 left(ranking::NodeBase* x)
const 520 YAT_ASSERT(x->left_ != &impl_.head_);
521 return static_cast<ranking::NodeValue<T>*
>(x->left_);
525 const ranking::NodeValue<T>*
526 right(
const ranking::NodeBase* x)
const 528 YAT_ASSERT(x->right_ != &impl_.head_);
529 return static_cast<const ranking::NodeValue<T>*
>(x->right_);
533 ranking::NodeValue<T>*
534 right(ranking::NodeBase* x)
const 536 YAT_ASSERT(x->right_ != &impl_.head_);
537 return static_cast<ranking::NodeValue<T>*
>(x->right_);
542 void erase(ranking::NodeValue<T>* x)
const 547 ranking::NodeValue<T>* tmp = left(x);
562 element->parent_ = &impl_.head_;
563 impl_.root_node() = element.release();
564 impl_.head_.left_ = impl_.root_node();
565 impl_.head_.right_ = impl_.root_node();
566 impl_.right_most() = impl_.root_node();
567 impl_.head_.update_height();
568 impl_.head_.update_size();
570 YAT_ASSERT(impl_.root_node()->parent_);
571 YAT_ASSERT(impl_.root_node()->parent_ == &impl_.head_);
572 YAT_ASSERT(impl_.root_node()->is_left_node());
574 YAT_ASSERT(validate());
578 return insert(impl_.root_node(), std::move(element));
584 std::unique_ptr<ranking::NodeValue<T>>&& element)
587 YAT_ASSERT(!x->is_head_node());
590 ranking::NodeBase* parent = x;
591 if (compare_(element->value(), value(x))) {
594 return insert_and_rebalance(std::move(element), *parent,
true);
599 return insert_and_rebalance(std::move(element), *parent,
false);
602 YAT_ASSERT(0 &&
"we can't reach here");
608 std::unique_ptr<ranking::NodeValue<T>>&& element)
611 if (hint.node_ == head_node()) {
612 YAT_ASSERT(hint ==
cend());
613 if (
empty() || compare_(element->value(), value(impl_.right_most())))
614 return insert(std::move(element));
615 return insert_and_rebalance(std::move(element), *impl_.right_most(),
619 YAT_ASSERT(hint !=
end());
622 if (!compare_(*hint, element->value())) {
624 if (hint.node_ == impl_.left_most()) {
625 YAT_ASSERT(hint ==
cbegin());
626 return insert_and_rebalance(std::move(element),
632 YAT_ASSERT(hint !=
cbegin());
633 auto before = std::prev(hint);
634 if (!compare_(element->value(), *before)) {
635 return insert(const_cast<ranking::NodeBase*>(hint.node_),
639 return insert(std::move(element));
644 YAT_ASSERT(compare_(*hint, element->value()));
646 if (hint.node_ == impl_.right_most()) {
647 return insert_and_rebalance(std::move(element),
651 auto after = std::next(hint);
652 YAT_ASSERT(after !=
cend());
654 if (!compare_(*after, element->value())) {
655 return insert(const_cast<ranking::NodeBase*>(after.node_),
660 return insert(std::move(element));
669 lower_bound(
const ranking::NodeValue<T>* x,
const ranking::NodeBase* y,
678 if (!compare_(x->value(), key)) {
692 YAT_ASSERT(y==head_node() || !compare_(value(y), key));
694 YAT_ASSERT(y->left_==
nullptr ||
695 compare_(value(y->left_->right_most()), key));
700 const ranking::NodeValue<T>* parent(
const ranking::NodeBase* x)
const 703 YAT_ASSERT(x->parent_);
704 YAT_ASSERT(x->parent_ != &impl_.head_);
705 return static_cast<const ranking::NodeValue<T>*
>(x->parent_);
709 ranking::NodeValue<T>* parent(ranking::NodeBase* x)
const 712 YAT_ASSERT(x->parent_);
713 YAT_ASSERT(x->parent_ != &impl_.head_);
714 return static_cast<ranking::NodeValue<T>*
>(x->parent_);
723 upper_bound(
const ranking::NodeValue<T>* x,
const ranking::NodeBase* y,
732 if (compare_(key, x->value())) {
746 YAT_ASSERT(y==head_node() || compare_(key, value(y)));
750 YAT_ASSERT(y->left_==
nullptr ||
751 !compare_(key, value(y->left_->right_most())));
756 const T& value(
const ranking::NodeBase* p)
const 759 YAT_ASSERT(!p->is_head_node());
760 return static_cast<const ranking::NodeValue<T>*
>(p)->value();
764 bool validate(
void)
const 766 #ifndef YAT_DEBUG_RANKING 769 if (!impl_.validate()) {
770 std::cerr <<
"Impl::validate failed\n";
776 YAT_ASSERT(
cbegin().node_);
777 YAT_ASSERT(
cend().node_);
781 std::cerr <<
"ranking: " << r <<
"; expected: " << rank <<
"\n";
782 std::cerr <<
"size: " << it.node_->size_ <<
"\n";
783 std::cerr << it.node_->parent_ <<
" " 784 << it.node_->is_left_node() <<
" " 785 << it.node_->is_right_node() <<
"\n---\n";
801 template<
typename T,
typename C>
803 : compare_(other.compare())
806 impl_.root_node() = copy(other);
807 YAT_ASSERT(validate());
811 template<
typename T,
typename C>
813 : compare_(
std::move(other.compare())), impl_(
std::move(other.impl_))
815 YAT_ASSERT(validate());
819 template<
typename T,
typename C>
822 if (
this != &other) {
824 *
this = std::move(tmp);
830 template<
typename T,
typename C>
834 compare_ = std::move(other.compare_);
835 impl_ = std::move(other.impl_);
840 template<
typename T,
typename C>
841 ranking::NodeValue<T>* Ranking<T,C>::copy(
const Ranking& other)
843 YAT_ASSERT(other.root_node());
844 ranking::NodeValue<T>* root = copy(other.root_node());
845 root->parent_ = head_node();
846 head_node()->left_ = root;
847 head_node()->right_ = root->left_most();
848 head_node()->update_height();
849 head_node()->update_size();
851 impl_.right_most() = root_node()->right_most();
853 impl_.right_most() = head_node();
854 YAT_ASSERT(validate());
859 template<
typename T,
typename C>
860 ranking::NodeValue<T>*
861 Ranking<T,C>::copy(
const ranking::NodeValue<T>* x)
const 864 ranking::NodeValue<T>* root = clone_node(x);
866 root->height_ = x->height_;
867 root->size_ = x->size_;
871 root->left_ = copy(left(x));
872 root->left_->parent_ = root;
875 root->right_ = copy(right(x));
876 root->right_->parent_ = root;
879 catch (std::exception& e) {
881 std::rethrow_exception(std::current_exception());
887 template<
typename T,
typename C>
888 ranking::NodeValue<T>*
889 Ranking<T,C>::clone_node(
const ranking::NodeValue<T>* x)
const 892 ranking::NodeValue<T>* res =
new ranking::NodeValue<T>(x->value());
893 res->left_ =
nullptr;
894 res->right_ =
nullptr;
895 res->parent_ =
nullptr;
900 template<
typename T,
typename C>
903 YAT_ASSERT(p != end());
904 const ranking::NodeBase* node = p.node_;
907 impl_.erase_and_rebalance(node);
909 YAT_ASSERT(validate());
914 template<
typename T,
typename C>
918 YAT_ASSERT(p != end());
919 const_iterator res = p;
927 template<
typename T,
typename C>
930 auto it = lower_bound(value);
932 while (it!=end() && !compare_(value, *it)) {
940 template<
typename T,
typename C>
945 if (first == cbegin() && last == cend())
948 while (first != last) {
955 template<
typename T,
typename C>
958 auto it = lower_bound(x);
959 if (it != cend() && compare_(x, *it))
reverse_iterator rbegin(void)
Definition: Ranking.h:178
iterator insert(const T &element)
insert an element
Definition: Ranking.h:304
const_iterator cbegin(void) const
Definition: Ranking.h:141
const Compare & compare(void) const
Definition: Ranking.h:244
std::reverse_iterator< const_iterator > const_reverse_iterator
reverse iterator
Definition: Ranking.h:73
iterator begin(void)
Definition: Ranking.h:123
const_reverse_iterator rend(void) const
Definition: Ranking.h:196
const_iterator lower_bound(const T &x) const
Definition: Ranking.h:375
iterator insert(const_iterator hint, T &&element)
insert with hint
Definition: Ranking.h:347
const_iterator end(void) const
Definition: Ranking.h:159
The Department of Theoretical Physics namespace as we define it.
iterator end(void)
Definition: Ranking.h:150
Definition: stl_utility.h:64
void clear(std::vector< T > &vec)
reduce size and capacity to zero
Definition: stl_utility.h:493
const_iterator begin(void) const
Definition: Ranking.h:132
const_iterator find(const T &x) const
Compare key_compare
type used to compare elements
Definition: Ranking.h:55
T value_type
value type
Definition: Ranking.h:53
iterator erase(const_iterator position)
~Ranking(void)
Destructor.
Definition: Ranking.h:83
ranking::Iterator< T > const_iterator
iterator
Definition: Ranking.h:69
ranking::Iterator< T > iterator
iterator
Definition: Ranking.h:67
iterator insert(const_iterator hint, const T &element)
insert with hint
Definition: Ranking.h:333
void clear(void)
Definition: Ranking.h:231
const_iterator cend(void) const
Definition: Ranking.h:168
const T & reference
reference
Definition: Ranking.h:57
reverse_iterator rend(void)
Definition: Ranking.h:187
bool empty(void) const
Definition: Ranking.h:253
Ranking & operator=(const Ranking &other)
assignment operator
const_reverse_iterator crbegin(void) const
Definition: Ranking.h:214
Ranking(const Compare &c)
Definition: Ranking.h:91
const_reverse_iterator rbegin(void) const
Definition: Ranking.h:205
iterator insert(T &&element)
insert an element
Definition: Ranking.h:318
Ranking(void)=default
Default constructor.
const T & const_reference
reference
Definition: Ranking.h:59
size_t ranking(const_iterator it) const
Definition: Ranking.h:401
const T * pointer
pointer
Definition: Ranking.h:61
size_t size(void) const
Definition: Ranking.h:413
const T * const_pointer
const pointer
Definition: Ranking.h:63
size_t size_type
size type
Definition: Ranking.h:65
const_reverse_iterator crend(void) const
Definition: Ranking.h:222
std::reverse_iterator< iterator > reverse_iterator
reverse iterator
Definition: Ranking.h:71
void insert(InputIterator first, InputIterator last)
insert range
Definition: Ranking.h:363
const_iterator upper_bound(const T &x) const
Definition: Ranking.h:388