COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/bucket_heap.h

    r758 r730  
    2020#define LEMON_BUCKET_HEAP_H
    2121
    22 ///\ingroup heaps
     22///\ingroup auxdat
    2323///\file
    24 ///\brief Bucket heap implementation.
     24///\brief Bucket Heap implementation.
    2525
    2626#include <vector>
    … …  
    5454  }
    5555
    56   /// \ingroup heaps
    57   ///
    58   /// \brief Bucket heap data structure.
    59   ///
    60   /// This class implements the \e bucket \e heap data structure.
    61   /// It practically conforms to the \ref concepts::Heap "heap concept",
    62   /// but it has some limitations.
    63   ///
    64   /// The bucket heap is a very simple structure. It can store only
    65   /// \c int priorities and it maintains a list of items for each priority
    66   /// in the range <tt>[0..C)</tt>. So it should only be used when the
    67   /// priorities are small. It is not intended to use as a Dijkstra heap.
    68   ///
    69   /// \tparam IM A read-writable item map with \c int values, used
    70   /// internally to handle the cross references.
    71   /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
    72   /// The default is \e min-heap. If this parameter is set to \c false,
    73   /// then the comparison is reversed, so the top(), prio() and pop()
    74   /// functions deal with the item having maximum priority instead of the
    75   /// minimum.
    76   ///
    77   /// \sa SimpleBucketHeap
     56  /// \ingroup auxdat
     57  ///
     58  /// \brief A Bucket Heap implementation.
     59  ///
     60  /// This class implements the \e bucket \e heap data structure. A \e heap
     61  /// is a data structure for storing items with specified values called \e
     62  /// priorities in such a way that finding the item with minimum priority is
     63  /// efficient. The bucket heap is very simple implementation, it can store
     64  /// only integer priorities and it stores for each priority in the
     65  /// \f$ [0..C) \f$ range a list of items. So it should be used only when
     66  /// the priorities are small. It is not intended to use as dijkstra heap.
     67  ///
     68  /// \param IM A read and write Item int map, used internally
     69  /// to handle the cross references.
     70  /// \param MIN If the given parameter is false then instead of the
     71  /// minimum value the maximum can be retrivied with the top() and
     72  /// prio() member functions.
    7873  template <typename IM, bool MIN = true>
    7974  class BucketHeap {
    8075
    8176  public:
    82 
    83     /// Type of the item-int map.
     77    /// \e
     78    typedef typename IM::Key Item;
     79    /// \e
     80    typedef int Prio;
     81    /// \e
     82    typedef std::pair<Item, Prio> Pair;
     83    /// \e
    8484    typedef IM ItemIntMap;
    85     /// Type of the priorities.
    86     typedef int Prio;
    87     /// Type of the items stored in the heap.
    88     typedef typename ItemIntMap::Key Item;
    89     /// Type of the item-priority pairs.
    90     typedef std::pair<Item,Prio> Pair;
    9185
    9286  private:
    … …  
    9690  public:
    9791
    98     /// \brief Type to represent the states of the items.
    99     ///
    100     /// Each item has a state associated to it. It can be "in heap",
    101     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     92    /// \brief Type to represent the items states.
     93    ///
     94    /// Each Item element have a state associated to it. It may be "in heap",
     95    /// "pre heap" or "post heap". The latter two are indifferent from the
    10296    /// heap's point of view, but may be useful to the user.
    10397    ///
    … …  
    111105
    112106  public:
    113 
    114     /// \brief Constructor.
    115     ///
    116     /// Constructor.
    117     /// \param map A map that assigns \c int values to the items.
    118     /// It is used internally to handle the cross references.
    119     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     107    /// \brief The constructor.
     108    ///
     109    /// The constructor.
     110    /// \param map should be given to the constructor, since it is used
     111    /// internally to handle the cross references. The value of the map
     112    /// should be PRE_HEAP (-1) for each element.
    120113    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
    121114
    122     /// \brief The number of items stored in the heap.
    123     ///
    124     /// This function returns the number of items stored in the heap.
     115    /// The number of items stored in the heap.
     116    ///
     117    /// \brief Returns the number of items stored in the heap.
    125118    int size() const { return _data.size(); }
    126119
    127     /// \brief Check if the heap is empty.
    128     ///
    129     /// This function returns \c true if the heap is empty.
     120    /// \brief Checks if the heap stores no items.
     121    ///
     122    /// Returns \c true if and only if the heap stores no items.
    130123    bool empty() const { return _data.empty(); }
    131124
    132     /// \brief Make the heap empty.
    133     ///
    134     /// This functon makes the heap empty.
    135     /// It does not change the cross reference map. If you want to reuse
    136     /// a heap that is not surely empty, you should first clear it and
    137     /// then you should set the cross reference map to \c PRE_HEAP
    138     /// for each item.
     125    /// \brief Make empty this heap.
     126    ///
     127    /// Make empty this heap. It does not change the cross reference
     128    /// map.  If you want to reuse a heap what is not surely empty you
     129    /// should first clear the heap and after that you should set the
     130    /// cross reference map for each item to \c PRE_HEAP.
    139131    void clear() {
    140132      _data.clear(); _first.clear(); _minimum = 0;
    … …  
    143135  private:
    144136
    145     void relocateLast(int idx) {
     137    void relocate_last(int idx) {
    146138      if (idx + 1 < int(_data.size())) {
    147139        _data[idx] = _data.back();
    … …  
    183175
    184176  public:
    185 
    186177    /// \brief Insert a pair of item and priority into the heap.
    187178    ///
    188     /// This function inserts \c p.first to the heap with priority
    189     /// \c p.second.
     179    /// Adds \c p.first to the heap with priority \c p.second.
    190180    /// \param p The pair to insert.
    191     /// \pre \c p.first must not be stored in the heap.
    192181    void push(const Pair& p) {
    193182      push(p.first, p.second);
    … …  
    196185    /// \brief Insert an item into the heap with the given priority.
    197186    ///
    198     /// This function inserts the given item into the heap with the
    199     /// given priority.
     187    /// Adds \c i to the heap with priority \c p.
    200188    /// \param i The item to insert.
    201189    /// \param p The priority of the item.
    202     /// \pre \e i must not be stored in the heap.
    203190    void push(const Item &i, const Prio &p) {
    204191      int idx = _data.size();
    … …  
    211198    }
    212199
    213     /// \brief Return the item having minimum priority.
    214     ///
    215     /// This function returns the item having minimum priority.
    216     /// \pre The heap must be non-empty.
     200    /// \brief Returns the item with minimum priority.
     201    ///
     202    /// This method returns the item with minimum priority.
     203    /// \pre The heap must be nonempty.
    217204    Item top() const {
    218205      while (_first[_minimum] == -1) {
    … …  
    222209    }
    223210
    224     /// \brief The minimum priority.
    225     ///
    226     /// This function returns the minimum priority.
    227     /// \pre The heap must be non-empty.
     211    /// \brief Returns the minimum priority.
     212    ///
     213    /// It returns the minimum priority.
     214    /// \pre The heap must be nonempty.
    228215    Prio prio() const {
    229216      while (_first[_minimum] == -1) {
    … …  
    233220    }
    234221
    235     /// \brief Remove the item having minimum priority.
    236     ///
    237     /// This function removes the item having minimum priority.
     222    /// \brief Deletes the item with minimum priority.
     223    ///
     224    /// This method deletes the item with minimum priority from the heap.
    238225    /// \pre The heap must be non-empty.
    239226    void pop() {
    … …  
    244231      _iim[_data[idx].item] = -2;
    245232      unlace(idx);
    246       relocateLast(idx);
    247     }
    248 
    249     /// \brief Remove the given item from the heap.
    250     ///
    251     /// This function removes the given item from the heap if it is
    252     /// already stored.
    253     /// \param i The item to delete.
    254     /// \pre \e i must be in the heap.
     233      relocate_last(idx);
     234    }
     235
     236    /// \brief Deletes \c i from the heap.
     237    ///
     238    /// This method deletes item \c i from the heap, if \c i was
     239    /// already stored in the heap.
     240    /// \param i The item to erase.
    255241    void erase(const Item &i) {
    256242      int idx = _iim[i];
    257243      _iim[_data[idx].item] = -2;
    258244      unlace(idx);
    259       relocateLast(idx);
    260     }
    261 
    262     /// \brief The priority of the given item.
    263     ///
    264     /// This function returns the priority of the given item.
    265     /// \param i The item.
    266     /// \pre \e i must be in the heap.
     245      relocate_last(idx);
     246    }
     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.
    267254    Prio operator[](const Item &i) const {
    268255      int idx = _iim[i];
    … …  
    270257    }
    271258
    272     /// \brief Set the priority of an item or insert it, if it is
    273     /// not stored in the heap.
    274     ///
    275     /// This method sets the priority of the given item if it is
    276     /// already stored in the heap. Otherwise it inserts the given
    277     /// item into the heap with the given priority.
     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.
    278264    /// \param i The item.
    279265    /// \param p The priority.
    … …  
    289275    }
    290276
    291     /// \brief Decrease the priority of an item to the given value.
    292     ///
    293     /// This function decreases the priority of an item to the given value.
     277    /// \brief Decreases the priority of \c i to \c p.
     278    ///
     279    /// This method decreases the priority of item \c i to \c p.
     280    /// \pre \c i must be stored in the heap with priority at least \c
     281    /// p relative to \c Compare.
    294282    /// \param i The item.
    295283    /// \param p The priority.
    296     /// \pre \e i must be stored in the heap with priority at least \e p.
    297284    void decrease(const Item &i, const Prio &p) {
    298285      int idx = _iim[i];
    … …  
    305292    }
    306293
    307     /// \brief Increase the priority of an item to the given value.
    308     ///
    309     /// This function increases the priority of an item to the given value.
     294    /// \brief Increases the priority of \c i to \c p.
     295    ///
     296    /// This method sets the priority of item \c i to \c p.
     297    /// \pre \c i must be stored in the heap with priority at most \c
     298    /// p relative to \c Compare.
    310299    /// \param i The item.
    311300    /// \param p The priority.
    312     /// \pre \e i must be stored in the heap with priority at most \e p.
    313301    void increase(const Item &i, const Prio &p) {
    314302      int idx = _iim[i];
    … …  
    318306    }
    319307
    320     /// \brief Return the state of an item.
    321     ///
    322     /// This method returns \c PRE_HEAP if the given item has never
    323     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    324     /// and \c POST_HEAP otherwise.
    325     /// In the latter case it is possible that the item will get back
    326     /// to the heap again.
     308    /// \brief Returns if \c item is in, has already been in, or has
     309    /// never been in the heap.
     310    ///
     311    /// This method returns PRE_HEAP if \c item has never been in the
     312    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     313    /// otherwise. In the latter case it is possible that \c item will
     314    /// get back to the heap again.
    327315    /// \param i The item.
    328316    State state(const Item &i) const {
    … …  
    332320    }
    333321
    334     /// \brief Set the state of an item in the heap.
    335     ///
    336     /// This function sets the state of the given item in the heap.
    337     /// It can be used to manually clear the heap when it is important
    338     /// to achive better time complexity.
     322    /// \brief Sets the state of the \c item in the heap.
     323    ///
     324    /// Sets the state of the \c item in the heap. It can be used to
     325    /// manually clear the heap when it is important to achive the
     326    /// better time complexity.
    339327    /// \param i The item.
    340328    /// \param st The state. It should not be \c IN_HEAP.
    … …  
    372360  }; // class BucketHeap
    373361
    374   /// \ingroup heaps
    375   ///
    376   /// \brief Simplified bucket heap data structure.
     362  /// \ingroup auxdat
     363  ///
     364  /// \brief A Simplified Bucket Heap implementation.
    377365  ///
    378366  /// This class implements a simplified \e bucket \e heap data
    379   /// structure. It does not provide some functionality, but it is
    380   /// faster and simpler than BucketHeap. The main difference is
    381   /// that BucketHeap stores a doubly-linked list for each key while
    382   /// this class stores only simply-linked lists. It supports erasing
    383   /// only for the item having minimum priority and it does not support
    384   /// key increasing and decreasing.
    385   ///
    386   /// Note that this implementation does not conform to the
    387   /// \ref concepts::Heap "heap concept" due to the lack of some
    388   /// functionality.
    389   ///
    390   /// \tparam IM A read-writable item map with \c int values, used
    391   /// internally to handle the cross references.
    392   /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
    393   /// The default is \e min-heap. If this parameter is set to \c false,
    394   /// then the comparison is reversed, so the top(), prio() and pop()
    395   /// functions deal with the item having maximum priority instead of the
    396   /// minimum.
     367  /// structure.  It does not provide some functionality but it faster
     368  /// and simplier data structure than the BucketHeap. The main
     369  /// difference is that the BucketHeap stores for every key a double
     370  /// linked list while this class stores just simple lists. In the
     371  /// other way it does not support erasing each elements just the
     372  /// minimal and it does not supports key increasing, decreasing.
     373  ///
     374  /// \param IM A read and write Item int map, used internally
     375  /// to handle the cross references.
     376  /// \param MIN If the given parameter is false then instead of the
     377  /// minimum value the maximum can be retrivied with the top() and
     378  /// prio() member functions.
    397379  ///
    398380  /// \sa BucketHeap
    … …  
    401383
    402384  public:
    403 
    404     /// Type of the item-int map.
     385    typedef typename IM::Key Item;
     386    typedef int Prio;
     387    typedef std::pair<Item, Prio> Pair;
    405388    typedef IM ItemIntMap;
    406     /// Type of the priorities.
    407     typedef int Prio;
    408     /// Type of the items stored in the heap.
    409     typedef typename ItemIntMap::Key Item;
    410     /// Type of the item-priority pairs.
    411     typedef std::pair<Item,Prio> Pair;
    412389
    413390  private:
    … …  
    417394  public:
    418395
    419     /// \brief Type to represent the states of the items.
    420     ///
    421     /// Each item has a state associated to it. It can be "in heap",
    422     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     396    /// \brief Type to represent the items states.
     397    ///
     398    /// Each Item element have a state associated to it. It may be "in heap",
     399    /// "pre heap" or "post heap". The latter two are indifferent from the
    423400    /// heap's point of view, but may be useful to the user.
    424401    ///
    … …  
    433410  public:
    434411
    435     /// \brief Constructor.
    436     ///
    437     /// Constructor.
    438     /// \param map A map that assigns \c int values to the items.
    439     /// It is used internally to handle the cross references.
    440     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     412    /// \brief The constructor.
     413    ///
     414    /// The constructor.
     415    /// \param map should be given to the constructor, since it is used
     416    /// internally to handle the cross references. The value of the map
     417    /// should be PRE_HEAP (-1) for each element.
    441418    explicit SimpleBucketHeap(ItemIntMap &map)
    442419      : _iim(map), _free(-1), _num(0), _minimum(0) {}
    443420
    444     /// \brief The number of items stored in the heap.
    445     ///
    446     /// This function returns the number of items stored in the heap.
     421    /// \brief Returns the number of items stored in the heap.
     422    ///
     423    /// The number of items stored in the heap.
    447424    int size() const { return _num; }
    448425
    449     /// \brief Check if the heap is empty.
    450     ///
    451     /// This function returns \c true if the heap is empty.
     426    /// \brief Checks if the heap stores no items.
     427    ///
     428    /// Returns \c true if and only if the heap stores no items.
    452429    bool empty() const { return _num == 0; }
    453430
    454     /// \brief Make the heap empty.
    455     ///
    456     /// This functon makes the heap empty.
    457     /// It does not change the cross reference map. If you want to reuse
    458     /// a heap that is not surely empty, you should first clear it and
    459     /// then you should set the cross reference map to \c PRE_HEAP
    460     /// for each item.
     431    /// \brief Make empty this heap.
     432    ///
     433    /// Make empty this heap. It does not change the cross reference
     434    /// map.  If you want to reuse a heap what is not surely empty you
     435    /// should first clear the heap and after that you should set the
     436    /// cross reference map for each item to \c PRE_HEAP.
    461437    void clear() {
    462438      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
    … …  
    465441    /// \brief Insert a pair of item and priority into the heap.
    466442    ///
    467     /// This function inserts \c p.first to the heap with priority
    468     /// \c p.second.
     443    /// Adds \c p.first to the heap with priority \c p.second.
    469444    /// \param p The pair to insert.
    470     /// \pre \c p.first must not be stored in the heap.
    471445    void push(const Pair& p) {
    472446      push(p.first, p.second);
    … …  
    475449    /// \brief Insert an item into the heap with the given priority.
    476450    ///
    477     /// This function inserts the given item into the heap with the
    478     /// given priority.
     451    /// Adds \c i to the heap with priority \c p.
    479452    /// \param i The item to insert.
    480453    /// \param p The priority of the item.
    481     /// \pre \e i must not be stored in the heap.
    482454    void push(const Item &i, const Prio &p) {
    483455      int idx;
    … …  
    500472    }
    501473
    502     /// \brief Return the item having minimum priority.
    503     ///
    504     /// This function returns the item having minimum priority.
    505     /// \pre The heap must be non-empty.
     474    /// \brief Returns the item with minimum priority.
     475    ///
     476    /// This method returns the item with minimum priority.
     477    /// \pre The heap must be nonempty.
    506478    Item top() const {
    507479      while (_first[_minimum] == -1) {
    … …  
    511483    }
    512484
    513     /// \brief The minimum priority.
    514     ///
    515     /// This function returns the minimum priority.
    516     /// \pre The heap must be non-empty.
     485    /// \brief Returns the minimum priority.
     486    ///
     487    /// It returns the minimum priority.
     488    /// \pre The heap must be nonempty.
    517489    Prio prio() const {
    518490      while (_first[_minimum] == -1) {
    … …  
    522494    }
    523495
    524     /// \brief Remove the item having minimum priority.
    525     ///
    526     /// This function removes the item having minimum priority.
     496    /// \brief Deletes the item with minimum priority.
     497    ///
     498    /// This method deletes the item with minimum priority from the heap.
    527499    /// \pre The heap must be non-empty.
    528500    void pop() {
    … …  
    538510    }
    539511
    540     /// \brief The priority of the given item.
    541     ///
    542     /// This function returns the priority of the given item.
    543     /// \param i The item.
    544     /// \pre \e i must be in the heap.
    545     /// \warning This operator is not a constant time function because
    546     /// it scans the whole data structure to find the proper value.
     512    /// \brief Returns the priority of \c i.
     513    ///
     514    /// This function returns the priority of item \c i.
     515    /// \warning This operator is not a constant time function
     516    /// because it scans the whole data structure to find the proper
     517    /// value.
     518    /// \pre \c i must be in the heap.
     519    /// \param i The item.
    547520    Prio operator[](const Item &i) const {
    548       for (int k = 0; k < int(_first.size()); ++k) {
     521      for (int k = 0; k < _first.size(); ++k) {
    549522        int idx = _first[k];
    550523        while (idx != -1) {
    … …  
    558531    }
    559532
    560     /// \brief Return the state of an item.
    561     ///
    562     /// This method returns \c PRE_HEAP if the given item has never
    563     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    564     /// and \c POST_HEAP otherwise.
    565     /// In the latter case it is possible that the item will get back
    566     /// to the heap again.
     533    /// \brief Returns if \c item is in, has already been in, or has
     534    /// never been in the heap.
     535    ///
     536    /// This method returns PRE_HEAP if \c item has never been in the
     537    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     538    /// otherwise. In the latter case it is possible that \c item will
     539    /// get back to the heap again.
    567540    /// \param i The item.
    568541    State state(const Item &i) const {
Note: See TracChangeset for help on using the changeset viewer.