00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00023
00024 #ifndef LEMON_CONCEPT_HEAP_H
00025 #define LEMON_CONCEPT_HEAP_H
00026
00027 #include <lemon/invalid.h>
00028
00029 namespace lemon {
00030 namespace concept {
00033
00034
00039 template <typename Item, typename Prio, typename ItemIntMap>
00040 class Heap {
00041 public:
00042
00043
00052 enum state_enum {
00053 IN_HEAP = 0,
00054 PRE_HEAP = -1,
00055 POST_HEAP = -2
00056 };
00057
00064 explicit Heap(ItemIntMap &_iim) {}
00065
00069 int size() const { return 0; }
00070
00074 bool empty() const { return false; }
00075
00079 void clear();
00080
00086 void push(const Item &i, const Prio &p) {}
00087
00092 Item top() const {}
00093
00098 Prio prio() const {}
00099
00104 void pop() {}
00105
00111 void erase(const Item &i) {}
00112
00118 Prio operator[](const Item &i) const {}
00119
00128 void set(const Item &i, const Prio &p) {}
00129
00136 void decrease(const Item &i, const Prio &p) {}
00137
00145 void increase(const Item &i, const Prio &p) {}
00146
00155 state_enum state(const Item &i) const {}
00156
00164 void state(const Item& i, state_enum st) {}
00165
00166
00167 template <typename _Heap>
00168 struct Constraints {
00169 public:
00170
00171 void constraints() {
00172 Item item;
00173 Prio prio;
00174
00175 item=Item();
00176 prio=Prio();
00177
00178 ignore_unused_variable_warning(item);
00179 ignore_unused_variable_warning(prio);
00180
00181 typedef typename _Heap::state_enum state_enum;
00182 state_enum state;
00183
00184 ignore_unused_variable_warning(state);
00185
00186 _Heap heap1 = _Heap(map);
00187
00188 ignore_unused_variable_warning(heap1);
00189
00190 heap.push(item, prio);
00191
00192 prio = heap.prio();
00193 item = heap.top();
00194
00195 heap.pop();
00196
00197 heap.set(item, prio);
00198 heap.decrease(item, prio);
00199 heap.increase(item, prio);
00200 prio = heap[item];
00201
00202 heap.erase(item);
00203
00204 state = heap.state(item);
00205
00206 state = _Heap::PRE_HEAP;
00207 state = _Heap::IN_HEAP;
00208 state = _Heap::POST_HEAP;
00209
00210 heap.clear();
00211 }
00212
00213 _Heap& heap;
00214 ItemIntMap& map;
00215
00216 Constraints() : heap(0), map(0) {}
00217 };
00218 };
00219
00221 }
00222 }
00223 #endif // LEMON_CONCEPT_PATH_H