yat/utility/Ranking.h

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

Generated on Sat Oct 14 02:25:12 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)