Changeset 1127:be7dd3a8d6a3 in lemon for lemon/concepts/heap.h
 Timestamp:
 01/20/12 19:20:02 (11 years ago)
 Branch:
 1.2
 Parents:
 1122:0976225b5cae (diff), 1125:b873350e6258 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/concepts/heap.h
r956 r1127 315 315 _Heap& heap; 316 316 ItemIntMap& map; 317 Constraints() {} 317 318 }; 318 319 }; 
lemon/concepts/heap.h
r1125 r1127 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 200320 095 * Copyright (C) 20032010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 17 17 */ 18 18 19 #ifndef LEMON_CONCEPTS_HEAP_H 20 #define LEMON_CONCEPTS_HEAP_H 21 19 22 ///\ingroup concept 20 23 ///\file 21 24 ///\brief The concept of heaps. 22 25 23 #ifndef LEMON_CONCEPTS_HEAP_H24 #define LEMON_CONCEPTS_HEAP_H25 26 26 #include <lemon/core.h> 27 27 #include <lemon/concept_check.h> … … 36 36 /// \brief The heap concept. 37 37 /// 38 /// Concept class describing the main interface of heaps. A \e heap 39 /// is a data structure for storing items with specified values called 40 /// \e priorities in such a way that finding the item with minimum 41 /// priority is efficient. In a heap one can change the priority of an 42 /// item, add or erase an item, etc. 38 /// This concept class describes the main interface of heaps. 39 /// The various \ref heaps "heap structures" are efficient 40 /// implementations of the abstract data type \e priority \e queue. 41 /// They store items with specified values called \e priorities 42 /// in such a way that finding and removing the item with minimum 43 /// priority are efficient. The basic operations are adding and 44 /// erasing items, changing the priority of an item, etc. 43 45 /// 44 /// \tparam PR Type of the priority of the items. 45 /// \tparam IM A read and writable item map with int values, used 46 /// Heaps are crucial in several algorithms, such as Dijkstra and Prim. 47 /// Any class that conforms to this concept can be used easily in such 48 /// algorithms. 49 /// 50 /// \tparam PR Type of the priorities of the items. 51 /// \tparam IM A readwritable item map with \c int values, used 46 52 /// internally to handle the cross references. 47 /// \tparam C omp A functor class for the ordering ofthe priorities.53 /// \tparam CMP A functor class for comparing the priorities. 48 54 /// The default is \c std::less<PR>. 49 55 #ifdef DOXYGEN 50 template <typename PR, typename IM, typename C omp = std::less<PR>>51 #else 52 template <typename PR, typename IM >56 template <typename PR, typename IM, typename CMP> 57 #else 58 template <typename PR, typename IM, typename CMP = std::less<PR> > 53 59 #endif 54 60 class Heap { … … 65 71 /// 66 72 /// Each item has a state associated to it. It can be "in heap", 67 /// "pre heap" or "post heap". The later two are indifferent 68 /// from the point of view of the heap, but may be useful for 69 /// the user. 73 /// "preheap" or "postheap". The latter two are indifferent from the 74 /// heap's point of view, but may be useful to the user. 70 75 /// 71 76 /// The itemint map must be initialized in such way that it assigns … … 73 78 enum State { 74 79 IN_HEAP = 0, ///< = 0. The "in heap" state constant. 75 PRE_HEAP = 1, ///< = 1. The "pre 76 POST_HEAP = 2 ///< = 2. The "post 80 PRE_HEAP = 1, ///< = 1. The "preheap" state constant. 81 POST_HEAP = 2 ///< = 2. The "postheap" state constant. 77 82 }; 78 83 79 /// \brief The constructor.80 /// 81 /// The constructor.84 /// \brief Constructor. 85 /// 86 /// Constructor. 82 87 /// \param map A map that assigns \c int values to keys of type 83 88 /// \c Item. It is used internally by the heap implementations to 84 89 /// handle the cross references. The assigned value must be 85 /// \c PRE_HEAP (<tt>1</tt>) for every item. 90 /// \c PRE_HEAP (<tt>1</tt>) for each item. 91 #ifdef DOXYGEN 86 92 explicit Heap(ItemIntMap &map) {} 93 #else 94 explicit Heap(ItemIntMap&) {} 95 #endif 96 97 /// \brief Constructor. 98 /// 99 /// Constructor. 100 /// \param map A map that assigns \c int values to keys of type 101 /// \c Item. It is used internally by the heap implementations to 102 /// handle the cross references. The assigned value must be 103 /// \c PRE_HEAP (<tt>1</tt>) for each item. 104 /// \param comp The function object used for comparing the priorities. 105 #ifdef DOXYGEN 106 explicit Heap(ItemIntMap &map, const CMP &comp) {} 107 #else 108 explicit Heap(ItemIntMap&, const CMP&) {} 109 #endif 87 110 88 111 /// \brief The number of items stored in the heap. 89 112 /// 90 /// Returns the number of items stored in the heap.113 /// This function returns the number of items stored in the heap. 91 114 int size() const { return 0; } 92 115 93 /// \brief Check sif the heap is empty.94 /// 95 /// Returns \c true if the heap is empty.116 /// \brief Check if the heap is empty. 117 /// 118 /// This function returns \c true if the heap is empty. 96 119 bool empty() const { return false; } 97 120 98 /// \brief Makes the heap empty. 99 /// 100 /// Makes the heap empty. 101 void clear(); 102 103 /// \brief Inserts an item into the heap with the given priority. 104 /// 105 /// Inserts the given item into the heap with the given priority. 121 /// \brief Make the heap empty. 122 /// 123 /// This functon makes the heap empty. 124 /// It does not change the cross reference map. If you want to reuse 125 /// a heap that is not surely empty, you should first clear it and 126 /// then you should set the cross reference map to \c PRE_HEAP 127 /// for each item. 128 void clear() {} 129 130 /// \brief Insert an item into the heap with the given priority. 131 /// 132 /// This function inserts the given item into the heap with the 133 /// given priority. 106 134 /// \param i The item to insert. 107 135 /// \param p The priority of the item. 136 /// \pre \e i must not be stored in the heap. 137 #ifdef DOXYGEN 108 138 void push(const Item &i, const Prio &p) {} 109 110 /// \brief Returns the item having minimum priority. 111 /// 112 /// Returns the item having minimum priority. 139 #else 140 void push(const Item&, const Prio&) {} 141 #endif 142 143 /// \brief Return the item having minimum priority. 144 /// 145 /// This function returns the item having minimum priority. 113 146 /// \pre The heap must be nonempty. 114 Item top() const { }147 Item top() const { return Item(); } 115 148 116 149 /// \brief The minimum priority. 117 150 /// 118 /// Returns the minimum priority.151 /// This function returns the minimum priority. 119 152 /// \pre The heap must be nonempty. 120 Prio prio() const { }121 122 /// \brief Remove sthe item having minimum priority.123 /// 124 /// Removes the item having minimum priority.153 Prio prio() const { return Prio(); } 154 155 /// \brief Remove the item having minimum priority. 156 /// 157 /// This function removes the item having minimum priority. 125 158 /// \pre The heap must be nonempty. 126 159 void pop() {} 127 160 128 /// \brief Removes an item from the heap. 129 /// 130 /// Removes the given item from the heap if it is already stored. 161 /// \brief Remove the given item from the heap. 162 /// 163 /// This function removes the given item from the heap if it is 164 /// already stored. 131 165 /// \param i The item to delete. 166 /// \pre \e i must be in the heap. 167 #ifdef DOXYGEN 132 168 void erase(const Item &i) {} 133 134 /// \brief The priority of an item. 135 /// 136 /// Returns the priority of the given item. 137 /// \param i The item. 138 /// \pre \c i must be in the heap. 169 #else 170 void erase(const Item&) {} 171 #endif 172 173 /// \brief The priority of the given item. 174 /// 175 /// This function returns the priority of the given item. 176 /// \param i The item. 177 /// \pre \e i must be in the heap. 178 #ifdef DOXYGEN 139 179 Prio operator[](const Item &i) const {} 140 141 /// \brief Sets the priority of an item or inserts it, if it is 180 #else 181 Prio operator[](const Item&) const { return Prio(); } 182 #endif 183 184 /// \brief Set the priority of an item or insert it, if it is 142 185 /// not stored in the heap. 143 186 /// 144 187 /// This method sets the priority of the given item if it is 145 /// already stored in the heap. 146 /// Otherwise it inserts the given itemwith the given priority.188 /// already stored in the heap. Otherwise it inserts the given 189 /// item into the heap with the given priority. 147 190 /// 148 191 /// \param i The item. 149 192 /// \param p The priority. 193 #ifdef DOXYGEN 150 194 void set(const Item &i, const Prio &p) {} 151 152 /// \brief Decreases the priority of an item to the given value. 153 /// 154 /// Decreases the priority of an item to the given value. 195 #else 196 void set(const Item&, const Prio&) {} 197 #endif 198 199 /// \brief Decrease the priority of an item to the given value. 200 /// 201 /// This function decreases the priority of an item to the given value. 155 202 /// \param i The item. 156 203 /// \param p The priority. 157 /// \pre \c i must be stored in the heap with priority at least \c p. 204 /// \pre \e i must be stored in the heap with priority at least \e p. 205 #ifdef DOXYGEN 158 206 void decrease(const Item &i, const Prio &p) {} 159 160 /// \brief Increases the priority of an item to the given value. 161 /// 162 /// Increases the priority of an item to the given value. 207 #else 208 void decrease(const Item&, const Prio&) {} 209 #endif 210 211 /// \brief Increase the priority of an item to the given value. 212 /// 213 /// This function increases the priority of an item to the given value. 163 214 /// \param i The item. 164 215 /// \param p The priority. 165 /// \pre \c i must be stored in the heap with priority at most \c p. 216 /// \pre \e i must be stored in the heap with priority at most \e p. 217 #ifdef DOXYGEN 166 218 void increase(const Item &i, const Prio &p) {} 167 168 /// \brief Returns if an item is in, has already been in, or has 169 /// never been in the heap. 219 #else 220 void increase(const Item&, const Prio&) {} 221 #endif 222 223 /// \brief Return the state of an item. 170 224 /// 171 225 /// This method returns \c PRE_HEAP if the given item has never … … 175 229 /// to the heap again. 176 230 /// \param i The item. 231 #ifdef DOXYGEN 177 232 State state(const Item &i) const {} 178 179 /// \brief Sets the state of an item in the heap. 180 /// 181 /// Sets the state of the given item in the heap. It can be used 182 /// to manually clear the heap when it is important to achive the 183 /// better time complexity. 233 #else 234 State state(const Item&) const { return PRE_HEAP; } 235 #endif 236 237 /// \brief Set the state of an item in the heap. 238 /// 239 /// This function sets the state of the given item in the heap. 240 /// It can be used to manually clear the heap when it is important 241 /// to achive better time complexity. 184 242 /// \param i The item. 185 243 /// \param st The state. It should not be \c IN_HEAP. 244 #ifdef DOXYGEN 186 245 void state(const Item& i, State st) {} 246 #else 247 void state(const Item&, State) {} 248 #endif 187 249 188 250
Note: See TracChangeset
for help on using the changeset viewer.