Changeset 113:18a7ee8fa56e in lemon
 Timestamp:
 03/30/08 14:27:25 (14 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/concepts/heap.h
r100 r113 19 19 ///\ingroup concept 20 20 ///\file 21 ///\brief Classes for representing heaps. 22 /// 21 ///\brief The concept of heaps. 23 22 24 23 #ifndef LEMON_CONCEPT_HEAP_H … … 28 27 29 28 namespace lemon { 29 30 30 namespace concepts { 31 31 32 /// \addtogroup concept 32 33 /// @{ 33 34 34 35 /// \brief A concept structure describes the main interface of heaps. 35 /// \brief The heap concept. 36 36 /// 37 /// A concept structure describes the main interface of heaps. 38 /// 39 template <typename Prio, typename ItemIntMap> 37 /// Concept class describing the main interface of heaps. 38 template <typename Priority, typename ItemIntMap> 40 39 class Heap { 41 40 public: 42 41 43 ///\brief Type of the items stored in the heap. 44 typedef typename ItemIntMap::Key Item; 45 46 47 /// \brief Type to represent the items states. 48 /// 49 /// Each Item element have a state associated to it. It may be "in heap", 50 /// "pre heap" or "post heap". The later two are indifferent from the 51 /// heap's point of view, but may be useful to the user. 52 /// 53 /// The ItemIntMap _should_ be initialized in such way, that it maps 54 /// PRE_HEAP (1) to any element to be put in the heap... 42 /// Type of the items stored in the heap. 43 typedef typename ItemIntMap::Key Item; 44 45 /// Type of the priorities. 46 typedef Priority Prio; 47 48 /// \brief Type to represent the states of the items. 49 /// 50 /// Each item has a state associated to it. It can be "in heap", 51 /// "pre heap" or "post heap". The later two are indifferent 52 /// from the point of view of the heap, but may be useful for 53 /// the user. 54 /// 55 /// The \c ItemIntMap must be initialized in such a way, that it 56 /// assigns \c PRE_HEAP (<tt>1</tt>) to every item. 55 57 enum State { 56 58 IN_HEAP = 0, … … 62 64 /// 63 65 /// The constructor. 64 /// \param _iim should be given to the constructor, since it is used 65 /// internally to handle the cross references. The value of the map 66 /// should be PRE_HEAP (1) for each element. 67 explicit Heap(ItemIntMap &_iim) {} 66 /// \param map A map that assigns \c int values to keys of type 67 /// \c Item. It is used internally by the heap implementations to 68 /// handle the cross references. The assigned value must be 69 /// \c PRE_HEAP (<tt>1</tt>) for every item. 70 explicit Heap(ItemIntMap &map) {} 68 71 69 72 /// \brief The number of items stored in the heap. … … 72 75 int size() const { return 0; } 73 76 74 /// \brief Checks if the heap stores no items.75 /// 76 /// Returns \c true if and only if the heap stores no items.77 /// \brief Checks if the heap is empty. 78 /// 79 /// Returns \c true if the heap is empty. 77 80 bool empty() const { return false; } 78 81 79 /// \brief Makes empty this heap.80 /// 81 /// Makes th isheap empty.82 /// \brief Makes the heap empty. 83 /// 84 /// Makes the heap empty. 82 85 void clear(); 83 86 84 /// \brief Insert an item into the heap with the given heap.87 /// \brief Inserts an item into the heap with the given priority. 85 88 /// 86 /// Adds \c i to the heap with priority \c p.89 /// Inserts the given item into the heap with the given priority. 87 90 /// \param i The item to insert. 88 91 /// \param p The priority of the item. 89 92 void push(const Item &i, const Prio &p) {} 90 93 91 /// \brief Returns the item withminimum priority.92 /// 93 /// This method returns the item with minimum priority.94 /// \pre The heap must be non empty.94 /// \brief Returns the item having minimum priority. 95 /// 96 /// Returns the item having minimum priority. 97 /// \pre The heap must be nonempty. 95 98 Item top() const {} 96 99 97 /// \brief Returns the minimum priority.98 /// 99 /// It returns the minimum priority.100 /// \pre The heap must be non empty.100 /// \brief The minimum priority. 101 /// 102 /// Returns the minimum priority. 103 /// \pre The heap must be nonempty. 101 104 Prio prio() const {} 102 105 103 /// \brief Deletes the item withminimum priority.104 /// 105 /// This method deletes the item withminimum priority.106 /// \pre The heap must be nonempty. 106 /// \brief Removes the item having minimum priority. 107 /// 108 /// Removes the item having minimum priority. 109 /// \pre The heap must be nonempty. 107 110 void pop() {} 108 111 109 /// \brief Deletes \c i from the heap. 110 /// 111 /// This method deletes item \c i from the heap, if \c i was 112 /// \brief Removes an item from the heap. 113 /// 114 /// Removes the given item from the heap if it is already stored. 115 /// \param i The item to delete. 116 void erase(const Item &i) {} 117 118 /// \brief The priority of an item. 119 /// 120 /// Returns the priority of the given item. 121 /// \pre \c i must be in the heap. 122 /// \param i The item. 123 Prio operator[](const Item &i) const {} 124 125 /// \brief Sets the priority of an item or inserts it, if it is 126 /// not stored in the heap. 127 /// 128 /// This method sets the priority of the given item if it is 112 129 /// already stored in the heap. 113 /// \param i The item to erase. 114 void erase(const Item &i) {} 115 116 /// \brief Returns the priority of \c i. 117 /// 118 /// This function returns the priority of item \c i. 119 /// \pre \c i must be in the heap. 120 /// \param i The item. 121 Prio operator[](const Item &i) const {} 122 123 /// \brief \c i gets to the heap with priority \c p independently 124 /// if \c i was already there. 125 /// 126 /// This method calls \ref push(\c i, \c p) if \c i is not stored 127 /// in the heap and sets the priority of \c i to \c p otherwise. 128 /// It may throw an \e UnderFlowPriorityException. 130 /// Otherwise it inserts the given item with the given priority. 131 /// 132 /// It may throw an \ref UnderflowPriorityException. 129 133 /// \param i The item. 130 134 /// \param p The priority. 131 135 void set(const Item &i, const Prio &p) {} 132 136 133 /// \brief Decreases the priority of \c i to \c p.134 /// 135 /// This method decreases the priority of item \c i to \c p.137 /// \brief Decreases the priority of an item to the given value. 138 /// 139 /// Decreases the priority of an item to the given value. 136 140 /// \pre \c i must be stored in the heap with priority at least \c p. 137 141 /// \param i The item. … … 139 143 void decrease(const Item &i, const Prio &p) {} 140 144 141 /// \brief Increases the priority of \c i to \c p. 142 /// 143 /// This method sets the priority of item \c i to \c p. 144 /// \pre \c i must be stored in the heap with priority at most \c 145 /// p relative to \c Compare. 145 /// \brief Increases the priority of an item to the given value. 146 /// 147 /// Increases the priority of an item to the given value. 148 /// \pre \c i must be stored in the heap with priority at most \c p. 146 149 /// \param i The item. 147 150 /// \param p The priority. 148 151 void increase(const Item &i, const Prio &p) {} 149 152 150 /// \brief Returns if \c item is in, has already been in, or has153 /// \brief Returns if an item is in, has already been in, or has 151 154 /// never been in the heap. 152 155 /// 153 /// This method returns PRE_HEAP if \c item has never been in the 154 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 155 /// otherwise. In the latter case it is possible that \c item will 156 /// get back to the heap again. 156 /// This method returns \c PRE_HEAP if the given item has never 157 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 158 /// and \c POST_HEAP otherwise. 159 /// In the latter case it is possible that the item will get back 160 /// to the heap again. 157 161 /// \param i The item. 158 162 State state(const Item &i) const {} 159 163 160 /// \brief Sets the state of the \citem in the heap.161 /// 162 /// Sets the state of the \c item in the heap. It can be used to163 /// manually clear the heap when it is important to achive the164 /// \brief Sets the state of an item in the heap. 165 /// 166 /// Sets the state of the given item in the heap. It can be used 167 /// to manually clear the heap when it is important to achive the 164 168 /// better time complexity. 165 169 /// \param i The item. 166 /// \param st The state. It should not be \c IN_HEAP. 170 /// \param st The state. It should not be \c IN_HEAP. 167 171 void state(const Item& i, State st) {} 168 172 … … 171 175 struct Constraints { 172 176 public: 173 174 177 void constraints() { 178 typedef typename _Heap::Item OwnItem; 179 typedef typename _Heap::Prio OwnPrio; 180 typedef typename _Heap::State OwnState; 181 175 182 Item item; 176 183 Prio prio; 177 184 State state; 178 185 item=Item(); 179 186 prio=Prio(); 180 181 187 ignore_unused_variable_warning(item); 182 188 ignore_unused_variable_warning(prio); 183 184 typedef typename _Heap::State State;185 State state;186 187 189 ignore_unused_variable_warning(state); 188 189 _Heap heap1 = _Heap(map); 190 190 191 OwnItem own_item; 192 OwnPrio own_prio; 193 OwnState own_state; 194 own_item=Item(); 195 own_prio=Prio(); 196 ignore_unused_variable_warning(own_item); 197 ignore_unused_variable_warning(own_prio); 198 ignore_unused_variable_warning(own_state); 199 200 _Heap heap1(map); 201 _Heap heap2 = heap1; 191 202 ignore_unused_variable_warning(heap1); 192 193 heap.push(item, prio); 203 ignore_unused_variable_warning(heap2); 204 205 int s = heap.size(); 206 bool e = heap.empty(); 194 207 195 208 prio = heap.prio(); 196 209 item = heap.top(); 197 210 prio = heap[item]; 211 own_prio = heap.prio(); 212 own_item = heap.top(); 213 own_prio = heap[own_item]; 214 215 heap.push(item, prio); 216 heap.push(own_item, own_prio); 198 217 heap.pop(); 199 218 … … 201 220 heap.decrease(item, prio); 202 221 heap.increase(item, prio); 203 prio = heap[item]; 222 heap.set(own_item, own_prio); 223 heap.decrease(own_item, own_prio); 224 heap.increase(own_item, own_prio); 204 225 205 226 heap.erase(item); 227 heap.erase(own_item); 228 heap.clear(); 206 229 207 230 state = heap.state(item); 231 heap.state(item, state); 232 state = heap.state(own_item); 233 heap.state(own_item, own_state); 208 234 209 235 state = _Heap::PRE_HEAP; 210 236 state = _Heap::IN_HEAP; 211 237 state = _Heap::POST_HEAP; 212 213 heap.clear(); 238 own_state = _Heap::PRE_HEAP; 239 own_state = _Heap::IN_HEAP; 240 own_state = _Heap::POST_HEAP; 214 241 } 215 242 216 243 _Heap& heap; 217 244 ItemIntMap& map; 218 219 Constraints() : heap(0), map(0) {}220 245 }; 221 246 };
Note: See TracChangeset
for help on using the changeset viewer.