1.1 --- a/lemon/bin_heap.h Thu Jun 11 23:13:24 2009 +0200
1.2 +++ b/lemon/bin_heap.h Wed Jul 08 17:21:30 2009 +0200
1.3 @@ -21,7 +21,7 @@
1.4
1.5 ///\ingroup auxdat
1.6 ///\file
1.7 -///\brief Binary Heap implementation.
1.8 +///\brief Binary heap implementation.
1.9
1.10 #include <vector>
1.11 #include <utility>
1.12 @@ -29,45 +29,41 @@
1.13
1.14 namespace lemon {
1.15
1.16 - ///\ingroup auxdat
1.17 + /// \ingroup auxdat
1.18 ///
1.19 - ///\brief A Binary Heap implementation.
1.20 + /// \brief Binary heap data structure.
1.21 ///
1.22 - ///This class implements the \e binary \e heap data structure.
1.23 + /// This class implements the \e binary \e heap data structure.
1.24 + /// It fully conforms to the \ref concepts::Heap "heap concept".
1.25 ///
1.26 - ///A \e heap is a data structure for storing items with specified values
1.27 - ///called \e priorities in such a way that finding the item with minimum
1.28 - ///priority is efficient. \c CMP specifies the ordering of the priorities.
1.29 - ///In a heap one can change the priority of an item, add or erase an
1.30 - ///item, etc.
1.31 - ///
1.32 - ///\tparam PR Type of the priority of the items.
1.33 - ///\tparam IM A read and writable item map with int values, used internally
1.34 - ///to handle the cross references.
1.35 - ///\tparam CMP A functor class for the ordering of the priorities.
1.36 - ///The default is \c std::less<PR>.
1.37 - ///
1.38 - ///\sa FibHeap
1.39 - ///\sa Dijkstra
1.40 + /// \tparam PR Type of the priorities of the items.
1.41 + /// \tparam IM A read-writable item map with \c int values, used
1.42 + /// internally to handle the cross references.
1.43 + /// \tparam CMP A functor class for comparing the priorities.
1.44 + /// The default is \c std::less<PR>.
1.45 +#ifdef DOXYGEN
1.46 + template <typename PR, typename IM, typename CMP>
1.47 +#else
1.48 template <typename PR, typename IM, typename CMP = std::less<PR> >
1.49 +#endif
1.50 class BinHeap {
1.51 + public:
1.52
1.53 - public:
1.54 - ///\e
1.55 + /// Type of the item-int map.
1.56 typedef IM ItemIntMap;
1.57 - ///\e
1.58 + /// Type of the priorities.
1.59 typedef PR Prio;
1.60 - ///\e
1.61 + /// Type of the items stored in the heap.
1.62 typedef typename ItemIntMap::Key Item;
1.63 - ///\e
1.64 + /// Type of the item-priority pairs.
1.65 typedef std::pair<Item,Prio> Pair;
1.66 - ///\e
1.67 + /// Functor type for comparing the priorities.
1.68 typedef CMP Compare;
1.69
1.70 - /// \brief Type to represent the items states.
1.71 + /// \brief Type to represent the states of the items.
1.72 ///
1.73 - /// Each Item element have a state associated to it. It may be "in heap",
1.74 - /// "pre heap" or "post heap". The latter two are indifferent from the
1.75 + /// Each item has a state associated to it. It can be "in heap",
1.76 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
1.77 /// heap's point of view, but may be useful to the user.
1.78 ///
1.79 /// The item-int map must be initialized in such way that it assigns
1.80 @@ -84,42 +80,43 @@
1.81 ItemIntMap &_iim;
1.82
1.83 public:
1.84 - /// \brief The constructor.
1.85 +
1.86 + /// \brief Constructor.
1.87 ///
1.88 - /// The constructor.
1.89 - /// \param map should be given to the constructor, since it is used
1.90 - /// internally to handle the cross references. The value of the map
1.91 - /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
1.92 + /// Constructor.
1.93 + /// \param map A map that assigns \c int values to the items.
1.94 + /// It is used internally to handle the cross references.
1.95 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
1.96 explicit BinHeap(ItemIntMap &map) : _iim(map) {}
1.97
1.98 - /// \brief The constructor.
1.99 + /// \brief Constructor.
1.100 ///
1.101 - /// The constructor.
1.102 - /// \param map should be given to the constructor, since it is used
1.103 - /// internally to handle the cross references. The value of the map
1.104 - /// should be PRE_HEAP (-1) for each element.
1.105 - ///
1.106 - /// \param comp The comparator function object.
1.107 + /// Constructor.
1.108 + /// \param map A map that assigns \c int values to the items.
1.109 + /// It is used internally to handle the cross references.
1.110 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
1.111 + /// \param comp The function object used for comparing the priorities.
1.112 BinHeap(ItemIntMap &map, const Compare &comp)
1.113 : _iim(map), _comp(comp) {}
1.114
1.115
1.116 - /// The number of items stored in the heap.
1.117 + /// \brief The number of items stored in the heap.
1.118 ///
1.119 - /// \brief Returns the number of items stored in the heap.
1.120 + /// This function returns the number of items stored in the heap.
1.121 int size() const { return _data.size(); }
1.122
1.123 - /// \brief Checks if the heap stores no items.
1.124 + /// \brief Check if the heap is empty.
1.125 ///
1.126 - /// Returns \c true if and only if the heap stores no items.
1.127 + /// This function returns \c true if the heap is empty.
1.128 bool empty() const { return _data.empty(); }
1.129
1.130 - /// \brief Make empty this heap.
1.131 + /// \brief Make the heap empty.
1.132 ///
1.133 - /// Make empty this heap. It does not change the cross reference map.
1.134 - /// If you want to reuse what is not surely empty you should first clear
1.135 - /// the heap and after that you should set the cross reference map for
1.136 - /// each item to \c PRE_HEAP.
1.137 + /// This functon makes the heap empty.
1.138 + /// It does not change the cross reference map. If you want to reuse
1.139 + /// a heap that is not surely empty, you should first clear it and
1.140 + /// then you should set the cross reference map to \c PRE_HEAP
1.141 + /// for each item.
1.142 void clear() {
1.143 _data.clear();
1.144 }
1.145 @@ -171,44 +168,47 @@
1.146 }
1.147
1.148 public:
1.149 +
1.150 /// \brief Insert a pair of item and priority into the heap.
1.151 ///
1.152 - /// Adds \c p.first to the heap with priority \c p.second.
1.153 + /// This function inserts \c p.first to the heap with priority
1.154 + /// \c p.second.
1.155 /// \param p The pair to insert.
1.156 + /// \pre \c p.first must not be stored in the heap.
1.157 void push(const Pair &p) {
1.158 int n = _data.size();
1.159 _data.resize(n+1);
1.160 bubble_up(n, p);
1.161 }
1.162
1.163 - /// \brief Insert an item into the heap with the given heap.
1.164 + /// \brief Insert an item into the heap with the given priority.
1.165 ///
1.166 - /// Adds \c i to the heap with priority \c p.
1.167 + /// This function inserts the given item into the heap with the
1.168 + /// given priority.
1.169 /// \param i The item to insert.
1.170 /// \param p The priority of the item.
1.171 + /// \pre \e i must not be stored in the heap.
1.172 void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
1.173
1.174 - /// \brief Returns the item with minimum priority relative to \c Compare.
1.175 + /// \brief Return the item having minimum priority.
1.176 ///
1.177 - /// This method returns the item with minimum priority relative to \c
1.178 - /// Compare.
1.179 - /// \pre The heap must be nonempty.
1.180 + /// This function returns the item having minimum priority.
1.181 + /// \pre The heap must be non-empty.
1.182 Item top() const {
1.183 return _data[0].first;
1.184 }
1.185
1.186 - /// \brief Returns the minimum priority relative to \c Compare.
1.187 + /// \brief The minimum priority.
1.188 ///
1.189 - /// It returns the minimum priority relative to \c Compare.
1.190 - /// \pre The heap must be nonempty.
1.191 + /// This function returns the minimum priority.
1.192 + /// \pre The heap must be non-empty.
1.193 Prio prio() const {
1.194 return _data[0].second;
1.195 }
1.196
1.197 - /// \brief Deletes the item with minimum priority relative to \c Compare.
1.198 + /// \brief Remove the item having minimum priority.
1.199 ///
1.200 - /// This method deletes the item with minimum priority relative to \c
1.201 - /// Compare from the heap.
1.202 + /// This function removes the item having minimum priority.
1.203 /// \pre The heap must be non-empty.
1.204 void pop() {
1.205 int n = _data.size()-1;
1.206 @@ -219,11 +219,12 @@
1.207 _data.pop_back();
1.208 }
1.209
1.210 - /// \brief Deletes \c i from the heap.
1.211 + /// \brief Remove the given item from the heap.
1.212 ///
1.213 - /// This method deletes item \c i from the heap.
1.214 - /// \param i The item to erase.
1.215 - /// \pre The item should be in the heap.
1.216 + /// This function removes the given item from the heap if it is
1.217 + /// already stored.
1.218 + /// \param i The item to delete.
1.219 + /// \pre \e i must be in the heap.
1.220 void erase(const Item &i) {
1.221 int h = _iim[i];
1.222 int n = _data.size()-1;
1.223 @@ -236,22 +237,22 @@
1.224 _data.pop_back();
1.225 }
1.226
1.227 -
1.228 - /// \brief Returns the priority of \c i.
1.229 + /// \brief The priority of the given item.
1.230 ///
1.231 - /// This function returns the priority of item \c i.
1.232 + /// This function returns the priority of the given item.
1.233 /// \param i The item.
1.234 - /// \pre \c i must be in the heap.
1.235 + /// \pre \e i must be in the heap.
1.236 Prio operator[](const Item &i) const {
1.237 int idx = _iim[i];
1.238 return _data[idx].second;
1.239 }
1.240
1.241 - /// \brief \c i gets to the heap with priority \c p independently
1.242 - /// if \c i was already there.
1.243 + /// \brief Set the priority of an item or insert it, if it is
1.244 + /// not stored in the heap.
1.245 ///
1.246 - /// This method calls \ref push(\c i, \c p) if \c i is not stored
1.247 - /// in the heap and sets the priority of \c i to \c p otherwise.
1.248 + /// This method sets the priority of the given item if it is
1.249 + /// already stored in the heap. Otherwise it inserts the given
1.250 + /// item into the heap with the given priority.
1.251 /// \param i The item.
1.252 /// \param p The priority.
1.253 void set(const Item &i, const Prio &p) {
1.254 @@ -267,37 +268,35 @@
1.255 }
1.256 }
1.257
1.258 - /// \brief Decreases the priority of \c i to \c p.
1.259 + /// \brief Decrease the priority of an item to the given value.
1.260 ///
1.261 - /// This method decreases the priority of item \c i to \c p.
1.262 + /// This function decreases the priority of an item to the given value.
1.263 /// \param i The item.
1.264 /// \param p The priority.
1.265 - /// \pre \c i must be stored in the heap with priority at least \c
1.266 - /// p relative to \c Compare.
1.267 + /// \pre \e i must be stored in the heap with priority at least \e p.
1.268 void decrease(const Item &i, const Prio &p) {
1.269 int idx = _iim[i];
1.270 bubble_up(idx, Pair(i,p));
1.271 }
1.272
1.273 - /// \brief Increases the priority of \c i to \c p.
1.274 + /// \brief Increase the priority of an item to the given value.
1.275 ///
1.276 - /// This method sets the priority of item \c i to \c p.
1.277 + /// This function increases the priority of an item to the given value.
1.278 /// \param i The item.
1.279 /// \param p The priority.
1.280 - /// \pre \c i must be stored in the heap with priority at most \c
1.281 - /// p relative to \c Compare.
1.282 + /// \pre \e i must be stored in the heap with priority at most \e p.
1.283 void increase(const Item &i, const Prio &p) {
1.284 int idx = _iim[i];
1.285 bubble_down(idx, Pair(i,p), _data.size());
1.286 }
1.287
1.288 - /// \brief Returns if \c item is in, has already been in, or has
1.289 - /// never been in the heap.
1.290 + /// \brief Return the state of an item.
1.291 ///
1.292 - /// This method returns PRE_HEAP if \c item has never been in the
1.293 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
1.294 - /// otherwise. In the latter case it is possible that \c item will
1.295 - /// get back to the heap again.
1.296 + /// This method returns \c PRE_HEAP if the given item has never
1.297 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
1.298 + /// and \c POST_HEAP otherwise.
1.299 + /// In the latter case it is possible that the item will get back
1.300 + /// to the heap again.
1.301 /// \param i The item.
1.302 State state(const Item &i) const {
1.303 int s = _iim[i];
1.304 @@ -306,11 +305,11 @@
1.305 return State(s);
1.306 }
1.307
1.308 - /// \brief Sets the state of the \c item in the heap.
1.309 + /// \brief Set the state of an item in the heap.
1.310 ///
1.311 - /// Sets the state of the \c item in the heap. It can be used to
1.312 - /// manually clear the heap when it is important to achive the
1.313 - /// better time complexity.
1.314 + /// This function sets the state of the given item in the heap.
1.315 + /// It can be used to manually clear the heap when it is important
1.316 + /// to achive better time complexity.
1.317 /// \param i The item.
1.318 /// \param st The state. It should not be \c IN_HEAP.
1.319 void state(const Item& i, State st) {
1.320 @@ -327,12 +326,13 @@
1.321 }
1.322 }
1.323
1.324 - /// \brief Replaces an item in the heap.
1.325 + /// \brief Replace an item in the heap.
1.326 ///
1.327 - /// The \c i item is replaced with \c j item. The \c i item should
1.328 - /// be in the heap, while the \c j should be out of the heap. The
1.329 - /// \c i item will out of the heap and \c j will be in the heap
1.330 - /// with the same prioriority as prevoiusly the \c i item.
1.331 + /// This function replaces item \c i with item \c j.
1.332 + /// Item \c i must be in the heap, while \c j must be out of the heap.
1.333 + /// After calling this method, item \c i will be out of the
1.334 + /// heap and \c j will be in the heap with the same prioriority
1.335 + /// as item \c i had before.
1.336 void replace(const Item& i, const Item& j) {
1.337 int idx = _iim[i];
1.338 _iim.set(i, _iim[j]);
2.1 --- a/lemon/bucket_heap.h Thu Jun 11 23:13:24 2009 +0200
2.2 +++ b/lemon/bucket_heap.h Wed Jul 08 17:21:30 2009 +0200
2.3 @@ -21,7 +21,7 @@
2.4
2.5 ///\ingroup auxdat
2.6 ///\file
2.7 -///\brief Bucket Heap implementation.
2.8 +///\brief Bucket heap implementation.
2.9
2.10 #include <vector>
2.11 #include <utility>
2.12 @@ -55,33 +55,39 @@
2.13
2.14 /// \ingroup auxdat
2.15 ///
2.16 - /// \brief A Bucket Heap implementation.
2.17 + /// \brief Bucket heap data structure.
2.18 ///
2.19 - /// This class implements the \e bucket \e heap data structure. A \e heap
2.20 - /// is a data structure for storing items with specified values called \e
2.21 - /// priorities in such a way that finding the item with minimum priority is
2.22 - /// efficient. The bucket heap is very simple implementation, it can store
2.23 - /// only integer priorities and it stores for each priority in the
2.24 - /// \f$ [0..C) \f$ range a list of items. So it should be used only when
2.25 - /// the priorities are small. It is not intended to use as dijkstra heap.
2.26 + /// This class implements the \e bucket \e heap data structure.
2.27 + /// It practically conforms to the \ref concepts::Heap "heap concept",
2.28 + /// but it has some limitations.
2.29 ///
2.30 - /// \param IM A read and write Item int map, used internally
2.31 - /// to handle the cross references.
2.32 - /// \param MIN If the given parameter is false then instead of the
2.33 - /// minimum value the maximum can be retrivied with the top() and
2.34 - /// prio() member functions.
2.35 + /// The bucket heap is a very simple structure. It can store only
2.36 + /// \c int priorities and it maintains a list of items for each priority
2.37 + /// in the range <tt>[0..C)</tt>. So it should only be used when the
2.38 + /// priorities are small. It is not intended to use as a Dijkstra heap.
2.39 + ///
2.40 + /// \tparam IM A read-writable item map with \c int values, used
2.41 + /// internally to handle the cross references.
2.42 + /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
2.43 + /// The default is \e min-heap. If this parameter is set to \c false,
2.44 + /// then the comparison is reversed, so the top(), prio() and pop()
2.45 + /// functions deal with the item having maximum priority instead of the
2.46 + /// minimum.
2.47 + ///
2.48 + /// \sa SimpleBucketHeap
2.49 template <typename IM, bool MIN = true>
2.50 class BucketHeap {
2.51
2.52 public:
2.53 - /// \e
2.54 - typedef typename IM::Key Item;
2.55 - /// \e
2.56 +
2.57 + /// Type of the item-int map.
2.58 + typedef IM ItemIntMap;
2.59 + /// Type of the priorities.
2.60 typedef int Prio;
2.61 - /// \e
2.62 - typedef std::pair<Item, Prio> Pair;
2.63 - /// \e
2.64 - typedef IM ItemIntMap;
2.65 + /// Type of the items stored in the heap.
2.66 + typedef typename ItemIntMap::Key Item;
2.67 + /// Type of the item-priority pairs.
2.68 + typedef std::pair<Item,Prio> Pair;
2.69
2.70 private:
2.71
2.72 @@ -89,10 +95,10 @@
2.73
2.74 public:
2.75
2.76 - /// \brief Type to represent the items states.
2.77 + /// \brief Type to represent the states of the items.
2.78 ///
2.79 - /// Each Item element have a state associated to it. It may be "in heap",
2.80 - /// "pre heap" or "post heap". The latter two are indifferent from the
2.81 + /// Each item has a state associated to it. It can be "in heap",
2.82 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
2.83 /// heap's point of view, but may be useful to the user.
2.84 ///
2.85 /// The item-int map must be initialized in such way that it assigns
2.86 @@ -104,30 +110,32 @@
2.87 };
2.88
2.89 public:
2.90 - /// \brief The constructor.
2.91 +
2.92 + /// \brief Constructor.
2.93 ///
2.94 - /// The constructor.
2.95 - /// \param map should be given to the constructor, since it is used
2.96 - /// internally to handle the cross references. The value of the map
2.97 - /// should be PRE_HEAP (-1) for each element.
2.98 + /// Constructor.
2.99 + /// \param map A map that assigns \c int values to the items.
2.100 + /// It is used internally to handle the cross references.
2.101 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
2.102 explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
2.103
2.104 - /// The number of items stored in the heap.
2.105 + /// \brief The number of items stored in the heap.
2.106 ///
2.107 - /// \brief Returns the number of items stored in the heap.
2.108 + /// This function returns the number of items stored in the heap.
2.109 int size() const { return _data.size(); }
2.110
2.111 - /// \brief Checks if the heap stores no items.
2.112 + /// \brief Check if the heap is empty.
2.113 ///
2.114 - /// Returns \c true if and only if the heap stores no items.
2.115 + /// This function returns \c true if the heap is empty.
2.116 bool empty() const { return _data.empty(); }
2.117
2.118 - /// \brief Make empty this heap.
2.119 + /// \brief Make the heap empty.
2.120 ///
2.121 - /// Make empty this heap. It does not change the cross reference
2.122 - /// map. If you want to reuse a heap what is not surely empty you
2.123 - /// should first clear the heap and after that you should set the
2.124 - /// cross reference map for each item to \c PRE_HEAP.
2.125 + /// This functon makes the heap empty.
2.126 + /// It does not change the cross reference map. If you want to reuse
2.127 + /// a heap that is not surely empty, you should first clear it and
2.128 + /// then you should set the cross reference map to \c PRE_HEAP
2.129 + /// for each item.
2.130 void clear() {
2.131 _data.clear(); _first.clear(); _minimum = 0;
2.132 }
2.133 @@ -174,19 +182,24 @@
2.134 }
2.135
2.136 public:
2.137 +
2.138 /// \brief Insert a pair of item and priority into the heap.
2.139 ///
2.140 - /// Adds \c p.first to the heap with priority \c p.second.
2.141 + /// This function inserts \c p.first to the heap with priority
2.142 + /// \c p.second.
2.143 /// \param p The pair to insert.
2.144 + /// \pre \c p.first must not be stored in the heap.
2.145 void push(const Pair& p) {
2.146 push(p.first, p.second);
2.147 }
2.148
2.149 /// \brief Insert an item into the heap with the given priority.
2.150 ///
2.151 - /// Adds \c i to the heap with priority \c p.
2.152 + /// This function inserts the given item into the heap with the
2.153 + /// given priority.
2.154 /// \param i The item to insert.
2.155 /// \param p The priority of the item.
2.156 + /// \pre \e i must not be stored in the heap.
2.157 void push(const Item &i, const Prio &p) {
2.158 int idx = _data.size();
2.159 _iim[i] = idx;
2.160 @@ -197,10 +210,10 @@
2.161 }
2.162 }
2.163
2.164 - /// \brief Returns the item with minimum priority.
2.165 + /// \brief Return the item having minimum priority.
2.166 ///
2.167 - /// This method returns the item with minimum priority.
2.168 - /// \pre The heap must be nonempty.
2.169 + /// This function returns the item having minimum priority.
2.170 + /// \pre The heap must be non-empty.
2.171 Item top() const {
2.172 while (_first[_minimum] == -1) {
2.173 Direction::increase(_minimum);
2.174 @@ -208,10 +221,10 @@
2.175 return _data[_first[_minimum]].item;
2.176 }
2.177
2.178 - /// \brief Returns the minimum priority.
2.179 + /// \brief The minimum priority.
2.180 ///
2.181 - /// It returns the minimum priority.
2.182 - /// \pre The heap must be nonempty.
2.183 + /// This function returns the minimum priority.
2.184 + /// \pre The heap must be non-empty.
2.185 Prio prio() const {
2.186 while (_first[_minimum] == -1) {
2.187 Direction::increase(_minimum);
2.188 @@ -219,9 +232,9 @@
2.189 return _minimum;
2.190 }
2.191
2.192 - /// \brief Deletes the item with minimum priority.
2.193 + /// \brief Remove the item having minimum priority.
2.194 ///
2.195 - /// This method deletes the item with minimum priority from the heap.
2.196 + /// This function removes the item having minimum priority.
2.197 /// \pre The heap must be non-empty.
2.198 void pop() {
2.199 while (_first[_minimum] == -1) {
2.200 @@ -233,11 +246,12 @@
2.201 relocate_last(idx);
2.202 }
2.203
2.204 - /// \brief Deletes \c i from the heap.
2.205 + /// \brief Remove the given item from the heap.
2.206 ///
2.207 - /// This method deletes item \c i from the heap, if \c i was
2.208 - /// already stored in the heap.
2.209 - /// \param i The item to erase.
2.210 + /// This function removes the given item from the heap if it is
2.211 + /// already stored.
2.212 + /// \param i The item to delete.
2.213 + /// \pre \e i must be in the heap.
2.214 void erase(const Item &i) {
2.215 int idx = _iim[i];
2.216 _iim[_data[idx].item] = -2;
2.217 @@ -245,22 +259,22 @@
2.218 relocate_last(idx);
2.219 }
2.220
2.221 -
2.222 - /// \brief Returns the priority of \c i.
2.223 + /// \brief The priority of the given item.
2.224 ///
2.225 - /// This function returns the priority of item \c i.
2.226 - /// \pre \c i must be in the heap.
2.227 + /// This function returns the priority of the given item.
2.228 /// \param i The item.
2.229 + /// \pre \e i must be in the heap.
2.230 Prio operator[](const Item &i) const {
2.231 int idx = _iim[i];
2.232 return _data[idx].value;
2.233 }
2.234
2.235 - /// \brief \c i gets to the heap with priority \c p independently
2.236 - /// if \c i was already there.
2.237 + /// \brief Set the priority of an item or insert it, if it is
2.238 + /// not stored in the heap.
2.239 ///
2.240 - /// This method calls \ref push(\c i, \c p) if \c i is not stored
2.241 - /// in the heap and sets the priority of \c i to \c p otherwise.
2.242 + /// This method sets the priority of the given item if it is
2.243 + /// already stored in the heap. Otherwise it inserts the given
2.244 + /// item into the heap with the given priority.
2.245 /// \param i The item.
2.246 /// \param p The priority.
2.247 void set(const Item &i, const Prio &p) {
2.248 @@ -274,13 +288,12 @@
2.249 }
2.250 }
2.251
2.252 - /// \brief Decreases the priority of \c i to \c p.
2.253 + /// \brief Decrease the priority of an item to the given value.
2.254 ///
2.255 - /// This method decreases the priority of item \c i to \c p.
2.256 - /// \pre \c i must be stored in the heap with priority at least \c
2.257 - /// p relative to \c Compare.
2.258 + /// This function decreases the priority of an item to the given value.
2.259 /// \param i The item.
2.260 /// \param p The priority.
2.261 + /// \pre \e i must be stored in the heap with priority at least \e p.
2.262 void decrease(const Item &i, const Prio &p) {
2.263 int idx = _iim[i];
2.264 unlace(idx);
2.265 @@ -291,13 +304,12 @@
2.266 lace(idx);
2.267 }
2.268
2.269 - /// \brief Increases the priority of \c i to \c p.
2.270 + /// \brief Increase the priority of an item to the given value.
2.271 ///
2.272 - /// This method sets the priority of item \c i to \c p.
2.273 - /// \pre \c i must be stored in the heap with priority at most \c
2.274 - /// p relative to \c Compare.
2.275 + /// This function increases the priority of an item to the given value.
2.276 /// \param i The item.
2.277 /// \param p The priority.
2.278 + /// \pre \e i must be stored in the heap with priority at most \e p.
2.279 void increase(const Item &i, const Prio &p) {
2.280 int idx = _iim[i];
2.281 unlace(idx);
2.282 @@ -305,13 +317,13 @@
2.283 lace(idx);
2.284 }
2.285
2.286 - /// \brief Returns if \c item is in, has already been in, or has
2.287 - /// never been in the heap.
2.288 + /// \brief Return the state of an item.
2.289 ///
2.290 - /// This method returns PRE_HEAP if \c item has never been in the
2.291 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
2.292 - /// otherwise. In the latter case it is possible that \c item will
2.293 - /// get back to the heap again.
2.294 + /// This method returns \c PRE_HEAP if the given item has never
2.295 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
2.296 + /// and \c POST_HEAP otherwise.
2.297 + /// In the latter case it is possible that the item will get back
2.298 + /// to the heap again.
2.299 /// \param i The item.
2.300 State state(const Item &i) const {
2.301 int idx = _iim[i];
2.302 @@ -319,11 +331,11 @@
2.303 return State(idx);
2.304 }
2.305
2.306 - /// \brief Sets the state of the \c item in the heap.
2.307 + /// \brief Set the state of an item in the heap.
2.308 ///
2.309 - /// Sets the state of the \c item in the heap. It can be used to
2.310 - /// manually clear the heap when it is important to achive the
2.311 - /// better time complexity.
2.312 + /// This function sets the state of the given item in the heap.
2.313 + /// It can be used to manually clear the heap when it is important
2.314 + /// to achive better time complexity.
2.315 /// \param i The item.
2.316 /// \param st The state. It should not be \c IN_HEAP.
2.317 void state(const Item& i, State st) {
2.318 @@ -361,31 +373,42 @@
2.319
2.320 /// \ingroup auxdat
2.321 ///
2.322 - /// \brief A Simplified Bucket Heap implementation.
2.323 + /// \brief Simplified bucket heap data structure.
2.324 ///
2.325 /// This class implements a simplified \e bucket \e heap data
2.326 - /// structure. It does not provide some functionality but it faster
2.327 - /// and simplier data structure than the BucketHeap. The main
2.328 - /// difference is that the BucketHeap stores for every key a double
2.329 - /// linked list while this class stores just simple lists. In the
2.330 - /// other way it does not support erasing each elements just the
2.331 - /// minimal and it does not supports key increasing, decreasing.
2.332 + /// structure. It does not provide some functionality, but it is
2.333 + /// faster and simpler than BucketHeap. The main difference is
2.334 + /// that BucketHeap stores a doubly-linked list for each key while
2.335 + /// this class stores only simply-linked lists. It supports erasing
2.336 + /// only for the item having minimum priority and it does not support
2.337 + /// key increasing and decreasing.
2.338 ///
2.339 - /// \param IM A read and write Item int map, used internally
2.340 - /// to handle the cross references.
2.341 - /// \param MIN If the given parameter is false then instead of the
2.342 - /// minimum value the maximum can be retrivied with the top() and
2.343 - /// prio() member functions.
2.344 + /// Note that this implementation does not conform to the
2.345 + /// \ref concepts::Heap "heap concept" due to the lack of some
2.346 + /// functionality.
2.347 + ///
2.348 + /// \tparam IM A read-writable item map with \c int values, used
2.349 + /// internally to handle the cross references.
2.350 + /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
2.351 + /// The default is \e min-heap. If this parameter is set to \c false,
2.352 + /// then the comparison is reversed, so the top(), prio() and pop()
2.353 + /// functions deal with the item having maximum priority instead of the
2.354 + /// minimum.
2.355 ///
2.356 /// \sa BucketHeap
2.357 template <typename IM, bool MIN = true >
2.358 class SimpleBucketHeap {
2.359
2.360 public:
2.361 - typedef typename IM::Key Item;
2.362 +
2.363 + /// Type of the item-int map.
2.364 + typedef IM ItemIntMap;
2.365 + /// Type of the priorities.
2.366 typedef int Prio;
2.367 - typedef std::pair<Item, Prio> Pair;
2.368 - typedef IM ItemIntMap;
2.369 + /// Type of the items stored in the heap.
2.370 + typedef typename ItemIntMap::Key Item;
2.371 + /// Type of the item-priority pairs.
2.372 + typedef std::pair<Item,Prio> Pair;
2.373
2.374 private:
2.375
2.376 @@ -393,10 +416,10 @@
2.377
2.378 public:
2.379
2.380 - /// \brief Type to represent the items states.
2.381 + /// \brief Type to represent the states of the items.
2.382 ///
2.383 - /// Each Item element have a state associated to it. It may be "in heap",
2.384 - /// "pre heap" or "post heap". The latter two are indifferent from the
2.385 + /// Each item has a state associated to it. It can be "in heap",
2.386 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
2.387 /// heap's point of view, but may be useful to the user.
2.388 ///
2.389 /// The item-int map must be initialized in such way that it assigns
2.390 @@ -409,48 +432,53 @@
2.391
2.392 public:
2.393
2.394 - /// \brief The constructor.
2.395 + /// \brief Constructor.
2.396 ///
2.397 - /// The constructor.
2.398 - /// \param map should be given to the constructor, since it is used
2.399 - /// internally to handle the cross references. The value of the map
2.400 - /// should be PRE_HEAP (-1) for each element.
2.401 + /// Constructor.
2.402 + /// \param map A map that assigns \c int values to the items.
2.403 + /// It is used internally to handle the cross references.
2.404 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
2.405 explicit SimpleBucketHeap(ItemIntMap &map)
2.406 : _iim(map), _free(-1), _num(0), _minimum(0) {}
2.407
2.408 - /// \brief Returns the number of items stored in the heap.
2.409 + /// \brief The number of items stored in the heap.
2.410 ///
2.411 - /// The number of items stored in the heap.
2.412 + /// This function returns the number of items stored in the heap.
2.413 int size() const { return _num; }
2.414
2.415 - /// \brief Checks if the heap stores no items.
2.416 + /// \brief Check if the heap is empty.
2.417 ///
2.418 - /// Returns \c true if and only if the heap stores no items.
2.419 + /// This function returns \c true if the heap is empty.
2.420 bool empty() const { return _num == 0; }
2.421
2.422 - /// \brief Make empty this heap.
2.423 + /// \brief Make the heap empty.
2.424 ///
2.425 - /// Make empty this heap. It does not change the cross reference
2.426 - /// map. If you want to reuse a heap what is not surely empty you
2.427 - /// should first clear the heap and after that you should set the
2.428 - /// cross reference map for each item to \c PRE_HEAP.
2.429 + /// This functon makes the heap empty.
2.430 + /// It does not change the cross reference map. If you want to reuse
2.431 + /// a heap that is not surely empty, you should first clear it and
2.432 + /// then you should set the cross reference map to \c PRE_HEAP
2.433 + /// for each item.
2.434 void clear() {
2.435 _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
2.436 }
2.437
2.438 /// \brief Insert a pair of item and priority into the heap.
2.439 ///
2.440 - /// Adds \c p.first to the heap with priority \c p.second.
2.441 + /// This function inserts \c p.first to the heap with priority
2.442 + /// \c p.second.
2.443 /// \param p The pair to insert.
2.444 + /// \pre \c p.first must not be stored in the heap.
2.445 void push(const Pair& p) {
2.446 push(p.first, p.second);
2.447 }
2.448
2.449 /// \brief Insert an item into the heap with the given priority.
2.450 ///
2.451 - /// Adds \c i to the heap with priority \c p.
2.452 + /// This function inserts the given item into the heap with the
2.453 + /// given priority.
2.454 /// \param i The item to insert.
2.455 /// \param p The priority of the item.
2.456 + /// \pre \e i must not be stored in the heap.
2.457 void push(const Item &i, const Prio &p) {
2.458 int idx;
2.459 if (_free == -1) {
2.460 @@ -471,10 +499,10 @@
2.461 ++_num;
2.462 }
2.463
2.464 - /// \brief Returns the item with minimum priority.
2.465 + /// \brief Return the item having minimum priority.
2.466 ///
2.467 - /// This method returns the item with minimum priority.
2.468 - /// \pre The heap must be nonempty.
2.469 + /// This function returns the item having minimum priority.
2.470 + /// \pre The heap must be non-empty.
2.471 Item top() const {
2.472 while (_first[_minimum] == -1) {
2.473 Direction::increase(_minimum);
2.474 @@ -482,10 +510,10 @@
2.475 return _data[_first[_minimum]].item;
2.476 }
2.477
2.478 - /// \brief Returns the minimum priority.
2.479 + /// \brief The minimum priority.
2.480 ///
2.481 - /// It returns the minimum priority.
2.482 - /// \pre The heap must be nonempty.
2.483 + /// This function returns the minimum priority.
2.484 + /// \pre The heap must be non-empty.
2.485 Prio prio() const {
2.486 while (_first[_minimum] == -1) {
2.487 Direction::increase(_minimum);
2.488 @@ -493,9 +521,9 @@
2.489 return _minimum;
2.490 }
2.491
2.492 - /// \brief Deletes the item with minimum priority.
2.493 + /// \brief Remove the item having minimum priority.
2.494 ///
2.495 - /// This method deletes the item with minimum priority from the heap.
2.496 + /// This function removes the item having minimum priority.
2.497 /// \pre The heap must be non-empty.
2.498 void pop() {
2.499 while (_first[_minimum] == -1) {
2.500 @@ -509,16 +537,15 @@
2.501 --_num;
2.502 }
2.503
2.504 - /// \brief Returns the priority of \c i.
2.505 + /// \brief The priority of the given item.
2.506 ///
2.507 - /// This function returns the priority of item \c i.
2.508 - /// \warning This operator is not a constant time function
2.509 - /// because it scans the whole data structure to find the proper
2.510 - /// value.
2.511 - /// \pre \c i must be in the heap.
2.512 + /// This function returns the priority of the given item.
2.513 /// \param i The item.
2.514 + /// \pre \e i must be in the heap.
2.515 + /// \warning This operator is not a constant time function because
2.516 + /// it scans the whole data structure to find the proper value.
2.517 Prio operator[](const Item &i) const {
2.518 - for (int k = 0; k < _first.size(); ++k) {
2.519 + for (int k = 0; k < int(_first.size()); ++k) {
2.520 int idx = _first[k];
2.521 while (idx != -1) {
2.522 if (_data[idx].item == i) {
2.523 @@ -530,13 +557,13 @@
2.524 return -1;
2.525 }
2.526
2.527 - /// \brief Returns if \c item is in, has already been in, or has
2.528 - /// never been in the heap.
2.529 + /// \brief Return the state of an item.
2.530 ///
2.531 - /// This method returns PRE_HEAP if \c item has never been in the
2.532 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
2.533 - /// otherwise. In the latter case it is possible that \c item will
2.534 - /// get back to the heap again.
2.535 + /// This method returns \c PRE_HEAP if the given item has never
2.536 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
2.537 + /// and \c POST_HEAP otherwise.
2.538 + /// In the latter case it is possible that the item will get back
2.539 + /// to the heap again.
2.540 /// \param i The item.
2.541 State state(const Item &i) const {
2.542 int idx = _iim[i];
3.1 --- a/lemon/concepts/heap.h Thu Jun 11 23:13:24 2009 +0200
3.2 +++ b/lemon/concepts/heap.h Wed Jul 08 17:21:30 2009 +0200
3.3 @@ -16,13 +16,13 @@
3.4 *
3.5 */
3.6
3.7 +#ifndef LEMON_CONCEPTS_HEAP_H
3.8 +#define LEMON_CONCEPTS_HEAP_H
3.9 +
3.10 ///\ingroup concept
3.11 ///\file
3.12 ///\brief The concept of heaps.
3.13
3.14 -#ifndef LEMON_CONCEPTS_HEAP_H
3.15 -#define LEMON_CONCEPTS_HEAP_H
3.16 -
3.17 #include <lemon/core.h>
3.18 #include <lemon/concept_check.h>
3.19
3.20 @@ -35,21 +35,27 @@
3.21
3.22 /// \brief The heap concept.
3.23 ///
3.24 - /// Concept class describing the main interface of heaps. A \e heap
3.25 - /// is a data structure for storing items with specified values called
3.26 - /// \e priorities in such a way that finding the item with minimum
3.27 - /// priority is efficient. In a heap one can change the priority of an
3.28 - /// item, add or erase an item, etc.
3.29 + /// This concept class describes the main interface of heaps.
3.30 + /// The various heap structures are efficient
3.31 + /// implementations of the abstract data type \e priority \e queue.
3.32 + /// They store items with specified values called \e priorities
3.33 + /// in such a way that finding and removing the item with minimum
3.34 + /// priority are efficient. The basic operations are adding and
3.35 + /// erasing items, changing the priority of an item, etc.
3.36 ///
3.37 - /// \tparam PR Type of the priority of the items.
3.38 - /// \tparam IM A read and writable item map with int values, used
3.39 + /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
3.40 + /// Any class that conforms to this concept can be used easily in such
3.41 + /// algorithms.
3.42 + ///
3.43 + /// \tparam PR Type of the priorities of the items.
3.44 + /// \tparam IM A read-writable item map with \c int values, used
3.45 /// internally to handle the cross references.
3.46 - /// \tparam Comp A functor class for the ordering of the priorities.
3.47 + /// \tparam CMP A functor class for comparing the priorities.
3.48 /// The default is \c std::less<PR>.
3.49 #ifdef DOXYGEN
3.50 - template <typename PR, typename IM, typename Comp = std::less<PR> >
3.51 + template <typename PR, typename IM, typename CMP>
3.52 #else
3.53 - template <typename PR, typename IM>
3.54 + template <typename PR, typename IM, typename CMP = std::less<PR> >
3.55 #endif
3.56 class Heap {
3.57 public:
3.58 @@ -64,109 +70,125 @@
3.59 /// \brief Type to represent the states of the items.
3.60 ///
3.61 /// Each item has a state associated to it. It can be "in heap",
3.62 - /// "pre heap" or "post heap". The later two are indifferent
3.63 - /// from the point of view of the heap, but may be useful for
3.64 - /// the user.
3.65 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
3.66 + /// heap's point of view, but may be useful to the user.
3.67 ///
3.68 /// The item-int map must be initialized in such way that it assigns
3.69 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
3.70 enum State {
3.71 IN_HEAP = 0, ///< = 0. The "in heap" state constant.
3.72 - PRE_HEAP = -1, ///< = -1. The "pre heap" state constant.
3.73 - POST_HEAP = -2 ///< = -2. The "post heap" state constant.
3.74 + PRE_HEAP = -1, ///< = -1. The "pre-heap" state constant.
3.75 + POST_HEAP = -2 ///< = -2. The "post-heap" state constant.
3.76 };
3.77
3.78 - /// \brief The constructor.
3.79 + /// \brief Constructor.
3.80 ///
3.81 - /// The constructor.
3.82 + /// Constructor.
3.83 /// \param map A map that assigns \c int values to keys of type
3.84 /// \c Item. It is used internally by the heap implementations to
3.85 /// handle the cross references. The assigned value must be
3.86 - /// \c PRE_HEAP (<tt>-1</tt>) for every item.
3.87 + /// \c PRE_HEAP (<tt>-1</tt>) for each item.
3.88 explicit Heap(ItemIntMap &map) {}
3.89
3.90 + /// \brief Constructor.
3.91 + ///
3.92 + /// Constructor.
3.93 + /// \param map A map that assigns \c int values to keys of type
3.94 + /// \c Item. It is used internally by the heap implementations to
3.95 + /// handle the cross references. The assigned value must be
3.96 + /// \c PRE_HEAP (<tt>-1</tt>) for each item.
3.97 + /// \param comp The function object used for comparing the priorities.
3.98 + explicit Heap(ItemIntMap &map, const CMP &comp) {}
3.99 +
3.100 /// \brief The number of items stored in the heap.
3.101 ///
3.102 - /// Returns the number of items stored in the heap.
3.103 + /// This function returns the number of items stored in the heap.
3.104 int size() const { return 0; }
3.105
3.106 - /// \brief Checks if the heap is empty.
3.107 + /// \brief Check if the heap is empty.
3.108 ///
3.109 - /// Returns \c true if the heap is empty.
3.110 + /// This function returns \c true if the heap is empty.
3.111 bool empty() const { return false; }
3.112
3.113 - /// \brief Makes the heap empty.
3.114 + /// \brief Make the heap empty.
3.115 ///
3.116 - /// Makes the heap empty.
3.117 - void clear();
3.118 + /// This functon makes the heap empty.
3.119 + /// It does not change the cross reference map. If you want to reuse
3.120 + /// a heap that is not surely empty, you should first clear it and
3.121 + /// then you should set the cross reference map to \c PRE_HEAP
3.122 + /// for each item.
3.123 + void clear() {}
3.124
3.125 - /// \brief Inserts an item into the heap with the given priority.
3.126 + /// \brief Insert an item into the heap with the given priority.
3.127 ///
3.128 - /// Inserts the given item into the heap with the given priority.
3.129 + /// This function inserts the given item into the heap with the
3.130 + /// given priority.
3.131 /// \param i The item to insert.
3.132 /// \param p The priority of the item.
3.133 + /// \pre \e i must not be stored in the heap.
3.134 void push(const Item &i, const Prio &p) {}
3.135
3.136 - /// \brief Returns the item having minimum priority.
3.137 + /// \brief Return the item having minimum priority.
3.138 ///
3.139 - /// Returns the item having minimum priority.
3.140 + /// This function returns the item having minimum priority.
3.141 /// \pre The heap must be non-empty.
3.142 Item top() const {}
3.143
3.144 /// \brief The minimum priority.
3.145 ///
3.146 - /// Returns the minimum priority.
3.147 + /// This function returns the minimum priority.
3.148 /// \pre The heap must be non-empty.
3.149 Prio prio() const {}
3.150
3.151 - /// \brief Removes the item having minimum priority.
3.152 + /// \brief Remove the item having minimum priority.
3.153 ///
3.154 - /// Removes the item having minimum priority.
3.155 + /// This function removes the item having minimum priority.
3.156 /// \pre The heap must be non-empty.
3.157 void pop() {}
3.158
3.159 - /// \brief Removes an item from the heap.
3.160 + /// \brief Remove the given item from the heap.
3.161 ///
3.162 - /// Removes the given item from the heap if it is already stored.
3.163 + /// This function removes the given item from the heap if it is
3.164 + /// already stored.
3.165 /// \param i The item to delete.
3.166 + /// \pre \e i must be in the heap.
3.167 void erase(const Item &i) {}
3.168
3.169 - /// \brief The priority of an item.
3.170 + /// \brief The priority of the given item.
3.171 ///
3.172 - /// Returns the priority of the given item.
3.173 + /// This function returns the priority of the given item.
3.174 /// \param i The item.
3.175 - /// \pre \c i must be in the heap.
3.176 + /// \pre \e i must be in the heap.
3.177 Prio operator[](const Item &i) const {}
3.178
3.179 - /// \brief Sets the priority of an item or inserts it, if it is
3.180 + /// \brief Set the priority of an item or insert it, if it is
3.181 /// not stored in the heap.
3.182 ///
3.183 /// This method sets the priority of the given item if it is
3.184 - /// already stored in the heap.
3.185 - /// Otherwise it inserts the given item with the given priority.
3.186 + /// already stored in the heap. Otherwise it inserts the given
3.187 + /// item into the heap with the given priority.
3.188 ///
3.189 /// \param i The item.
3.190 /// \param p The priority.
3.191 void set(const Item &i, const Prio &p) {}
3.192
3.193 - /// \brief Decreases the priority of an item to the given value.
3.194 + /// \brief Decrease the priority of an item to the given value.
3.195 ///
3.196 - /// Decreases the priority of an item to the given value.
3.197 + /// This function decreases the priority of an item to the given value.
3.198 /// \param i The item.
3.199 /// \param p The priority.
3.200 - /// \pre \c i must be stored in the heap with priority at least \c p.
3.201 + /// \pre \e i must be stored in the heap with priority at least \e p.
3.202 void decrease(const Item &i, const Prio &p) {}
3.203
3.204 - /// \brief Increases the priority of an item to the given value.
3.205 + /// \brief Increase the priority of an item to the given value.
3.206 ///
3.207 - /// Increases the priority of an item to the given value.
3.208 + /// This function increases the priority of an item to the given value.
3.209 /// \param i The item.
3.210 /// \param p The priority.
3.211 - /// \pre \c i must be stored in the heap with priority at most \c p.
3.212 + /// \pre \e i must be stored in the heap with priority at most \e p.
3.213 void increase(const Item &i, const Prio &p) {}
3.214
3.215 - /// \brief Returns if an item is in, has already been in, or has
3.216 - /// never been in the heap.
3.217 + /// \brief Return the state of an item.
3.218 ///
3.219 /// This method returns \c PRE_HEAP if the given item has never
3.220 /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
3.221 @@ -176,11 +198,11 @@
3.222 /// \param i The item.
3.223 State state(const Item &i) const {}
3.224
3.225 - /// \brief Sets the state of an item in the heap.
3.226 + /// \brief Set the state of an item in the heap.
3.227 ///
3.228 - /// Sets the state of the given item in the heap. It can be used
3.229 - /// to manually clear the heap when it is important to achive the
3.230 - /// better time complexity.
3.231 + /// This function sets the state of the given item in the heap.
3.232 + /// It can be used to manually clear the heap when it is important
3.233 + /// to achive better time complexity.
3.234 /// \param i The item.
3.235 /// \param st The state. It should not be \c IN_HEAP.
3.236 void state(const Item& i, State st) {}
4.1 --- a/lemon/fib_heap.h Thu Jun 11 23:13:24 2009 +0200
4.2 +++ b/lemon/fib_heap.h Wed Jul 08 17:21:30 2009 +0200
4.3 @@ -21,9 +21,10 @@
4.4
4.5 ///\file
4.6 ///\ingroup auxdat
4.7 -///\brief Fibonacci Heap implementation.
4.8 +///\brief Fibonacci heap implementation.
4.9
4.10 #include <vector>
4.11 +#include <utility>
4.12 #include <functional>
4.13 #include <lemon/math.h>
4.14
4.15 @@ -31,42 +32,37 @@
4.16
4.17 /// \ingroup auxdat
4.18 ///
4.19 - ///\brief Fibonacci Heap.
4.20 + /// \brief Fibonacci heap data structure.
4.21 ///
4.22 - ///This class implements the \e Fibonacci \e heap data structure. A \e heap
4.23 - ///is a data structure for storing items with specified values called \e
4.24 - ///priorities in such a way that finding the item with minimum priority is
4.25 - ///efficient. \c CMP specifies the ordering of the priorities. In a heap
4.26 - ///one can change the priority of an item, add or erase an item, etc.
4.27 + /// This class implements the \e Fibonacci \e heap data structure.
4.28 + /// It fully conforms to the \ref concepts::Heap "heap concept".
4.29 ///
4.30 - ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
4.31 - ///heap. In case of many calls to these operations, it is better to use a
4.32 - ///\ref BinHeap "binary heap".
4.33 + /// The methods \ref increase() and \ref erase() are not efficient in a
4.34 + /// Fibonacci heap. In case of many calls of these operations, it is
4.35 + /// better to use other heap structure, e.g. \ref BinHeap "binary heap".
4.36 ///
4.37 - ///\param PRIO Type of the priority of the items.
4.38 - ///\param IM A read and writable Item int map, used internally
4.39 - ///to handle the cross references.
4.40 - ///\param CMP A class for the ordering of the priorities. The
4.41 - ///default is \c std::less<PRIO>.
4.42 - ///
4.43 - ///\sa BinHeap
4.44 - ///\sa Dijkstra
4.45 + /// \tparam PR Type of the priorities of the items.
4.46 + /// \tparam IM A read-writable item map with \c int values, used
4.47 + /// internally to handle the cross references.
4.48 + /// \tparam CMP A functor class for comparing the priorities.
4.49 + /// The default is \c std::less<PR>.
4.50 #ifdef DOXYGEN
4.51 - template <typename PRIO, typename IM, typename CMP>
4.52 + template <typename PR, typename IM, typename CMP>
4.53 #else
4.54 - template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
4.55 + template <typename PR, typename IM, typename CMP = std::less<PR> >
4.56 #endif
4.57 class FibHeap {
4.58 public:
4.59 - ///\e
4.60 +
4.61 + /// Type of the item-int map.
4.62 typedef IM ItemIntMap;
4.63 - ///\e
4.64 - typedef PRIO Prio;
4.65 - ///\e
4.66 + /// Type of the priorities.
4.67 + typedef PR Prio;
4.68 + /// Type of the items stored in the heap.
4.69 typedef typename ItemIntMap::Key Item;
4.70 - ///\e
4.71 + /// Type of the item-priority pairs.
4.72 typedef std::pair<Item,Prio> Pair;
4.73 - ///\e
4.74 + /// Functor type for comparing the priorities.
4.75 typedef CMP Compare;
4.76
4.77 private:
4.78 @@ -80,10 +76,10 @@
4.79
4.80 public:
4.81
4.82 - /// \brief Type to represent the items states.
4.83 + /// \brief Type to represent the states of the items.
4.84 ///
4.85 - /// Each Item element have a state associated to it. It may be "in heap",
4.86 - /// "pre heap" or "post heap". The latter two are indifferent from the
4.87 + /// Each item has a state associated to it. It can be "in heap",
4.88 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
4.89 /// heap's point of view, but may be useful to the user.
4.90 ///
4.91 /// The item-int map must be initialized in such way that it assigns
4.92 @@ -94,60 +90,54 @@
4.93 POST_HEAP = -2 ///< = -2.
4.94 };
4.95
4.96 - /// \brief The constructor
4.97 + /// \brief Constructor.
4.98 ///
4.99 - /// \c map should be given to the constructor, since it is
4.100 - /// used internally to handle the cross references.
4.101 + /// Constructor.
4.102 + /// \param map A map that assigns \c int values to the items.
4.103 + /// It is used internally to handle the cross references.
4.104 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
4.105 explicit FibHeap(ItemIntMap &map)
4.106 : _minimum(0), _iim(map), _num() {}
4.107
4.108 - /// \brief The constructor
4.109 + /// \brief Constructor.
4.110 ///
4.111 - /// \c map should be given to the constructor, since it is used
4.112 - /// internally to handle the cross references. \c comp is an
4.113 - /// object for ordering of the priorities.
4.114 + /// Constructor.
4.115 + /// \param map A map that assigns \c int values to the items.
4.116 + /// It is used internally to handle the cross references.
4.117 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
4.118 + /// \param comp The function object used for comparing the priorities.
4.119 FibHeap(ItemIntMap &map, const Compare &comp)
4.120 : _minimum(0), _iim(map), _comp(comp), _num() {}
4.121
4.122 /// \brief The number of items stored in the heap.
4.123 ///
4.124 - /// Returns the number of items stored in the heap.
4.125 + /// This function returns the number of items stored in the heap.
4.126 int size() const { return _num; }
4.127
4.128 - /// \brief Checks if the heap stores no items.
4.129 + /// \brief Check if the heap is empty.
4.130 ///
4.131 - /// Returns \c true if and only if the heap stores no items.
4.132 + /// This function returns \c true if the heap is empty.
4.133 bool empty() const { return _num==0; }
4.134
4.135 - /// \brief Make empty this heap.
4.136 + /// \brief Make the heap empty.
4.137 ///
4.138 - /// Make empty this heap. It does not change the cross reference
4.139 - /// map. If you want to reuse a heap what is not surely empty you
4.140 - /// should first clear the heap and after that you should set the
4.141 - /// cross reference map for each item to \c PRE_HEAP.
4.142 + /// This functon makes the heap empty.
4.143 + /// It does not change the cross reference map. If you want to reuse
4.144 + /// a heap that is not surely empty, you should first clear it and
4.145 + /// then you should set the cross reference map to \c PRE_HEAP
4.146 + /// for each item.
4.147 void clear() {
4.148 _data.clear(); _minimum = 0; _num = 0;
4.149 }
4.150
4.151 - /// \brief \c item gets to the heap with priority \c value independently
4.152 - /// if \c item was already there.
4.153 + /// \brief Insert an item into the heap with the given priority.
4.154 ///
4.155 - /// This method calls \ref push(\c item, \c value) if \c item is not
4.156 - /// stored in the heap and it calls \ref decrease(\c item, \c value) or
4.157 - /// \ref increase(\c item, \c value) otherwise.
4.158 - void set (const Item& item, const Prio& value) {
4.159 - int i=_iim[item];
4.160 - if ( i >= 0 && _data[i].in ) {
4.161 - if ( _comp(value, _data[i].prio) ) decrease(item, value);
4.162 - if ( _comp(_data[i].prio, value) ) increase(item, value);
4.163 - } else push(item, value);
4.164 - }
4.165 -
4.166 - /// \brief Adds \c item to the heap with priority \c value.
4.167 - ///
4.168 - /// Adds \c item to the heap with priority \c value.
4.169 - /// \pre \c item must not be stored in the heap.
4.170 - void push (const Item& item, const Prio& value) {
4.171 + /// This function inserts the given item into the heap with the
4.172 + /// given priority.
4.173 + /// \param item The item to insert.
4.174 + /// \param prio The priority of the item.
4.175 + /// \pre \e item must not be stored in the heap.
4.176 + void push (const Item& item, const Prio& prio) {
4.177 int i=_iim[item];
4.178 if ( i < 0 ) {
4.179 int s=_data.size();
4.180 @@ -168,40 +158,30 @@
4.181 _data[i].right_neighbor=_data[_minimum].right_neighbor;
4.182 _data[_minimum].right_neighbor=i;
4.183 _data[i].left_neighbor=_minimum;
4.184 - if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
4.185 + if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
4.186 } else {
4.187 _data[i].right_neighbor=_data[i].left_neighbor=i;
4.188 _minimum=i;
4.189 }
4.190 - _data[i].prio=value;
4.191 + _data[i].prio=prio;
4.192 ++_num;
4.193 }
4.194
4.195 - /// \brief Returns the item with minimum priority relative to \c Compare.
4.196 + /// \brief Return the item having minimum priority.
4.197 ///
4.198 - /// This method returns the item with minimum priority relative to \c
4.199 - /// Compare.
4.200 - /// \pre The heap must be nonempty.
4.201 + /// This function returns the item having minimum priority.
4.202 + /// \pre The heap must be non-empty.
4.203 Item top() const { return _data[_minimum].name; }
4.204
4.205 - /// \brief Returns the minimum priority relative to \c Compare.
4.206 + /// \brief The minimum priority.
4.207 ///
4.208 - /// It returns the minimum priority relative to \c Compare.
4.209 - /// \pre The heap must be nonempty.
4.210 - const Prio& prio() const { return _data[_minimum].prio; }
4.211 + /// This function returns the minimum priority.
4.212 + /// \pre The heap must be non-empty.
4.213 + Prio prio() const { return _data[_minimum].prio; }
4.214
4.215 - /// \brief Returns the priority of \c item.
4.216 + /// \brief Remove the item having minimum priority.
4.217 ///
4.218 - /// It returns the priority of \c item.
4.219 - /// \pre \c item must be in the heap.
4.220 - const Prio& operator[](const Item& item) const {
4.221 - return _data[_iim[item]].prio;
4.222 - }
4.223 -
4.224 - /// \brief Deletes the item with minimum priority relative to \c Compare.
4.225 - ///
4.226 - /// This method deletes the item with minimum priority relative to \c
4.227 - /// Compare from the heap.
4.228 + /// This function removes the item having minimum priority.
4.229 /// \pre The heap must be non-empty.
4.230 void pop() {
4.231 /*The first case is that there are only one root.*/
4.232 @@ -234,10 +214,12 @@
4.233 --_num;
4.234 }
4.235
4.236 - /// \brief Deletes \c item from the heap.
4.237 + /// \brief Remove the given item from the heap.
4.238 ///
4.239 - /// This method deletes \c item from the heap, if \c item was already
4.240 - /// stored in the heap. It is quite inefficient in Fibonacci heaps.
4.241 + /// This function removes the given item from the heap if it is
4.242 + /// already stored.
4.243 + /// \param item The item to delete.
4.244 + /// \pre \e item must be in the heap.
4.245 void erase (const Item& item) {
4.246 int i=_iim[item];
4.247
4.248 @@ -252,43 +234,68 @@
4.249 }
4.250 }
4.251
4.252 - /// \brief Decreases the priority of \c item to \c value.
4.253 + /// \brief The priority of the given item.
4.254 ///
4.255 - /// This method decreases the priority of \c item to \c value.
4.256 - /// \pre \c item must be stored in the heap with priority at least \c
4.257 - /// value relative to \c Compare.
4.258 - void decrease (Item item, const Prio& value) {
4.259 + /// This function returns the priority of the given item.
4.260 + /// \param item The item.
4.261 + /// \pre \e item must be in the heap.
4.262 + Prio operator[](const Item& item) const {
4.263 + return _data[_iim[item]].prio;
4.264 + }
4.265 +
4.266 + /// \brief Set the priority of an item or insert it, if it is
4.267 + /// not stored in the heap.
4.268 + ///
4.269 + /// This method sets the priority of the given item if it is
4.270 + /// already stored in the heap. Otherwise it inserts the given
4.271 + /// item into the heap with the given priority.
4.272 + /// \param item The item.
4.273 + /// \param prio The priority.
4.274 + void set (const Item& item, const Prio& prio) {
4.275 int i=_iim[item];
4.276 - _data[i].prio=value;
4.277 + if ( i >= 0 && _data[i].in ) {
4.278 + if ( _comp(prio, _data[i].prio) ) decrease(item, prio);
4.279 + if ( _comp(_data[i].prio, prio) ) increase(item, prio);
4.280 + } else push(item, prio);
4.281 + }
4.282 +
4.283 + /// \brief Decrease the priority of an item to the given value.
4.284 + ///
4.285 + /// This function decreases the priority of an item to the given value.
4.286 + /// \param item The item.
4.287 + /// \param prio The priority.
4.288 + /// \pre \e item must be stored in the heap with priority at least \e prio.
4.289 + void decrease (const Item& item, const Prio& prio) {
4.290 + int i=_iim[item];
4.291 + _data[i].prio=prio;
4.292 int p=_data[i].parent;
4.293
4.294 - if ( p!=-1 && _comp(value, _data[p].prio) ) {
4.295 + if ( p!=-1 && _comp(prio, _data[p].prio) ) {
4.296 cut(i,p);
4.297 cascade(p);
4.298 }
4.299 - if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
4.300 + if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
4.301 }
4.302
4.303 - /// \brief Increases the priority of \c item to \c value.
4.304 + /// \brief Increase the priority of an item to the given value.
4.305 ///
4.306 - /// This method sets the priority of \c item to \c value. Though
4.307 - /// there is no precondition on the priority of \c item, this
4.308 - /// method should be used only if it is indeed necessary to increase
4.309 - /// (relative to \c Compare) the priority of \c item, because this
4.310 - /// method is inefficient.
4.311 - void increase (Item item, const Prio& value) {
4.312 + /// This function increases the priority of an item to the given value.
4.313 + /// \param item The item.
4.314 + /// \param prio The priority.
4.315 + /// \pre \e item must be stored in the heap with priority at most \e prio.
4.316 + void increase (const Item& item, const Prio& prio) {
4.317 erase(item);
4.318 - push(item, value);
4.319 + push(item, prio);
4.320 }
4.321
4.322 -
4.323 - /// \brief Returns if \c item is in, has already been in, or has never
4.324 - /// been in the heap.
4.325 + /// \brief Return the state of an item.
4.326 ///
4.327 - /// This method returns PRE_HEAP if \c item has never been in the
4.328 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
4.329 - /// otherwise. In the latter case it is possible that \c item will
4.330 - /// get back to the heap again.
4.331 + /// This method returns \c PRE_HEAP if the given item has never
4.332 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
4.333 + /// and \c POST_HEAP otherwise.
4.334 + /// In the latter case it is possible that the item will get back
4.335 + /// to the heap again.
4.336 + /// \param item The item.
4.337 State state(const Item &item) const {
4.338 int i=_iim[item];
4.339 if( i>=0 ) {
4.340 @@ -298,11 +305,11 @@
4.341 return State(i);
4.342 }
4.343
4.344 - /// \brief Sets the state of the \c item in the heap.
4.345 + /// \brief Set the state of an item in the heap.
4.346 ///
4.347 - /// Sets the state of the \c item in the heap. It can be used to
4.348 - /// manually clear the heap when it is important to achive the
4.349 - /// better time _complexity.
4.350 + /// This function sets the state of the given item in the heap.
4.351 + /// It can be used to manually clear the heap when it is important
4.352 + /// to achive better time complexity.
4.353 /// \param i The item.
4.354 /// \param st The state. It should not be \c IN_HEAP.
4.355 void state(const Item& i, State st) {
5.1 --- a/lemon/radix_heap.h Thu Jun 11 23:13:24 2009 +0200
5.2 +++ b/lemon/radix_heap.h Wed Jul 08 17:21:30 2009 +0200
5.3 @@ -21,7 +21,7 @@
5.4
5.5 ///\ingroup auxdat
5.6 ///\file
5.7 -///\brief Radix Heap implementation.
5.8 +///\brief Radix heap implementation.
5.9
5.10 #include <vector>
5.11 #include <lemon/error.h>
5.12 @@ -29,37 +29,35 @@
5.13 namespace lemon {
5.14
5.15
5.16 - /// \ingroup auxdata
5.17 + /// \ingroup auxdat
5.18 ///
5.19 - /// \brief A Radix Heap implementation.
5.20 + /// \brief Radix heap data structure.
5.21 ///
5.22 - /// This class implements the \e radix \e heap data structure. A \e heap
5.23 - /// is a data structure for storing items with specified values called \e
5.24 - /// priorities in such a way that finding the item with minimum priority is
5.25 - /// efficient. This heap type can store only items with \e int priority.
5.26 - /// In a heap one can change the priority of an item, add or erase an
5.27 - /// item, but the priority cannot be decreased under the last removed
5.28 - /// item's priority.
5.29 + /// This class implements the \e radix \e heap data structure.
5.30 + /// It practically conforms to the \ref concepts::Heap "heap concept",
5.31 + /// but it has some limitations due its special implementation.
5.32 + /// The type of the priorities must be \c int and the priority of an
5.33 + /// item cannot be decreased under the priority of the last removed item.
5.34 ///
5.35 - /// \param IM A read and writable Item int map, used internally
5.36 - /// to handle the cross references.
5.37 - ///
5.38 - /// \see BinHeap
5.39 - /// \see Dijkstra
5.40 + /// \tparam IM A read-writable item map with \c int values, used
5.41 + /// internally to handle the cross references.
5.42 template <typename IM>
5.43 class RadixHeap {
5.44
5.45 public:
5.46 - typedef typename IM::Key Item;
5.47 +
5.48 + /// Type of the item-int map.
5.49 + typedef IM ItemIntMap;
5.50 + /// Type of the priorities.
5.51 typedef int Prio;
5.52 - typedef IM ItemIntMap;
5.53 + /// Type of the items stored in the heap.
5.54 + typedef typename ItemIntMap::Key Item;
5.55
5.56 /// \brief Exception thrown by RadixHeap.
5.57 ///
5.58 - /// This Exception is thrown when a smaller priority
5.59 - /// is inserted into the \e RadixHeap then the last time erased.
5.60 + /// This exception is thrown when an item is inserted into a
5.61 + /// RadixHeap with a priority smaller than the last erased one.
5.62 /// \see RadixHeap
5.63 -
5.64 class UnderFlowPriorityError : public Exception {
5.65 public:
5.66 virtual const char* what() const throw() {
5.67 @@ -67,18 +65,18 @@
5.68 }
5.69 };
5.70
5.71 - /// \brief Type to represent the items states.
5.72 + /// \brief Type to represent the states of the items.
5.73 ///
5.74 - /// Each Item element have a state associated to it. It may be "in heap",
5.75 - /// "pre heap" or "post heap". The latter two are indifferent from the
5.76 + /// Each item has a state associated to it. It can be "in heap",
5.77 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
5.78 /// heap's point of view, but may be useful to the user.
5.79 ///
5.80 - /// The ItemIntMap \e should be initialized in such way that it maps
5.81 - /// PRE_HEAP (-1) to any element to be put in the heap...
5.82 + /// The item-int map must be initialized in such way that it assigns
5.83 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
5.84 enum State {
5.85 - IN_HEAP = 0,
5.86 - PRE_HEAP = -1,
5.87 - POST_HEAP = -2
5.88 + IN_HEAP = 0, ///< = 0.
5.89 + PRE_HEAP = -1, ///< = -1.
5.90 + POST_HEAP = -2 ///< = -2.
5.91 };
5.92
5.93 private:
5.94 @@ -101,47 +99,50 @@
5.95
5.96 ItemIntMap &_iim;
5.97
5.98 + public:
5.99
5.100 - public:
5.101 - /// \brief The constructor.
5.102 + /// \brief Constructor.
5.103 ///
5.104 - /// The constructor.
5.105 - ///
5.106 - /// \param map It should be given to the constructor, since it is used
5.107 - /// internally to handle the cross references. The value of the map
5.108 - /// should be PRE_HEAP (-1) for each element.
5.109 - ///
5.110 - /// \param minimal The initial minimal value of the heap.
5.111 - /// \param capacity It determines the initial capacity of the heap.
5.112 - RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
5.113 - : _iim(map) {
5.114 - boxes.push_back(RadixBox(minimal, 1));
5.115 - boxes.push_back(RadixBox(minimal + 1, 1));
5.116 - while (lower(boxes.size() - 1, capacity + minimal - 1)) {
5.117 + /// Constructor.
5.118 + /// \param map A map that assigns \c int values to the items.
5.119 + /// It is used internally to handle the cross references.
5.120 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
5.121 + /// \param minimum The initial minimum value of the heap.
5.122 + /// \param capacity The initial capacity of the heap.
5.123 + RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
5.124 + : _iim(map)
5.125 + {
5.126 + boxes.push_back(RadixBox(minimum, 1));
5.127 + boxes.push_back(RadixBox(minimum + 1, 1));
5.128 + while (lower(boxes.size() - 1, capacity + minimum - 1)) {
5.129 extend();
5.130 }
5.131 }
5.132
5.133 - /// The number of items stored in the heap.
5.134 + /// \brief The number of items stored in the heap.
5.135 ///
5.136 - /// \brief Returns the number of items stored in the heap.
5.137 + /// This function returns the number of items stored in the heap.
5.138 int size() const { return data.size(); }
5.139 - /// \brief Checks if the heap stores no items.
5.140 +
5.141 + /// \brief Check if the heap is empty.
5.142 ///
5.143 - /// Returns \c true if and only if the heap stores no items.
5.144 + /// This function returns \c true if the heap is empty.
5.145 bool empty() const { return data.empty(); }
5.146
5.147 - /// \brief Make empty this heap.
5.148 + /// \brief Make the heap empty.
5.149 ///
5.150 - /// Make empty this heap. It does not change the cross reference
5.151 - /// map. If you want to reuse a heap what is not surely empty you
5.152 - /// should first clear the heap and after that you should set the
5.153 - /// cross reference map for each item to \c PRE_HEAP.
5.154 - void clear(int minimal = 0, int capacity = 0) {
5.155 + /// This functon makes the heap empty.
5.156 + /// It does not change the cross reference map. If you want to reuse
5.157 + /// a heap that is not surely empty, you should first clear it and
5.158 + /// then you should set the cross reference map to \c PRE_HEAP
5.159 + /// for each item.
5.160 + /// \param minimum The minimum value of the heap.
5.161 + /// \param capacity The capacity of the heap.
5.162 + void clear(int minimum = 0, int capacity = 0) {
5.163 data.clear(); boxes.clear();
5.164 - boxes.push_back(RadixBox(minimal, 1));
5.165 - boxes.push_back(RadixBox(minimal + 1, 1));
5.166 - while (lower(boxes.size() - 1, capacity + minimal - 1)) {
5.167 + boxes.push_back(RadixBox(minimum, 1));
5.168 + boxes.push_back(RadixBox(minimum + 1, 1));
5.169 + while (lower(boxes.size() - 1, capacity + minimum - 1)) {
5.170 extend();
5.171 }
5.172 }
5.173 @@ -156,7 +157,7 @@
5.174 return pr >= boxes[box].min + boxes[box].size;
5.175 }
5.176
5.177 - /// \brief Remove item from the box list.
5.178 + // Remove item from the box list
5.179 void remove(int index) {
5.180 if (data[index].prev >= 0) {
5.181 data[data[index].prev].next = data[index].next;
5.182 @@ -168,7 +169,7 @@
5.183 }
5.184 }
5.185
5.186 - /// \brief Insert item into the box list.
5.187 + // Insert item into the box list
5.188 void insert(int box, int index) {
5.189 if (boxes[box].first == -1) {
5.190 boxes[box].first = index;
5.191 @@ -182,14 +183,14 @@
5.192 data[index].box = box;
5.193 }
5.194
5.195 - /// \brief Add a new box to the box list.
5.196 + // Add a new box to the box list
5.197 void extend() {
5.198 int min = boxes.back().min + boxes.back().size;
5.199 int bs = 2 * boxes.back().size;
5.200 boxes.push_back(RadixBox(min, bs));
5.201 }
5.202
5.203 - /// \brief Move an item up into the proper box.
5.204 + // Move an item up into the proper box.
5.205 void bubble_up(int index) {
5.206 if (!lower(data[index].box, data[index].prio)) return;
5.207 remove(index);
5.208 @@ -197,7 +198,7 @@
5.209 insert(box, index);
5.210 }
5.211
5.212 - /// \brief Find up the proper box for the item with the given prio.
5.213 + // Find up the proper box for the item with the given priority
5.214 int findUp(int start, int pr) {
5.215 while (lower(start, pr)) {
5.216 if (++start == int(boxes.size())) {
5.217 @@ -207,7 +208,7 @@
5.218 return start;
5.219 }
5.220
5.221 - /// \brief Move an item down into the proper box.
5.222 + // Move an item down into the proper box
5.223 void bubble_down(int index) {
5.224 if (!upper(data[index].box, data[index].prio)) return;
5.225 remove(index);
5.226 @@ -215,7 +216,7 @@
5.227 insert(box, index);
5.228 }
5.229
5.230 - /// \brief Find up the proper box for the item with the given prio.
5.231 + // Find down the proper box for the item with the given priority
5.232 int findDown(int start, int pr) {
5.233 while (upper(start, pr)) {
5.234 if (--start < 0) throw UnderFlowPriorityError();
5.235 @@ -223,14 +224,14 @@
5.236 return start;
5.237 }
5.238
5.239 - /// \brief Find the first not empty box.
5.240 + // Find the first non-empty box
5.241 int findFirst() {
5.242 int first = 0;
5.243 while (boxes[first].first == -1) ++first;
5.244 return first;
5.245 }
5.246
5.247 - /// \brief Gives back the minimal prio of the box.
5.248 + // Gives back the minimum priority of the given box
5.249 int minValue(int box) {
5.250 int min = data[boxes[box].first].prio;
5.251 for (int k = boxes[box].first; k != -1; k = data[k].next) {
5.252 @@ -239,8 +240,7 @@
5.253 return min;
5.254 }
5.255
5.256 - /// \brief Rearrange the items of the heap and makes the
5.257 - /// first box not empty.
5.258 + // Rearrange the items of the heap and make the first box non-empty
5.259 void moveDown() {
5.260 int box = findFirst();
5.261 if (box == 0) return;
5.262 @@ -277,9 +277,12 @@
5.263
5.264 /// \brief Insert an item into the heap with the given priority.
5.265 ///
5.266 - /// Adds \c i to the heap with priority \c p.
5.267 + /// This function inserts the given item into the heap with the
5.268 + /// given priority.
5.269 /// \param i The item to insert.
5.270 /// \param p The priority of the item.
5.271 + /// \pre \e i must not be stored in the heap.
5.272 + /// \warning This method may throw an \c UnderFlowPriorityException.
5.273 void push(const Item &i, const Prio &p) {
5.274 int n = data.size();
5.275 _iim.set(i, n);
5.276 @@ -291,27 +294,27 @@
5.277 insert(box, n);
5.278 }
5.279
5.280 - /// \brief Returns the item with minimum priority.
5.281 + /// \brief Return the item having minimum priority.
5.282 ///
5.283 - /// This method returns the item with minimum priority.
5.284 - /// \pre The heap must be nonempty.
5.285 + /// This function returns the item having minimum priority.
5.286 + /// \pre The heap must be non-empty.
5.287 Item top() const {
5.288 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
5.289 return data[boxes[0].first].item;
5.290 }
5.291
5.292 - /// \brief Returns the minimum priority.
5.293 + /// \brief The minimum priority.
5.294 ///
5.295 - /// It returns the minimum priority.
5.296 - /// \pre The heap must be nonempty.
5.297 + /// This function returns the minimum priority.
5.298 + /// \pre The heap must be non-empty.
5.299 Prio prio() const {
5.300 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
5.301 return data[boxes[0].first].prio;
5.302 }
5.303
5.304 - /// \brief Deletes the item with minimum priority.
5.305 + /// \brief Remove the item having minimum priority.
5.306 ///
5.307 - /// This method deletes the item with minimum priority.
5.308 + /// This function removes the item having minimum priority.
5.309 /// \pre The heap must be non-empty.
5.310 void pop() {
5.311 moveDown();
5.312 @@ -321,11 +324,12 @@
5.313 relocate_last(index);
5.314 }
5.315
5.316 - /// \brief Deletes \c i from the heap.
5.317 + /// \brief Remove the given item from the heap.
5.318 ///
5.319 - /// This method deletes item \c i from the heap, if \c i was
5.320 - /// already stored in the heap.
5.321 - /// \param i The item to erase.
5.322 + /// This function removes the given item from the heap if it is
5.323 + /// already stored.
5.324 + /// \param i The item to delete.
5.325 + /// \pre \e i must be in the heap.
5.326 void erase(const Item &i) {
5.327 int index = _iim[i];
5.328 _iim[i] = POST_HEAP;
5.329 @@ -333,24 +337,26 @@
5.330 relocate_last(index);
5.331 }
5.332
5.333 - /// \brief Returns the priority of \c i.
5.334 + /// \brief The priority of the given item.
5.335 ///
5.336 - /// This function returns the priority of item \c i.
5.337 - /// \pre \c i must be in the heap.
5.338 + /// This function returns the priority of the given item.
5.339 /// \param i The item.
5.340 + /// \pre \e i must be in the heap.
5.341 Prio operator[](const Item &i) const {
5.342 int idx = _iim[i];
5.343 return data[idx].prio;
5.344 }
5.345
5.346 - /// \brief \c i gets to the heap with priority \c p independently
5.347 - /// if \c i was already there.
5.348 + /// \brief Set the priority of an item or insert it, if it is
5.349 + /// not stored in the heap.
5.350 ///
5.351 - /// This method calls \ref push(\c i, \c p) if \c i is not stored
5.352 - /// in the heap and sets the priority of \c i to \c p otherwise.
5.353 - /// It may throw an \e UnderFlowPriorityException.
5.354 + /// This method sets the priority of the given item if it is
5.355 + /// already stored in the heap. Otherwise it inserts the given
5.356 + /// item into the heap with the given priority.
5.357 /// \param i The item.
5.358 /// \param p The priority.
5.359 + /// \pre \e i must be in the heap.
5.360 + /// \warning This method may throw an \c UnderFlowPriorityException.
5.361 void set(const Item &i, const Prio &p) {
5.362 int idx = _iim[i];
5.363 if( idx < 0 ) {
5.364 @@ -365,39 +371,38 @@
5.365 }
5.366 }
5.367
5.368 -
5.369 - /// \brief Decreases the priority of \c i to \c p.
5.370 + /// \brief Decrease the priority of an item to the given value.
5.371 ///
5.372 - /// This method decreases the priority of item \c i to \c p.
5.373 - /// \pre \c i must be stored in the heap with priority at least \c p, and
5.374 - /// \c should be greater or equal to the last removed item's priority.
5.375 + /// This function decreases the priority of an item to the given value.
5.376 /// \param i The item.
5.377 /// \param p The priority.
5.378 + /// \pre \e i must be stored in the heap with priority at least \e p.
5.379 + /// \warning This method may throw an \c UnderFlowPriorityException.
5.380 void decrease(const Item &i, const Prio &p) {
5.381 int idx = _iim[i];
5.382 data[idx].prio = p;
5.383 bubble_down(idx);
5.384 }
5.385
5.386 - /// \brief Increases the priority of \c i to \c p.
5.387 + /// \brief Increase the priority of an item to the given value.
5.388 ///
5.389 - /// This method sets the priority of item \c i to \c p.
5.390 - /// \pre \c i must be stored in the heap with priority at most \c p
5.391 + /// This function increases the priority of an item to the given value.
5.392 /// \param i The item.
5.393 /// \param p The priority.
5.394 + /// \pre \e i must be stored in the heap with priority at most \e p.
5.395 void increase(const Item &i, const Prio &p) {
5.396 int idx = _iim[i];
5.397 data[idx].prio = p;
5.398 bubble_up(idx);
5.399 }
5.400
5.401 - /// \brief Returns if \c item is in, has already been in, or has
5.402 - /// never been in the heap.
5.403 + /// \brief Return the state of an item.
5.404 ///
5.405 - /// This method returns PRE_HEAP if \c item has never been in the
5.406 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
5.407 - /// otherwise. In the latter case it is possible that \c item will
5.408 - /// get back to the heap again.
5.409 + /// This method returns \c PRE_HEAP if the given item has never
5.410 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
5.411 + /// and \c POST_HEAP otherwise.
5.412 + /// In the latter case it is possible that the item will get back
5.413 + /// to the heap again.
5.414 /// \param i The item.
5.415 State state(const Item &i) const {
5.416 int s = _iim[i];
5.417 @@ -405,11 +410,11 @@
5.418 return State(s);
5.419 }
5.420
5.421 - /// \brief Sets the state of the \c item in the heap.
5.422 + /// \brief Set the state of an item in the heap.
5.423 ///
5.424 - /// Sets the state of the \c item in the heap. It can be used to
5.425 - /// manually clear the heap when it is important to achive the
5.426 - /// better time complexity.
5.427 + /// This function sets the state of the given item in the heap.
5.428 + /// It can be used to manually clear the heap when it is important
5.429 + /// to achive better time complexity.
5.430 /// \param i The item.
5.431 /// \param st The state. It should not be \c IN_HEAP.
5.432 void state(const Item& i, State st) {