COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 703:bb3392fe91f2 in lemon-1.2 for lemon/fourary_heap.h


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)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/fourary_heap.h

    r701 r703  
    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
Note: See TracChangeset for help on using the changeset viewer.