COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 756:0747f332c478 in lemon for lemon/bucket_heap.h


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

Improve and unify the documentation of heaps (#299)
and avoid a warning in SimpleBucketHeap::operator[].

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/bucket_heap.h

    r730 r756  
    2222///\ingroup auxdat
    2323///\file
    24 ///\brief Bucket Heap implementation.
     24///\brief Bucket heap implementation.
    2525
    2626#include <vector>
    … …  
    5656  /// \ingroup auxdat
    5757  ///
    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.
     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
    7378  template <typename IM, bool MIN = true>
    7479  class BucketHeap {
    7580
    7681  public:
    77     /// \e
    78     typedef typename IM::Key Item;
    79     /// \e
     82
     83    /// Type of the item-int map.
     84    typedef IM ItemIntMap;
     85    /// Type of the priorities.
    8086    typedef int Prio;
    81     /// \e
    82     typedef std::pair<Item, Prio> Pair;
    83     /// \e
    84     typedef IM ItemIntMap;
     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;
    8591
    8692  private:
    … …  
    9096  public:
    9197
    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
     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
    96102    /// heap's point of view, but may be useful to the user.
    97103    ///
    … …  
    105111
    106112  public:
    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.
     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.
    113120    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
    114121
    115     /// The number of items stored in the heap.
    116     ///
    117     /// \brief Returns the number of items stored in the heap.
     122    /// \brief The number of items stored in the heap.
     123    ///
     124    /// This function returns the number of items stored in the heap.
    118125    int size() const { return _data.size(); }
    119126
    120     /// \brief Checks if the heap stores no items.
    121     ///
    122     /// Returns \c true if and only if the heap stores no items.
     127    /// \brief Check if the heap is empty.
     128    ///
     129    /// This function returns \c true if the heap is empty.
    123130    bool empty() const { return _data.empty(); }
    124131
    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.
     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.
    131139    void clear() {
    132140      _data.clear(); _first.clear(); _minimum = 0;
    … …  
    175183
    176184  public:
     185
    177186    /// \brief Insert a pair of item and priority into the heap.
    178187    ///
    179     /// Adds \c p.first to the heap with priority \c p.second.
     188    /// This function inserts \c p.first to the heap with priority
     189    /// \c p.second.
    180190    /// \param p The pair to insert.
     191    /// \pre \c p.first must not be stored in the heap.
    181192    void push(const Pair& p) {
    182193      push(p.first, p.second);
    … …  
    185196    /// \brief Insert an item into the heap with the given priority.
    186197    ///
    187     /// Adds \c i to the heap with priority \c p.
     198    /// This function inserts the given item into the heap with the
     199    /// given priority.
    188200    /// \param i The item to insert.
    189201    /// \param p The priority of the item.
     202    /// \pre \e i must not be stored in the heap.
    190203    void push(const Item &i, const Prio &p) {
    191204      int idx = _data.size();
    … …  
    198211    }
    199212
    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.
     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.
    204217    Item top() const {
    205218      while (_first[_minimum] == -1) {
    … …  
    209222    }
    210223
    211     /// \brief Returns the minimum priority.
    212     ///
    213     /// It returns the minimum priority.
    214     /// \pre The heap must be nonempty.
     224    /// \brief The minimum priority.
     225    ///
     226    /// This function returns the minimum priority.
     227    /// \pre The heap must be non-empty.
    215228    Prio prio() const {
    216229      while (_first[_minimum] == -1) {
    … …  
    220233    }
    221234
    222     /// \brief Deletes the item with minimum priority.
    223     ///
    224     /// This method deletes the item with minimum priority from the heap.
     235    /// \brief Remove the item having minimum priority.
     236    ///
     237    /// This function removes the item having minimum priority.
    225238    /// \pre The heap must be non-empty.
    226239    void pop() {
    … …  
    234247    }
    235248
    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.
     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.
    241255    void erase(const Item &i) {
    242256      int idx = _iim[i];
    … …  
    246260    }
    247261
    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.
     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.
    254267    Prio operator[](const Item &i) const {
    255268      int idx = _iim[i];
    … …  
    257270    }
    258271
    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.
     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.
    264278    /// \param i The item.
    265279    /// \param p The priority.
    … …  
    275289    }
    276290
    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.
     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.
    282294    /// \param i The item.
    283295    /// \param p The priority.
     296    /// \pre \e i must be stored in the heap with priority at least \e p.
    284297    void decrease(const Item &i, const Prio &p) {
    285298      int idx = _iim[i];
    … …  
    292305    }
    293306
    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.
     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.
    299310    /// \param i The item.
    300311    /// \param p The priority.
     312    /// \pre \e i must be stored in the heap with priority at most \e p.
    301313    void increase(const Item &i, const Prio &p) {
    302314      int idx = _iim[i];
    … …  
    306318    }
    307319
    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.
     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.
    315327    /// \param i The item.
    316328    State state(const Item &i) const {
    … …  
    320332    }
    321333
    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.
     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.
    327339    /// \param i The item.
    328340    /// \param st The state. It should not be \c IN_HEAP.
    … …  
    362374  /// \ingroup auxdat
    363375  ///
    364   /// \brief A Simplified Bucket Heap implementation.
     376  /// \brief Simplified bucket heap data structure.
    365377  ///
    366378  /// This class implements a simplified \e bucket \e heap data
    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.
     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.
    379397  ///
    380398  /// \sa BucketHeap
    … …  
    383401
    384402  public:
    385     typedef typename IM::Key Item;
     403
     404    /// Type of the item-int map.
     405    typedef IM ItemIntMap;
     406    /// Type of the priorities.
    386407    typedef int Prio;
    387     typedef std::pair<Item, Prio> Pair;
    388     typedef IM ItemIntMap;
     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;
    389412
    390413  private:
    … …  
    394417  public:
    395418
    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
     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
    400423    /// heap's point of view, but may be useful to the user.
    401424    ///
    … …  
    410433  public:
    411434
    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.
     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.
    418441    explicit SimpleBucketHeap(ItemIntMap &map)
    419442      : _iim(map), _free(-1), _num(0), _minimum(0) {}
    420443
    421     /// \brief Returns the number of items stored in the heap.
    422     ///
    423     /// The number of items stored in the heap.
     444    /// \brief The number of items stored in the heap.
     445    ///
     446    /// This function returns the number of items stored in the heap.
    424447    int size() const { return _num; }
    425448
    426     /// \brief Checks if the heap stores no items.
    427     ///
    428     /// Returns \c true if and only if the heap stores no items.
     449    /// \brief Check if the heap is empty.
     450    ///
     451    /// This function returns \c true if the heap is empty.
    429452    bool empty() const { return _num == 0; }
    430453
    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.
     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.
    437461    void clear() {
    438462      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
    … …  
    441465    /// \brief Insert a pair of item and priority into the heap.
    442466    ///
    443     /// Adds \c p.first to the heap with priority \c p.second.
     467    /// This function inserts \c p.first to the heap with priority
     468    /// \c p.second.
    444469    /// \param p The pair to insert.
     470    /// \pre \c p.first must not be stored in the heap.
    445471    void push(const Pair& p) {
    446472      push(p.first, p.second);
    … …  
    449475    /// \brief Insert an item into the heap with the given priority.
    450476    ///
    451     /// Adds \c i to the heap with priority \c p.
     477    /// This function inserts the given item into the heap with the
     478    /// given priority.
    452479    /// \param i The item to insert.
    453480    /// \param p The priority of the item.
     481    /// \pre \e i must not be stored in the heap.
    454482    void push(const Item &i, const Prio &p) {
    455483      int idx;
    … …  
    472500    }
    473501
    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.
     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.
    478506    Item top() const {
    479507      while (_first[_minimum] == -1) {
    … …  
    483511    }
    484512
    485     /// \brief Returns the minimum priority.
    486     ///
    487     /// It returns the minimum priority.
    488     /// \pre The heap must be nonempty.
     513    /// \brief The minimum priority.
     514    ///
     515    /// This function returns the minimum priority.
     516    /// \pre The heap must be non-empty.
    489517    Prio prio() const {
    490518      while (_first[_minimum] == -1) {
    … …  
    494522    }
    495523
    496     /// \brief Deletes the item with minimum priority.
    497     ///
    498     /// This method deletes the item with minimum priority from the heap.
     524    /// \brief Remove the item having minimum priority.
     525    ///
     526    /// This function removes the item having minimum priority.
    499527    /// \pre The heap must be non-empty.
    500528    void pop() {
    … …  
    510538    }
    511539
    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.
     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.
    520547    Prio operator[](const Item &i) const {
    521       for (int k = 0; k < _first.size(); ++k) {
     548      for (int k = 0; k < int(_first.size()); ++k) {
    522549        int idx = _first[k];
    523550        while (idx != -1) {
    … …  
    531558    }
    532559
    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.
     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.
    540567    /// \param i The item.
    541568    State state(const Item &i) const {
Note: See TracChangeset for help on using the changeset viewer.