source: branches/kendall-score/yat/utility/Ranking.h @ 4077

Last change on this file since 4077 was 4077, checked in by Peter, 19 months ago

implement insert with hint; refs #710

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 20.2 KB
Line 
1#ifndef theplu_yat_utility_ranking
2#define theplu_yat_utility_ranking
3
4// $Id: Ranking.h 4077 2021-08-26 04:07:09Z peter $
5
6/*
7  Copyright (C) 2021 Peter Johansson
8
9  This file is part of the yat library, http://dev.thep.lu.se/yat
10
11  The yat library is free software; you can redistribute it and/or
12  modify it under the terms of the GNU General Public License as
13  published by the Free Software Foundation; either version 3 of the
14  License, or (at your option) any later version.
15
16  The yat library is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19  General Public License for more details.
20
21  You should have received a copy of the GNU General Public License
22  along with yat. If not, see <http://www.gnu.org/licenses/>.
23*/
24
25#include "ranking/Impl.h"
26#include "ranking/Iterator.h"
27#include "ranking/NodeBase.h"
28#include "ranking/NodeValue.h"
29
30#include "yat_assert.h"
31
32#include <cstddef>
33#include <functional>
34#include <iostream>
35#include <iterator>
36#include <memory>
37
38namespace theplu {
39namespace yat {
40namespace utility {
41
42  /**
43     Class is a binary tree with the special extension that it allow
44     fast access to the rank of an element in the tree.
45
46     \since New in yat 0.19
47   */
48  template<typename T, class Compare = std::less<T> >
49  class Ranking
50  {
51  public:
52    /// value type
53    typedef T value_type;
54    /// type used to compare elements
55    typedef Compare key_compare;
56    /// size type
57    typedef size_t size_type;
58    /// iterator
59    typedef ranking::Iterator<T> iterator;
60    /// iterator
61    typedef ranking::Iterator<T> const_iterator;
62    /// reverse iterator
63    typedef std::reverse_iterator<iterator> reverse_iterator;
64    /// reverse iterator
65    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
66
67    /**
68       \brief Default constructor
69     */
70    Ranking(void) = default;
71
72    /**
73       \brief Destructor
74     */
75    ~Ranking(void)
76    {
77      clear();
78    }
79
80    /**
81       Construct empty container with comparison function \c c.
82     */
83    Ranking(const Compare& c)
84      : compare_(c)
85    {
86      YAT_ASSERT(validate());
87    }
88
89
90    /**
91       \brief Copy constructor
92     */
93    Ranking(const Ranking& other);
94
95    /**
96       \brief move constructor
97     */
98    Ranking(Ranking&& other);
99
100    /**
101       \brief assignment operator
102     */
103    Ranking& operator=(const Ranking& other);
104
105    /**
106       \brief move assignment
107     */
108    Ranking& operator=(Ranking&& other);
109
110
111    /**
112       \return iterator pointing to the first element, i.e., the
113       node with the smallest value.
114     */
115    iterator begin(void)
116    {
117      return iterator(impl_.left_most());
118    }
119
120
121    /**
122       \return iterator pointing to the first element
123     */
124    const_iterator begin(void) const
125    {
126      return cbegin();
127    }
128
129
130    /**
131       \return iterator pointing to the first element
132     */
133    const_iterator cbegin(void) const
134    {
135      return const_iterator(impl_.left_most());
136    }
137
138
139    /**
140       \return iterator pointing to one-passed-last element
141     */
142    iterator end(void)
143    {
144      return iterator(&impl_.head_);
145    }
146
147
148    /**
149       \return iterator pointing to one-passed-last element
150     */
151    const_iterator end(void) const
152    {
153      return cend();
154    }
155
156
157    /**
158       \return iterator pointing to one-passed-last element
159     */
160    const_iterator cend(void) const
161    {
162      return const_iterator(&impl_.head_);
163    }
164
165
166    /**
167       \return reverse iterator pointing to first element, i.e., the
168       node with the largest value.
169     */
170    reverse_iterator rbegin(void)
171    {
172      return reverse_iterator(end());
173    }
174
175
176    /**
177       \return reverse iterator pointing to one-passed-last element
178     */
179    reverse_iterator rend(void)
180    {
181      return reverse_iterator(begin());
182    }
183
184
185    /**
186       \return reverse iterator pointing to one-passed-last element
187     */
188    const_reverse_iterator rend(void) const
189    {
190      return crend();
191    }
192
193
194    /**
195       \return reverse iterator pointing to first element
196     */
197    const_reverse_iterator rbegin(void) const
198    {
199      return crbegin();
200    }
201
202
203    /**
204       \return reverse iterator pointing to first element
205     */
206    const_reverse_iterator crbegin(void) const
207    {
208      return const_reverse_iterator(cend());
209    }
210
211    /**
212       \return reverse iterator pointing to the one-passed-last element
213     */
214    const_reverse_iterator crend(void) const
215    {
216      return const_reverse_iterator(cbegin());
217    }
218
219
220    /**
221       Remove all nodes
222     */
223    void clear(void)
224    {
225      if (size()) {
226        YAT_ASSERT(root_node() != head_node());
227        erase(root_node());
228      }
229      impl_.reset();
230    }
231
232
233    /**
234       access comparison function which is used to sort elements
235     */
236    const Compare& compare(void) const
237    {
238      return compare_;
239    }
240
241
242    /**
243       \return true if (and only if) container has zero elements
244     */
245    bool empty(void) const
246    {
247      return impl_.empty();
248    }
249
250
251    /**
252       Remove node pointed to by \c position.
253
254       \return An iterator pointing to the element that follows the
255       last element removed.
256     */
257    iterator erase(const_iterator position);
258
259    /**
260       Erase all elements that are equivalent with \c value
261       \return number of elements removed
262     */
263    size_type erase(const T& value);
264
265    /**
266       Remove elements in range [first, last).
267
268       \return An iterator pointing to the element that follows the
269       last element removed.
270     */
271    iterator erase(const_iterator first, const_iterator last);
272
273    /**
274       Find an element that is equivalent to x
275     */
276    const_iterator find(const T& x) const;
277
278
279    /**
280       \brief insert an element
281     */
282    iterator insert(const T& element)
283    {
284      std::unique_ptr<ranking::NodeValue<T>>
285        newnode(new ranking::NodeValue<T>(element));
286      return insert(std::move(newnode));
287    }
288
289
290    /**
291       \brief insert an element
292     */
293    iterator insert(T&& element)
294    {
295      std::unique_ptr<ranking::NodeValue<T>>
296        newnode(new ranking::NodeValue<T>(std::move(element)));
297      return insert(std::move(newnode));
298    }
299
300
301    /**
302       \brief insert with hint
303
304       If \c hint will follow the inserted element, the insertion is done
305       in constant time. Otherwise, the usual insert function is
306       called which takes logN.
307     */
308    iterator insert(const_iterator hint, const T& element)
309    {
310      std::unique_ptr<ranking::NodeValue<T>>
311        newnode(new ranking::NodeValue<T>(element));
312      return insert(hint, std::move(newnode));
313    }
314
315
316    /**
317       \brief insert with hint
318     */
319    iterator insert(const_iterator hint,  T&& element)
320    {
321      std::unique_ptr<ranking::NodeValue<T>>
322        newnode(new ranking::NodeValue<T>(std::move(element)));
323      return insert(hint, std::move(newnode));
324    }
325
326
327    /**
328       \brief insert range
329     */
330    template<typename InputIterator>
331    void insert(InputIterator first, InputIterator last)
332    {
333      for (; first!=last; ++first)
334        insert(end(), *first);
335    }
336
337
338    /**
339       \return the first element which is equal (or greater) to \c x
340     */
341    const_iterator lower_bound(const T& x) const
342    {
343      if (empty())
344        return cend();
345      return lower_bound(root_node(), head_node(), x);
346    }
347
348
349    /**
350       \return the first element which is greater than \c x
351     */
352    const_iterator upper_bound(const T& x) const
353    {
354      if (empty())
355        return cend();
356      return upper_bound(root_node(), head_node(), x);
357    }
358
359
360    /**
361       \return number of elements smaller than \c it
362     */
363    size_t ranking(const_iterator it) const
364    {
365      YAT_ASSERT(it.node_);
366      return impl_.ranking(it.node_);
367    }
368
369
370    /**
371       \return number of elements in container
372     */
373    size_t size(void) const
374    {
375      return impl_.size();
376    }
377
378  private:
379    Compare compare_;
380    ranking::Impl impl_;
381
382    iterator
383    insert_and_rebalance(std::unique_ptr<ranking::NodeValue<T>>&& element,
384                         ranking::NodeBase& parent, bool left)
385    {
386      iterator result(element.get());
387      impl_.insert_and_rebalance(std::move(element), parent, left);
388      YAT_ASSERT(validate());
389      return result;
390    }
391
392
393
394    void print(const ranking::NodeBase* p, std::ostream& os) const
395    {
396      if (p) {
397        if (p->is_head_node()==false) {
398          print(p->right_, os);
399        }
400        os << std::string(p->generation()*4, ' ');
401        if (!p->is_head_node())
402          os << value(p);
403        else
404          os << "H";
405        os << ", H=" << ranking::height(p) << ", S=" << ranking::size(p);
406        os << ":   "
407           << p->parent_ << " "
408           << p << " "
409           << p->left_ << " "
410           << p->right_ << "\n";
411        if (p->is_head_node()==false) {
412          print(p->left_, os);
413        }
414        if (p->parent_ && !p->is_left_node() && !p->is_right_node()) {
415          os << "print error: " << p << "\n";
416          exit(1);
417        }
418      }
419    }
420
421    // return a copy of x but with children and parent set to nullptr.
422    ranking::NodeValue<T>*
423    clone_node(const ranking::NodeValue<T>* x) const;
424
425    /**
426       copy data in other.Impl_ into impl_
427
428       Basically copy constructor of Impl but nodes (except for head
429       node) are copied as NodeValue<T> and Impl is not aware of T.
430     */
431    ranking::NodeValue<T>* copy(const Ranking& other);
432
433    /**
434       Create a copy of root and return it
435     */
436    ranking::NodeValue<T>* copy(const ranking::NodeValue<T>* root) const;
437
438    /**
439       Remove node position is pointing to
440     */
441    void erase_node(const_iterator position);
442
443    // return the root node
444    const ranking::NodeValue<T>* root_node(void) const
445    {
446      return static_cast<const ranking::NodeValue<T>*>(impl_.root_node());
447    }
448
449
450    ranking::NodeValue<T>* root_node(void)
451    {
452      return static_cast<ranking::NodeValue<T>*>(impl_.root_node());
453    }
454
455
456    const ranking::NodeBase* head_node(void) const
457    {
458      return &impl_.head_;
459    }
460
461
462    ranking::NodeBase* head_node(void)
463    {
464      return &impl_.head_;
465    }
466
467
468    const ranking::NodeValue<T>*
469    left(const ranking::NodeBase* x) const
470    {
471      YAT_ASSERT(x->left_ != &impl_.head_);
472      return static_cast<const ranking::NodeValue<T>*>(x->left_);
473    }
474
475
476    ranking::NodeValue<T>*
477    left(ranking::NodeBase* x) const
478    {
479      YAT_ASSERT(x->left_ != &impl_.head_);
480      return static_cast<ranking::NodeValue<T>*>(x->left_);
481    }
482
483
484    const ranking::NodeValue<T>*
485    right(const ranking::NodeBase* x) const
486    {
487      YAT_ASSERT(x->right_ != &impl_.head_);
488      return static_cast<const ranking::NodeValue<T>*>(x->right_);
489    }
490
491
492    ranking::NodeValue<T>*
493    right(ranking::NodeBase* x) const
494    {
495      YAT_ASSERT(x->right_ != &impl_.head_);
496      return static_cast<ranking::NodeValue<T>*>(x->right_);
497    }
498
499
500    // delete x and its offsprings
501    void erase(ranking::NodeValue<T>* x) const
502    {
503      while (x) {
504        if (x->right_)
505          erase(right(x));
506        ranking::NodeValue<T>* tmp = left(x);
507        delete x;
508        x = tmp;
509      }
510    }
511
512
513    /**
514       traverse the tree and find a suitable leaf where we can insert
515       \c element and keep the tree sorted.
516     */
517    iterator insert(std::unique_ptr<ranking::NodeValue<T>>&& element)
518    {
519
520      if (empty()) {
521        element->parent_ = &impl_.head_;
522        impl_.root_node() = element.release();
523        impl_.head_.left_ = impl_.root_node();
524        impl_.head_.right_ = impl_.root_node();
525        impl_.head_.update_height();
526        impl_.head_.update_size();
527
528        YAT_ASSERT(impl_.root_node()->parent_);
529        YAT_ASSERT(impl_.root_node()->parent_ == &impl_.head_);
530        YAT_ASSERT(impl_.root_node()->is_left_node());
531
532        YAT_ASSERT(validate());
533        return iterator(root_node());
534      }
535
536      return insert(impl_.root_node(), std::move(element));
537    }
538
539
540    // Insert \a element into the subtree in which x is the root.
541    iterator insert(ranking::NodeBase* x,
542                    std::unique_ptr<ranking::NodeValue<T>>&& element)
543    {
544      YAT_ASSERT(x);
545      YAT_ASSERT(!x->is_head_node());
546
547      while (true) {
548        ranking::NodeBase* parent = x;
549        if (compare_(element->value(), value(x))) {
550          x = x->left_;
551          if (x == nullptr)
552            return insert_and_rebalance(std::move(element), *parent, true);
553        }
554        else {
555          x = x->right_;
556          if (x == nullptr)
557            return insert_and_rebalance(std::move(element), *parent, false);
558        }
559      }
560      YAT_ASSERT(0 && "we can't reach here");
561      return iterator(element.get());
562    }
563
564
565    iterator insert(const_iterator hint,
566                    std::unique_ptr<ranking::NodeValue<T>>&& element)
567    {
568      // special case when hint == end()
569      if (hint.node_ == head_node()) {
570        YAT_ASSERT(hint == cend());
571        if (empty() || compare_(element->value(), value(impl_.right_most())))
572          return insert(std::move(element));
573        return insert_and_rebalance(std::move(element), *impl_.right_most(),
574                                    false);
575      }
576
577      YAT_ASSERT(hint != end());
578
579      // value <= hint i.e. !(hint<value)
580      if (!compare_(*hint, element->value())) {
581        // if hint == begin
582        if (hint.node_ == impl_.left_most()) {
583          YAT_ASSERT(hint == cbegin());
584          return insert_and_rebalance(std::move(element),
585                                      *impl_.left_most(),
586                                      true);
587        }
588
589        // prev <= value <= hint insert
590        YAT_ASSERT(hint != cbegin());
591        auto before = std::prev(hint);
592        if (!compare_(element->value(), *before)) {
593          return insert(const_cast<ranking::NodeBase*>(hint.node_),
594                        std::move(element));
595        }
596        else {
597          return insert(std::move(element));
598        }
599      }
600      // else value > hint
601      else {
602        YAT_ASSERT(compare_(*hint, element->value()));
603        // hint == rightmost
604        if (hint.node_ == impl_.right_most()) {
605          return insert_and_rebalance(std::move(element),
606                                      *impl_.right_most(),
607                                      false);
608        }
609        auto after = std::next(hint);
610        YAT_ASSERT(after != cend());
611        // hint < value <= after
612        if (!compare_(*after, element->value())) {
613          return insert(const_cast<ranking::NodeBase*>(after.node_),
614                        std::move(element));
615        }
616      }
617
618      return insert(std::move(element));
619    }
620
621
622    /*
623      Find the first node that is greater or equal to key, i.e., all
624      elements left of returned node are less than key.
625     */
626    const_iterator
627    lower_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
628                const T& key) const
629    {
630      // x is used to traverse the tree
631      // y holds the result
632
633      while (x) {
634        // key is less (or equal) than x, store x as potential result
635        // and search in left branch
636        if (!compare_(x->value(), key)) {
637          y = x;
638          x = left(x);
639        }
640        // key is greater than x, the lower bound is not x; it is
641        // either in the right branch or a previously assigned
642        // ancestor. Do not store x as potential result, but search
643        // branch.
644        else
645          x = right(x);
646      }
647      // x has reached a leaf, and the result should be stored in y
648
649      // returned node is not smaller than key
650      YAT_ASSERT(y==head_node() || !compare_(value(y), key));
651      // all nodes left of returned node are smaller than key
652      YAT_ASSERT(y->left_==nullptr ||
653                 compare_(value(y->left_->right_most()), key));
654      return const_iterator(y);
655    }
656
657
658    const ranking::NodeValue<T>* parent(const ranking::NodeBase* x) const
659    {
660      YAT_ASSERT(x);
661      YAT_ASSERT(x->parent_);
662      YAT_ASSERT(x->parent_ != &impl_.head_);
663      return static_cast<const ranking::NodeValue<T>*>(x->parent_);
664    }
665
666
667    ranking::NodeValue<T>* parent(ranking::NodeBase* x) const
668    {
669      YAT_ASSERT(x);
670      YAT_ASSERT(x->parent_);
671      YAT_ASSERT(x->parent_ != &impl_.head_);
672      return static_cast<ranking::NodeValue<T>*>(x->parent_);
673    }
674
675
676    /*
677      Find the first node that is greater than key, i.e., all
678      elements left of returned node are less or equal to key.
679     */
680    const_iterator
681    upper_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
682                const T& key) const
683    {
684      // x is used to traverse the tree
685      // y holds the result
686
687      while (x) {
688        // key is less than x value, x is a potential upper_bound,
689        // store and search in left
690        if (compare_(key, x->value())) {
691          y = x;
692          x = left(x);
693        }
694        else {
695          // key is greater (or equal) than x, x is not the upper
696          // bound. It is either in the right branch or in a
697          // previously assigned ancestor (current y).
698          x = right(x);
699        }
700      }
701      // x has reached a leaf, and the result should be stored in y
702
703      // key is less than returned node
704      YAT_ASSERT(y==head_node() || compare_(key, value(y)));
705      // all nodes left of returned node are smaller (or equal) than
706      // key, i.e., key is not smaller than any of the nodes to the
707      // left of returned node.
708      YAT_ASSERT(y->left_==nullptr ||
709                 !compare_(key, value(y->left_->right_most())));
710      return const_iterator(y);
711    }
712
713
714    const T& value(const ranking::NodeBase* p) const
715    {
716      YAT_ASSERT(p);
717      YAT_ASSERT(!p->is_head_node());
718      return static_cast<const ranking::NodeValue<T>*>(p)->value();
719    }
720
721
722    bool validate(void) const
723    {
724#ifndef YAT_DEBUG_RANKING
725      return true;
726#else
727      if (!impl_.validate()) {
728        std::cerr << "Impl::validate failed\n";
729        return false;
730      }
731
732      bool ok = true;
733      size_t rank = 0;
734      YAT_ASSERT(cbegin().node_);
735      YAT_ASSERT(cend().node_);
736      for (auto it = cbegin(); it!=cend(); ++it) {
737        size_t r = ranking(it);
738        if (r != rank) {
739          std::cerr << "ranking: " << r << "; expected: " << rank << "\n";
740          std::cerr << "size: " << it.node_->size_ << "\n";
741          std::cerr << it.node_->parent_ << " "
742                    << it.node_->is_left_node() << " "
743                    << it.node_->is_right_node() << "\n---\n";
744          ok = false;
745        }
746        ++rank;
747      }
748      return ok;
749#endif
750    }
751  };
752
753  // avoid doxygen reading code below as it has problems to to match
754  // declarations and implementations unless matching perfectly.
755
756  /// \cond IGNORE_DOXYGEN
757
758  // implementations
759  template<typename T, typename C>
760  Ranking<T,C>::Ranking(const Ranking& other)
761    : compare_(other.compare())
762  {
763    if (!other.empty())
764      impl_.root_node() = copy(other);
765    YAT_ASSERT(validate());
766  }
767
768
769  template<typename T, typename C>
770  Ranking<T,C>::Ranking(Ranking&& other)
771    : compare_(std::move(other.compare())), impl_(std::move(other.impl_))
772  {
773    YAT_ASSERT(validate());
774  }
775
776
777  template<typename T, typename C>
778  Ranking<T, C>& Ranking<T, C>::operator=(const Ranking& other)
779  {
780    if (this != &other) {
781      Ranking tmp(other);
782      *this = std::move(tmp);
783    }
784    return *this;
785  }
786
787
788  template<typename T, typename C>
789  Ranking<T, C>& Ranking<T, C>::operator=(Ranking&& other)
790  {
791    clear();
792    compare_ = std::move(other.compare_);
793    impl_ = std::move(other.impl_);
794    return *this;
795  }
796
797
798  template<typename T, typename C>
799  ranking::NodeValue<T>* Ranking<T,C>::copy(const Ranking& other)
800  {
801    YAT_ASSERT(other.root_node());
802    ranking::NodeValue<T>* root = copy(other.root_node());
803    root->parent_ = head_node();
804    head_node()->left_ = root;
805    head_node()->right_ = root->left_most();
806    head_node()->update_height();
807    head_node()->update_size();
808    YAT_ASSERT(validate());
809    return root;
810  }
811
812
813  template<typename T, typename C>
814  ranking::NodeValue<T>*
815  Ranking<T,C>::copy(const ranking::NodeValue<T>* x) const
816  {
817    YAT_ASSERT(x);
818    ranking::NodeValue<T>* root = clone_node(x);
819    YAT_ASSERT(root);
820    root->height_ = x->height_;
821    root->size_ = x->size_;
822
823    try {
824      if (x->left_) {
825        root->left_ = copy(left(x));
826        root->left_->parent_ = root;
827      }
828      if (x->right_) {
829        root->right_ = copy(right(x));
830        root->right_->parent_ = root;
831      }
832    }
833    catch (std::exception& e) {
834      erase(root);
835      std::rethrow_exception(std::current_exception());
836    }
837    return root;
838  }
839
840
841  template<typename T, typename C>
842  ranking::NodeValue<T>*
843  Ranking<T,C>::clone_node(const ranking::NodeValue<T>* x) const
844  {
845    YAT_ASSERT(x);
846    ranking::NodeValue<T>* res = new ranking::NodeValue<T>(x->value());
847    res->left_ = nullptr;
848    res->right_ = nullptr;
849    res->parent_ = nullptr;
850    return res;
851  }
852
853
854  template<typename T, typename C>
855  void Ranking<T, C>::erase_node(typename Ranking<T, C>::const_iterator p)
856  {
857    YAT_ASSERT(p != end());
858    const ranking::NodeBase* node = p.node_;
859    YAT_ASSERT(node);
860
861    impl_.erase_and_rebalance(node);
862    delete node;
863    YAT_ASSERT(validate());
864    return;
865  }
866
867
868  template<typename T, typename C>
869  typename Ranking<T, C>::iterator
870  Ranking<T, C>::erase(typename Ranking<T, C>::const_iterator p)
871  {
872    YAT_ASSERT(p != end());
873    const_iterator res = p;
874    ++res;
875    erase_node(p);
876    // iterator and const_iterator are same at the moment
877    return res;
878  }
879
880
881  template<typename T, typename C>
882  typename Ranking<T, C>::size_type Ranking<T, C>::erase(const T& value)
883  {
884    auto it = lower_bound(value);
885    typename Ranking<T, C>::size_type n = 0;
886    while (it!=end() && !compare_(value, *it)) {
887      erase_node(it++);
888      ++n;
889    }
890    return n;
891  }
892
893
894  template<typename T, typename C>
895  typename Ranking<T, C>::iterator
896  Ranking<T, C>::erase(typename Ranking<T, C>::const_iterator first,
897                       typename Ranking<T, C>::const_iterator last)
898  {
899    if (first == cbegin() && last == cend())
900      clear();
901    else
902      while (first != last) {
903        erase_node(first++);
904      }
905    return last;
906  }
907
908
909  template<typename T, typename C>
910  typename Ranking<T, C>::const_iterator Ranking<T, C>::find(const T& x) const
911  {
912    auto it = lower_bound(x);
913    if (it != cend() && compare_(x, *it))
914      it = cend();
915    return it;
916  }
917
918  /// \endcond
919
920}}} // of namespace utility, yat, and theplu
921#endif
Note: See TracBrowser for help on using the repository browser.