Changes in lemon/concepts/heap.h [757:f1fe0ddad6f7:631:33c6b6e755cd] in lemon
- File:
-
- 1 edited
-
lemon/concepts/heap.h (modified) (7 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/heap.h
r757 r631 17 17 */ 18 18 19 #ifndef LEMON_CONCEPTS_HEAP_H20 #define LEMON_CONCEPTS_HEAP_H21 22 19 ///\ingroup concept 23 20 ///\file 24 21 ///\brief The concept of heaps. 25 22 23 #ifndef LEMON_CONCEPTS_HEAP_H 24 #define LEMON_CONCEPTS_HEAP_H 25 26 26 #include <lemon/core.h> 27 27 #include <lemon/concept_check.h> … … 36 36 /// \brief The heap concept. 37 37 /// 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. 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. 45 43 /// 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 read-writable item map with \c int values, used 44 /// \tparam PR Type of the priority of the items. 45 /// \tparam IM A read and writable item map with int values, used 52 46 /// internally to handle the cross references. 53 /// \tparam C MP A functor class for comparingthe priorities.47 /// \tparam Comp A functor class for the ordering of the priorities. 54 48 /// The default is \c std::less<PR>. 55 49 #ifdef DOXYGEN 56 template <typename PR, typename IM, typename C MP>50 template <typename PR, typename IM, typename Comp = std::less<PR> > 57 51 #else 58 template <typename PR, typename IM , typename CMP = std::less<PR>>52 template <typename PR, typename IM> 59 53 #endif 60 54 class Heap { … … 71 65 /// 72 66 /// Each item has a state associated to it. It can be "in heap", 73 /// "pre-heap" or "post-heap". The latter two are indifferent from the 74 /// heap's point of view, but may be useful to the user. 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. 75 70 /// 76 71 /// The item-int map must be initialized in such way that it assigns … … 78 73 enum State { 79 74 IN_HEAP = 0, ///< = 0. The "in heap" state constant. 80 PRE_HEAP = -1, ///< = -1. The "pre -heap" state constant.81 POST_HEAP = -2 ///< = -2. The "post -heap" state constant.75 PRE_HEAP = -1, ///< = -1. The "pre heap" state constant. 76 POST_HEAP = -2 ///< = -2. The "post heap" state constant. 82 77 }; 83 78 84 /// \brief Constructor.85 /// 86 /// Constructor.79 /// \brief The constructor. 80 /// 81 /// The constructor. 87 82 /// \param map A map that assigns \c int values to keys of type 88 83 /// \c Item. It is used internally by the heap implementations to 89 84 /// handle the cross references. The assigned value must be 90 /// \c PRE_HEAP (<tt>-1</tt>) for e achitem.85 /// \c PRE_HEAP (<tt>-1</tt>) for every item. 91 86 explicit Heap(ItemIntMap &map) {} 92 87 93 /// \brief Constructor.94 ///95 /// Constructor.96 /// \param map A map that assigns \c int values to keys of type97 /// \c Item. It is used internally by the heap implementations to98 /// handle the cross references. The assigned value must be99 /// \c PRE_HEAP (<tt>-1</tt>) for each item.100 /// \param comp The function object used for comparing the priorities.101 explicit Heap(ItemIntMap &map, const CMP &comp) {}102 103 88 /// \brief The number of items stored in the heap. 104 89 /// 105 /// This function returns the number of items stored in the heap.90 /// Returns the number of items stored in the heap. 106 91 int size() const { return 0; } 107 92 108 /// \brief Check if the heap is empty.109 /// 110 /// This function returns \c true if the heap is empty.93 /// \brief Checks if the heap is empty. 94 /// 95 /// Returns \c true if the heap is empty. 111 96 bool empty() const { return false; } 112 97 113 /// \brief Make the heap empty. 114 /// 115 /// This functon makes the heap empty. 116 /// It does not change the cross reference map. If you want to reuse 117 /// a heap that is not surely empty, you should first clear it and 118 /// then you should set the cross reference map to \c PRE_HEAP 119 /// for each item. 120 void clear() {} 121 122 /// \brief Insert an item into the heap with the given priority. 123 /// 124 /// This function inserts the given item into the heap with the 125 /// given priority. 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. 126 106 /// \param i The item to insert. 127 107 /// \param p The priority of the item. 128 /// \pre \e i must not be stored in the heap.129 108 void push(const Item &i, const Prio &p) {} 130 109 131 /// \brief Return the item having minimum priority.132 /// 133 /// This function returns the item having minimum priority.110 /// \brief Returns the item having minimum priority. 111 /// 112 /// Returns the item having minimum priority. 134 113 /// \pre The heap must be non-empty. 135 114 Item top() const {} … … 137 116 /// \brief The minimum priority. 138 117 /// 139 /// This function returns the minimum priority.118 /// Returns the minimum priority. 140 119 /// \pre The heap must be non-empty. 141 120 Prio prio() const {} 142 121 143 /// \brief Remove the item having minimum priority.144 /// 145 /// This function removes the item having minimum priority.122 /// \brief Removes the item having minimum priority. 123 /// 124 /// Removes the item having minimum priority. 146 125 /// \pre The heap must be non-empty. 147 126 void pop() {} 148 127 149 /// \brief Remove the given item from the heap. 150 /// 151 /// This function removes the given item from the heap if it is 152 /// already stored. 128 /// \brief Removes an item from the heap. 129 /// 130 /// Removes the given item from the heap if it is already stored. 153 131 /// \param i The item to delete. 154 /// \pre \e i must be in the heap.155 132 void erase(const Item &i) {} 156 133 157 /// \brief The priority of the given item.158 /// 159 /// This function returns the priority of the given item.160 /// \param i The item. 161 /// \pre \ ei must be in the heap.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. 162 139 Prio operator[](const Item &i) const {} 163 140 164 /// \brief Set the priority of an item or insertit, if it is141 /// \brief Sets the priority of an item or inserts it, if it is 165 142 /// not stored in the heap. 166 143 /// 167 144 /// This method sets the priority of the given item if it is 168 /// already stored in the heap. Otherwise it inserts the given169 /// item into the heapwith the given priority.145 /// already stored in the heap. 146 /// Otherwise it inserts the given item with the given priority. 170 147 /// 171 148 /// \param i The item. … … 173 150 void set(const Item &i, const Prio &p) {} 174 151 175 /// \brief Decrease the priority of an item to the given value.176 /// 177 /// This function decreases the priority of an item to the given value.152 /// \brief Decreases the priority of an item to the given value. 153 /// 154 /// Decreases the priority of an item to the given value. 178 155 /// \param i The item. 179 156 /// \param p The priority. 180 /// \pre \ e i must be stored in the heap with priority at least \ep.157 /// \pre \c i must be stored in the heap with priority at least \c p. 181 158 void decrease(const Item &i, const Prio &p) {} 182 159 183 /// \brief Increase the priority of an item to the given value.184 /// 185 /// This function increases the priority of an item to the given value.160 /// \brief Increases the priority of an item to the given value. 161 /// 162 /// Increases the priority of an item to the given value. 186 163 /// \param i The item. 187 164 /// \param p The priority. 188 /// \pre \ e i must be stored in the heap with priority at most \ep.165 /// \pre \c i must be stored in the heap with priority at most \c p. 189 166 void increase(const Item &i, const Prio &p) {} 190 167 191 /// \brief Return the state of an item. 168 /// \brief Returns if an item is in, has already been in, or has 169 /// never been in the heap. 192 170 /// 193 171 /// This method returns \c PRE_HEAP if the given item has never … … 199 177 State state(const Item &i) const {} 200 178 201 /// \brief Set the state of an item in the heap.202 /// 203 /// This function sets the state of the given item in the heap.204 /// It can be used to manually clear the heap when it is important205 /// to achivebetter time complexity.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. 206 184 /// \param i The item. 207 185 /// \param st The state. It should not be \c IN_HEAP.
Note: See TracChangeset
for help on using the changeset viewer.
