1.1 --- a/lemon/concepts/heap.h Thu Mar 27 13:26:16 2008 +0100
1.2 +++ b/lemon/concepts/heap.h Sun Mar 30 14:27:25 2008 +0200
1.3 @@ -18,8 +18,7 @@
1.4
1.5 ///\ingroup concept
1.6 ///\file
1.7 -///\brief Classes for representing heaps.
1.8 -///
1.9 +///\brief The concept of heaps.
1.10
1.11 #ifndef LEMON_CONCEPT_HEAP_H
1.12 #define LEMON_CONCEPT_HEAP_H
1.13 @@ -27,31 +26,34 @@
1.14 #include <lemon/bits/invalid.h>
1.15
1.16 namespace lemon {
1.17 +
1.18 namespace concepts {
1.19 +
1.20 /// \addtogroup concept
1.21 /// @{
1.22
1.23 -
1.24 - /// \brief A concept structure describes the main interface of heaps.
1.25 + /// \brief The heap concept.
1.26 ///
1.27 - /// A concept structure describes the main interface of heaps.
1.28 - ///
1.29 - template <typename Prio, typename ItemIntMap>
1.30 + /// Concept class describing the main interface of heaps.
1.31 + template <typename Priority, typename ItemIntMap>
1.32 class Heap {
1.33 public:
1.34
1.35 - ///\brief Type of the items stored in the heap.
1.36 - typedef typename ItemIntMap::Key Item;
1.37 -
1.38 + /// Type of the items stored in the heap.
1.39 + typedef typename ItemIntMap::Key Item;
1.40
1.41 - /// \brief Type to represent the items states.
1.42 + /// Type of the priorities.
1.43 + typedef Priority Prio;
1.44 +
1.45 + /// \brief Type to represent the states of the items.
1.46 ///
1.47 - /// Each Item element have a state associated to it. It may be "in heap",
1.48 - /// "pre heap" or "post heap". The later two are indifferent from the
1.49 - /// heap's point of view, but may be useful to the user.
1.50 + /// Each item has a state associated to it. It can be "in heap",
1.51 + /// "pre heap" or "post heap". The later two are indifferent
1.52 + /// from the point of view of the heap, but may be useful for
1.53 + /// the user.
1.54 ///
1.55 - /// The ItemIntMap _should_ be initialized in such way, that it maps
1.56 - /// PRE_HEAP (-1) to any element to be put in the heap...
1.57 + /// The \c ItemIntMap must be initialized in such a way, that it
1.58 + /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
1.59 enum State {
1.60 IN_HEAP = 0,
1.61 PRE_HEAP = -1,
1.62 @@ -61,162 +63,185 @@
1.63 /// \brief The constructor.
1.64 ///
1.65 /// The constructor.
1.66 - /// \param _iim should be given to the constructor, since it is used
1.67 - /// internally to handle the cross references. The value of the map
1.68 - /// should be PRE_HEAP (-1) for each element.
1.69 - explicit Heap(ItemIntMap &_iim) {}
1.70 + /// \param map A map that assigns \c int values to keys of type
1.71 + /// \c Item. It is used internally by the heap implementations to
1.72 + /// handle the cross references. The assigned value must be
1.73 + /// \c PRE_HEAP (<tt>-1</tt>) for every item.
1.74 + explicit Heap(ItemIntMap &map) {}
1.75
1.76 /// \brief The number of items stored in the heap.
1.77 ///
1.78 /// Returns the number of items stored in the heap.
1.79 int size() const { return 0; }
1.80
1.81 - /// \brief Checks if the heap stores no items.
1.82 + /// \brief Checks if the heap is empty.
1.83 ///
1.84 - /// Returns \c true if and only if the heap stores no items.
1.85 + /// Returns \c true if the heap is empty.
1.86 bool empty() const { return false; }
1.87
1.88 - /// \brief Makes empty this heap.
1.89 + /// \brief Makes the heap empty.
1.90 ///
1.91 - /// Makes this heap empty.
1.92 + /// Makes the heap empty.
1.93 void clear();
1.94
1.95 - /// \brief Insert an item into the heap with the given heap.
1.96 + /// \brief Inserts an item into the heap with the given priority.
1.97 ///
1.98 - /// Adds \c i to the heap with priority \c p.
1.99 + /// Inserts the given item into the heap with the given priority.
1.100 /// \param i The item to insert.
1.101 /// \param p The priority of the item.
1.102 void push(const Item &i, const Prio &p) {}
1.103
1.104 - /// \brief Returns the item with minimum priority.
1.105 + /// \brief Returns the item having minimum priority.
1.106 ///
1.107 - /// This method returns the item with minimum priority.
1.108 - /// \pre The heap must be nonempty.
1.109 + /// Returns the item having minimum priority.
1.110 + /// \pre The heap must be non-empty.
1.111 Item top() const {}
1.112
1.113 - /// \brief Returns the minimum priority.
1.114 + /// \brief The minimum priority.
1.115 ///
1.116 - /// It returns the minimum priority.
1.117 - /// \pre The heap must be nonempty.
1.118 + /// Returns the minimum priority.
1.119 + /// \pre The heap must be non-empty.
1.120 Prio prio() const {}
1.121
1.122 - /// \brief Deletes the item with minimum priority.
1.123 + /// \brief Removes the item having minimum priority.
1.124 ///
1.125 - /// This method deletes the item with minimum priority.
1.126 - /// \pre The heap must be non-empty.
1.127 + /// Removes the item having minimum priority.
1.128 + /// \pre The heap must be non-empty.
1.129 void pop() {}
1.130
1.131 - /// \brief Deletes \c i from the heap.
1.132 + /// \brief Removes an item from the heap.
1.133 ///
1.134 - /// This method deletes item \c i from the heap, if \c i was
1.135 - /// already stored in the heap.
1.136 - /// \param i The item to erase.
1.137 + /// Removes the given item from the heap if it is already stored.
1.138 + /// \param i The item to delete.
1.139 void erase(const Item &i) {}
1.140
1.141 - /// \brief Returns the priority of \c i.
1.142 + /// \brief The priority of an item.
1.143 ///
1.144 - /// This function returns the priority of item \c i.
1.145 + /// Returns the priority of the given item.
1.146 /// \pre \c i must be in the heap.
1.147 /// \param i The item.
1.148 Prio operator[](const Item &i) const {}
1.149
1.150 - /// \brief \c i gets to the heap with priority \c p independently
1.151 - /// if \c i was already there.
1.152 + /// \brief Sets the priority of an item or inserts it, if it is
1.153 + /// not stored in the heap.
1.154 ///
1.155 - /// This method calls \ref push(\c i, \c p) if \c i is not stored
1.156 - /// in the heap and sets the priority of \c i to \c p otherwise.
1.157 - /// It may throw an \e UnderFlowPriorityException.
1.158 + /// This method sets the priority of the given item if it is
1.159 + /// already stored in the heap.
1.160 + /// Otherwise it inserts the given item with the given priority.
1.161 + ///
1.162 + /// It may throw an \ref UnderflowPriorityException.
1.163 /// \param i The item.
1.164 /// \param p The priority.
1.165 void set(const Item &i, const Prio &p) {}
1.166
1.167 - /// \brief Decreases the priority of \c i to \c p.
1.168 + /// \brief Decreases the priority of an item to the given value.
1.169 ///
1.170 - /// This method decreases the priority of item \c i to \c p.
1.171 + /// Decreases the priority of an item to the given value.
1.172 /// \pre \c i must be stored in the heap with priority at least \c p.
1.173 /// \param i The item.
1.174 /// \param p The priority.
1.175 void decrease(const Item &i, const Prio &p) {}
1.176
1.177 - /// \brief Increases the priority of \c i to \c p.
1.178 + /// \brief Increases the priority of an item to the given value.
1.179 ///
1.180 - /// This method sets the priority of item \c i to \c p.
1.181 - /// \pre \c i must be stored in the heap with priority at most \c
1.182 - /// p relative to \c Compare.
1.183 + /// Increases the priority of an item to the given value.
1.184 + /// \pre \c i must be stored in the heap with priority at most \c p.
1.185 /// \param i The item.
1.186 /// \param p The priority.
1.187 void increase(const Item &i, const Prio &p) {}
1.188
1.189 - /// \brief Returns if \c item is in, has already been in, or has
1.190 + /// \brief Returns if an item is in, has already been in, or has
1.191 /// never been in the heap.
1.192 ///
1.193 - /// This method returns PRE_HEAP if \c item has never been in the
1.194 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
1.195 - /// otherwise. In the latter case it is possible that \c item will
1.196 - /// get back to the heap again.
1.197 + /// This method returns \c PRE_HEAP if the given item has never
1.198 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
1.199 + /// and \c POST_HEAP otherwise.
1.200 + /// In the latter case it is possible that the item will get back
1.201 + /// to the heap again.
1.202 /// \param i The item.
1.203 State state(const Item &i) const {}
1.204
1.205 - /// \brief Sets the state of the \c item in the heap.
1.206 + /// \brief Sets the state of an item in the heap.
1.207 ///
1.208 - /// Sets the state of the \c item in the heap. It can be used to
1.209 - /// manually clear the heap when it is important to achive the
1.210 + /// Sets the state of the given item in the heap. It can be used
1.211 + /// to manually clear the heap when it is important to achive the
1.212 /// better time complexity.
1.213 /// \param i The item.
1.214 - /// \param st The state. It should not be \c IN_HEAP.
1.215 + /// \param st The state. It should not be \c IN_HEAP.
1.216 void state(const Item& i, State st) {}
1.217
1.218
1.219 template <typename _Heap>
1.220 struct Constraints {
1.221 public:
1.222 -
1.223 void constraints() {
1.224 + typedef typename _Heap::Item OwnItem;
1.225 + typedef typename _Heap::Prio OwnPrio;
1.226 + typedef typename _Heap::State OwnState;
1.227 +
1.228 Item item;
1.229 Prio prio;
1.230 -
1.231 + State state;
1.232 item=Item();
1.233 prio=Prio();
1.234 -
1.235 ignore_unused_variable_warning(item);
1.236 ignore_unused_variable_warning(prio);
1.237 + ignore_unused_variable_warning(state);
1.238
1.239 - typedef typename _Heap::State State;
1.240 - State state;
1.241 + OwnItem own_item;
1.242 + OwnPrio own_prio;
1.243 + OwnState own_state;
1.244 + own_item=Item();
1.245 + own_prio=Prio();
1.246 + ignore_unused_variable_warning(own_item);
1.247 + ignore_unused_variable_warning(own_prio);
1.248 + ignore_unused_variable_warning(own_state);
1.249
1.250 - ignore_unused_variable_warning(state);
1.251 -
1.252 - _Heap heap1 = _Heap(map);
1.253 -
1.254 + _Heap heap1(map);
1.255 + _Heap heap2 = heap1;
1.256 ignore_unused_variable_warning(heap1);
1.257 -
1.258 - heap.push(item, prio);
1.259 + ignore_unused_variable_warning(heap2);
1.260 +
1.261 + int s = heap.size();
1.262 + bool e = heap.empty();
1.263
1.264 prio = heap.prio();
1.265 item = heap.top();
1.266 + prio = heap[item];
1.267 + own_prio = heap.prio();
1.268 + own_item = heap.top();
1.269 + own_prio = heap[own_item];
1.270
1.271 + heap.push(item, prio);
1.272 + heap.push(own_item, own_prio);
1.273 heap.pop();
1.274
1.275 heap.set(item, prio);
1.276 heap.decrease(item, prio);
1.277 heap.increase(item, prio);
1.278 - prio = heap[item];
1.279 + heap.set(own_item, own_prio);
1.280 + heap.decrease(own_item, own_prio);
1.281 + heap.increase(own_item, own_prio);
1.282
1.283 heap.erase(item);
1.284 + heap.erase(own_item);
1.285 + heap.clear();
1.286
1.287 state = heap.state(item);
1.288 + heap.state(item, state);
1.289 + state = heap.state(own_item);
1.290 + heap.state(own_item, own_state);
1.291
1.292 state = _Heap::PRE_HEAP;
1.293 state = _Heap::IN_HEAP;
1.294 state = _Heap::POST_HEAP;
1.295 + own_state = _Heap::PRE_HEAP;
1.296 + own_state = _Heap::IN_HEAP;
1.297 + own_state = _Heap::POST_HEAP;
1.298 + }
1.299
1.300 - heap.clear();
1.301 - }
1.302 -
1.303 _Heap& heap;
1.304 ItemIntMap& map;
1.305 -
1.306 - Constraints() : heap(0), map(0) {}
1.307 };
1.308 };
1.309