Unification of names in heaps (#50)
authorBalazs Dezso <deba@inf.elte.hu>
Thu, 11 Jun 2009 23:13:24 +0200
changeset 7309f529abcaebf
parent 729 bb8c4cd57900
child 733 7439dc5fe1b9
child 738 9e54e3b27db0
child 740 7bda7860e0a8
child 743 c9b9da1a90a0
child 748 d1a9224f1e30
child 756 0747f332c478
child 760 4ac30454f1c1
child 765 703ebf476a1d
child 805 b31e130db13d
Unification of names in heaps (#50)
lemon/bin_heap.h
lemon/bucket_heap.h
lemon/fib_heap.h
lemon/radix_heap.h
     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;