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/radix_heap.h


Ignore:
Timestamp:
07/08/09 17:21:30 (15 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/radix_heap.h

    r730 r756  
    2222///\ingroup auxdat
    2323///\file
    24 ///\brief Radix Heap implementation.
     24///\brief Radix heap implementation.
    2525
    2626#include <vector>
    … …  
    3030
    3131
    32   /// \ingroup auxdata
     32  /// \ingroup auxdat
    3333  ///
    34   /// \brief A Radix Heap implementation.
     34  /// \brief Radix heap data structure.
    3535  ///
    36   /// This class implements the \e radix \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. This heap type can store only items with \e int priority.
    40   /// In a heap one can change the priority of an item, add or erase an
    41   /// item, but the priority cannot be decreased under the last removed
    42   /// item's priority.
     36  /// This class implements the \e radix \e heap data structure.
     37  /// It practically conforms to the \ref concepts::Heap "heap concept",
     38  /// but it has some limitations due its special implementation.
     39  /// The type of the priorities must be \c int and the priority of an
     40  /// item cannot be decreased under the priority of the last removed item.
    4341  ///
    44   /// \param IM A read and writable Item int map, used internally
    45   /// to handle the cross references.
    46   ///
    47   /// \see BinHeap
    48   /// \see Dijkstra
     42  /// \tparam IM A read-writable item map with \c int values, used
     43  /// internally to handle the cross references.
    4944  template <typename IM>
    5045  class RadixHeap {
    5146
    5247  public:
    53     typedef typename IM::Key Item;
     48
     49    /// Type of the item-int map.
     50    typedef IM ItemIntMap;
     51    /// Type of the priorities.
    5452    typedef int Prio;
    55     typedef IM ItemIntMap;
     53    /// Type of the items stored in the heap.
     54    typedef typename ItemIntMap::Key Item;
    5655
    5756    /// \brief Exception thrown by RadixHeap.
    5857    ///
    59     /// This Exception is thrown when a smaller priority
    60     /// is inserted into the \e RadixHeap then the last time erased.
     58    /// This exception is thrown when an item is inserted into a
     59    /// RadixHeap with a priority smaller than the last erased one.
    6160    /// \see RadixHeap
    62 
    6361    class UnderFlowPriorityError : public Exception {
    6462    public:
    … …  
    6866    };
    6967
    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
     68    /// \brief Type to represent the states of the items.
     69    ///
     70    /// Each item has a state associated to it. It can be "in heap",
     71    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    7472    /// heap's point of view, but may be useful to the user.
    7573    ///
    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...
     74    /// The item-int map must be initialized in such way that it assigns
     75    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    7876    enum State {
    79       IN_HEAP = 0,
    80       PRE_HEAP = -1,
    81       POST_HEAP = -2
     77      IN_HEAP = 0,    ///< = 0.
     78      PRE_HEAP = -1,  ///< = -1.
     79      POST_HEAP = -2  ///< = -2.
    8280    };
    8381
    … …  
    102100    ItemIntMap &_iim;
    103101
    104 
    105102  public:
    106     /// \brief The constructor.
    107     ///
    108     /// The constructor.
    109     ///
    110     /// \param map It 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     /// \param minimal The initial minimal value of the heap.
    115     /// \param capacity It determines the initial capacity of the heap.
    116     RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
    117       : _iim(map) {
    118       boxes.push_back(RadixBox(minimal, 1));
    119       boxes.push_back(RadixBox(minimal + 1, 1));
    120       while (lower(boxes.size() - 1, capacity + minimal - 1)) {
     103
     104    /// \brief Constructor.
     105    ///
     106    /// Constructor.
     107    /// \param map A map that assigns \c int values to the items.
     108    /// It is used internally to handle the cross references.
     109    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     110    /// \param minimum The initial minimum value of the heap.
     111    /// \param capacity The initial capacity of the heap.
     112    RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
     113      : _iim(map)
     114    {
     115      boxes.push_back(RadixBox(minimum, 1));
     116      boxes.push_back(RadixBox(minimum + 1, 1));
     117      while (lower(boxes.size() - 1, capacity + minimum - 1)) {
    121118        extend();
    122119      }
    123120    }
    124121
    125     /// The number of items stored in the heap.
    126     ///
    127     /// \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.
    128125    int size() const { return data.size(); }
    129     /// \brief Checks if the heap stores no items.
    130     ///
    131     /// Returns \c true if and only if the heap stores no items.
     126
     127    /// \brief Check if the heap is empty.
     128    ///
     129    /// This function returns \c true if the heap is empty.
    132130    bool empty() const { return data.empty(); }
    133131
    134     /// \brief Make empty this heap.
    135     ///
    136     /// Make empty this heap. It does not change the cross reference
    137     /// map.  If you want to reuse a heap what is not surely empty you
    138     /// should first clear the heap and after that you should set the
    139     /// cross reference map for each item to \c PRE_HEAP.
    140     void clear(int minimal = 0, int capacity = 0) {
     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.
     139    /// \param minimum The minimum value of the heap.
     140    /// \param capacity The capacity of the heap.
     141    void clear(int minimum = 0, int capacity = 0) {
    141142      data.clear(); boxes.clear();
    142       boxes.push_back(RadixBox(minimal, 1));
    143       boxes.push_back(RadixBox(minimal + 1, 1));
    144       while (lower(boxes.size() - 1, capacity + minimal - 1)) {
     143      boxes.push_back(RadixBox(minimum, 1));
     144      boxes.push_back(RadixBox(minimum + 1, 1));
     145      while (lower(boxes.size() - 1, capacity + minimum - 1)) {
    145146        extend();
    146147      }
    … …  
    157158    }
    158159
    159     /// \brief Remove item from the box list.
     160    // Remove item from the box list
    160161    void remove(int index) {
    161162      if (data[index].prev >= 0) {
    … …  
    169170    }
    170171
    171     /// \brief Insert item into the box list.
     172    // Insert item into the box list
    172173    void insert(int box, int index) {
    173174      if (boxes[box].first == -1) {
    … …  
    183184    }
    184185
    185     /// \brief Add a new box to the box list.
     186    // Add a new box to the box list
    186187    void extend() {
    187188      int min = boxes.back().min + boxes.back().size;
    … …  
    190191    }
    191192
    192     /// \brief Move an item up into the proper box.
     193    // Move an item up into the proper box.
    193194    void bubble_up(int index) {
    194195      if (!lower(data[index].box, data[index].prio)) return;
    … …  
    198199    }
    199200
    200     /// \brief Find up the proper box for the item with the given prio.
     201    // Find up the proper box for the item with the given priority
    201202    int findUp(int start, int pr) {
    202203      while (lower(start, pr)) {
    … …  
    208209    }
    209210
    210     /// \brief Move an item down into the proper box.
     211    // Move an item down into the proper box
    211212    void bubble_down(int index) {
    212213      if (!upper(data[index].box, data[index].prio)) return;
    … …  
    216217    }
    217218
    218     /// \brief Find up the proper box for the item with the given prio.
     219    // Find down the proper box for the item with the given priority
    219220    int findDown(int start, int pr) {
    220221      while (upper(start, pr)) {
    … …  
    224225    }
    225226
    226     /// \brief Find the first not empty box.
     227    // Find the first non-empty box
    227228    int findFirst() {
    228229      int first = 0;
    … …  
    231232    }
    232233
    233     /// \brief Gives back the minimal prio of the box.
     234    // Gives back the minimum priority of the given box
    234235    int minValue(int box) {
    235236      int min = data[boxes[box].first].prio;
    … …  
    240241    }
    241242
    242     /// \brief Rearrange the items of the heap and makes the
    243     /// first box not empty.
     243    // Rearrange the items of the heap and make the first box non-empty
    244244    void moveDown() {
    245245      int box = findFirst();
    … …  
    278278    /// \brief Insert an item into the heap with the given priority.
    279279    ///
    280     /// Adds \c i to the heap with priority \c p.
     280    /// This function inserts the given item into the heap with the
     281    /// given priority.
    281282    /// \param i The item to insert.
    282283    /// \param p The priority of the item.
     284    /// \pre \e i must not be stored in the heap.
     285    /// \warning This method may throw an \c UnderFlowPriorityException.
    283286    void push(const Item &i, const Prio &p) {
    284287      int n = data.size();
    … …  
    292295    }
    293296
    294     /// \brief Returns the item with minimum priority.
    295     ///
    296     /// This method returns the item with minimum priority.
    297     /// \pre The heap must be nonempty.
     297    /// \brief Return the item having minimum priority.
     298    ///
     299    /// This function returns the item having minimum priority.
     300    /// \pre The heap must be non-empty.
    298301    Item top() const {
    299302      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
    … …  
    301304    }
    302305
    303     /// \brief Returns the minimum priority.
    304     ///
    305     /// It returns the minimum priority.
    306     /// \pre The heap must be nonempty.
     306    /// \brief The minimum priority.
     307    ///
     308    /// This function returns the minimum priority.
     309    /// \pre The heap must be non-empty.
    307310    Prio prio() const {
    308311      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
    … …  
    310313     }
    311314
    312     /// \brief Deletes the item with minimum priority.
    313     ///
    314     /// This method deletes the item with minimum priority.
     315    /// \brief Remove the item having minimum priority.
     316    ///
     317    /// This function removes the item having minimum priority.
    315318    /// \pre The heap must be non-empty.
    316319    void pop() {
    … …  
    322325    }
    323326
    324     /// \brief Deletes \c i from the heap.
    325     ///
    326     /// This method deletes item \c i from the heap, if \c i was
    327     /// already stored in the heap.
    328     /// \param i The item to erase.
     327    /// \brief Remove the given item from the heap.
     328    ///
     329    /// This function removes the given item from the heap if it is
     330    /// already stored.
     331    /// \param i The item to delete.
     332    /// \pre \e i must be in the heap.
    329333    void erase(const Item &i) {
    330334      int index = _iim[i];
    … …  
    334338   }
    335339
    336     /// \brief Returns the priority of \c i.
    337     ///
    338     /// This function returns the priority of item \c i.
    339     /// \pre \c i must be in the heap.
    340     /// \param i The item.
     340    /// \brief The priority of the given item.
     341    ///
     342    /// This function returns the priority of the given item.
     343    /// \param i The item.
     344    /// \pre \e i must be in the heap.
    341345    Prio operator[](const Item &i) const {
    342346      int idx = _iim[i];
    … …  
    344348    }
    345349
    346     /// \brief \c i gets to the heap with priority \c p independently
    347     /// if \c i was already there.
    348     ///
    349     /// This method calls \ref push(\c i, \c p) if \c i is not stored
    350     /// in the heap and sets the priority of \c i to \c p otherwise.
    351     /// It may throw an \e UnderFlowPriorityException.
     350    /// \brief Set the priority of an item or insert it, if it is
     351    /// not stored in the heap.
     352    ///
     353    /// This method sets the priority of the given item if it is
     354    /// already stored in the heap. Otherwise it inserts the given
     355    /// item into the heap with the given priority.
    352356    /// \param i The item.
    353357    /// \param p The priority.
     358    /// \pre \e i must be in the heap.
     359    /// \warning This method may throw an \c UnderFlowPriorityException.
    354360    void set(const Item &i, const Prio &p) {
    355361      int idx = _iim[i];
    … …  
    366372    }
    367373
    368 
    369     /// \brief Decreases the priority of \c i to \c p.
    370     ///
    371     /// This method decreases the priority of item \c i to \c p.
    372     /// \pre \c i must be stored in the heap with priority at least \c p, and
    373     /// \c should be greater or equal to the last removed item's priority.
     374    /// \brief Decrease the priority of an item to the given value.
     375    ///
     376    /// This function decreases the priority of an item to the given value.
    374377    /// \param i The item.
    375378    /// \param p The priority.
     379    /// \pre \e i must be stored in the heap with priority at least \e p.
     380    /// \warning This method may throw an \c UnderFlowPriorityException.
    376381    void decrease(const Item &i, const Prio &p) {
    377382      int idx = _iim[i];
    … …  
    380385    }
    381386
    382     /// \brief Increases the priority of \c i to \c p.
    383     ///
    384     /// This method sets the priority of item \c i to \c p.
    385     /// \pre \c i must be stored in the heap with priority at most \c p
     387    /// \brief Increase the priority of an item to the given value.
     388    ///
     389    /// This function increases the priority of an item to the given value.
    386390    /// \param i The item.
    387391    /// \param p The priority.
     392    /// \pre \e i must be stored in the heap with priority at most \e p.
    388393    void increase(const Item &i, const Prio &p) {
    389394      int idx = _iim[i];
    … …  
    392397    }
    393398
    394     /// \brief Returns if \c item is in, has already been in, or has
    395     /// never been in the heap.
    396     ///
    397     /// This method returns PRE_HEAP if \c item has never been in the
    398     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    399     /// otherwise. In the latter case it is possible that \c item will
    400     /// get back to the heap again.
     399    /// \brief Return the state of an item.
     400    ///
     401    /// This method returns \c PRE_HEAP if the given item has never
     402    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
     403    /// and \c POST_HEAP otherwise.
     404    /// In the latter case it is possible that the item will get back
     405    /// to the heap again.
    401406    /// \param i The item.
    402407    State state(const Item &i) const {
    … …  
    406411    }
    407412
    408     /// \brief Sets the state of the \c item in the heap.
    409     ///
    410     /// Sets the state of the \c item in the heap. It can be used to
    411     /// manually clear the heap when it is important to achive the
    412     /// better time complexity.
     413    /// \brief Set the state of an item in the heap.
     414    ///
     415    /// This function sets the state of the given item in the heap.
     416    /// It can be used to manually clear the heap when it is important
     417    /// to achive better time complexity.
    413418    /// \param i The item.
    414419    /// \param st The state. It should not be \c IN_HEAP.
Note: See TracChangeset for help on using the changeset viewer.