# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1260461425 -3600
# Node ID 76689f2fc02ded052e33c2ea083ac953d5b1b01e
# Parent 2305167d249124fae5c930f87ec4d020b2686851# Parent 994c7df296c94a4705d55e67858911b2e6991e86
Merge bugfix #330 to branch 1.1
diff -r 2305167d2491 -r 76689f2fc02d lemon/Makefile.am
--- a/lemon/Makefile.am Thu Nov 05 16:01:39 2009 +0100
+++ b/lemon/Makefile.am Thu Dec 10 17:10:25 2009 +0100
@@ -59,6 +59,7 @@
lemon/assert.h \
lemon/bfs.h \
lemon/bin_heap.h \
+ lemon/bucket_heap.h \
lemon/cbc.h \
lemon/circulation.h \
lemon/clp.h \
@@ -76,6 +77,7 @@
lemon/elevator.h \
lemon/error.h \
lemon/euler.h \
+ lemon/fib_heap.h \
lemon/full_graph.h \
lemon/glpk.h \
lemon/gomory_hu.h \
@@ -98,6 +100,7 @@
lemon/network_simplex.h \
lemon/path.h \
lemon/preflow.h \
+ lemon/radix_heap.h \
lemon/radix_sort.h \
lemon/random.h \
lemon/smart_graph.h \
diff -r 2305167d2491 -r 76689f2fc02d lemon/bin_heap.h
--- a/lemon/bin_heap.h Thu Nov 05 16:01:39 2009 +0100
+++ b/lemon/bin_heap.h Thu Dec 10 17:10:25 2009 +0100
@@ -33,23 +33,23 @@
///
///\brief A Binary Heap implementation.
///
- ///This class implements the \e binary \e heap data structure.
- ///
+ ///This class implements the \e binary \e heap data structure.
+ ///
///A \e heap is a data structure for storing items with specified values
///called \e priorities in such a way that finding the item with minimum
- ///priority is efficient. \c Comp specifies the ordering of the priorities.
+ ///priority is efficient. \c CMP specifies the ordering of the priorities.
///In a heap one can change the priority of an item, add or erase an
///item, etc.
///
///\tparam PR Type of the priority of the items.
///\tparam IM A read and writable item map with int values, used internally
///to handle the cross references.
- ///\tparam Comp A functor class for the ordering of the priorities.
+ ///\tparam CMP A functor class for the ordering of the priorities.
///The default is \c std::less<PR>.
///
///\sa FibHeap
///\sa Dijkstra
- template <typename PR, typename IM, typename Comp = std::less<PR> >
+ template <typename PR, typename IM, typename CMP = std::less<PR> >
class BinHeap {
public:
@@ -62,7 +62,7 @@
///\e
typedef std::pair<Item,Prio> Pair;
///\e
- typedef Comp Compare;
+ typedef CMP Compare;
/// \brief Type to represent the items states.
///
diff -r 2305167d2491 -r 76689f2fc02d lemon/bits/map_extender.h
--- a/lemon/bits/map_extender.h Thu Nov 05 16:01:39 2009 +0100
+++ b/lemon/bits/map_extender.h Thu Dec 10 17:10:25 2009 +0100
@@ -49,6 +49,8 @@
typedef typename Parent::Reference Reference;
typedef typename Parent::ConstReference ConstReference;
+ typedef typename Parent::ReferenceMapTag ReferenceMapTag;
+
class MapIt;
class ConstMapIt;
@@ -82,36 +84,36 @@
typedef typename Map::Value Value;
- MapIt() {}
+ MapIt() : map(NULL) {}
- MapIt(Invalid i) : Parent(i) { }
+ MapIt(Invalid i) : Parent(i), map(NULL) {}
- explicit MapIt(Map& _map) : map(_map) {
- map.notifier()->first(*this);
+ explicit MapIt(Map& _map) : map(&_map) {
+ map->notifier()->first(*this);
}
MapIt(const Map& _map, const Item& item)
- : Parent(item), map(_map) {}
+ : Parent(item), map(&_map) {}
MapIt& operator++() {
- map.notifier()->next(*this);
+ map->notifier()->next(*this);
return *this;
}
typename MapTraits<Map>::ConstReturnValue operator*() const {
- return map[*this];
+ return (*map)[*this];
}
typename MapTraits<Map>::ReturnValue operator*() {
- return map[*this];
+ return (*map)[*this];
}
void set(const Value& value) {
- map.set(*this, value);
+ map->set(*this, value);
}
protected:
- Map& map;
+ Map* map;
};
@@ -122,19 +124,19 @@
typedef typename Map::Value Value;
- ConstMapIt() {}
+ ConstMapIt() : map(NULL) {}
- ConstMapIt(Invalid i) : Parent(i) { }
+ ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
- explicit ConstMapIt(Map& _map) : map(_map) {
- map.notifier()->first(*this);
+ explicit ConstMapIt(Map& _map) : map(&_map) {
+ map->notifier()->first(*this);
}
ConstMapIt(const Map& _map, const Item& item)
: Parent(item), map(_map) {}
ConstMapIt& operator++() {
- map.notifier()->next(*this);
+ map->notifier()->next(*this);
return *this;
}
@@ -143,32 +145,32 @@
}
protected:
- const Map& map;
+ const Map* map;
};
class ItemIt : public Item {
typedef Item Parent;
public:
+ ItemIt() : map(NULL) {}
- ItemIt() {}
- ItemIt(Invalid i) : Parent(i) { }
+ ItemIt(Invalid i) : Parent(i), map(NULL) {}
- explicit ItemIt(Map& _map) : map(_map) {
- map.notifier()->first(*this);
+ explicit ItemIt(Map& _map) : map(&_map) {
+ map->notifier()->first(*this);
}
ItemIt(const Map& _map, const Item& item)
- : Parent(item), map(_map) {}
+ : Parent(item), map(&_map) {}
ItemIt& operator++() {
- map.notifier()->next(*this);
+ map->notifier()->next(*this);
return *this;
}
protected:
- const Map& map;
+ const Map* map;
};
};
@@ -191,6 +193,8 @@
typedef typename Parent::Reference Reference;
typedef typename Parent::ConstReference ConstReference;
+ typedef typename Parent::ReferenceMapTag ReferenceMapTag;
+
class MapIt;
class ConstMapIt;
@@ -227,36 +231,36 @@
public:
typedef typename Map::Value Value;
- MapIt() {}
+ MapIt() : map(NULL) {}
- MapIt(Invalid i) : Parent(i) { }
+ MapIt(Invalid i) : Parent(i), map(NULL) { }
- explicit MapIt(Map& _map) : map(_map) {
- map.graph.first(*this);
+ explicit MapIt(Map& _map) : map(&_map) {
+ map->graph.first(*this);
}
MapIt(const Map& _map, const Item& item)
- : Parent(item), map(_map) {}
+ : Parent(item), map(&_map) {}
MapIt& operator++() {
- map.graph.next(*this);
+ map->graph.next(*this);
return *this;
}
typename MapTraits<Map>::ConstReturnValue operator*() const {
- return map[*this];
+ return (*map)[*this];
}
typename MapTraits<Map>::ReturnValue operator*() {
- return map[*this];
+ return (*map)[*this];
}
void set(const Value& value) {
- map.set(*this, value);
+ map->set(*this, value);
}
protected:
- Map& map;
+ Map* map;
};
@@ -267,53 +271,53 @@
typedef typename Map::Value Value;
- ConstMapIt() {}
+ ConstMapIt() : map(NULL) {}
- ConstMapIt(Invalid i) : Parent(i) { }
+ ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
- explicit ConstMapIt(Map& _map) : map(_map) {
- map.graph.first(*this);
+ explicit ConstMapIt(Map& _map) : map(&_map) {
+ map->graph.first(*this);
}
ConstMapIt(const Map& _map, const Item& item)
- : Parent(item), map(_map) {}
+ : Parent(item), map(&_map) {}
ConstMapIt& operator++() {
- map.graph.next(*this);
+ map->graph.next(*this);
return *this;
}
typename MapTraits<Map>::ConstReturnValue operator*() const {
- return map[*this];
+ return (*map)[*this];
}
protected:
- const Map& map;
+ const Map* map;
};
class ItemIt : public Item {
typedef Item Parent;
public:
+ ItemIt() : map(NULL) {}
- ItemIt() {}
- ItemIt(Invalid i) : Parent(i) { }
+ ItemIt(Invalid i) : Parent(i), map(NULL) { }
- explicit ItemIt(Map& _map) : map(_map) {
- map.graph.first(*this);
+ explicit ItemIt(Map& _map) : map(&_map) {
+ map->graph.first(*this);
}
ItemIt(const Map& _map, const Item& item)
- : Parent(item), map(_map) {}
+ : Parent(item), map(&_map) {}
ItemIt& operator++() {
- map.graph.next(*this);
+ map->graph.next(*this);
return *this;
}
protected:
- const Map& map;
+ const Map* map;
};
diff -r 2305167d2491 -r 76689f2fc02d lemon/bucket_heap.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/bucket_heap.h Thu Dec 10 17:10:25 2009 +0100
@@ -0,0 +1,567 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_BUCKET_HEAP_H
+#define LEMON_BUCKET_HEAP_H
+
+///\ingroup auxdat
+///\file
+///\brief Bucket Heap implementation.
+
+#include <vector>
+#include <utility>
+#include <functional>
+
+namespace lemon {
+
+ namespace _bucket_heap_bits {
+
+ template <bool MIN>
+ struct DirectionTraits {
+ static bool less(int left, int right) {
+ return left < right;
+ }
+ static void increase(int& value) {
+ ++value;
+ }
+ };
+
+ template <>
+ struct DirectionTraits<false> {
+ static bool less(int left, int right) {
+ return left > right;
+ }
+ static void increase(int& value) {
+ --value;
+ }
+ };
+
+ }
+
+ /// \ingroup auxdat
+ ///
+ /// \brief A Bucket Heap implementation.
+ ///
+ /// This class implements the \e bucket \e heap data structure. A \e heap
+ /// is a data structure for storing items with specified values called \e
+ /// priorities in such a way that finding the item with minimum priority is
+ /// efficient. The bucket heap is very simple implementation, it can store
+ /// only integer priorities and it stores for each priority in the
+ /// \f$ [0..C) \f$ range a list of items. So it should be used only when
+ /// the priorities are small. It is not intended to use as dijkstra heap.
+ ///
+ /// \param IM A read and write Item int map, used internally
+ /// to handle the cross references.
+ /// \param MIN If the given parameter is false then instead of the
+ /// minimum value the maximum can be retrivied with the top() and
+ /// prio() member functions.
+ template <typename IM, bool MIN = true>
+ class BucketHeap {
+
+ public:
+ /// \e
+ typedef typename IM::Key Item;
+ /// \e
+ typedef int Prio;
+ /// \e
+ typedef std::pair<Item, Prio> Pair;
+ /// \e
+ typedef IM ItemIntMap;
+
+ private:
+
+ typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
+
+ public:
+
+ /// \brief Type to represent the items states.
+ ///
+ /// Each Item element have a state associated to it. It may be "in heap",
+ /// "pre heap" or "post heap". The latter two are indifferent from the
+ /// heap's point of view, but may be useful to the user.
+ ///
+ /// The item-int map must be initialized in such way that it assigns
+ /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
+ enum State {
+ IN_HEAP = 0, ///< = 0.
+ PRE_HEAP = -1, ///< = -1.
+ POST_HEAP = -2 ///< = -2.
+ };
+
+ public:
+ /// \brief The constructor.
+ ///
+ /// The constructor.
+ /// \param map should be given to the constructor, since it is used
+ /// internally to handle the cross references. The value of the map
+ /// should be PRE_HEAP (-1) for each element.
+ explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
+
+ /// The number of items stored in the heap.
+ ///
+ /// \brief Returns the number of items stored in the heap.
+ int size() const { return _data.size(); }
+
+ /// \brief Checks if the heap stores no items.
+ ///
+ /// Returns \c true if and only if the heap stores no items.
+ bool empty() const { return _data.empty(); }
+
+ /// \brief Make empty this heap.
+ ///
+ /// Make empty this heap. It does not change the cross reference
+ /// map. If you want to reuse a heap what is not surely empty you
+ /// should first clear the heap and after that you should set the
+ /// cross reference map for each item to \c PRE_HEAP.
+ void clear() {
+ _data.clear(); _first.clear(); _minimum = 0;
+ }
+
+ private:
+
+ void relocate_last(int idx) {
+ if (idx + 1 < int(_data.size())) {
+ _data[idx] = _data.back();
+ if (_data[idx].prev != -1) {
+ _data[_data[idx].prev].next = idx;
+ } else {
+ _first[_data[idx].value] = idx;
+ }
+ if (_data[idx].next != -1) {
+ _data[_data[idx].next].prev = idx;
+ }
+ _iim[_data[idx].item] = idx;
+ }
+ _data.pop_back();
+ }
+
+ void unlace(int idx) {
+ if (_data[idx].prev != -1) {
+ _data[_data[idx].prev].next = _data[idx].next;
+ } else {
+ _first[_data[idx].value] = _data[idx].next;
+ }
+ if (_data[idx].next != -1) {
+ _data[_data[idx].next].prev = _data[idx].prev;
+ }
+ }
+
+ void lace(int idx) {
+ if (int(_first.size()) <= _data[idx].value) {
+ _first.resize(_data[idx].value + 1, -1);
+ }
+ _data[idx].next = _first[_data[idx].value];
+ if (_data[idx].next != -1) {
+ _data[_data[idx].next].prev = idx;
+ }
+ _first[_data[idx].value] = idx;
+ _data[idx].prev = -1;
+ }
+
+ public:
+ /// \brief Insert a pair of item and priority into the heap.
+ ///
+ /// Adds \c p.first to the heap with priority \c p.second.
+ /// \param p The pair to insert.
+ void push(const Pair& p) {
+ push(p.first, p.second);
+ }
+
+ /// \brief Insert an item into the heap with the given priority.
+ ///
+ /// Adds \c i to the heap with priority \c p.
+ /// \param i The item to insert.
+ /// \param p The priority of the item.
+ void push(const Item &i, const Prio &p) {
+ int idx = _data.size();
+ _iim[i] = idx;
+ _data.push_back(BucketItem(i, p));
+ lace(idx);
+ if (Direction::less(p, _minimum)) {
+ _minimum = p;
+ }
+ }
+
+ /// \brief Returns the item with minimum priority.
+ ///
+ /// This method returns the item with minimum priority.
+ /// \pre The heap must be nonempty.
+ Item top() const {
+ while (_first[_minimum] == -1) {
+ Direction::increase(_minimum);
+ }
+ return _data[_first[_minimum]].item;
+ }
+
+ /// \brief Returns the minimum priority.
+ ///
+ /// It returns the minimum priority.
+ /// \pre The heap must be nonempty.
+ Prio prio() const {
+ while (_first[_minimum] == -1) {
+ Direction::increase(_minimum);
+ }
+ return _minimum;
+ }
+
+ /// \brief Deletes the item with minimum priority.
+ ///
+ /// This method deletes the item with minimum priority from the heap.
+ /// \pre The heap must be non-empty.
+ void pop() {
+ while (_first[_minimum] == -1) {
+ Direction::increase(_minimum);
+ }
+ int idx = _first[_minimum];
+ _iim[_data[idx].item] = -2;
+ unlace(idx);
+ relocate_last(idx);
+ }
+
+ /// \brief Deletes \c i from the heap.
+ ///
+ /// This method deletes item \c i from the heap, if \c i was
+ /// already stored in the heap.
+ /// \param i The item to erase.
+ void erase(const Item &i) {
+ int idx = _iim[i];
+ _iim[_data[idx].item] = -2;
+ unlace(idx);
+ relocate_last(idx);
+ }
+
+
+ /// \brief Returns the priority of \c i.
+ ///
+ /// This function returns the priority of item \c i.
+ /// \pre \c i must be in the heap.
+ /// \param i The item.
+ Prio operator[](const Item &i) const {
+ int idx = _iim[i];
+ return _data[idx].value;
+ }
+
+ /// \brief \c i gets to the heap with priority \c p independently
+ /// if \c i was already there.
+ ///
+ /// This method calls \ref push(\c i, \c p) if \c i is not stored
+ /// in the heap and sets the priority of \c i to \c p otherwise.
+ /// \param i The item.
+ /// \param p The priority.
+ void set(const Item &i, const Prio &p) {
+ int idx = _iim[i];
+ if (idx < 0) {
+ push(i, p);
+ } else if (Direction::less(p, _data[idx].value)) {
+ decrease(i, p);
+ } else {
+ increase(i, p);
+ }
+ }
+
+ /// \brief Decreases the priority of \c i to \c p.
+ ///
+ /// This method decreases the priority of item \c i to \c p.
+ /// \pre \c i must be stored in the heap with priority at least \c
+ /// p relative to \c Compare.
+ /// \param i The item.
+ /// \param p The priority.
+ void decrease(const Item &i, const Prio &p) {
+ int idx = _iim[i];
+ unlace(idx);
+ _data[idx].value = p;
+ if (Direction::less(p, _minimum)) {
+ _minimum = p;
+ }
+ lace(idx);
+ }
+
+ /// \brief Increases the priority of \c i to \c p.
+ ///
+ /// This method sets the priority of item \c i to \c p.
+ /// \pre \c i must be stored in the heap with priority at most \c
+ /// p relative to \c Compare.
+ /// \param i The item.
+ /// \param p The priority.
+ void increase(const Item &i, const Prio &p) {
+ int idx = _iim[i];
+ unlace(idx);
+ _data[idx].value = p;
+ lace(idx);
+ }
+
+ /// \brief Returns if \c item is in, has already been in, or has
+ /// never been in the heap.
+ ///
+ /// This method returns PRE_HEAP if \c item has never been in the
+ /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+ /// otherwise. In the latter case it is possible that \c item will
+ /// get back to the heap again.
+ /// \param i The item.
+ State state(const Item &i) const {
+ int idx = _iim[i];
+ if (idx >= 0) idx = 0;
+ return State(idx);
+ }
+
+ /// \brief Sets the state of the \c item in the heap.
+ ///
+ /// Sets the state of the \c item in the heap. It can be used to
+ /// manually clear the heap when it is important to achive the
+ /// better time complexity.
+ /// \param i The item.
+ /// \param st The state. It should not be \c IN_HEAP.
+ void state(const Item& i, State st) {
+ switch (st) {
+ case POST_HEAP:
+ case PRE_HEAP:
+ if (state(i) == IN_HEAP) {
+ erase(i);
+ }
+ _iim[i] = st;
+ break;
+ case IN_HEAP:
+ break;
+ }
+ }
+
+ private:
+
+ struct BucketItem {
+ BucketItem(const Item& _item, int _value)
+ : item(_item), value(_value) {}
+
+ Item item;
+ int value;
+
+ int prev, next;
+ };
+
+ ItemIntMap& _iim;
+ std::vector<int> _first;
+ std::vector<BucketItem> _data;
+ mutable int _minimum;
+
+ }; // class BucketHeap
+
+ /// \ingroup auxdat
+ ///
+ /// \brief A Simplified Bucket Heap implementation.
+ ///
+ /// This class implements a simplified \e bucket \e heap data
+ /// structure. It does not provide some functionality but it faster
+ /// and simplier data structure than the BucketHeap. The main
+ /// difference is that the BucketHeap stores for every key a double
+ /// linked list while this class stores just simple lists. In the
+ /// other way it does not support erasing each elements just the
+ /// minimal and it does not supports key increasing, decreasing.
+ ///
+ /// \param IM A read and write Item int map, used internally
+ /// to handle the cross references.
+ /// \param MIN If the given parameter is false then instead of the
+ /// minimum value the maximum can be retrivied with the top() and
+ /// prio() member functions.
+ ///
+ /// \sa BucketHeap
+ template <typename IM, bool MIN = true >
+ class SimpleBucketHeap {
+
+ public:
+ typedef typename IM::Key Item;
+ typedef int Prio;
+ typedef std::pair<Item, Prio> Pair;
+ typedef IM ItemIntMap;
+
+ private:
+
+ typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
+
+ public:
+
+ /// \brief Type to represent the items states.
+ ///
+ /// Each Item element have a state associated to it. It may be "in heap",
+ /// "pre heap" or "post heap". The latter two are indifferent from the
+ /// heap's point of view, but may be useful to the user.
+ ///
+ /// The item-int map must be initialized in such way that it assigns
+ /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
+ enum State {
+ IN_HEAP = 0, ///< = 0.
+ PRE_HEAP = -1, ///< = -1.
+ POST_HEAP = -2 ///< = -2.
+ };
+
+ public:
+
+ /// \brief The constructor.
+ ///
+ /// The constructor.
+ /// \param map should be given to the constructor, since it is used
+ /// internally to handle the cross references. The value of the map
+ /// should be PRE_HEAP (-1) for each element.
+ explicit SimpleBucketHeap(ItemIntMap &map)
+ : _iim(map), _free(-1), _num(0), _minimum(0) {}
+
+ /// \brief Returns the number of items stored in the heap.
+ ///
+ /// The number of items stored in the heap.
+ int size() const { return _num; }
+
+ /// \brief Checks if the heap stores no items.
+ ///
+ /// Returns \c true if and only if the heap stores no items.
+ bool empty() const { return _num == 0; }
+
+ /// \brief Make empty this heap.
+ ///
+ /// Make empty this heap. It does not change the cross reference
+ /// map. If you want to reuse a heap what is not surely empty you
+ /// should first clear the heap and after that you should set the
+ /// cross reference map for each item to \c PRE_HEAP.
+ void clear() {
+ _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
+ }
+
+ /// \brief Insert a pair of item and priority into the heap.
+ ///
+ /// Adds \c p.first to the heap with priority \c p.second.
+ /// \param p The pair to insert.
+ void push(const Pair& p) {
+ push(p.first, p.second);
+ }
+
+ /// \brief Insert an item into the heap with the given priority.
+ ///
+ /// Adds \c i to the heap with priority \c p.
+ /// \param i The item to insert.
+ /// \param p The priority of the item.
+ void push(const Item &i, const Prio &p) {
+ int idx;
+ if (_free == -1) {
+ idx = _data.size();
+ _data.push_back(BucketItem(i));
+ } else {
+ idx = _free;
+ _free = _data[idx].next;
+ _data[idx].item = i;
+ }
+ _iim[i] = idx;
+ if (p >= int(_first.size())) _first.resize(p + 1, -1);
+ _data[idx].next = _first[p];
+ _first[p] = idx;
+ if (Direction::less(p, _minimum)) {
+ _minimum = p;
+ }
+ ++_num;
+ }
+
+ /// \brief Returns the item with minimum priority.
+ ///
+ /// This method returns the item with minimum priority.
+ /// \pre The heap must be nonempty.
+ Item top() const {
+ while (_first[_minimum] == -1) {
+ Direction::increase(_minimum);
+ }
+ return _data[_first[_minimum]].item;
+ }
+
+ /// \brief Returns the minimum priority.
+ ///
+ /// It returns the minimum priority.
+ /// \pre The heap must be nonempty.
+ Prio prio() const {
+ while (_first[_minimum] == -1) {
+ Direction::increase(_minimum);
+ }
+ return _minimum;
+ }
+
+ /// \brief Deletes the item with minimum priority.
+ ///
+ /// This method deletes the item with minimum priority from the heap.
+ /// \pre The heap must be non-empty.
+ void pop() {
+ while (_first[_minimum] == -1) {
+ Direction::increase(_minimum);
+ }
+ int idx = _first[_minimum];
+ _iim[_data[idx].item] = -2;
+ _first[_minimum] = _data[idx].next;
+ _data[idx].next = _free;
+ _free = idx;
+ --_num;
+ }
+
+ /// \brief Returns the priority of \c i.
+ ///
+ /// This function returns the priority of item \c i.
+ /// \warning This operator is not a constant time function
+ /// because it scans the whole data structure to find the proper
+ /// value.
+ /// \pre \c i must be in the heap.
+ /// \param i The item.
+ Prio operator[](const Item &i) const {
+ for (int k = 0; k < _first.size(); ++k) {
+ int idx = _first[k];
+ while (idx != -1) {
+ if (_data[idx].item == i) {
+ return k;
+ }
+ idx = _data[idx].next;
+ }
+ }
+ return -1;
+ }
+
+ /// \brief Returns if \c item is in, has already been in, or has
+ /// never been in the heap.
+ ///
+ /// This method returns PRE_HEAP if \c item has never been in the
+ /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+ /// otherwise. In the latter case it is possible that \c item will
+ /// get back to the heap again.
+ /// \param i The item.
+ State state(const Item &i) const {
+ int idx = _iim[i];
+ if (idx >= 0) idx = 0;
+ return State(idx);
+ }
+
+ private:
+
+ struct BucketItem {
+ BucketItem(const Item& _item)
+ : item(_item) {}
+
+ Item item;
+ int next;
+ };
+
+ ItemIntMap& _iim;
+ std::vector<int> _first;
+ std::vector<BucketItem> _data;
+ int _free, _num;
+ mutable int _minimum;
+
+ }; // class SimpleBucketHeap
+
+}
+
+#endif
diff -r 2305167d2491 -r 76689f2fc02d lemon/concepts/maps.h
--- a/lemon/concepts/maps.h Thu Nov 05 16:01:39 2009 +0100
+++ b/lemon/concepts/maps.h Thu Dec 10 17:10:25 2009 +0100
@@ -182,7 +182,8 @@
template<typename _ReferenceMap>
struct Constraints {
- void constraints() {
+ typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
+ constraints() {
checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
ref = m[key];
m[key] = val;
diff -r 2305167d2491 -r 76689f2fc02d lemon/fib_heap.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/fib_heap.h Thu Dec 10 17:10:25 2009 +0100
@@ -0,0 +1,468 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_FIB_HEAP_H
+#define LEMON_FIB_HEAP_H
+
+///\file
+///\ingroup auxdat
+///\brief Fibonacci Heap implementation.
+
+#include <vector>
+#include <functional>
+#include <lemon/math.h>
+
+namespace lemon {
+
+ /// \ingroup auxdat
+ ///
+ ///\brief Fibonacci Heap.
+ ///
+ ///This class implements the \e Fibonacci \e heap data structure. A \e heap
+ ///is a data structure for storing items with specified values called \e
+ ///priorities in such a way that finding the item with minimum priority is
+ ///efficient. \c CMP specifies the ordering of the priorities. In a heap
+ ///one can change the priority of an item, add or erase an item, etc.
+ ///
+ ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
+ ///heap. In case of many calls to these operations, it is better to use a
+ ///\ref BinHeap "binary heap".
+ ///
+ ///\param PRIO Type of the priority of the items.
+ ///\param IM A read and writable Item int map, used internally
+ ///to handle the cross references.
+ ///\param CMP A class for the ordering of the priorities. The
+ ///default is \c std::less<PRIO>.
+ ///
+ ///\sa BinHeap
+ ///\sa Dijkstra
+#ifdef DOXYGEN
+ template <typename PRIO, typename IM, typename CMP>
+#else
+ template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
+#endif
+ class FibHeap {
+ public:
+ ///\e
+ typedef IM ItemIntMap;
+ ///\e
+ typedef PRIO Prio;
+ ///\e
+ typedef typename ItemIntMap::Key Item;
+ ///\e
+ typedef std::pair<Item,Prio> Pair;
+ ///\e
+ typedef CMP Compare;
+
+ private:
+ class Store;
+
+ std::vector<Store> _data;
+ int _minimum;
+ ItemIntMap &_iim;
+ Compare _comp;
+ int _num;
+
+ public:
+
+ /// \brief Type to represent the items states.
+ ///
+ /// Each Item element have a state associated to it. It may be "in heap",
+ /// "pre heap" or "post heap". The latter two are indifferent from the
+ /// heap's point of view, but may be useful to the user.
+ ///
+ /// The item-int map must be initialized in such way that it assigns
+ /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
+ enum State {
+ IN_HEAP = 0, ///< = 0.
+ PRE_HEAP = -1, ///< = -1.
+ POST_HEAP = -2 ///< = -2.
+ };
+
+ /// \brief The constructor
+ ///
+ /// \c map should be given to the constructor, since it is
+ /// used internally to handle the cross references.
+ explicit FibHeap(ItemIntMap &map)
+ : _minimum(0), _iim(map), _num() {}
+
+ /// \brief The constructor
+ ///
+ /// \c map should be given to the constructor, since it is used
+ /// internally to handle the cross references. \c comp is an
+ /// object for ordering of the priorities.
+ FibHeap(ItemIntMap &map, const Compare &comp)
+ : _minimum(0), _iim(map), _comp(comp), _num() {}
+
+ /// \brief The number of items stored in the heap.
+ ///
+ /// Returns the number of items stored in the heap.
+ int size() const { return _num; }
+
+ /// \brief Checks if the heap stores no items.
+ ///
+ /// Returns \c true if and only if the heap stores no items.
+ bool empty() const { return _num==0; }
+
+ /// \brief Make empty this heap.
+ ///
+ /// Make empty this heap. It does not change the cross reference
+ /// map. If you want to reuse a heap what is not surely empty you
+ /// should first clear the heap and after that you should set the
+ /// cross reference map for each item to \c PRE_HEAP.
+ void clear() {
+ _data.clear(); _minimum = 0; _num = 0;
+ }
+
+ /// \brief \c item gets to the heap with priority \c value independently
+ /// if \c item was already there.
+ ///
+ /// This method calls \ref push(\c item, \c value) if \c item is not
+ /// stored in the heap and it calls \ref decrease(\c item, \c value) or
+ /// \ref increase(\c item, \c value) otherwise.
+ void set (const Item& item, const Prio& value) {
+ int i=_iim[item];
+ if ( i >= 0 && _data[i].in ) {
+ if ( _comp(value, _data[i].prio) ) decrease(item, value);
+ if ( _comp(_data[i].prio, value) ) increase(item, value);
+ } else push(item, value);
+ }
+
+ /// \brief Adds \c item to the heap with priority \c value.
+ ///
+ /// Adds \c item to the heap with priority \c value.
+ /// \pre \c item must not be stored in the heap.
+ void push (const Item& item, const Prio& value) {
+ int i=_iim[item];
+ if ( i < 0 ) {
+ int s=_data.size();
+ _iim.set( item, s );
+ Store st;
+ st.name=item;
+ _data.push_back(st);
+ i=s;
+ } else {
+ _data[i].parent=_data[i].child=-1;
+ _data[i].degree=0;
+ _data[i].in=true;
+ _data[i].marked=false;
+ }
+
+ if ( _num ) {
+ _data[_data[_minimum].right_neighbor].left_neighbor=i;
+ _data[i].right_neighbor=_data[_minimum].right_neighbor;
+ _data[_minimum].right_neighbor=i;
+ _data[i].left_neighbor=_minimum;
+ if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
+ } else {
+ _data[i].right_neighbor=_data[i].left_neighbor=i;
+ _minimum=i;
+ }
+ _data[i].prio=value;
+ ++_num;
+ }
+
+ /// \brief Returns the item with minimum priority relative to \c Compare.
+ ///
+ /// This method returns the item with minimum priority relative to \c
+ /// Compare.
+ /// \pre The heap must be nonempty.
+ Item top() const { return _data[_minimum].name; }
+
+ /// \brief Returns the minimum priority relative to \c Compare.
+ ///
+ /// It returns the minimum priority relative to \c Compare.
+ /// \pre The heap must be nonempty.
+ const Prio& prio() const { return _data[_minimum].prio; }
+
+ /// \brief Returns the priority of \c item.
+ ///
+ /// It returns the priority of \c item.
+ /// \pre \c item must be in the heap.
+ const Prio& operator[](const Item& item) const {
+ return _data[_iim[item]].prio;
+ }
+
+ /// \brief Deletes the item with minimum priority relative to \c Compare.
+ ///
+ /// This method deletes the item with minimum priority relative to \c
+ /// Compare from the heap.
+ /// \pre The heap must be non-empty.
+ void pop() {
+ /*The first case is that there are only one root.*/
+ if ( _data[_minimum].left_neighbor==_minimum ) {
+ _data[_minimum].in=false;
+ if ( _data[_minimum].degree!=0 ) {
+ makeroot(_data[_minimum].child);
+ _minimum=_data[_minimum].child;
+ balance();
+ }
+ } else {
+ int right=_data[_minimum].right_neighbor;
+ unlace(_minimum);
+ _data[_minimum].in=false;
+ if ( _data[_minimum].degree > 0 ) {
+ int left=_data[_minimum].left_neighbor;
+ int child=_data[_minimum].child;
+ int last_child=_data[child].left_neighbor;
+
+ makeroot(child);
+
+ _data[left].right_neighbor=child;
+ _data[child].left_neighbor=left;
+ _data[right].left_neighbor=last_child;
+ _data[last_child].right_neighbor=right;
+ }
+ _minimum=right;
+ balance();
+ } // the case where there are more roots
+ --_num;
+ }
+
+ /// \brief Deletes \c item from the heap.
+ ///
+ /// This method deletes \c item from the heap, if \c item was already
+ /// stored in the heap. It is quite inefficient in Fibonacci heaps.
+ void erase (const Item& item) {
+ int i=_iim[item];
+
+ if ( i >= 0 && _data[i].in ) {
+ if ( _data[i].parent!=-1 ) {
+ int p=_data[i].parent;
+ cut(i,p);
+ cascade(p);
+ }
+ _minimum=i; //As if its prio would be -infinity
+ pop();
+ }
+ }
+
+ /// \brief Decreases the priority of \c item to \c value.
+ ///
+ /// This method decreases the priority of \c item to \c value.
+ /// \pre \c item must be stored in the heap with priority at least \c
+ /// value relative to \c Compare.
+ void decrease (Item item, const Prio& value) {
+ int i=_iim[item];
+ _data[i].prio=value;
+ int p=_data[i].parent;
+
+ if ( p!=-1 && _comp(value, _data[p].prio) ) {
+ cut(i,p);
+ cascade(p);
+ }
+ if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
+ }
+
+ /// \brief Increases the priority of \c item to \c value.
+ ///
+ /// This method sets the priority of \c item to \c value. Though
+ /// there is no precondition on the priority of \c item, this
+ /// method should be used only if it is indeed necessary to increase
+ /// (relative to \c Compare) the priority of \c item, because this
+ /// method is inefficient.
+ void increase (Item item, const Prio& value) {
+ erase(item);
+ push(item, value);
+ }
+
+
+ /// \brief Returns if \c item is in, has already been in, or has never
+ /// been in the heap.
+ ///
+ /// This method returns PRE_HEAP if \c item has never been in the
+ /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+ /// otherwise. In the latter case it is possible that \c item will
+ /// get back to the heap again.
+ State state(const Item &item) const {
+ int i=_iim[item];
+ if( i>=0 ) {
+ if ( _data[i].in ) i=0;
+ else i=-2;
+ }
+ return State(i);
+ }
+
+ /// \brief Sets the state of the \c item in the heap.
+ ///
+ /// Sets the state of the \c item in the heap. It can be used to
+ /// manually clear the heap when it is important to achive the
+ /// better time _complexity.
+ /// \param i The item.
+ /// \param st The state. It should not be \c IN_HEAP.
+ void state(const Item& i, State st) {
+ switch (st) {
+ case POST_HEAP:
+ case PRE_HEAP:
+ if (state(i) == IN_HEAP) {
+ erase(i);
+ }
+ _iim[i] = st;
+ break;
+ case IN_HEAP:
+ break;
+ }
+ }
+
+ private:
+
+ void balance() {
+
+ int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1;
+
+ std::vector<int> A(maxdeg,-1);
+
+ /*
+ *Recall that now minimum does not point to the minimum prio element.
+ *We set minimum to this during balance().
+ */
+ int anchor=_data[_minimum].left_neighbor;
+ int next=_minimum;
+ bool end=false;
+
+ do {
+ int active=next;
+ if ( anchor==active ) end=true;
+ int d=_data[active].degree;
+ next=_data[active].right_neighbor;
+
+ while (A[d]!=-1) {
+ if( _comp(_data[active].prio, _data[A[d]].prio) ) {
+ fuse(active,A[d]);
+ } else {
+ fuse(A[d],active);
+ active=A[d];
+ }
+ A[d]=-1;
+ ++d;
+ }
+ A[d]=active;
+ } while ( !end );
+
+
+ while ( _data[_minimum].parent >=0 )
+ _minimum=_data[_minimum].parent;
+ int s=_minimum;
+ int m=_minimum;
+ do {
+ if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
+ s=_data[s].right_neighbor;
+ } while ( s != m );
+ }
+
+ void makeroot(int c) {
+ int s=c;
+ do {
+ _data[s].parent=-1;
+ s=_data[s].right_neighbor;
+ } while ( s != c );
+ }
+
+ void cut(int a, int b) {
+ /*
+ *Replacing a from the children of b.
+ */
+ --_data[b].degree;
+
+ if ( _data[b].degree !=0 ) {
+ int child=_data[b].child;
+ if ( child==a )
+ _data[b].child=_data[child].right_neighbor;
+ unlace(a);
+ }
+
+
+ /*Lacing a to the roots.*/
+ int right=_data[_minimum].right_neighbor;
+ _data[_minimum].right_neighbor=a;
+ _data[a].left_neighbor=_minimum;
+ _data[a].right_neighbor=right;
+ _data[right].left_neighbor=a;
+
+ _data[a].parent=-1;
+ _data[a].marked=false;
+ }
+
+ void cascade(int a) {
+ if ( _data[a].parent!=-1 ) {
+ int p=_data[a].parent;
+
+ if ( _data[a].marked==false ) _data[a].marked=true;
+ else {
+ cut(a,p);
+ cascade(p);
+ }
+ }
+ }
+
+ void fuse(int a, int b) {
+ unlace(b);
+
+ /*Lacing b under a.*/
+ _data[b].parent=a;
+
+ if (_data[a].degree==0) {
+ _data[b].left_neighbor=b;
+ _data[b].right_neighbor=b;
+ _data[a].child=b;
+ } else {
+ int child=_data[a].child;
+ int last_child=_data[child].left_neighbor;
+ _data[child].left_neighbor=b;
+ _data[b].right_neighbor=child;
+ _data[last_child].right_neighbor=b;
+ _data[b].left_neighbor=last_child;
+ }
+
+ ++_data[a].degree;
+
+ _data[b].marked=false;
+ }
+
+ /*
+ *It is invoked only if a has siblings.
+ */
+ void unlace(int a) {
+ int leftn=_data[a].left_neighbor;
+ int rightn=_data[a].right_neighbor;
+ _data[leftn].right_neighbor=rightn;
+ _data[rightn].left_neighbor=leftn;
+ }
+
+
+ class Store {
+ friend class FibHeap;
+
+ Item name;
+ int parent;
+ int left_neighbor;
+ int right_neighbor;
+ int child;
+ int degree;
+ bool marked;
+ bool in;
+ Prio prio;
+
+ Store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
+ };
+ };
+
+} //namespace lemon
+
+#endif //LEMON_FIB_HEAP_H
+
diff -r 2305167d2491 -r 76689f2fc02d lemon/radix_heap.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/radix_heap.h Thu Dec 10 17:10:25 2009 +0100
@@ -0,0 +1,433 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_RADIX_HEAP_H
+#define LEMON_RADIX_HEAP_H
+
+///\ingroup auxdat
+///\file
+///\brief Radix Heap implementation.
+
+#include <vector>
+#include <lemon/error.h>
+
+namespace lemon {
+
+
+ /// \ingroup auxdata
+ ///
+ /// \brief A Radix Heap implementation.
+ ///
+ /// This class implements the \e radix \e heap data structure. A \e heap
+ /// is a data structure for storing items with specified values called \e
+ /// priorities in such a way that finding the item with minimum priority is
+ /// efficient. This heap type can store only items with \e int priority.
+ /// In a heap one can change the priority of an item, add or erase an
+ /// item, but the priority cannot be decreased under the last removed
+ /// item's priority.
+ ///
+ /// \param IM A read and writable Item int map, used internally
+ /// to handle the cross references.
+ ///
+ /// \see BinHeap
+ /// \see Dijkstra
+ template <typename IM>
+ class RadixHeap {
+
+ public:
+ typedef typename IM::Key Item;
+ typedef int Prio;
+ typedef IM ItemIntMap;
+
+ /// \brief Exception thrown by RadixHeap.
+ ///
+ /// This Exception is thrown when a smaller priority
+ /// is inserted into the \e RadixHeap then the last time erased.
+ /// \see RadixHeap
+
+ class UnderFlowPriorityError : public Exception {
+ public:
+ virtual const char* what() const throw() {
+ return "lemon::RadixHeap::UnderFlowPriorityError";
+ }
+ };
+
+ /// \brief Type to represent the items states.
+ ///
+ /// Each Item element have a state associated to it. It may be "in heap",
+ /// "pre heap" or "post heap". The latter two are indifferent from the
+ /// heap's point of view, but may be useful to the user.
+ ///
+ /// The ItemIntMap \e should be initialized in such way that it maps
+ /// PRE_HEAP (-1) to any element to be put in the heap...
+ enum State {
+ IN_HEAP = 0,
+ PRE_HEAP = -1,
+ POST_HEAP = -2
+ };
+
+ private:
+
+ struct RadixItem {
+ int prev, next, box;
+ Item item;
+ int prio;
+ RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
+ };
+
+ struct RadixBox {
+ int first;
+ int min, size;
+ RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
+ };
+
+ std::vector<RadixItem> data;
+ std::vector<RadixBox> boxes;
+
+ ItemIntMap &_iim;
+
+
+ public:
+ /// \brief The constructor.
+ ///
+ /// The constructor.
+ ///
+ /// \param map It should be given to the constructor, since it is used
+ /// internally to handle the cross references. The value of the map
+ /// should be PRE_HEAP (-1) for each element.
+ ///
+ /// \param minimal The initial minimal value of the heap.
+ /// \param capacity It determines the initial capacity of the heap.
+ RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
+ : _iim(map) {
+ boxes.push_back(RadixBox(minimal, 1));
+ boxes.push_back(RadixBox(minimal + 1, 1));
+ while (lower(boxes.size() - 1, capacity + minimal - 1)) {
+ extend();
+ }
+ }
+
+ /// The number of items stored in the heap.
+ ///
+ /// \brief Returns the number of items stored in the heap.
+ int size() const { return data.size(); }
+ /// \brief Checks if the heap stores no items.
+ ///
+ /// Returns \c true if and only if the heap stores no items.
+ bool empty() const { return data.empty(); }
+
+ /// \brief Make empty this heap.
+ ///
+ /// Make empty this heap. It does not change the cross reference
+ /// map. If you want to reuse a heap what is not surely empty you
+ /// should first clear the heap and after that you should set the
+ /// cross reference map for each item to \c PRE_HEAP.
+ void clear(int minimal = 0, int capacity = 0) {
+ data.clear(); boxes.clear();
+ boxes.push_back(RadixBox(minimal, 1));
+ boxes.push_back(RadixBox(minimal + 1, 1));
+ while (lower(boxes.size() - 1, capacity + minimal - 1)) {
+ extend();
+ }
+ }
+
+ private:
+
+ bool upper(int box, Prio pr) {
+ return pr < boxes[box].min;
+ }
+
+ bool lower(int box, Prio pr) {
+ return pr >= boxes[box].min + boxes[box].size;
+ }
+
+ /// \brief Remove item from the box list.
+ void remove(int index) {
+ if (data[index].prev >= 0) {
+ data[data[index].prev].next = data[index].next;
+ } else {
+ boxes[data[index].box].first = data[index].next;
+ }
+ if (data[index].next >= 0) {
+ data[data[index].next].prev = data[index].prev;
+ }
+ }
+
+ /// \brief Insert item into the box list.
+ void insert(int box, int index) {
+ if (boxes[box].first == -1) {
+ boxes[box].first = index;
+ data[index].next = data[index].prev = -1;
+ } else {
+ data[index].next = boxes[box].first;
+ data[boxes[box].first].prev = index;
+ data[index].prev = -1;
+ boxes[box].first = index;
+ }
+ data[index].box = box;
+ }
+
+ /// \brief Add a new box to the box list.
+ void extend() {
+ int min = boxes.back().min + boxes.back().size;
+ int bs = 2 * boxes.back().size;
+ boxes.push_back(RadixBox(min, bs));
+ }
+
+ /// \brief Move an item up into the proper box.
+ void bubble_up(int index) {
+ if (!lower(data[index].box, data[index].prio)) return;
+ remove(index);
+ int box = findUp(data[index].box, data[index].prio);
+ insert(box, index);
+ }
+
+ /// \brief Find up the proper box for the item with the given prio.
+ int findUp(int start, int pr) {
+ while (lower(start, pr)) {
+ if (++start == int(boxes.size())) {
+ extend();
+ }
+ }
+ return start;
+ }
+
+ /// \brief Move an item down into the proper box.
+ void bubble_down(int index) {
+ if (!upper(data[index].box, data[index].prio)) return;
+ remove(index);
+ int box = findDown(data[index].box, data[index].prio);
+ insert(box, index);
+ }
+
+ /// \brief Find up the proper box for the item with the given prio.
+ int findDown(int start, int pr) {
+ while (upper(start, pr)) {
+ if (--start < 0) throw UnderFlowPriorityError();
+ }
+ return start;
+ }
+
+ /// \brief Find the first not empty box.
+ int findFirst() {
+ int first = 0;
+ while (boxes[first].first == -1) ++first;
+ return first;
+ }
+
+ /// \brief Gives back the minimal prio of the box.
+ int minValue(int box) {
+ int min = data[boxes[box].first].prio;
+ for (int k = boxes[box].first; k != -1; k = data[k].next) {
+ if (data[k].prio < min) min = data[k].prio;
+ }
+ return min;
+ }
+
+ /// \brief Rearrange the items of the heap and makes the
+ /// first box not empty.
+ void moveDown() {
+ int box = findFirst();
+ if (box == 0) return;
+ int min = minValue(box);
+ for (int i = 0; i <= box; ++i) {
+ boxes[i].min = min;
+ min += boxes[i].size;
+ }
+ int curr = boxes[box].first, next;
+ while (curr != -1) {
+ next = data[curr].next;
+ bubble_down(curr);
+ curr = next;
+ }
+ }
+
+ void relocate_last(int index) {
+ if (index != int(data.size()) - 1) {
+ data[index] = data.back();
+ if (data[index].prev != -1) {
+ data[data[index].prev].next = index;
+ } else {
+ boxes[data[index].box].first = index;
+ }
+ if (data[index].next != -1) {
+ data[data[index].next].prev = index;
+ }
+ _iim[data[index].item] = index;
+ }
+ data.pop_back();
+ }
+
+ public:
+
+ /// \brief Insert an item into the heap with the given priority.
+ ///
+ /// Adds \c i to the heap with priority \c p.
+ /// \param i The item to insert.
+ /// \param p The priority of the item.
+ void push(const Item &i, const Prio &p) {
+ int n = data.size();
+ _iim.set(i, n);
+ data.push_back(RadixItem(i, p));
+ while (lower(boxes.size() - 1, p)) {
+ extend();
+ }
+ int box = findDown(boxes.size() - 1, p);
+ insert(box, n);
+ }
+
+ /// \brief Returns the item with minimum priority.
+ ///
+ /// This method returns the item with minimum priority.
+ /// \pre The heap must be nonempty.
+ Item top() const {
+ const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
+ return data[boxes[0].first].item;
+ }
+
+ /// \brief Returns the minimum priority.
+ ///
+ /// It returns the minimum priority.
+ /// \pre The heap must be nonempty.
+ Prio prio() const {
+ const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
+ return data[boxes[0].first].prio;
+ }
+
+ /// \brief Deletes the item with minimum priority.
+ ///
+ /// This method deletes the item with minimum priority.
+ /// \pre The heap must be non-empty.
+ void pop() {
+ moveDown();
+ int index = boxes[0].first;
+ _iim[data[index].item] = POST_HEAP;
+ remove(index);
+ relocate_last(index);
+ }
+
+ /// \brief Deletes \c i from the heap.
+ ///
+ /// This method deletes item \c i from the heap, if \c i was
+ /// already stored in the heap.
+ /// \param i The item to erase.
+ void erase(const Item &i) {
+ int index = _iim[i];
+ _iim[i] = POST_HEAP;
+ remove(index);
+ relocate_last(index);
+ }
+
+ /// \brief Returns the priority of \c i.
+ ///
+ /// This function returns the priority of item \c i.
+ /// \pre \c i must be in the heap.
+ /// \param i The item.
+ Prio operator[](const Item &i) const {
+ int idx = _iim[i];
+ return data[idx].prio;
+ }
+
+ /// \brief \c i gets to the heap with priority \c p independently
+ /// if \c i was already there.
+ ///
+ /// This method calls \ref push(\c i, \c p) if \c i is not stored
+ /// in the heap and sets the priority of \c i to \c p otherwise.
+ /// It may throw an \e UnderFlowPriorityException.
+ /// \param i The item.
+ /// \param p The priority.
+ void set(const Item &i, const Prio &p) {
+ int idx = _iim[i];
+ if( idx < 0 ) {
+ push(i, p);
+ }
+ else if( p >= data[idx].prio ) {
+ data[idx].prio = p;
+ bubble_up(idx);
+ } else {
+ data[idx].prio = p;
+ bubble_down(idx);
+ }
+ }
+
+
+ /// \brief Decreases the priority of \c i to \c p.
+ ///
+ /// This method decreases the priority of item \c i to \c p.
+ /// \pre \c i must be stored in the heap with priority at least \c p, and
+ /// \c should be greater or equal to the last removed item's priority.
+ /// \param i The item.
+ /// \param p The priority.
+ void decrease(const Item &i, const Prio &p) {
+ int idx = _iim[i];
+ data[idx].prio = p;
+ bubble_down(idx);
+ }
+
+ /// \brief Increases the priority of \c i to \c p.
+ ///
+ /// This method sets the priority of item \c i to \c p.
+ /// \pre \c i must be stored in the heap with priority at most \c p
+ /// \param i The item.
+ /// \param p The priority.
+ void increase(const Item &i, const Prio &p) {
+ int idx = _iim[i];
+ data[idx].prio = p;
+ bubble_up(idx);
+ }
+
+ /// \brief Returns if \c item is in, has already been in, or has
+ /// never been in the heap.
+ ///
+ /// This method returns PRE_HEAP if \c item has never been in the
+ /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+ /// otherwise. In the latter case it is possible that \c item will
+ /// get back to the heap again.
+ /// \param i The item.
+ State state(const Item &i) const {
+ int s = _iim[i];
+ if( s >= 0 ) s = 0;
+ return State(s);
+ }
+
+ /// \brief Sets the state of the \c item in the heap.
+ ///
+ /// Sets the state of the \c item in the heap. It can be used to
+ /// manually clear the heap when it is important to achive the
+ /// better time complexity.
+ /// \param i The item.
+ /// \param st The state. It should not be \c IN_HEAP.
+ void state(const Item& i, State st) {
+ switch (st) {
+ case POST_HEAP:
+ case PRE_HEAP:
+ if (state(i) == IN_HEAP) {
+ erase(i);
+ }
+ _iim[i] = st;
+ break;
+ case IN_HEAP:
+ break;
+ }
+ }
+
+ }; // class RadixHeap
+
+} // namespace lemon
+
+#endif // LEMON_RADIX_HEAP_H
diff -r 2305167d2491 -r 76689f2fc02d test/heap_test.cc
--- a/test/heap_test.cc Thu Nov 05 16:01:39 2009 +0100
+++ b/test/heap_test.cc Thu Dec 10 17:10:25 2009 +0100
@@ -31,6 +31,9 @@
#include <lemon/maps.h>
#include <lemon/bin_heap.h>
+#include <lemon/fib_heap.h>
+#include <lemon/radix_heap.h>
+#include <lemon/bucket_heap.h>
#include "test_tools.h"
@@ -183,5 +186,39 @@
dijkstraHeapTest<NodeHeap>(digraph, length, source);
}
+ {
+ typedef FibHeap<Prio, ItemIntMap> IntHeap;
+ checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+ heapSortTest<IntHeap>();
+ heapIncreaseTest<IntHeap>();
+
+ typedef FibHeap<Prio, IntNodeMap > NodeHeap;
+ checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+ dijkstraHeapTest<NodeHeap>(digraph, length, source);
+ }
+
+ {
+ typedef RadixHeap<ItemIntMap> IntHeap;
+ checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+ heapSortTest<IntHeap>();
+ heapIncreaseTest<IntHeap>();
+
+ typedef RadixHeap<IntNodeMap > NodeHeap;
+ checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+ dijkstraHeapTest<NodeHeap>(digraph, length, source);
+ }
+
+ {
+ typedef BucketHeap<ItemIntMap> IntHeap;
+ checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
+ heapSortTest<IntHeap>();
+ heapIncreaseTest<IntHeap>();
+
+ typedef BucketHeap<IntNodeMap > NodeHeap;
+ checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
+ dijkstraHeapTest<NodeHeap>(digraph, length, source);
+ }
+
+
return 0;
}