COIN-OR::LEMON - Graph Library

Changeset 750:bb3392fe91f2 in lemon


Ignore:
Timestamp:
07/09/09 04:07:08 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improve and unify the doc + names in the new heaps (#301)

Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/binom_heap.h

    r748 r750  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2121
    2222///\file
    23 ///\ingroup auxdat
     23///\ingroup heaps
    2424///\brief Binomial Heap implementation.
    2525
    2626#include <vector>
     27#include <utility>
    2728#include <functional>
    2829#include <lemon/math.h>
     
    3132namespace lemon {
    3233
    33   /// \ingroup auxdat
     34  /// \ingroup heaps
    3435  ///
    35   ///\brief Binomial Heap.
     36  ///\brief Binomial heap data structure.
    3637  ///
    37   ///This class implements the \e Binomial \e heap data structure. A \e heap
    38   ///is a data structure for storing items with specified values called \e
    39   ///priorities in such a way that finding the item with minimum priority is
    40   ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    41   ///one can change the priority of an item, add or erase an item, etc.
     38  /// This class implements the \e binomial \e heap data structure.
     39  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4240  ///
    43   ///The methods \ref increase and \ref erase are not efficient in a Binomial
    44   ///heap. In case of many calls to these operations, it is better to use a
    45   ///\ref BinHeap "binary heap".
     41  /// The methods \ref increase() and \ref erase() are not efficient
     42  /// in a binomial heap. In case of many calls of these operations,
     43  /// it is better to use other heap structure, e.g. \ref BinHeap
     44  /// "binary heap".
    4645  ///
    47   ///\param _Prio Type of the priority of the items.
    48   ///\param _ItemIntMap A read and writable Item int map, used internally
    49   ///to handle the cross references.
    50   ///\param _Compare A class for the ordering of the priorities. The
    51   ///default is \c std::less<_Prio>.
    52   ///
    53   ///\sa BinHeap
    54   ///\sa Dijkstra
    55   ///\author Dorian Batha
    56 
     46  /// \tparam PR Type of the priorities of the items.
     47  /// \tparam IM A read-writable item map with \c int values, used
     48  /// internally to handle the cross references.
     49  /// \tparam CMP A functor class for comparing the priorities.
     50  /// The default is \c std::less<PR>.
    5751#ifdef DOXYGEN
    58   template <typename _Prio,
    59             typename _ItemIntMap,
    60             typename _Compare>
     52  template <typename PR, typename IM, typename CMP>
    6153#else
    62   template <typename _Prio,
    63             typename _ItemIntMap,
    64             typename _Compare = std::less<_Prio> >
     54  template <typename PR, typename IM, typename CMP = std::less<PR> >
    6555#endif
    6656  class BinomHeap {
    6757  public:
    68     typedef _ItemIntMap ItemIntMap;
    69     typedef _Prio Prio;
     58    /// Type of the item-int map.
     59    typedef IM ItemIntMap;
     60    /// Type of the priorities.
     61    typedef PR Prio;
     62    /// Type of the items stored in the heap.
    7063    typedef typename ItemIntMap::Key Item;
    71     typedef std::pair<Item,Prio> Pair;
    72     typedef _Compare Compare;
     64    /// Functor type for comparing the priorities.
     65    typedef CMP Compare;
     66
     67    /// \brief Type to represent the states of the items.
     68    ///
     69    /// Each item has a state associated to it. It can be "in heap",
     70    /// "pre-heap" or "post-heap". The latter two are indifferent from the
     71    /// heap's point of view, but may be useful to the user.
     72    ///
     73    /// The item-int map must be initialized in such way that it assigns
     74    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
     75    enum State {
     76      IN_HEAP = 0,    ///< = 0.
     77      PRE_HEAP = -1,  ///< = -1.
     78      POST_HEAP = -2  ///< = -2.
     79    };
    7380
    7481  private:
    7582    class store;
    7683
    77     std::vector<store> container;
    78     int minimum, head;
    79     ItemIntMap &iimap;
    80     Compare comp;
    81     int num_items;
     84    std::vector<store> _data;
     85    int _min, _head;
     86    ItemIntMap &_iim;
     87    Compare _comp;
     88    int _num_items;
    8289
    8390  public:
    84     ///Status of the nodes
    85     enum State {
    86       ///The node is in the heap
    87       IN_HEAP = 0,
    88       ///The node has never been in the heap
    89       PRE_HEAP = -1,
    90       ///The node was in the heap but it got out of it
    91       POST_HEAP = -2
    92     };
    93 
    94     /// \brief The constructor
    95     ///
    96     /// \c _iimap should be given to the constructor, since it is
    97     ///   used internally to handle the cross references.
    98     explicit BinomHeap(ItemIntMap &_iimap)
    99       : minimum(0), head(-1), iimap(_iimap), num_items() {}
    100 
    101     /// \brief The constructor
    102     ///
    103     /// \c _iimap should be given to the constructor, since it is used
    104     /// internally to handle the cross references. \c _comp is an
    105     /// object for ordering of the priorities.
    106     BinomHeap(ItemIntMap &_iimap, const Compare &_comp)
    107       : minimum(0), head(-1), iimap(_iimap), comp(_comp), num_items() {}
     91    /// \brief Constructor.
     92    ///
     93    /// Constructor.
     94    /// \param map A map that assigns \c int values to the items.
     95    /// It is used internally to handle the cross references.
     96    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     97    explicit BinomHeap(ItemIntMap &map)
     98      : _min(0), _head(-1), _iim(map), _num_items(0) {}
     99
     100    /// \brief Constructor.
     101    ///
     102    /// Constructor.
     103    /// \param map A map that assigns \c int values to the items.
     104    /// It is used internally to handle the cross references.
     105    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     106    /// \param comp The function object used for comparing the priorities.
     107    BinomHeap(ItemIntMap &map, const Compare &comp)
     108      : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
    108109
    109110    /// \brief The number of items stored in the heap.
    110111    ///
    111     /// Returns the number of items stored in the heap.
    112     int size() const { return num_items; }
    113 
    114     /// \brief Checks if the heap stores no items.
    115     ///
    116     ///   Returns \c true if and only if the heap stores no items.
    117     bool empty() const { return num_items==0; }
    118 
    119     /// \brief Make empty this heap.
    120     ///
    121     /// Make empty this heap. It does not change the cross reference
    122     /// map.  If you want to reuse a heap what is not surely empty you
    123     /// should first clear the heap and after that you should set the
    124     /// cross reference map for each item to \c PRE_HEAP.
     112    /// This function returns the number of items stored in the heap.
     113    int size() const { return _num_items; }
     114
     115    /// \brief Check if the heap is empty.
     116    ///
     117    /// This function returns \c true if the heap is empty.
     118    bool empty() const { return _num_items==0; }
     119
     120    /// \brief Make the heap empty.
     121    ///
     122    /// This functon makes the heap empty.
     123    /// It does not change the cross reference map. If you want to reuse
     124    /// a heap that is not surely empty, you should first clear it and
     125    /// then you should set the cross reference map to \c PRE_HEAP
     126    /// for each item.
    125127    void clear() {
    126       container.clear(); minimum=0; num_items=0; head=-1;
    127     }
    128 
    129     /// \brief \c item gets to the heap with priority \c value independently
    130     /// if \c item was already there.
    131     ///
    132     /// This method calls \ref push(\c item, \c value) if \c item is not
    133     /// stored in the heap and it calls \ref decrease(\c item, \c value) or
    134     /// \ref increase(\c item, \c value) otherwise.
     128      _data.clear(); _min=0; _num_items=0; _head=-1;
     129    }
     130
     131    /// \brief Set the priority of an item or insert it, if it is
     132    /// not stored in the heap.
     133    ///
     134    /// This method sets the priority of the given item if it is
     135    /// already stored in the heap. Otherwise it inserts the given
     136    /// item into the heap with the given priority.
     137    /// \param item The item.
     138    /// \param value The priority.
    135139    void set (const Item& item, const Prio& value) {
    136       int i=iimap[item];
    137       if ( i >= 0 && container[i].in ) {
    138         if ( comp(value, container[i].prio) ) decrease(item, value);
    139         if ( comp(container[i].prio, value) ) increase(item, value);
     140      int i=_iim[item];
     141      if ( i >= 0 && _data[i].in ) {
     142        if ( _comp(value, _data[i].prio) ) decrease(item, value);
     143        if ( _comp(_data[i].prio, value) ) increase(item, value);
    140144      } else push(item, value);
    141145    }
    142146
    143     /// \brief Adds \c item to the heap with priority \c value.
    144     ///
    145     /// Adds \c item to the heap with priority \c value.
    146     /// \pre \c item must not be stored in the heap.
     147    /// \brief Insert an item into the heap with the given priority.
     148    ///
     149    /// This function inserts the given item into the heap with the
     150    /// given priority.
     151    /// \param item The item to insert.
     152    /// \param value The priority of the item.
     153    /// \pre \e item must not be stored in the heap.
    147154    void push (const Item& item, const Prio& value) {
    148       int i=iimap[item];
     155      int i=_iim[item];
    149156      if ( i<0 ) {
    150         int s=container.size();
    151         iimap.set( item,s );
     157        int s=_data.size();
     158        _iim.set( item,s );
    152159        store st;
    153160        st.name=item;
    154         container.push_back(st);
     161        _data.push_back(st);
    155162        i=s;
    156163      }
    157164      else {
    158         container[i].parent=container[i].right_neighbor=container[i].child=-1;
    159         container[i].degree=0;
    160         container[i].in=true;
    161       }
    162       container[i].prio=value;
    163 
    164       if( 0==num_items ) { head=i; minimum=i; }
     165        _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
     166        _data[i].degree=0;
     167        _data[i].in=true;
     168      }
     169      _data[i].prio=value;
     170
     171      if( 0==_num_items ) { _head=i; _min=i; }
    165172      else { merge(i); }
    166173
    167       minimum = find_min();
    168 
    169       ++num_items;
    170     }
    171 
    172     /// \brief Returns the item with minimum priority relative to \c Compare.
    173     ///
    174     /// This method returns the item with minimum priority relative to \c
    175     /// Compare.
    176     /// \pre The heap must be nonempty.
    177     Item top() const { return container[minimum].name; }
    178 
    179     /// \brief Returns the minimum priority relative to \c Compare.
    180     ///
    181     /// It returns the minimum priority relative to \c Compare.
    182     /// \pre The heap must be nonempty.
    183     const Prio& prio() const { return container[minimum].prio; }
    184 
    185     /// \brief Returns the priority of \c item.
    186     ///
    187     /// It returns the priority of \c item.
    188     /// \pre \c item must be in the heap.
     174      _min = findMin();
     175
     176      ++_num_items;
     177    }
     178
     179    /// \brief Return the item having minimum priority.
     180    ///
     181    /// This function returns the item having minimum priority.
     182    /// \pre The heap must be non-empty.
     183    Item top() const { return _data[_min].name; }
     184
     185    /// \brief The minimum priority.
     186    ///
     187    /// This function returns the minimum priority.
     188    /// \pre The heap must be non-empty.
     189    Prio prio() const { return _data[_min].prio; }
     190
     191    /// \brief The priority of the given item.
     192    ///
     193    /// This function returns the priority of the given item.
     194    /// \param item The item.
     195    /// \pre \e item must be in the heap.
    189196    const Prio& operator[](const Item& item) const {
    190       return container[iimap[item]].prio;
    191     }
    192 
    193     /// \brief Deletes the item with minimum priority relative to \c Compare.
    194     ///
    195     /// This method deletes the item with minimum priority relative to \c
    196     /// Compare from the heap.
     197      return _data[_iim[item]].prio;
     198    }
     199
     200    /// \brief Remove the item having minimum priority.
     201    ///
     202    /// This function removes the item having minimum priority.
    197203    /// \pre The heap must be non-empty.
    198204    void pop() {
    199       container[minimum].in=false;
     205      _data[_min].in=false;
    200206
    201207      int head_child=-1;
    202       if ( container[minimum].child!=-1 ) {
    203         int child=container[minimum].child;
     208      if ( _data[_min].child!=-1 ) {
     209        int child=_data[_min].child;
    204210        int neighb;
    205211        int prev=-1;
    206212        while( child!=-1 ) {
    207           neighb=container[child].right_neighbor;
    208           container[child].parent=-1;
    209           container[child].right_neighbor=prev;
     213          neighb=_data[child].right_neighbor;
     214          _data[child].parent=-1;
     215          _data[child].right_neighbor=prev;
    210216          head_child=child;
    211217          prev=child;
     
    215221
    216222      // The first case is that there are only one root.
    217       if ( -1==container[head].right_neighbor ) {
    218         head=head_child;
     223      if ( -1==_data[_head].right_neighbor ) {
     224        _head=head_child;
    219225      }
    220226      // The case where there are more roots.
    221227      else {
    222         if( head!=minimum )  { unlace(minimum); }
    223         else { head=container[head].right_neighbor; }
     228        if( _head!=_min )  { unlace(_min); }
     229        else { _head=_data[_head].right_neighbor; }
    224230
    225231        merge(head_child);
    226232      }
    227       minimum=find_min();
    228       --num_items;
    229     }
    230 
    231     /// \brief Deletes \c item from the heap.
    232     ///
    233     /// This method deletes \c item from the heap, if \c item was already
    234     /// stored in the heap. It is quite inefficient in Binomial heaps.
     233      _min=findMin();
     234      --_num_items;
     235    }
     236
     237    /// \brief Remove the given item from the heap.
     238    ///
     239    /// This function removes the given item from the heap if it is
     240    /// already stored.
     241    /// \param item The item to delete.
     242    /// \pre \e item must be in the heap.
    235243    void erase (const Item& item) {
    236       int i=iimap[item];
    237       if ( i >= 0 && container[i].in ) {
    238         decrease( item, container[minimum].prio-1 );
     244      int i=_iim[item];
     245      if ( i >= 0 && _data[i].in ) {
     246        decrease( item, _data[_min].prio-1 );
    239247        pop();
    240248      }
    241249    }
    242250
    243     /// \brief Decreases the priority of \c item to \c value.
    244     ///
    245     /// This method decreases the priority of \c item to \c value.
    246     /// \pre \c item must be stored in the heap with priority at least \c
    247     ///   value relative to \c Compare.
     251    /// \brief Decrease the priority of an item to the given value.
     252    ///
     253    /// This function decreases the priority of an item to the given value.
     254    /// \param item The item.
     255    /// \param value The priority.
     256    /// \pre \e item must be stored in the heap with priority at least \e value.
    248257    void decrease (Item item, const Prio& value) {
    249       int i=iimap[item];
    250 
    251       if( comp( value,container[i].prio ) ) {
    252         container[i].prio=value;
    253 
    254         int p_loc=container[i].parent, loc=i;
     258      int i=_iim[item];
     259
     260      if( _comp( value,_data[i].prio ) ) {
     261        _data[i].prio=value;
     262
     263        int p_loc=_data[i].parent, loc=i;
    255264        int parent, child, neighb;
    256265
    257         while( -1!=p_loc && comp(container[loc].prio,container[p_loc].prio) ) {
     266        while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) {
    258267
    259268          // parent set for other loc_child
    260           child=container[loc].child;
     269          child=_data[loc].child;
    261270          while( -1!=child ) {
    262             container[child].parent=p_loc;
    263             child=container[child].right_neighbor;
     271            _data[child].parent=p_loc;
     272            child=_data[child].right_neighbor;
    264273          }
    265274
    266275          // parent set for other p_loc_child
    267           child=container[p_loc].child;
     276          child=_data[p_loc].child;
    268277          while( -1!=child ) {
    269             container[child].parent=loc;
    270             child=container[child].right_neighbor;
    271           }
    272 
    273           child=container[p_loc].child;
    274           container[p_loc].child=container[loc].child;
     278            _data[child].parent=loc;
     279            child=_data[child].right_neighbor;
     280          }
     281
     282          child=_data[p_loc].child;
     283          _data[p_loc].child=_data[loc].child;
    275284          if( child==loc )
    276285            child=p_loc;
    277           container[loc].child=child;
     286          _data[loc].child=child;
    278287
    279288          // left_neighb set for p_loc
    280           if( container[loc].child!=p_loc ) {
    281             while( container[child].right_neighbor!=loc )
    282               child=container[child].right_neighbor;
    283             container[child].right_neighbor=p_loc;
     289          if( _data[loc].child!=p_loc ) {
     290            while( _data[child].right_neighbor!=loc )
     291              child=_data[child].right_neighbor;
     292            _data[child].right_neighbor=p_loc;
    284293          }
    285294
    286295          // left_neighb set for loc
    287           parent=container[p_loc].parent;
    288           if( -1!=parent ) child=container[parent].child;
    289           else child=head;
     296          parent=_data[p_loc].parent;
     297          if( -1!=parent ) child=_data[parent].child;
     298          else child=_head;
    290299
    291300          if( child!=p_loc ) {
    292             while( container[child].right_neighbor!=p_loc )
    293               child=container[child].right_neighbor;
    294             container[child].right_neighbor=loc;
    295           }
    296 
    297           neighb=container[p_loc].right_neighbor;
    298           container[p_loc].right_neighbor=container[loc].right_neighbor;
    299           container[loc].right_neighbor=neighb;
    300 
    301           container[p_loc].parent=loc;
    302           container[loc].parent=parent;
    303 
    304           if( -1!=parent && container[parent].child==p_loc )
    305             container[parent].child=loc;
     301            while( _data[child].right_neighbor!=p_loc )
     302              child=_data[child].right_neighbor;
     303            _data[child].right_neighbor=loc;
     304          }
     305
     306          neighb=_data[p_loc].right_neighbor;
     307          _data[p_loc].right_neighbor=_data[loc].right_neighbor;
     308          _data[loc].right_neighbor=neighb;
     309
     310          _data[p_loc].parent=loc;
     311          _data[loc].parent=parent;
     312
     313          if( -1!=parent && _data[parent].child==p_loc )
     314            _data[parent].child=loc;
    306315
    307316          /*if new parent will be the first root*/
    308           if( head==p_loc )
    309             head=loc;
    310 
    311           p_loc=container[loc].parent;
    312         }
    313       }
    314       if( comp(value,container[minimum].prio) ) {
    315         minimum=i;
    316       }
    317     }
    318 
    319     /// \brief Increases the priority of \c item to \c value.
    320     ///
    321     /// This method sets the priority of \c item to \c value. Though
    322     /// there is no precondition on the priority of \c item, this
    323     /// method should be used only if it is indeed necessary to increase
    324     /// (relative to \c Compare) the priority of \c item, because this
    325     /// method is inefficient.
     317          if( _head==p_loc )
     318            _head=loc;
     319
     320          p_loc=_data[loc].parent;
     321        }
     322      }
     323      if( _comp(value,_data[_min].prio) ) {
     324        _min=i;
     325      }
     326    }
     327
     328    /// \brief Increase the priority of an item to the given value.
     329    ///
     330    /// This function increases the priority of an item to the given value.
     331    /// \param item The item.
     332    /// \param value The priority.
     333    /// \pre \e item must be stored in the heap with priority at most \e value.
    326334    void increase (Item item, const Prio& value) {
    327335      erase(item);
     
    329337    }
    330338
    331 
    332     /// \brief Returns if \c item is in, has already been in, or has never
    333     /// been in the heap.
    334     ///
    335     /// This method returns PRE_HEAP if \c item has never been in the
    336     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    337     /// otherwise. In the latter case it is possible that \c item will
    338     /// get back to the heap again.
     339    /// \brief Return the state of an item.
     340    ///
     341    /// This method returns \c PRE_HEAP if the given item has never
     342    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
     343    /// and \c POST_HEAP otherwise.
     344    /// In the latter case it is possible that the item will get back
     345    /// to the heap again.
     346    /// \param item The item.
    339347    State state(const Item &item) const {
    340       int i=iimap[item];
     348      int i=_iim[item];
    341349      if( i>=0 ) {
    342         if ( container[i].in ) i=0;
     350        if ( _data[i].in ) i=0;
    343351        else i=-2;
    344352      }
     
    346354    }
    347355
    348     /// \brief Sets the state of the \c item in the heap.
    349     ///
    350     /// Sets the state of the \c item in the heap. It can be used to
    351     /// manually clear the heap when it is important to achive the
    352     /// better time complexity.
     356    /// \brief Set the state of an item in the heap.
     357    ///
     358    /// This function sets the state of the given item in the heap.
     359    /// It can be used to manually clear the heap when it is important
     360    /// to achive better time complexity.
    353361    /// \param i The item.
    354362    /// \param st The state. It should not be \c IN_HEAP.
     
    360368          erase(i);
    361369        }
    362         iimap[i] = st;
     370        _iim[i] = st;
    363371        break;
    364372      case IN_HEAP:
     
    368376
    369377  private:
    370     int find_min() {
     378    int findMin() {
    371379      int min_loc=-1, min_val;
    372       int x=head;
     380      int x=_head;
    373381      if( x!=-1 ) {
    374         min_val=container[x].prio;
     382        min_val=_data[x].prio;
    375383        min_loc=x;
    376         x=container[x].right_neighbor;
     384        x=_data[x].right_neighbor;
    377385
    378386        while( x!=-1 ) {
    379           if( comp( container[x].prio,min_val ) ) {
    380             min_val=container[x].prio;
     387          if( _comp( _data[x].prio,min_val ) ) {
     388            min_val=_data[x].prio;
    381389            min_loc=x;
    382390          }
    383           x=container[x].right_neighbor;
     391          x=_data[x].right_neighbor;
    384392        }
    385393      }
     
    390398      interleave(a);
    391399
    392       int x=head;
     400      int x=_head;
    393401      if( -1!=x ) {
    394         int x_prev=-1, x_next=container[x].right_neighbor;
     402        int x_prev=-1, x_next=_data[x].right_neighbor;
    395403        while( -1!=x_next ) {
    396           if( container[x].degree!=container[x_next].degree || ( -1!=container[x_next].right_neighbor && container[container[x_next].right_neighbor].degree==container[x].degree ) ) {
     404          if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
    397405            x_prev=x;
    398406            x=x_next;
    399407          }
    400408          else {
    401             if( comp(container[x].prio,container[x_next].prio) ) {
    402               container[x].right_neighbor=container[x_next].right_neighbor;
     409            if( _comp(_data[x].prio,_data[x_next].prio) ) {
     410              _data[x].right_neighbor=_data[x_next].right_neighbor;
    403411              fuse(x_next,x);
    404412            }
    405413            else {
    406               if( -1==x_prev ) { head=x_next; }
     414              if( -1==x_prev ) { _head=x_next; }
    407415              else {
    408                 container[x_prev].right_neighbor=x_next;
     416                _data[x_prev].right_neighbor=x_next;
    409417              }
    410418              fuse(x,x_next);
     
    412420            }
    413421          }
    414           x_next=container[x].right_neighbor;
     422          x_next=_data[x].right_neighbor;
    415423        }
    416424      }
     
    420428      int other=-1, head_other=-1;
    421429
    422       while( -1!=a || -1!=head ) {
     430      while( -1!=a || -1!=_head ) {
    423431        if( -1==a ) {
    424432          if( -1==head_other ) {
    425             head_other=head;
     433            head_other=_head;
    426434          }
    427435          else {
    428             container[other].right_neighbor=head;
    429           }
    430           head=-1;
    431         }
    432         else if( -1==head ) {
     436            _data[other].right_neighbor=_head;
     437          }
     438          _head=-1;
     439        }
     440        else if( -1==_head ) {
    433441          if( -1==head_other ) {
    434442            head_other=a;
    435443          }
    436444          else {
    437             container[other].right_neighbor=a;
     445            _data[other].right_neighbor=a;
    438446          }
    439447          a=-1;
    440448        }
    441449        else {
    442           if( container[a].degree<container[head].degree ) {
     450          if( _data[a].degree<_data[_head].degree ) {
    443451            if( -1==head_other ) {
    444452              head_other=a;
    445453            }
    446454            else {
    447               container[other].right_neighbor=a;
     455              _data[other].right_neighbor=a;
    448456            }
    449457            other=a;
    450             a=container[a].right_neighbor;
     458            a=_data[a].right_neighbor;
    451459          }
    452460          else {
    453461            if( -1==head_other ) {
    454               head_other=head;
     462              head_other=_head;
    455463            }
    456464            else {
    457               container[other].right_neighbor=head;
     465              _data[other].right_neighbor=_head;
    458466            }
    459             other=head;
    460             head=container[head].right_neighbor;
    461           }
    462         }
    463       }
    464       head=head_other;
     467            other=_head;
     468            _head=_data[_head].right_neighbor;
     469          }
     470        }
     471      }
     472      _head=head_other;
    465473    }
    466474
    467475    // Lacing a under b
    468476    void fuse(int a, int b) {
    469       container[a].parent=b;
    470       container[a].right_neighbor=container[b].child;
    471       container[b].child=a;
    472 
    473       ++container[b].degree;
     477      _data[a].parent=b;
     478      _data[a].right_neighbor=_data[b].child;
     479      _data[b].child=a;
     480
     481      ++_data[b].degree;
    474482    }
    475483
    476484    // It is invoked only if a has siblings.
    477485    void unlace(int a) {
    478       int neighb=container[a].right_neighbor;
    479       int other=head;
    480 
    481       while( container[other].right_neighbor!=a )
    482         other=container[other].right_neighbor;
    483       container[other].right_neighbor=neighb;
     486      int neighb=_data[a].right_neighbor;
     487      int other=_head;
     488
     489      while( _data[other].right_neighbor!=a )
     490        other=_data[other].right_neighbor;
     491      _data[other].right_neighbor=neighb;
    484492    }
    485493
  • lemon/fourary_heap.h

    r748 r750  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
    4  *
    5  * Copyright (C) 2003-2008
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
     4 *
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2020#define LEMON_FOURARY_HEAP_H
    2121
    22 ///\ingroup auxdat
     22///\ingroup heaps
    2323///\file
    24 ///\brief 4ary Heap implementation.
    25 
    26 #include <iostream>
     24///\brief Fourary heap implementation.
     25
    2726#include <vector>
    2827#include <utility>
     
    3130namespace lemon {
    3231
    33   ///\ingroup auxdat
    34   ///
    35   ///\brief A 4ary Heap implementation.
    36   ///
    37   ///This class implements the \e 4ary \e heap data structure. A \e heap
    38   ///is a data structure for storing items with specified values called \e
    39   ///priorities in such a way that finding the item with minimum priority is
    40   ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    41   ///one can change the priority of an item, add or erase an item, etc.
    42   ///
    43   ///\param _Prio Type of the priority of the items.
    44   ///\param _ItemIntMap A read and writable Item int map, used internally
    45   ///to handle the cross references.
    46   ///\param _Compare A class for the ordering of the priorities. The
    47   ///default is \c std::less<_Prio>.
    48   ///
    49   ///\sa FibHeap
    50   ///\sa Dijkstra
    51   ///\author Dorian Batha
    52 
    53   template <typename _Prio, typename _ItemIntMap,
    54             typename _Compare = std::less<_Prio> >
    55 
     32  /// \ingroup heaps
     33  ///
     34  ///\brief Fourary heap data structure.
     35  ///
     36  /// This class implements the \e fourary \e heap data structure.
     37  /// It fully conforms to the \ref concepts::Heap "heap concept".
     38  ///
     39  /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap"
     40  /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap",
     41  /// but its nodes have at most four children, instead of two.
     42  ///
     43  /// \tparam PR Type of the priorities of the items.
     44  /// \tparam IM A read-writable item map with \c int values, used
     45  /// internally to handle the cross references.
     46  /// \tparam CMP A functor class for comparing the priorities.
     47  /// The default is \c std::less<PR>.
     48  ///
     49  ///\sa BinHeap
     50  ///\sa KaryHeap
     51#ifdef DOXYGEN
     52  template <typename PR, typename IM, typename CMP>
     53#else
     54  template <typename PR, typename IM, typename CMP = std::less<PR> >
     55#endif
    5656  class FouraryHeap {
    57 
    5857  public:
    59     ///\e
    60     typedef _ItemIntMap ItemIntMap;
    61     ///\e
    62     typedef _Prio Prio;
    63     ///\e
     58    /// Type of the item-int map.
     59    typedef IM ItemIntMap;
     60    /// Type of the priorities.
     61    typedef PR Prio;
     62    /// Type of the items stored in the heap.
    6463    typedef typename ItemIntMap::Key Item;
    65     ///\e
     64    /// Type of the item-priority pairs.
    6665    typedef std::pair<Item,Prio> Pair;
    67     ///\e
    68     typedef _Compare Compare;
    69 
    70     /// \brief Type to represent the items states.
    71     ///
    72     /// Each Item element have a state associated to it. It may be "in heap",
    73     /// "pre heap" or "post heap". The latter two are indifferent from the
     66    /// Functor type for comparing the priorities.
     67    typedef CMP Compare;
     68
     69    /// \brief Type to represent the states of the items.
     70    ///
     71    /// Each item has a state associated to it. It can be "in heap",
     72    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    7473    /// heap's point of view, but may be useful to the user.
    7574    ///
    76     /// The ItemIntMap \e should be initialized in such way that it maps
    77     /// PRE_HEAP (-1) to any element to be put in the heap...
     75    /// The item-int map must be initialized in such way that it assigns
     76    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    7877    enum State {
    79       IN_HEAP = 0,
    80       PRE_HEAP = -1,
    81       POST_HEAP = -2
     78      IN_HEAP = 0,    ///< = 0.
     79      PRE_HEAP = -1,  ///< = -1.
     80      POST_HEAP = -2  ///< = -2.
    8281    };
    8382
    8483  private:
    85     std::vector<Pair> data;
    86     Compare comp;
    87     ItemIntMap &iim;
     84    std::vector<Pair> _data;
     85    Compare _comp;
     86    ItemIntMap &_iim;
    8887
    8988  public:
    90     /// \brief The constructor.
    91     ///
    92     /// The constructor.
    93     /// \param _iim should be given to the constructor, since it is used
    94     /// internally to handle the cross references. The value of the map
    95     /// should be PRE_HEAP (-1) for each element.
    96     explicit FouraryHeap(ItemIntMap &_iim) : iim(_iim) {}
    97 
    98     /// \brief The constructor.
    99     ///
    100     /// The constructor.
    101     /// \param _iim should be given to the constructor, since it is used
    102     /// internally to handle the cross references. The value of the map
    103     /// should be PRE_HEAP (-1) for each element.
    104     ///
    105     /// \param _comp The comparator function object.
    106     FouraryHeap(ItemIntMap &_iim, const Compare &_comp)
    107       : iim(_iim), comp(_comp) {}
    108 
    109     /// The number of items stored in the heap.
    110     ///
    111     /// \brief Returns the number of items stored in the heap.
    112     int size() const { return data.size(); }
    113 
    114     /// \brief Checks if the heap stores no items.
    115     ///
    116     /// Returns \c true if and only if the heap stores no items.
    117     bool empty() const { return data.empty(); }
    118 
    119     /// \brief Make empty this heap.
    120     ///
    121     /// Make empty this heap. It does not change the cross reference map.
    122     /// If you want to reuse what is not surely empty you should first clear
    123     /// the heap and after that you should set the cross reference map for
    124     /// each item to \c PRE_HEAP.
    125     void clear() { data.clear(); }
     89    /// \brief Constructor.
     90    ///
     91    /// Constructor.
     92    /// \param map A map that assigns \c int values to the items.
     93    /// It is used internally to handle the cross references.
     94    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     95    explicit FouraryHeap(ItemIntMap &map) : _iim(map) {}
     96
     97    /// \brief Constructor.
     98    ///
     99    /// Constructor.
     100    /// \param map A map that assigns \c int values to the items.
     101    /// It is used internally to handle the cross references.
     102    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     103    /// \param comp The function object used for comparing the priorities.
     104    FouraryHeap(ItemIntMap &map, const Compare &comp)
     105      : _iim(map), _comp(comp) {}
     106
     107    /// \brief The number of items stored in the heap.
     108    ///
     109    /// This function returns the number of items stored in the heap.
     110    int size() const { return _data.size(); }
     111
     112    /// \brief Check if the heap is empty.
     113    ///
     114    /// This function returns \c true if the heap is empty.
     115    bool empty() const { return _data.empty(); }
     116
     117    /// \brief Make the heap empty.
     118    ///
     119    /// This functon makes the heap empty.
     120    /// It does not change the cross reference map. If you want to reuse
     121    /// a heap that is not surely empty, you should first clear it and
     122    /// then you should set the cross reference map to \c PRE_HEAP
     123    /// for each item.
     124    void clear() { _data.clear(); }
    126125
    127126  private:
     
    130129
    131130    bool less(const Pair &p1, const Pair &p2) const {
    132       return comp(p1.second, p2.second);
    133     }
    134 
    135     int find_min(const int child, const int length) {
     131      return _comp(p1.second, p2.second);
     132    }
     133
     134    int findMin(const int child, const int length) {
    136135      int min=child;
    137136      if( child+3<length ) {
    138         if( less(data[child+3], data[min]) )
     137        if( less(_data[child+3], _data[min]) )
    139138          min=child+3;
    140         if( less(data[child+2], data[min]) )
     139        if( less(_data[child+2], _data[min]) )
    141140          min=child+2;
    142         if( less(data[child+1], data[min]) )
     141        if( less(_data[child+1], _data[min]) )
    143142          min=child+1;
    144143      }
    145144      else if( child+2<length ) {
    146         if( less(data[child+2], data[min]) )
     145        if( less(_data[child+2], _data[min]) )
    147146          min=child+2;
    148         if( less(data[child+1], data[min]) )
     147        if( less(_data[child+1], _data[min]) )
    149148          min=child+1;
    150149      }
    151150      else if( child+1<length ) {
    152         if( less(data[child+1], data[min]) )
     151        if( less(_data[child+1], _data[min]) )
    153152          min=child+1;
    154153      }
     
    156155    }
    157156
    158     void bubble_up(int hole, Pair p) {
     157    void bubbleUp(int hole, Pair p) {
    159158      int par = parent(hole);
    160       while( hole>0 && less(p,data[par]) ) {
    161         move(data[par],hole);
     159      while( hole>0 && less(p,_data[par]) ) {
     160        move(_data[par],hole);
    162161        hole = par;
    163162        par = parent(hole);
     
    166165    }
    167166
    168     void bubble_down(int hole, Pair p, int length) {
     167    void bubbleDown(int hole, Pair p, int length) {
    169168      int child = firstChild(hole);
    170169      while( child<length && length>1 ) {
    171         child = find_min(child,length);
    172         if( !less(data[child], p) )
     170        child = findMin(child,length);
     171        if( !less(_data[child], p) )
    173172          goto ok;
    174         move(data[child], hole);
     173        move(_data[child], hole);
    175174        hole = child;
    176175        child = firstChild(hole);
     
    181180
    182181    void move(const Pair &p, int i) {
    183       data[i] = p;
    184       iim.set(p.first, i);
     182      _data[i] = p;
     183      _iim.set(p.first, i);
    185184    }
    186185
    187186  public:
    188 
    189187    /// \brief Insert a pair of item and priority into the heap.
    190188    ///
    191     /// Adds \c p.first to the heap with priority \c p.second.
     189    /// This function inserts \c p.first to the heap with priority
     190    /// \c p.second.
    192191    /// \param p The pair to insert.
     192    /// \pre \c p.first must not be stored in the heap.
    193193    void push(const Pair &p) {
    194       int n = data.size();
    195       data.resize(n+1);
    196       bubble_up(n, p);
    197     }
    198 
    199     /// \brief Insert an item into the heap with the given heap.
    200     ///
    201     /// Adds \c i to the heap with priority \c p.
     194      int n = _data.size();
     195      _data.resize(n+1);
     196      bubbleUp(n, p);
     197    }
     198
     199    /// \brief Insert an item into the heap with the given priority.
     200    ///
     201    /// This function inserts the given item into the heap with the
     202    /// given priority.
    202203    /// \param i The item to insert.
    203204    /// \param p The priority of the item.
     205    /// \pre \e i must not be stored in the heap.
    204206    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    205207
    206     /// \brief Returns the item with minimum priority relative to \c Compare.
    207     ///
    208     /// This method returns the item with minimum priority relative to \c
    209     /// Compare.
    210     /// \pre The heap must be nonempty.
    211     Item top() const { return data[0].first; }
    212 
    213     /// \brief Returns the minimum priority relative to \c Compare.
    214     ///
    215     /// It returns the minimum priority relative to \c Compare.
    216     /// \pre The heap must be nonempty.
    217     Prio prio() const { return data[0].second; }
    218 
    219     /// \brief Deletes the item with minimum priority relative to \c Compare.
    220     ///
    221     /// This method deletes the item with minimum priority relative to \c
    222     /// Compare from the heap.
     208    /// \brief Return the item having minimum priority.
     209    ///
     210    /// This function returns the item having minimum priority.
     211    /// \pre The heap must be non-empty.
     212    Item top() const { return _data[0].first; }
     213
     214    /// \brief The minimum priority.
     215    ///
     216    /// This function returns the minimum priority.
     217    /// \pre The heap must be non-empty.
     218    Prio prio() const { return _data[0].second; }
     219
     220    /// \brief Remove the item having minimum priority.
     221    ///
     222    /// This function removes the item having minimum priority.
    223223    /// \pre The heap must be non-empty.
    224224    void pop() {
    225       int n = data.size()-1;
    226       iim.set(data[0].first, POST_HEAP);
    227       if (n>0) bubble_down(0, data[n], n);
    228       data.pop_back();
    229     }
    230 
    231     /// \brief Deletes \c i from the heap.
    232     ///
    233     /// This method deletes item \c i from the heap.
    234     /// \param i The item to erase.
    235     /// \pre The item should be in the heap.
     225      int n = _data.size()-1;
     226      _iim.set(_data[0].first, POST_HEAP);
     227      if (n>0) bubbleDown(0, _data[n], n);
     228      _data.pop_back();
     229    }
     230
     231    /// \brief Remove the given item from the heap.
     232    ///
     233    /// This function removes the given item from the heap if it is
     234    /// already stored.
     235    /// \param i The item to delete.
     236    /// \pre \e i must be in the heap.
    236237    void erase(const Item &i) {
    237       int h = iim[i];
    238       int n = data.size()-1;
    239       iim.set(data[h].first, POST_HEAP);
     238      int h = _iim[i];
     239      int n = _data.size()-1;
     240      _iim.set(_data[h].first, POST_HEAP);
    240241      if( h<n ) {
    241         if( less(data[parent(h)], data[n]) )
    242           bubble_down(h, data[n], n);
     242        if( less(_data[parent(h)], _data[n]) )
     243          bubbleDown(h, _data[n], n);
    243244        else
    244           bubble_up(h, data[n]);
    245       }
    246       data.pop_back();
    247     }
    248 
    249     /// \brief Returns the priority of \c i.
    250     ///
    251     /// This function returns the priority of item \c i.
    252     /// \pre \c i must be in the heap.
    253     /// \param i The item.
     245          bubbleUp(h, _data[n]);
     246      }
     247      _data.pop_back();
     248    }
     249
     250    /// \brief The priority of the given item.
     251    ///
     252    /// This function returns the priority of the given item.
     253    /// \param i The item.
     254    /// \pre \e i must be in the heap.
    254255    Prio operator[](const Item &i) const {
    255       int idx = iim[i];
    256       return data[idx].second;
    257     }
    258 
    259     /// \brief \c i gets to the heap with priority \c p independently
    260     /// if \c i was already there.
    261     ///
    262     /// This method calls \ref push(\c i, \c p) if \c i is not stored
    263     /// in the heap and sets the priority of \c i to \c p otherwise.
     256      int idx = _iim[i];
     257      return _data[idx].second;
     258    }
     259
     260    /// \brief Set the priority of an item or insert it, if it is
     261    /// not stored in the heap.
     262    ///
     263    /// This method sets the priority of the given item if it is
     264    /// already stored in the heap. Otherwise it inserts the given
     265    /// item into the heap with the given priority.
    264266    /// \param i The item.
    265267    /// \param p The priority.
    266268    void set(const Item &i, const Prio &p) {
    267       int idx = iim[i];
     269      int idx = _iim[i];
    268270      if( idx < 0 )
    269271        push(i,p);
    270       else if( comp(p, data[idx].second) )
    271         bubble_up(idx, Pair(i,p));
     272      else if( _comp(p, _data[idx].second) )
     273        bubbleUp(idx, Pair(i,p));
    272274      else
    273         bubble_down(idx, Pair(i,p), data.size());
    274     }
    275 
    276     /// \brief Decreases the priority of \c i to \c p.
    277     ///
    278     /// This method decreases the priority of item \c i to \c p.
    279     /// \pre \c i must be stored in the heap with priority at least \c
    280     /// p relative to \c Compare.
     275        bubbleDown(idx, Pair(i,p), _data.size());
     276    }
     277
     278    /// \brief Decrease the priority of an item to the given value.
     279    ///
     280    /// This function decreases the priority of an item to the given value.
    281281    /// \param i The item.
    282282    /// \param p The priority.
     283    /// \pre \e i must be stored in the heap with priority at least \e p.
    283284    void decrease(const Item &i, const Prio &p) {
    284       int idx = iim[i];
    285       bubble_up(idx, Pair(i,p));
    286     }
    287 
    288     /// \brief Increases the priority of \c i to \c p.
    289     ///
    290     /// This method sets the priority of item \c i to \c p.
    291     /// \pre \c i must be stored in the heap with priority at most \c
    292     /// p relative to \c Compare.
     285      int idx = _iim[i];
     286      bubbleUp(idx, Pair(i,p));
     287    }
     288
     289    /// \brief Increase the priority of an item to the given value.
     290    ///
     291    /// This function increases the priority of an item to the given value.
    293292    /// \param i The item.
    294293    /// \param p The priority.
     294    /// \pre \e i must be stored in the heap with priority at most \e p.
    295295    void increase(const Item &i, const Prio &p) {
    296       int idx = iim[i];
    297       bubble_down(idx, Pair(i,p), data.size());
    298     }
    299 
    300     /// \brief Returns if \c item is in, has already been in, or has
    301     /// never been in the heap.
    302     ///
    303     /// This method returns PRE_HEAP if \c item has never been in the
    304     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    305     /// otherwise. In the latter case it is possible that \c item will
    306     /// get back to the heap again.
     296      int idx = _iim[i];
     297      bubbleDown(idx, Pair(i,p), _data.size());
     298    }
     299
     300    /// \brief Return the state of an item.
     301    ///
     302    /// This method returns \c PRE_HEAP if the given item has never
     303    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
     304    /// and \c POST_HEAP otherwise.
     305    /// In the latter case it is possible that the item will get back
     306    /// to the heap again.
    307307    /// \param i The item.
    308308    State state(const Item &i) const {
    309       int s = iim[i];
     309      int s = _iim[i];
    310310      if (s>=0) s=0;
    311311      return State(s);
    312312    }
    313313
    314     /// \brief Sets the state of the \c item in the heap.
    315     ///
    316     /// Sets the state of the \c item in the heap. It can be used to
    317     /// manually clear the heap when it is important to achive the
    318     /// better time complexity.
     314    /// \brief Set the state of an item in the heap.
     315    ///
     316    /// This function sets the state of the given item in the heap.
     317    /// It can be used to manually clear the heap when it is important
     318    /// to achive better time complexity.
    319319    /// \param i The item.
    320320    /// \param st The state. It should not be \c IN_HEAP.
     
    324324        case PRE_HEAP:
    325325          if (state(i) == IN_HEAP) erase(i);
    326           iim[i] = st;
     326          _iim[i] = st;
    327327          break;
    328328        case IN_HEAP:
     
    331331    }
    332332
    333     /// \brief Replaces an item in the heap.
    334     ///
    335     /// The \c i item is replaced with \c j item. The \c i item should
    336     /// be in the heap, while the \c j should be out of the heap. The
    337     /// \c i item will out of the heap and \c j will be in the heap
    338     /// with the same prioriority as prevoiusly the \c i item.
     333    /// \brief Replace an item in the heap.
     334    ///
     335    /// This function replaces item \c i with item \c j.
     336    /// Item \c i must be in the heap, while \c j must be out of the heap.
     337    /// After calling this method, item \c i will be out of the
     338    /// heap and \c j will be in the heap with the same prioriority
     339    /// as item \c i had before.
    339340    void replace(const Item& i, const Item& j) {
    340       int idx = iim[i];
    341       iim.set(i, iim[j]);
    342       iim.set(j, idx);
    343       data[idx].first = j;
     341      int idx = _iim[i];
     342      _iim.set(i, _iim[j]);
     343      _iim.set(j, idx);
     344      _data[idx].first = j;
    344345    }
    345346
  • lemon/kary_heap.h

    r748 r750  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
    4  *
    5  * Copyright (C) 2003-2008
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
     4 *
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2020#define LEMON_KARY_HEAP_H
    2121
    22 ///\ingroup auxdat
     22///\ingroup heaps
    2323///\file
    24 ///\brief Kary Heap implementation.
    25 
    26 #include <iostream>
     24///\brief Fourary heap implementation.
     25
    2726#include <vector>
    2827#include <utility>
     
    3130namespace lemon {
    3231
    33   ///\ingroup auxdat
    34   ///
    35   ///\brief A Kary Heap implementation.
    36   ///
    37   ///This class implements the \e Kary \e heap data structure. A \e heap
    38   ///is a data structure for storing items with specified values called \e
    39   ///priorities in such a way that finding the item with minimum priority is
    40   ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    41   ///one can change the priority of an item, add or erase an item, etc.
    42   ///
    43   ///\param _Prio Type of the priority of the items.
    44   ///\param _ItemIntMap A read and writable Item int map, used internally
    45   ///to handle the cross references.
    46   ///\param _Compare A class for the ordering of the priorities. The
    47   ///default is \c std::less<_Prio>.
    48   ///
    49   ///\sa FibHeap
    50   ///\sa Dijkstra
    51   ///\author Dorian Batha
    52 
    53   template <typename _Prio, typename _ItemIntMap,
    54             typename _Compare = std::less<_Prio> >
    55 
     32  /// \ingroup heaps
     33  ///
     34  ///\brief K-ary heap data structure.
     35  ///
     36  /// This class implements the \e K-ary \e heap data structure.
     37  /// It fully conforms to the \ref concepts::Heap "heap concept".
     38  ///
     39  /// The \ref KaryHeap "K-ary heap" is a generalization of the
     40  /// \ref BinHeap "binary heap" structure, its nodes have at most
     41  /// \c K children, instead of two.
     42  /// \ref BinHeap and \ref FouraryHeap are specialized implementations
     43  /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively.
     44  ///
     45  /// \tparam PR Type of the priorities of the items.
     46  /// \tparam IM A read-writable item map with \c int values, used
     47  /// internally to handle the cross references.
     48  /// \tparam CMP A functor class for comparing the priorities.
     49  /// The default is \c std::less<PR>.
     50  ///
     51  ///\sa BinHeap
     52  ///\sa FouraryHeap
     53#ifdef DOXYGEN
     54  template <typename PR, typename IM, typename CMP>
     55#else
     56  template <typename PR, typename IM, typename CMP = std::less<PR> >
     57#endif
    5658  class KaryHeap {
    57 
    5859  public:
    59     ///\e
    60     typedef _ItemIntMap ItemIntMap;
    61     ///\e
    62     typedef _Prio Prio;
    63     ///\e
     60    /// Type of the item-int map.
     61    typedef IM ItemIntMap;
     62    /// Type of the priorities.
     63    typedef PR Prio;
     64    /// Type of the items stored in the heap.
    6465    typedef typename ItemIntMap::Key Item;
    65     ///\e
     66    /// Type of the item-priority pairs.
    6667    typedef std::pair<Item,Prio> Pair;
    67     ///\e
    68     typedef _Compare Compare;
    69     ///\e
    70 
    71     /// \brief Type to represent the items states.
    72     ///
    73     /// Each Item element have a state associated to it. It may be "in heap",
    74     /// "pre heap" or "post heap". The latter two are indifferent from the
     68    /// Functor type for comparing the priorities.
     69    typedef CMP Compare;
     70
     71    /// \brief Type to represent the states of the items.
     72    ///
     73    /// Each item has a state associated to it. It can be "in heap",
     74    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    7575    /// heap's point of view, but may be useful to the user.
    7676    ///
    77     /// The ItemIntMap \e should be initialized in such way that it maps
    78     /// PRE_HEAP (-1) to any element to be put in the heap...
     77    /// The item-int map must be initialized in such way that it assigns
     78    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    7979    enum State {
    80       IN_HEAP = 0,
    81       PRE_HEAP = -1,
    82       POST_HEAP = -2
     80      IN_HEAP = 0,    ///< = 0.
     81      PRE_HEAP = -1,  ///< = -1.
     82      POST_HEAP = -2  ///< = -2.
    8383    };
    8484
    8585  private:
    86     std::vector<Pair> data;
    87     Compare comp;
    88     ItemIntMap &iim;
    89     int K;
     86    std::vector<Pair> _data;
     87    Compare _comp;
     88    ItemIntMap &_iim;
     89    int _K;
    9090
    9191  public:
    92     /// \brief The constructor.
    93     ///
    94     /// The constructor.
    95     /// \param _iim should be given to the constructor, since it is used
    96     /// internally to handle the cross references. The value of the map
    97     /// should be PRE_HEAP (-1) for each element.
    98     explicit KaryHeap(ItemIntMap &_iim, const int &_K=32) : iim(_iim), K(_K) {}
    99 
    100     /// \brief The constructor.
    101     ///
    102     /// The constructor.
    103     /// \param _iim should be given to the constructor, since it is used
    104     /// internally to handle the cross references. The value of the map
    105     /// should be PRE_HEAP (-1) for each element.
    106     ///
    107     /// \param _comp The comparator function object.
    108     KaryHeap(ItemIntMap &_iim, const Compare &_comp, const int &_K=32)
    109       : iim(_iim), comp(_comp), K(_K) {}
    110 
    111 
    112     /// The number of items stored in the heap.
    113     ///
    114     /// \brief Returns the number of items stored in the heap.
    115     int size() const { return data.size(); }
    116 
    117     /// \brief Checks if the heap stores no items.
    118     ///
    119     /// Returns \c true if and only if the heap stores no items.
    120     bool empty() const { return data.empty(); }
    121 
    122     /// \brief Make empty this heap.
    123     ///
    124     /// Make empty this heap. It does not change the cross reference map.
    125     /// If you want to reuse what is not surely empty you should first clear
    126     /// the heap and after that you should set the cross reference map for
    127     /// each item to \c PRE_HEAP.
    128     void clear() { data.clear(); }
     92    /// \brief Constructor.
     93    ///
     94    /// Constructor.
     95    /// \param map A map that assigns \c int values to the items.
     96    /// It is used internally to handle the cross references.
     97    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     98    explicit KaryHeap(ItemIntMap &map, int K=32) : _iim(map), _K(K) {}
     99
     100    /// \brief Constructor.
     101    ///
     102    /// Constructor.
     103    /// \param map A map that assigns \c int values to the items.
     104    /// It is used internally to handle the cross references.
     105    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     106    /// \param comp The function object used for comparing the priorities.
     107    KaryHeap(ItemIntMap &map, const Compare &comp, int K=32)
     108      : _iim(map), _comp(comp), _K(K) {}
     109
     110    /// \brief The number of items stored in the heap.
     111    ///
     112    /// This function returns the number of items stored in the heap.
     113    int size() const { return _data.size(); }
     114
     115    /// \brief Check if the heap is empty.
     116    ///
     117    /// This function returns \c true if the heap is empty.
     118    bool empty() const { return _data.empty(); }
     119
     120    /// \brief Make the heap empty.
     121    ///
     122    /// This functon makes the heap empty.
     123    /// It does not change the cross reference map. If you want to reuse
     124    /// a heap that is not surely empty, you should first clear it and
     125    /// then you should set the cross reference map to \c PRE_HEAP
     126    /// for each item.
     127    void clear() { _data.clear(); }
    129128
    130129  private:
    131     int parent(int i) { return (i-1)/K; }
    132     int first_child(int i) { return K*i+1; }
     130    int parent(int i) { return (i-1)/_K; }
     131    int firstChild(int i) { return _K*i+1; }
    133132
    134133    bool less(const Pair &p1, const Pair &p2) const {
    135       return comp(p1.second, p2.second);
    136     }
    137 
    138     int find_min(const int child, const int length) {
     134      return _comp(p1.second, p2.second);
     135    }
     136
     137    int findMin(const int child, const int length) {
    139138      int min=child, i=1;
    140       while( i<K && child+i<length ) {
    141         if( less(data[child+i], data[min]) )
     139      while( i<_K && child+i<length ) {
     140        if( less(_data[child+i], _data[min]) )
    142141          min=child+i;
    143142        ++i;
     
    146145    }
    147146
    148     void bubble_up(int hole, Pair p) {
     147    void bubbleUp(int hole, Pair p) {
    149148      int par = parent(hole);
    150       while( hole>0 && less(p,data[par]) ) {
    151         move(data[par],hole);
     149      while( hole>0 && less(p,_data[par]) ) {
     150        move(_data[par],hole);
    152151        hole = par;
    153152        par = parent(hole);
     
    156155    }
    157156
    158     void bubble_down(int hole, Pair p, int length) {
     157    void bubbleDown(int hole, Pair p, int length) {
    159158      if( length>1 ) {
    160         int child = first_child(hole);
     159        int child = firstChild(hole);
    161160        while( child<length ) {
    162           child = find_min(child, length);
    163           if( !less(data[child], p) )
     161          child = findMin(child, length);
     162          if( !less(_data[child], p) )
    164163            goto ok;
    165           move(data[child], hole);
     164          move(_data[child], hole);
    166165          hole = child;
    167           child = first_child(hole);
     166          child = firstChild(hole);
    168167        }
    169168      }
     
    173172
    174173    void move(const Pair &p, int i) {
    175       data[i] = p;
    176       iim.set(p.first, i);
     174      _data[i] = p;
     175      _iim.set(p.first, i);
    177176    }
    178177
     
    180179    /// \brief Insert a pair of item and priority into the heap.
    181180    ///
    182     /// Adds \c p.first to the heap with priority \c p.second.
     181    /// This function inserts \c p.first to the heap with priority
     182    /// \c p.second.
    183183    /// \param p The pair to insert.
     184    /// \pre \c p.first must not be stored in the heap.
    184185    void push(const Pair &p) {
    185       int n = data.size();
    186       data.resize(n+1);
    187       bubble_up(n, p);
    188     }
    189 
    190     /// \brief Insert an item into the heap with the given heap.
    191     ///
    192     /// Adds \c i to the heap with priority \c p.
     186      int n = _data.size();
     187      _data.resize(n+1);
     188      bubbleUp(n, p);
     189    }
     190
     191    /// \brief Insert an item into the heap with the given priority.
     192    ///
     193    /// This function inserts the given item into the heap with the
     194    /// given priority.
    193195    /// \param i The item to insert.
    194196    /// \param p The priority of the item.
     197    /// \pre \e i must not be stored in the heap.
    195198    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    196199
    197     /// \brief Returns the item with minimum priority relative to \c Compare.
    198     ///
    199     /// This method returns the item with minimum priority relative to \c
    200     /// Compare.
    201     /// \pre The heap must be nonempty.
    202     Item top() const { return data[0].first; }
    203 
    204     /// \brief Returns the minimum priority relative to \c Compare.
    205     ///
    206     /// It returns the minimum priority relative to \c Compare.
    207     /// \pre The heap must be nonempty.
    208     Prio prio() const { return data[0].second; }
    209 
    210     /// \brief Deletes the item with minimum priority relative to \c Compare.
    211     ///
    212     /// This method deletes the item with minimum priority relative to \c
    213     /// Compare from the heap.
     200    /// \brief Return the item having minimum priority.
     201    ///
     202    /// This function returns the item having minimum priority.
     203    /// \pre The heap must be non-empty.
     204    Item top() const { return _data[0].first; }
     205
     206    /// \brief The minimum priority.
     207    ///
     208    /// This function returns the minimum priority.
     209    /// \pre The heap must be non-empty.
     210    Prio prio() const { return _data[0].second; }
     211
     212    /// \brief Remove the item having minimum priority.
     213    ///
     214    /// This function removes the item having minimum priority.
    214215    /// \pre The heap must be non-empty.
    215216    void pop() {
    216       int n = data.size()-1;
    217       iim.set(data[0].first, POST_HEAP);
    218       if (n>0) bubble_down(0, data[n], n);
    219       data.pop_back();
    220     }
    221 
    222     /// \brief Deletes \c i from the heap.
    223     ///
    224     /// This method deletes item \c i from the heap.
    225     /// \param i The item to erase.
    226     /// \pre The item should be in the heap.
     217      int n = _data.size()-1;
     218      _iim.set(_data[0].first, POST_HEAP);
     219      if (n>0) bubbleDown(0, _data[n], n);
     220      _data.pop_back();
     221    }
     222
     223    /// \brief Remove the given item from the heap.
     224    ///
     225    /// This function removes the given item from the heap if it is
     226    /// already stored.
     227    /// \param i The item to delete.
     228    /// \pre \e i must be in the heap.
    227229    void erase(const Item &i) {
    228       int h = iim[i];
    229       int n = data.size()-1;
    230       iim.set(data[h].first, POST_HEAP);
     230      int h = _iim[i];
     231      int n = _data.size()-1;
     232      _iim.set(_data[h].first, POST_HEAP);
    231233      if( h<n ) {
    232         if( less(data[parent(h)], data[n]) )
    233           bubble_down(h, data[n], n);
     234        if( less(_data[parent(h)], _data[n]) )
     235          bubbleDown(h, _data[n], n);
    234236        else
    235           bubble_up(h, data[n]);
    236       }
    237       data.pop_back();
    238     }
    239 
    240 
    241     /// \brief Returns the priority of \c i.
    242     ///
    243     /// This function returns the priority of item \c i.
    244     /// \pre \c i must be in the heap.
    245     /// \param i The item.
     237          bubbleUp(h, _data[n]);
     238      }
     239      _data.pop_back();
     240    }
     241
     242    /// \brief The priority of the given item.
     243    ///
     244    /// This function returns the priority of the given item.
     245    /// \param i The item.
     246    /// \pre \e i must be in the heap.
    246247    Prio operator[](const Item &i) const {
    247       int idx = iim[i];
    248       return data[idx].second;
    249     }
    250 
    251     /// \brief \c i gets to the heap with priority \c p independently
    252     /// if \c i was already there.
    253     ///
    254     /// This method calls \ref push(\c i, \c p) if \c i is not stored
    255     /// in the heap and sets the priority of \c i to \c p otherwise.
     248      int idx = _iim[i];
     249      return _data[idx].second;
     250    }
     251
     252    /// \brief Set the priority of an item or insert it, if it is
     253    /// not stored in the heap.
     254    ///
     255    /// This method sets the priority of the given item if it is
     256    /// already stored in the heap. Otherwise it inserts the given
     257    /// item into the heap with the given priority.
    256258    /// \param i The item.
    257259    /// \param p The priority.
    258260    void set(const Item &i, const Prio &p) {
    259       int idx = iim[i];
     261      int idx = _iim[i];
    260262      if( idx<0 )
    261263        push(i,p);
    262       else if( comp(p, data[idx].second) )
    263         bubble_up(idx, Pair(i,p));
     264      else if( _comp(p, _data[idx].second) )
     265        bubbleUp(idx, Pair(i,p));
    264266      else
    265         bubble_down(idx, Pair(i,p), data.size());
    266     }
    267 
    268     /// \brief Decreases the priority of \c i to \c p.
    269     ///
    270     /// This method decreases the priority of item \c i to \c p.
    271     /// \pre \c i must be stored in the heap with priority at least \c
    272     /// p relative to \c Compare.
     267        bubbleDown(idx, Pair(i,p), _data.size());
     268    }
     269
     270    /// \brief Decrease the priority of an item to the given value.
     271    ///
     272    /// This function decreases the priority of an item to the given value.
    273273    /// \param i The item.
    274274    /// \param p The priority.
     275    /// \pre \e i must be stored in the heap with priority at least \e p.
    275276    void decrease(const Item &i, const Prio &p) {
    276       int idx = iim[i];
    277       bubble_up(idx, Pair(i,p));
    278     }
    279 
    280     /// \brief Increases the priority of \c i to \c p.
    281     ///
    282     /// This method sets the priority of item \c i to \c p.
    283     /// \pre \c i must be stored in the heap with priority at most \c
    284     /// p relative to \c Compare.
     277      int idx = _iim[i];
     278      bubbleUp(idx, Pair(i,p));
     279    }
     280
     281    /// \brief Increase the priority of an item to the given value.
     282    ///
     283    /// This function increases the priority of an item to the given value.
    285284    /// \param i The item.
    286285    /// \param p The priority.
     286    /// \pre \e i must be stored in the heap with priority at most \e p.
    287287    void increase(const Item &i, const Prio &p) {
    288       int idx = iim[i];
    289       bubble_down(idx, Pair(i,p), data.size());
    290     }
    291 
    292     /// \brief Returns if \c item is in, has already been in, or has
    293     /// never been in the heap.
    294     ///
    295     /// This method returns PRE_HEAP if \c item has never been in the
    296     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    297     /// otherwise. In the latter case it is possible that \c item will
    298     /// get back to the heap again.
     288      int idx = _iim[i];
     289      bubbleDown(idx, Pair(i,p), _data.size());
     290    }
     291
     292    /// \brief Return the state of an item.
     293    ///
     294    /// This method returns \c PRE_HEAP if the given item has never
     295    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
     296    /// and \c POST_HEAP otherwise.
     297    /// In the latter case it is possible that the item will get back
     298    /// to the heap again.
    299299    /// \param i The item.
    300300    State state(const Item &i) const {
    301       int s = iim[i];
     301      int s = _iim[i];
    302302      if (s>=0) s=0;
    303303      return State(s);
    304304    }
    305305
    306     /// \brief Sets the state of the \c item in the heap.
    307     ///
    308     /// Sets the state of the \c item in the heap. It can be used to
    309     /// manually clear the heap when it is important to achive the
    310     /// better time complexity.
     306    /// \brief Set the state of an item in the heap.
     307    ///
     308    /// This function sets the state of the given item in the heap.
     309    /// It can be used to manually clear the heap when it is important
     310    /// to achive better time complexity.
    311311    /// \param i The item.
    312312    /// \param st The state. It should not be \c IN_HEAP.
    313313    void state(const Item& i, State st) {
    314314      switch (st) {
    315       case POST_HEAP:
    316       case PRE_HEAP:
    317         if (state(i) == IN_HEAP) erase(i);
    318         iim[i] = st;
    319         break;
    320       case IN_HEAP:
    321         break;
    322       }
    323     }
    324 
    325     /// \brief Replaces an item in the heap.
    326     ///
    327     /// The \c i item is replaced with \c j item. The \c i item should
    328     /// be in the heap, while the \c j should be out of the heap. The
    329     /// \c i item will out of the heap and \c j will be in the heap
    330     /// with the same prioriority as prevoiusly the \c i item.
     315        case POST_HEAP:
     316        case PRE_HEAP:
     317          if (state(i) == IN_HEAP) erase(i);
     318          _iim[i] = st;
     319          break;
     320        case IN_HEAP:
     321          break;
     322      }
     323    }
     324
     325    /// \brief Replace an item in the heap.
     326    ///
     327    /// This function replaces item \c i with item \c j.
     328    /// Item \c i must be in the heap, while \c j must be out of the heap.
     329    /// After calling this method, item \c i will be out of the
     330    /// heap and \c j will be in the heap with the same prioriority
     331    /// as item \c i had before.
    331332    void replace(const Item& i, const Item& j) {
    332       int idx=iim[i];
    333       iim.set(i, iim[j]);
    334       iim.set(j, idx);
    335       data[idx].first=j;
     333      int idx=_iim[i];
     334      _iim.set(i, _iim[j]);
     335      _iim.set(j, idx);
     336      _data[idx].first=j;
    336337    }
    337338
  • lemon/pairing_heap.h

    r749 r750  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2121
    2222///\file
    23 ///\ingroup auxdat
    24 ///\brief Pairing Heap implementation.
     23///\ingroup heaps
     24///\brief Pairing heap implementation.
    2525
    2626#include <vector>
     27#include <utility>
    2728#include <functional>
    2829#include <lemon/math.h>
     
    3031namespace lemon {
    3132
    32   /// \ingroup auxdat
     33  /// \ingroup heaps
    3334  ///
    3435  ///\brief Pairing Heap.
    3536  ///
    36   ///This class implements the \e Pairing \e heap data structure. A \e heap
    37   ///is a data structure for storing items with specified values called \e
    38   ///priorities in such a way that finding the item with minimum priority is
    39   ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    40   ///one can change the priority of an item, add or erase an item, etc.
     37  /// This class implements the \e pairing \e heap data structure.
     38  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4139  ///
    42   ///The methods \ref increase and \ref erase are not efficient in a Pairing
    43   ///heap. In case of many calls to these operations, it is better to use a
    44   ///\ref BinHeap "binary heap".
     40  /// The methods \ref increase() and \ref erase() are not efficient
     41  /// in a pairing heap. In case of many calls of these operations,
     42  /// it is better to use other heap structure, e.g. \ref BinHeap
     43  /// "binary heap".
    4544  ///
    46   ///\param _Prio Type of the priority of the items.
    47   ///\param _ItemIntMap A read and writable Item int map, used internally
    48   ///to handle the cross references.
    49   ///\param _Compare A class for the ordering of the priorities. The
    50   ///default is \c std::less<_Prio>.
    51   ///
    52   ///\sa BinHeap
    53   ///\sa Dijkstra
    54   ///\author Dorian Batha
    55 
     45  /// \tparam PR Type of the priorities of the items.
     46  /// \tparam IM A read-writable item map with \c int values, used
     47  /// internally to handle the cross references.
     48  /// \tparam CMP A functor class for comparing the priorities.
     49  /// The default is \c std::less<PR>.
    5650#ifdef DOXYGEN
    57   template <typename _Prio,
    58             typename _ItemIntMap,
    59             typename _Compare>
     51  template <typename PR, typename IM, typename CMP>
    6052#else
    61   template <typename _Prio,
    62             typename _ItemIntMap,
    63             typename _Compare = std::less<_Prio> >
     53  template <typename PR, typename IM, typename CMP = std::less<PR> >
    6454#endif
    6555  class PairingHeap {
    6656  public:
    67     typedef _ItemIntMap ItemIntMap;
    68     typedef _Prio Prio;
     57    /// Type of the item-int map.
     58    typedef IM ItemIntMap;
     59    /// Type of the priorities.
     60    typedef PR Prio;
     61    /// Type of the items stored in the heap.
    6962    typedef typename ItemIntMap::Key Item;
    70     typedef std::pair<Item,Prio> Pair;
    71     typedef _Compare Compare;
     63    /// Functor type for comparing the priorities.
     64    typedef CMP Compare;
     65
     66    /// \brief Type to represent the states of the items.
     67    ///
     68    /// Each item has a state associated to it. It can be "in heap",
     69    /// "pre-heap" or "post-heap". The latter two are indifferent from the
     70    /// heap's point of view, but may be useful to the user.
     71    ///
     72    /// The item-int map must be initialized in such way that it assigns
     73    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
     74    enum State {
     75      IN_HEAP = 0,    ///< = 0.
     76      PRE_HEAP = -1,  ///< = -1.
     77      POST_HEAP = -2  ///< = -2.
     78    };
    7279
    7380  private:
    7481    class store;
    7582
    76     std::vector<store> container;
    77     int minimum;
    78     ItemIntMap &iimap;
    79     Compare comp;
    80     int num_items;
     83    std::vector<store> _data;
     84    int _min;
     85    ItemIntMap &_iim;
     86    Compare _comp;
     87    int _num_items;
    8188
    8289  public:
    83     ///Status of the nodes
    84     enum State {
    85       ///The node is in the heap
    86       IN_HEAP = 0,
    87       ///The node has never been in the heap
    88       PRE_HEAP = -1,
    89       ///The node was in the heap but it got out of it
    90       POST_HEAP = -2
    91     };
    92 
    93     /// \brief The constructor
    94     ///
    95     /// \c _iimap should be given to the constructor, since it is
    96     ///   used internally to handle the cross references.
    97     explicit PairingHeap(ItemIntMap &_iimap)
    98       : minimum(0), iimap(_iimap), num_items(0) {}
    99 
    100     /// \brief The constructor
    101     ///
    102     /// \c _iimap should be given to the constructor, since it is used
    103     /// internally to handle the cross references. \c _comp is an
    104     /// object for ordering of the priorities.
    105     PairingHeap(ItemIntMap &_iimap, const Compare &_comp)
    106       : minimum(0), iimap(_iimap), comp(_comp), num_items(0) {}
     90    /// \brief Constructor.
     91    ///
     92    /// Constructor.
     93    /// \param map A map that assigns \c int values to the items.
     94    /// It is used internally to handle the cross references.
     95    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     96    explicit PairingHeap(ItemIntMap &map)
     97      : _min(0), _iim(map), _num_items(0) {}
     98
     99    /// \brief Constructor.
     100    ///
     101    /// Constructor.
     102    /// \param map A map that assigns \c int values to the items.
     103    /// It is used internally to handle the cross references.
     104    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     105    /// \param comp The function object used for comparing the priorities.
     106    PairingHeap(ItemIntMap &map, const Compare &comp)
     107      : _min(0), _iim(map), _comp(comp), _num_items(0) {}
    107108
    108109    /// \brief The number of items stored in the heap.
    109110    ///
    110     /// Returns the number of items stored in the heap.
    111     int size() const { return num_items; }
    112 
    113     /// \brief Checks if the heap stores no items.
    114     ///
    115     ///   Returns \c true if and only if the heap stores no items.
    116     bool empty() const { return num_items==0; }
    117 
    118     /// \brief Make empty this heap.
    119     ///
    120     /// Make empty this heap. It does not change the cross reference
    121     /// map.  If you want to reuse a heap what is not surely empty you
    122     /// should first clear the heap and after that you should set the
    123     /// cross reference map for each item to \c PRE_HEAP.
     111    /// This function returns the number of items stored in the heap.
     112    int size() const { return _num_items; }
     113
     114    /// \brief Check if the heap is empty.
     115    ///
     116    /// This function returns \c true if the heap is empty.
     117    bool empty() const { return _num_items==0; }
     118
     119    /// \brief Make the heap empty.
     120    ///
     121    /// This functon makes the heap empty.
     122    /// It does not change the cross reference map. If you want to reuse
     123    /// a heap that is not surely empty, you should first clear it and
     124    /// then you should set the cross reference map to \c PRE_HEAP
     125    /// for each item.
    124126    void clear() {
    125       container.clear();
    126       minimum = 0;
    127       num_items = 0;
    128     }
    129 
    130     /// \brief \c item gets to the heap with priority \c value independently
    131     /// if \c item was already there.
    132     ///
    133     /// This method calls \ref push(\c item, \c value) if \c item is not
    134     /// stored in the heap and it calls \ref decrease(\c item, \c value) or
    135     /// \ref increase(\c item, \c value) otherwise.
     127      _data.clear();
     128      _min = 0;
     129      _num_items = 0;
     130    }
     131
     132    /// \brief Set the priority of an item or insert it, if it is
     133    /// not stored in the heap.
     134    ///
     135    /// This method sets the priority of the given item if it is
     136    /// already stored in the heap. Otherwise it inserts the given
     137    /// item into the heap with the given priority.
     138    /// \param item The item.
     139    /// \param value The priority.
    136140    void set (const Item& item, const Prio& value) {
    137       int i=iimap[item];
    138       if ( i>=0 && container[i].in ) {
    139         if ( comp(value, container[i].prio) ) decrease(item, value);
    140         if ( comp(container[i].prio, value) ) increase(item, value);
     141      int i=_iim[item];
     142      if ( i>=0 && _data[i].in ) {
     143        if ( _comp(value, _data[i].prio) ) decrease(item, value);
     144        if ( _comp(_data[i].prio, value) ) increase(item, value);
    141145      } else push(item, value);
    142146    }
    143147
    144     /// \brief Adds \c item to the heap with priority \c value.
    145     ///
    146     /// Adds \c item to the heap with priority \c value.
    147     /// \pre \c item must not be stored in the heap.
     148    /// \brief Insert an item into the heap with the given priority.
     149    ///
     150    /// This function inserts the given item into the heap with the
     151    /// given priority.
     152    /// \param item The item to insert.
     153    /// \param value The priority of the item.
     154    /// \pre \e item must not be stored in the heap.
    148155    void push (const Item& item, const Prio& value) {
    149       int i=iimap[item];
     156      int i=_iim[item];
    150157      if( i<0 ) {
    151         int s=container.size();
    152         iimap.set(item, s);
     158        int s=_data.size();
     159        _iim.set(item, s);
    153160        store st;
    154161        st.name=item;
    155         container.push_back(st);
     162        _data.push_back(st);
    156163        i=s;
    157164      } else {
    158         container[i].parent=container[i].child=-1;
    159         container[i].left_child=false;
    160         container[i].degree=0;
    161         container[i].in=true;
    162       }
    163 
    164       container[i].prio=value;
    165 
    166       if ( num_items!=0 ) {
    167         if ( comp( value, container[minimum].prio) ) {
    168           fuse(i,minimum);
    169           minimum=i;
    170         }
    171         else fuse(minimum,i);
    172       }
    173       else minimum=i;
    174 
    175       ++num_items;
    176     }
    177 
    178     /// \brief Returns the item with minimum priority relative to \c Compare.
    179     ///
    180     /// This method returns the item with minimum priority relative to \c
    181     /// Compare.
    182     /// \pre The heap must be nonempty.
    183     Item top() const { return container[minimum].name; }
    184 
    185     /// \brief Returns the minimum priority relative to \c Compare.
    186     ///
    187     /// It returns the minimum priority relative to \c Compare.
    188     /// \pre The heap must be nonempty.
    189     const Prio& prio() const { return container[minimum].prio; }
    190 
    191     /// \brief Returns the priority of \c item.
    192     ///
    193     /// It returns the priority of \c item.
    194     /// \pre \c item must be in the heap.
     165        _data[i].parent=_data[i].child=-1;
     166        _data[i].left_child=false;
     167        _data[i].degree=0;
     168        _data[i].in=true;
     169      }
     170
     171      _data[i].prio=value;
     172
     173      if ( _num_items!=0 ) {
     174        if ( _comp( value, _data[_min].prio) ) {
     175          fuse(i,_min);
     176          _min=i;
     177        }
     178        else fuse(_min,i);
     179      }
     180      else _min=i;
     181
     182      ++_num_items;
     183    }
     184
     185    /// \brief Return the item having minimum priority.
     186    ///
     187    /// This function returns the item having minimum priority.
     188    /// \pre The heap must be non-empty.
     189    Item top() const { return _data[_min].name; }
     190
     191    /// \brief The minimum priority.
     192    ///
     193    /// This function returns the minimum priority.
     194    /// \pre The heap must be non-empty.
     195    const Prio& prio() const { return _data[_min].prio; }
     196
     197    /// \brief The priority of the given item.
     198    ///
     199    /// This function returns the priority of the given item.
     200    /// \param item The item.
     201    /// \pre \e item must be in the heap.
    195202    const Prio& operator[](const Item& item) const {
    196       return container[iimap[item]].prio;
    197     }
    198 
    199     /// \brief Deletes the item with minimum priority relative to \c Compare.
    200     ///
    201     /// This method deletes the item with minimum priority relative to \c
    202     /// Compare from the heap.
     203      return _data[_iim[item]].prio;
     204    }
     205
     206    /// \brief Remove the item having minimum priority.
     207    ///
     208    /// This function removes the item having minimum priority.
    203209    /// \pre The heap must be non-empty.
    204210    void pop() {
    205       int TreeArray[num_items];
     211      int TreeArray[_num_items];
    206212      int i=0, num_child=0, child_right = 0;
    207       container[minimum].in=false;
    208 
    209       if( -1!=container[minimum].child ) {
    210         i=container[minimum].child;
     213      _data[_min].in=false;
     214
     215      if( -1!=_data[_min].child ) {
     216        i=_data[_min].child;
    211217        TreeArray[num_child] = i;
    212         container[i].parent = -1;
    213         container[minimum].child = -1;
     218        _data[i].parent = -1;
     219        _data[_min].child = -1;
    214220
    215221        ++num_child;
    216222        int ch=-1;
    217         while( container[i].child!=-1 ) {
    218           ch=container[i].child;
    219           if( container[ch].left_child && i==container[ch].parent ) {
     223        while( _data[i].child!=-1 ) {
     224          ch=_data[i].child;
     225          if( _data[ch].left_child && i==_data[ch].parent ) {
    220226            i=ch;
    221227            //break;
    222228          } else {
    223             if( container[ch].left_child ) {
    224               child_right=container[ch].parent;
    225               container[ch].parent = i;
    226               --container[i].degree;
     229            if( _data[ch].left_child ) {
     230              child_right=_data[ch].parent;
     231              _data[ch].parent = i;
     232              --_data[i].degree;
    227233            }
    228234            else {
    229235              child_right=ch;
    230               container[i].child=-1;
    231               container[i].degree=0;
     236              _data[i].child=-1;
     237              _data[i].degree=0;
    232238            }
    233             container[child_right].parent = -1;
     239            _data[child_right].parent = -1;
    234240            TreeArray[num_child] = child_right;
    235241            i = child_right;
     
    240246        int other;
    241247        for( i=0; i<num_child-1; i+=2 ) {
    242           if ( !comp(container[TreeArray[i]].prio,
    243                      container[TreeArray[i+1]].prio) ) {
     248          if ( !_comp(_data[TreeArray[i]].prio,
     249                     _data[TreeArray[i+1]].prio) ) {
    244250            other=TreeArray[i];
    245251            TreeArray[i]=TreeArray[i+1];
     
    251257        i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
    252258        while(i>=2) {
    253           if ( comp(container[TreeArray[i]].prio,
    254                     container[TreeArray[i-2]].prio) ) {
     259          if ( _comp(_data[TreeArray[i]].prio,
     260                    _data[TreeArray[i-2]].prio) ) {
    255261            other=TreeArray[i];
    256262            TreeArray[i]=TreeArray[i-2];
     
    260266          i-=2;
    261267        }
    262         minimum = TreeArray[0];
     268        _min = TreeArray[0];
    263269      }
    264270
    265271      if ( 0==num_child ) {
    266         minimum = container[minimum].child;
    267       }
    268 
    269       if (minimum >= 0) container[minimum].left_child = false;
    270 
    271       --num_items;
    272     }
    273 
    274     /// \brief Deletes \c item from the heap.
    275     ///
    276     /// This method deletes \c item from the heap, if \c item was already
    277     /// stored in the heap. It is quite inefficient in Pairing heaps.
     272        _min = _data[_min].child;
     273      }
     274
     275      if (_min >= 0) _data[_min].left_child = false;
     276
     277      --_num_items;
     278    }
     279
     280    /// \brief Remove the given item from the heap.
     281    ///
     282    /// This function removes the given item from the heap if it is
     283    /// already stored.
     284    /// \param item The item to delete.
     285    /// \pre \e item must be in the heap.
    278286    void erase (const Item& item) {
    279       int i=iimap[item];
    280       if ( i>=0 && container[i].in ) {
    281         decrease( item, container[minimum].prio-1 );
     287      int i=_iim[item];
     288      if ( i>=0 && _data[i].in ) {
     289        decrease( item, _data[_min].prio-1 );
    282290        pop();
    283291      }
    284292    }
    285293
    286     /// \brief Decreases the priority of \c item to \c value.
    287     ///
    288     /// This method decreases the priority of \c item to \c value.
    289     /// \pre \c item must be stored in the heap with priority at least \c
    290     ///   value relative to \c Compare.
     294    /// \brief Decrease the priority of an item to the given value.
     295    ///
     296    /// This function decreases the priority of an item to the given value.
     297    /// \param item The item.
     298    /// \param value The priority.
     299    /// \pre \e item must be stored in the heap with priority at least \e value.
    291300    void decrease (Item item, const Prio& value) {
    292       int i=iimap[item];
    293       container[i].prio=value;
    294       int p=container[i].parent;
    295 
    296       if( container[i].left_child && i!=container[p].child ) {
    297         p=container[p].parent;
    298       }
    299 
    300       if ( p!=-1 && comp(value,container[p].prio) ) {
     301      int i=_iim[item];
     302      _data[i].prio=value;
     303      int p=_data[i].parent;
     304
     305      if( _data[i].left_child && i!=_data[p].child ) {
     306        p=_data[p].parent;
     307      }
     308
     309      if ( p!=-1 && _comp(value,_data[p].prio) ) {
    301310        cut(i,p);
    302         if ( comp(container[minimum].prio,value) ) {
    303           fuse(minimum,i);
     311        if ( _comp(_data[_min].prio,value) ) {
     312          fuse(_min,i);
    304313        } else {
    305           fuse(i,minimum);
    306           minimum=i;
    307         }
    308       }
    309     }
    310 
    311     /// \brief Increases the priority of \c item to \c value.
    312     ///
    313     /// This method sets the priority of \c item to \c value. Though
    314     /// there is no precondition on the priority of \c item, this
    315     /// method should be used only if it is indeed necessary to increase
    316     /// (relative to \c Compare) the priority of \c item, because this
    317     /// method is inefficient.
     314          fuse(i,_min);
     315          _min=i;
     316        }
     317      }
     318    }
     319
     320    /// \brief Increase the priority of an item to the given value.
     321    ///
     322    /// This function increases the priority of an item to the given value.
     323    /// \param item The item.
     324    /// \param value The priority.
     325    /// \pre \e item must be stored in the heap with priority at most \e value.
    318326    void increase (Item item, const Prio& value) {
    319327      erase(item);
     
    321329    }
    322330
    323     /// \brief Returns if \c item is in, has already been in, or has never
    324     /// been in the heap.
    325     ///
    326     /// This method returns PRE_HEAP if \c item has never been in the
    327     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    328     /// otherwise. In the latter case it is possible that \c item will
    329     /// get back to the heap again.
     331    /// \brief Return the state of an item.
     332    ///
     333    /// This method returns \c PRE_HEAP if the given item has never
     334    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
     335    /// and \c POST_HEAP otherwise.
     336    /// In the latter case it is possible that the item will get back
     337    /// to the heap again.
     338    /// \param item The item.
    330339    State state(const Item &item) const {
    331       int i=iimap[item];
     340      int i=_iim[item];
    332341      if( i>=0 ) {
    333         if( container[i].in ) i=0;
     342        if( _data[i].in ) i=0;
    334343        else i=-2;
    335344      }
     
    337346    }
    338347
    339     /// \brief Sets the state of the \c item in the heap.
    340     ///
    341     /// Sets the state of the \c item in the heap. It can be used to
    342     /// manually clear the heap when it is important to achive the
    343     /// better time complexity.
     348    /// \brief Set the state of an item in the heap.
     349    ///
     350    /// This function sets the state of the given item in the heap.
     351    /// It can be used to manually clear the heap when it is important
     352    /// to achive better time complexity.
    344353    /// \param i The item.
    345354    /// \param st The state. It should not be \c IN_HEAP.
     
    349358      case PRE_HEAP:
    350359        if (state(i) == IN_HEAP) erase(i);
    351         iimap[i]=st;
     360        _iim[i]=st;
    352361        break;
    353362      case IN_HEAP:
     
    360369    void cut(int a, int b) {
    361370      int child_a;
    362       switch (container[a].degree) {
     371      switch (_data[a].degree) {
    363372        case 2:
    364           child_a = container[container[a].child].parent;
    365           if( container[a].left_child ) {
    366             container[child_a].left_child=true;
    367             container[b].child=child_a;
    368             container[child_a].parent=container[a].parent;
     373          child_a = _data[_data[a].child].parent;
     374          if( _data[a].left_child ) {
     375            _data[child_a].left_child=true;
     376            _data[b].child=child_a;
     377            _data[child_a].parent=_data[a].parent;
    369378          }
    370379          else {
    371             container[child_a].left_child=false;
    372             container[child_a].parent=b;
    373             if( a!=container[b].child )
    374               container[container[b].child].parent=child_a;
     380            _data[child_a].left_child=false;
     381            _data[child_a].parent=b;
     382            if( a!=_data[b].child )
     383              _data[_data[b].child].parent=child_a;
    375384            else
    376               container[b].child=child_a;
    377           }
    378           --container[a].degree;
    379           container[container[a].child].parent=a;
     385              _data[b].child=child_a;
     386          }
     387          --_data[a].degree;
     388          _data[_data[a].child].parent=a;
    380389          break;
    381390
    382391        case 1:
    383           child_a = container[a].child;
    384           if( !container[child_a].left_child ) {
    385             --container[a].degree;
    386             if( container[a].left_child ) {
    387               container[child_a].left_child=true;
    388               container[child_a].parent=container[a].parent;
    389               container[b].child=child_a;
     392          child_a = _data[a].child;
     393          if( !_data[child_a].left_child ) {
     394            --_data[a].degree;
     395            if( _data[a].left_child ) {
     396              _data[child_a].left_child=true;
     397              _data[child_a].parent=_data[a].parent;
     398              _data[b].child=child_a;
    390399            }
    391400            else {
    392               container[child_a].left_child=false;
    393               container[child_a].parent=b;
    394               if( a!=container[b].child )
    395                 container[container[b].child].parent=child_a;
     401              _data[child_a].left_child=false;
     402              _data[child_a].parent=b;
     403              if( a!=_data[b].child )
     404                _data[_data[b].child].parent=child_a;
    396405              else
    397                 container[b].child=child_a;
     406                _data[b].child=child_a;
    398407            }
    399             container[a].child=-1;
     408            _data[a].child=-1;
    400409          }
    401410          else {
    402             --container[b].degree;
    403             if( container[a].left_child ) {
    404               container[b].child =
    405                 (1==container[b].degree) ? container[a].parent : -1;
     411            --_data[b].degree;
     412            if( _data[a].left_child ) {
     413              _data[b].child =
     414                (1==_data[b].degree) ? _data[a].parent : -1;
    406415            } else {
    407               if (1==container[b].degree)
    408                 container[container[b].child].parent=b;
     416              if (1==_data[b].degree)
     417                _data[_data[b].child].parent=b;
    409418              else
    410                 container[b].child=-1;
     419                _data[b].child=-1;
    411420            }
    412421          }
     
    414423
    415424        case 0:
    416           --container[b].degree;
    417           if( container[a].left_child ) {
    418             container[b].child =
    419               (0!=container[b].degree) ? container[a].parent : -1;
     425          --_data[b].degree;
     426          if( _data[a].left_child ) {
     427            _data[b].child =
     428              (0!=_data[b].degree) ? _data[a].parent : -1;
    420429          } else {
    421             if( 0!=container[b].degree )
    422               container[container[b].child].parent=b;
     430            if( 0!=_data[b].degree )
     431              _data[_data[b].child].parent=b;
    423432            else
    424               container[b].child=-1;
     433              _data[b].child=-1;
    425434          }
    426435          break;
    427436      }
    428       container[a].parent=-1;
    429       container[a].left_child=false;
     437      _data[a].parent=-1;
     438      _data[a].left_child=false;
    430439    }
    431440
    432441    void fuse(int a, int b) {
    433       int child_a = container[a].child;
    434       int child_b = container[b].child;
    435       container[a].child=b;
    436       container[b].parent=a;
    437       container[b].left_child=true;
     442      int child_a = _data[a].child;
     443      int child_b = _data[b].child;
     444      _data[a].child=b;
     445      _data[b].parent=a;
     446      _data[b].left_child=true;
    438447
    439448      if( -1!=child_a ) {
    440         container[b].child=child_a;
    441         container[child_a].parent=b;
    442         container[child_a].left_child=false;
    443         ++container[b].degree;
     449        _data[b].child=child_a;
     450        _data[child_a].parent=b;
     451        _data[child_a].left_child=false;
     452        ++_data[b].degree;
    444453
    445454        if( -1!=child_b ) {
    446            container[b].child=child_b;
    447            container[child_b].parent=child_a;
    448         }
    449       }
    450       else { ++container[a].degree; }
     455           _data[b].child=child_b;
     456           _data[child_b].parent=child_a;
     457        }
     458      }
     459      else { ++_data[a].degree; }
    451460    }
    452461
Note: See TracChangeset for help on using the changeset viewer.