1.1 --- a/lemon/bin_heap.h Thu Jun 11 22:16:11 2009 +0200
1.2 +++ b/lemon/bin_heap.h Thu Jun 11 23:13:24 2009 +0200
1.3 @@ -33,23 +33,23 @@
1.4 ///
1.5 ///\brief A Binary Heap implementation.
1.6 ///
1.7 - ///This class implements the \e binary \e heap data structure.
1.8 - ///
1.9 + ///This class implements the \e binary \e heap data structure.
1.10 + ///
1.11 ///A \e heap is a data structure for storing items with specified values
1.12 ///called \e priorities in such a way that finding the item with minimum
1.13 - ///priority is efficient. \c Comp specifies the ordering of the priorities.
1.14 + ///priority is efficient. \c CMP specifies the ordering of the priorities.
1.15 ///In a heap one can change the priority of an item, add or erase an
1.16 ///item, etc.
1.17 ///
1.18 ///\tparam PR Type of the priority of the items.
1.19 ///\tparam IM A read and writable item map with int values, used internally
1.20 ///to handle the cross references.
1.21 - ///\tparam Comp A functor class for the ordering of the priorities.
1.22 + ///\tparam CMP A functor class for the ordering of the priorities.
1.23 ///The default is \c std::less<PR>.
1.24 ///
1.25 ///\sa FibHeap
1.26 ///\sa Dijkstra
1.27 - template <typename PR, typename IM, typename Comp = std::less<PR> >
1.28 + template <typename PR, typename IM, typename CMP = std::less<PR> >
1.29 class BinHeap {
1.30
1.31 public:
1.32 @@ -62,7 +62,7 @@
1.33 ///\e
1.34 typedef std::pair<Item,Prio> Pair;
1.35 ///\e
1.36 - typedef Comp Compare;
1.37 + typedef CMP Compare;
1.38
1.39 /// \brief Type to represent the items states.
1.40 ///
2.1 --- a/lemon/bucket_heap.h Thu Jun 11 22:16:11 2009 +0200
2.2 +++ b/lemon/bucket_heap.h Thu Jun 11 23:13:24 2009 +0200
2.3 @@ -31,7 +31,7 @@
2.4
2.5 namespace _bucket_heap_bits {
2.6
2.7 - template <bool minimize>
2.8 + template <bool MIN>
2.9 struct DirectionTraits {
2.10 static bool less(int left, int right) {
2.11 return left < right;
2.12 @@ -65,26 +65,27 @@
2.13 /// \f$ [0..C) \f$ range a list of items. So it should be used only when
2.14 /// the priorities are small. It is not intended to use as dijkstra heap.
2.15 ///
2.16 - /// \param _ItemIntMap A read and writable Item int map, used internally
2.17 + /// \param IM A read and write Item int map, used internally
2.18 /// to handle the cross references.
2.19 - /// \param minimize If the given parameter is true then the heap gives back
2.20 - /// the lowest priority.
2.21 - template <typename _ItemIntMap, bool minimize = true>
2.22 + /// \param MIN If the given parameter is false then instead of the
2.23 + /// minimum value the maximum can be retrivied with the top() and
2.24 + /// prio() member functions.
2.25 + template <typename IM, bool MIN = true>
2.26 class BucketHeap {
2.27
2.28 public:
2.29 /// \e
2.30 - typedef typename _ItemIntMap::Key Item;
2.31 + typedef typename IM::Key Item;
2.32 /// \e
2.33 typedef int Prio;
2.34 /// \e
2.35 typedef std::pair<Item, Prio> Pair;
2.36 /// \e
2.37 - typedef _ItemIntMap ItemIntMap;
2.38 + typedef IM ItemIntMap;
2.39
2.40 private:
2.41
2.42 - typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
2.43 + typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
2.44
2.45 public:
2.46
2.47 @@ -94,32 +95,32 @@
2.48 /// "pre heap" or "post heap". The latter two are indifferent from the
2.49 /// heap's point of view, but may be useful to the user.
2.50 ///
2.51 - /// The ItemIntMap \e should be initialized in such way that it maps
2.52 - /// PRE_HEAP (-1) to any element to be put in the heap...
2.53 + /// The item-int map must be initialized in such way that it assigns
2.54 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
2.55 enum State {
2.56 - IN_HEAP = 0,
2.57 - PRE_HEAP = -1,
2.58 - POST_HEAP = -2
2.59 + IN_HEAP = 0, ///< = 0.
2.60 + PRE_HEAP = -1, ///< = -1.
2.61 + POST_HEAP = -2 ///< = -2.
2.62 };
2.63
2.64 public:
2.65 /// \brief The constructor.
2.66 ///
2.67 /// The constructor.
2.68 - /// \param _index should be given to the constructor, since it is used
2.69 + /// \param map should be given to the constructor, since it is used
2.70 /// internally to handle the cross references. The value of the map
2.71 /// should be PRE_HEAP (-1) for each element.
2.72 - explicit BucketHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
2.73 + explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
2.74
2.75 /// The number of items stored in the heap.
2.76 ///
2.77 /// \brief Returns the number of items stored in the heap.
2.78 - int size() const { return data.size(); }
2.79 + int size() const { return _data.size(); }
2.80
2.81 /// \brief Checks if the heap stores no items.
2.82 ///
2.83 /// Returns \c true if and only if the heap stores no items.
2.84 - bool empty() const { return data.empty(); }
2.85 + bool empty() const { return _data.empty(); }
2.86
2.87 /// \brief Make empty this heap.
2.88 ///
2.89 @@ -128,48 +129,48 @@
2.90 /// should first clear the heap and after that you should set the
2.91 /// cross reference map for each item to \c PRE_HEAP.
2.92 void clear() {
2.93 - data.clear(); first.clear(); minimal = 0;
2.94 + _data.clear(); _first.clear(); _minimum = 0;
2.95 }
2.96
2.97 private:
2.98
2.99 void relocate_last(int idx) {
2.100 - if (idx + 1 < int(data.size())) {
2.101 - data[idx] = data.back();
2.102 - if (data[idx].prev != -1) {
2.103 - data[data[idx].prev].next = idx;
2.104 + if (idx + 1 < int(_data.size())) {
2.105 + _data[idx] = _data.back();
2.106 + if (_data[idx].prev != -1) {
2.107 + _data[_data[idx].prev].next = idx;
2.108 } else {
2.109 - first[data[idx].value] = idx;
2.110 + _first[_data[idx].value] = idx;
2.111 }
2.112 - if (data[idx].next != -1) {
2.113 - data[data[idx].next].prev = idx;
2.114 + if (_data[idx].next != -1) {
2.115 + _data[_data[idx].next].prev = idx;
2.116 }
2.117 - index[data[idx].item] = idx;
2.118 + _iim[_data[idx].item] = idx;
2.119 }
2.120 - data.pop_back();
2.121 + _data.pop_back();
2.122 }
2.123
2.124 void unlace(int idx) {
2.125 - if (data[idx].prev != -1) {
2.126 - data[data[idx].prev].next = data[idx].next;
2.127 + if (_data[idx].prev != -1) {
2.128 + _data[_data[idx].prev].next = _data[idx].next;
2.129 } else {
2.130 - first[data[idx].value] = data[idx].next;
2.131 + _first[_data[idx].value] = _data[idx].next;
2.132 }
2.133 - if (data[idx].next != -1) {
2.134 - data[data[idx].next].prev = data[idx].prev;
2.135 + if (_data[idx].next != -1) {
2.136 + _data[_data[idx].next].prev = _data[idx].prev;
2.137 }
2.138 }
2.139
2.140 void lace(int idx) {
2.141 - if (int(first.size()) <= data[idx].value) {
2.142 - first.resize(data[idx].value + 1, -1);
2.143 + if (int(_first.size()) <= _data[idx].value) {
2.144 + _first.resize(_data[idx].value + 1, -1);
2.145 }
2.146 - data[idx].next = first[data[idx].value];
2.147 - if (data[idx].next != -1) {
2.148 - data[data[idx].next].prev = idx;
2.149 + _data[idx].next = _first[_data[idx].value];
2.150 + if (_data[idx].next != -1) {
2.151 + _data[_data[idx].next].prev = idx;
2.152 }
2.153 - first[data[idx].value] = idx;
2.154 - data[idx].prev = -1;
2.155 + _first[_data[idx].value] = idx;
2.156 + _data[idx].prev = -1;
2.157 }
2.158
2.159 public:
2.160 @@ -187,12 +188,12 @@
2.161 /// \param i The item to insert.
2.162 /// \param p The priority of the item.
2.163 void push(const Item &i, const Prio &p) {
2.164 - int idx = data.size();
2.165 - index[i] = idx;
2.166 - data.push_back(BucketItem(i, p));
2.167 + int idx = _data.size();
2.168 + _iim[i] = idx;
2.169 + _data.push_back(BucketItem(i, p));
2.170 lace(idx);
2.171 - if (Direction::less(p, minimal)) {
2.172 - minimal = p;
2.173 + if (Direction::less(p, _minimum)) {
2.174 + _minimum = p;
2.175 }
2.176 }
2.177
2.178 @@ -201,10 +202,10 @@
2.179 /// This method returns the item with minimum priority.
2.180 /// \pre The heap must be nonempty.
2.181 Item top() const {
2.182 - while (first[minimal] == -1) {
2.183 - Direction::increase(minimal);
2.184 + while (_first[_minimum] == -1) {
2.185 + Direction::increase(_minimum);
2.186 }
2.187 - return data[first[minimal]].item;
2.188 + return _data[_first[_minimum]].item;
2.189 }
2.190
2.191 /// \brief Returns the minimum priority.
2.192 @@ -212,10 +213,10 @@
2.193 /// It returns the minimum priority.
2.194 /// \pre The heap must be nonempty.
2.195 Prio prio() const {
2.196 - while (first[minimal] == -1) {
2.197 - Direction::increase(minimal);
2.198 + while (_first[_minimum] == -1) {
2.199 + Direction::increase(_minimum);
2.200 }
2.201 - return minimal;
2.202 + return _minimum;
2.203 }
2.204
2.205 /// \brief Deletes the item with minimum priority.
2.206 @@ -223,11 +224,11 @@
2.207 /// This method deletes the item with minimum priority from the heap.
2.208 /// \pre The heap must be non-empty.
2.209 void pop() {
2.210 - while (first[minimal] == -1) {
2.211 - Direction::increase(minimal);
2.212 + while (_first[_minimum] == -1) {
2.213 + Direction::increase(_minimum);
2.214 }
2.215 - int idx = first[minimal];
2.216 - index[data[idx].item] = -2;
2.217 + int idx = _first[_minimum];
2.218 + _iim[_data[idx].item] = -2;
2.219 unlace(idx);
2.220 relocate_last(idx);
2.221 }
2.222 @@ -238,8 +239,8 @@
2.223 /// already stored in the heap.
2.224 /// \param i The item to erase.
2.225 void erase(const Item &i) {
2.226 - int idx = index[i];
2.227 - index[data[idx].item] = -2;
2.228 + int idx = _iim[i];
2.229 + _iim[_data[idx].item] = -2;
2.230 unlace(idx);
2.231 relocate_last(idx);
2.232 }
2.233 @@ -251,8 +252,8 @@
2.234 /// \pre \c i must be in the heap.
2.235 /// \param i The item.
2.236 Prio operator[](const Item &i) const {
2.237 - int idx = index[i];
2.238 - return data[idx].value;
2.239 + int idx = _iim[i];
2.240 + return _data[idx].value;
2.241 }
2.242
2.243 /// \brief \c i gets to the heap with priority \c p independently
2.244 @@ -263,10 +264,10 @@
2.245 /// \param i The item.
2.246 /// \param p The priority.
2.247 void set(const Item &i, const Prio &p) {
2.248 - int idx = index[i];
2.249 + int idx = _iim[i];
2.250 if (idx < 0) {
2.251 push(i, p);
2.252 - } else if (Direction::less(p, data[idx].value)) {
2.253 + } else if (Direction::less(p, _data[idx].value)) {
2.254 decrease(i, p);
2.255 } else {
2.256 increase(i, p);
2.257 @@ -281,11 +282,11 @@
2.258 /// \param i The item.
2.259 /// \param p The priority.
2.260 void decrease(const Item &i, const Prio &p) {
2.261 - int idx = index[i];
2.262 + int idx = _iim[i];
2.263 unlace(idx);
2.264 - data[idx].value = p;
2.265 - if (Direction::less(p, minimal)) {
2.266 - minimal = p;
2.267 + _data[idx].value = p;
2.268 + if (Direction::less(p, _minimum)) {
2.269 + _minimum = p;
2.270 }
2.271 lace(idx);
2.272 }
2.273 @@ -298,9 +299,9 @@
2.274 /// \param i The item.
2.275 /// \param p The priority.
2.276 void increase(const Item &i, const Prio &p) {
2.277 - int idx = index[i];
2.278 + int idx = _iim[i];
2.279 unlace(idx);
2.280 - data[idx].value = p;
2.281 + _data[idx].value = p;
2.282 lace(idx);
2.283 }
2.284
2.285 @@ -313,7 +314,7 @@
2.286 /// get back to the heap again.
2.287 /// \param i The item.
2.288 State state(const Item &i) const {
2.289 - int idx = index[i];
2.290 + int idx = _iim[i];
2.291 if (idx >= 0) idx = 0;
2.292 return State(idx);
2.293 }
2.294 @@ -332,7 +333,7 @@
2.295 if (state(i) == IN_HEAP) {
2.296 erase(i);
2.297 }
2.298 - index[i] = st;
2.299 + _iim[i] = st;
2.300 break;
2.301 case IN_HEAP:
2.302 break;
2.303 @@ -351,10 +352,10 @@
2.304 int prev, next;
2.305 };
2.306
2.307 - ItemIntMap& index;
2.308 - std::vector<int> first;
2.309 - std::vector<BucketItem> data;
2.310 - mutable int minimal;
2.311 + ItemIntMap& _iim;
2.312 + std::vector<int> _first;
2.313 + std::vector<BucketItem> _data;
2.314 + mutable int _minimum;
2.315
2.316 }; // class BucketHeap
2.317
2.318 @@ -370,24 +371,25 @@
2.319 /// other way it does not support erasing each elements just the
2.320 /// minimal and it does not supports key increasing, decreasing.
2.321 ///
2.322 - /// \param _ItemIntMap A read and writable Item int map, used internally
2.323 + /// \param IM A read and write Item int map, used internally
2.324 /// to handle the cross references.
2.325 - /// \param minimize If the given parameter is true then the heap gives back
2.326 - /// the lowest priority.
2.327 + /// \param MIN If the given parameter is false then instead of the
2.328 + /// minimum value the maximum can be retrivied with the top() and
2.329 + /// prio() member functions.
2.330 ///
2.331 /// \sa BucketHeap
2.332 - template <typename _ItemIntMap, bool minimize = true >
2.333 + template <typename IM, bool MIN = true >
2.334 class SimpleBucketHeap {
2.335
2.336 public:
2.337 - typedef typename _ItemIntMap::Key Item;
2.338 + typedef typename IM::Key Item;
2.339 typedef int Prio;
2.340 typedef std::pair<Item, Prio> Pair;
2.341 - typedef _ItemIntMap ItemIntMap;
2.342 + typedef IM ItemIntMap;
2.343
2.344 private:
2.345
2.346 - typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
2.347 + typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
2.348
2.349 public:
2.350
2.351 @@ -397,12 +399,12 @@
2.352 /// "pre heap" or "post heap". The latter two are indifferent from the
2.353 /// heap's point of view, but may be useful to the user.
2.354 ///
2.355 - /// The ItemIntMap \e should be initialized in such way that it maps
2.356 - /// PRE_HEAP (-1) to any element to be put in the heap...
2.357 + /// The item-int map must be initialized in such way that it assigns
2.358 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
2.359 enum State {
2.360 - IN_HEAP = 0,
2.361 - PRE_HEAP = -1,
2.362 - POST_HEAP = -2
2.363 + IN_HEAP = 0, ///< = 0.
2.364 + PRE_HEAP = -1, ///< = -1.
2.365 + POST_HEAP = -2 ///< = -2.
2.366 };
2.367
2.368 public:
2.369 @@ -410,21 +412,21 @@
2.370 /// \brief The constructor.
2.371 ///
2.372 /// The constructor.
2.373 - /// \param _index should be given to the constructor, since it is used
2.374 + /// \param map should be given to the constructor, since it is used
2.375 /// internally to handle the cross references. The value of the map
2.376 /// should be PRE_HEAP (-1) for each element.
2.377 - explicit SimpleBucketHeap(ItemIntMap &_index)
2.378 - : index(_index), free(-1), num(0), minimal(0) {}
2.379 + explicit SimpleBucketHeap(ItemIntMap &map)
2.380 + : _iim(map), _free(-1), _num(0), _minimum(0) {}
2.381
2.382 /// \brief Returns the number of items stored in the heap.
2.383 ///
2.384 /// The number of items stored in the heap.
2.385 - int size() const { return num; }
2.386 + int size() const { return _num; }
2.387
2.388 /// \brief Checks if the heap stores no items.
2.389 ///
2.390 /// Returns \c true if and only if the heap stores no items.
2.391 - bool empty() const { return num == 0; }
2.392 + bool empty() const { return _num == 0; }
2.393
2.394 /// \brief Make empty this heap.
2.395 ///
2.396 @@ -433,7 +435,7 @@
2.397 /// should first clear the heap and after that you should set the
2.398 /// cross reference map for each item to \c PRE_HEAP.
2.399 void clear() {
2.400 - data.clear(); first.clear(); free = -1; num = 0; minimal = 0;
2.401 + _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
2.402 }
2.403
2.404 /// \brief Insert a pair of item and priority into the heap.
2.405 @@ -451,22 +453,22 @@
2.406 /// \param p The priority of the item.
2.407 void push(const Item &i, const Prio &p) {
2.408 int idx;
2.409 - if (free == -1) {
2.410 - idx = data.size();
2.411 - data.push_back(BucketItem(i));
2.412 + if (_free == -1) {
2.413 + idx = _data.size();
2.414 + _data.push_back(BucketItem(i));
2.415 } else {
2.416 - idx = free;
2.417 - free = data[idx].next;
2.418 - data[idx].item = i;
2.419 + idx = _free;
2.420 + _free = _data[idx].next;
2.421 + _data[idx].item = i;
2.422 }
2.423 - index[i] = idx;
2.424 - if (p >= int(first.size())) first.resize(p + 1, -1);
2.425 - data[idx].next = first[p];
2.426 - first[p] = idx;
2.427 - if (Direction::less(p, minimal)) {
2.428 - minimal = p;
2.429 + _iim[i] = idx;
2.430 + if (p >= int(_first.size())) _first.resize(p + 1, -1);
2.431 + _data[idx].next = _first[p];
2.432 + _first[p] = idx;
2.433 + if (Direction::less(p, _minimum)) {
2.434 + _minimum = p;
2.435 }
2.436 - ++num;
2.437 + ++_num;
2.438 }
2.439
2.440 /// \brief Returns the item with minimum priority.
2.441 @@ -474,10 +476,10 @@
2.442 /// This method returns the item with minimum priority.
2.443 /// \pre The heap must be nonempty.
2.444 Item top() const {
2.445 - while (first[minimal] == -1) {
2.446 - Direction::increase(minimal);
2.447 + while (_first[_minimum] == -1) {
2.448 + Direction::increase(_minimum);
2.449 }
2.450 - return data[first[minimal]].item;
2.451 + return _data[_first[_minimum]].item;
2.452 }
2.453
2.454 /// \brief Returns the minimum priority.
2.455 @@ -485,10 +487,10 @@
2.456 /// It returns the minimum priority.
2.457 /// \pre The heap must be nonempty.
2.458 Prio prio() const {
2.459 - while (first[minimal] == -1) {
2.460 - Direction::increase(minimal);
2.461 + while (_first[_minimum] == -1) {
2.462 + Direction::increase(_minimum);
2.463 }
2.464 - return minimal;
2.465 + return _minimum;
2.466 }
2.467
2.468 /// \brief Deletes the item with minimum priority.
2.469 @@ -496,15 +498,15 @@
2.470 /// This method deletes the item with minimum priority from the heap.
2.471 /// \pre The heap must be non-empty.
2.472 void pop() {
2.473 - while (first[minimal] == -1) {
2.474 - Direction::increase(minimal);
2.475 + while (_first[_minimum] == -1) {
2.476 + Direction::increase(_minimum);
2.477 }
2.478 - int idx = first[minimal];
2.479 - index[data[idx].item] = -2;
2.480 - first[minimal] = data[idx].next;
2.481 - data[idx].next = free;
2.482 - free = idx;
2.483 - --num;
2.484 + int idx = _first[_minimum];
2.485 + _iim[_data[idx].item] = -2;
2.486 + _first[_minimum] = _data[idx].next;
2.487 + _data[idx].next = _free;
2.488 + _free = idx;
2.489 + --_num;
2.490 }
2.491
2.492 /// \brief Returns the priority of \c i.
2.493 @@ -516,13 +518,13 @@
2.494 /// \pre \c i must be in the heap.
2.495 /// \param i The item.
2.496 Prio operator[](const Item &i) const {
2.497 - for (int k = 0; k < first.size(); ++k) {
2.498 - int idx = first[k];
2.499 + for (int k = 0; k < _first.size(); ++k) {
2.500 + int idx = _first[k];
2.501 while (idx != -1) {
2.502 - if (data[idx].item == i) {
2.503 + if (_data[idx].item == i) {
2.504 return k;
2.505 }
2.506 - idx = data[idx].next;
2.507 + idx = _data[idx].next;
2.508 }
2.509 }
2.510 return -1;
2.511 @@ -537,7 +539,7 @@
2.512 /// get back to the heap again.
2.513 /// \param i The item.
2.514 State state(const Item &i) const {
2.515 - int idx = index[i];
2.516 + int idx = _iim[i];
2.517 if (idx >= 0) idx = 0;
2.518 return State(idx);
2.519 }
2.520 @@ -552,11 +554,11 @@
2.521 int next;
2.522 };
2.523
2.524 - ItemIntMap& index;
2.525 - std::vector<int> first;
2.526 - std::vector<BucketItem> data;
2.527 - int free, num;
2.528 - mutable int minimal;
2.529 + ItemIntMap& _iim;
2.530 + std::vector<int> _first;
2.531 + std::vector<BucketItem> _data;
2.532 + int _free, _num;
2.533 + mutable int _minimum;
2.534
2.535 }; // class SimpleBucketHeap
2.536
3.1 --- a/lemon/fib_heap.h Thu Jun 11 22:16:11 2009 +0200
3.2 +++ b/lemon/fib_heap.h Thu Jun 11 23:13:24 2009 +0200
3.3 @@ -36,87 +36,88 @@
3.4 ///This class implements the \e Fibonacci \e heap data structure. A \e heap
3.5 ///is a data structure for storing items with specified values called \e
3.6 ///priorities in such a way that finding the item with minimum priority is
3.7 - ///efficient. \c Compare specifies the ordering of the priorities. In a heap
3.8 + ///efficient. \c CMP specifies the ordering of the priorities. In a heap
3.9 ///one can change the priority of an item, add or erase an item, etc.
3.10 ///
3.11 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
3.12 ///heap. In case of many calls to these operations, it is better to use a
3.13 ///\ref BinHeap "binary heap".
3.14 ///
3.15 - ///\param _Prio Type of the priority of the items.
3.16 - ///\param _ItemIntMap A read and writable Item int map, used internally
3.17 + ///\param PRIO Type of the priority of the items.
3.18 + ///\param IM A read and writable Item int map, used internally
3.19 ///to handle the cross references.
3.20 - ///\param _Compare A class for the ordering of the priorities. The
3.21 - ///default is \c std::less<_Prio>.
3.22 + ///\param CMP A class for the ordering of the priorities. The
3.23 + ///default is \c std::less<PRIO>.
3.24 ///
3.25 ///\sa BinHeap
3.26 ///\sa Dijkstra
3.27 #ifdef DOXYGEN
3.28 - template <typename _Prio,
3.29 - typename _ItemIntMap,
3.30 - typename _Compare>
3.31 + template <typename PRIO, typename IM, typename CMP>
3.32 #else
3.33 - template <typename _Prio,
3.34 - typename _ItemIntMap,
3.35 - typename _Compare = std::less<_Prio> >
3.36 + template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
3.37 #endif
3.38 class FibHeap {
3.39 public:
3.40 ///\e
3.41 - typedef _ItemIntMap ItemIntMap;
3.42 + typedef IM ItemIntMap;
3.43 ///\e
3.44 - typedef _Prio Prio;
3.45 + typedef PRIO Prio;
3.46 ///\e
3.47 typedef typename ItemIntMap::Key Item;
3.48 ///\e
3.49 typedef std::pair<Item,Prio> Pair;
3.50 ///\e
3.51 - typedef _Compare Compare;
3.52 + typedef CMP Compare;
3.53
3.54 private:
3.55 - class store;
3.56 + class Store;
3.57
3.58 - std::vector<store> container;
3.59 - int minimum;
3.60 - ItemIntMap &iimap;
3.61 - Compare comp;
3.62 - int num_items;
3.63 + std::vector<Store> _data;
3.64 + int _minimum;
3.65 + ItemIntMap &_iim;
3.66 + Compare _comp;
3.67 + int _num;
3.68
3.69 public:
3.70 - ///Status of the nodes
3.71 +
3.72 + /// \brief Type to represent the items states.
3.73 + ///
3.74 + /// Each Item element have a state associated to it. It may be "in heap",
3.75 + /// "pre heap" or "post heap". The latter two are indifferent from the
3.76 + /// heap's point of view, but may be useful to the user.
3.77 + ///
3.78 + /// The item-int map must be initialized in such way that it assigns
3.79 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
3.80 enum State {
3.81 - ///The node is in the heap
3.82 - IN_HEAP = 0,
3.83 - ///The node has never been in the heap
3.84 - PRE_HEAP = -1,
3.85 - ///The node was in the heap but it got out of it
3.86 - POST_HEAP = -2
3.87 + IN_HEAP = 0, ///< = 0.
3.88 + PRE_HEAP = -1, ///< = -1.
3.89 + POST_HEAP = -2 ///< = -2.
3.90 };
3.91
3.92 /// \brief The constructor
3.93 ///
3.94 - /// \c _iimap should be given to the constructor, since it is
3.95 + /// \c map should be given to the constructor, since it is
3.96 /// used internally to handle the cross references.
3.97 - explicit FibHeap(ItemIntMap &_iimap)
3.98 - : minimum(0), iimap(_iimap), num_items() {}
3.99 + explicit FibHeap(ItemIntMap &map)
3.100 + : _minimum(0), _iim(map), _num() {}
3.101
3.102 /// \brief The constructor
3.103 ///
3.104 - /// \c _iimap should be given to the constructor, since it is used
3.105 - /// internally to handle the cross references. \c _comp is an
3.106 + /// \c map should be given to the constructor, since it is used
3.107 + /// internally to handle the cross references. \c comp is an
3.108 /// object for ordering of the priorities.
3.109 - FibHeap(ItemIntMap &_iimap, const Compare &_comp)
3.110 - : minimum(0), iimap(_iimap), comp(_comp), num_items() {}
3.111 + FibHeap(ItemIntMap &map, const Compare &comp)
3.112 + : _minimum(0), _iim(map), _comp(comp), _num() {}
3.113
3.114 /// \brief The number of items stored in the heap.
3.115 ///
3.116 /// Returns the number of items stored in the heap.
3.117 - int size() const { return num_items; }
3.118 + int size() const { return _num; }
3.119
3.120 /// \brief Checks if the heap stores no items.
3.121 ///
3.122 /// Returns \c true if and only if the heap stores no items.
3.123 - bool empty() const { return num_items==0; }
3.124 + bool empty() const { return _num==0; }
3.125
3.126 /// \brief Make empty this heap.
3.127 ///
3.128 @@ -125,7 +126,7 @@
3.129 /// should first clear the heap and after that you should set the
3.130 /// cross reference map for each item to \c PRE_HEAP.
3.131 void clear() {
3.132 - container.clear(); minimum = 0; num_items = 0;
3.133 + _data.clear(); _minimum = 0; _num = 0;
3.134 }
3.135
3.136 /// \brief \c item gets to the heap with priority \c value independently
3.137 @@ -135,10 +136,10 @@
3.138 /// stored in the heap and it calls \ref decrease(\c item, \c value) or
3.139 /// \ref increase(\c item, \c value) otherwise.
3.140 void set (const Item& item, const Prio& value) {
3.141 - int i=iimap[item];
3.142 - if ( i >= 0 && container[i].in ) {
3.143 - if ( comp(value, container[i].prio) ) decrease(item, value);
3.144 - if ( comp(container[i].prio, value) ) increase(item, value);
3.145 + int i=_iim[item];
3.146 + if ( i >= 0 && _data[i].in ) {
3.147 + if ( _comp(value, _data[i].prio) ) decrease(item, value);
3.148 + if ( _comp(_data[i].prio, value) ) increase(item, value);
3.149 } else push(item, value);
3.150 }
3.151
3.152 @@ -147,33 +148,33 @@
3.153 /// Adds \c item to the heap with priority \c value.
3.154 /// \pre \c item must not be stored in the heap.
3.155 void push (const Item& item, const Prio& value) {
3.156 - int i=iimap[item];
3.157 + int i=_iim[item];
3.158 if ( i < 0 ) {
3.159 - int s=container.size();
3.160 - iimap.set( item, s );
3.161 - store st;
3.162 + int s=_data.size();
3.163 + _iim.set( item, s );
3.164 + Store st;
3.165 st.name=item;
3.166 - container.push_back(st);
3.167 + _data.push_back(st);
3.168 i=s;
3.169 } else {
3.170 - container[i].parent=container[i].child=-1;
3.171 - container[i].degree=0;
3.172 - container[i].in=true;
3.173 - container[i].marked=false;
3.174 + _data[i].parent=_data[i].child=-1;
3.175 + _data[i].degree=0;
3.176 + _data[i].in=true;
3.177 + _data[i].marked=false;
3.178 }
3.179
3.180 - if ( num_items ) {
3.181 - container[container[minimum].right_neighbor].left_neighbor=i;
3.182 - container[i].right_neighbor=container[minimum].right_neighbor;
3.183 - container[minimum].right_neighbor=i;
3.184 - container[i].left_neighbor=minimum;
3.185 - if ( comp( value, container[minimum].prio) ) minimum=i;
3.186 + if ( _num ) {
3.187 + _data[_data[_minimum].right_neighbor].left_neighbor=i;
3.188 + _data[i].right_neighbor=_data[_minimum].right_neighbor;
3.189 + _data[_minimum].right_neighbor=i;
3.190 + _data[i].left_neighbor=_minimum;
3.191 + if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
3.192 } else {
3.193 - container[i].right_neighbor=container[i].left_neighbor=i;
3.194 - minimum=i;
3.195 + _data[i].right_neighbor=_data[i].left_neighbor=i;
3.196 + _minimum=i;
3.197 }
3.198 - container[i].prio=value;
3.199 - ++num_items;
3.200 + _data[i].prio=value;
3.201 + ++_num;
3.202 }
3.203
3.204 /// \brief Returns the item with minimum priority relative to \c Compare.
3.205 @@ -181,20 +182,20 @@
3.206 /// This method returns the item with minimum priority relative to \c
3.207 /// Compare.
3.208 /// \pre The heap must be nonempty.
3.209 - Item top() const { return container[minimum].name; }
3.210 + Item top() const { return _data[_minimum].name; }
3.211
3.212 /// \brief Returns the minimum priority relative to \c Compare.
3.213 ///
3.214 /// It returns the minimum priority relative to \c Compare.
3.215 /// \pre The heap must be nonempty.
3.216 - const Prio& prio() const { return container[minimum].prio; }
3.217 + const Prio& prio() const { return _data[_minimum].prio; }
3.218
3.219 /// \brief Returns the priority of \c item.
3.220 ///
3.221 /// It returns the priority of \c item.
3.222 /// \pre \c item must be in the heap.
3.223 const Prio& operator[](const Item& item) const {
3.224 - return container[iimap[item]].prio;
3.225 + return _data[_iim[item]].prio;
3.226 }
3.227
3.228 /// \brief Deletes the item with minimum priority relative to \c Compare.
3.229 @@ -204,33 +205,33 @@
3.230 /// \pre The heap must be non-empty.
3.231 void pop() {
3.232 /*The first case is that there are only one root.*/
3.233 - if ( container[minimum].left_neighbor==minimum ) {
3.234 - container[minimum].in=false;
3.235 - if ( container[minimum].degree!=0 ) {
3.236 - makeroot(container[minimum].child);
3.237 - minimum=container[minimum].child;
3.238 + if ( _data[_minimum].left_neighbor==_minimum ) {
3.239 + _data[_minimum].in=false;
3.240 + if ( _data[_minimum].degree!=0 ) {
3.241 + makeroot(_data[_minimum].child);
3.242 + _minimum=_data[_minimum].child;
3.243 balance();
3.244 }
3.245 } else {
3.246 - int right=container[minimum].right_neighbor;
3.247 - unlace(minimum);
3.248 - container[minimum].in=false;
3.249 - if ( container[minimum].degree > 0 ) {
3.250 - int left=container[minimum].left_neighbor;
3.251 - int child=container[minimum].child;
3.252 - int last_child=container[child].left_neighbor;
3.253 + int right=_data[_minimum].right_neighbor;
3.254 + unlace(_minimum);
3.255 + _data[_minimum].in=false;
3.256 + if ( _data[_minimum].degree > 0 ) {
3.257 + int left=_data[_minimum].left_neighbor;
3.258 + int child=_data[_minimum].child;
3.259 + int last_child=_data[child].left_neighbor;
3.260
3.261 makeroot(child);
3.262
3.263 - container[left].right_neighbor=child;
3.264 - container[child].left_neighbor=left;
3.265 - container[right].left_neighbor=last_child;
3.266 - container[last_child].right_neighbor=right;
3.267 + _data[left].right_neighbor=child;
3.268 + _data[child].left_neighbor=left;
3.269 + _data[right].left_neighbor=last_child;
3.270 + _data[last_child].right_neighbor=right;
3.271 }
3.272 - minimum=right;
3.273 + _minimum=right;
3.274 balance();
3.275 } // the case where there are more roots
3.276 - --num_items;
3.277 + --_num;
3.278 }
3.279
3.280 /// \brief Deletes \c item from the heap.
3.281 @@ -238,15 +239,15 @@
3.282 /// This method deletes \c item from the heap, if \c item was already
3.283 /// stored in the heap. It is quite inefficient in Fibonacci heaps.
3.284 void erase (const Item& item) {
3.285 - int i=iimap[item];
3.286 + int i=_iim[item];
3.287
3.288 - if ( i >= 0 && container[i].in ) {
3.289 - if ( container[i].parent!=-1 ) {
3.290 - int p=container[i].parent;
3.291 + if ( i >= 0 && _data[i].in ) {
3.292 + if ( _data[i].parent!=-1 ) {
3.293 + int p=_data[i].parent;
3.294 cut(i,p);
3.295 cascade(p);
3.296 }
3.297 - minimum=i; //As if its prio would be -infinity
3.298 + _minimum=i; //As if its prio would be -infinity
3.299 pop();
3.300 }
3.301 }
3.302 @@ -257,15 +258,15 @@
3.303 /// \pre \c item must be stored in the heap with priority at least \c
3.304 /// value relative to \c Compare.
3.305 void decrease (Item item, const Prio& value) {
3.306 - int i=iimap[item];
3.307 - container[i].prio=value;
3.308 - int p=container[i].parent;
3.309 + int i=_iim[item];
3.310 + _data[i].prio=value;
3.311 + int p=_data[i].parent;
3.312
3.313 - if ( p!=-1 && comp(value, container[p].prio) ) {
3.314 + if ( p!=-1 && _comp(value, _data[p].prio) ) {
3.315 cut(i,p);
3.316 cascade(p);
3.317 }
3.318 - if ( comp(value, container[minimum].prio) ) minimum=i;
3.319 + if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
3.320 }
3.321
3.322 /// \brief Increases the priority of \c item to \c value.
3.323 @@ -289,9 +290,9 @@
3.324 /// otherwise. In the latter case it is possible that \c item will
3.325 /// get back to the heap again.
3.326 State state(const Item &item) const {
3.327 - int i=iimap[item];
3.328 + int i=_iim[item];
3.329 if( i>=0 ) {
3.330 - if ( container[i].in ) i=0;
3.331 + if ( _data[i].in ) i=0;
3.332 else i=-2;
3.333 }
3.334 return State(i);
3.335 @@ -301,7 +302,7 @@
3.336 ///
3.337 /// Sets the state of the \c item in the heap. It can be used to
3.338 /// manually clear the heap when it is important to achive the
3.339 - /// better time complexity.
3.340 + /// better time _complexity.
3.341 /// \param i The item.
3.342 /// \param st The state. It should not be \c IN_HEAP.
3.343 void state(const Item& i, State st) {
3.344 @@ -311,7 +312,7 @@
3.345 if (state(i) == IN_HEAP) {
3.346 erase(i);
3.347 }
3.348 - iimap[i] = st;
3.349 + _iim[i] = st;
3.350 break;
3.351 case IN_HEAP:
3.352 break;
3.353 @@ -322,7 +323,7 @@
3.354
3.355 void balance() {
3.356
3.357 - int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
3.358 + int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1;
3.359
3.360 std::vector<int> A(maxdeg,-1);
3.361
3.362 @@ -330,18 +331,18 @@
3.363 *Recall that now minimum does not point to the minimum prio element.
3.364 *We set minimum to this during balance().
3.365 */
3.366 - int anchor=container[minimum].left_neighbor;
3.367 - int next=minimum;
3.368 + int anchor=_data[_minimum].left_neighbor;
3.369 + int next=_minimum;
3.370 bool end=false;
3.371
3.372 do {
3.373 int active=next;
3.374 if ( anchor==active ) end=true;
3.375 - int d=container[active].degree;
3.376 - next=container[active].right_neighbor;
3.377 + int d=_data[active].degree;
3.378 + next=_data[active].right_neighbor;
3.379
3.380 while (A[d]!=-1) {
3.381 - if( comp(container[active].prio, container[A[d]].prio) ) {
3.382 + if( _comp(_data[active].prio, _data[A[d]].prio) ) {
3.383 fuse(active,A[d]);
3.384 } else {
3.385 fuse(A[d],active);
3.386 @@ -354,21 +355,21 @@
3.387 } while ( !end );
3.388
3.389
3.390 - while ( container[minimum].parent >=0 )
3.391 - minimum=container[minimum].parent;
3.392 - int s=minimum;
3.393 - int m=minimum;
3.394 + while ( _data[_minimum].parent >=0 )
3.395 + _minimum=_data[_minimum].parent;
3.396 + int s=_minimum;
3.397 + int m=_minimum;
3.398 do {
3.399 - if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
3.400 - s=container[s].right_neighbor;
3.401 + if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
3.402 + s=_data[s].right_neighbor;
3.403 } while ( s != m );
3.404 }
3.405
3.406 void makeroot(int c) {
3.407 int s=c;
3.408 do {
3.409 - container[s].parent=-1;
3.410 - s=container[s].right_neighbor;
3.411 + _data[s].parent=-1;
3.412 + s=_data[s].right_neighbor;
3.413 } while ( s != c );
3.414 }
3.415
3.416 @@ -376,32 +377,32 @@
3.417 /*
3.418 *Replacing a from the children of b.
3.419 */
3.420 - --container[b].degree;
3.421 + --_data[b].degree;
3.422
3.423 - if ( container[b].degree !=0 ) {
3.424 - int child=container[b].child;
3.425 + if ( _data[b].degree !=0 ) {
3.426 + int child=_data[b].child;
3.427 if ( child==a )
3.428 - container[b].child=container[child].right_neighbor;
3.429 + _data[b].child=_data[child].right_neighbor;
3.430 unlace(a);
3.431 }
3.432
3.433
3.434 /*Lacing a to the roots.*/
3.435 - int right=container[minimum].right_neighbor;
3.436 - container[minimum].right_neighbor=a;
3.437 - container[a].left_neighbor=minimum;
3.438 - container[a].right_neighbor=right;
3.439 - container[right].left_neighbor=a;
3.440 + int right=_data[_minimum].right_neighbor;
3.441 + _data[_minimum].right_neighbor=a;
3.442 + _data[a].left_neighbor=_minimum;
3.443 + _data[a].right_neighbor=right;
3.444 + _data[right].left_neighbor=a;
3.445
3.446 - container[a].parent=-1;
3.447 - container[a].marked=false;
3.448 + _data[a].parent=-1;
3.449 + _data[a].marked=false;
3.450 }
3.451
3.452 void cascade(int a) {
3.453 - if ( container[a].parent!=-1 ) {
3.454 - int p=container[a].parent;
3.455 + if ( _data[a].parent!=-1 ) {
3.456 + int p=_data[a].parent;
3.457
3.458 - if ( container[a].marked==false ) container[a].marked=true;
3.459 + if ( _data[a].marked==false ) _data[a].marked=true;
3.460 else {
3.461 cut(a,p);
3.462 cascade(p);
3.463 @@ -413,38 +414,38 @@
3.464 unlace(b);
3.465
3.466 /*Lacing b under a.*/
3.467 - container[b].parent=a;
3.468 + _data[b].parent=a;
3.469
3.470 - if (container[a].degree==0) {
3.471 - container[b].left_neighbor=b;
3.472 - container[b].right_neighbor=b;
3.473 - container[a].child=b;
3.474 + if (_data[a].degree==0) {
3.475 + _data[b].left_neighbor=b;
3.476 + _data[b].right_neighbor=b;
3.477 + _data[a].child=b;
3.478 } else {
3.479 - int child=container[a].child;
3.480 - int last_child=container[child].left_neighbor;
3.481 - container[child].left_neighbor=b;
3.482 - container[b].right_neighbor=child;
3.483 - container[last_child].right_neighbor=b;
3.484 - container[b].left_neighbor=last_child;
3.485 + int child=_data[a].child;
3.486 + int last_child=_data[child].left_neighbor;
3.487 + _data[child].left_neighbor=b;
3.488 + _data[b].right_neighbor=child;
3.489 + _data[last_child].right_neighbor=b;
3.490 + _data[b].left_neighbor=last_child;
3.491 }
3.492
3.493 - ++container[a].degree;
3.494 + ++_data[a].degree;
3.495
3.496 - container[b].marked=false;
3.497 + _data[b].marked=false;
3.498 }
3.499
3.500 /*
3.501 *It is invoked only if a has siblings.
3.502 */
3.503 void unlace(int a) {
3.504 - int leftn=container[a].left_neighbor;
3.505 - int rightn=container[a].right_neighbor;
3.506 - container[leftn].right_neighbor=rightn;
3.507 - container[rightn].left_neighbor=leftn;
3.508 + int leftn=_data[a].left_neighbor;
3.509 + int rightn=_data[a].right_neighbor;
3.510 + _data[leftn].right_neighbor=rightn;
3.511 + _data[rightn].left_neighbor=leftn;
3.512 }
3.513
3.514
3.515 - class store {
3.516 + class Store {
3.517 friend class FibHeap;
3.518
3.519 Item name;
3.520 @@ -457,7 +458,7 @@
3.521 bool in;
3.522 Prio prio;
3.523
3.524 - store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
3.525 + Store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
3.526 };
3.527 };
3.528
4.1 --- a/lemon/radix_heap.h Thu Jun 11 22:16:11 2009 +0200
4.2 +++ b/lemon/radix_heap.h Thu Jun 11 23:13:24 2009 +0200
4.3 @@ -41,18 +41,18 @@
4.4 /// item, but the priority cannot be decreased under the last removed
4.5 /// item's priority.
4.6 ///
4.7 - /// \param _ItemIntMap A read and writable Item int map, used internally
4.8 + /// \param IM A read and writable Item int map, used internally
4.9 /// to handle the cross references.
4.10 ///
4.11 /// \see BinHeap
4.12 /// \see Dijkstra
4.13 - template <typename _ItemIntMap>
4.14 + template <typename IM>
4.15 class RadixHeap {
4.16
4.17 public:
4.18 - typedef typename _ItemIntMap::Key Item;
4.19 + typedef typename IM::Key Item;
4.20 typedef int Prio;
4.21 - typedef _ItemIntMap ItemIntMap;
4.22 + typedef IM ItemIntMap;
4.23
4.24 /// \brief Exception thrown by RadixHeap.
4.25 ///
4.26 @@ -99,7 +99,7 @@
4.27 std::vector<RadixItem> data;
4.28 std::vector<RadixBox> boxes;
4.29
4.30 - ItemIntMap &iim;
4.31 + ItemIntMap &_iim;
4.32
4.33
4.34 public:
4.35 @@ -107,14 +107,14 @@
4.36 ///
4.37 /// The constructor.
4.38 ///
4.39 - /// \param _iim It should be given to the constructor, since it is used
4.40 + /// \param map It should be given to the constructor, since it is used
4.41 /// internally to handle the cross references. The value of the map
4.42 /// should be PRE_HEAP (-1) for each element.
4.43 ///
4.44 /// \param minimal The initial minimal value of the heap.
4.45 /// \param capacity It determines the initial capacity of the heap.
4.46 - RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
4.47 - : iim(_iim) {
4.48 + RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
4.49 + : _iim(map) {
4.50 boxes.push_back(RadixBox(minimal, 1));
4.51 boxes.push_back(RadixBox(minimal + 1, 1));
4.52 while (lower(boxes.size() - 1, capacity + minimal - 1)) {
4.53 @@ -268,7 +268,7 @@
4.54 if (data[index].next != -1) {
4.55 data[data[index].next].prev = index;
4.56 }
4.57 - iim[data[index].item] = index;
4.58 + _iim[data[index].item] = index;
4.59 }
4.60 data.pop_back();
4.61 }
4.62 @@ -282,7 +282,7 @@
4.63 /// \param p The priority of the item.
4.64 void push(const Item &i, const Prio &p) {
4.65 int n = data.size();
4.66 - iim.set(i, n);
4.67 + _iim.set(i, n);
4.68 data.push_back(RadixItem(i, p));
4.69 while (lower(boxes.size() - 1, p)) {
4.70 extend();
4.71 @@ -316,7 +316,7 @@
4.72 void pop() {
4.73 moveDown();
4.74 int index = boxes[0].first;
4.75 - iim[data[index].item] = POST_HEAP;
4.76 + _iim[data[index].item] = POST_HEAP;
4.77 remove(index);
4.78 relocate_last(index);
4.79 }
4.80 @@ -327,8 +327,8 @@
4.81 /// already stored in the heap.
4.82 /// \param i The item to erase.
4.83 void erase(const Item &i) {
4.84 - int index = iim[i];
4.85 - iim[i] = POST_HEAP;
4.86 + int index = _iim[i];
4.87 + _iim[i] = POST_HEAP;
4.88 remove(index);
4.89 relocate_last(index);
4.90 }
4.91 @@ -339,7 +339,7 @@
4.92 /// \pre \c i must be in the heap.
4.93 /// \param i The item.
4.94 Prio operator[](const Item &i) const {
4.95 - int idx = iim[i];
4.96 + int idx = _iim[i];
4.97 return data[idx].prio;
4.98 }
4.99
4.100 @@ -352,7 +352,7 @@
4.101 /// \param i The item.
4.102 /// \param p The priority.
4.103 void set(const Item &i, const Prio &p) {
4.104 - int idx = iim[i];
4.105 + int idx = _iim[i];
4.106 if( idx < 0 ) {
4.107 push(i, p);
4.108 }
4.109 @@ -374,7 +374,7 @@
4.110 /// \param i The item.
4.111 /// \param p The priority.
4.112 void decrease(const Item &i, const Prio &p) {
4.113 - int idx = iim[i];
4.114 + int idx = _iim[i];
4.115 data[idx].prio = p;
4.116 bubble_down(idx);
4.117 }
4.118 @@ -386,7 +386,7 @@
4.119 /// \param i The item.
4.120 /// \param p The priority.
4.121 void increase(const Item &i, const Prio &p) {
4.122 - int idx = iim[i];
4.123 + int idx = _iim[i];
4.124 data[idx].prio = p;
4.125 bubble_up(idx);
4.126 }
4.127 @@ -400,7 +400,7 @@
4.128 /// get back to the heap again.
4.129 /// \param i The item.
4.130 State state(const Item &i) const {
4.131 - int s = iim[i];
4.132 + int s = _iim[i];
4.133 if( s >= 0 ) s = 0;
4.134 return State(s);
4.135 }
4.136 @@ -419,7 +419,7 @@
4.137 if (state(i) == IN_HEAP) {
4.138 erase(i);
4.139 }
4.140 - iim[i] = st;
4.141 + _iim[i] = st;
4.142 break;
4.143 case IN_HEAP:
4.144 break;