1.1 --- a/lemon/binom_heap.h Thu Jul 09 02:39:47 2009 +0200
1.2 +++ b/lemon/binom_heap.h Thu Jul 09 04:07:08 2009 +0200
1.3 @@ -1,8 +1,8 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 - * Copyright (C) 2003-2008
1.11 + * Copyright (C) 2003-2009
1.12 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.13 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.14 *
1.15 @@ -20,193 +20,199 @@
1.16 #define LEMON_BINOM_HEAP_H
1.17
1.18 ///\file
1.19 -///\ingroup auxdat
1.20 +///\ingroup heaps
1.21 ///\brief Binomial Heap implementation.
1.22
1.23 #include <vector>
1.24 +#include <utility>
1.25 #include <functional>
1.26 #include <lemon/math.h>
1.27 #include <lemon/counter.h>
1.28
1.29 namespace lemon {
1.30
1.31 - /// \ingroup auxdat
1.32 + /// \ingroup heaps
1.33 ///
1.34 - ///\brief Binomial Heap.
1.35 + ///\brief Binomial heap data structure.
1.36 ///
1.37 - ///This class implements the \e Binomial \e heap data structure. A \e heap
1.38 - ///is a data structure for storing items with specified values called \e
1.39 - ///priorities in such a way that finding the item with minimum priority is
1.40 - ///efficient. \c Compare specifies the ordering of the priorities. In a heap
1.41 - ///one can change the priority of an item, add or erase an item, etc.
1.42 + /// This class implements the \e binomial \e heap data structure.
1.43 + /// It fully conforms to the \ref concepts::Heap "heap concept".
1.44 ///
1.45 - ///The methods \ref increase and \ref erase are not efficient in a Binomial
1.46 - ///heap. In case of many calls to these operations, it is better to use a
1.47 - ///\ref BinHeap "binary heap".
1.48 + /// The methods \ref increase() and \ref erase() are not efficient
1.49 + /// in a binomial heap. In case of many calls of these operations,
1.50 + /// it is better to use other heap structure, e.g. \ref BinHeap
1.51 + /// "binary heap".
1.52 ///
1.53 - ///\param _Prio Type of the priority of the items.
1.54 - ///\param _ItemIntMap A read and writable Item int map, used internally
1.55 - ///to handle the cross references.
1.56 - ///\param _Compare A class for the ordering of the priorities. The
1.57 - ///default is \c std::less<_Prio>.
1.58 - ///
1.59 - ///\sa BinHeap
1.60 - ///\sa Dijkstra
1.61 - ///\author Dorian Batha
1.62 -
1.63 + /// \tparam PR Type of the priorities of the items.
1.64 + /// \tparam IM A read-writable item map with \c int values, used
1.65 + /// internally to handle the cross references.
1.66 + /// \tparam CMP A functor class for comparing the priorities.
1.67 + /// The default is \c std::less<PR>.
1.68 #ifdef DOXYGEN
1.69 - template <typename _Prio,
1.70 - typename _ItemIntMap,
1.71 - typename _Compare>
1.72 + template <typename PR, typename IM, typename CMP>
1.73 #else
1.74 - template <typename _Prio,
1.75 - typename _ItemIntMap,
1.76 - typename _Compare = std::less<_Prio> >
1.77 + template <typename PR, typename IM, typename CMP = std::less<PR> >
1.78 #endif
1.79 class BinomHeap {
1.80 public:
1.81 - typedef _ItemIntMap ItemIntMap;
1.82 - typedef _Prio Prio;
1.83 + /// Type of the item-int map.
1.84 + typedef IM ItemIntMap;
1.85 + /// Type of the priorities.
1.86 + typedef PR Prio;
1.87 + /// Type of the items stored in the heap.
1.88 typedef typename ItemIntMap::Key Item;
1.89 - typedef std::pair<Item,Prio> Pair;
1.90 - typedef _Compare Compare;
1.91 + /// Functor type for comparing the priorities.
1.92 + typedef CMP Compare;
1.93 +
1.94 + /// \brief Type to represent the states of the items.
1.95 + ///
1.96 + /// Each item has a state associated to it. It can be "in heap",
1.97 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
1.98 + /// heap's point of view, but may be useful to the user.
1.99 + ///
1.100 + /// The item-int map must be initialized in such way that it assigns
1.101 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
1.102 + enum State {
1.103 + IN_HEAP = 0, ///< = 0.
1.104 + PRE_HEAP = -1, ///< = -1.
1.105 + POST_HEAP = -2 ///< = -2.
1.106 + };
1.107
1.108 private:
1.109 class store;
1.110
1.111 - std::vector<store> container;
1.112 - int minimum, head;
1.113 - ItemIntMap &iimap;
1.114 - Compare comp;
1.115 - int num_items;
1.116 + std::vector<store> _data;
1.117 + int _min, _head;
1.118 + ItemIntMap &_iim;
1.119 + Compare _comp;
1.120 + int _num_items;
1.121
1.122 public:
1.123 - ///Status of the nodes
1.124 - enum State {
1.125 - ///The node is in the heap
1.126 - IN_HEAP = 0,
1.127 - ///The node has never been in the heap
1.128 - PRE_HEAP = -1,
1.129 - ///The node was in the heap but it got out of it
1.130 - POST_HEAP = -2
1.131 - };
1.132 + /// \brief Constructor.
1.133 + ///
1.134 + /// Constructor.
1.135 + /// \param map A map that assigns \c int values to the items.
1.136 + /// It is used internally to handle the cross references.
1.137 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
1.138 + explicit BinomHeap(ItemIntMap &map)
1.139 + : _min(0), _head(-1), _iim(map), _num_items(0) {}
1.140
1.141 - /// \brief The constructor
1.142 + /// \brief Constructor.
1.143 ///
1.144 - /// \c _iimap should be given to the constructor, since it is
1.145 - /// used internally to handle the cross references.
1.146 - explicit BinomHeap(ItemIntMap &_iimap)
1.147 - : minimum(0), head(-1), iimap(_iimap), num_items() {}
1.148 -
1.149 - /// \brief The constructor
1.150 - ///
1.151 - /// \c _iimap should be given to the constructor, since it is used
1.152 - /// internally to handle the cross references. \c _comp is an
1.153 - /// object for ordering of the priorities.
1.154 - BinomHeap(ItemIntMap &_iimap, const Compare &_comp)
1.155 - : minimum(0), head(-1), iimap(_iimap), comp(_comp), num_items() {}
1.156 + /// Constructor.
1.157 + /// \param map A map that assigns \c int values to the items.
1.158 + /// It is used internally to handle the cross references.
1.159 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
1.160 + /// \param comp The function object used for comparing the priorities.
1.161 + BinomHeap(ItemIntMap &map, const Compare &comp)
1.162 + : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
1.163
1.164 /// \brief The number of items stored in the heap.
1.165 ///
1.166 - /// Returns the number of items stored in the heap.
1.167 - int size() const { return num_items; }
1.168 + /// This function returns the number of items stored in the heap.
1.169 + int size() const { return _num_items; }
1.170
1.171 - /// \brief Checks if the heap stores no items.
1.172 + /// \brief Check if the heap is empty.
1.173 ///
1.174 - /// Returns \c true if and only if the heap stores no items.
1.175 - bool empty() const { return num_items==0; }
1.176 + /// This function returns \c true if the heap is empty.
1.177 + bool empty() const { return _num_items==0; }
1.178
1.179 - /// \brief Make empty this heap.
1.180 + /// \brief Make the heap empty.
1.181 ///
1.182 - /// Make empty this heap. It does not change the cross reference
1.183 - /// map. If you want to reuse a heap what is not surely empty you
1.184 - /// should first clear the heap and after that you should set the
1.185 - /// cross reference map for each item to \c PRE_HEAP.
1.186 + /// This functon makes the heap empty.
1.187 + /// It does not change the cross reference map. If you want to reuse
1.188 + /// a heap that is not surely empty, you should first clear it and
1.189 + /// then you should set the cross reference map to \c PRE_HEAP
1.190 + /// for each item.
1.191 void clear() {
1.192 - container.clear(); minimum=0; num_items=0; head=-1;
1.193 + _data.clear(); _min=0; _num_items=0; _head=-1;
1.194 }
1.195
1.196 - /// \brief \c item gets to the heap with priority \c value independently
1.197 - /// if \c item was already there.
1.198 + /// \brief Set the priority of an item or insert it, if it is
1.199 + /// not stored in the heap.
1.200 ///
1.201 - /// This method calls \ref push(\c item, \c value) if \c item is not
1.202 - /// stored in the heap and it calls \ref decrease(\c item, \c value) or
1.203 - /// \ref increase(\c item, \c value) otherwise.
1.204 + /// This method sets the priority of the given item if it is
1.205 + /// already stored in the heap. Otherwise it inserts the given
1.206 + /// item into the heap with the given priority.
1.207 + /// \param item The item.
1.208 + /// \param value The priority.
1.209 void set (const Item& item, const Prio& value) {
1.210 - int i=iimap[item];
1.211 - if ( i >= 0 && container[i].in ) {
1.212 - if ( comp(value, container[i].prio) ) decrease(item, value);
1.213 - if ( comp(container[i].prio, value) ) increase(item, value);
1.214 + int i=_iim[item];
1.215 + if ( i >= 0 && _data[i].in ) {
1.216 + if ( _comp(value, _data[i].prio) ) decrease(item, value);
1.217 + if ( _comp(_data[i].prio, value) ) increase(item, value);
1.218 } else push(item, value);
1.219 }
1.220
1.221 - /// \brief Adds \c item to the heap with priority \c value.
1.222 + /// \brief Insert an item into the heap with the given priority.
1.223 ///
1.224 - /// Adds \c item to the heap with priority \c value.
1.225 - /// \pre \c item must not be stored in the heap.
1.226 + /// This function inserts the given item into the heap with the
1.227 + /// given priority.
1.228 + /// \param item The item to insert.
1.229 + /// \param value The priority of the item.
1.230 + /// \pre \e item must not be stored in the heap.
1.231 void push (const Item& item, const Prio& value) {
1.232 - int i=iimap[item];
1.233 + int i=_iim[item];
1.234 if ( i<0 ) {
1.235 - int s=container.size();
1.236 - iimap.set( item,s );
1.237 + int s=_data.size();
1.238 + _iim.set( item,s );
1.239 store st;
1.240 st.name=item;
1.241 - container.push_back(st);
1.242 + _data.push_back(st);
1.243 i=s;
1.244 }
1.245 else {
1.246 - container[i].parent=container[i].right_neighbor=container[i].child=-1;
1.247 - container[i].degree=0;
1.248 - container[i].in=true;
1.249 + _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
1.250 + _data[i].degree=0;
1.251 + _data[i].in=true;
1.252 }
1.253 - container[i].prio=value;
1.254 + _data[i].prio=value;
1.255
1.256 - if( 0==num_items ) { head=i; minimum=i; }
1.257 + if( 0==_num_items ) { _head=i; _min=i; }
1.258 else { merge(i); }
1.259
1.260 - minimum = find_min();
1.261 + _min = findMin();
1.262
1.263 - ++num_items;
1.264 + ++_num_items;
1.265 }
1.266
1.267 - /// \brief Returns the item with minimum priority relative to \c Compare.
1.268 + /// \brief Return the item having minimum priority.
1.269 ///
1.270 - /// This method returns the item with minimum priority relative to \c
1.271 - /// Compare.
1.272 - /// \pre The heap must be nonempty.
1.273 - Item top() const { return container[minimum].name; }
1.274 + /// This function returns the item having minimum priority.
1.275 + /// \pre The heap must be non-empty.
1.276 + Item top() const { return _data[_min].name; }
1.277
1.278 - /// \brief Returns the minimum priority relative to \c Compare.
1.279 + /// \brief The minimum priority.
1.280 ///
1.281 - /// It returns the minimum priority relative to \c Compare.
1.282 - /// \pre The heap must be nonempty.
1.283 - const Prio& prio() const { return container[minimum].prio; }
1.284 + /// This function returns the minimum priority.
1.285 + /// \pre The heap must be non-empty.
1.286 + Prio prio() const { return _data[_min].prio; }
1.287
1.288 - /// \brief Returns the priority of \c item.
1.289 + /// \brief The priority of the given item.
1.290 ///
1.291 - /// It returns the priority of \c item.
1.292 - /// \pre \c item must be in the heap.
1.293 + /// This function returns the priority of the given item.
1.294 + /// \param item The item.
1.295 + /// \pre \e item must be in the heap.
1.296 const Prio& operator[](const Item& item) const {
1.297 - return container[iimap[item]].prio;
1.298 + return _data[_iim[item]].prio;
1.299 }
1.300
1.301 - /// \brief Deletes the item with minimum priority relative to \c Compare.
1.302 + /// \brief Remove the item having minimum priority.
1.303 ///
1.304 - /// This method deletes the item with minimum priority relative to \c
1.305 - /// Compare from the heap.
1.306 + /// This function removes the item having minimum priority.
1.307 /// \pre The heap must be non-empty.
1.308 void pop() {
1.309 - container[minimum].in=false;
1.310 + _data[_min].in=false;
1.311
1.312 int head_child=-1;
1.313 - if ( container[minimum].child!=-1 ) {
1.314 - int child=container[minimum].child;
1.315 + if ( _data[_min].child!=-1 ) {
1.316 + int child=_data[_min].child;
1.317 int neighb;
1.318 int prev=-1;
1.319 while( child!=-1 ) {
1.320 - neighb=container[child].right_neighbor;
1.321 - container[child].parent=-1;
1.322 - container[child].right_neighbor=prev;
1.323 + neighb=_data[child].right_neighbor;
1.324 + _data[child].parent=-1;
1.325 + _data[child].right_neighbor=prev;
1.326 head_child=child;
1.327 prev=child;
1.328 child=neighb;
1.329 @@ -214,142 +220,144 @@
1.330 }
1.331
1.332 // The first case is that there are only one root.
1.333 - if ( -1==container[head].right_neighbor ) {
1.334 - head=head_child;
1.335 + if ( -1==_data[_head].right_neighbor ) {
1.336 + _head=head_child;
1.337 }
1.338 // The case where there are more roots.
1.339 else {
1.340 - if( head!=minimum ) { unlace(minimum); }
1.341 - else { head=container[head].right_neighbor; }
1.342 + if( _head!=_min ) { unlace(_min); }
1.343 + else { _head=_data[_head].right_neighbor; }
1.344
1.345 merge(head_child);
1.346 }
1.347 - minimum=find_min();
1.348 - --num_items;
1.349 + _min=findMin();
1.350 + --_num_items;
1.351 }
1.352
1.353 - /// \brief Deletes \c item from the heap.
1.354 + /// \brief Remove the given item from the heap.
1.355 ///
1.356 - /// This method deletes \c item from the heap, if \c item was already
1.357 - /// stored in the heap. It is quite inefficient in Binomial heaps.
1.358 + /// This function removes the given item from the heap if it is
1.359 + /// already stored.
1.360 + /// \param item The item to delete.
1.361 + /// \pre \e item must be in the heap.
1.362 void erase (const Item& item) {
1.363 - int i=iimap[item];
1.364 - if ( i >= 0 && container[i].in ) {
1.365 - decrease( item, container[minimum].prio-1 );
1.366 + int i=_iim[item];
1.367 + if ( i >= 0 && _data[i].in ) {
1.368 + decrease( item, _data[_min].prio-1 );
1.369 pop();
1.370 }
1.371 }
1.372
1.373 - /// \brief Decreases the priority of \c item to \c value.
1.374 + /// \brief Decrease the priority of an item to the given value.
1.375 ///
1.376 - /// This method decreases the priority of \c item to \c value.
1.377 - /// \pre \c item must be stored in the heap with priority at least \c
1.378 - /// value relative to \c Compare.
1.379 + /// This function decreases the priority of an item to the given value.
1.380 + /// \param item The item.
1.381 + /// \param value The priority.
1.382 + /// \pre \e item must be stored in the heap with priority at least \e value.
1.383 void decrease (Item item, const Prio& value) {
1.384 - int i=iimap[item];
1.385 + int i=_iim[item];
1.386
1.387 - if( comp( value,container[i].prio ) ) {
1.388 - container[i].prio=value;
1.389 + if( _comp( value,_data[i].prio ) ) {
1.390 + _data[i].prio=value;
1.391
1.392 - int p_loc=container[i].parent, loc=i;
1.393 + int p_loc=_data[i].parent, loc=i;
1.394 int parent, child, neighb;
1.395
1.396 - while( -1!=p_loc && comp(container[loc].prio,container[p_loc].prio) ) {
1.397 + while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) {
1.398
1.399 // parent set for other loc_child
1.400 - child=container[loc].child;
1.401 + child=_data[loc].child;
1.402 while( -1!=child ) {
1.403 - container[child].parent=p_loc;
1.404 - child=container[child].right_neighbor;
1.405 + _data[child].parent=p_loc;
1.406 + child=_data[child].right_neighbor;
1.407 }
1.408
1.409 // parent set for other p_loc_child
1.410 - child=container[p_loc].child;
1.411 + child=_data[p_loc].child;
1.412 while( -1!=child ) {
1.413 - container[child].parent=loc;
1.414 - child=container[child].right_neighbor;
1.415 + _data[child].parent=loc;
1.416 + child=_data[child].right_neighbor;
1.417 }
1.418
1.419 - child=container[p_loc].child;
1.420 - container[p_loc].child=container[loc].child;
1.421 + child=_data[p_loc].child;
1.422 + _data[p_loc].child=_data[loc].child;
1.423 if( child==loc )
1.424 child=p_loc;
1.425 - container[loc].child=child;
1.426 + _data[loc].child=child;
1.427
1.428 // left_neighb set for p_loc
1.429 - if( container[loc].child!=p_loc ) {
1.430 - while( container[child].right_neighbor!=loc )
1.431 - child=container[child].right_neighbor;
1.432 - container[child].right_neighbor=p_loc;
1.433 + if( _data[loc].child!=p_loc ) {
1.434 + while( _data[child].right_neighbor!=loc )
1.435 + child=_data[child].right_neighbor;
1.436 + _data[child].right_neighbor=p_loc;
1.437 }
1.438
1.439 // left_neighb set for loc
1.440 - parent=container[p_loc].parent;
1.441 - if( -1!=parent ) child=container[parent].child;
1.442 - else child=head;
1.443 + parent=_data[p_loc].parent;
1.444 + if( -1!=parent ) child=_data[parent].child;
1.445 + else child=_head;
1.446
1.447 if( child!=p_loc ) {
1.448 - while( container[child].right_neighbor!=p_loc )
1.449 - child=container[child].right_neighbor;
1.450 - container[child].right_neighbor=loc;
1.451 + while( _data[child].right_neighbor!=p_loc )
1.452 + child=_data[child].right_neighbor;
1.453 + _data[child].right_neighbor=loc;
1.454 }
1.455
1.456 - neighb=container[p_loc].right_neighbor;
1.457 - container[p_loc].right_neighbor=container[loc].right_neighbor;
1.458 - container[loc].right_neighbor=neighb;
1.459 + neighb=_data[p_loc].right_neighbor;
1.460 + _data[p_loc].right_neighbor=_data[loc].right_neighbor;
1.461 + _data[loc].right_neighbor=neighb;
1.462
1.463 - container[p_loc].parent=loc;
1.464 - container[loc].parent=parent;
1.465 + _data[p_loc].parent=loc;
1.466 + _data[loc].parent=parent;
1.467
1.468 - if( -1!=parent && container[parent].child==p_loc )
1.469 - container[parent].child=loc;
1.470 + if( -1!=parent && _data[parent].child==p_loc )
1.471 + _data[parent].child=loc;
1.472
1.473 /*if new parent will be the first root*/
1.474 - if( head==p_loc )
1.475 - head=loc;
1.476 + if( _head==p_loc )
1.477 + _head=loc;
1.478
1.479 - p_loc=container[loc].parent;
1.480 + p_loc=_data[loc].parent;
1.481 }
1.482 }
1.483 - if( comp(value,container[minimum].prio) ) {
1.484 - minimum=i;
1.485 + if( _comp(value,_data[_min].prio) ) {
1.486 + _min=i;
1.487 }
1.488 }
1.489
1.490 - /// \brief Increases the priority of \c item to \c value.
1.491 + /// \brief Increase the priority of an item to the given value.
1.492 ///
1.493 - /// This method sets the priority of \c item to \c value. Though
1.494 - /// there is no precondition on the priority of \c item, this
1.495 - /// method should be used only if it is indeed necessary to increase
1.496 - /// (relative to \c Compare) the priority of \c item, because this
1.497 - /// method is inefficient.
1.498 + /// This function increases the priority of an item to the given value.
1.499 + /// \param item The item.
1.500 + /// \param value The priority.
1.501 + /// \pre \e item must be stored in the heap with priority at most \e value.
1.502 void increase (Item item, const Prio& value) {
1.503 erase(item);
1.504 push(item, value);
1.505 }
1.506
1.507 -
1.508 - /// \brief Returns if \c item is in, has already been in, or has never
1.509 - /// been in the heap.
1.510 + /// \brief Return the state of an item.
1.511 ///
1.512 - /// This method returns PRE_HEAP if \c item has never been in the
1.513 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
1.514 - /// otherwise. In the latter case it is possible that \c item will
1.515 - /// get back to the heap again.
1.516 + /// This method returns \c PRE_HEAP if the given item has never
1.517 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
1.518 + /// and \c POST_HEAP otherwise.
1.519 + /// In the latter case it is possible that the item will get back
1.520 + /// to the heap again.
1.521 + /// \param item The item.
1.522 State state(const Item &item) const {
1.523 - int i=iimap[item];
1.524 + int i=_iim[item];
1.525 if( i>=0 ) {
1.526 - if ( container[i].in ) i=0;
1.527 + if ( _data[i].in ) i=0;
1.528 else i=-2;
1.529 }
1.530 return State(i);
1.531 }
1.532
1.533 - /// \brief Sets the state of the \c item in the heap.
1.534 + /// \brief Set the state of an item in the heap.
1.535 ///
1.536 - /// Sets the state of the \c item in the heap. It can be used to
1.537 - /// manually clear the heap when it is important to achive the
1.538 - /// better time complexity.
1.539 + /// This function sets the state of the given item in the heap.
1.540 + /// It can be used to manually clear the heap when it is important
1.541 + /// to achive better time complexity.
1.542 /// \param i The item.
1.543 /// \param st The state. It should not be \c IN_HEAP.
1.544 void state(const Item& i, State st) {
1.545 @@ -359,7 +367,7 @@
1.546 if (state(i) == IN_HEAP) {
1.547 erase(i);
1.548 }
1.549 - iimap[i] = st;
1.550 + _iim[i] = st;
1.551 break;
1.552 case IN_HEAP:
1.553 break;
1.554 @@ -367,20 +375,20 @@
1.555 }
1.556
1.557 private:
1.558 - int find_min() {
1.559 + int findMin() {
1.560 int min_loc=-1, min_val;
1.561 - int x=head;
1.562 + int x=_head;
1.563 if( x!=-1 ) {
1.564 - min_val=container[x].prio;
1.565 + min_val=_data[x].prio;
1.566 min_loc=x;
1.567 - x=container[x].right_neighbor;
1.568 + x=_data[x].right_neighbor;
1.569
1.570 while( x!=-1 ) {
1.571 - if( comp( container[x].prio,min_val ) ) {
1.572 - min_val=container[x].prio;
1.573 + if( _comp( _data[x].prio,min_val ) ) {
1.574 + min_val=_data[x].prio;
1.575 min_loc=x;
1.576 }
1.577 - x=container[x].right_neighbor;
1.578 + x=_data[x].right_neighbor;
1.579 }
1.580 }
1.581 return min_loc;
1.582 @@ -389,29 +397,29 @@
1.583 void merge(int a) {
1.584 interleave(a);
1.585
1.586 - int x=head;
1.587 + int x=_head;
1.588 if( -1!=x ) {
1.589 - int x_prev=-1, x_next=container[x].right_neighbor;
1.590 + int x_prev=-1, x_next=_data[x].right_neighbor;
1.591 while( -1!=x_next ) {
1.592 - if( container[x].degree!=container[x_next].degree || ( -1!=container[x_next].right_neighbor && container[container[x_next].right_neighbor].degree==container[x].degree ) ) {
1.593 + if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
1.594 x_prev=x;
1.595 x=x_next;
1.596 }
1.597 else {
1.598 - if( comp(container[x].prio,container[x_next].prio) ) {
1.599 - container[x].right_neighbor=container[x_next].right_neighbor;
1.600 + if( _comp(_data[x].prio,_data[x_next].prio) ) {
1.601 + _data[x].right_neighbor=_data[x_next].right_neighbor;
1.602 fuse(x_next,x);
1.603 }
1.604 else {
1.605 - if( -1==x_prev ) { head=x_next; }
1.606 + if( -1==x_prev ) { _head=x_next; }
1.607 else {
1.608 - container[x_prev].right_neighbor=x_next;
1.609 + _data[x_prev].right_neighbor=x_next;
1.610 }
1.611 fuse(x,x_next);
1.612 x=x_next;
1.613 }
1.614 }
1.615 - x_next=container[x].right_neighbor;
1.616 + x_next=_data[x].right_neighbor;
1.617 }
1.618 }
1.619 }
1.620 @@ -419,68 +427,68 @@
1.621 void interleave(int a) {
1.622 int other=-1, head_other=-1;
1.623
1.624 - while( -1!=a || -1!=head ) {
1.625 + while( -1!=a || -1!=_head ) {
1.626 if( -1==a ) {
1.627 if( -1==head_other ) {
1.628 - head_other=head;
1.629 + head_other=_head;
1.630 }
1.631 else {
1.632 - container[other].right_neighbor=head;
1.633 + _data[other].right_neighbor=_head;
1.634 }
1.635 - head=-1;
1.636 + _head=-1;
1.637 }
1.638 - else if( -1==head ) {
1.639 + else if( -1==_head ) {
1.640 if( -1==head_other ) {
1.641 head_other=a;
1.642 }
1.643 else {
1.644 - container[other].right_neighbor=a;
1.645 + _data[other].right_neighbor=a;
1.646 }
1.647 a=-1;
1.648 }
1.649 else {
1.650 - if( container[a].degree<container[head].degree ) {
1.651 + if( _data[a].degree<_data[_head].degree ) {
1.652 if( -1==head_other ) {
1.653 head_other=a;
1.654 }
1.655 else {
1.656 - container[other].right_neighbor=a;
1.657 + _data[other].right_neighbor=a;
1.658 }
1.659 other=a;
1.660 - a=container[a].right_neighbor;
1.661 + a=_data[a].right_neighbor;
1.662 }
1.663 else {
1.664 if( -1==head_other ) {
1.665 - head_other=head;
1.666 + head_other=_head;
1.667 }
1.668 else {
1.669 - container[other].right_neighbor=head;
1.670 + _data[other].right_neighbor=_head;
1.671 }
1.672 - other=head;
1.673 - head=container[head].right_neighbor;
1.674 + other=_head;
1.675 + _head=_data[_head].right_neighbor;
1.676 }
1.677 }
1.678 }
1.679 - head=head_other;
1.680 + _head=head_other;
1.681 }
1.682
1.683 // Lacing a under b
1.684 void fuse(int a, int b) {
1.685 - container[a].parent=b;
1.686 - container[a].right_neighbor=container[b].child;
1.687 - container[b].child=a;
1.688 + _data[a].parent=b;
1.689 + _data[a].right_neighbor=_data[b].child;
1.690 + _data[b].child=a;
1.691
1.692 - ++container[b].degree;
1.693 + ++_data[b].degree;
1.694 }
1.695
1.696 // It is invoked only if a has siblings.
1.697 void unlace(int a) {
1.698 - int neighb=container[a].right_neighbor;
1.699 - int other=head;
1.700 + int neighb=_data[a].right_neighbor;
1.701 + int other=_head;
1.702
1.703 - while( container[other].right_neighbor!=a )
1.704 - other=container[other].right_neighbor;
1.705 - container[other].right_neighbor=neighb;
1.706 + while( _data[other].right_neighbor!=a )
1.707 + other=_data[other].right_neighbor;
1.708 + _data[other].right_neighbor=neighb;
1.709 }
1.710
1.711 private:
2.1 --- a/lemon/fourary_heap.h Thu Jul 09 02:39:47 2009 +0200
2.2 +++ b/lemon/fourary_heap.h Thu Jul 09 04:07:08 2009 +0200
2.3 @@ -1,8 +1,8 @@
2.4 -/* -*- C++ -*-
2.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.6 *
2.7 - * This file is a part of LEMON, a generic C++ optimization library
2.8 + * This file is a part of LEMON, a generic C++ optimization library.
2.9 *
2.10 - * Copyright (C) 2003-2008
2.11 + * Copyright (C) 2003-2009
2.12 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.13 * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.14 *
2.15 @@ -19,159 +19,158 @@
2.16 #ifndef LEMON_FOURARY_HEAP_H
2.17 #define LEMON_FOURARY_HEAP_H
2.18
2.19 -///\ingroup auxdat
2.20 +///\ingroup heaps
2.21 ///\file
2.22 -///\brief 4ary Heap implementation.
2.23 +///\brief Fourary heap implementation.
2.24
2.25 -#include <iostream>
2.26 #include <vector>
2.27 #include <utility>
2.28 #include <functional>
2.29
2.30 namespace lemon {
2.31
2.32 - ///\ingroup auxdat
2.33 + /// \ingroup heaps
2.34 ///
2.35 - ///\brief A 4ary Heap implementation.
2.36 + ///\brief Fourary heap data structure.
2.37 ///
2.38 - ///This class implements the \e 4ary \e heap data structure. A \e heap
2.39 - ///is a data structure for storing items with specified values called \e
2.40 - ///priorities in such a way that finding the item with minimum priority is
2.41 - ///efficient. \c Compare specifies the ordering of the priorities. In a heap
2.42 - ///one can change the priority of an item, add or erase an item, etc.
2.43 + /// This class implements the \e fourary \e heap data structure.
2.44 + /// It fully conforms to the \ref concepts::Heap "heap concept".
2.45 ///
2.46 - ///\param _Prio Type of the priority of the items.
2.47 - ///\param _ItemIntMap A read and writable Item int map, used internally
2.48 - ///to handle the cross references.
2.49 - ///\param _Compare A class for the ordering of the priorities. The
2.50 - ///default is \c std::less<_Prio>.
2.51 + /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap"
2.52 + /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap",
2.53 + /// but its nodes have at most four children, instead of two.
2.54 ///
2.55 - ///\sa FibHeap
2.56 - ///\sa Dijkstra
2.57 - ///\author Dorian Batha
2.58 + /// \tparam PR Type of the priorities of the items.
2.59 + /// \tparam IM A read-writable item map with \c int values, used
2.60 + /// internally to handle the cross references.
2.61 + /// \tparam CMP A functor class for comparing the priorities.
2.62 + /// The default is \c std::less<PR>.
2.63 + ///
2.64 + ///\sa BinHeap
2.65 + ///\sa KaryHeap
2.66 +#ifdef DOXYGEN
2.67 + template <typename PR, typename IM, typename CMP>
2.68 +#else
2.69 + template <typename PR, typename IM, typename CMP = std::less<PR> >
2.70 +#endif
2.71 + class FouraryHeap {
2.72 + public:
2.73 + /// Type of the item-int map.
2.74 + typedef IM ItemIntMap;
2.75 + /// Type of the priorities.
2.76 + typedef PR Prio;
2.77 + /// Type of the items stored in the heap.
2.78 + typedef typename ItemIntMap::Key Item;
2.79 + /// Type of the item-priority pairs.
2.80 + typedef std::pair<Item,Prio> Pair;
2.81 + /// Functor type for comparing the priorities.
2.82 + typedef CMP Compare;
2.83
2.84 - template <typename _Prio, typename _ItemIntMap,
2.85 - typename _Compare = std::less<_Prio> >
2.86 -
2.87 - class FouraryHeap {
2.88 -
2.89 - public:
2.90 - ///\e
2.91 - typedef _ItemIntMap ItemIntMap;
2.92 - ///\e
2.93 - typedef _Prio Prio;
2.94 - ///\e
2.95 - typedef typename ItemIntMap::Key Item;
2.96 - ///\e
2.97 - typedef std::pair<Item,Prio> Pair;
2.98 - ///\e
2.99 - typedef _Compare Compare;
2.100 -
2.101 - /// \brief Type to represent the items states.
2.102 + /// \brief Type to represent the states of the items.
2.103 ///
2.104 - /// Each Item element have a state associated to it. It may be "in heap",
2.105 - /// "pre heap" or "post heap". The latter two are indifferent from the
2.106 + /// Each item has a state associated to it. It can be "in heap",
2.107 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
2.108 /// heap's point of view, but may be useful to the user.
2.109 ///
2.110 - /// The ItemIntMap \e should be initialized in such way that it maps
2.111 - /// PRE_HEAP (-1) to any element to be put in the heap...
2.112 + /// The item-int map must be initialized in such way that it assigns
2.113 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
2.114 enum State {
2.115 - IN_HEAP = 0,
2.116 - PRE_HEAP = -1,
2.117 - POST_HEAP = -2
2.118 + IN_HEAP = 0, ///< = 0.
2.119 + PRE_HEAP = -1, ///< = -1.
2.120 + POST_HEAP = -2 ///< = -2.
2.121 };
2.122
2.123 private:
2.124 - std::vector<Pair> data;
2.125 - Compare comp;
2.126 - ItemIntMap &iim;
2.127 + std::vector<Pair> _data;
2.128 + Compare _comp;
2.129 + ItemIntMap &_iim;
2.130
2.131 public:
2.132 - /// \brief The constructor.
2.133 + /// \brief Constructor.
2.134 ///
2.135 - /// The constructor.
2.136 - /// \param _iim should be given to the constructor, since it is used
2.137 - /// internally to handle the cross references. The value of the map
2.138 - /// should be PRE_HEAP (-1) for each element.
2.139 - explicit FouraryHeap(ItemIntMap &_iim) : iim(_iim) {}
2.140 + /// Constructor.
2.141 + /// \param map A map that assigns \c int values to the items.
2.142 + /// It is used internally to handle the cross references.
2.143 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
2.144 + explicit FouraryHeap(ItemIntMap &map) : _iim(map) {}
2.145
2.146 - /// \brief The constructor.
2.147 + /// \brief Constructor.
2.148 ///
2.149 - /// The constructor.
2.150 - /// \param _iim should be given to the constructor, since it is used
2.151 - /// internally to handle the cross references. The value of the map
2.152 - /// should be PRE_HEAP (-1) for each element.
2.153 + /// Constructor.
2.154 + /// \param map A map that assigns \c int values to the items.
2.155 + /// It is used internally to handle the cross references.
2.156 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
2.157 + /// \param comp The function object used for comparing the priorities.
2.158 + FouraryHeap(ItemIntMap &map, const Compare &comp)
2.159 + : _iim(map), _comp(comp) {}
2.160 +
2.161 + /// \brief The number of items stored in the heap.
2.162 ///
2.163 - /// \param _comp The comparator function object.
2.164 - FouraryHeap(ItemIntMap &_iim, const Compare &_comp)
2.165 - : iim(_iim), comp(_comp) {}
2.166 + /// This function returns the number of items stored in the heap.
2.167 + int size() const { return _data.size(); }
2.168
2.169 - /// The number of items stored in the heap.
2.170 + /// \brief Check if the heap is empty.
2.171 ///
2.172 - /// \brief Returns the number of items stored in the heap.
2.173 - int size() const { return data.size(); }
2.174 + /// This function returns \c true if the heap is empty.
2.175 + bool empty() const { return _data.empty(); }
2.176
2.177 - /// \brief Checks if the heap stores no items.
2.178 + /// \brief Make the heap empty.
2.179 ///
2.180 - /// Returns \c true if and only if the heap stores no items.
2.181 - bool empty() const { return data.empty(); }
2.182 -
2.183 - /// \brief Make empty this heap.
2.184 - ///
2.185 - /// Make empty this heap. It does not change the cross reference map.
2.186 - /// If you want to reuse what is not surely empty you should first clear
2.187 - /// the heap and after that you should set the cross reference map for
2.188 - /// each item to \c PRE_HEAP.
2.189 - void clear() { data.clear(); }
2.190 + /// This functon makes the heap empty.
2.191 + /// It does not change the cross reference map. If you want to reuse
2.192 + /// a heap that is not surely empty, you should first clear it and
2.193 + /// then you should set the cross reference map to \c PRE_HEAP
2.194 + /// for each item.
2.195 + void clear() { _data.clear(); }
2.196
2.197 private:
2.198 static int parent(int i) { return (i-1)/4; }
2.199 static int firstChild(int i) { return 4*i+1; }
2.200
2.201 bool less(const Pair &p1, const Pair &p2) const {
2.202 - return comp(p1.second, p2.second);
2.203 + return _comp(p1.second, p2.second);
2.204 }
2.205
2.206 - int find_min(const int child, const int length) {
2.207 + int findMin(const int child, const int length) {
2.208 int min=child;
2.209 if( child+3<length ) {
2.210 - if( less(data[child+3], data[min]) )
2.211 + if( less(_data[child+3], _data[min]) )
2.212 min=child+3;
2.213 - if( less(data[child+2], data[min]) )
2.214 + if( less(_data[child+2], _data[min]) )
2.215 min=child+2;
2.216 - if( less(data[child+1], data[min]) )
2.217 + if( less(_data[child+1], _data[min]) )
2.218 min=child+1;
2.219 }
2.220 else if( child+2<length ) {
2.221 - if( less(data[child+2], data[min]) )
2.222 + if( less(_data[child+2], _data[min]) )
2.223 min=child+2;
2.224 - if( less(data[child+1], data[min]) )
2.225 + if( less(_data[child+1], _data[min]) )
2.226 min=child+1;
2.227 }
2.228 else if( child+1<length ) {
2.229 - if( less(data[child+1], data[min]) )
2.230 + if( less(_data[child+1], _data[min]) )
2.231 min=child+1;
2.232 }
2.233 return min;
2.234 }
2.235
2.236 - void bubble_up(int hole, Pair p) {
2.237 + void bubbleUp(int hole, Pair p) {
2.238 int par = parent(hole);
2.239 - while( hole>0 && less(p,data[par]) ) {
2.240 - move(data[par],hole);
2.241 + while( hole>0 && less(p,_data[par]) ) {
2.242 + move(_data[par],hole);
2.243 hole = par;
2.244 par = parent(hole);
2.245 }
2.246 move(p, hole);
2.247 }
2.248
2.249 - void bubble_down(int hole, Pair p, int length) {
2.250 + void bubbleDown(int hole, Pair p, int length) {
2.251 int child = firstChild(hole);
2.252 while( child<length && length>1 ) {
2.253 - child = find_min(child,length);
2.254 - if( !less(data[child], p) )
2.255 + child = findMin(child,length);
2.256 + if( !less(_data[child], p) )
2.257 goto ok;
2.258 - move(data[child], hole);
2.259 + move(_data[child], hole);
2.260 hole = child;
2.261 child = firstChild(hole);
2.262 }
2.263 @@ -180,142 +179,143 @@
2.264 }
2.265
2.266 void move(const Pair &p, int i) {
2.267 - data[i] = p;
2.268 - iim.set(p.first, i);
2.269 + _data[i] = p;
2.270 + _iim.set(p.first, i);
2.271 }
2.272
2.273 public:
2.274 -
2.275 /// \brief Insert a pair of item and priority into the heap.
2.276 ///
2.277 - /// Adds \c p.first to the heap with priority \c p.second.
2.278 + /// This function inserts \c p.first to the heap with priority
2.279 + /// \c p.second.
2.280 /// \param p The pair to insert.
2.281 + /// \pre \c p.first must not be stored in the heap.
2.282 void push(const Pair &p) {
2.283 - int n = data.size();
2.284 - data.resize(n+1);
2.285 - bubble_up(n, p);
2.286 + int n = _data.size();
2.287 + _data.resize(n+1);
2.288 + bubbleUp(n, p);
2.289 }
2.290
2.291 - /// \brief Insert an item into the heap with the given heap.
2.292 + /// \brief Insert an item into the heap with the given priority.
2.293 ///
2.294 - /// Adds \c i to the heap with priority \c p.
2.295 + /// This function inserts the given item into the heap with the
2.296 + /// given priority.
2.297 /// \param i The item to insert.
2.298 /// \param p The priority of the item.
2.299 + /// \pre \e i must not be stored in the heap.
2.300 void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
2.301
2.302 - /// \brief Returns the item with minimum priority relative to \c Compare.
2.303 + /// \brief Return the item having minimum priority.
2.304 ///
2.305 - /// This method returns the item with minimum priority relative to \c
2.306 - /// Compare.
2.307 - /// \pre The heap must be nonempty.
2.308 - Item top() const { return data[0].first; }
2.309 + /// This function returns the item having minimum priority.
2.310 + /// \pre The heap must be non-empty.
2.311 + Item top() const { return _data[0].first; }
2.312
2.313 - /// \brief Returns the minimum priority relative to \c Compare.
2.314 + /// \brief The minimum priority.
2.315 ///
2.316 - /// It returns the minimum priority relative to \c Compare.
2.317 - /// \pre The heap must be nonempty.
2.318 - Prio prio() const { return data[0].second; }
2.319 + /// This function returns the minimum priority.
2.320 + /// \pre The heap must be non-empty.
2.321 + Prio prio() const { return _data[0].second; }
2.322
2.323 - /// \brief Deletes the item with minimum priority relative to \c Compare.
2.324 + /// \brief Remove the item having minimum priority.
2.325 ///
2.326 - /// This method deletes the item with minimum priority relative to \c
2.327 - /// Compare from the heap.
2.328 + /// This function removes the item having minimum priority.
2.329 /// \pre The heap must be non-empty.
2.330 void pop() {
2.331 - int n = data.size()-1;
2.332 - iim.set(data[0].first, POST_HEAP);
2.333 - if (n>0) bubble_down(0, data[n], n);
2.334 - data.pop_back();
2.335 + int n = _data.size()-1;
2.336 + _iim.set(_data[0].first, POST_HEAP);
2.337 + if (n>0) bubbleDown(0, _data[n], n);
2.338 + _data.pop_back();
2.339 }
2.340
2.341 - /// \brief Deletes \c i from the heap.
2.342 + /// \brief Remove the given item from the heap.
2.343 ///
2.344 - /// This method deletes item \c i from the heap.
2.345 - /// \param i The item to erase.
2.346 - /// \pre The item should be in the heap.
2.347 + /// This function removes the given item from the heap if it is
2.348 + /// already stored.
2.349 + /// \param i The item to delete.
2.350 + /// \pre \e i must be in the heap.
2.351 void erase(const Item &i) {
2.352 - int h = iim[i];
2.353 - int n = data.size()-1;
2.354 - iim.set(data[h].first, POST_HEAP);
2.355 + int h = _iim[i];
2.356 + int n = _data.size()-1;
2.357 + _iim.set(_data[h].first, POST_HEAP);
2.358 if( h<n ) {
2.359 - if( less(data[parent(h)], data[n]) )
2.360 - bubble_down(h, data[n], n);
2.361 + if( less(_data[parent(h)], _data[n]) )
2.362 + bubbleDown(h, _data[n], n);
2.363 else
2.364 - bubble_up(h, data[n]);
2.365 + bubbleUp(h, _data[n]);
2.366 }
2.367 - data.pop_back();
2.368 + _data.pop_back();
2.369 }
2.370
2.371 - /// \brief Returns the priority of \c i.
2.372 + /// \brief The priority of the given item.
2.373 ///
2.374 - /// This function returns the priority of item \c i.
2.375 - /// \pre \c i must be in the heap.
2.376 + /// This function returns the priority of the given item.
2.377 /// \param i The item.
2.378 + /// \pre \e i must be in the heap.
2.379 Prio operator[](const Item &i) const {
2.380 - int idx = iim[i];
2.381 - return data[idx].second;
2.382 + int idx = _iim[i];
2.383 + return _data[idx].second;
2.384 }
2.385
2.386 - /// \brief \c i gets to the heap with priority \c p independently
2.387 - /// if \c i was already there.
2.388 + /// \brief Set the priority of an item or insert it, if it is
2.389 + /// not stored in the heap.
2.390 ///
2.391 - /// This method calls \ref push(\c i, \c p) if \c i is not stored
2.392 - /// in the heap and sets the priority of \c i to \c p otherwise.
2.393 + /// This method sets the priority of the given item if it is
2.394 + /// already stored in the heap. Otherwise it inserts the given
2.395 + /// item into the heap with the given priority.
2.396 /// \param i The item.
2.397 /// \param p The priority.
2.398 void set(const Item &i, const Prio &p) {
2.399 - int idx = iim[i];
2.400 + int idx = _iim[i];
2.401 if( idx < 0 )
2.402 push(i,p);
2.403 - else if( comp(p, data[idx].second) )
2.404 - bubble_up(idx, Pair(i,p));
2.405 + else if( _comp(p, _data[idx].second) )
2.406 + bubbleUp(idx, Pair(i,p));
2.407 else
2.408 - bubble_down(idx, Pair(i,p), data.size());
2.409 + bubbleDown(idx, Pair(i,p), _data.size());
2.410 }
2.411
2.412 - /// \brief Decreases the priority of \c i to \c p.
2.413 + /// \brief Decrease the priority of an item to the given value.
2.414 ///
2.415 - /// This method decreases the priority of item \c i to \c p.
2.416 - /// \pre \c i must be stored in the heap with priority at least \c
2.417 - /// p relative to \c Compare.
2.418 + /// This function decreases the priority of an item to the given value.
2.419 /// \param i The item.
2.420 /// \param p The priority.
2.421 + /// \pre \e i must be stored in the heap with priority at least \e p.
2.422 void decrease(const Item &i, const Prio &p) {
2.423 - int idx = iim[i];
2.424 - bubble_up(idx, Pair(i,p));
2.425 + int idx = _iim[i];
2.426 + bubbleUp(idx, Pair(i,p));
2.427 }
2.428
2.429 - /// \brief Increases the priority of \c i to \c p.
2.430 + /// \brief Increase the priority of an item to the given value.
2.431 ///
2.432 - /// This method sets the priority of item \c i to \c p.
2.433 - /// \pre \c i must be stored in the heap with priority at most \c
2.434 - /// p relative to \c Compare.
2.435 + /// This function increases the priority of an item to the given value.
2.436 /// \param i The item.
2.437 /// \param p The priority.
2.438 + /// \pre \e i must be stored in the heap with priority at most \e p.
2.439 void increase(const Item &i, const Prio &p) {
2.440 - int idx = iim[i];
2.441 - bubble_down(idx, Pair(i,p), data.size());
2.442 + int idx = _iim[i];
2.443 + bubbleDown(idx, Pair(i,p), _data.size());
2.444 }
2.445
2.446 - /// \brief Returns if \c item is in, has already been in, or has
2.447 - /// never been in the heap.
2.448 + /// \brief Return the state of an item.
2.449 ///
2.450 - /// This method returns PRE_HEAP if \c item has never been in the
2.451 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
2.452 - /// otherwise. In the latter case it is possible that \c item will
2.453 - /// get back to the heap again.
2.454 + /// This method returns \c PRE_HEAP if the given item has never
2.455 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
2.456 + /// and \c POST_HEAP otherwise.
2.457 + /// In the latter case it is possible that the item will get back
2.458 + /// to the heap again.
2.459 /// \param i The item.
2.460 State state(const Item &i) const {
2.461 - int s = iim[i];
2.462 + int s = _iim[i];
2.463 if (s>=0) s=0;
2.464 return State(s);
2.465 }
2.466
2.467 - /// \brief Sets the state of the \c item in the heap.
2.468 + /// \brief Set the state of an item in the heap.
2.469 ///
2.470 - /// Sets the state of the \c item in the heap. It can be used to
2.471 - /// manually clear the heap when it is important to achive the
2.472 - /// better time complexity.
2.473 + /// This function sets the state of the given item in the heap.
2.474 + /// It can be used to manually clear the heap when it is important
2.475 + /// to achive better time complexity.
2.476 /// \param i The item.
2.477 /// \param st The state. It should not be \c IN_HEAP.
2.478 void state(const Item& i, State st) {
2.479 @@ -323,24 +323,25 @@
2.480 case POST_HEAP:
2.481 case PRE_HEAP:
2.482 if (state(i) == IN_HEAP) erase(i);
2.483 - iim[i] = st;
2.484 + _iim[i] = st;
2.485 break;
2.486 case IN_HEAP:
2.487 break;
2.488 }
2.489 }
2.490
2.491 - /// \brief Replaces an item in the heap.
2.492 + /// \brief Replace an item in the heap.
2.493 ///
2.494 - /// The \c i item is replaced with \c j item. The \c i item should
2.495 - /// be in the heap, while the \c j should be out of the heap. The
2.496 - /// \c i item will out of the heap and \c j will be in the heap
2.497 - /// with the same prioriority as prevoiusly the \c i item.
2.498 + /// This function replaces item \c i with item \c j.
2.499 + /// Item \c i must be in the heap, while \c j must be out of the heap.
2.500 + /// After calling this method, item \c i will be out of the
2.501 + /// heap and \c j will be in the heap with the same prioriority
2.502 + /// as item \c i had before.
2.503 void replace(const Item& i, const Item& j) {
2.504 - int idx = iim[i];
2.505 - iim.set(i, iim[j]);
2.506 - iim.set(j, idx);
2.507 - data[idx].first = j;
2.508 + int idx = _iim[i];
2.509 + _iim.set(i, _iim[j]);
2.510 + _iim.set(j, idx);
2.511 + _data[idx].first = j;
2.512 }
2.513
2.514 }; // class FouraryHeap
3.1 --- a/lemon/kary_heap.h Thu Jul 09 02:39:47 2009 +0200
3.2 +++ b/lemon/kary_heap.h Thu Jul 09 04:07:08 2009 +0200
3.3 @@ -1,8 +1,8 @@
3.4 -/* -*- C++ -*-
3.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.6 *
3.7 - * This file is a part of LEMON, a generic C++ optimization library
3.8 + * This file is a part of LEMON, a generic C++ optimization library.
3.9 *
3.10 - * Copyright (C) 2003-2008
3.11 + * Copyright (C) 2003-2009
3.12 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.13 * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.14 *
3.15 @@ -19,152 +19,151 @@
3.16 #ifndef LEMON_KARY_HEAP_H
3.17 #define LEMON_KARY_HEAP_H
3.18
3.19 -///\ingroup auxdat
3.20 +///\ingroup heaps
3.21 ///\file
3.22 -///\brief Kary Heap implementation.
3.23 +///\brief Fourary heap implementation.
3.24
3.25 -#include <iostream>
3.26 #include <vector>
3.27 #include <utility>
3.28 #include <functional>
3.29
3.30 namespace lemon {
3.31
3.32 - ///\ingroup auxdat
3.33 + /// \ingroup heaps
3.34 ///
3.35 - ///\brief A Kary Heap implementation.
3.36 + ///\brief K-ary heap data structure.
3.37 ///
3.38 - ///This class implements the \e Kary \e heap data structure. A \e heap
3.39 - ///is a data structure for storing items with specified values called \e
3.40 - ///priorities in such a way that finding the item with minimum priority is
3.41 - ///efficient. \c Compare specifies the ordering of the priorities. In a heap
3.42 - ///one can change the priority of an item, add or erase an item, etc.
3.43 + /// This class implements the \e K-ary \e heap data structure.
3.44 + /// It fully conforms to the \ref concepts::Heap "heap concept".
3.45 ///
3.46 - ///\param _Prio Type of the priority of the items.
3.47 - ///\param _ItemIntMap A read and writable Item int map, used internally
3.48 - ///to handle the cross references.
3.49 - ///\param _Compare A class for the ordering of the priorities. The
3.50 - ///default is \c std::less<_Prio>.
3.51 + /// The \ref KaryHeap "K-ary heap" is a generalization of the
3.52 + /// \ref BinHeap "binary heap" structure, its nodes have at most
3.53 + /// \c K children, instead of two.
3.54 + /// \ref BinHeap and \ref FouraryHeap are specialized implementations
3.55 + /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively.
3.56 ///
3.57 - ///\sa FibHeap
3.58 - ///\sa Dijkstra
3.59 - ///\author Dorian Batha
3.60 + /// \tparam PR Type of the priorities of the items.
3.61 + /// \tparam IM A read-writable item map with \c int values, used
3.62 + /// internally to handle the cross references.
3.63 + /// \tparam CMP A functor class for comparing the priorities.
3.64 + /// The default is \c std::less<PR>.
3.65 + ///
3.66 + ///\sa BinHeap
3.67 + ///\sa FouraryHeap
3.68 +#ifdef DOXYGEN
3.69 + template <typename PR, typename IM, typename CMP>
3.70 +#else
3.71 + template <typename PR, typename IM, typename CMP = std::less<PR> >
3.72 +#endif
3.73 + class KaryHeap {
3.74 + public:
3.75 + /// Type of the item-int map.
3.76 + typedef IM ItemIntMap;
3.77 + /// Type of the priorities.
3.78 + typedef PR Prio;
3.79 + /// Type of the items stored in the heap.
3.80 + typedef typename ItemIntMap::Key Item;
3.81 + /// Type of the item-priority pairs.
3.82 + typedef std::pair<Item,Prio> Pair;
3.83 + /// Functor type for comparing the priorities.
3.84 + typedef CMP Compare;
3.85
3.86 - template <typename _Prio, typename _ItemIntMap,
3.87 - typename _Compare = std::less<_Prio> >
3.88 -
3.89 - class KaryHeap {
3.90 -
3.91 - public:
3.92 - ///\e
3.93 - typedef _ItemIntMap ItemIntMap;
3.94 - ///\e
3.95 - typedef _Prio Prio;
3.96 - ///\e
3.97 - typedef typename ItemIntMap::Key Item;
3.98 - ///\e
3.99 - typedef std::pair<Item,Prio> Pair;
3.100 - ///\e
3.101 - typedef _Compare Compare;
3.102 - ///\e
3.103 -
3.104 - /// \brief Type to represent the items states.
3.105 + /// \brief Type to represent the states of the items.
3.106 ///
3.107 - /// Each Item element have a state associated to it. It may be "in heap",
3.108 - /// "pre heap" or "post heap". The latter two are indifferent from the
3.109 + /// Each item has a state associated to it. It can be "in heap",
3.110 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
3.111 /// heap's point of view, but may be useful to the user.
3.112 ///
3.113 - /// The ItemIntMap \e should be initialized in such way that it maps
3.114 - /// PRE_HEAP (-1) to any element to be put in the heap...
3.115 + /// The item-int map must be initialized in such way that it assigns
3.116 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
3.117 enum State {
3.118 - IN_HEAP = 0,
3.119 - PRE_HEAP = -1,
3.120 - POST_HEAP = -2
3.121 + IN_HEAP = 0, ///< = 0.
3.122 + PRE_HEAP = -1, ///< = -1.
3.123 + POST_HEAP = -2 ///< = -2.
3.124 };
3.125
3.126 private:
3.127 - std::vector<Pair> data;
3.128 - Compare comp;
3.129 - ItemIntMap &iim;
3.130 - int K;
3.131 + std::vector<Pair> _data;
3.132 + Compare _comp;
3.133 + ItemIntMap &_iim;
3.134 + int _K;
3.135
3.136 public:
3.137 - /// \brief The constructor.
3.138 + /// \brief Constructor.
3.139 ///
3.140 - /// The constructor.
3.141 - /// \param _iim should be given to the constructor, since it is used
3.142 - /// internally to handle the cross references. The value of the map
3.143 - /// should be PRE_HEAP (-1) for each element.
3.144 - explicit KaryHeap(ItemIntMap &_iim, const int &_K=32) : iim(_iim), K(_K) {}
3.145 + /// Constructor.
3.146 + /// \param map A map that assigns \c int values to the items.
3.147 + /// It is used internally to handle the cross references.
3.148 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
3.149 + explicit KaryHeap(ItemIntMap &map, int K=32) : _iim(map), _K(K) {}
3.150
3.151 - /// \brief The constructor.
3.152 + /// \brief Constructor.
3.153 ///
3.154 - /// The constructor.
3.155 - /// \param _iim should be given to the constructor, since it is used
3.156 - /// internally to handle the cross references. The value of the map
3.157 - /// should be PRE_HEAP (-1) for each element.
3.158 + /// Constructor.
3.159 + /// \param map A map that assigns \c int values to the items.
3.160 + /// It is used internally to handle the cross references.
3.161 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
3.162 + /// \param comp The function object used for comparing the priorities.
3.163 + KaryHeap(ItemIntMap &map, const Compare &comp, int K=32)
3.164 + : _iim(map), _comp(comp), _K(K) {}
3.165 +
3.166 + /// \brief The number of items stored in the heap.
3.167 ///
3.168 - /// \param _comp The comparator function object.
3.169 - KaryHeap(ItemIntMap &_iim, const Compare &_comp, const int &_K=32)
3.170 - : iim(_iim), comp(_comp), K(_K) {}
3.171 + /// This function returns the number of items stored in the heap.
3.172 + int size() const { return _data.size(); }
3.173
3.174 + /// \brief Check if the heap is empty.
3.175 + ///
3.176 + /// This function returns \c true if the heap is empty.
3.177 + bool empty() const { return _data.empty(); }
3.178
3.179 - /// The number of items stored in the heap.
3.180 + /// \brief Make the heap empty.
3.181 ///
3.182 - /// \brief Returns the number of items stored in the heap.
3.183 - int size() const { return data.size(); }
3.184 -
3.185 - /// \brief Checks if the heap stores no items.
3.186 - ///
3.187 - /// Returns \c true if and only if the heap stores no items.
3.188 - bool empty() const { return data.empty(); }
3.189 -
3.190 - /// \brief Make empty this heap.
3.191 - ///
3.192 - /// Make empty this heap. It does not change the cross reference map.
3.193 - /// If you want to reuse what is not surely empty you should first clear
3.194 - /// the heap and after that you should set the cross reference map for
3.195 - /// each item to \c PRE_HEAP.
3.196 - void clear() { data.clear(); }
3.197 + /// This functon makes the heap empty.
3.198 + /// It does not change the cross reference map. If you want to reuse
3.199 + /// a heap that is not surely empty, you should first clear it and
3.200 + /// then you should set the cross reference map to \c PRE_HEAP
3.201 + /// for each item.
3.202 + void clear() { _data.clear(); }
3.203
3.204 private:
3.205 - int parent(int i) { return (i-1)/K; }
3.206 - int first_child(int i) { return K*i+1; }
3.207 + int parent(int i) { return (i-1)/_K; }
3.208 + int firstChild(int i) { return _K*i+1; }
3.209
3.210 bool less(const Pair &p1, const Pair &p2) const {
3.211 - return comp(p1.second, p2.second);
3.212 + return _comp(p1.second, p2.second);
3.213 }
3.214
3.215 - int find_min(const int child, const int length) {
3.216 + int findMin(const int child, const int length) {
3.217 int min=child, i=1;
3.218 - while( i<K && child+i<length ) {
3.219 - if( less(data[child+i], data[min]) )
3.220 + while( i<_K && child+i<length ) {
3.221 + if( less(_data[child+i], _data[min]) )
3.222 min=child+i;
3.223 ++i;
3.224 }
3.225 return min;
3.226 }
3.227
3.228 - void bubble_up(int hole, Pair p) {
3.229 + void bubbleUp(int hole, Pair p) {
3.230 int par = parent(hole);
3.231 - while( hole>0 && less(p,data[par]) ) {
3.232 - move(data[par],hole);
3.233 + while( hole>0 && less(p,_data[par]) ) {
3.234 + move(_data[par],hole);
3.235 hole = par;
3.236 par = parent(hole);
3.237 }
3.238 move(p, hole);
3.239 }
3.240
3.241 - void bubble_down(int hole, Pair p, int length) {
3.242 + void bubbleDown(int hole, Pair p, int length) {
3.243 if( length>1 ) {
3.244 - int child = first_child(hole);
3.245 + int child = firstChild(hole);
3.246 while( child<length ) {
3.247 - child = find_min(child, length);
3.248 - if( !less(data[child], p) )
3.249 + child = findMin(child, length);
3.250 + if( !less(_data[child], p) )
3.251 goto ok;
3.252 - move(data[child], hole);
3.253 + move(_data[child], hole);
3.254 hole = child;
3.255 - child = first_child(hole);
3.256 + child = firstChild(hole);
3.257 }
3.258 }
3.259 ok:
3.260 @@ -172,167 +171,169 @@
3.261 }
3.262
3.263 void move(const Pair &p, int i) {
3.264 - data[i] = p;
3.265 - iim.set(p.first, i);
3.266 + _data[i] = p;
3.267 + _iim.set(p.first, i);
3.268 }
3.269
3.270 public:
3.271 /// \brief Insert a pair of item and priority into the heap.
3.272 ///
3.273 - /// Adds \c p.first to the heap with priority \c p.second.
3.274 + /// This function inserts \c p.first to the heap with priority
3.275 + /// \c p.second.
3.276 /// \param p The pair to insert.
3.277 + /// \pre \c p.first must not be stored in the heap.
3.278 void push(const Pair &p) {
3.279 - int n = data.size();
3.280 - data.resize(n+1);
3.281 - bubble_up(n, p);
3.282 + int n = _data.size();
3.283 + _data.resize(n+1);
3.284 + bubbleUp(n, p);
3.285 }
3.286
3.287 - /// \brief Insert an item into the heap with the given heap.
3.288 + /// \brief Insert an item into the heap with the given priority.
3.289 ///
3.290 - /// Adds \c i to the heap with priority \c p.
3.291 + /// This function inserts the given item into the heap with the
3.292 + /// given priority.
3.293 /// \param i The item to insert.
3.294 /// \param p The priority of the item.
3.295 + /// \pre \e i must not be stored in the heap.
3.296 void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
3.297
3.298 - /// \brief Returns the item with minimum priority relative to \c Compare.
3.299 + /// \brief Return the item having minimum priority.
3.300 ///
3.301 - /// This method returns the item with minimum priority relative to \c
3.302 - /// Compare.
3.303 - /// \pre The heap must be nonempty.
3.304 - Item top() const { return data[0].first; }
3.305 + /// This function returns the item having minimum priority.
3.306 + /// \pre The heap must be non-empty.
3.307 + Item top() const { return _data[0].first; }
3.308
3.309 - /// \brief Returns the minimum priority relative to \c Compare.
3.310 + /// \brief The minimum priority.
3.311 ///
3.312 - /// It returns the minimum priority relative to \c Compare.
3.313 - /// \pre The heap must be nonempty.
3.314 - Prio prio() const { return data[0].second; }
3.315 + /// This function returns the minimum priority.
3.316 + /// \pre The heap must be non-empty.
3.317 + Prio prio() const { return _data[0].second; }
3.318
3.319 - /// \brief Deletes the item with minimum priority relative to \c Compare.
3.320 + /// \brief Remove the item having minimum priority.
3.321 ///
3.322 - /// This method deletes the item with minimum priority relative to \c
3.323 - /// Compare from the heap.
3.324 + /// This function removes the item having minimum priority.
3.325 /// \pre The heap must be non-empty.
3.326 void pop() {
3.327 - int n = data.size()-1;
3.328 - iim.set(data[0].first, POST_HEAP);
3.329 - if (n>0) bubble_down(0, data[n], n);
3.330 - data.pop_back();
3.331 + int n = _data.size()-1;
3.332 + _iim.set(_data[0].first, POST_HEAP);
3.333 + if (n>0) bubbleDown(0, _data[n], n);
3.334 + _data.pop_back();
3.335 }
3.336
3.337 - /// \brief Deletes \c i from the heap.
3.338 + /// \brief Remove the given item from the heap.
3.339 ///
3.340 - /// This method deletes item \c i from the heap.
3.341 - /// \param i The item to erase.
3.342 - /// \pre The item should be in the heap.
3.343 + /// This function removes the given item from the heap if it is
3.344 + /// already stored.
3.345 + /// \param i The item to delete.
3.346 + /// \pre \e i must be in the heap.
3.347 void erase(const Item &i) {
3.348 - int h = iim[i];
3.349 - int n = data.size()-1;
3.350 - iim.set(data[h].first, POST_HEAP);
3.351 + int h = _iim[i];
3.352 + int n = _data.size()-1;
3.353 + _iim.set(_data[h].first, POST_HEAP);
3.354 if( h<n ) {
3.355 - if( less(data[parent(h)], data[n]) )
3.356 - bubble_down(h, data[n], n);
3.357 + if( less(_data[parent(h)], _data[n]) )
3.358 + bubbleDown(h, _data[n], n);
3.359 else
3.360 - bubble_up(h, data[n]);
3.361 + bubbleUp(h, _data[n]);
3.362 }
3.363 - data.pop_back();
3.364 + _data.pop_back();
3.365 }
3.366
3.367 -
3.368 - /// \brief Returns the priority of \c i.
3.369 + /// \brief The priority of the given item.
3.370 ///
3.371 - /// This function returns the priority of item \c i.
3.372 - /// \pre \c i must be in the heap.
3.373 + /// This function returns the priority of the given item.
3.374 /// \param i The item.
3.375 + /// \pre \e i must be in the heap.
3.376 Prio operator[](const Item &i) const {
3.377 - int idx = iim[i];
3.378 - return data[idx].second;
3.379 + int idx = _iim[i];
3.380 + return _data[idx].second;
3.381 }
3.382
3.383 - /// \brief \c i gets to the heap with priority \c p independently
3.384 - /// if \c i was already there.
3.385 + /// \brief Set the priority of an item or insert it, if it is
3.386 + /// not stored in the heap.
3.387 ///
3.388 - /// This method calls \ref push(\c i, \c p) if \c i is not stored
3.389 - /// in the heap and sets the priority of \c i to \c p otherwise.
3.390 + /// This method sets the priority of the given item if it is
3.391 + /// already stored in the heap. Otherwise it inserts the given
3.392 + /// item into the heap with the given priority.
3.393 /// \param i The item.
3.394 /// \param p The priority.
3.395 void set(const Item &i, const Prio &p) {
3.396 - int idx = iim[i];
3.397 + int idx = _iim[i];
3.398 if( idx<0 )
3.399 push(i,p);
3.400 - else if( comp(p, data[idx].second) )
3.401 - bubble_up(idx, Pair(i,p));
3.402 + else if( _comp(p, _data[idx].second) )
3.403 + bubbleUp(idx, Pair(i,p));
3.404 else
3.405 - bubble_down(idx, Pair(i,p), data.size());
3.406 + bubbleDown(idx, Pair(i,p), _data.size());
3.407 }
3.408
3.409 - /// \brief Decreases the priority of \c i to \c p.
3.410 + /// \brief Decrease the priority of an item to the given value.
3.411 ///
3.412 - /// This method decreases the priority of item \c i to \c p.
3.413 - /// \pre \c i must be stored in the heap with priority at least \c
3.414 - /// p relative to \c Compare.
3.415 + /// This function decreases the priority of an item to the given value.
3.416 /// \param i The item.
3.417 /// \param p The priority.
3.418 + /// \pre \e i must be stored in the heap with priority at least \e p.
3.419 void decrease(const Item &i, const Prio &p) {
3.420 - int idx = iim[i];
3.421 - bubble_up(idx, Pair(i,p));
3.422 + int idx = _iim[i];
3.423 + bubbleUp(idx, Pair(i,p));
3.424 }
3.425
3.426 - /// \brief Increases the priority of \c i to \c p.
3.427 + /// \brief Increase the priority of an item to the given value.
3.428 ///
3.429 - /// This method sets the priority of item \c i to \c p.
3.430 - /// \pre \c i must be stored in the heap with priority at most \c
3.431 - /// p relative to \c Compare.
3.432 + /// This function increases the priority of an item to the given value.
3.433 /// \param i The item.
3.434 /// \param p The priority.
3.435 + /// \pre \e i must be stored in the heap with priority at most \e p.
3.436 void increase(const Item &i, const Prio &p) {
3.437 - int idx = iim[i];
3.438 - bubble_down(idx, Pair(i,p), data.size());
3.439 + int idx = _iim[i];
3.440 + bubbleDown(idx, Pair(i,p), _data.size());
3.441 }
3.442
3.443 - /// \brief Returns if \c item is in, has already been in, or has
3.444 - /// never been in the heap.
3.445 + /// \brief Return the state of an item.
3.446 ///
3.447 - /// This method returns PRE_HEAP if \c item has never been in the
3.448 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
3.449 - /// otherwise. In the latter case it is possible that \c item will
3.450 - /// get back to the heap again.
3.451 + /// This method returns \c PRE_HEAP if the given item has never
3.452 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
3.453 + /// and \c POST_HEAP otherwise.
3.454 + /// In the latter case it is possible that the item will get back
3.455 + /// to the heap again.
3.456 /// \param i The item.
3.457 State state(const Item &i) const {
3.458 - int s = iim[i];
3.459 + int s = _iim[i];
3.460 if (s>=0) s=0;
3.461 return State(s);
3.462 }
3.463
3.464 - /// \brief Sets the state of the \c item in the heap.
3.465 + /// \brief Set the state of an item in the heap.
3.466 ///
3.467 - /// Sets the state of the \c item in the heap. It can be used to
3.468 - /// manually clear the heap when it is important to achive the
3.469 - /// better time complexity.
3.470 + /// This function sets the state of the given item in the heap.
3.471 + /// It can be used to manually clear the heap when it is important
3.472 + /// to achive better time complexity.
3.473 /// \param i The item.
3.474 /// \param st The state. It should not be \c IN_HEAP.
3.475 void state(const Item& i, State st) {
3.476 switch (st) {
3.477 - case POST_HEAP:
3.478 - case PRE_HEAP:
3.479 - if (state(i) == IN_HEAP) erase(i);
3.480 - iim[i] = st;
3.481 - break;
3.482 - case IN_HEAP:
3.483 - break;
3.484 + case POST_HEAP:
3.485 + case PRE_HEAP:
3.486 + if (state(i) == IN_HEAP) erase(i);
3.487 + _iim[i] = st;
3.488 + break;
3.489 + case IN_HEAP:
3.490 + break;
3.491 }
3.492 }
3.493
3.494 - /// \brief Replaces an item in the heap.
3.495 + /// \brief Replace an item in the heap.
3.496 ///
3.497 - /// The \c i item is replaced with \c j item. The \c i item should
3.498 - /// be in the heap, while the \c j should be out of the heap. The
3.499 - /// \c i item will out of the heap and \c j will be in the heap
3.500 - /// with the same prioriority as prevoiusly the \c i item.
3.501 + /// This function replaces item \c i with item \c j.
3.502 + /// Item \c i must be in the heap, while \c j must be out of the heap.
3.503 + /// After calling this method, item \c i will be out of the
3.504 + /// heap and \c j will be in the heap with the same prioriority
3.505 + /// as item \c i had before.
3.506 void replace(const Item& i, const Item& j) {
3.507 - int idx=iim[i];
3.508 - iim.set(i, iim[j]);
3.509 - iim.set(j, idx);
3.510 - data[idx].first=j;
3.511 + int idx=_iim[i];
3.512 + _iim.set(i, _iim[j]);
3.513 + _iim.set(j, idx);
3.514 + _data[idx].first=j;
3.515 }
3.516
3.517 }; // class KaryHeap
4.1 --- a/lemon/pairing_heap.h Thu Jul 09 02:39:47 2009 +0200
4.2 +++ b/lemon/pairing_heap.h Thu Jul 09 04:07:08 2009 +0200
4.3 @@ -1,8 +1,8 @@
4.4 -/* -*- C++ -*-
4.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
4.6 *
4.7 - * This file is a part of LEMON, a generic C++ optimization library
4.8 + * This file is a part of LEMON, a generic C++ optimization library.
4.9 *
4.10 - * Copyright (C) 2003-2008
4.11 + * Copyright (C) 2003-2009
4.12 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.13 * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.14 *
4.15 @@ -20,217 +20,223 @@
4.16 #define LEMON_PAIRING_HEAP_H
4.17
4.18 ///\file
4.19 -///\ingroup auxdat
4.20 -///\brief Pairing Heap implementation.
4.21 +///\ingroup heaps
4.22 +///\brief Pairing heap implementation.
4.23
4.24 #include <vector>
4.25 +#include <utility>
4.26 #include <functional>
4.27 #include <lemon/math.h>
4.28
4.29 namespace lemon {
4.30
4.31 - /// \ingroup auxdat
4.32 + /// \ingroup heaps
4.33 ///
4.34 ///\brief Pairing Heap.
4.35 ///
4.36 - ///This class implements the \e Pairing \e heap data structure. A \e heap
4.37 - ///is a data structure for storing items with specified values called \e
4.38 - ///priorities in such a way that finding the item with minimum priority is
4.39 - ///efficient. \c Compare specifies the ordering of the priorities. In a heap
4.40 - ///one can change the priority of an item, add or erase an item, etc.
4.41 + /// This class implements the \e pairing \e heap data structure.
4.42 + /// It fully conforms to the \ref concepts::Heap "heap concept".
4.43 ///
4.44 - ///The methods \ref increase and \ref erase are not efficient in a Pairing
4.45 - ///heap. In case of many calls to these operations, it is better to use a
4.46 - ///\ref BinHeap "binary heap".
4.47 + /// The methods \ref increase() and \ref erase() are not efficient
4.48 + /// in a pairing heap. In case of many calls of these operations,
4.49 + /// it is better to use other heap structure, e.g. \ref BinHeap
4.50 + /// "binary heap".
4.51 ///
4.52 - ///\param _Prio Type of the priority of the items.
4.53 - ///\param _ItemIntMap A read and writable Item int map, used internally
4.54 - ///to handle the cross references.
4.55 - ///\param _Compare A class for the ordering of the priorities. The
4.56 - ///default is \c std::less<_Prio>.
4.57 - ///
4.58 - ///\sa BinHeap
4.59 - ///\sa Dijkstra
4.60 - ///\author Dorian Batha
4.61 -
4.62 + /// \tparam PR Type of the priorities of the items.
4.63 + /// \tparam IM A read-writable item map with \c int values, used
4.64 + /// internally to handle the cross references.
4.65 + /// \tparam CMP A functor class for comparing the priorities.
4.66 + /// The default is \c std::less<PR>.
4.67 #ifdef DOXYGEN
4.68 - template <typename _Prio,
4.69 - typename _ItemIntMap,
4.70 - typename _Compare>
4.71 + template <typename PR, typename IM, typename CMP>
4.72 #else
4.73 - template <typename _Prio,
4.74 - typename _ItemIntMap,
4.75 - typename _Compare = std::less<_Prio> >
4.76 + template <typename PR, typename IM, typename CMP = std::less<PR> >
4.77 #endif
4.78 class PairingHeap {
4.79 public:
4.80 - typedef _ItemIntMap ItemIntMap;
4.81 - typedef _Prio Prio;
4.82 + /// Type of the item-int map.
4.83 + typedef IM ItemIntMap;
4.84 + /// Type of the priorities.
4.85 + typedef PR Prio;
4.86 + /// Type of the items stored in the heap.
4.87 typedef typename ItemIntMap::Key Item;
4.88 - typedef std::pair<Item,Prio> Pair;
4.89 - typedef _Compare Compare;
4.90 + /// Functor type for comparing the priorities.
4.91 + typedef CMP Compare;
4.92 +
4.93 + /// \brief Type to represent the states of the items.
4.94 + ///
4.95 + /// Each item has a state associated to it. It can be "in heap",
4.96 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
4.97 + /// heap's point of view, but may be useful to the user.
4.98 + ///
4.99 + /// The item-int map must be initialized in such way that it assigns
4.100 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
4.101 + enum State {
4.102 + IN_HEAP = 0, ///< = 0.
4.103 + PRE_HEAP = -1, ///< = -1.
4.104 + POST_HEAP = -2 ///< = -2.
4.105 + };
4.106
4.107 private:
4.108 class store;
4.109
4.110 - std::vector<store> container;
4.111 - int minimum;
4.112 - ItemIntMap &iimap;
4.113 - Compare comp;
4.114 - int num_items;
4.115 + std::vector<store> _data;
4.116 + int _min;
4.117 + ItemIntMap &_iim;
4.118 + Compare _comp;
4.119 + int _num_items;
4.120
4.121 public:
4.122 - ///Status of the nodes
4.123 - enum State {
4.124 - ///The node is in the heap
4.125 - IN_HEAP = 0,
4.126 - ///The node has never been in the heap
4.127 - PRE_HEAP = -1,
4.128 - ///The node was in the heap but it got out of it
4.129 - POST_HEAP = -2
4.130 - };
4.131 + /// \brief Constructor.
4.132 + ///
4.133 + /// Constructor.
4.134 + /// \param map A map that assigns \c int values to the items.
4.135 + /// It is used internally to handle the cross references.
4.136 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
4.137 + explicit PairingHeap(ItemIntMap &map)
4.138 + : _min(0), _iim(map), _num_items(0) {}
4.139
4.140 - /// \brief The constructor
4.141 + /// \brief Constructor.
4.142 ///
4.143 - /// \c _iimap should be given to the constructor, since it is
4.144 - /// used internally to handle the cross references.
4.145 - explicit PairingHeap(ItemIntMap &_iimap)
4.146 - : minimum(0), iimap(_iimap), num_items(0) {}
4.147 -
4.148 - /// \brief The constructor
4.149 - ///
4.150 - /// \c _iimap should be given to the constructor, since it is used
4.151 - /// internally to handle the cross references. \c _comp is an
4.152 - /// object for ordering of the priorities.
4.153 - PairingHeap(ItemIntMap &_iimap, const Compare &_comp)
4.154 - : minimum(0), iimap(_iimap), comp(_comp), num_items(0) {}
4.155 + /// Constructor.
4.156 + /// \param map A map that assigns \c int values to the items.
4.157 + /// It is used internally to handle the cross references.
4.158 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
4.159 + /// \param comp The function object used for comparing the priorities.
4.160 + PairingHeap(ItemIntMap &map, const Compare &comp)
4.161 + : _min(0), _iim(map), _comp(comp), _num_items(0) {}
4.162
4.163 /// \brief The number of items stored in the heap.
4.164 ///
4.165 - /// Returns the number of items stored in the heap.
4.166 - int size() const { return num_items; }
4.167 + /// This function returns the number of items stored in the heap.
4.168 + int size() const { return _num_items; }
4.169
4.170 - /// \brief Checks if the heap stores no items.
4.171 + /// \brief Check if the heap is empty.
4.172 ///
4.173 - /// Returns \c true if and only if the heap stores no items.
4.174 - bool empty() const { return num_items==0; }
4.175 + /// This function returns \c true if the heap is empty.
4.176 + bool empty() const { return _num_items==0; }
4.177
4.178 - /// \brief Make empty this heap.
4.179 + /// \brief Make the heap empty.
4.180 ///
4.181 - /// Make empty this heap. It does not change the cross reference
4.182 - /// map. If you want to reuse a heap what is not surely empty you
4.183 - /// should first clear the heap and after that you should set the
4.184 - /// cross reference map for each item to \c PRE_HEAP.
4.185 + /// This functon makes the heap empty.
4.186 + /// It does not change the cross reference map. If you want to reuse
4.187 + /// a heap that is not surely empty, you should first clear it and
4.188 + /// then you should set the cross reference map to \c PRE_HEAP
4.189 + /// for each item.
4.190 void clear() {
4.191 - container.clear();
4.192 - minimum = 0;
4.193 - num_items = 0;
4.194 + _data.clear();
4.195 + _min = 0;
4.196 + _num_items = 0;
4.197 }
4.198
4.199 - /// \brief \c item gets to the heap with priority \c value independently
4.200 - /// if \c item was already there.
4.201 + /// \brief Set the priority of an item or insert it, if it is
4.202 + /// not stored in the heap.
4.203 ///
4.204 - /// This method calls \ref push(\c item, \c value) if \c item is not
4.205 - /// stored in the heap and it calls \ref decrease(\c item, \c value) or
4.206 - /// \ref increase(\c item, \c value) otherwise.
4.207 + /// This method sets the priority of the given item if it is
4.208 + /// already stored in the heap. Otherwise it inserts the given
4.209 + /// item into the heap with the given priority.
4.210 + /// \param item The item.
4.211 + /// \param value The priority.
4.212 void set (const Item& item, const Prio& value) {
4.213 - int i=iimap[item];
4.214 - if ( i>=0 && container[i].in ) {
4.215 - if ( comp(value, container[i].prio) ) decrease(item, value);
4.216 - if ( comp(container[i].prio, value) ) increase(item, value);
4.217 + int i=_iim[item];
4.218 + if ( i>=0 && _data[i].in ) {
4.219 + if ( _comp(value, _data[i].prio) ) decrease(item, value);
4.220 + if ( _comp(_data[i].prio, value) ) increase(item, value);
4.221 } else push(item, value);
4.222 }
4.223
4.224 - /// \brief Adds \c item to the heap with priority \c value.
4.225 + /// \brief Insert an item into the heap with the given priority.
4.226 ///
4.227 - /// Adds \c item to the heap with priority \c value.
4.228 - /// \pre \c item must not be stored in the heap.
4.229 + /// This function inserts the given item into the heap with the
4.230 + /// given priority.
4.231 + /// \param item The item to insert.
4.232 + /// \param value The priority of the item.
4.233 + /// \pre \e item must not be stored in the heap.
4.234 void push (const Item& item, const Prio& value) {
4.235 - int i=iimap[item];
4.236 + int i=_iim[item];
4.237 if( i<0 ) {
4.238 - int s=container.size();
4.239 - iimap.set(item, s);
4.240 + int s=_data.size();
4.241 + _iim.set(item, s);
4.242 store st;
4.243 st.name=item;
4.244 - container.push_back(st);
4.245 + _data.push_back(st);
4.246 i=s;
4.247 } else {
4.248 - container[i].parent=container[i].child=-1;
4.249 - container[i].left_child=false;
4.250 - container[i].degree=0;
4.251 - container[i].in=true;
4.252 + _data[i].parent=_data[i].child=-1;
4.253 + _data[i].left_child=false;
4.254 + _data[i].degree=0;
4.255 + _data[i].in=true;
4.256 }
4.257
4.258 - container[i].prio=value;
4.259 + _data[i].prio=value;
4.260
4.261 - if ( num_items!=0 ) {
4.262 - if ( comp( value, container[minimum].prio) ) {
4.263 - fuse(i,minimum);
4.264 - minimum=i;
4.265 + if ( _num_items!=0 ) {
4.266 + if ( _comp( value, _data[_min].prio) ) {
4.267 + fuse(i,_min);
4.268 + _min=i;
4.269 }
4.270 - else fuse(minimum,i);
4.271 + else fuse(_min,i);
4.272 }
4.273 - else minimum=i;
4.274 + else _min=i;
4.275
4.276 - ++num_items;
4.277 + ++_num_items;
4.278 }
4.279
4.280 - /// \brief Returns the item with minimum priority relative to \c Compare.
4.281 + /// \brief Return the item having minimum priority.
4.282 ///
4.283 - /// This method returns the item with minimum priority relative to \c
4.284 - /// Compare.
4.285 - /// \pre The heap must be nonempty.
4.286 - Item top() const { return container[minimum].name; }
4.287 + /// This function returns the item having minimum priority.
4.288 + /// \pre The heap must be non-empty.
4.289 + Item top() const { return _data[_min].name; }
4.290
4.291 - /// \brief Returns the minimum priority relative to \c Compare.
4.292 + /// \brief The minimum priority.
4.293 ///
4.294 - /// It returns the minimum priority relative to \c Compare.
4.295 - /// \pre The heap must be nonempty.
4.296 - const Prio& prio() const { return container[minimum].prio; }
4.297 + /// This function returns the minimum priority.
4.298 + /// \pre The heap must be non-empty.
4.299 + const Prio& prio() const { return _data[_min].prio; }
4.300
4.301 - /// \brief Returns the priority of \c item.
4.302 + /// \brief The priority of the given item.
4.303 ///
4.304 - /// It returns the priority of \c item.
4.305 - /// \pre \c item must be in the heap.
4.306 + /// This function returns the priority of the given item.
4.307 + /// \param item The item.
4.308 + /// \pre \e item must be in the heap.
4.309 const Prio& operator[](const Item& item) const {
4.310 - return container[iimap[item]].prio;
4.311 + return _data[_iim[item]].prio;
4.312 }
4.313
4.314 - /// \brief Deletes the item with minimum priority relative to \c Compare.
4.315 + /// \brief Remove the item having minimum priority.
4.316 ///
4.317 - /// This method deletes the item with minimum priority relative to \c
4.318 - /// Compare from the heap.
4.319 + /// This function removes the item having minimum priority.
4.320 /// \pre The heap must be non-empty.
4.321 void pop() {
4.322 - int TreeArray[num_items];
4.323 + int TreeArray[_num_items];
4.324 int i=0, num_child=0, child_right = 0;
4.325 - container[minimum].in=false;
4.326 + _data[_min].in=false;
4.327
4.328 - if( -1!=container[minimum].child ) {
4.329 - i=container[minimum].child;
4.330 + if( -1!=_data[_min].child ) {
4.331 + i=_data[_min].child;
4.332 TreeArray[num_child] = i;
4.333 - container[i].parent = -1;
4.334 - container[minimum].child = -1;
4.335 + _data[i].parent = -1;
4.336 + _data[_min].child = -1;
4.337
4.338 ++num_child;
4.339 int ch=-1;
4.340 - while( container[i].child!=-1 ) {
4.341 - ch=container[i].child;
4.342 - if( container[ch].left_child && i==container[ch].parent ) {
4.343 + while( _data[i].child!=-1 ) {
4.344 + ch=_data[i].child;
4.345 + if( _data[ch].left_child && i==_data[ch].parent ) {
4.346 i=ch;
4.347 //break;
4.348 } else {
4.349 - if( container[ch].left_child ) {
4.350 - child_right=container[ch].parent;
4.351 - container[ch].parent = i;
4.352 - --container[i].degree;
4.353 + if( _data[ch].left_child ) {
4.354 + child_right=_data[ch].parent;
4.355 + _data[ch].parent = i;
4.356 + --_data[i].degree;
4.357 }
4.358 else {
4.359 child_right=ch;
4.360 - container[i].child=-1;
4.361 - container[i].degree=0;
4.362 + _data[i].child=-1;
4.363 + _data[i].degree=0;
4.364 }
4.365 - container[child_right].parent = -1;
4.366 + _data[child_right].parent = -1;
4.367 TreeArray[num_child] = child_right;
4.368 i = child_right;
4.369 ++num_child;
4.370 @@ -239,8 +245,8 @@
4.371
4.372 int other;
4.373 for( i=0; i<num_child-1; i+=2 ) {
4.374 - if ( !comp(container[TreeArray[i]].prio,
4.375 - container[TreeArray[i+1]].prio) ) {
4.376 + if ( !_comp(_data[TreeArray[i]].prio,
4.377 + _data[TreeArray[i+1]].prio) ) {
4.378 other=TreeArray[i];
4.379 TreeArray[i]=TreeArray[i+1];
4.380 TreeArray[i+1]=other;
4.381 @@ -250,8 +256,8 @@
4.382
4.383 i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
4.384 while(i>=2) {
4.385 - if ( comp(container[TreeArray[i]].prio,
4.386 - container[TreeArray[i-2]].prio) ) {
4.387 + if ( _comp(_data[TreeArray[i]].prio,
4.388 + _data[TreeArray[i-2]].prio) ) {
4.389 other=TreeArray[i];
4.390 TreeArray[i]=TreeArray[i-2];
4.391 TreeArray[i-2]=other;
4.392 @@ -259,88 +265,91 @@
4.393 fuse( TreeArray[i-2], TreeArray[i] );
4.394 i-=2;
4.395 }
4.396 - minimum = TreeArray[0];
4.397 + _min = TreeArray[0];
4.398 }
4.399
4.400 if ( 0==num_child ) {
4.401 - minimum = container[minimum].child;
4.402 + _min = _data[_min].child;
4.403 }
4.404
4.405 - if (minimum >= 0) container[minimum].left_child = false;
4.406 + if (_min >= 0) _data[_min].left_child = false;
4.407
4.408 - --num_items;
4.409 + --_num_items;
4.410 }
4.411
4.412 - /// \brief Deletes \c item from the heap.
4.413 + /// \brief Remove the given item from the heap.
4.414 ///
4.415 - /// This method deletes \c item from the heap, if \c item was already
4.416 - /// stored in the heap. It is quite inefficient in Pairing heaps.
4.417 + /// This function removes the given item from the heap if it is
4.418 + /// already stored.
4.419 + /// \param item The item to delete.
4.420 + /// \pre \e item must be in the heap.
4.421 void erase (const Item& item) {
4.422 - int i=iimap[item];
4.423 - if ( i>=0 && container[i].in ) {
4.424 - decrease( item, container[minimum].prio-1 );
4.425 + int i=_iim[item];
4.426 + if ( i>=0 && _data[i].in ) {
4.427 + decrease( item, _data[_min].prio-1 );
4.428 pop();
4.429 }
4.430 }
4.431
4.432 - /// \brief Decreases the priority of \c item to \c value.
4.433 + /// \brief Decrease the priority of an item to the given value.
4.434 ///
4.435 - /// This method decreases the priority of \c item to \c value.
4.436 - /// \pre \c item must be stored in the heap with priority at least \c
4.437 - /// value relative to \c Compare.
4.438 + /// This function decreases the priority of an item to the given value.
4.439 + /// \param item The item.
4.440 + /// \param value The priority.
4.441 + /// \pre \e item must be stored in the heap with priority at least \e value.
4.442 void decrease (Item item, const Prio& value) {
4.443 - int i=iimap[item];
4.444 - container[i].prio=value;
4.445 - int p=container[i].parent;
4.446 + int i=_iim[item];
4.447 + _data[i].prio=value;
4.448 + int p=_data[i].parent;
4.449
4.450 - if( container[i].left_child && i!=container[p].child ) {
4.451 - p=container[p].parent;
4.452 + if( _data[i].left_child && i!=_data[p].child ) {
4.453 + p=_data[p].parent;
4.454 }
4.455
4.456 - if ( p!=-1 && comp(value,container[p].prio) ) {
4.457 + if ( p!=-1 && _comp(value,_data[p].prio) ) {
4.458 cut(i,p);
4.459 - if ( comp(container[minimum].prio,value) ) {
4.460 - fuse(minimum,i);
4.461 + if ( _comp(_data[_min].prio,value) ) {
4.462 + fuse(_min,i);
4.463 } else {
4.464 - fuse(i,minimum);
4.465 - minimum=i;
4.466 + fuse(i,_min);
4.467 + _min=i;
4.468 }
4.469 }
4.470 }
4.471
4.472 - /// \brief Increases the priority of \c item to \c value.
4.473 + /// \brief Increase the priority of an item to the given value.
4.474 ///
4.475 - /// This method sets the priority of \c item to \c value. Though
4.476 - /// there is no precondition on the priority of \c item, this
4.477 - /// method should be used only if it is indeed necessary to increase
4.478 - /// (relative to \c Compare) the priority of \c item, because this
4.479 - /// method is inefficient.
4.480 + /// This function increases the priority of an item to the given value.
4.481 + /// \param item The item.
4.482 + /// \param value The priority.
4.483 + /// \pre \e item must be stored in the heap with priority at most \e value.
4.484 void increase (Item item, const Prio& value) {
4.485 erase(item);
4.486 push(item,value);
4.487 }
4.488
4.489 - /// \brief Returns if \c item is in, has already been in, or has never
4.490 - /// been in the heap.
4.491 + /// \brief Return the state of an item.
4.492 ///
4.493 - /// This method returns PRE_HEAP if \c item has never been in the
4.494 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
4.495 - /// otherwise. In the latter case it is possible that \c item will
4.496 - /// get back to the heap again.
4.497 + /// This method returns \c PRE_HEAP if the given item has never
4.498 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
4.499 + /// and \c POST_HEAP otherwise.
4.500 + /// In the latter case it is possible that the item will get back
4.501 + /// to the heap again.
4.502 + /// \param item The item.
4.503 State state(const Item &item) const {
4.504 - int i=iimap[item];
4.505 + int i=_iim[item];
4.506 if( i>=0 ) {
4.507 - if( container[i].in ) i=0;
4.508 + if( _data[i].in ) i=0;
4.509 else i=-2;
4.510 }
4.511 return State(i);
4.512 }
4.513
4.514 - /// \brief Sets the state of the \c item in the heap.
4.515 + /// \brief Set the state of an item in the heap.
4.516 ///
4.517 - /// Sets the state of the \c item in the heap. It can be used to
4.518 - /// manually clear the heap when it is important to achive the
4.519 - /// better time complexity.
4.520 + /// This function sets the state of the given item in the heap.
4.521 + /// It can be used to manually clear the heap when it is important
4.522 + /// to achive better time complexity.
4.523 /// \param i The item.
4.524 /// \param st The state. It should not be \c IN_HEAP.
4.525 void state(const Item& i, State st) {
4.526 @@ -348,7 +357,7 @@
4.527 case POST_HEAP:
4.528 case PRE_HEAP:
4.529 if (state(i) == IN_HEAP) erase(i);
4.530 - iimap[i]=st;
4.531 + _iim[i]=st;
4.532 break;
4.533 case IN_HEAP:
4.534 break;
4.535 @@ -359,95 +368,95 @@
4.536
4.537 void cut(int a, int b) {
4.538 int child_a;
4.539 - switch (container[a].degree) {
4.540 + switch (_data[a].degree) {
4.541 case 2:
4.542 - child_a = container[container[a].child].parent;
4.543 - if( container[a].left_child ) {
4.544 - container[child_a].left_child=true;
4.545 - container[b].child=child_a;
4.546 - container[child_a].parent=container[a].parent;
4.547 + child_a = _data[_data[a].child].parent;
4.548 + if( _data[a].left_child ) {
4.549 + _data[child_a].left_child=true;
4.550 + _data[b].child=child_a;
4.551 + _data[child_a].parent=_data[a].parent;
4.552 }
4.553 else {
4.554 - container[child_a].left_child=false;
4.555 - container[child_a].parent=b;
4.556 - if( a!=container[b].child )
4.557 - container[container[b].child].parent=child_a;
4.558 + _data[child_a].left_child=false;
4.559 + _data[child_a].parent=b;
4.560 + if( a!=_data[b].child )
4.561 + _data[_data[b].child].parent=child_a;
4.562 else
4.563 - container[b].child=child_a;
4.564 + _data[b].child=child_a;
4.565 }
4.566 - --container[a].degree;
4.567 - container[container[a].child].parent=a;
4.568 + --_data[a].degree;
4.569 + _data[_data[a].child].parent=a;
4.570 break;
4.571
4.572 case 1:
4.573 - child_a = container[a].child;
4.574 - if( !container[child_a].left_child ) {
4.575 - --container[a].degree;
4.576 - if( container[a].left_child ) {
4.577 - container[child_a].left_child=true;
4.578 - container[child_a].parent=container[a].parent;
4.579 - container[b].child=child_a;
4.580 + child_a = _data[a].child;
4.581 + if( !_data[child_a].left_child ) {
4.582 + --_data[a].degree;
4.583 + if( _data[a].left_child ) {
4.584 + _data[child_a].left_child=true;
4.585 + _data[child_a].parent=_data[a].parent;
4.586 + _data[b].child=child_a;
4.587 }
4.588 else {
4.589 - container[child_a].left_child=false;
4.590 - container[child_a].parent=b;
4.591 - if( a!=container[b].child )
4.592 - container[container[b].child].parent=child_a;
4.593 + _data[child_a].left_child=false;
4.594 + _data[child_a].parent=b;
4.595 + if( a!=_data[b].child )
4.596 + _data[_data[b].child].parent=child_a;
4.597 else
4.598 - container[b].child=child_a;
4.599 + _data[b].child=child_a;
4.600 }
4.601 - container[a].child=-1;
4.602 + _data[a].child=-1;
4.603 }
4.604 else {
4.605 - --container[b].degree;
4.606 - if( container[a].left_child ) {
4.607 - container[b].child =
4.608 - (1==container[b].degree) ? container[a].parent : -1;
4.609 + --_data[b].degree;
4.610 + if( _data[a].left_child ) {
4.611 + _data[b].child =
4.612 + (1==_data[b].degree) ? _data[a].parent : -1;
4.613 } else {
4.614 - if (1==container[b].degree)
4.615 - container[container[b].child].parent=b;
4.616 + if (1==_data[b].degree)
4.617 + _data[_data[b].child].parent=b;
4.618 else
4.619 - container[b].child=-1;
4.620 + _data[b].child=-1;
4.621 }
4.622 }
4.623 break;
4.624
4.625 case 0:
4.626 - --container[b].degree;
4.627 - if( container[a].left_child ) {
4.628 - container[b].child =
4.629 - (0!=container[b].degree) ? container[a].parent : -1;
4.630 + --_data[b].degree;
4.631 + if( _data[a].left_child ) {
4.632 + _data[b].child =
4.633 + (0!=_data[b].degree) ? _data[a].parent : -1;
4.634 } else {
4.635 - if( 0!=container[b].degree )
4.636 - container[container[b].child].parent=b;
4.637 + if( 0!=_data[b].degree )
4.638 + _data[_data[b].child].parent=b;
4.639 else
4.640 - container[b].child=-1;
4.641 + _data[b].child=-1;
4.642 }
4.643 break;
4.644 }
4.645 - container[a].parent=-1;
4.646 - container[a].left_child=false;
4.647 + _data[a].parent=-1;
4.648 + _data[a].left_child=false;
4.649 }
4.650
4.651 void fuse(int a, int b) {
4.652 - int child_a = container[a].child;
4.653 - int child_b = container[b].child;
4.654 - container[a].child=b;
4.655 - container[b].parent=a;
4.656 - container[b].left_child=true;
4.657 + int child_a = _data[a].child;
4.658 + int child_b = _data[b].child;
4.659 + _data[a].child=b;
4.660 + _data[b].parent=a;
4.661 + _data[b].left_child=true;
4.662
4.663 if( -1!=child_a ) {
4.664 - container[b].child=child_a;
4.665 - container[child_a].parent=b;
4.666 - container[child_a].left_child=false;
4.667 - ++container[b].degree;
4.668 + _data[b].child=child_a;
4.669 + _data[child_a].parent=b;
4.670 + _data[child_a].left_child=false;
4.671 + ++_data[b].degree;
4.672
4.673 if( -1!=child_b ) {
4.674 - container[b].child=child_b;
4.675 - container[child_b].parent=child_a;
4.676 + _data[b].child=child_b;
4.677 + _data[child_b].parent=child_a;
4.678 }
4.679 }
4.680 - else { ++container[a].degree; }
4.681 + else { ++_data[a].degree; }
4.682 }
4.683
4.684 class store {