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. |
38 /// Concept class describing the main interface of heaps. A \e heap |
39 template <typename Priority, typename ItemIntMap> |
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. |
|
43 /// |
|
44 /// \tparam PR Type of the priority of the items. |
|
45 /// \tparam IM A read and writable item map with int values, used |
|
46 /// internally to handle the cross references. |
|
47 /// \tparam Comp A functor class for the ordering of the priorities. |
|
48 /// The default is \c std::less<PR>. |
|
49 #ifdef DOXYGEN |
|
50 template <typename PR, typename IM, typename Comp = std::less<PR> > |
|
51 #else |
|
52 template <typename PR, typename IM> |
|
53 #endif |
40 class Heap { |
54 class Heap { |
41 public: |
55 public: |
42 |
56 |
|
57 /// Type of the item-int map. |
|
58 typedef IM ItemIntMap; |
|
59 /// Type of the priorities. |
|
60 typedef PR Prio; |
43 /// Type of the items stored in the heap. |
61 /// Type of the items stored in the heap. |
44 typedef typename ItemIntMap::Key Item; |
62 typedef typename ItemIntMap::Key Item; |
45 |
|
46 /// Type of the priorities. |
|
47 typedef Priority Prio; |
|
48 |
63 |
49 /// \brief Type to represent the states of the items. |
64 /// \brief Type to represent the states of the items. |
50 /// |
65 /// |
51 /// Each item has a state associated to it. It can be "in heap", |
66 /// Each item has a state associated to it. It can be "in heap", |
52 /// "pre heap" or "post heap". The later two are indifferent |
67 /// "pre heap" or "post heap". The later two are indifferent |
53 /// from the point of view of the heap, but may be useful for |
68 /// from the point of view of the heap, but may be useful for |
54 /// the user. |
69 /// the user. |
55 /// |
70 /// |
56 /// The \c ItemIntMap must be initialized in such a way, that it |
71 /// The item-int map must be initialized in such way that it assigns |
57 /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item. |
72 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
58 enum State { |
73 enum State { |
59 IN_HEAP = 0, |
74 IN_HEAP = 0, ///< The "in heap" state constant. |
60 PRE_HEAP = -1, |
75 PRE_HEAP = -1, ///< The "pre heap" state constant. |
61 POST_HEAP = -2 |
76 POST_HEAP = -2 ///< The "post heap" state constant. |
62 }; |
77 }; |
63 |
78 |
64 /// \brief The constructor. |
79 /// \brief The constructor. |
65 /// |
80 /// |
66 /// The constructor. |
81 /// The constructor. |
117 void erase(const Item &i) {} |
132 void erase(const Item &i) {} |
118 |
133 |
119 /// \brief The priority of an item. |
134 /// \brief The priority of an item. |
120 /// |
135 /// |
121 /// Returns the priority of the given item. |
136 /// Returns the priority of the given item. |
|
137 /// \param i The item. |
122 /// \pre \c i must be in the heap. |
138 /// \pre \c i must be in the heap. |
123 /// \param i The item. |
|
124 Prio operator[](const Item &i) const {} |
139 Prio operator[](const Item &i) const {} |
125 |
140 |
126 /// \brief Sets the priority of an item or inserts it, if it is |
141 /// \brief Sets the priority of an item or inserts it, if it is |
127 /// not stored in the heap. |
142 /// not stored in the heap. |
128 /// |
143 /// |
135 void set(const Item &i, const Prio &p) {} |
150 void set(const Item &i, const Prio &p) {} |
136 |
151 |
137 /// \brief Decreases the priority of an item to the given value. |
152 /// \brief Decreases the priority of an item to the given value. |
138 /// |
153 /// |
139 /// Decreases the priority of an item to the given value. |
154 /// Decreases the priority of an item to the given value. |
|
155 /// \param i The item. |
|
156 /// \param p The priority. |
140 /// \pre \c i must be stored in the heap with priority at least \c p. |
157 /// \pre \c i must be stored in the heap with priority at least \c p. |
|
158 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. |
141 /// \param i The item. |
163 /// \param i The item. |
142 /// \param p The priority. |
164 /// \param p The priority. |
143 void decrease(const Item &i, const Prio &p) {} |
|
144 |
|
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. |
165 /// \pre \c i must be stored in the heap with priority at most \c p. |
149 /// \param i The item. |
|
150 /// \param p The priority. |
|
151 void increase(const Item &i, const Prio &p) {} |
166 void increase(const Item &i, const Prio &p) {} |
152 |
167 |
153 /// \brief Returns if an item is in, has already been in, or has |
168 /// \brief Returns if an item is in, has already been in, or has |
154 /// never been in the heap. |
169 /// never been in the heap. |
155 /// |
170 /// |