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

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

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