33 /// \addtogroup concept |
33 /// \addtogroup concept |
34 /// @{ |
34 /// @{ |
35 |
35 |
36 /// \brief The heap concept. |
36 /// \brief The heap concept. |
37 /// |
37 /// |
38 /// Concept class describing the main interface of heaps. A \e heap |
38 /// This concept class describes the main interface of heaps. |
39 /// is a data structure for storing items with specified values called |
39 /// The various heap structures are efficient |
40 /// \e priorities in such a way that finding the item with minimum |
40 /// implementations of the abstract data type \e priority \e queue. |
41 /// priority is efficient. In a heap one can change the priority of an |
41 /// They store items with specified values called \e priorities |
42 /// item, add or erase an item, etc. |
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. |
46 /// Heaps are crucial in several algorithms, such as Dijkstra and Prim. |
45 /// \tparam IM A read and writable item map with int values, used |
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 |
46 /// internally to handle the cross references. |
52 /// internally to handle the cross references. |
47 /// \tparam Comp A functor class for the ordering of the priorities. |
53 /// \tparam CMP A functor class for comparing the priorities. |
48 /// The default is \c std::less<PR>. |
54 /// The default is \c std::less<PR>. |
49 #ifdef DOXYGEN |
55 #ifdef DOXYGEN |
50 template <typename PR, typename IM, typename Comp = std::less<PR> > |
56 template <typename PR, typename IM, typename CMP> |
51 #else |
57 #else |
52 template <typename PR, typename IM> |
58 template <typename PR, typename IM, typename CMP = std::less<PR> > |
53 #endif |
59 #endif |
54 class Heap { |
60 class Heap { |
55 public: |
61 public: |
56 |
62 |
57 /// Type of the item-int map. |
63 /// Type of the item-int map. |
62 typedef typename ItemIntMap::Key Item; |
68 typedef typename ItemIntMap::Key Item; |
63 |
69 |
64 /// \brief Type to represent the states of the items. |
70 /// \brief Type to represent the states of the items. |
65 /// |
71 /// |
66 /// Each item has a state associated to it. It can be "in heap", |
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 |
73 /// "pre-heap" or "post-heap". The latter two are indifferent from the |
68 /// from the point of view of the heap, but may be useful for |
74 /// heap's point of view, but may be useful to the user. |
69 /// the user. |
|
70 /// |
75 /// |
71 /// The item-int map must be initialized in such way that it assigns |
76 /// The item-int map must be initialized in such way that it assigns |
72 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
77 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
73 enum State { |
78 enum State { |
74 IN_HEAP = 0, ///< = 0. The "in heap" state constant. |
79 IN_HEAP = 0, ///< = 0. The "in heap" state constant. |
75 PRE_HEAP = -1, ///< = -1. The "pre heap" state constant. |
80 PRE_HEAP = -1, ///< = -1. The "pre-heap" state constant. |
76 POST_HEAP = -2 ///< = -2. The "post heap" state constant. |
81 POST_HEAP = -2 ///< = -2. The "post-heap" state constant. |
77 }; |
82 }; |
78 |
83 |
79 /// \brief The constructor. |
84 /// \brief Constructor. |
80 /// |
85 /// |
81 /// The constructor. |
86 /// Constructor. |
82 /// \param map A map that assigns \c int values to keys of type |
87 /// \param map A map that assigns \c int values to keys of type |
83 /// \c Item. It is used internally by the heap implementations to |
88 /// \c Item. It is used internally by the heap implementations to |
84 /// handle the cross references. The assigned value must be |
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. |
86 explicit Heap(ItemIntMap &map) {} |
91 explicit Heap(ItemIntMap &map) {} |
87 |
92 |
|
93 /// \brief Constructor. |
|
94 /// |
|
95 /// Constructor. |
|
96 /// \param map A map that assigns \c int values to keys of type |
|
97 /// \c Item. It is used internally by the heap implementations to |
|
98 /// handle the cross references. The assigned value must be |
|
99 /// \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 |
88 /// \brief The number of items stored in the heap. |
103 /// \brief The number of items stored in the heap. |
89 /// |
104 /// |
90 /// Returns the number of items stored in the heap. |
105 /// This function returns the number of items stored in the heap. |
91 int size() const { return 0; } |
106 int size() const { return 0; } |
92 |
107 |
93 /// \brief Checks if the heap is empty. |
108 /// \brief Check if the heap is empty. |
94 /// |
109 /// |
95 /// Returns \c true if the heap is empty. |
110 /// This function returns \c true if the heap is empty. |
96 bool empty() const { return false; } |
111 bool empty() const { return false; } |
97 |
112 |
98 /// \brief Makes the heap empty. |
113 /// \brief Make the heap empty. |
99 /// |
114 /// |
100 /// Makes the heap empty. |
115 /// This functon makes the heap empty. |
101 void clear(); |
116 /// It does not change the cross reference map. If you want to reuse |
102 |
117 /// a heap that is not surely empty, you should first clear it and |
103 /// \brief Inserts an item into the heap with the given priority. |
118 /// then you should set the cross reference map to \c PRE_HEAP |
104 /// |
119 /// for each item. |
105 /// Inserts the given item into the heap with the given priority. |
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. |
106 /// \param i The item to insert. |
126 /// \param i The item to insert. |
107 /// \param p The priority of the item. |
127 /// \param p The priority of the item. |
|
128 /// \pre \e i must not be stored in the heap. |
108 void push(const Item &i, const Prio &p) {} |
129 void push(const Item &i, const Prio &p) {} |
109 |
130 |
110 /// \brief Returns the item having minimum priority. |
131 /// \brief Return the item having minimum priority. |
111 /// |
132 /// |
112 /// Returns the item having minimum priority. |
133 /// This function returns the item having minimum priority. |
113 /// \pre The heap must be non-empty. |
134 /// \pre The heap must be non-empty. |
114 Item top() const {} |
135 Item top() const {} |
115 |
136 |
116 /// \brief The minimum priority. |
137 /// \brief The minimum priority. |
117 /// |
138 /// |
118 /// Returns the minimum priority. |
139 /// This function returns the minimum priority. |
119 /// \pre The heap must be non-empty. |
140 /// \pre The heap must be non-empty. |
120 Prio prio() const {} |
141 Prio prio() const {} |
121 |
142 |
122 /// \brief Removes the item having minimum priority. |
143 /// \brief Remove the item having minimum priority. |
123 /// |
144 /// |
124 /// Removes the item having minimum priority. |
145 /// This function removes the item having minimum priority. |
125 /// \pre The heap must be non-empty. |
146 /// \pre The heap must be non-empty. |
126 void pop() {} |
147 void pop() {} |
127 |
148 |
128 /// \brief Removes an item from the heap. |
149 /// \brief Remove the given item from the heap. |
129 /// |
150 /// |
130 /// Removes the given item from the heap if it is already stored. |
151 /// This function removes the given item from the heap if it is |
|
152 /// already stored. |
131 /// \param i The item to delete. |
153 /// \param i The item to delete. |
|
154 /// \pre \e i must be in the heap. |
132 void erase(const Item &i) {} |
155 void erase(const Item &i) {} |
133 |
156 |
134 /// \brief The priority of an item. |
157 /// \brief The priority of the given item. |
135 /// |
158 /// |
136 /// Returns the priority of the given item. |
159 /// This function returns the priority of the given item. |
137 /// \param i The item. |
160 /// \param i The item. |
138 /// \pre \c i must be in the heap. |
161 /// \pre \e i must be in the heap. |
139 Prio operator[](const Item &i) const {} |
162 Prio operator[](const Item &i) const {} |
140 |
163 |
141 /// \brief Sets the priority of an item or inserts it, if it is |
164 /// \brief Set the priority of an item or insert it, if it is |
142 /// not stored in the heap. |
165 /// not stored in the heap. |
143 /// |
166 /// |
144 /// This method sets the priority of the given item if it is |
167 /// This method sets the priority of the given item if it is |
145 /// already stored in the heap. |
168 /// already stored in the heap. Otherwise it inserts the given |
146 /// Otherwise it inserts the given item with the given priority. |
169 /// item into the heap with the given priority. |
147 /// |
170 /// |
148 /// \param i The item. |
171 /// \param i The item. |
149 /// \param p The priority. |
172 /// \param p The priority. |
150 void set(const Item &i, const Prio &p) {} |
173 void set(const Item &i, const Prio &p) {} |
151 |
174 |
152 /// \brief Decreases the priority of an item to the given value. |
175 /// \brief Decrease the priority of an item to the given value. |
153 /// |
176 /// |
154 /// Decreases the priority of an item to the given value. |
177 /// This function decreases the priority of an item to the given value. |
155 /// \param i The item. |
178 /// \param i The item. |
156 /// \param p The priority. |
179 /// \param p The priority. |
157 /// \pre \c i must be stored in the heap with priority at least \c p. |
180 /// \pre \e i must be stored in the heap with priority at least \e p. |
158 void decrease(const Item &i, const Prio &p) {} |
181 void decrease(const Item &i, const Prio &p) {} |
159 |
182 |
160 /// \brief Increases the priority of an item to the given value. |
183 /// \brief Increase the priority of an item to the given value. |
161 /// |
184 /// |
162 /// Increases the priority of an item to the given value. |
185 /// This function increases the priority of an item to the given value. |
163 /// \param i The item. |
186 /// \param i The item. |
164 /// \param p The priority. |
187 /// \param p The priority. |
165 /// \pre \c i must be stored in the heap with priority at most \c p. |
188 /// \pre \e i must be stored in the heap with priority at most \e p. |
166 void increase(const Item &i, const Prio &p) {} |
189 void increase(const Item &i, const Prio &p) {} |
167 |
190 |
168 /// \brief Returns if an item is in, has already been in, or has |
191 /// \brief Return the state of an item. |
169 /// never been in the heap. |
|
170 /// |
192 /// |
171 /// This method returns \c PRE_HEAP if the given item has never |
193 /// This method returns \c PRE_HEAP if the given item has never |
172 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
194 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
173 /// and \c POST_HEAP otherwise. |
195 /// and \c POST_HEAP otherwise. |
174 /// In the latter case it is possible that the item will get back |
196 /// In the latter case it is possible that the item will get back |
175 /// to the heap again. |
197 /// to the heap again. |
176 /// \param i The item. |
198 /// \param i The item. |
177 State state(const Item &i) const {} |
199 State state(const Item &i) const {} |
178 |
200 |
179 /// \brief Sets the state of an item in the heap. |
201 /// \brief Set the state of an item in the heap. |
180 /// |
202 /// |
181 /// Sets the state of the given item in the heap. It can be used |
203 /// This function sets the state of the given item in the heap. |
182 /// to manually clear the heap when it is important to achive the |
204 /// It can be used to manually clear the heap when it is important |
183 /// better time complexity. |
205 /// to achive better time complexity. |
184 /// \param i The item. |
206 /// \param i The item. |
185 /// \param st The state. It should not be \c IN_HEAP. |
207 /// \param st The state. It should not be \c IN_HEAP. |
186 void state(const Item& i, State st) {} |
208 void state(const Item& i, State st) {} |
187 |
209 |
188 |
210 |