1.1 --- a/lemon/bin_heap.h Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/lemon/bin_heap.h Sun Jul 13 19:51:02 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -48,7 +48,7 @@
1.13 ///\sa FibHeap
1.14 ///\sa Dijkstra
1.15 template <typename _Prio, typename _ItemIntMap,
1.16 - typename _Compare = std::less<_Prio> >
1.17 + typename _Compare = std::less<_Prio> >
1.18 class BinHeap {
1.19
1.20 public:
1.21 @@ -90,7 +90,7 @@
1.22 /// internally to handle the cross references. The value of the map
1.23 /// should be PRE_HEAP (-1) for each element.
1.24 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
1.25 -
1.26 +
1.27 /// \brief The constructor.
1.28 ///
1.29 /// The constructor.
1.30 @@ -99,7 +99,7 @@
1.31 /// should be PRE_HEAP (-1) for each element.
1.32 ///
1.33 /// \param _comp The comparator function object.
1.34 - BinHeap(ItemIntMap &_iim, const Compare &_comp)
1.35 + BinHeap(ItemIntMap &_iim, const Compare &_comp)
1.36 : iim(_iim), comp(_comp) {}
1.37
1.38
1.39 @@ -107,20 +107,20 @@
1.40 ///
1.41 /// \brief Returns the number of items stored in the heap.
1.42 int size() const { return data.size(); }
1.43 -
1.44 +
1.45 /// \brief Checks if the heap stores no items.
1.46 ///
1.47 /// Returns \c true if and only if the heap stores no items.
1.48 bool empty() const { return data.empty(); }
1.49
1.50 /// \brief Make empty this heap.
1.51 - ///
1.52 + ///
1.53 /// Make empty this heap. It does not change the cross reference map.
1.54 /// If you want to reuse what is not surely empty you should first clear
1.55 /// the heap and after that you should set the cross reference map for
1.56 /// each item to \c PRE_HEAP.
1.57 - void clear() {
1.58 - data.clear();
1.59 + void clear() {
1.60 + data.clear();
1.61 }
1.62
1.63 private:
1.64 @@ -134,9 +134,9 @@
1.65 int bubble_up(int hole, Pair p) {
1.66 int par = parent(hole);
1.67 while( hole>0 && less(p,data[par]) ) {
1.68 - move(data[par],hole);
1.69 - hole = par;
1.70 - par = parent(hole);
1.71 + move(data[par],hole);
1.72 + hole = par;
1.73 + par = parent(hole);
1.74 }
1.75 move(p, hole);
1.76 return hole;
1.77 @@ -145,19 +145,19 @@
1.78 int bubble_down(int hole, Pair p, int length) {
1.79 int child = second_child(hole);
1.80 while(child < length) {
1.81 - if( less(data[child-1], data[child]) ) {
1.82 - --child;
1.83 - }
1.84 - if( !less(data[child], p) )
1.85 - goto ok;
1.86 - move(data[child], hole);
1.87 - hole = child;
1.88 - child = second_child(hole);
1.89 + if( less(data[child-1], data[child]) ) {
1.90 + --child;
1.91 + }
1.92 + if( !less(data[child], p) )
1.93 + goto ok;
1.94 + move(data[child], hole);
1.95 + hole = child;
1.96 + child = second_child(hole);
1.97 }
1.98 child--;
1.99 if( child<length && less(data[child], p) ) {
1.100 - move(data[child], hole);
1.101 - hole=child;
1.102 + move(data[child], hole);
1.103 + hole=child;
1.104 }
1.105 ok:
1.106 move(p, hole);
1.107 @@ -181,8 +181,8 @@
1.108 }
1.109
1.110 /// \brief Insert an item into the heap with the given heap.
1.111 - ///
1.112 - /// Adds \c i to the heap with priority \c p.
1.113 + ///
1.114 + /// Adds \c i to the heap with priority \c p.
1.115 /// \param i The item to insert.
1.116 /// \param p The priority of the item.
1.117 void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
1.118 @@ -190,8 +190,8 @@
1.119 /// \brief Returns the item with minimum priority relative to \c Compare.
1.120 ///
1.121 /// This method returns the item with minimum priority relative to \c
1.122 - /// Compare.
1.123 - /// \pre The heap must be nonempty.
1.124 + /// Compare.
1.125 + /// \pre The heap must be nonempty.
1.126 Item top() const {
1.127 return data[0].first;
1.128 }
1.129 @@ -207,13 +207,13 @@
1.130 /// \brief Deletes the item with minimum priority relative to \c Compare.
1.131 ///
1.132 /// This method deletes the item with minimum priority relative to \c
1.133 - /// Compare from the heap.
1.134 - /// \pre The heap must be non-empty.
1.135 + /// Compare from the heap.
1.136 + /// \pre The heap must be non-empty.
1.137 void pop() {
1.138 int n = data.size()-1;
1.139 iim.set(data[0].first, POST_HEAP);
1.140 if (n > 0) {
1.141 - bubble_down(0, data[n], n);
1.142 + bubble_down(0, data[n], n);
1.143 }
1.144 data.pop_back();
1.145 }
1.146 @@ -228,17 +228,17 @@
1.147 int n = data.size()-1;
1.148 iim.set(data[h].first, POST_HEAP);
1.149 if( h < n ) {
1.150 - if ( bubble_up(h, data[n]) == h) {
1.151 - bubble_down(h, data[n], n);
1.152 - }
1.153 + if ( bubble_up(h, data[n]) == h) {
1.154 + bubble_down(h, data[n], n);
1.155 + }
1.156 }
1.157 data.pop_back();
1.158 }
1.159
1.160 -
1.161 +
1.162 /// \brief Returns the priority of \c i.
1.163 ///
1.164 - /// This function returns the priority of item \c i.
1.165 + /// This function returns the priority of item \c i.
1.166 /// \pre \c i must be in the heap.
1.167 /// \param i The item.
1.168 Prio operator[](const Item &i) const {
1.169 @@ -246,7 +246,7 @@
1.170 return data[idx].second;
1.171 }
1.172
1.173 - /// \brief \c i gets to the heap with priority \c p independently
1.174 + /// \brief \c i gets to the heap with priority \c p independently
1.175 /// if \c i was already there.
1.176 ///
1.177 /// This method calls \ref push(\c i, \c p) if \c i is not stored
1.178 @@ -256,13 +256,13 @@
1.179 void set(const Item &i, const Prio &p) {
1.180 int idx = iim[i];
1.181 if( idx < 0 ) {
1.182 - push(i,p);
1.183 + push(i,p);
1.184 }
1.185 else if( comp(p, data[idx].second) ) {
1.186 - bubble_up(idx, Pair(i,p));
1.187 + bubble_up(idx, Pair(i,p));
1.188 }
1.189 else {
1.190 - bubble_down(idx, Pair(i,p), data.size());
1.191 + bubble_down(idx, Pair(i,p), data.size());
1.192 }
1.193 }
1.194
1.195 @@ -277,10 +277,10 @@
1.196 int idx = iim[i];
1.197 bubble_up(idx, Pair(i,p));
1.198 }
1.199 -
1.200 +
1.201 /// \brief Increases the priority of \c i to \c p.
1.202 ///
1.203 - /// This method sets the priority of item \c i to \c p.
1.204 + /// This method sets the priority of item \c i to \c p.
1.205 /// \pre \c i must be stored in the heap with priority at most \c
1.206 /// p relative to \c Compare.
1.207 /// \param i The item.
1.208 @@ -290,7 +290,7 @@
1.209 bubble_down(idx, Pair(i,p), data.size());
1.210 }
1.211
1.212 - /// \brief Returns if \c item is in, has already been in, or has
1.213 + /// \brief Returns if \c item is in, has already been in, or has
1.214 /// never been in the heap.
1.215 ///
1.216 /// This method returns PRE_HEAP if \c item has never been in the
1.217 @@ -301,7 +301,7 @@
1.218 State state(const Item &i) const {
1.219 int s = iim[i];
1.220 if( s>=0 )
1.221 - s=0;
1.222 + s=0;
1.223 return State(s);
1.224 }
1.225
1.226 @@ -311,7 +311,7 @@
1.227 /// manually clear the heap when it is important to achive the
1.228 /// better time complexity.
1.229 /// \param i The item.
1.230 - /// \param st The state. It should not be \c IN_HEAP.
1.231 + /// \param st The state. It should not be \c IN_HEAP.
1.232 void state(const Item& i, State st) {
1.233 switch (st) {
1.234 case POST_HEAP:
1.235 @@ -340,7 +340,7 @@
1.236 }
1.237
1.238 }; // class BinHeap
1.239 -
1.240 +
1.241 } // namespace lemon
1.242
1.243 #endif // LEMON_BIN_HEAP_H