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

Last change on this file since 4064 was 4064, checked in by Peter, 13 months ago

first functioning version (tests pass) of Kendall class using the Ranking class. Split out the code in separate header and source files. Ranking class is still slow (linear) so Kendall::score is still quadratic. refs #710

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 11.3 KB
Line 
1#ifndef theplu_yat_utility_ranking
2#define theplu_yat_utility_ranking
3
4// $Id: Ranking.h 4064 2021-08-05 05:36:32Z 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 <memory>
35
36namespace theplu {
37namespace yat {
38namespace utility {
39
40  template<typename T, class Compare = std::less<T> >
41  class Ranking
42  {
43  public:
44    typedef T value_type;
45    typedef Compare key_compare;
46    typedef size_t size_type;
47
48    typedef ranking::Iterator<T> iterator;
49    typedef ranking::Iterator<T> const_iterator;
50    typedef std::reverse_iterator<iterator> reverse_iterator;
51    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
52
53    /**
54       \brief Default constructor
55     */
56    Ranking(void) = default;
57
58    /**
59       Construct empty container with comparison function \c c.
60     */
61    Ranking(const Compare& c)
62      : compare_(c)
63    {
64      YAT_ASSERT(validate());
65    }
66
67
68    Ranking(const Ranking& other)
69      : compare_(other.compare())
70    {
71      if (!other.empty())
72        impl_.head_.parent_ = copy(other);
73    }
74    Ranking(Ranking&& other) = default;
75    Ranking& operator=(const Ranking& other);
76    Ranking& operator=(Ranking&& other);
77
78
79    iterator begin(void)
80    {
81      return iterator(left_most());
82    }
83
84
85    const_iterator begin(void) const
86    {
87      return cbegin();
88    }
89
90
91    const_iterator cbegin(void) const
92    {
93      return const_iterator(left_most());
94    }
95
96
97    iterator end(void)
98    {
99      return iterator(&impl_.head_);
100    }
101
102
103    const_iterator end(void) const
104    {
105      return cend();
106    }
107
108
109    const_iterator cend(void) const
110    {
111      return const_iterator(&impl_.head_);
112    }
113
114
115    reverse_iterator rbegin(void)
116    {
117      return reverse_iterator(end());
118    }
119
120
121    reverse_iterator rend(void)
122    {
123      return reverse_iterator(begin());
124    }
125
126
127    const_reverse_iterator rend(void) const
128    {
129      return crend();
130    }
131
132
133    const_reverse_iterator rbegin(void) const
134    {
135      return crbegin();
136    }
137
138
139    const_reverse_iterator crbegin(void) const
140    {
141      return const_reverse_iterator(cend());
142    }
143
144
145    const_reverse_iterator crend(void) const
146    {
147      return const_reverse_iterator(cbegin());
148    }
149
150
151    const Compare& compare(void) const
152    {
153      return compare_;
154    }
155
156
157    bool empty(void) const
158    {
159      return size()==0;
160    }
161
162
163    const_iterator find(const T& x) const;
164
165
166    iterator insert(const T& element)
167    {
168      std::unique_ptr<ranking::NodeValue<T>>
169        newnode(new ranking::NodeValue<T>(element));
170      return insert(std::move(newnode));
171    }
172
173
174    iterator insert(T&& element)
175    {
176      std::unique_ptr<ranking::NodeValue<T>>
177        newnode(new ranking::NodeValue<T>(std::move(element)));
178      return insert(std::move(newnode));
179    }
180
181
182    iterator insert(const_iterator hint, const T& element)
183    {
184      // FIXME use the hint
185      return insert(element);
186    }
187
188
189    iterator insert(const_iterator hint,  T&& element)
190    {
191      // FIXME use the hint
192      return insert(std::move(element));
193    }
194
195
196    template<typename InputIterator>
197    void insert(InputIterator first, InputIterator last)
198    {
199      for (; first!=last; ++first)
200        insert(end(), *first);
201    }
202
203
204    const_iterator lower_bound(const T& x) const
205    {
206      if (empty())
207        return cend();
208      return lower_bound(first_node(), last_node(), x);
209    }
210
211
212    const_iterator upper_bound(const T& x) const
213    {
214      if (empty())
215        return cend();
216      return upper_bound(first_node(), last_node(), x);
217    }
218
219
220    size_t ranking(const_iterator it) const
221    {
222      // FIXME
223      return std::distance(cbegin(), it);
224    }
225
226
227    size_t size(void) const
228    {
229      return impl_.node_count_;
230    }
231
232  private:
233    Compare compare_;
234    ranking::Impl impl_;
235
236    ranking::NodeValue<T>*
237    clone_node(const ranking::NodeValue<T>* x) const
238    {
239      YAT_ASSERT(0 && "implement me");
240      YAT_ASSERT(x);
241      ranking::NodeValue<T>* tmp = new ranking::NodeValue<T>(*x);
242      tmp->left_ = nullptr;
243      tmp->right_ = nullptr;
244      return tmp;
245    }
246
247
248    ranking::NodeValue<T>* copy(const Ranking& other)
249    {
250      YAT_ASSERT(0 && "implement me");
251      ranking::NodeValue<T>* root = copy(other.first_node(), last_node());
252      //impl_.left_ = root->left_most();
253      //impl_.right_ = root->right_most();
254      //size_ = other.size_;
255      return root;
256    }
257
258
259    ranking::NodeValue<T>*
260    copy(const ranking::NodeValue<T>* x, ranking::NodeBase* p)
261    {
262      YAT_ASSERT(0 && "implement me");
263      ranking::NodeValue<T>* top = clone_node(x);
264      top->parent_ = p;
265      try {
266        if (x->right_)
267          top->right_ = copy(right(x), top);
268        p = top;
269        x = left(x);
270        while (x != 0) {
271          ranking::NodeValue<T>* y = clone_node(x);
272          p->left_ = y;
273          y->parent_ = p;
274          if (x->right_)
275            y->right_ = copy(right(x), y);
276          p = y;
277          x = left(x);
278        }
279      }
280      catch (std::exception& e) {
281        // cleanup
282        erase(top);
283        std::rethrow_exception(std::current_exception());
284      }
285      return top;
286    }
287
288
289    // return the root node
290    const ranking::NodeValue<T>* first_node(void) const
291    {
292      YAT_ASSERT(impl_.head_.parent_);
293      return static_cast<const ranking::NodeValue<T>*>(impl_.head_.parent_);
294    }
295
296
297    ranking::NodeValue<T>* first_node(void)
298    {
299      YAT_ASSERT(impl_.head_.parent_);
300      return static_cast<ranking::NodeValue<T>*>(impl_.head_.parent_);
301    }
302
303
304    const ranking::NodeBase* last_node(void) const
305    {
306      return &impl_.head_;
307    }
308
309
310    ranking::NodeBase* last_node(void)
311    {
312      return &impl_.head_;
313    }
314
315
316    const ranking::NodeValue<T>*
317    left(const ranking::NodeBase* x) const
318    {
319      YAT_ASSERT(x->left_ != &impl_.head_);
320      return static_cast<const ranking::NodeValue<T>*>(x->left_);
321    }
322
323
324    ranking::NodeValue<T>*
325    left(ranking::NodeBase* x) const
326    {
327      YAT_ASSERT(x->left_ != &impl_.head_);
328      return static_cast<ranking::NodeValue<T>*>(x->left_);
329    }
330
331
332    const ranking::NodeValue<T>*
333    right(const ranking::NodeBase* x) const
334    {
335      YAT_ASSERT(x->right_ != &impl_.head_);
336      return static_cast<const ranking::NodeValue<T>*>(x->right_);
337    }
338
339
340    ranking::NodeValue<T>*
341    right(ranking::NodeBase* x) const
342    {
343      YAT_ASSERT(x->right_ != &impl_.head_);
344      return static_cast<ranking::NodeValue<T>*>(x->right_);
345    }
346
347
348    // delete x and its offsprings
349    void erase(ranking::NodeValue<T>* x)
350    {
351      YAT_ASSERT(0 && "implement me");
352      while (x) {
353        erase(right(x));
354        ranking::NodeValue<T>* tmp = left(x);
355        delete x;
356        x = tmp;
357      }
358    }
359
360
361    /**
362       traverse the tree and find a suitable leaf where we can insert
363       \c element and keep the tree sorted.
364     */
365    iterator insert(std::unique_ptr<ranking::NodeValue<T>>&& element)
366    {
367      iterator result(element.get());
368      if (empty()) {
369        YAT_ASSERT(root_node() == nullptr);
370        root_node() = element.release();
371        root_node()->right_ = &impl_.head_;
372        impl_.head_.left_ = root_node();
373        ++impl_.node_count_;
374        YAT_ASSERT(root_node()->validate());
375        YAT_ASSERT(impl_.head_.validate());
376        YAT_ASSERT(validate());
377        return result;
378      }
379
380      ranking::NodeBase* x = root_node();
381      YAT_ASSERT(x);
382      YAT_ASSERT(!x->is_head_node());
383
384      // element right of root
385      if (!compare_(element->value(),
386                    static_cast<ranking::NodeValue<T>*>(x)->value())) {
387        // make new root parent of head
388        impl_.head_.parent_ = element.release();
389        impl_.head_.parent_->right_ = &impl_.head_;
390
391        // make old root and left child of new root
392        x->right_ = nullptr;
393        impl_.head_.parent_->left_ = x;
394        x->parent_ = impl_.head_.parent_;
395
396        ++impl_.node_count_;
397        YAT_ASSERT(x->validate());
398        YAT_ASSERT(impl_.head_.parent_);
399        YAT_ASSERT(impl_.head_.parent_->validate());
400        YAT_ASSERT(impl_.head_.left_);
401        YAT_ASSERT(impl_.head_.left_->validate());
402        YAT_ASSERT(validate());
403        return result;
404      }
405
406      ranking::NodeBase* parent = nullptr;
407      YAT_ASSERT(x);
408      while (true) {
409        parent = x;
410        if (compare_(element->value(),
411                     static_cast<ranking::NodeValue<T>*>(x)->value())) {
412          x = x->left_;
413          if (x == nullptr) {
414            element->parent_ = parent;
415            parent->left_ = element.release();
416            if (impl_.head_.left_ == parent)
417              impl_.head_.left_ = parent->left_;
418            ++impl_.node_count_;
419            YAT_ASSERT(validate());
420            return result;
421          }
422        }
423        else {
424          x = x->right_;
425          if (x == nullptr) {
426            element->parent_ = parent;
427            parent->right_ = element.release();
428            ++impl_.node_count_;
429            YAT_ASSERT(validate());
430            return result;
431          }
432        }
433        YAT_ASSERT(x != &impl_.head_);
434        YAT_ASSERT(x != parent);
435      }
436    }
437
438
439    iterator insert(std::unique_ptr<ranking::NodeValue<T>>&& element,
440                    ranking::NodeBase* parent, ranking::NodeBase*& child)
441    {
442      YAT_ASSERT(0 && "implement me");
443      YAT_ASSERT(parent);
444      YAT_ASSERT(child==parent->left_ || child==parent->right_);
445      // if child is null, assign element
446      if (!child) {
447        child = element.release();
448        child->parent_ = parent;
449        YAT_ASSERT(child==parent->left_ || child==parent->right_);
450        ++impl_.node_count_;
451        return iterator(child);
452      }
453      if (compare_(element->value(),
454                   static_cast<ranking::NodeValue<T>*>(child)->value()))
455        return insert(std::move(element), child, child->left_);
456      return insert(std::move(element), child, child->right_);
457    }
458
459
460    const_iterator
461    lower_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
462                const T& key) const
463    {
464      if (compare_(x->value(), key))
465        return const_iterator(y);
466
467      while (x) {
468        // x value is greater than key, search in left branch
469        if (!compare_(x->value(), key)) {
470          y = x;
471          // asign x->left_ as NodeValue*
472          x = left(x);
473        }
474        else { // x value <= key, search in right branch but don't update y
475          YAT_ASSERT(x->right_ != &impl_.head_);
476          // asign x->right_ as NodeValue*
477          x = right(x);
478        }
479      }
480      return const_iterator(y);
481    }
482
483
484    /**
485       \return the root of the tree
486     */
487    ranking::NodeBase*& root_node(void)
488    {
489      return impl_.head_.parent_;
490    }
491
492
493    const ranking::NodeBase* const root_node(void) const
494    {
495      YAT_ASSERT(0 && "implement me");
496      return impl_.head_.parent_;
497    }
498
499
500    ranking::NodeBase* left_most(void)
501    {
502      return impl_.head_.left_;
503    }
504
505
506    const ranking::NodeBase* left_most(void) const
507    {
508      return impl_.head_.left_;
509    }
510
511    /*
512    ranking::NodeBase* right_most(void)
513    {
514      head_.right_;
515    }
516
517
518    const ranking::NodeBase* right_most(void) const
519    {
520      head_.right_;
521    }
522    */
523
524    const_iterator
525    upper_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
526                const T& key) const
527    {
528      if (!compare_(key, x->value()))
529        return const_iterator(y);
530
531
532      while (x) {
533        // key is less than x value, search in left
534        if (compare_(key, x->value())) {
535          y = x;
536          x = left(x);
537        }
538        else {
539          YAT_ASSERT(x->right_ != &impl_.head_);
540          x = right(x);
541        }
542      }
543      return const_iterator(y);
544    }
545
546
547    bool validate(void) const
548    {
549#ifdef YAT_DEBUG_RANKING
550      return impl_.validate();
551#else
552      return true;
553#endif
554
555    }
556
557  };
558
559}}} // of namespace utility, yat, and theplu
560#endif
Note: See TracBrowser for help on using the repository browser.