ceph/src/boost/boost/heap/detail/mutable_heap.hpp

   1 // boost heap
   2 //
   3 // Copyright (C) 2010 Tim Blechmann
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP
  10 #define BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP
  11
  12 /*! \file
  13  * INTERNAL ONLY
  14  */
  15
  16 #include <list>
  17 #include <utility>
  18
  19 #include <boost/iterator/iterator_adaptor.hpp>
  20 #include <boost/heap/detail/ordered_adaptor_iterator.hpp>
  21
  22 namespace boost  {
  23 namespace heap   {
  24 namespace detail {
  25
  26 /* wrapper for a mutable heap container adaptors
  27  *
  28  * this wrapper introduces an additional indirection. the heap is not constructed from objects,
  29  * but instead from std::list iterators. this way, the mutability is achieved
  30  *
  31  */
  32 template <typename PriorityQueueType>
  33 class priority_queue_mutable_wrapper
  34 {
  35 public:
  36     typedef typename PriorityQueueType::value_type value_type;
  37     typedef typename PriorityQueueType::size_type size_type;
  38     typedef typename PriorityQueueType::value_compare value_compare;
  39     typedef typename PriorityQueueType::allocator_type allocator_type;
  40
  41     typedef typename PriorityQueueType::reference reference;
  42     typedef typename PriorityQueueType::const_reference const_reference;
  43     typedef typename PriorityQueueType::pointer pointer;
  44     typedef typename PriorityQueueType::const_pointer const_pointer;
  45     static const bool is_stable = PriorityQueueType::is_stable;
  46
  47 private:
  48     typedef std::pair<value_type, size_type> node_type;
  49
  50     typedef std::list<node_type, typename allocator_type::template rebind<node_type>::other> object_list;
  51
  52     typedef typename object_list::iterator list_iterator;
  53     typedef typename object_list::const_iterator const_list_iterator;
  54
  55     template <typename Heap1, typename Heap2>
  56     friend struct heap_merge_emulate;
  57
  58     typedef typename PriorityQueueType::super_t::stability_counter_type stability_counter_type;
  59
  60     stability_counter_type get_stability_count(void) const
  61     {
  62         return q_.get_stability_count();
  63     }
  64
  65     void set_stability_count(stability_counter_type new_count)
  66     {
  67         q_.set_stability_count(new_count);
  68     }
  69
  70     struct index_updater
  71     {
  72         template <typename It>
  73         static void run(It & it, size_type new_index)
  74         {
  75             q_type::get_value(it)->second = new_index;
  76         }
  77     };
  78
  79 public:
  80     struct handle_type
  81     {
  82         value_type & operator*() const
  83         {
  84             return iterator->first;
  85         }
  86
  87         handle_type (void)
  88         {}
  89
  90         handle_type(handle_type const & rhs):
  91             iterator(rhs.iterator)
  92         {}
  93
  94         bool operator==(handle_type const & rhs) const
  95         {
  96             return iterator == rhs.iterator;
  97         }
  98
  99         bool operator!=(handle_type const & rhs) const
 100         {
 101             return iterator != rhs.iterator;
 102         }
 103
 104     private:
 105         explicit handle_type(list_iterator const & it):
 106             iterator(it)
 107         {}
 108
 109         list_iterator iterator;
 110
 111         friend class priority_queue_mutable_wrapper;
 112     };
 113
 114 private:
 115     struct indirect_cmp:
 116         public value_compare
 117     {
 118         indirect_cmp(value_compare const & cmp = value_compare()):
 119             value_compare(cmp)
 120         {}
 121
 122         bool operator()(const_list_iterator const & lhs, const_list_iterator const & rhs) const
 123         {
 124             return value_compare::operator()(lhs->first, rhs->first);
 125         }
 126     };
 127
 128     typedef typename PriorityQueueType::template rebind<list_iterator,
 129                                                         indirect_cmp,
 130                                                         allocator_type, index_updater >::other q_type;
 131
 132 protected:
 133     q_type q_;
 134     object_list objects;
 135
 136 protected:
 137     priority_queue_mutable_wrapper(value_compare const & cmp = value_compare()):
 138         q_(cmp)
 139     {}
 140
 141     priority_queue_mutable_wrapper(priority_queue_mutable_wrapper const & rhs):
 142         q_(rhs.q_), objects(rhs.objects)
 143     {
 144         for (typename object_list::iterator it = objects.begin(); it != objects.end(); ++it)
 145             q_.push(it);
 146     }
 147
 148     priority_queue_mutable_wrapper & operator=(priority_queue_mutable_wrapper const & rhs)
 149     {
 150         q_ = rhs.q_;
 151         objects = rhs.objects;
 152         q_.clear();
 153         for (typename object_list::iterator it = objects.begin(); it != objects.end(); ++it)
 154             q_.push(it);
 155         return *this;
 156     }
 157
 158 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 159     priority_queue_mutable_wrapper (priority_queue_mutable_wrapper && rhs):
 160         q_(std::move(rhs.q_))
 161     {
 162         /// FIXME: msvc seems to invalidate iterators when moving std::list
 163         std::swap(objects, rhs.objects);
 164     }
 165
 166     priority_queue_mutable_wrapper & operator=(priority_queue_mutable_wrapper && rhs)
 167     {
 168         q_ = std::move(rhs.q_);
 169         objects.clear();
 170         std::swap(objects, rhs.objects);
 171         return *this;
 172     }
 173 #endif
 174
 175
 176 public:
 177     template <typename iterator_type>
 178     class iterator_base:
 179         public boost::iterator_adaptor<iterator_base<iterator_type>,
 180                                        iterator_type,
 181                                        value_type const,
 182                                        boost::bidirectional_traversal_tag>
 183     {
 184         typedef boost::iterator_adaptor<iterator_base<iterator_type>,
 185                                        iterator_type,
 186                                        value_type const,
 187                                        boost::bidirectional_traversal_tag> super_t;
 188
 189         friend class boost::iterator_core_access;
 190         friend class priority_queue_mutable_wrapper;
 191
 192         iterator_base(void):
 193             super_t(0)
 194         {}
 195
 196         template <typename T>
 197         explicit iterator_base(T const & it):
 198             super_t(it)
 199         {}
 200
 201         value_type const & dereference() const
 202         {
 203             return super_t::base()->first;
 204         }
 205
 206         iterator_type get_list_iterator() const
 207         {
 208             return super_t::base_reference();
 209         }
 210     };
 211
 212     typedef iterator_base<list_iterator> iterator;
 213     typedef iterator_base<const_list_iterator> const_iterator;
 214
 215     typedef typename object_list::difference_type difference_type;
 216
 217     class ordered_iterator:
 218         public boost::iterator_adaptor<ordered_iterator,
 219                                        const_list_iterator,
 220                                        value_type const,
 221                                        boost::forward_traversal_tag
 222                                       >,
 223         q_type::ordered_iterator_dispatcher
 224     {
 225         typedef boost::iterator_adaptor<ordered_iterator,
 226                                         const_list_iterator,
 227                                         value_type const,
 228                                         boost::forward_traversal_tag
 229                                       > adaptor_type;
 230
 231         typedef const_list_iterator iterator;
 232         typedef typename q_type::ordered_iterator_dispatcher ordered_iterator_dispatcher;
 233
 234         friend class boost::iterator_core_access;
 235
 236     public:
 237         ordered_iterator(void):
 238             adaptor_type(0), unvisited_nodes(indirect_cmp()), q_(NULL)
 239         {}
 240
 241         ordered_iterator(const priority_queue_mutable_wrapper * q, indirect_cmp const & cmp):
 242             adaptor_type(0), unvisited_nodes(cmp), q_(q)
 243         {}
 244
 245         ordered_iterator(const_list_iterator it, const priority_queue_mutable_wrapper * q, indirect_cmp const & cmp):
 246             adaptor_type(it), unvisited_nodes(cmp), q_(q)
 247         {
 248             if (it != q->objects.end())
 249                 discover_nodes(it);
 250         }
 251
 252         bool operator!=(ordered_iterator const & rhs) const
 253         {
 254             return adaptor_type::base() != rhs.base();
 255         }
 256
 257         bool operator==(ordered_iterator const & rhs) const
 258         {
 259             return !operator!=(rhs);
 260         }
 261
 262     private:
 263         void increment(void)
 264         {
 265             if (unvisited_nodes.empty())
 266                 adaptor_type::base_reference() = q_->objects.end();
 267             else {
 268                 iterator next = unvisited_nodes.top();
 269                 unvisited_nodes.pop();
 270                 discover_nodes(next);
 271                 adaptor_type::base_reference() = next;
 272             }
 273         }
 274
 275         value_type const & dereference() const
 276         {
 277             return adaptor_type::base()->first;
 278         }
 279
 280         void discover_nodes(iterator current)
 281         {
 282             size_type current_index = current->second;
 283             const q_type * q = &(q_->q_);
 284
 285             if (ordered_iterator_dispatcher::is_leaf(q, current_index))
 286                 return;
 287
 288             std::pair<size_type, size_type> child_range = ordered_iterator_dispatcher::get_child_nodes(q, current_index);
 289
 290             for (size_type i = child_range.first; i <= child_range.second; ++i) {
 291                 typename q_type::internal_type const & internal_value_at_index = ordered_iterator_dispatcher::get_internal_value(q, i);
 292                 typename q_type::value_type const & value_at_index = q_->q_.get_value(internal_value_at_index);
 293
 294                 unvisited_nodes.push(value_at_index);
 295             }
 296         }
 297
 298         std::priority_queue<iterator,
 299                             std::vector<iterator, typename allocator_type::template rebind<iterator>::other >,
 300                             indirect_cmp
 301                            > unvisited_nodes;
 302         const priority_queue_mutable_wrapper * q_;
 303     };
 304
 305     bool empty(void) const
 306     {
 307         return q_.empty();
 308     }
 309
 310     size_type size(void) const
 311     {
 312         return q_.size();
 313     }
 314
 315     size_type max_size(void) const
 316     {
 317         return objects.max_size();
 318     }
 319
 320     void clear(void)
 321     {
 322         q_.clear();
 323         objects.clear();
 324     }
 325
 326     allocator_type get_allocator(void) const
 327     {
 328         return q_.get_allocator();
 329     }
 330
 331     void swap(priority_queue_mutable_wrapper & rhs)
 332     {
 333         objects.swap(rhs.objects);
 334         q_.swap(rhs.q_);
 335     }
 336
 337     const_reference top(void) const
 338     {
 339         BOOST_ASSERT(!empty());
 340         return q_.top()->first;
 341     }
 342
 343     handle_type push(value_type const & v)
 344     {
 345         objects.push_front(std::make_pair(v, 0));
 346         list_iterator ret = objects.begin();
 347         q_.push(ret);
 348         return handle_type(ret);
 349     }
 350
 351 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 352     template <class... Args>
 353     handle_type emplace(Args&&... args)
 354     {
 355         objects.push_front(std::make_pair(std::forward<Args>(args)..., 0));
 356         list_iterator ret = objects.begin();
 357         q_.push(ret);
 358         return handle_type(ret);
 359     }
 360 #endif
 361
 362     void pop(void)
 363     {
 364         BOOST_ASSERT(!empty());
 365         list_iterator q_top = q_.top();
 366         q_.pop();
 367         objects.erase(q_top);
 368     }
 369
 370     /**
 371      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 372      *
 373      * \b Complexity: Logarithmic.
 374      *
 375      * */
 376     void update(handle_type handle, const_reference v)
 377     {
 378         list_iterator it = handle.iterator;
 379         value_type const & current_value = it->first;
 380         value_compare const & cmp = q_.value_comp();
 381         if (cmp(v, current_value))
 382             decrease(handle, v);
 383         else
 384             increase(handle, v);
 385     }
 386
 387     /**
 388      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 389      *
 390      * \b Complexity: Logarithmic.
 391      *
 392      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
 393      * */
 394     void update(handle_type handle)
 395     {
 396         list_iterator it = handle.iterator;
 397         size_type index = it->second;
 398         q_.update(index);
 399     }
 400
 401      /**
 402      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 403      *
 404      * \b Complexity: Logarithmic.
 405      *
 406      * \b Note: The new value is expected to be greater than the current one
 407      * */
 408     void increase(handle_type handle, const_reference v)
 409     {
 410         BOOST_ASSERT(!value_compare()(v, handle.iterator->first));
 411         handle.iterator->first = v;
 412         increase(handle);
 413     }
 414
 415     /**
 416      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 417      *
 418      * \b Complexity: Logarithmic.
 419      *
 420      * \b Note: The new value is expected to be greater than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
 421      * */
 422     void increase(handle_type handle)
 423     {
 424         list_iterator it = handle.iterator;
 425         size_type index = it->second;
 426         q_.increase(index);
 427     }
 428
 429      /**
 430      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 431      *
 432      * \b Complexity: Logarithmic.
 433      *
 434      * \b Note: The new value is expected to be less than the current one
 435      * */
 436     void decrease(handle_type handle, const_reference v)
 437     {
 438         BOOST_ASSERT(!value_compare()(handle.iterator->first, v));
 439         handle.iterator->first = v;
 440         decrease(handle);
 441     }
 442
 443     /**
 444      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 445      *
 446      * \b Complexity: Logarithmic.
 447      *
 448      * \b Note: The new value is expected to be less than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
 449      * */
 450     void decrease(handle_type handle)
 451     {
 452         list_iterator it = handle.iterator;
 453         size_type index = it->second;
 454         q_.decrease(index);
 455     }
 456
 457     /**
 458      * \b Effects: Removes the element handled by \c handle from the priority_queue.
 459      *
 460      * \b Complexity: Logarithmic.
 461      * */
 462     void erase(handle_type handle)
 463     {
 464         list_iterator it = handle.iterator;
 465         size_type index = it->second;
 466         q_.erase(index);
 467         objects.erase(it);
 468     }
 469
 470     const_iterator begin(void) const
 471     {
 472         return const_iterator(objects.begin());
 473     }
 474
 475     const_iterator end(void) const
 476     {
 477         return const_iterator(objects.end());
 478     }
 479
 480     iterator begin(void)
 481     {
 482         return iterator(objects.begin());
 483     }
 484
 485     iterator end(void)
 486     {
 487         return iterator(objects.end());
 488     }
 489
 490     ordered_iterator ordered_begin(void) const
 491     {
 492         if (!empty())
 493             return ordered_iterator(q_.top(), this, indirect_cmp(q_.value_comp()));
 494         else
 495             return ordered_end();
 496     }
 497
 498     ordered_iterator ordered_end(void) const
 499     {
 500         return ordered_iterator(objects.end(), this, indirect_cmp(q_.value_comp()));
 501     }
 502
 503     static handle_type s_handle_from_iterator(iterator const & it)
 504     {
 505         return handle_type(it.get_list_iterator());
 506     }
 507
 508     value_compare const & value_comp(void) const
 509     {
 510         return q_.value_comp();
 511     }
 512
 513     void reserve (size_type element_count)
 514     {
 515         q_.reserve(element_count);
 516     }
 517 };
 518
 519
 520 } /* namespace detail */
 521 } /* namespace heap */
 522 } /* namespace boost */
 523
 524 #endif /* BOOST_HEAP_DETAIL_MUTABLE_HEAP_HPP */