1.1 --- a/lemon/bin_heap.h Thu Dec 20 15:21:22 2007 +0000
1.2 +++ b/lemon/bin_heap.h Thu Dec 27 13:40:16 2007 +0000
1.3 @@ -39,24 +39,24 @@
1.4 ///efficient. \c Compare specifies the ordering of the priorities. In a heap
1.5 ///one can change the priority of an item, add or erase an item, etc.
1.6 ///
1.7 - ///\param Prio Type of the priority of the items.
1.8 - ///\param ItemIntMap A read and writable Item int map, used internally
1.9 + ///\param _Prio Type of the priority of the items.
1.10 + ///\param _ItemIntMap A read and writable Item int map, used internally
1.11 ///to handle the cross references.
1.12 - ///\param Compare A class for the ordering of the priorities. The
1.13 - ///default is \c std::less<Prio>.
1.14 + ///\param _Compare A class for the ordering of the priorities. The
1.15 + ///default is \c std::less<_Prio>.
1.16 ///
1.17 ///\sa FibHeap
1.18 ///\sa Dijkstra
1.19 - template <typename Prio, typename ItemIntMap,
1.20 - typename Compare = std::less<Prio> >
1.21 + template <typename _Prio, typename _ItemIntMap,
1.22 + typename _Compare = std::less<_Prio> >
1.23 class BinHeap {
1.24
1.25 public:
1.26 - typedef typename ItemIntMap::Key ItemType;
1.27 - typedef Prio PrioType;
1.28 - typedef std::pair<ItemType,PrioType> PairType;
1.29 - typedef ItemIntMap ItemIntMapType;
1.30 - typedef Compare PrioCompare;
1.31 + typedef _ItemIntMap ItemIntMap;
1.32 + typedef _Prio Prio;
1.33 + typedef typename ItemIntMap::Key Item;
1.34 + typedef std::pair<Item,Prio> Pair;
1.35 + typedef _Compare Compare;
1.36
1.37 /// \brief Type to represent the items states.
1.38 ///
1.39 @@ -66,14 +66,14 @@
1.40 ///
1.41 /// The ItemIntMap \e should be initialized in such way that it maps
1.42 /// PRE_HEAP (-1) to any element to be put in the heap...
1.43 - enum state_enum {
1.44 + enum State {
1.45 IN_HEAP = 0,
1.46 PRE_HEAP = -1,
1.47 POST_HEAP = -2
1.48 };
1.49
1.50 private:
1.51 - std::vector<PairType> data;
1.52 + std::vector<Pair> data;
1.53 Compare comp;
1.54 ItemIntMap &iim;
1.55
1.56 @@ -122,11 +122,11 @@
1.57 static int parent(int i) { return (i-1)/2; }
1.58
1.59 static int second_child(int i) { return 2*i+2; }
1.60 - bool less(const PairType &p1, const PairType &p2) const {
1.61 + bool less(const Pair &p1, const Pair &p2) const {
1.62 return comp(p1.second, p2.second);
1.63 }
1.64
1.65 - int bubble_up(int hole, PairType p) {
1.66 + int bubble_up(int hole, Pair p) {
1.67 int par = parent(hole);
1.68 while( hole>0 && less(p,data[par]) ) {
1.69 move(data[par],hole);
1.70 @@ -137,7 +137,7 @@
1.71 return hole;
1.72 }
1.73
1.74 - int bubble_down(int hole, PairType p, int length) {
1.75 + int bubble_down(int hole, Pair p, int length) {
1.76 int child = second_child(hole);
1.77 while(child < length) {
1.78 if( less(data[child-1], data[child]) ) {
1.79 @@ -159,7 +159,7 @@
1.80 return hole;
1.81 }
1.82
1.83 - void move(const PairType &p, int i) {
1.84 + void move(const Pair &p, int i) {
1.85 data[i] = p;
1.86 iim.set(p.first, i);
1.87 }
1.88 @@ -169,7 +169,7 @@
1.89 ///
1.90 /// Adds \c p.first to the heap with priority \c p.second.
1.91 /// \param p The pair to insert.
1.92 - void push(const PairType &p) {
1.93 + void push(const Pair &p) {
1.94 int n = data.size();
1.95 data.resize(n+1);
1.96 bubble_up(n, p);
1.97 @@ -180,14 +180,14 @@
1.98 /// Adds \c i to the heap with priority \c p.
1.99 /// \param i The item to insert.
1.100 /// \param p The priority of the item.
1.101 - void push(const ItemType &i, const Prio &p) { push(PairType(i,p)); }
1.102 + void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
1.103
1.104 /// \brief Returns the item with minimum priority relative to \c Compare.
1.105 ///
1.106 /// This method returns the item with minimum priority relative to \c
1.107 /// Compare.
1.108 /// \pre The heap must be nonempty.
1.109 - ItemType top() const {
1.110 + Item top() const {
1.111 return data[0].first;
1.112 }
1.113
1.114 @@ -218,7 +218,7 @@
1.115 /// This method deletes item \c i from the heap.
1.116 /// \param i The item to erase.
1.117 /// \pre The item should be in the heap.
1.118 - void erase(const ItemType &i) {
1.119 + void erase(const Item &i) {
1.120 int h = iim[i];
1.121 int n = data.size()-1;
1.122 iim.set(data[h].first, POST_HEAP);
1.123 @@ -236,7 +236,7 @@
1.124 /// This function returns the priority of item \c i.
1.125 /// \pre \c i must be in the heap.
1.126 /// \param i The item.
1.127 - Prio operator[](const ItemType &i) const {
1.128 + Prio operator[](const Item &i) const {
1.129 int idx = iim[i];
1.130 return data[idx].second;
1.131 }
1.132 @@ -248,16 +248,16 @@
1.133 /// in the heap and sets the priority of \c i to \c p otherwise.
1.134 /// \param i The item.
1.135 /// \param p The priority.
1.136 - void set(const ItemType &i, const Prio &p) {
1.137 + void set(const Item &i, const Prio &p) {
1.138 int idx = iim[i];
1.139 if( idx < 0 ) {
1.140 push(i,p);
1.141 }
1.142 else if( comp(p, data[idx].second) ) {
1.143 - bubble_up(idx, PairType(i,p));
1.144 + bubble_up(idx, Pair(i,p));
1.145 }
1.146 else {
1.147 - bubble_down(idx, PairType(i,p), data.size());
1.148 + bubble_down(idx, Pair(i,p), data.size());
1.149 }
1.150 }
1.151
1.152 @@ -268,9 +268,9 @@
1.153 /// p relative to \c Compare.
1.154 /// \param i The item.
1.155 /// \param p The priority.
1.156 - void decrease(const ItemType &i, const Prio &p) {
1.157 + void decrease(const Item &i, const Prio &p) {
1.158 int idx = iim[i];
1.159 - bubble_up(idx, PairType(i,p));
1.160 + bubble_up(idx, Pair(i,p));
1.161 }
1.162
1.163 /// \brief Increases the priority of \c i to \c p.
1.164 @@ -280,9 +280,9 @@
1.165 /// p relative to \c Compare.
1.166 /// \param i The item.
1.167 /// \param p The priority.
1.168 - void increase(const ItemType &i, const Prio &p) {
1.169 + void increase(const Item &i, const Prio &p) {
1.170 int idx = iim[i];
1.171 - bubble_down(idx, PairType(i,p), data.size());
1.172 + bubble_down(idx, Pair(i,p), data.size());
1.173 }
1.174
1.175 /// \brief Returns if \c item is in, has already been in, or has
1.176 @@ -293,11 +293,11 @@
1.177 /// otherwise. In the latter case it is possible that \c item will
1.178 /// get back to the heap again.
1.179 /// \param i The item.
1.180 - state_enum state(const ItemType &i) const {
1.181 + State state(const Item &i) const {
1.182 int s = iim[i];
1.183 if( s>=0 )
1.184 s=0;
1.185 - return state_enum(s);
1.186 + return State(s);
1.187 }
1.188
1.189 /// \brief Sets the state of the \c item in the heap.
1.190 @@ -307,7 +307,7 @@
1.191 /// better time complexity.
1.192 /// \param i The item.
1.193 /// \param st The state. It should not be \c IN_HEAP.
1.194 - void state(const ItemType& i, state_enum st) {
1.195 + void state(const Item& i, State st) {
1.196 switch (st) {
1.197 case POST_HEAP:
1.198 case PRE_HEAP:
2.1 --- a/lemon/bucket_heap.h Thu Dec 20 15:21:22 2007 +0000
2.2 +++ b/lemon/bucket_heap.h Thu Dec 27 13:40:16 2007 +0000
2.3 @@ -49,9 +49,13 @@
2.4 class BucketHeap {
2.5
2.6 public:
2.7 + /// \e
2.8 typedef typename _ItemIntMap::Key Item;
2.9 + /// \e
2.10 typedef int Prio;
2.11 + /// \e
2.12 typedef std::pair<Item, Prio> Pair;
2.13 + /// \e
2.14 typedef _ItemIntMap ItemIntMap;
2.15
2.16 /// \brief Type to represent the items states.
2.17 @@ -62,7 +66,7 @@
2.18 ///
2.19 /// The ItemIntMap \e should be initialized in such way that it maps
2.20 /// PRE_HEAP (-1) to any element to be put in the heap...
2.21 - enum state_enum {
2.22 + enum State {
2.23 IN_HEAP = 0,
2.24 PRE_HEAP = -1,
2.25 POST_HEAP = -2
2.26 @@ -278,10 +282,10 @@
2.27 /// otherwise. In the latter case it is possible that \c item will
2.28 /// get back to the heap again.
2.29 /// \param i The item.
2.30 - state_enum state(const Item &i) const {
2.31 + State state(const Item &i) const {
2.32 int idx = index[i];
2.33 if (idx >= 0) idx = 0;
2.34 - return state_enum(idx);
2.35 + return State(idx);
2.36 }
2.37
2.38 /// \brief Sets the state of the \c item in the heap.
2.39 @@ -291,7 +295,7 @@
2.40 /// better time complexity.
2.41 /// \param i The item.
2.42 /// \param st The state. It should not be \c IN_HEAP.
2.43 - void state(const Item& i, state_enum st) {
2.44 + void state(const Item& i, State st) {
2.45 switch (st) {
2.46 case POST_HEAP:
2.47 case PRE_HEAP:
2.48 @@ -334,7 +338,7 @@
2.49 typedef std::pair<Item, Prio> Pair;
2.50 typedef _ItemIntMap ItemIntMap;
2.51
2.52 - enum state_enum {
2.53 + enum State {
2.54 IN_HEAP = 0,
2.55 PRE_HEAP = -1,
2.56 POST_HEAP = -2
2.57 @@ -472,13 +476,13 @@
2.58 lace(idx);
2.59 }
2.60
2.61 - state_enum state(const Item &i) const {
2.62 + State state(const Item &i) const {
2.63 int idx = index[i];
2.64 if (idx >= 0) idx = 0;
2.65 - return state_enum(idx);
2.66 + return State(idx);
2.67 }
2.68
2.69 - void state(const Item& i, state_enum st) {
2.70 + void state(const Item& i, State st) {
2.71 switch (st) {
2.72 case POST_HEAP:
2.73 case PRE_HEAP:
2.74 @@ -546,7 +550,7 @@
2.75 ///
2.76 /// The ItemIntMap \e should be initialized in such way that it maps
2.77 /// PRE_HEAP (-1) to any element to be put in the heap...
2.78 - enum state_enum {
2.79 + enum State {
2.80 IN_HEAP = 0,
2.81 PRE_HEAP = -1,
2.82 POST_HEAP = -2
2.83 @@ -683,10 +687,10 @@
2.84 /// otherwise. In the latter case it is possible that \c item will
2.85 /// get back to the heap again.
2.86 /// \param i The item.
2.87 - state_enum state(const Item &i) const {
2.88 + State state(const Item &i) const {
2.89 int idx = index[i];
2.90 if (idx >= 0) idx = 0;
2.91 - return state_enum(idx);
2.92 + return State(idx);
2.93 }
2.94
2.95 private:
2.96 @@ -716,7 +720,7 @@
2.97 typedef std::pair<Item, Prio> Pair;
2.98 typedef _ItemIntMap ItemIntMap;
2.99
2.100 - enum state_enum {
2.101 + enum State {
2.102 IN_HEAP = 0,
2.103 PRE_HEAP = -1,
2.104 POST_HEAP = -2
2.105 @@ -798,10 +802,10 @@
2.106 return -1;
2.107 }
2.108
2.109 - state_enum state(const Item &i) const {
2.110 + State state(const Item &i) const {
2.111 int idx = index[i];
2.112 if (idx >= 0) idx = 0;
2.113 - return state_enum(idx);
2.114 + return State(idx);
2.115 }
2.116
2.117 private:
3.1 --- a/lemon/concepts/heap.h Thu Dec 20 15:21:22 2007 +0000
3.2 +++ b/lemon/concepts/heap.h Thu Dec 27 13:40:16 2007 +0000
3.3 @@ -52,7 +52,7 @@
3.4 ///
3.5 /// The ItemIntMap _should_ be initialized in such way, that it maps
3.6 /// PRE_HEAP (-1) to any element to be put in the heap...
3.7 - enum state_enum {
3.8 + enum State {
3.9 IN_HEAP = 0,
3.10 PRE_HEAP = -1,
3.11 POST_HEAP = -2
3.12 @@ -155,7 +155,7 @@
3.13 /// otherwise. In the latter case it is possible that \c item will
3.14 /// get back to the heap again.
3.15 /// \param i The item.
3.16 - state_enum state(const Item &i) const {}
3.17 + State state(const Item &i) const {}
3.18
3.19 /// \brief Sets the state of the \c item in the heap.
3.20 ///
3.21 @@ -164,7 +164,7 @@
3.22 /// better time complexity.
3.23 /// \param i The item.
3.24 /// \param st The state. It should not be \c IN_HEAP.
3.25 - void state(const Item& i, state_enum st) {}
3.26 + void state(const Item& i, State st) {}
3.27
3.28
3.29 template <typename _Heap>
3.30 @@ -181,8 +181,8 @@
3.31 ignore_unused_variable_warning(item);
3.32 ignore_unused_variable_warning(prio);
3.33
3.34 - typedef typename _Heap::state_enum state_enum;
3.35 - state_enum state;
3.36 + typedef typename _Heap::State State;
3.37 + State state;
3.38
3.39 ignore_unused_variable_warning(state);
3.40
4.1 --- a/lemon/fib_heap.h Thu Dec 20 15:21:22 2007 +0000
4.2 +++ b/lemon/fib_heap.h Thu Dec 27 13:40:16 2007 +0000
4.3 @@ -41,31 +41,34 @@
4.4 ///
4.5 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
4.6 ///heap. In case of many calls to these operations, it is better to use a
4.7 - ///\e binary \e heap.
4.8 + ///\ref BinHeap "binary heap".
4.9 ///
4.10 - ///\param Prio Type of the priority of the items.
4.11 - ///\param ItemIntMap A read and writable Item int map, used internally
4.12 + ///\param _Prio Type of the priority of the items.
4.13 + ///\param _ItemIntMap A read and writable Item int map, used internally
4.14 ///to handle the cross references.
4.15 - ///\param Compare A class for the ordering of the priorities. The
4.16 - ///default is \c std::less<Prio>.
4.17 + ///\param _Compare A class for the ordering of the priorities. The
4.18 + ///default is \c std::less<_Prio>.
4.19 ///
4.20 ///\sa BinHeap
4.21 ///\sa Dijkstra
4.22 ///\author Jacint Szabo
4.23
4.24 #ifdef DOXYGEN
4.25 - template <typename Prio,
4.26 - typename ItemIntMap,
4.27 - typename Compare>
4.28 + template <typename _Prio,
4.29 + typename _ItemIntMap,
4.30 + typename _Compare>
4.31 #else
4.32 - template <typename Prio,
4.33 - typename ItemIntMap,
4.34 - typename Compare = std::less<Prio> >
4.35 + template <typename _Prio,
4.36 + typename _ItemIntMap,
4.37 + typename _Compare = std::less<_Prio> >
4.38 #endif
4.39 class FibHeap {
4.40 public:
4.41 + typedef _ItemIntMap ItemIntMap;
4.42 + typedef _Prio Prio;
4.43 typedef typename ItemIntMap::Key Item;
4.44 - typedef Prio PrioType;
4.45 + typedef std::pair<Item,Prio> Pair;
4.46 + typedef _Compare Compare;
4.47
4.48 private:
4.49 class store;
4.50 @@ -78,7 +81,7 @@
4.51
4.52 public:
4.53 ///Status of the nodes
4.54 - enum state_enum {
4.55 + enum State {
4.56 ///The node is in the heap
4.57 IN_HEAP = 0,
4.58 ///The node has never been in the heap
4.59 @@ -99,8 +102,8 @@
4.60 /// \c _iimap should be given to the constructor, since it is used
4.61 /// internally to handle the cross references. \c _comp is an
4.62 /// object for ordering of the priorities.
4.63 - FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
4.64 - iimap(_iimap), comp(_comp), num_items() {}
4.65 + FibHeap(ItemIntMap &_iimap, const Compare &_comp)
4.66 + : minimum(0), iimap(_iimap), comp(_comp), num_items() {}
4.67
4.68 /// \brief The number of items stored in the heap.
4.69 ///
4.70 @@ -128,163 +131,19 @@
4.71 /// This method calls \ref push(\c item, \c value) if \c item is not
4.72 /// stored in the heap and it calls \ref decrease(\c item, \c value) or
4.73 /// \ref increase(\c item, \c value) otherwise.
4.74 - void set (Item const item, PrioType const value);
4.75 + void set (const Item& item, const Prio& value) {
4.76 + int i=iimap[item];
4.77 + if ( i >= 0 && container[i].in ) {
4.78 + if ( comp(value, container[i].prio) ) decrease(item, value);
4.79 + if ( comp(container[i].prio, value) ) increase(item, value);
4.80 + } else push(item, value);
4.81 + }
4.82
4.83 /// \brief Adds \c item to the heap with priority \c value.
4.84 ///
4.85 /// Adds \c item to the heap with priority \c value.
4.86 /// \pre \c item must not be stored in the heap.
4.87 - void push (Item const item, PrioType const value);
4.88 -
4.89 - /// \brief Returns the item with minimum priority relative to \c Compare.
4.90 - ///
4.91 - /// This method returns the item with minimum priority relative to \c
4.92 - /// Compare.
4.93 - /// \pre The heap must be nonempty.
4.94 - Item top() const { return container[minimum].name; }
4.95 -
4.96 - /// \brief Returns the minimum priority relative to \c Compare.
4.97 - ///
4.98 - /// It returns the minimum priority relative to \c Compare.
4.99 - /// \pre The heap must be nonempty.
4.100 - PrioType prio() const { return container[minimum].prio; }
4.101 -
4.102 - /// \brief Returns the priority of \c item.
4.103 - ///
4.104 - /// This function returns the priority of \c item.
4.105 - /// \pre \c item must be in the heap.
4.106 - PrioType& operator[](const Item& item) {
4.107 - return container[iimap[item]].prio;
4.108 - }
4.109 -
4.110 - /// \brief Returns the priority of \c item.
4.111 - ///
4.112 - /// It returns the priority of \c item.
4.113 - /// \pre \c item must be in the heap.
4.114 - const PrioType& operator[](const Item& item) const {
4.115 - return container[iimap[item]].prio;
4.116 - }
4.117 -
4.118 -
4.119 - /// \brief Deletes the item with minimum priority relative to \c Compare.
4.120 - ///
4.121 - /// This method deletes the item with minimum priority relative to \c
4.122 - /// Compare from the heap.
4.123 - /// \pre The heap must be non-empty.
4.124 - void pop();
4.125 -
4.126 - /// \brief Deletes \c item from the heap.
4.127 - ///
4.128 - /// This method deletes \c item from the heap, if \c item was already
4.129 - /// stored in the heap. It is quite inefficient in Fibonacci heaps.
4.130 - void erase (const Item& item);
4.131 -
4.132 - /// \brief Decreases the priority of \c item to \c value.
4.133 - ///
4.134 - /// This method decreases the priority of \c item to \c value.
4.135 - /// \pre \c item must be stored in the heap with priority at least \c
4.136 - /// value relative to \c Compare.
4.137 - void decrease (Item item, PrioType const value);
4.138 -
4.139 - /// \brief Increases the priority of \c item to \c value.
4.140 - ///
4.141 - /// This method sets the priority of \c item to \c value. Though
4.142 - /// there is no precondition on the priority of \c item, this
4.143 - /// method should be used only if it is indeed necessary to increase
4.144 - /// (relative to \c Compare) the priority of \c item, because this
4.145 - /// method is inefficient.
4.146 - void increase (Item item, PrioType const value) {
4.147 - erase(item);
4.148 - push(item, value);
4.149 - }
4.150 -
4.151 -
4.152 - /// \brief Returns if \c item is in, has already been in, or has never
4.153 - /// been in the heap.
4.154 - ///
4.155 - /// This method returns PRE_HEAP if \c item has never been in the
4.156 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
4.157 - /// otherwise. In the latter case it is possible that \c item will
4.158 - /// get back to the heap again.
4.159 - state_enum state(const Item &item) const {
4.160 - int i=iimap[item];
4.161 - if( i>=0 ) {
4.162 - if ( container[i].in ) i=0;
4.163 - else i=-2;
4.164 - }
4.165 - return state_enum(i);
4.166 - }
4.167 -
4.168 - /// \brief Sets the state of the \c item in the heap.
4.169 - ///
4.170 - /// Sets the state of the \c item in the heap. It can be used to
4.171 - /// manually clear the heap when it is important to achive the
4.172 - /// better time complexity.
4.173 - /// \param i The item.
4.174 - /// \param st The state. It should not be \c IN_HEAP.
4.175 - void state(const Item& i, state_enum st) {
4.176 - switch (st) {
4.177 - case POST_HEAP:
4.178 - case PRE_HEAP:
4.179 - if (state(i) == IN_HEAP) {
4.180 - erase(i);
4.181 - }
4.182 - iimap[i] = st;
4.183 - break;
4.184 - case IN_HEAP:
4.185 - break;
4.186 - }
4.187 - }
4.188 -
4.189 - private:
4.190 -
4.191 - void balance();
4.192 - void makeroot(int c);
4.193 - void cut(int a, int b);
4.194 - void cascade(int a);
4.195 - void fuse(int a, int b);
4.196 - void unlace(int a);
4.197 -
4.198 -
4.199 - class store {
4.200 - friend class FibHeap;
4.201 -
4.202 - Item name;
4.203 - int parent;
4.204 - int left_neighbor;
4.205 - int right_neighbor;
4.206 - int child;
4.207 - int degree;
4.208 - bool marked;
4.209 - bool in;
4.210 - PrioType prio;
4.211 -
4.212 - store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
4.213 - };
4.214 - };
4.215 -
4.216 -
4.217 -
4.218 - // **********************************************************************
4.219 - // IMPLEMENTATIONS
4.220 - // **********************************************************************
4.221 -
4.222 - template <typename Prio, typename ItemIntMap,
4.223 - typename Compare>
4.224 - void FibHeap<Prio, ItemIntMap, Compare>::set
4.225 - (Item const item, PrioType const value)
4.226 - {
4.227 - int i=iimap[item];
4.228 - if ( i >= 0 && container[i].in ) {
4.229 - if ( comp(value, container[i].prio) ) decrease(item, value);
4.230 - if ( comp(container[i].prio, value) ) increase(item, value);
4.231 - } else push(item, value);
4.232 - }
4.233 -
4.234 - template <typename Prio, typename ItemIntMap,
4.235 - typename Compare>
4.236 - void FibHeap<Prio, ItemIntMap, Compare>::push
4.237 - (Item const item, PrioType const value) {
4.238 + void push (const Item& item, const Prio& value) {
4.239 int i=iimap[item];
4.240 if ( i < 0 ) {
4.241 int s=container.size();
4.242 @@ -314,9 +173,33 @@
4.243 ++num_items;
4.244 }
4.245
4.246 - template <typename Prio, typename ItemIntMap,
4.247 - typename Compare>
4.248 - void FibHeap<Prio, ItemIntMap, Compare>::pop() {
4.249 + /// \brief Returns the item with minimum priority relative to \c Compare.
4.250 + ///
4.251 + /// This method returns the item with minimum priority relative to \c
4.252 + /// Compare.
4.253 + /// \pre The heap must be nonempty.
4.254 + Item top() const { return container[minimum].name; }
4.255 +
4.256 + /// \brief Returns the minimum priority relative to \c Compare.
4.257 + ///
4.258 + /// It returns the minimum priority relative to \c Compare.
4.259 + /// \pre The heap must be nonempty.
4.260 + const Prio& prio() const { return container[minimum].prio; }
4.261 +
4.262 + /// \brief Returns the priority of \c item.
4.263 + ///
4.264 + /// It returns the priority of \c item.
4.265 + /// \pre \c item must be in the heap.
4.266 + const Prio& operator[](const Item& item) const {
4.267 + return container[iimap[item]].prio;
4.268 + }
4.269 +
4.270 + /// \brief Deletes the item with minimum priority relative to \c Compare.
4.271 + ///
4.272 + /// This method deletes the item with minimum priority relative to \c
4.273 + /// Compare from the heap.
4.274 + /// \pre The heap must be non-empty.
4.275 + void pop() {
4.276 /*The first case is that there are only one root.*/
4.277 if ( container[minimum].left_neighbor==minimum ) {
4.278 container[minimum].in=false;
4.279 @@ -333,7 +216,7 @@
4.280 int left=container[minimum].left_neighbor;
4.281 int child=container[minimum].child;
4.282 int last_child=container[child].left_neighbor;
4.283 -
4.284 +
4.285 makeroot(child);
4.286
4.287 container[left].right_neighbor=child;
4.288 @@ -347,11 +230,11 @@
4.289 --num_items;
4.290 }
4.291
4.292 -
4.293 - template <typename Prio, typename ItemIntMap,
4.294 - typename Compare>
4.295 - void FibHeap<Prio, ItemIntMap, Compare>::erase
4.296 - (const Item& item) {
4.297 + /// \brief Deletes \c item from the heap.
4.298 + ///
4.299 + /// This method deletes \c item from the heap, if \c item was already
4.300 + /// stored in the heap. It is quite inefficient in Fibonacci heaps.
4.301 + void erase (const Item& item) {
4.302 int i=iimap[item];
4.303
4.304 if ( i >= 0 && container[i].in ) {
4.305 @@ -363,12 +246,14 @@
4.306 minimum=i; //As if its prio would be -infinity
4.307 pop();
4.308 }
4.309 - }
4.310 -
4.311 - template <typename Prio, typename ItemIntMap,
4.312 - typename Compare>
4.313 - void FibHeap<Prio, ItemIntMap, Compare>::decrease
4.314 - (Item item, PrioType const value) {
4.315 + }
4.316 +
4.317 + /// \brief Decreases the priority of \c item to \c value.
4.318 + ///
4.319 + /// This method decreases the priority of \c item to \c value.
4.320 + /// \pre \c item must be stored in the heap with priority at least \c
4.321 + /// value relative to \c Compare.
4.322 + void decrease (Item item, const Prio& value) {
4.323 int i=iimap[item];
4.324 container[i].prio=value;
4.325 int p=container[i].parent;
4.326 @@ -378,26 +263,75 @@
4.327 cascade(p);
4.328 }
4.329 if ( comp(value, container[minimum].prio) ) minimum=i;
4.330 - }
4.331 -
4.332 + }
4.333
4.334 - template <typename Prio, typename ItemIntMap,
4.335 - typename Compare>
4.336 - void FibHeap<Prio, ItemIntMap, Compare>::balance() {
4.337 + /// \brief Increases the priority of \c item to \c value.
4.338 + ///
4.339 + /// This method sets the priority of \c item to \c value. Though
4.340 + /// there is no precondition on the priority of \c item, this
4.341 + /// method should be used only if it is indeed necessary to increase
4.342 + /// (relative to \c Compare) the priority of \c item, because this
4.343 + /// method is inefficient.
4.344 + void increase (Item item, const Prio& value) {
4.345 + erase(item);
4.346 + push(item, value);
4.347 + }
4.348
4.349 - int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
4.350 +
4.351 + /// \brief Returns if \c item is in, has already been in, or has never
4.352 + /// been in the heap.
4.353 + ///
4.354 + /// This method returns PRE_HEAP if \c item has never been in the
4.355 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
4.356 + /// otherwise. In the latter case it is possible that \c item will
4.357 + /// get back to the heap again.
4.358 + State state(const Item &item) const {
4.359 + int i=iimap[item];
4.360 + if( i>=0 ) {
4.361 + if ( container[i].in ) i=0;
4.362 + else i=-2;
4.363 + }
4.364 + return State(i);
4.365 + }
4.366 +
4.367 + /// \brief Sets the state of the \c item in the heap.
4.368 + ///
4.369 + /// Sets the state of the \c item in the heap. It can be used to
4.370 + /// manually clear the heap when it is important to achive the
4.371 + /// better time complexity.
4.372 + /// \param i The item.
4.373 + /// \param st The state. It should not be \c IN_HEAP.
4.374 + void state(const Item& i, State st) {
4.375 + switch (st) {
4.376 + case POST_HEAP:
4.377 + case PRE_HEAP:
4.378 + if (state(i) == IN_HEAP) {
4.379 + erase(i);
4.380 + }
4.381 + iimap[i] = st;
4.382 + break;
4.383 + case IN_HEAP:
4.384 + break;
4.385 + }
4.386 + }
4.387 +
4.388 + private:
4.389 +
4.390 + void balance() {
4.391 +
4.392 + int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
4.393
4.394 - std::vector<int> A(maxdeg,-1);
4.395 + std::vector<int> A(maxdeg,-1);
4.396
4.397 - /*
4.398 - *Recall that now minimum does not point to the minimum prio element.
4.399 - *We set minimum to this during balance().
4.400 - */
4.401 - int anchor=container[minimum].left_neighbor;
4.402 - int next=minimum;
4.403 - bool end=false;
4.404 + /*
4.405 + *Recall that now minimum does not point to the minimum prio element.
4.406 + *We set minimum to this during balance().
4.407 + */
4.408 + int anchor=container[minimum].left_neighbor;
4.409 + int next=minimum;
4.410 + bool end=false;
4.411
4.412 - do {
4.413 + do {
4.414 int active=next;
4.415 if ( anchor==active ) end=true;
4.416 int d=container[active].degree;
4.417 @@ -414,64 +348,53 @@
4.418 ++d;
4.419 }
4.420 A[d]=active;
4.421 - } while ( !end );
4.422 + } while ( !end );
4.423
4.424
4.425 - while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
4.426 - int s=minimum;
4.427 - int m=minimum;
4.428 - do {
4.429 - if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
4.430 - s=container[s].right_neighbor;
4.431 - } while ( s != m );
4.432 + while ( container[minimum].parent >=0 )
4.433 + minimum=container[minimum].parent;
4.434 + int s=minimum;
4.435 + int m=minimum;
4.436 + do {
4.437 + if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
4.438 + s=container[s].right_neighbor;
4.439 + } while ( s != m );
4.440 }
4.441
4.442 - template <typename Prio, typename ItemIntMap,
4.443 - typename Compare>
4.444 - void FibHeap<Prio, ItemIntMap, Compare>::makeroot
4.445 - (int c) {
4.446 + void makeroot(int c) {
4.447 int s=c;
4.448 do {
4.449 container[s].parent=-1;
4.450 s=container[s].right_neighbor;
4.451 } while ( s != c );
4.452 }
4.453 -
4.454 -
4.455 - template <typename Prio, typename ItemIntMap,
4.456 - typename Compare>
4.457 - void FibHeap<Prio, ItemIntMap, Compare>::cut
4.458 - (int a, int b) {
4.459 - /*
4.460 - *Replacing a from the children of b.
4.461 - */
4.462 - --container[b].degree;
4.463 +
4.464 + void cut(int a, int b) {
4.465 + /*
4.466 + *Replacing a from the children of b.
4.467 + */
4.468 + --container[b].degree;
4.469
4.470 - if ( container[b].degree !=0 ) {
4.471 - int child=container[b].child;
4.472 - if ( child==a )
4.473 - container[b].child=container[child].right_neighbor;
4.474 - unlace(a);
4.475 + if ( container[b].degree !=0 ) {
4.476 + int child=container[b].child;
4.477 + if ( child==a )
4.478 + container[b].child=container[child].right_neighbor;
4.479 + unlace(a);
4.480 + }
4.481 +
4.482 +
4.483 + /*Lacing a to the roots.*/
4.484 + int right=container[minimum].right_neighbor;
4.485 + container[minimum].right_neighbor=a;
4.486 + container[a].left_neighbor=minimum;
4.487 + container[a].right_neighbor=right;
4.488 + container[right].left_neighbor=a;
4.489 +
4.490 + container[a].parent=-1;
4.491 + container[a].marked=false;
4.492 }
4.493 -
4.494 -
4.495 - /*Lacing a to the roots.*/
4.496 - int right=container[minimum].right_neighbor;
4.497 - container[minimum].right_neighbor=a;
4.498 - container[a].left_neighbor=minimum;
4.499 - container[a].right_neighbor=right;
4.500 - container[right].left_neighbor=a;
4.501 -
4.502 - container[a].parent=-1;
4.503 - container[a].marked=false;
4.504 - }
4.505 -
4.506
4.507 - template <typename Prio, typename ItemIntMap,
4.508 - typename Compare>
4.509 - void FibHeap<Prio, ItemIntMap, Compare>::cascade
4.510 - (int a)
4.511 - {
4.512 + void cascade(int a) {
4.513 if ( container[a].parent!=-1 ) {
4.514 int p=container[a].parent;
4.515
4.516 @@ -483,11 +406,7 @@
4.517 }
4.518 }
4.519
4.520 -
4.521 - template <typename Prio, typename ItemIntMap,
4.522 - typename Compare>
4.523 - void FibHeap<Prio, ItemIntMap, Compare>::fuse
4.524 - (int a, int b) {
4.525 + void fuse(int a, int b) {
4.526 unlace(b);
4.527
4.528 /*Lacing b under a.*/
4.529 @@ -511,20 +430,33 @@
4.530 container[b].marked=false;
4.531 }
4.532
4.533 -
4.534 - /*
4.535 - *It is invoked only if a has siblings.
4.536 - */
4.537 - template <typename Prio, typename ItemIntMap,
4.538 - typename Compare>
4.539 - void FibHeap<Prio, ItemIntMap, Compare>::unlace
4.540 - (int a) {
4.541 + /*
4.542 + *It is invoked only if a has siblings.
4.543 + */
4.544 + void unlace(int a) {
4.545 int leftn=container[a].left_neighbor;
4.546 int rightn=container[a].right_neighbor;
4.547 container[leftn].right_neighbor=rightn;
4.548 container[rightn].left_neighbor=leftn;
4.549 - }
4.550 -
4.551 + }
4.552 +
4.553 +
4.554 + class store {
4.555 + friend class FibHeap;
4.556 +
4.557 + Item name;
4.558 + int parent;
4.559 + int left_neighbor;
4.560 + int right_neighbor;
4.561 + int child;
4.562 + int degree;
4.563 + bool marked;
4.564 + bool in;
4.565 + Prio prio;
4.566 +
4.567 + store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
4.568 + };
4.569 + };
4.570
4.571 } //namespace lemon
4.572
5.1 --- a/lemon/radix_heap.h Thu Dec 20 15:21:22 2007 +0000
5.2 +++ b/lemon/radix_heap.h Thu Dec 27 13:40:16 2007 +0000
5.3 @@ -28,19 +28,6 @@
5.4
5.5 namespace lemon {
5.6
5.7 - /// \brief Exception thrown by RadixHeap.
5.8 - ///
5.9 - /// This Exception is thrown when a smaller priority
5.10 - /// is inserted into the \e RadixHeap then the last time erased.
5.11 - /// \see RadixHeap
5.12 - /// \author Balazs Dezso
5.13 -
5.14 - class UnderFlowPriorityError : public RuntimeError {
5.15 - public:
5.16 - virtual const char* what() const throw() {
5.17 - return "lemon::UnderFlowPriorityError";
5.18 - }
5.19 - };
5.20
5.21 /// \ingroup auxdata
5.22 ///
5.23 @@ -69,6 +56,20 @@
5.24 typedef int Prio;
5.25 typedef _ItemIntMap ItemIntMap;
5.26
5.27 + /// \brief Exception thrown by RadixHeap.
5.28 + ///
5.29 + /// This Exception is thrown when a smaller priority
5.30 + /// is inserted into the \e RadixHeap then the last time erased.
5.31 + /// \see RadixHeap
5.32 + /// \author Balazs Dezso
5.33 +
5.34 + class UnderFlowPriorityError : public RuntimeError {
5.35 + public:
5.36 + virtual const char* what() const throw() {
5.37 + return "lemon::RadixHeap::UnderFlowPriorityError";
5.38 + }
5.39 + };
5.40 +
5.41 /// \brief Type to represent the items states.
5.42 ///
5.43 /// Each Item element have a state associated to it. It may be "in heap",
5.44 @@ -77,7 +78,7 @@
5.45 ///
5.46 /// The ItemIntMap \e should be initialized in such way that it maps
5.47 /// PRE_HEAP (-1) to any element to be put in the heap...
5.48 - enum state_enum {
5.49 + enum State {
5.50 IN_HEAP = 0,
5.51 PRE_HEAP = -1,
5.52 POST_HEAP = -2
5.53 @@ -401,10 +402,10 @@
5.54 /// otherwise. In the latter case it is possible that \c item will
5.55 /// get back to the heap again.
5.56 /// \param i The item.
5.57 - state_enum state(const Item &i) const {
5.58 + State state(const Item &i) const {
5.59 int s = iim[i];
5.60 if( s >= 0 ) s = 0;
5.61 - return state_enum(s);
5.62 + return State(s);
5.63 }
5.64
5.65 /// \brief Sets the state of the \c item in the heap.
5.66 @@ -414,7 +415,7 @@
5.67 /// better time complexity.
5.68 /// \param i The item.
5.69 /// \param st The state. It should not be \c IN_HEAP.
5.70 - void state(const Item& i, state_enum st) {
5.71 + void state(const Item& i, State st) {
5.72 switch (st) {
5.73 case POST_HEAP:
5.74 case PRE_HEAP: