Improve and unify the doc + names in the new heaps (#301)
authorPeter Kovacs <kpeter@inf.elte.hu>
Thu, 09 Jul 2009 04:07:08 +0200
changeset 750bb3392fe91f2
parent 749 bdc7dfc8c054
child 751 7124b2581f72
Improve and unify the doc + names in the new heaps (#301)
lemon/binom_heap.h
lemon/fourary_heap.h
lemon/kary_heap.h
lemon/pairing_heap.h
     1.1 --- a/lemon/binom_heap.h	Thu Jul 09 02:39:47 2009 +0200
     1.2 +++ b/lemon/binom_heap.h	Thu Jul 09 04:07:08 2009 +0200
     1.3 @@ -1,8 +1,8 @@
     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 + * Copyright (C) 2003-2009
    1.12   * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.13   * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.14   *
    1.15 @@ -20,193 +20,199 @@
    1.16  #define LEMON_BINOM_HEAP_H
    1.17  
    1.18  ///\file
    1.19 -///\ingroup auxdat
    1.20 +///\ingroup heaps
    1.21  ///\brief Binomial Heap implementation.
    1.22  
    1.23  #include <vector>
    1.24 +#include <utility>
    1.25  #include <functional>
    1.26  #include <lemon/math.h>
    1.27  #include <lemon/counter.h>
    1.28  
    1.29  namespace lemon {
    1.30  
    1.31 -  /// \ingroup auxdat
    1.32 +  /// \ingroup heaps
    1.33    ///
    1.34 -  ///\brief Binomial Heap.
    1.35 +  ///\brief Binomial heap data structure.
    1.36    ///
    1.37 -  ///This class implements the \e Binomial \e heap data structure. A \e heap
    1.38 -  ///is a data structure for storing items with specified values called \e
    1.39 -  ///priorities in such a way that finding the item with minimum priority is
    1.40 -  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    1.41 -  ///one can change the priority of an item, add or erase an item, etc.
    1.42 +  /// This class implements the \e binomial \e heap data structure.
    1.43 +  /// It fully conforms to the \ref concepts::Heap "heap concept".
    1.44    ///
    1.45 -  ///The methods \ref increase and \ref erase are not efficient in a Binomial
    1.46 -  ///heap. In case of many calls to these operations, it is better to use a
    1.47 -  ///\ref BinHeap "binary heap".
    1.48 +  /// The methods \ref increase() and \ref erase() are not efficient
    1.49 +  /// in a binomial heap. In case of many calls of these operations,
    1.50 +  /// it is better to use other heap structure, e.g. \ref BinHeap
    1.51 +  /// "binary heap".
    1.52    ///
    1.53 -  ///\param _Prio Type of the priority of the items.
    1.54 -  ///\param _ItemIntMap A read and writable Item int map, used internally
    1.55 -  ///to handle the cross references.
    1.56 -  ///\param _Compare A class for the ordering of the priorities. The
    1.57 -  ///default is \c std::less<_Prio>.
    1.58 -  ///
    1.59 -  ///\sa BinHeap
    1.60 -  ///\sa Dijkstra
    1.61 -  ///\author Dorian Batha
    1.62 -
    1.63 +  /// \tparam PR Type of the priorities of the items.
    1.64 +  /// \tparam IM A read-writable item map with \c int values, used
    1.65 +  /// internally to handle the cross references.
    1.66 +  /// \tparam CMP A functor class for comparing the priorities.
    1.67 +  /// The default is \c std::less<PR>.
    1.68  #ifdef DOXYGEN
    1.69 -  template <typename _Prio,
    1.70 -            typename _ItemIntMap,
    1.71 -            typename _Compare>
    1.72 +  template <typename PR, typename IM, typename CMP>
    1.73  #else
    1.74 -  template <typename _Prio,
    1.75 -            typename _ItemIntMap,
    1.76 -            typename _Compare = std::less<_Prio> >
    1.77 +  template <typename PR, typename IM, typename CMP = std::less<PR> >
    1.78  #endif
    1.79    class BinomHeap {
    1.80    public:
    1.81 -    typedef _ItemIntMap ItemIntMap;
    1.82 -    typedef _Prio Prio;
    1.83 +    /// Type of the item-int map.
    1.84 +    typedef IM ItemIntMap;
    1.85 +    /// Type of the priorities.
    1.86 +    typedef PR Prio;
    1.87 +    /// Type of the items stored in the heap.
    1.88      typedef typename ItemIntMap::Key Item;
    1.89 -    typedef std::pair<Item,Prio> Pair;
    1.90 -    typedef _Compare Compare;
    1.91 +    /// Functor type for comparing the priorities.
    1.92 +    typedef CMP Compare;
    1.93 +
    1.94 +    /// \brief Type to represent the states of the items.
    1.95 +    ///
    1.96 +    /// Each item has a state associated to it. It can be "in heap",
    1.97 +    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    1.98 +    /// heap's point of view, but may be useful to the user.
    1.99 +    ///
   1.100 +    /// The item-int map must be initialized in such way that it assigns
   1.101 +    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
   1.102 +    enum State {
   1.103 +      IN_HEAP = 0,    ///< = 0.
   1.104 +      PRE_HEAP = -1,  ///< = -1.
   1.105 +      POST_HEAP = -2  ///< = -2.
   1.106 +    };
   1.107  
   1.108    private:
   1.109      class store;
   1.110  
   1.111 -    std::vector<store> container;
   1.112 -    int minimum, head;
   1.113 -    ItemIntMap &iimap;
   1.114 -    Compare comp;
   1.115 -    int num_items;
   1.116 +    std::vector<store> _data;
   1.117 +    int _min, _head;
   1.118 +    ItemIntMap &_iim;
   1.119 +    Compare _comp;
   1.120 +    int _num_items;
   1.121  
   1.122    public:
   1.123 -    ///Status of the nodes
   1.124 -    enum State {
   1.125 -      ///The node is in the heap
   1.126 -      IN_HEAP = 0,
   1.127 -      ///The node has never been in the heap
   1.128 -      PRE_HEAP = -1,
   1.129 -      ///The node was in the heap but it got out of it
   1.130 -      POST_HEAP = -2
   1.131 -    };
   1.132 +    /// \brief Constructor.
   1.133 +    ///
   1.134 +    /// Constructor.
   1.135 +    /// \param map A map that assigns \c int values to the items.
   1.136 +    /// It is used internally to handle the cross references.
   1.137 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   1.138 +    explicit BinomHeap(ItemIntMap &map)
   1.139 +      : _min(0), _head(-1), _iim(map), _num_items(0) {}
   1.140  
   1.141 -    /// \brief The constructor
   1.142 +    /// \brief Constructor.
   1.143      ///
   1.144 -    /// \c _iimap should be given to the constructor, since it is
   1.145 -    ///   used internally to handle the cross references.
   1.146 -    explicit BinomHeap(ItemIntMap &_iimap)
   1.147 -      : minimum(0), head(-1), iimap(_iimap), num_items() {}
   1.148 -
   1.149 -    /// \brief The constructor
   1.150 -    ///
   1.151 -    /// \c _iimap should be given to the constructor, since it is used
   1.152 -    /// internally to handle the cross references. \c _comp is an
   1.153 -    /// object for ordering of the priorities.
   1.154 -    BinomHeap(ItemIntMap &_iimap, const Compare &_comp)
   1.155 -      : minimum(0), head(-1), iimap(_iimap), comp(_comp), num_items() {}
   1.156 +    /// Constructor.
   1.157 +    /// \param map A map that assigns \c int values to the items.
   1.158 +    /// It is used internally to handle the cross references.
   1.159 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   1.160 +    /// \param comp The function object used for comparing the priorities.
   1.161 +    BinomHeap(ItemIntMap &map, const Compare &comp)
   1.162 +      : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
   1.163  
   1.164      /// \brief The number of items stored in the heap.
   1.165      ///
   1.166 -    /// Returns the number of items stored in the heap.
   1.167 -    int size() const { return num_items; }
   1.168 +    /// This function returns the number of items stored in the heap.
   1.169 +    int size() const { return _num_items; }
   1.170  
   1.171 -    /// \brief Checks if the heap stores no items.
   1.172 +    /// \brief Check if the heap is empty.
   1.173      ///
   1.174 -    ///   Returns \c true if and only if the heap stores no items.
   1.175 -    bool empty() const { return num_items==0; }
   1.176 +    /// This function returns \c true if the heap is empty.
   1.177 +    bool empty() const { return _num_items==0; }
   1.178  
   1.179 -    /// \brief Make empty this heap.
   1.180 +    /// \brief Make the heap empty.
   1.181      ///
   1.182 -    /// Make empty this heap. It does not change the cross reference
   1.183 -    /// map.  If you want to reuse a heap what is not surely empty you
   1.184 -    /// should first clear the heap and after that you should set the
   1.185 -    /// cross reference map for each item to \c PRE_HEAP.
   1.186 +    /// This functon makes the heap empty.
   1.187 +    /// It does not change the cross reference map. If you want to reuse
   1.188 +    /// a heap that is not surely empty, you should first clear it and
   1.189 +    /// then you should set the cross reference map to \c PRE_HEAP
   1.190 +    /// for each item.
   1.191      void clear() {
   1.192 -      container.clear(); minimum=0; num_items=0; head=-1;
   1.193 +      _data.clear(); _min=0; _num_items=0; _head=-1;
   1.194      }
   1.195  
   1.196 -    /// \brief \c item gets to the heap with priority \c value independently
   1.197 -    /// if \c item was already there.
   1.198 +    /// \brief Set the priority of an item or insert it, if it is
   1.199 +    /// not stored in the heap.
   1.200      ///
   1.201 -    /// This method calls \ref push(\c item, \c value) if \c item is not
   1.202 -    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
   1.203 -    /// \ref increase(\c item, \c value) otherwise.
   1.204 +    /// This method sets the priority of the given item if it is
   1.205 +    /// already stored in the heap. Otherwise it inserts the given
   1.206 +    /// item into the heap with the given priority.
   1.207 +    /// \param item The item.
   1.208 +    /// \param value The priority.
   1.209      void set (const Item& item, const Prio& value) {
   1.210 -      int i=iimap[item];
   1.211 -      if ( i >= 0 && container[i].in ) {
   1.212 -        if ( comp(value, container[i].prio) ) decrease(item, value);
   1.213 -        if ( comp(container[i].prio, value) ) increase(item, value);
   1.214 +      int i=_iim[item];
   1.215 +      if ( i >= 0 && _data[i].in ) {
   1.216 +        if ( _comp(value, _data[i].prio) ) decrease(item, value);
   1.217 +        if ( _comp(_data[i].prio, value) ) increase(item, value);
   1.218        } else push(item, value);
   1.219      }
   1.220  
   1.221 -    /// \brief Adds \c item to the heap with priority \c value.
   1.222 +    /// \brief Insert an item into the heap with the given priority.
   1.223      ///
   1.224 -    /// Adds \c item to the heap with priority \c value.
   1.225 -    /// \pre \c item must not be stored in the heap.
   1.226 +    /// This function inserts the given item into the heap with the
   1.227 +    /// given priority.
   1.228 +    /// \param item The item to insert.
   1.229 +    /// \param value The priority of the item.
   1.230 +    /// \pre \e item must not be stored in the heap.
   1.231      void push (const Item& item, const Prio& value) {
   1.232 -      int i=iimap[item];
   1.233 +      int i=_iim[item];
   1.234        if ( i<0 ) {
   1.235 -        int s=container.size();
   1.236 -        iimap.set( item,s );
   1.237 +        int s=_data.size();
   1.238 +        _iim.set( item,s );
   1.239          store st;
   1.240          st.name=item;
   1.241 -        container.push_back(st);
   1.242 +        _data.push_back(st);
   1.243          i=s;
   1.244        }
   1.245        else {
   1.246 -        container[i].parent=container[i].right_neighbor=container[i].child=-1;
   1.247 -        container[i].degree=0;
   1.248 -        container[i].in=true;
   1.249 +        _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
   1.250 +        _data[i].degree=0;
   1.251 +        _data[i].in=true;
   1.252        }
   1.253 -      container[i].prio=value;
   1.254 +      _data[i].prio=value;
   1.255  
   1.256 -      if( 0==num_items ) { head=i; minimum=i; }
   1.257 +      if( 0==_num_items ) { _head=i; _min=i; }
   1.258        else { merge(i); }
   1.259  
   1.260 -      minimum = find_min();
   1.261 +      _min = findMin();
   1.262  
   1.263 -      ++num_items;
   1.264 +      ++_num_items;
   1.265      }
   1.266  
   1.267 -    /// \brief Returns the item with minimum priority relative to \c Compare.
   1.268 +    /// \brief Return the item having minimum priority.
   1.269      ///
   1.270 -    /// This method returns the item with minimum priority relative to \c
   1.271 -    /// Compare.
   1.272 -    /// \pre The heap must be nonempty.
   1.273 -    Item top() const { return container[minimum].name; }
   1.274 +    /// This function returns the item having minimum priority.
   1.275 +    /// \pre The heap must be non-empty.
   1.276 +    Item top() const { return _data[_min].name; }
   1.277  
   1.278 -    /// \brief Returns the minimum priority relative to \c Compare.
   1.279 +    /// \brief The minimum priority.
   1.280      ///
   1.281 -    /// It returns the minimum priority relative to \c Compare.
   1.282 -    /// \pre The heap must be nonempty.
   1.283 -    const Prio& prio() const { return container[minimum].prio; }
   1.284 +    /// This function returns the minimum priority.
   1.285 +    /// \pre The heap must be non-empty.
   1.286 +    Prio prio() const { return _data[_min].prio; }
   1.287  
   1.288 -    /// \brief Returns the priority of \c item.
   1.289 +    /// \brief The priority of the given item.
   1.290      ///
   1.291 -    /// It returns the priority of \c item.
   1.292 -    /// \pre \c item must be in the heap.
   1.293 +    /// This function returns the priority of the given item.
   1.294 +    /// \param item The item.
   1.295 +    /// \pre \e item must be in the heap.
   1.296      const Prio& operator[](const Item& item) const {
   1.297 -      return container[iimap[item]].prio;
   1.298 +      return _data[_iim[item]].prio;
   1.299      }
   1.300  
   1.301 -    /// \brief Deletes the item with minimum priority relative to \c Compare.
   1.302 +    /// \brief Remove the item having minimum priority.
   1.303      ///
   1.304 -    /// This method deletes the item with minimum priority relative to \c
   1.305 -    /// Compare from the heap.
   1.306 +    /// This function removes the item having minimum priority.
   1.307      /// \pre The heap must be non-empty.
   1.308      void pop() {
   1.309 -      container[minimum].in=false;
   1.310 +      _data[_min].in=false;
   1.311  
   1.312        int head_child=-1;
   1.313 -      if ( container[minimum].child!=-1 ) {
   1.314 -        int child=container[minimum].child;
   1.315 +      if ( _data[_min].child!=-1 ) {
   1.316 +        int child=_data[_min].child;
   1.317          int neighb;
   1.318          int prev=-1;
   1.319          while( child!=-1 ) {
   1.320 -          neighb=container[child].right_neighbor;
   1.321 -          container[child].parent=-1;
   1.322 -          container[child].right_neighbor=prev;
   1.323 +          neighb=_data[child].right_neighbor;
   1.324 +          _data[child].parent=-1;
   1.325 +          _data[child].right_neighbor=prev;
   1.326            head_child=child;
   1.327            prev=child;
   1.328            child=neighb;
   1.329 @@ -214,142 +220,144 @@
   1.330        }
   1.331  
   1.332        // The first case is that there are only one root.
   1.333 -      if ( -1==container[head].right_neighbor ) {
   1.334 -        head=head_child;
   1.335 +      if ( -1==_data[_head].right_neighbor ) {
   1.336 +        _head=head_child;
   1.337        }
   1.338        // The case where there are more roots.
   1.339        else {
   1.340 -        if( head!=minimum )  { unlace(minimum); }
   1.341 -        else { head=container[head].right_neighbor; }
   1.342 +        if( _head!=_min )  { unlace(_min); }
   1.343 +        else { _head=_data[_head].right_neighbor; }
   1.344  
   1.345          merge(head_child);
   1.346        }
   1.347 -      minimum=find_min();
   1.348 -      --num_items;
   1.349 +      _min=findMin();
   1.350 +      --_num_items;
   1.351      }
   1.352  
   1.353 -    /// \brief Deletes \c item from the heap.
   1.354 +    /// \brief Remove the given item from the heap.
   1.355      ///
   1.356 -    /// This method deletes \c item from the heap, if \c item was already
   1.357 -    /// stored in the heap. It is quite inefficient in Binomial heaps.
   1.358 +    /// This function removes the given item from the heap if it is
   1.359 +    /// already stored.
   1.360 +    /// \param item The item to delete.
   1.361 +    /// \pre \e item must be in the heap.
   1.362      void erase (const Item& item) {
   1.363 -      int i=iimap[item];
   1.364 -      if ( i >= 0 && container[i].in ) {
   1.365 -        decrease( item, container[minimum].prio-1 );
   1.366 +      int i=_iim[item];
   1.367 +      if ( i >= 0 && _data[i].in ) {
   1.368 +        decrease( item, _data[_min].prio-1 );
   1.369          pop();
   1.370        }
   1.371      }
   1.372  
   1.373 -    /// \brief Decreases the priority of \c item to \c value.
   1.374 +    /// \brief Decrease the priority of an item to the given value.
   1.375      ///
   1.376 -    /// This method decreases the priority of \c item to \c value.
   1.377 -    /// \pre \c item must be stored in the heap with priority at least \c
   1.378 -    ///   value relative to \c Compare.
   1.379 +    /// This function decreases the priority of an item to the given value.
   1.380 +    /// \param item The item.
   1.381 +    /// \param value The priority.
   1.382 +    /// \pre \e item must be stored in the heap with priority at least \e value.
   1.383      void decrease (Item item, const Prio& value) {
   1.384 -      int i=iimap[item];
   1.385 +      int i=_iim[item];
   1.386  
   1.387 -      if( comp( value,container[i].prio ) ) {
   1.388 -        container[i].prio=value;
   1.389 +      if( _comp( value,_data[i].prio ) ) {
   1.390 +        _data[i].prio=value;
   1.391  
   1.392 -        int p_loc=container[i].parent, loc=i;
   1.393 +        int p_loc=_data[i].parent, loc=i;
   1.394          int parent, child, neighb;
   1.395  
   1.396 -        while( -1!=p_loc && comp(container[loc].prio,container[p_loc].prio) ) {
   1.397 +        while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) {
   1.398  
   1.399            // parent set for other loc_child
   1.400 -          child=container[loc].child;
   1.401 +          child=_data[loc].child;
   1.402            while( -1!=child ) {
   1.403 -            container[child].parent=p_loc;
   1.404 -            child=container[child].right_neighbor;
   1.405 +            _data[child].parent=p_loc;
   1.406 +            child=_data[child].right_neighbor;
   1.407            }
   1.408  
   1.409            // parent set for other p_loc_child
   1.410 -          child=container[p_loc].child;
   1.411 +          child=_data[p_loc].child;
   1.412            while( -1!=child ) {
   1.413 -            container[child].parent=loc;
   1.414 -            child=container[child].right_neighbor;
   1.415 +            _data[child].parent=loc;
   1.416 +            child=_data[child].right_neighbor;
   1.417            }
   1.418  
   1.419 -          child=container[p_loc].child;
   1.420 -          container[p_loc].child=container[loc].child;
   1.421 +          child=_data[p_loc].child;
   1.422 +          _data[p_loc].child=_data[loc].child;
   1.423            if( child==loc )
   1.424              child=p_loc;
   1.425 -          container[loc].child=child;
   1.426 +          _data[loc].child=child;
   1.427  
   1.428            // left_neighb set for p_loc
   1.429 -          if( container[loc].child!=p_loc ) {
   1.430 -            while( container[child].right_neighbor!=loc )
   1.431 -              child=container[child].right_neighbor;
   1.432 -            container[child].right_neighbor=p_loc;
   1.433 +          if( _data[loc].child!=p_loc ) {
   1.434 +            while( _data[child].right_neighbor!=loc )
   1.435 +              child=_data[child].right_neighbor;
   1.436 +            _data[child].right_neighbor=p_loc;
   1.437            }
   1.438  
   1.439            // left_neighb set for loc
   1.440 -          parent=container[p_loc].parent;
   1.441 -          if( -1!=parent ) child=container[parent].child;
   1.442 -          else child=head;
   1.443 +          parent=_data[p_loc].parent;
   1.444 +          if( -1!=parent ) child=_data[parent].child;
   1.445 +          else child=_head;
   1.446  
   1.447            if( child!=p_loc ) {
   1.448 -            while( container[child].right_neighbor!=p_loc )
   1.449 -              child=container[child].right_neighbor;
   1.450 -            container[child].right_neighbor=loc;
   1.451 +            while( _data[child].right_neighbor!=p_loc )
   1.452 +              child=_data[child].right_neighbor;
   1.453 +            _data[child].right_neighbor=loc;
   1.454            }
   1.455  
   1.456 -          neighb=container[p_loc].right_neighbor;
   1.457 -          container[p_loc].right_neighbor=container[loc].right_neighbor;
   1.458 -          container[loc].right_neighbor=neighb;
   1.459 +          neighb=_data[p_loc].right_neighbor;
   1.460 +          _data[p_loc].right_neighbor=_data[loc].right_neighbor;
   1.461 +          _data[loc].right_neighbor=neighb;
   1.462  
   1.463 -          container[p_loc].parent=loc;
   1.464 -          container[loc].parent=parent;
   1.465 +          _data[p_loc].parent=loc;
   1.466 +          _data[loc].parent=parent;
   1.467  
   1.468 -          if( -1!=parent && container[parent].child==p_loc )
   1.469 -            container[parent].child=loc;
   1.470 +          if( -1!=parent && _data[parent].child==p_loc )
   1.471 +            _data[parent].child=loc;
   1.472  
   1.473            /*if new parent will be the first root*/
   1.474 -          if( head==p_loc )
   1.475 -            head=loc;
   1.476 +          if( _head==p_loc )
   1.477 +            _head=loc;
   1.478  
   1.479 -          p_loc=container[loc].parent;
   1.480 +          p_loc=_data[loc].parent;
   1.481          }
   1.482        }
   1.483 -      if( comp(value,container[minimum].prio) ) {
   1.484 -        minimum=i;
   1.485 +      if( _comp(value,_data[_min].prio) ) {
   1.486 +        _min=i;
   1.487        }
   1.488      }
   1.489  
   1.490 -    /// \brief Increases the priority of \c item to \c value.
   1.491 +    /// \brief Increase the priority of an item to the given value.
   1.492      ///
   1.493 -    /// This method sets the priority of \c item to \c value. Though
   1.494 -    /// there is no precondition on the priority of \c item, this
   1.495 -    /// method should be used only if it is indeed necessary to increase
   1.496 -    /// (relative to \c Compare) the priority of \c item, because this
   1.497 -    /// method is inefficient.
   1.498 +    /// This function increases the priority of an item to the given value.
   1.499 +    /// \param item The item.
   1.500 +    /// \param value The priority.
   1.501 +    /// \pre \e item must be stored in the heap with priority at most \e value.
   1.502      void increase (Item item, const Prio& value) {
   1.503        erase(item);
   1.504        push(item, value);
   1.505      }
   1.506  
   1.507 -
   1.508 -    /// \brief Returns if \c item is in, has already been in, or has never
   1.509 -    /// been in the heap.
   1.510 +    /// \brief Return the state of an item.
   1.511      ///
   1.512 -    /// This method returns PRE_HEAP if \c item has never been in the
   1.513 -    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   1.514 -    /// otherwise. In the latter case it is possible that \c item will
   1.515 -    /// get back to the heap again.
   1.516 +    /// This method returns \c PRE_HEAP if the given item has never
   1.517 +    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   1.518 +    /// and \c POST_HEAP otherwise.
   1.519 +    /// In the latter case it is possible that the item will get back
   1.520 +    /// to the heap again.
   1.521 +    /// \param item The item.
   1.522      State state(const Item &item) const {
   1.523 -      int i=iimap[item];
   1.524 +      int i=_iim[item];
   1.525        if( i>=0 ) {
   1.526 -        if ( container[i].in ) i=0;
   1.527 +        if ( _data[i].in ) i=0;
   1.528          else i=-2;
   1.529        }
   1.530        return State(i);
   1.531      }
   1.532  
   1.533 -    /// \brief Sets the state of the \c item in the heap.
   1.534 +    /// \brief Set the state of an item in the heap.
   1.535      ///
   1.536 -    /// Sets the state of the \c item in the heap. It can be used to
   1.537 -    /// manually clear the heap when it is important to achive the
   1.538 -    /// better time complexity.
   1.539 +    /// This function sets the state of the given item in the heap.
   1.540 +    /// It can be used to manually clear the heap when it is important
   1.541 +    /// to achive better time complexity.
   1.542      /// \param i The item.
   1.543      /// \param st The state. It should not be \c IN_HEAP.
   1.544      void state(const Item& i, State st) {
   1.545 @@ -359,7 +367,7 @@
   1.546          if (state(i) == IN_HEAP) {
   1.547            erase(i);
   1.548          }
   1.549 -        iimap[i] = st;
   1.550 +        _iim[i] = st;
   1.551          break;
   1.552        case IN_HEAP:
   1.553          break;
   1.554 @@ -367,20 +375,20 @@
   1.555      }
   1.556  
   1.557    private:
   1.558 -    int find_min() {
   1.559 +    int findMin() {
   1.560        int min_loc=-1, min_val;
   1.561 -      int x=head;
   1.562 +      int x=_head;
   1.563        if( x!=-1 ) {
   1.564 -        min_val=container[x].prio;
   1.565 +        min_val=_data[x].prio;
   1.566          min_loc=x;
   1.567 -        x=container[x].right_neighbor;
   1.568 +        x=_data[x].right_neighbor;
   1.569  
   1.570          while( x!=-1 ) {
   1.571 -          if( comp( container[x].prio,min_val ) ) {
   1.572 -            min_val=container[x].prio;
   1.573 +          if( _comp( _data[x].prio,min_val ) ) {
   1.574 +            min_val=_data[x].prio;
   1.575              min_loc=x;
   1.576            }
   1.577 -          x=container[x].right_neighbor;
   1.578 +          x=_data[x].right_neighbor;
   1.579          }
   1.580        }
   1.581        return min_loc;
   1.582 @@ -389,29 +397,29 @@
   1.583      void merge(int a) {
   1.584        interleave(a);
   1.585  
   1.586 -      int x=head;
   1.587 +      int x=_head;
   1.588        if( -1!=x ) {
   1.589 -        int x_prev=-1, x_next=container[x].right_neighbor;
   1.590 +        int x_prev=-1, x_next=_data[x].right_neighbor;
   1.591          while( -1!=x_next ) {
   1.592 -          if( container[x].degree!=container[x_next].degree || ( -1!=container[x_next].right_neighbor && container[container[x_next].right_neighbor].degree==container[x].degree ) ) {
   1.593 +          if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
   1.594              x_prev=x;
   1.595              x=x_next;
   1.596            }
   1.597            else {
   1.598 -            if( comp(container[x].prio,container[x_next].prio) ) {
   1.599 -              container[x].right_neighbor=container[x_next].right_neighbor;
   1.600 +            if( _comp(_data[x].prio,_data[x_next].prio) ) {
   1.601 +              _data[x].right_neighbor=_data[x_next].right_neighbor;
   1.602                fuse(x_next,x);
   1.603              }
   1.604              else {
   1.605 -              if( -1==x_prev ) { head=x_next; }
   1.606 +              if( -1==x_prev ) { _head=x_next; }
   1.607                else {
   1.608 -                container[x_prev].right_neighbor=x_next;
   1.609 +                _data[x_prev].right_neighbor=x_next;
   1.610                }
   1.611                fuse(x,x_next);
   1.612                x=x_next;
   1.613              }
   1.614            }
   1.615 -          x_next=container[x].right_neighbor;
   1.616 +          x_next=_data[x].right_neighbor;
   1.617          }
   1.618        }
   1.619      }
   1.620 @@ -419,68 +427,68 @@
   1.621      void interleave(int a) {
   1.622        int other=-1, head_other=-1;
   1.623  
   1.624 -      while( -1!=a || -1!=head ) {
   1.625 +      while( -1!=a || -1!=_head ) {
   1.626          if( -1==a ) {
   1.627            if( -1==head_other ) {
   1.628 -            head_other=head;
   1.629 +            head_other=_head;
   1.630            }
   1.631            else {
   1.632 -            container[other].right_neighbor=head;
   1.633 +            _data[other].right_neighbor=_head;
   1.634            }
   1.635 -          head=-1;
   1.636 +          _head=-1;
   1.637          }
   1.638 -        else if( -1==head ) {
   1.639 +        else if( -1==_head ) {
   1.640            if( -1==head_other ) {
   1.641              head_other=a;
   1.642            }
   1.643            else {
   1.644 -            container[other].right_neighbor=a;
   1.645 +            _data[other].right_neighbor=a;
   1.646            }
   1.647            a=-1;
   1.648          }
   1.649          else {
   1.650 -          if( container[a].degree<container[head].degree ) {
   1.651 +          if( _data[a].degree<_data[_head].degree ) {
   1.652              if( -1==head_other ) {
   1.653                head_other=a;
   1.654              }
   1.655              else {
   1.656 -              container[other].right_neighbor=a;
   1.657 +              _data[other].right_neighbor=a;
   1.658              }
   1.659              other=a;
   1.660 -            a=container[a].right_neighbor;
   1.661 +            a=_data[a].right_neighbor;
   1.662            }
   1.663            else {
   1.664              if( -1==head_other ) {
   1.665 -              head_other=head;
   1.666 +              head_other=_head;
   1.667              }
   1.668              else {
   1.669 -              container[other].right_neighbor=head;
   1.670 +              _data[other].right_neighbor=_head;
   1.671              }
   1.672 -            other=head;
   1.673 -            head=container[head].right_neighbor;
   1.674 +            other=_head;
   1.675 +            _head=_data[_head].right_neighbor;
   1.676            }
   1.677          }
   1.678        }
   1.679 -      head=head_other;
   1.680 +      _head=head_other;
   1.681      }
   1.682  
   1.683      // Lacing a under b
   1.684      void fuse(int a, int b) {
   1.685 -      container[a].parent=b;
   1.686 -      container[a].right_neighbor=container[b].child;
   1.687 -      container[b].child=a;
   1.688 +      _data[a].parent=b;
   1.689 +      _data[a].right_neighbor=_data[b].child;
   1.690 +      _data[b].child=a;
   1.691  
   1.692 -      ++container[b].degree;
   1.693 +      ++_data[b].degree;
   1.694      }
   1.695  
   1.696      // It is invoked only if a has siblings.
   1.697      void unlace(int a) {
   1.698 -      int neighb=container[a].right_neighbor;
   1.699 -      int other=head;
   1.700 +      int neighb=_data[a].right_neighbor;
   1.701 +      int other=_head;
   1.702  
   1.703 -      while( container[other].right_neighbor!=a )
   1.704 -        other=container[other].right_neighbor;
   1.705 -      container[other].right_neighbor=neighb;
   1.706 +      while( _data[other].right_neighbor!=a )
   1.707 +        other=_data[other].right_neighbor;
   1.708 +      _data[other].right_neighbor=neighb;
   1.709      }
   1.710  
   1.711    private:
     2.1 --- a/lemon/fourary_heap.h	Thu Jul 09 02:39:47 2009 +0200
     2.2 +++ b/lemon/fourary_heap.h	Thu Jul 09 04:07:08 2009 +0200
     2.3 @@ -1,8 +1,8 @@
     2.4 -/* -*- C++ -*-
     2.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2.6   *
     2.7 - * This file is a part of LEMON, a generic C++ optimization library
     2.8 + * This file is a part of LEMON, a generic C++ optimization library.
     2.9   *
    2.10 - * Copyright (C) 2003-2008
    2.11 + * Copyright (C) 2003-2009
    2.12   * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    2.13   * (Egervary Research Group on Combinatorial Optimization, EGRES).
    2.14   *
    2.15 @@ -19,159 +19,158 @@
    2.16  #ifndef LEMON_FOURARY_HEAP_H
    2.17  #define LEMON_FOURARY_HEAP_H
    2.18  
    2.19 -///\ingroup auxdat
    2.20 +///\ingroup heaps
    2.21  ///\file
    2.22 -///\brief 4ary Heap implementation.
    2.23 +///\brief Fourary heap implementation.
    2.24  
    2.25 -#include <iostream>
    2.26  #include <vector>
    2.27  #include <utility>
    2.28  #include <functional>
    2.29  
    2.30  namespace lemon {
    2.31  
    2.32 -  ///\ingroup auxdat
    2.33 +  /// \ingroup heaps
    2.34    ///
    2.35 -  ///\brief A 4ary Heap implementation.
    2.36 +  ///\brief Fourary heap data structure.
    2.37    ///
    2.38 -  ///This class implements the \e 4ary \e heap data structure. A \e heap
    2.39 -  ///is a data structure for storing items with specified values called \e
    2.40 -  ///priorities in such a way that finding the item with minimum priority is
    2.41 -  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    2.42 -  ///one can change the priority of an item, add or erase an item, etc.
    2.43 +  /// This class implements the \e fourary \e heap data structure.
    2.44 +  /// It fully conforms to the \ref concepts::Heap "heap concept".
    2.45    ///
    2.46 -  ///\param _Prio Type of the priority of the items.
    2.47 -  ///\param _ItemIntMap A read and writable Item int map, used internally
    2.48 -  ///to handle the cross references.
    2.49 -  ///\param _Compare A class for the ordering of the priorities. The
    2.50 -  ///default is \c std::less<_Prio>.
    2.51 +  /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap"
    2.52 +  /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap",
    2.53 +  /// but its nodes have at most four children, instead of two.
    2.54    ///
    2.55 -  ///\sa FibHeap
    2.56 -  ///\sa Dijkstra
    2.57 -  ///\author Dorian Batha
    2.58 +  /// \tparam PR Type of the priorities of the items.
    2.59 +  /// \tparam IM A read-writable item map with \c int values, used
    2.60 +  /// internally to handle the cross references.
    2.61 +  /// \tparam CMP A functor class for comparing the priorities.
    2.62 +  /// The default is \c std::less<PR>.
    2.63 +  ///
    2.64 +  ///\sa BinHeap
    2.65 +  ///\sa KaryHeap
    2.66 +#ifdef DOXYGEN
    2.67 +  template <typename PR, typename IM, typename CMP>
    2.68 +#else
    2.69 +  template <typename PR, typename IM, typename CMP = std::less<PR> >
    2.70 +#endif
    2.71 +  class FouraryHeap {
    2.72 +  public:
    2.73 +    /// Type of the item-int map.
    2.74 +    typedef IM ItemIntMap;
    2.75 +    /// Type of the priorities.
    2.76 +    typedef PR Prio;
    2.77 +    /// Type of the items stored in the heap.
    2.78 +    typedef typename ItemIntMap::Key Item;
    2.79 +    /// Type of the item-priority pairs.
    2.80 +    typedef std::pair<Item,Prio> Pair;
    2.81 +    /// Functor type for comparing the priorities.
    2.82 +    typedef CMP Compare;
    2.83  
    2.84 -  template <typename _Prio, typename _ItemIntMap,
    2.85 -            typename _Compare = std::less<_Prio> >
    2.86 -
    2.87 -  class FouraryHeap {
    2.88 -
    2.89 -  public:
    2.90 -    ///\e
    2.91 -    typedef _ItemIntMap ItemIntMap;
    2.92 -    ///\e
    2.93 -    typedef _Prio Prio;
    2.94 -    ///\e
    2.95 -    typedef typename ItemIntMap::Key Item;
    2.96 -    ///\e
    2.97 -    typedef std::pair<Item,Prio> Pair;
    2.98 -    ///\e
    2.99 -    typedef _Compare Compare;
   2.100 -
   2.101 -    /// \brief Type to represent the items states.
   2.102 +    /// \brief Type to represent the states of the items.
   2.103      ///
   2.104 -    /// Each Item element have a state associated to it. It may be "in heap",
   2.105 -    /// "pre heap" or "post heap". The latter two are indifferent from the
   2.106 +    /// Each item has a state associated to it. It can be "in heap",
   2.107 +    /// "pre-heap" or "post-heap". The latter two are indifferent from the
   2.108      /// heap's point of view, but may be useful to the user.
   2.109      ///
   2.110 -    /// The ItemIntMap \e should be initialized in such way that it maps
   2.111 -    /// PRE_HEAP (-1) to any element to be put in the heap...
   2.112 +    /// The item-int map must be initialized in such way that it assigns
   2.113 +    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
   2.114      enum State {
   2.115 -      IN_HEAP = 0,
   2.116 -      PRE_HEAP = -1,
   2.117 -      POST_HEAP = -2
   2.118 +      IN_HEAP = 0,    ///< = 0.
   2.119 +      PRE_HEAP = -1,  ///< = -1.
   2.120 +      POST_HEAP = -2  ///< = -2.
   2.121      };
   2.122  
   2.123    private:
   2.124 -    std::vector<Pair> data;
   2.125 -    Compare comp;
   2.126 -    ItemIntMap &iim;
   2.127 +    std::vector<Pair> _data;
   2.128 +    Compare _comp;
   2.129 +    ItemIntMap &_iim;
   2.130  
   2.131    public:
   2.132 -    /// \brief The constructor.
   2.133 +    /// \brief Constructor.
   2.134      ///
   2.135 -    /// The constructor.
   2.136 -    /// \param _iim should be given to the constructor, since it is used
   2.137 -    /// internally to handle the cross references. The value of the map
   2.138 -    /// should be PRE_HEAP (-1) for each element.
   2.139 -    explicit FouraryHeap(ItemIntMap &_iim) : iim(_iim) {}
   2.140 +    /// Constructor.
   2.141 +    /// \param map A map that assigns \c int values to the items.
   2.142 +    /// It is used internally to handle the cross references.
   2.143 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   2.144 +    explicit FouraryHeap(ItemIntMap &map) : _iim(map) {}
   2.145  
   2.146 -    /// \brief The constructor.
   2.147 +    /// \brief Constructor.
   2.148      ///
   2.149 -    /// The constructor.
   2.150 -    /// \param _iim should be given to the constructor, since it is used
   2.151 -    /// internally to handle the cross references. The value of the map
   2.152 -    /// should be PRE_HEAP (-1) for each element.
   2.153 +    /// Constructor.
   2.154 +    /// \param map A map that assigns \c int values to the items.
   2.155 +    /// It is used internally to handle the cross references.
   2.156 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   2.157 +    /// \param comp The function object used for comparing the priorities.
   2.158 +    FouraryHeap(ItemIntMap &map, const Compare &comp)
   2.159 +      : _iim(map), _comp(comp) {}
   2.160 +
   2.161 +    /// \brief The number of items stored in the heap.
   2.162      ///
   2.163 -    /// \param _comp The comparator function object.
   2.164 -    FouraryHeap(ItemIntMap &_iim, const Compare &_comp)
   2.165 -      : iim(_iim), comp(_comp) {}
   2.166 +    /// This function returns the number of items stored in the heap.
   2.167 +    int size() const { return _data.size(); }
   2.168  
   2.169 -    /// The number of items stored in the heap.
   2.170 +    /// \brief Check if the heap is empty.
   2.171      ///
   2.172 -    /// \brief Returns the number of items stored in the heap.
   2.173 -    int size() const { return data.size(); }
   2.174 +    /// This function returns \c true if the heap is empty.
   2.175 +    bool empty() const { return _data.empty(); }
   2.176  
   2.177 -    /// \brief Checks if the heap stores no items.
   2.178 +    /// \brief Make the heap empty.
   2.179      ///
   2.180 -    /// Returns \c true if and only if the heap stores no items.
   2.181 -    bool empty() const { return data.empty(); }
   2.182 -
   2.183 -    /// \brief Make empty this heap.
   2.184 -    ///
   2.185 -    /// Make empty this heap. It does not change the cross reference map.
   2.186 -    /// If you want to reuse what is not surely empty you should first clear
   2.187 -    /// the heap and after that you should set the cross reference map for
   2.188 -    /// each item to \c PRE_HEAP.
   2.189 -    void clear() { data.clear(); }
   2.190 +    /// This functon makes the heap empty.
   2.191 +    /// It does not change the cross reference map. If you want to reuse
   2.192 +    /// a heap that is not surely empty, you should first clear it and
   2.193 +    /// then you should set the cross reference map to \c PRE_HEAP
   2.194 +    /// for each item.
   2.195 +    void clear() { _data.clear(); }
   2.196  
   2.197    private:
   2.198      static int parent(int i) { return (i-1)/4; }
   2.199      static int firstChild(int i) { return 4*i+1; }
   2.200  
   2.201      bool less(const Pair &p1, const Pair &p2) const {
   2.202 -      return comp(p1.second, p2.second);
   2.203 +      return _comp(p1.second, p2.second);
   2.204      }
   2.205  
   2.206 -    int find_min(const int child, const int length) {
   2.207 +    int findMin(const int child, const int length) {
   2.208        int min=child;
   2.209        if( child+3<length ) {
   2.210 -        if( less(data[child+3], data[min]) )
   2.211 +        if( less(_data[child+3], _data[min]) )
   2.212            min=child+3;
   2.213 -        if( less(data[child+2], data[min]) )
   2.214 +        if( less(_data[child+2], _data[min]) )
   2.215            min=child+2;
   2.216 -        if( less(data[child+1], data[min]) )
   2.217 +        if( less(_data[child+1], _data[min]) )
   2.218            min=child+1;
   2.219        }
   2.220        else if( child+2<length ) {
   2.221 -        if( less(data[child+2], data[min]) )
   2.222 +        if( less(_data[child+2], _data[min]) )
   2.223            min=child+2;
   2.224 -        if( less(data[child+1], data[min]) )
   2.225 +        if( less(_data[child+1], _data[min]) )
   2.226            min=child+1;
   2.227        }
   2.228        else if( child+1<length ) {
   2.229 -        if( less(data[child+1], data[min]) )
   2.230 +        if( less(_data[child+1], _data[min]) )
   2.231            min=child+1;
   2.232        }
   2.233        return min;
   2.234      }
   2.235  
   2.236 -    void bubble_up(int hole, Pair p) {
   2.237 +    void bubbleUp(int hole, Pair p) {
   2.238        int par = parent(hole);
   2.239 -      while( hole>0 && less(p,data[par]) ) {
   2.240 -        move(data[par],hole);
   2.241 +      while( hole>0 && less(p,_data[par]) ) {
   2.242 +        move(_data[par],hole);
   2.243          hole = par;
   2.244          par = parent(hole);
   2.245        }
   2.246        move(p, hole);
   2.247      }
   2.248  
   2.249 -    void bubble_down(int hole, Pair p, int length) {
   2.250 +    void bubbleDown(int hole, Pair p, int length) {
   2.251        int child = firstChild(hole);
   2.252        while( child<length && length>1 ) {
   2.253 -        child = find_min(child,length);
   2.254 -        if( !less(data[child], p) )
   2.255 +        child = findMin(child,length);
   2.256 +        if( !less(_data[child], p) )
   2.257            goto ok;
   2.258 -        move(data[child], hole);
   2.259 +        move(_data[child], hole);
   2.260          hole = child;
   2.261          child = firstChild(hole);
   2.262        }
   2.263 @@ -180,142 +179,143 @@
   2.264      }
   2.265  
   2.266      void move(const Pair &p, int i) {
   2.267 -      data[i] = p;
   2.268 -      iim.set(p.first, i);
   2.269 +      _data[i] = p;
   2.270 +      _iim.set(p.first, i);
   2.271      }
   2.272  
   2.273    public:
   2.274 -
   2.275      /// \brief Insert a pair of item and priority into the heap.
   2.276      ///
   2.277 -    /// Adds \c p.first to the heap with priority \c p.second.
   2.278 +    /// This function inserts \c p.first to the heap with priority
   2.279 +    /// \c p.second.
   2.280      /// \param p The pair to insert.
   2.281 +    /// \pre \c p.first must not be stored in the heap.
   2.282      void push(const Pair &p) {
   2.283 -      int n = data.size();
   2.284 -      data.resize(n+1);
   2.285 -      bubble_up(n, p);
   2.286 +      int n = _data.size();
   2.287 +      _data.resize(n+1);
   2.288 +      bubbleUp(n, p);
   2.289      }
   2.290  
   2.291 -    /// \brief Insert an item into the heap with the given heap.
   2.292 +    /// \brief Insert an item into the heap with the given priority.
   2.293      ///
   2.294 -    /// Adds \c i to the heap with priority \c p.
   2.295 +    /// This function inserts the given item into the heap with the
   2.296 +    /// given priority.
   2.297      /// \param i The item to insert.
   2.298      /// \param p The priority of the item.
   2.299 +    /// \pre \e i must not be stored in the heap.
   2.300      void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
   2.301  
   2.302 -    /// \brief Returns the item with minimum priority relative to \c Compare.
   2.303 +    /// \brief Return the item having minimum priority.
   2.304      ///
   2.305 -    /// This method returns the item with minimum priority relative to \c
   2.306 -    /// Compare.
   2.307 -    /// \pre The heap must be nonempty.
   2.308 -    Item top() const { return data[0].first; }
   2.309 +    /// This function returns the item having minimum priority.
   2.310 +    /// \pre The heap must be non-empty.
   2.311 +    Item top() const { return _data[0].first; }
   2.312  
   2.313 -    /// \brief Returns the minimum priority relative to \c Compare.
   2.314 +    /// \brief The minimum priority.
   2.315      ///
   2.316 -    /// It returns the minimum priority relative to \c Compare.
   2.317 -    /// \pre The heap must be nonempty.
   2.318 -    Prio prio() const { return data[0].second; }
   2.319 +    /// This function returns the minimum priority.
   2.320 +    /// \pre The heap must be non-empty.
   2.321 +    Prio prio() const { return _data[0].second; }
   2.322  
   2.323 -    /// \brief Deletes the item with minimum priority relative to \c Compare.
   2.324 +    /// \brief Remove the item having minimum priority.
   2.325      ///
   2.326 -    /// This method deletes the item with minimum priority relative to \c
   2.327 -    /// Compare from the heap.
   2.328 +    /// This function removes the item having minimum priority.
   2.329      /// \pre The heap must be non-empty.
   2.330      void pop() {
   2.331 -      int n = data.size()-1;
   2.332 -      iim.set(data[0].first, POST_HEAP);
   2.333 -      if (n>0) bubble_down(0, data[n], n);
   2.334 -      data.pop_back();
   2.335 +      int n = _data.size()-1;
   2.336 +      _iim.set(_data[0].first, POST_HEAP);
   2.337 +      if (n>0) bubbleDown(0, _data[n], n);
   2.338 +      _data.pop_back();
   2.339      }
   2.340  
   2.341 -    /// \brief Deletes \c i from the heap.
   2.342 +    /// \brief Remove the given item from the heap.
   2.343      ///
   2.344 -    /// This method deletes item \c i from the heap.
   2.345 -    /// \param i The item to erase.
   2.346 -    /// \pre The item should be in the heap.
   2.347 +    /// This function removes the given item from the heap if it is
   2.348 +    /// already stored.
   2.349 +    /// \param i The item to delete.
   2.350 +    /// \pre \e i must be in the heap.
   2.351      void erase(const Item &i) {
   2.352 -      int h = iim[i];
   2.353 -      int n = data.size()-1;
   2.354 -      iim.set(data[h].first, POST_HEAP);
   2.355 +      int h = _iim[i];
   2.356 +      int n = _data.size()-1;
   2.357 +      _iim.set(_data[h].first, POST_HEAP);
   2.358        if( h<n ) {
   2.359 -        if( less(data[parent(h)], data[n]) )
   2.360 -          bubble_down(h, data[n], n);
   2.361 +        if( less(_data[parent(h)], _data[n]) )
   2.362 +          bubbleDown(h, _data[n], n);
   2.363          else
   2.364 -          bubble_up(h, data[n]);
   2.365 +          bubbleUp(h, _data[n]);
   2.366        }
   2.367 -      data.pop_back();
   2.368 +      _data.pop_back();
   2.369      }
   2.370  
   2.371 -    /// \brief Returns the priority of \c i.
   2.372 +    /// \brief The priority of the given item.
   2.373      ///
   2.374 -    /// This function returns the priority of item \c i.
   2.375 -    /// \pre \c i must be in the heap.
   2.376 +    /// This function returns the priority of the given item.
   2.377      /// \param i The item.
   2.378 +    /// \pre \e i must be in the heap.
   2.379      Prio operator[](const Item &i) const {
   2.380 -      int idx = iim[i];
   2.381 -      return data[idx].second;
   2.382 +      int idx = _iim[i];
   2.383 +      return _data[idx].second;
   2.384      }
   2.385  
   2.386 -    /// \brief \c i gets to the heap with priority \c p independently
   2.387 -    /// if \c i was already there.
   2.388 +    /// \brief Set the priority of an item or insert it, if it is
   2.389 +    /// not stored in the heap.
   2.390      ///
   2.391 -    /// This method calls \ref push(\c i, \c p) if \c i is not stored
   2.392 -    /// in the heap and sets the priority of \c i to \c p otherwise.
   2.393 +    /// This method sets the priority of the given item if it is
   2.394 +    /// already stored in the heap. Otherwise it inserts the given
   2.395 +    /// item into the heap with the given priority.
   2.396      /// \param i The item.
   2.397      /// \param p The priority.
   2.398      void set(const Item &i, const Prio &p) {
   2.399 -      int idx = iim[i];
   2.400 +      int idx = _iim[i];
   2.401        if( idx < 0 )
   2.402          push(i,p);
   2.403 -      else if( comp(p, data[idx].second) )
   2.404 -        bubble_up(idx, Pair(i,p));
   2.405 +      else if( _comp(p, _data[idx].second) )
   2.406 +        bubbleUp(idx, Pair(i,p));
   2.407        else
   2.408 -        bubble_down(idx, Pair(i,p), data.size());
   2.409 +        bubbleDown(idx, Pair(i,p), _data.size());
   2.410      }
   2.411  
   2.412 -    /// \brief Decreases the priority of \c i to \c p.
   2.413 +    /// \brief Decrease the priority of an item to the given value.
   2.414      ///
   2.415 -    /// This method decreases the priority of item \c i to \c p.
   2.416 -    /// \pre \c i must be stored in the heap with priority at least \c
   2.417 -    /// p relative to \c Compare.
   2.418 +    /// This function decreases the priority of an item to the given value.
   2.419      /// \param i The item.
   2.420      /// \param p The priority.
   2.421 +    /// \pre \e i must be stored in the heap with priority at least \e p.
   2.422      void decrease(const Item &i, const Prio &p) {
   2.423 -      int idx = iim[i];
   2.424 -      bubble_up(idx, Pair(i,p));
   2.425 +      int idx = _iim[i];
   2.426 +      bubbleUp(idx, Pair(i,p));
   2.427      }
   2.428  
   2.429 -    /// \brief Increases the priority of \c i to \c p.
   2.430 +    /// \brief Increase the priority of an item to the given value.
   2.431      ///
   2.432 -    /// This method sets the priority of item \c i to \c p.
   2.433 -    /// \pre \c i must be stored in the heap with priority at most \c
   2.434 -    /// p relative to \c Compare.
   2.435 +    /// This function increases the priority of an item to the given value.
   2.436      /// \param i The item.
   2.437      /// \param p The priority.
   2.438 +    /// \pre \e i must be stored in the heap with priority at most \e p.
   2.439      void increase(const Item &i, const Prio &p) {
   2.440 -      int idx = iim[i];
   2.441 -      bubble_down(idx, Pair(i,p), data.size());
   2.442 +      int idx = _iim[i];
   2.443 +      bubbleDown(idx, Pair(i,p), _data.size());
   2.444      }
   2.445  
   2.446 -    /// \brief Returns if \c item is in, has already been in, or has
   2.447 -    /// never been in the heap.
   2.448 +    /// \brief Return the state of an item.
   2.449      ///
   2.450 -    /// This method returns PRE_HEAP if \c item has never been in the
   2.451 -    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   2.452 -    /// otherwise. In the latter case it is possible that \c item will
   2.453 -    /// get back to the heap again.
   2.454 +    /// This method returns \c PRE_HEAP if the given item has never
   2.455 +    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   2.456 +    /// and \c POST_HEAP otherwise.
   2.457 +    /// In the latter case it is possible that the item will get back
   2.458 +    /// to the heap again.
   2.459      /// \param i The item.
   2.460      State state(const Item &i) const {
   2.461 -      int s = iim[i];
   2.462 +      int s = _iim[i];
   2.463        if (s>=0) s=0;
   2.464        return State(s);
   2.465      }
   2.466  
   2.467 -    /// \brief Sets the state of the \c item in the heap.
   2.468 +    /// \brief Set the state of an item in the heap.
   2.469      ///
   2.470 -    /// Sets the state of the \c item in the heap. It can be used to
   2.471 -    /// manually clear the heap when it is important to achive the
   2.472 -    /// better time complexity.
   2.473 +    /// This function sets the state of the given item in the heap.
   2.474 +    /// It can be used to manually clear the heap when it is important
   2.475 +    /// to achive better time complexity.
   2.476      /// \param i The item.
   2.477      /// \param st The state. It should not be \c IN_HEAP.
   2.478      void state(const Item& i, State st) {
   2.479 @@ -323,24 +323,25 @@
   2.480          case POST_HEAP:
   2.481          case PRE_HEAP:
   2.482            if (state(i) == IN_HEAP) erase(i);
   2.483 -          iim[i] = st;
   2.484 +          _iim[i] = st;
   2.485            break;
   2.486          case IN_HEAP:
   2.487            break;
   2.488        }
   2.489      }
   2.490  
   2.491 -    /// \brief Replaces an item in the heap.
   2.492 +    /// \brief Replace an item in the heap.
   2.493      ///
   2.494 -    /// The \c i item is replaced with \c j item. The \c i item should
   2.495 -    /// be in the heap, while the \c j should be out of the heap. The
   2.496 -    /// \c i item will out of the heap and \c j will be in the heap
   2.497 -    /// with the same prioriority as prevoiusly the \c i item.
   2.498 +    /// This function replaces item \c i with item \c j.
   2.499 +    /// Item \c i must be in the heap, while \c j must be out of the heap.
   2.500 +    /// After calling this method, item \c i will be out of the
   2.501 +    /// heap and \c j will be in the heap with the same prioriority
   2.502 +    /// as item \c i had before.
   2.503      void replace(const Item& i, const Item& j) {
   2.504 -      int idx = iim[i];
   2.505 -      iim.set(i, iim[j]);
   2.506 -      iim.set(j, idx);
   2.507 -      data[idx].first = j;
   2.508 +      int idx = _iim[i];
   2.509 +      _iim.set(i, _iim[j]);
   2.510 +      _iim.set(j, idx);
   2.511 +      _data[idx].first = j;
   2.512      }
   2.513  
   2.514    }; // class FouraryHeap
     3.1 --- a/lemon/kary_heap.h	Thu Jul 09 02:39:47 2009 +0200
     3.2 +++ b/lemon/kary_heap.h	Thu Jul 09 04:07:08 2009 +0200
     3.3 @@ -1,8 +1,8 @@
     3.4 -/* -*- C++ -*-
     3.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     3.6   *
     3.7 - * This file is a part of LEMON, a generic C++ optimization library
     3.8 + * This file is a part of LEMON, a generic C++ optimization library.
     3.9   *
    3.10 - * Copyright (C) 2003-2008
    3.11 + * Copyright (C) 2003-2009
    3.12   * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    3.13   * (Egervary Research Group on Combinatorial Optimization, EGRES).
    3.14   *
    3.15 @@ -19,152 +19,151 @@
    3.16  #ifndef LEMON_KARY_HEAP_H
    3.17  #define LEMON_KARY_HEAP_H
    3.18  
    3.19 -///\ingroup auxdat
    3.20 +///\ingroup heaps
    3.21  ///\file
    3.22 -///\brief Kary Heap implementation.
    3.23 +///\brief Fourary heap implementation.
    3.24  
    3.25 -#include <iostream>
    3.26  #include <vector>
    3.27  #include <utility>
    3.28  #include <functional>
    3.29  
    3.30  namespace lemon {
    3.31  
    3.32 -  ///\ingroup auxdat
    3.33 +  /// \ingroup heaps
    3.34    ///
    3.35 -  ///\brief A Kary Heap implementation.
    3.36 +  ///\brief K-ary heap data structure.
    3.37    ///
    3.38 -  ///This class implements the \e Kary \e heap data structure. A \e heap
    3.39 -  ///is a data structure for storing items with specified values called \e
    3.40 -  ///priorities in such a way that finding the item with minimum priority is
    3.41 -  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    3.42 -  ///one can change the priority of an item, add or erase an item, etc.
    3.43 +  /// This class implements the \e K-ary \e heap data structure.
    3.44 +  /// It fully conforms to the \ref concepts::Heap "heap concept".
    3.45    ///
    3.46 -  ///\param _Prio Type of the priority of the items.
    3.47 -  ///\param _ItemIntMap A read and writable Item int map, used internally
    3.48 -  ///to handle the cross references.
    3.49 -  ///\param _Compare A class for the ordering of the priorities. The
    3.50 -  ///default is \c std::less<_Prio>.
    3.51 +  /// The \ref KaryHeap "K-ary heap" is a generalization of the
    3.52 +  /// \ref BinHeap "binary heap" structure, its nodes have at most
    3.53 +  /// \c K children, instead of two.
    3.54 +  /// \ref BinHeap and \ref FouraryHeap are specialized implementations
    3.55 +  /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively.
    3.56    ///
    3.57 -  ///\sa FibHeap
    3.58 -  ///\sa Dijkstra
    3.59 -  ///\author Dorian Batha
    3.60 +  /// \tparam PR Type of the priorities of the items.
    3.61 +  /// \tparam IM A read-writable item map with \c int values, used
    3.62 +  /// internally to handle the cross references.
    3.63 +  /// \tparam CMP A functor class for comparing the priorities.
    3.64 +  /// The default is \c std::less<PR>.
    3.65 +  ///
    3.66 +  ///\sa BinHeap
    3.67 +  ///\sa FouraryHeap
    3.68 +#ifdef DOXYGEN
    3.69 +  template <typename PR, typename IM, typename CMP>
    3.70 +#else
    3.71 +  template <typename PR, typename IM, typename CMP = std::less<PR> >
    3.72 +#endif
    3.73 +  class KaryHeap {
    3.74 +  public:
    3.75 +    /// Type of the item-int map.
    3.76 +    typedef IM ItemIntMap;
    3.77 +    /// Type of the priorities.
    3.78 +    typedef PR Prio;
    3.79 +    /// Type of the items stored in the heap.
    3.80 +    typedef typename ItemIntMap::Key Item;
    3.81 +    /// Type of the item-priority pairs.
    3.82 +    typedef std::pair<Item,Prio> Pair;
    3.83 +    /// Functor type for comparing the priorities.
    3.84 +    typedef CMP Compare;
    3.85  
    3.86 -  template <typename _Prio, typename _ItemIntMap,
    3.87 -            typename _Compare = std::less<_Prio> >
    3.88 -
    3.89 -  class KaryHeap {
    3.90 -
    3.91 -  public:
    3.92 -    ///\e
    3.93 -    typedef _ItemIntMap ItemIntMap;
    3.94 -    ///\e
    3.95 -    typedef _Prio Prio;
    3.96 -    ///\e
    3.97 -    typedef typename ItemIntMap::Key Item;
    3.98 -    ///\e
    3.99 -    typedef std::pair<Item,Prio> Pair;
   3.100 -    ///\e
   3.101 -    typedef _Compare Compare;
   3.102 -    ///\e
   3.103 -
   3.104 -    /// \brief Type to represent the items states.
   3.105 +    /// \brief Type to represent the states of the items.
   3.106      ///
   3.107 -    /// Each Item element have a state associated to it. It may be "in heap",
   3.108 -    /// "pre heap" or "post heap". The latter two are indifferent from the
   3.109 +    /// Each item has a state associated to it. It can be "in heap",
   3.110 +    /// "pre-heap" or "post-heap". The latter two are indifferent from the
   3.111      /// heap's point of view, but may be useful to the user.
   3.112      ///
   3.113 -    /// The ItemIntMap \e should be initialized in such way that it maps
   3.114 -    /// PRE_HEAP (-1) to any element to be put in the heap...
   3.115 +    /// The item-int map must be initialized in such way that it assigns
   3.116 +    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
   3.117      enum State {
   3.118 -      IN_HEAP = 0,
   3.119 -      PRE_HEAP = -1,
   3.120 -      POST_HEAP = -2
   3.121 +      IN_HEAP = 0,    ///< = 0.
   3.122 +      PRE_HEAP = -1,  ///< = -1.
   3.123 +      POST_HEAP = -2  ///< = -2.
   3.124      };
   3.125  
   3.126    private:
   3.127 -    std::vector<Pair> data;
   3.128 -    Compare comp;
   3.129 -    ItemIntMap &iim;
   3.130 -    int K;
   3.131 +    std::vector<Pair> _data;
   3.132 +    Compare _comp;
   3.133 +    ItemIntMap &_iim;
   3.134 +    int _K;
   3.135  
   3.136    public:
   3.137 -    /// \brief The constructor.
   3.138 +    /// \brief Constructor.
   3.139      ///
   3.140 -    /// The constructor.
   3.141 -    /// \param _iim should be given to the constructor, since it is used
   3.142 -    /// internally to handle the cross references. The value of the map
   3.143 -    /// should be PRE_HEAP (-1) for each element.
   3.144 -    explicit KaryHeap(ItemIntMap &_iim, const int &_K=32) : iim(_iim), K(_K) {}
   3.145 +    /// Constructor.
   3.146 +    /// \param map A map that assigns \c int values to the items.
   3.147 +    /// It is used internally to handle the cross references.
   3.148 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   3.149 +    explicit KaryHeap(ItemIntMap &map, int K=32) : _iim(map), _K(K) {}
   3.150  
   3.151 -    /// \brief The constructor.
   3.152 +    /// \brief Constructor.
   3.153      ///
   3.154 -    /// The constructor.
   3.155 -    /// \param _iim should be given to the constructor, since it is used
   3.156 -    /// internally to handle the cross references. The value of the map
   3.157 -    /// should be PRE_HEAP (-1) for each element.
   3.158 +    /// Constructor.
   3.159 +    /// \param map A map that assigns \c int values to the items.
   3.160 +    /// It is used internally to handle the cross references.
   3.161 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   3.162 +    /// \param comp The function object used for comparing the priorities.
   3.163 +    KaryHeap(ItemIntMap &map, const Compare &comp, int K=32)
   3.164 +      : _iim(map), _comp(comp), _K(K) {}
   3.165 +
   3.166 +    /// \brief The number of items stored in the heap.
   3.167      ///
   3.168 -    /// \param _comp The comparator function object.
   3.169 -    KaryHeap(ItemIntMap &_iim, const Compare &_comp, const int &_K=32)
   3.170 -      : iim(_iim), comp(_comp), K(_K) {}
   3.171 +    /// This function returns the number of items stored in the heap.
   3.172 +    int size() const { return _data.size(); }
   3.173  
   3.174 +    /// \brief Check if the heap is empty.
   3.175 +    ///
   3.176 +    /// This function returns \c true if the heap is empty.
   3.177 +    bool empty() const { return _data.empty(); }
   3.178  
   3.179 -    /// The number of items stored in the heap.
   3.180 +    /// \brief Make the heap empty.
   3.181      ///
   3.182 -    /// \brief Returns the number of items stored in the heap.
   3.183 -    int size() const { return data.size(); }
   3.184 -
   3.185 -    /// \brief Checks if the heap stores no items.
   3.186 -    ///
   3.187 -    /// Returns \c true if and only if the heap stores no items.
   3.188 -    bool empty() const { return data.empty(); }
   3.189 -
   3.190 -    /// \brief Make empty this heap.
   3.191 -    ///
   3.192 -    /// Make empty this heap. It does not change the cross reference map.
   3.193 -    /// If you want to reuse what is not surely empty you should first clear
   3.194 -    /// the heap and after that you should set the cross reference map for
   3.195 -    /// each item to \c PRE_HEAP.
   3.196 -    void clear() { data.clear(); }
   3.197 +    /// This functon makes the heap empty.
   3.198 +    /// It does not change the cross reference map. If you want to reuse
   3.199 +    /// a heap that is not surely empty, you should first clear it and
   3.200 +    /// then you should set the cross reference map to \c PRE_HEAP
   3.201 +    /// for each item.
   3.202 +    void clear() { _data.clear(); }
   3.203  
   3.204    private:
   3.205 -    int parent(int i) { return (i-1)/K; }
   3.206 -    int first_child(int i) { return K*i+1; }
   3.207 +    int parent(int i) { return (i-1)/_K; }
   3.208 +    int firstChild(int i) { return _K*i+1; }
   3.209  
   3.210      bool less(const Pair &p1, const Pair &p2) const {
   3.211 -      return comp(p1.second, p2.second);
   3.212 +      return _comp(p1.second, p2.second);
   3.213      }
   3.214  
   3.215 -    int find_min(const int child, const int length) {
   3.216 +    int findMin(const int child, const int length) {
   3.217        int min=child, i=1;
   3.218 -      while( i<K && child+i<length ) {
   3.219 -        if( less(data[child+i], data[min]) )
   3.220 +      while( i<_K && child+i<length ) {
   3.221 +        if( less(_data[child+i], _data[min]) )
   3.222            min=child+i;
   3.223          ++i;
   3.224        }
   3.225        return min;
   3.226      }
   3.227  
   3.228 -    void bubble_up(int hole, Pair p) {
   3.229 +    void bubbleUp(int hole, Pair p) {
   3.230        int par = parent(hole);
   3.231 -      while( hole>0 && less(p,data[par]) ) {
   3.232 -        move(data[par],hole);
   3.233 +      while( hole>0 && less(p,_data[par]) ) {
   3.234 +        move(_data[par],hole);
   3.235          hole = par;
   3.236          par = parent(hole);
   3.237        }
   3.238        move(p, hole);
   3.239      }
   3.240  
   3.241 -    void bubble_down(int hole, Pair p, int length) {
   3.242 +    void bubbleDown(int hole, Pair p, int length) {
   3.243        if( length>1 ) {
   3.244 -        int child = first_child(hole);
   3.245 +        int child = firstChild(hole);
   3.246          while( child<length ) {
   3.247 -          child = find_min(child, length);
   3.248 -          if( !less(data[child], p) )
   3.249 +          child = findMin(child, length);
   3.250 +          if( !less(_data[child], p) )
   3.251              goto ok;
   3.252 -          move(data[child], hole);
   3.253 +          move(_data[child], hole);
   3.254            hole = child;
   3.255 -          child = first_child(hole);
   3.256 +          child = firstChild(hole);
   3.257          }
   3.258        }
   3.259      ok:
   3.260 @@ -172,167 +171,169 @@
   3.261      }
   3.262  
   3.263      void move(const Pair &p, int i) {
   3.264 -      data[i] = p;
   3.265 -      iim.set(p.first, i);
   3.266 +      _data[i] = p;
   3.267 +      _iim.set(p.first, i);
   3.268      }
   3.269  
   3.270    public:
   3.271      /// \brief Insert a pair of item and priority into the heap.
   3.272      ///
   3.273 -    /// Adds \c p.first to the heap with priority \c p.second.
   3.274 +    /// This function inserts \c p.first to the heap with priority
   3.275 +    /// \c p.second.
   3.276      /// \param p The pair to insert.
   3.277 +    /// \pre \c p.first must not be stored in the heap.
   3.278      void push(const Pair &p) {
   3.279 -      int n = data.size();
   3.280 -      data.resize(n+1);
   3.281 -      bubble_up(n, p);
   3.282 +      int n = _data.size();
   3.283 +      _data.resize(n+1);
   3.284 +      bubbleUp(n, p);
   3.285      }
   3.286  
   3.287 -    /// \brief Insert an item into the heap with the given heap.
   3.288 +    /// \brief Insert an item into the heap with the given priority.
   3.289      ///
   3.290 -    /// Adds \c i to the heap with priority \c p.
   3.291 +    /// This function inserts the given item into the heap with the
   3.292 +    /// given priority.
   3.293      /// \param i The item to insert.
   3.294      /// \param p The priority of the item.
   3.295 +    /// \pre \e i must not be stored in the heap.
   3.296      void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
   3.297  
   3.298 -    /// \brief Returns the item with minimum priority relative to \c Compare.
   3.299 +    /// \brief Return the item having minimum priority.
   3.300      ///
   3.301 -    /// This method returns the item with minimum priority relative to \c
   3.302 -    /// Compare.
   3.303 -    /// \pre The heap must be nonempty.
   3.304 -    Item top() const { return data[0].first; }
   3.305 +    /// This function returns the item having minimum priority.
   3.306 +    /// \pre The heap must be non-empty.
   3.307 +    Item top() const { return _data[0].first; }
   3.308  
   3.309 -    /// \brief Returns the minimum priority relative to \c Compare.
   3.310 +    /// \brief The minimum priority.
   3.311      ///
   3.312 -    /// It returns the minimum priority relative to \c Compare.
   3.313 -    /// \pre The heap must be nonempty.
   3.314 -    Prio prio() const { return data[0].second; }
   3.315 +    /// This function returns the minimum priority.
   3.316 +    /// \pre The heap must be non-empty.
   3.317 +    Prio prio() const { return _data[0].second; }
   3.318  
   3.319 -    /// \brief Deletes the item with minimum priority relative to \c Compare.
   3.320 +    /// \brief Remove the item having minimum priority.
   3.321      ///
   3.322 -    /// This method deletes the item with minimum priority relative to \c
   3.323 -    /// Compare from the heap.
   3.324 +    /// This function removes the item having minimum priority.
   3.325      /// \pre The heap must be non-empty.
   3.326      void pop() {
   3.327 -      int n = data.size()-1;
   3.328 -      iim.set(data[0].first, POST_HEAP);
   3.329 -      if (n>0) bubble_down(0, data[n], n);
   3.330 -      data.pop_back();
   3.331 +      int n = _data.size()-1;
   3.332 +      _iim.set(_data[0].first, POST_HEAP);
   3.333 +      if (n>0) bubbleDown(0, _data[n], n);
   3.334 +      _data.pop_back();
   3.335      }
   3.336  
   3.337 -    /// \brief Deletes \c i from the heap.
   3.338 +    /// \brief Remove the given item from the heap.
   3.339      ///
   3.340 -    /// This method deletes item \c i from the heap.
   3.341 -    /// \param i The item to erase.
   3.342 -    /// \pre The item should be in the heap.
   3.343 +    /// This function removes the given item from the heap if it is
   3.344 +    /// already stored.
   3.345 +    /// \param i The item to delete.
   3.346 +    /// \pre \e i must be in the heap.
   3.347      void erase(const Item &i) {
   3.348 -      int h = iim[i];
   3.349 -      int n = data.size()-1;
   3.350 -      iim.set(data[h].first, POST_HEAP);
   3.351 +      int h = _iim[i];
   3.352 +      int n = _data.size()-1;
   3.353 +      _iim.set(_data[h].first, POST_HEAP);
   3.354        if( h<n ) {
   3.355 -        if( less(data[parent(h)], data[n]) )
   3.356 -          bubble_down(h, data[n], n);
   3.357 +        if( less(_data[parent(h)], _data[n]) )
   3.358 +          bubbleDown(h, _data[n], n);
   3.359          else
   3.360 -          bubble_up(h, data[n]);
   3.361 +          bubbleUp(h, _data[n]);
   3.362        }
   3.363 -      data.pop_back();
   3.364 +      _data.pop_back();
   3.365      }
   3.366  
   3.367 -
   3.368 -    /// \brief Returns the priority of \c i.
   3.369 +    /// \brief The priority of the given item.
   3.370      ///
   3.371 -    /// This function returns the priority of item \c i.
   3.372 -    /// \pre \c i must be in the heap.
   3.373 +    /// This function returns the priority of the given item.
   3.374      /// \param i The item.
   3.375 +    /// \pre \e i must be in the heap.
   3.376      Prio operator[](const Item &i) const {
   3.377 -      int idx = iim[i];
   3.378 -      return data[idx].second;
   3.379 +      int idx = _iim[i];
   3.380 +      return _data[idx].second;
   3.381      }
   3.382  
   3.383 -    /// \brief \c i gets to the heap with priority \c p independently
   3.384 -    /// if \c i was already there.
   3.385 +    /// \brief Set the priority of an item or insert it, if it is
   3.386 +    /// not stored in the heap.
   3.387      ///
   3.388 -    /// This method calls \ref push(\c i, \c p) if \c i is not stored
   3.389 -    /// in the heap and sets the priority of \c i to \c p otherwise.
   3.390 +    /// This method sets the priority of the given item if it is
   3.391 +    /// already stored in the heap. Otherwise it inserts the given
   3.392 +    /// item into the heap with the given priority.
   3.393      /// \param i The item.
   3.394      /// \param p The priority.
   3.395      void set(const Item &i, const Prio &p) {
   3.396 -      int idx = iim[i];
   3.397 +      int idx = _iim[i];
   3.398        if( idx<0 )
   3.399          push(i,p);
   3.400 -      else if( comp(p, data[idx].second) )
   3.401 -        bubble_up(idx, Pair(i,p));
   3.402 +      else if( _comp(p, _data[idx].second) )
   3.403 +        bubbleUp(idx, Pair(i,p));
   3.404        else
   3.405 -        bubble_down(idx, Pair(i,p), data.size());
   3.406 +        bubbleDown(idx, Pair(i,p), _data.size());
   3.407      }
   3.408  
   3.409 -    /// \brief Decreases the priority of \c i to \c p.
   3.410 +    /// \brief Decrease the priority of an item to the given value.
   3.411      ///
   3.412 -    /// This method decreases the priority of item \c i to \c p.
   3.413 -    /// \pre \c i must be stored in the heap with priority at least \c
   3.414 -    /// p relative to \c Compare.
   3.415 +    /// This function decreases the priority of an item to the given value.
   3.416      /// \param i The item.
   3.417      /// \param p The priority.
   3.418 +    /// \pre \e i must be stored in the heap with priority at least \e p.
   3.419      void decrease(const Item &i, const Prio &p) {
   3.420 -      int idx = iim[i];
   3.421 -      bubble_up(idx, Pair(i,p));
   3.422 +      int idx = _iim[i];
   3.423 +      bubbleUp(idx, Pair(i,p));
   3.424      }
   3.425  
   3.426 -    /// \brief Increases the priority of \c i to \c p.
   3.427 +    /// \brief Increase the priority of an item to the given value.
   3.428      ///
   3.429 -    /// This method sets the priority of item \c i to \c p.
   3.430 -    /// \pre \c i must be stored in the heap with priority at most \c
   3.431 -    /// p relative to \c Compare.
   3.432 +    /// This function increases the priority of an item to the given value.
   3.433      /// \param i The item.
   3.434      /// \param p The priority.
   3.435 +    /// \pre \e i must be stored in the heap with priority at most \e p.
   3.436      void increase(const Item &i, const Prio &p) {
   3.437 -      int idx = iim[i];
   3.438 -      bubble_down(idx, Pair(i,p), data.size());
   3.439 +      int idx = _iim[i];
   3.440 +      bubbleDown(idx, Pair(i,p), _data.size());
   3.441      }
   3.442  
   3.443 -    /// \brief Returns if \c item is in, has already been in, or has
   3.444 -    /// never been in the heap.
   3.445 +    /// \brief Return the state of an item.
   3.446      ///
   3.447 -    /// This method returns PRE_HEAP if \c item has never been in the
   3.448 -    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   3.449 -    /// otherwise. In the latter case it is possible that \c item will
   3.450 -    /// get back to the heap again.
   3.451 +    /// This method returns \c PRE_HEAP if the given item has never
   3.452 +    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   3.453 +    /// and \c POST_HEAP otherwise.
   3.454 +    /// In the latter case it is possible that the item will get back
   3.455 +    /// to the heap again.
   3.456      /// \param i The item.
   3.457      State state(const Item &i) const {
   3.458 -      int s = iim[i];
   3.459 +      int s = _iim[i];
   3.460        if (s>=0) s=0;
   3.461        return State(s);
   3.462      }
   3.463  
   3.464 -    /// \brief Sets the state of the \c item in the heap.
   3.465 +    /// \brief Set the state of an item in the heap.
   3.466      ///
   3.467 -    /// Sets the state of the \c item in the heap. It can be used to
   3.468 -    /// manually clear the heap when it is important to achive the
   3.469 -    /// better time complexity.
   3.470 +    /// This function sets the state of the given item in the heap.
   3.471 +    /// It can be used to manually clear the heap when it is important
   3.472 +    /// to achive better time complexity.
   3.473      /// \param i The item.
   3.474      /// \param st The state. It should not be \c IN_HEAP.
   3.475      void state(const Item& i, State st) {
   3.476        switch (st) {
   3.477 -      case POST_HEAP:
   3.478 -      case PRE_HEAP:
   3.479 -        if (state(i) == IN_HEAP) erase(i);
   3.480 -        iim[i] = st;
   3.481 -        break;
   3.482 -      case IN_HEAP:
   3.483 -        break;
   3.484 +        case POST_HEAP:
   3.485 +        case PRE_HEAP:
   3.486 +          if (state(i) == IN_HEAP) erase(i);
   3.487 +          _iim[i] = st;
   3.488 +          break;
   3.489 +        case IN_HEAP:
   3.490 +          break;
   3.491        }
   3.492      }
   3.493  
   3.494 -    /// \brief Replaces an item in the heap.
   3.495 +    /// \brief Replace an item in the heap.
   3.496      ///
   3.497 -    /// The \c i item is replaced with \c j item. The \c i item should
   3.498 -    /// be in the heap, while the \c j should be out of the heap. The
   3.499 -    /// \c i item will out of the heap and \c j will be in the heap
   3.500 -    /// with the same prioriority as prevoiusly the \c i item.
   3.501 +    /// This function replaces item \c i with item \c j.
   3.502 +    /// Item \c i must be in the heap, while \c j must be out of the heap.
   3.503 +    /// After calling this method, item \c i will be out of the
   3.504 +    /// heap and \c j will be in the heap with the same prioriority
   3.505 +    /// as item \c i had before.
   3.506      void replace(const Item& i, const Item& j) {
   3.507 -      int idx=iim[i];
   3.508 -      iim.set(i, iim[j]);
   3.509 -      iim.set(j, idx);
   3.510 -      data[idx].first=j;
   3.511 +      int idx=_iim[i];
   3.512 +      _iim.set(i, _iim[j]);
   3.513 +      _iim.set(j, idx);
   3.514 +      _data[idx].first=j;
   3.515      }
   3.516  
   3.517    }; // class KaryHeap
     4.1 --- a/lemon/pairing_heap.h	Thu Jul 09 02:39:47 2009 +0200
     4.2 +++ b/lemon/pairing_heap.h	Thu Jul 09 04:07:08 2009 +0200
     4.3 @@ -1,8 +1,8 @@
     4.4 -/* -*- C++ -*-
     4.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     4.6   *
     4.7 - * This file is a part of LEMON, a generic C++ optimization library
     4.8 + * This file is a part of LEMON, a generic C++ optimization library.
     4.9   *
    4.10 - * Copyright (C) 2003-2008
    4.11 + * Copyright (C) 2003-2009
    4.12   * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    4.13   * (Egervary Research Group on Combinatorial Optimization, EGRES).
    4.14   *
    4.15 @@ -20,217 +20,223 @@
    4.16  #define LEMON_PAIRING_HEAP_H
    4.17  
    4.18  ///\file
    4.19 -///\ingroup auxdat
    4.20 -///\brief Pairing Heap implementation.
    4.21 +///\ingroup heaps
    4.22 +///\brief Pairing heap implementation.
    4.23  
    4.24  #include <vector>
    4.25 +#include <utility>
    4.26  #include <functional>
    4.27  #include <lemon/math.h>
    4.28  
    4.29  namespace lemon {
    4.30  
    4.31 -  /// \ingroup auxdat
    4.32 +  /// \ingroup heaps
    4.33    ///
    4.34    ///\brief Pairing Heap.
    4.35    ///
    4.36 -  ///This class implements the \e Pairing \e heap data structure. A \e heap
    4.37 -  ///is a data structure for storing items with specified values called \e
    4.38 -  ///priorities in such a way that finding the item with minimum priority is
    4.39 -  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    4.40 -  ///one can change the priority of an item, add or erase an item, etc.
    4.41 +  /// This class implements the \e pairing \e heap data structure.
    4.42 +  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4.43    ///
    4.44 -  ///The methods \ref increase and \ref erase are not efficient in a Pairing
    4.45 -  ///heap. In case of many calls to these operations, it is better to use a
    4.46 -  ///\ref BinHeap "binary heap".
    4.47 +  /// The methods \ref increase() and \ref erase() are not efficient
    4.48 +  /// in a pairing heap. In case of many calls of these operations,
    4.49 +  /// it is better to use other heap structure, e.g. \ref BinHeap
    4.50 +  /// "binary heap".
    4.51    ///
    4.52 -  ///\param _Prio Type of the priority of the items.
    4.53 -  ///\param _ItemIntMap A read and writable Item int map, used internally
    4.54 -  ///to handle the cross references.
    4.55 -  ///\param _Compare A class for the ordering of the priorities. The
    4.56 -  ///default is \c std::less<_Prio>.
    4.57 -  ///
    4.58 -  ///\sa BinHeap
    4.59 -  ///\sa Dijkstra
    4.60 -  ///\author Dorian Batha
    4.61 -
    4.62 +  /// \tparam PR Type of the priorities of the items.
    4.63 +  /// \tparam IM A read-writable item map with \c int values, used
    4.64 +  /// internally to handle the cross references.
    4.65 +  /// \tparam CMP A functor class for comparing the priorities.
    4.66 +  /// The default is \c std::less<PR>.
    4.67  #ifdef DOXYGEN
    4.68 -  template <typename _Prio,
    4.69 -            typename _ItemIntMap,
    4.70 -            typename _Compare>
    4.71 +  template <typename PR, typename IM, typename CMP>
    4.72  #else
    4.73 -  template <typename _Prio,
    4.74 -            typename _ItemIntMap,
    4.75 -            typename _Compare = std::less<_Prio> >
    4.76 +  template <typename PR, typename IM, typename CMP = std::less<PR> >
    4.77  #endif
    4.78    class PairingHeap {
    4.79    public:
    4.80 -    typedef _ItemIntMap ItemIntMap;
    4.81 -    typedef _Prio Prio;
    4.82 +    /// Type of the item-int map.
    4.83 +    typedef IM ItemIntMap;
    4.84 +    /// Type of the priorities.
    4.85 +    typedef PR Prio;
    4.86 +    /// Type of the items stored in the heap.
    4.87      typedef typename ItemIntMap::Key Item;
    4.88 -    typedef std::pair<Item,Prio> Pair;
    4.89 -    typedef _Compare Compare;
    4.90 +    /// Functor type for comparing the priorities.
    4.91 +    typedef CMP Compare;
    4.92 +
    4.93 +    /// \brief Type to represent the states of the items.
    4.94 +    ///
    4.95 +    /// Each item has a state associated to it. It can be "in heap",
    4.96 +    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    4.97 +    /// heap's point of view, but may be useful to the user.
    4.98 +    ///
    4.99 +    /// The item-int map must be initialized in such way that it assigns
   4.100 +    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
   4.101 +    enum State {
   4.102 +      IN_HEAP = 0,    ///< = 0.
   4.103 +      PRE_HEAP = -1,  ///< = -1.
   4.104 +      POST_HEAP = -2  ///< = -2.
   4.105 +    };
   4.106  
   4.107    private:
   4.108      class store;
   4.109  
   4.110 -    std::vector<store> container;
   4.111 -    int minimum;
   4.112 -    ItemIntMap &iimap;
   4.113 -    Compare comp;
   4.114 -    int num_items;
   4.115 +    std::vector<store> _data;
   4.116 +    int _min;
   4.117 +    ItemIntMap &_iim;
   4.118 +    Compare _comp;
   4.119 +    int _num_items;
   4.120  
   4.121    public:
   4.122 -    ///Status of the nodes
   4.123 -    enum State {
   4.124 -      ///The node is in the heap
   4.125 -      IN_HEAP = 0,
   4.126 -      ///The node has never been in the heap
   4.127 -      PRE_HEAP = -1,
   4.128 -      ///The node was in the heap but it got out of it
   4.129 -      POST_HEAP = -2
   4.130 -    };
   4.131 +    /// \brief Constructor.
   4.132 +    ///
   4.133 +    /// Constructor.
   4.134 +    /// \param map A map that assigns \c int values to the items.
   4.135 +    /// It is used internally to handle the cross references.
   4.136 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   4.137 +    explicit PairingHeap(ItemIntMap &map)
   4.138 +      : _min(0), _iim(map), _num_items(0) {}
   4.139  
   4.140 -    /// \brief The constructor
   4.141 +    /// \brief Constructor.
   4.142      ///
   4.143 -    /// \c _iimap should be given to the constructor, since it is
   4.144 -    ///   used internally to handle the cross references.
   4.145 -    explicit PairingHeap(ItemIntMap &_iimap)
   4.146 -      : minimum(0), iimap(_iimap), num_items(0) {}
   4.147 -
   4.148 -    /// \brief The constructor
   4.149 -    ///
   4.150 -    /// \c _iimap should be given to the constructor, since it is used
   4.151 -    /// internally to handle the cross references. \c _comp is an
   4.152 -    /// object for ordering of the priorities.
   4.153 -    PairingHeap(ItemIntMap &_iimap, const Compare &_comp)
   4.154 -      : minimum(0), iimap(_iimap), comp(_comp), num_items(0) {}
   4.155 +    /// Constructor.
   4.156 +    /// \param map A map that assigns \c int values to the items.
   4.157 +    /// It is used internally to handle the cross references.
   4.158 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   4.159 +    /// \param comp The function object used for comparing the priorities.
   4.160 +    PairingHeap(ItemIntMap &map, const Compare &comp)
   4.161 +      : _min(0), _iim(map), _comp(comp), _num_items(0) {}
   4.162  
   4.163      /// \brief The number of items stored in the heap.
   4.164      ///
   4.165 -    /// Returns the number of items stored in the heap.
   4.166 -    int size() const { return num_items; }
   4.167 +    /// This function returns the number of items stored in the heap.
   4.168 +    int size() const { return _num_items; }
   4.169  
   4.170 -    /// \brief Checks if the heap stores no items.
   4.171 +    /// \brief Check if the heap is empty.
   4.172      ///
   4.173 -    ///   Returns \c true if and only if the heap stores no items.
   4.174 -    bool empty() const { return num_items==0; }
   4.175 +    /// This function returns \c true if the heap is empty.
   4.176 +    bool empty() const { return _num_items==0; }
   4.177  
   4.178 -    /// \brief Make empty this heap.
   4.179 +    /// \brief Make the heap empty.
   4.180      ///
   4.181 -    /// Make empty this heap. It does not change the cross reference
   4.182 -    /// map.  If you want to reuse a heap what is not surely empty you
   4.183 -    /// should first clear the heap and after that you should set the
   4.184 -    /// cross reference map for each item to \c PRE_HEAP.
   4.185 +    /// This functon makes the heap empty.
   4.186 +    /// It does not change the cross reference map. If you want to reuse
   4.187 +    /// a heap that is not surely empty, you should first clear it and
   4.188 +    /// then you should set the cross reference map to \c PRE_HEAP
   4.189 +    /// for each item.
   4.190      void clear() {
   4.191 -      container.clear();
   4.192 -      minimum = 0;
   4.193 -      num_items = 0;
   4.194 +      _data.clear();
   4.195 +      _min = 0;
   4.196 +      _num_items = 0;
   4.197      }
   4.198  
   4.199 -    /// \brief \c item gets to the heap with priority \c value independently
   4.200 -    /// if \c item was already there.
   4.201 +    /// \brief Set the priority of an item or insert it, if it is
   4.202 +    /// not stored in the heap.
   4.203      ///
   4.204 -    /// This method calls \ref push(\c item, \c value) if \c item is not
   4.205 -    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
   4.206 -    /// \ref increase(\c item, \c value) otherwise.
   4.207 +    /// This method sets the priority of the given item if it is
   4.208 +    /// already stored in the heap. Otherwise it inserts the given
   4.209 +    /// item into the heap with the given priority.
   4.210 +    /// \param item The item.
   4.211 +    /// \param value The priority.
   4.212      void set (const Item& item, const Prio& value) {
   4.213 -      int i=iimap[item];
   4.214 -      if ( i>=0 && container[i].in ) {
   4.215 -        if ( comp(value, container[i].prio) ) decrease(item, value);
   4.216 -        if ( comp(container[i].prio, value) ) increase(item, value);
   4.217 +      int i=_iim[item];
   4.218 +      if ( i>=0 && _data[i].in ) {
   4.219 +        if ( _comp(value, _data[i].prio) ) decrease(item, value);
   4.220 +        if ( _comp(_data[i].prio, value) ) increase(item, value);
   4.221        } else push(item, value);
   4.222      }
   4.223  
   4.224 -    /// \brief Adds \c item to the heap with priority \c value.
   4.225 +    /// \brief Insert an item into the heap with the given priority.
   4.226      ///
   4.227 -    /// Adds \c item to the heap with priority \c value.
   4.228 -    /// \pre \c item must not be stored in the heap.
   4.229 +    /// This function inserts the given item into the heap with the
   4.230 +    /// given priority.
   4.231 +    /// \param item The item to insert.
   4.232 +    /// \param value The priority of the item.
   4.233 +    /// \pre \e item must not be stored in the heap.
   4.234      void push (const Item& item, const Prio& value) {
   4.235 -      int i=iimap[item];
   4.236 +      int i=_iim[item];
   4.237        if( i<0 ) {
   4.238 -        int s=container.size();
   4.239 -        iimap.set(item, s);
   4.240 +        int s=_data.size();
   4.241 +        _iim.set(item, s);
   4.242          store st;
   4.243          st.name=item;
   4.244 -        container.push_back(st);
   4.245 +        _data.push_back(st);
   4.246          i=s;
   4.247        } else {
   4.248 -        container[i].parent=container[i].child=-1;
   4.249 -        container[i].left_child=false;
   4.250 -        container[i].degree=0;
   4.251 -        container[i].in=true;
   4.252 +        _data[i].parent=_data[i].child=-1;
   4.253 +        _data[i].left_child=false;
   4.254 +        _data[i].degree=0;
   4.255 +        _data[i].in=true;
   4.256        }
   4.257  
   4.258 -      container[i].prio=value;
   4.259 +      _data[i].prio=value;
   4.260  
   4.261 -      if ( num_items!=0 ) {
   4.262 -        if ( comp( value, container[minimum].prio) ) {
   4.263 -          fuse(i,minimum);
   4.264 -          minimum=i;
   4.265 +      if ( _num_items!=0 ) {
   4.266 +        if ( _comp( value, _data[_min].prio) ) {
   4.267 +          fuse(i,_min);
   4.268 +          _min=i;
   4.269          }
   4.270 -        else fuse(minimum,i);
   4.271 +        else fuse(_min,i);
   4.272        }
   4.273 -      else minimum=i;
   4.274 +      else _min=i;
   4.275  
   4.276 -      ++num_items;
   4.277 +      ++_num_items;
   4.278      }
   4.279  
   4.280 -    /// \brief Returns the item with minimum priority relative to \c Compare.
   4.281 +    /// \brief Return the item having minimum priority.
   4.282      ///
   4.283 -    /// This method returns the item with minimum priority relative to \c
   4.284 -    /// Compare.
   4.285 -    /// \pre The heap must be nonempty.
   4.286 -    Item top() const { return container[minimum].name; }
   4.287 +    /// This function returns the item having minimum priority.
   4.288 +    /// \pre The heap must be non-empty.
   4.289 +    Item top() const { return _data[_min].name; }
   4.290  
   4.291 -    /// \brief Returns the minimum priority relative to \c Compare.
   4.292 +    /// \brief The minimum priority.
   4.293      ///
   4.294 -    /// It returns the minimum priority relative to \c Compare.
   4.295 -    /// \pre The heap must be nonempty.
   4.296 -    const Prio& prio() const { return container[minimum].prio; }
   4.297 +    /// This function returns the minimum priority.
   4.298 +    /// \pre The heap must be non-empty.
   4.299 +    const Prio& prio() const { return _data[_min].prio; }
   4.300  
   4.301 -    /// \brief Returns the priority of \c item.
   4.302 +    /// \brief The priority of the given item.
   4.303      ///
   4.304 -    /// It returns the priority of \c item.
   4.305 -    /// \pre \c item must be in the heap.
   4.306 +    /// This function returns the priority of the given item.
   4.307 +    /// \param item The item.
   4.308 +    /// \pre \e item must be in the heap.
   4.309      const Prio& operator[](const Item& item) const {
   4.310 -      return container[iimap[item]].prio;
   4.311 +      return _data[_iim[item]].prio;
   4.312      }
   4.313  
   4.314 -    /// \brief Deletes the item with minimum priority relative to \c Compare.
   4.315 +    /// \brief Remove the item having minimum priority.
   4.316      ///
   4.317 -    /// This method deletes the item with minimum priority relative to \c
   4.318 -    /// Compare from the heap.
   4.319 +    /// This function removes the item having minimum priority.
   4.320      /// \pre The heap must be non-empty.
   4.321      void pop() {
   4.322 -      int TreeArray[num_items];
   4.323 +      int TreeArray[_num_items];
   4.324        int i=0, num_child=0, child_right = 0;
   4.325 -      container[minimum].in=false;
   4.326 +      _data[_min].in=false;
   4.327  
   4.328 -      if( -1!=container[minimum].child ) {
   4.329 -        i=container[minimum].child;
   4.330 +      if( -1!=_data[_min].child ) {
   4.331 +        i=_data[_min].child;
   4.332          TreeArray[num_child] = i;
   4.333 -        container[i].parent = -1;
   4.334 -        container[minimum].child = -1;
   4.335 +        _data[i].parent = -1;
   4.336 +        _data[_min].child = -1;
   4.337  
   4.338          ++num_child;
   4.339          int ch=-1;
   4.340 -        while( container[i].child!=-1 ) {
   4.341 -          ch=container[i].child;
   4.342 -          if( container[ch].left_child && i==container[ch].parent ) {
   4.343 +        while( _data[i].child!=-1 ) {
   4.344 +          ch=_data[i].child;
   4.345 +          if( _data[ch].left_child && i==_data[ch].parent ) {
   4.346              i=ch;
   4.347              //break;
   4.348            } else {
   4.349 -            if( container[ch].left_child ) {
   4.350 -              child_right=container[ch].parent;
   4.351 -              container[ch].parent = i;
   4.352 -              --container[i].degree;
   4.353 +            if( _data[ch].left_child ) {
   4.354 +              child_right=_data[ch].parent;
   4.355 +              _data[ch].parent = i;
   4.356 +              --_data[i].degree;
   4.357              }
   4.358              else {
   4.359                child_right=ch;
   4.360 -              container[i].child=-1;
   4.361 -              container[i].degree=0;
   4.362 +              _data[i].child=-1;
   4.363 +              _data[i].degree=0;
   4.364              }
   4.365 -            container[child_right].parent = -1;
   4.366 +            _data[child_right].parent = -1;
   4.367              TreeArray[num_child] = child_right;
   4.368              i = child_right;
   4.369              ++num_child;
   4.370 @@ -239,8 +245,8 @@
   4.371  
   4.372          int other;
   4.373          for( i=0; i<num_child-1; i+=2 ) {
   4.374 -          if ( !comp(container[TreeArray[i]].prio,
   4.375 -                     container[TreeArray[i+1]].prio) ) {
   4.376 +          if ( !_comp(_data[TreeArray[i]].prio,
   4.377 +                     _data[TreeArray[i+1]].prio) ) {
   4.378              other=TreeArray[i];
   4.379              TreeArray[i]=TreeArray[i+1];
   4.380              TreeArray[i+1]=other;
   4.381 @@ -250,8 +256,8 @@
   4.382  
   4.383          i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
   4.384          while(i>=2) {
   4.385 -          if ( comp(container[TreeArray[i]].prio,
   4.386 -                    container[TreeArray[i-2]].prio) ) {
   4.387 +          if ( _comp(_data[TreeArray[i]].prio,
   4.388 +                    _data[TreeArray[i-2]].prio) ) {
   4.389              other=TreeArray[i];
   4.390              TreeArray[i]=TreeArray[i-2];
   4.391              TreeArray[i-2]=other;
   4.392 @@ -259,88 +265,91 @@
   4.393            fuse( TreeArray[i-2], TreeArray[i] );
   4.394            i-=2;
   4.395          }
   4.396 -        minimum = TreeArray[0];
   4.397 +        _min = TreeArray[0];
   4.398        }
   4.399  
   4.400        if ( 0==num_child ) {
   4.401 -        minimum = container[minimum].child;
   4.402 +        _min = _data[_min].child;
   4.403        }
   4.404  
   4.405 -      if (minimum >= 0) container[minimum].left_child = false;
   4.406 +      if (_min >= 0) _data[_min].left_child = false;
   4.407  
   4.408 -      --num_items;
   4.409 +      --_num_items;
   4.410      }
   4.411  
   4.412 -    /// \brief Deletes \c item from the heap.
   4.413 +    /// \brief Remove the given item from the heap.
   4.414      ///
   4.415 -    /// This method deletes \c item from the heap, if \c item was already
   4.416 -    /// stored in the heap. It is quite inefficient in Pairing heaps.
   4.417 +    /// This function removes the given item from the heap if it is
   4.418 +    /// already stored.
   4.419 +    /// \param item The item to delete.
   4.420 +    /// \pre \e item must be in the heap.
   4.421      void erase (const Item& item) {
   4.422 -      int i=iimap[item];
   4.423 -      if ( i>=0 && container[i].in ) {
   4.424 -        decrease( item, container[minimum].prio-1 );
   4.425 +      int i=_iim[item];
   4.426 +      if ( i>=0 && _data[i].in ) {
   4.427 +        decrease( item, _data[_min].prio-1 );
   4.428          pop();
   4.429        }
   4.430      }
   4.431  
   4.432 -    /// \brief Decreases the priority of \c item to \c value.
   4.433 +    /// \brief Decrease the priority of an item to the given value.
   4.434      ///
   4.435 -    /// This method decreases the priority of \c item to \c value.
   4.436 -    /// \pre \c item must be stored in the heap with priority at least \c
   4.437 -    ///   value relative to \c Compare.
   4.438 +    /// This function decreases the priority of an item to the given value.
   4.439 +    /// \param item The item.
   4.440 +    /// \param value The priority.
   4.441 +    /// \pre \e item must be stored in the heap with priority at least \e value.
   4.442      void decrease (Item item, const Prio& value) {
   4.443 -      int i=iimap[item];
   4.444 -      container[i].prio=value;
   4.445 -      int p=container[i].parent;
   4.446 +      int i=_iim[item];
   4.447 +      _data[i].prio=value;
   4.448 +      int p=_data[i].parent;
   4.449  
   4.450 -      if( container[i].left_child && i!=container[p].child ) {
   4.451 -        p=container[p].parent;
   4.452 +      if( _data[i].left_child && i!=_data[p].child ) {
   4.453 +        p=_data[p].parent;
   4.454        }
   4.455  
   4.456 -      if ( p!=-1 && comp(value,container[p].prio) ) {
   4.457 +      if ( p!=-1 && _comp(value,_data[p].prio) ) {
   4.458          cut(i,p);
   4.459 -        if ( comp(container[minimum].prio,value) ) {
   4.460 -          fuse(minimum,i);
   4.461 +        if ( _comp(_data[_min].prio,value) ) {
   4.462 +          fuse(_min,i);
   4.463          } else {
   4.464 -          fuse(i,minimum);
   4.465 -          minimum=i;
   4.466 +          fuse(i,_min);
   4.467 +          _min=i;
   4.468          }
   4.469        }
   4.470      }
   4.471  
   4.472 -    /// \brief Increases the priority of \c item to \c value.
   4.473 +    /// \brief Increase the priority of an item to the given value.
   4.474      ///
   4.475 -    /// This method sets the priority of \c item to \c value. Though
   4.476 -    /// there is no precondition on the priority of \c item, this
   4.477 -    /// method should be used only if it is indeed necessary to increase
   4.478 -    /// (relative to \c Compare) the priority of \c item, because this
   4.479 -    /// method is inefficient.
   4.480 +    /// This function increases the priority of an item to the given value.
   4.481 +    /// \param item The item.
   4.482 +    /// \param value The priority.
   4.483 +    /// \pre \e item must be stored in the heap with priority at most \e value.
   4.484      void increase (Item item, const Prio& value) {
   4.485        erase(item);
   4.486        push(item,value);
   4.487      }
   4.488  
   4.489 -    /// \brief Returns if \c item is in, has already been in, or has never
   4.490 -    /// been in the heap.
   4.491 +    /// \brief Return the state of an item.
   4.492      ///
   4.493 -    /// This method returns PRE_HEAP if \c item has never been in the
   4.494 -    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   4.495 -    /// otherwise. In the latter case it is possible that \c item will
   4.496 -    /// get back to the heap again.
   4.497 +    /// This method returns \c PRE_HEAP if the given item has never
   4.498 +    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   4.499 +    /// and \c POST_HEAP otherwise.
   4.500 +    /// In the latter case it is possible that the item will get back
   4.501 +    /// to the heap again.
   4.502 +    /// \param item The item.
   4.503      State state(const Item &item) const {
   4.504 -      int i=iimap[item];
   4.505 +      int i=_iim[item];
   4.506        if( i>=0 ) {
   4.507 -        if( container[i].in ) i=0;
   4.508 +        if( _data[i].in ) i=0;
   4.509          else i=-2;
   4.510        }
   4.511        return State(i);
   4.512      }
   4.513  
   4.514 -    /// \brief Sets the state of the \c item in the heap.
   4.515 +    /// \brief Set the state of an item in the heap.
   4.516      ///
   4.517 -    /// Sets the state of the \c item in the heap. It can be used to
   4.518 -    /// manually clear the heap when it is important to achive the
   4.519 -    /// better time complexity.
   4.520 +    /// This function sets the state of the given item in the heap.
   4.521 +    /// It can be used to manually clear the heap when it is important
   4.522 +    /// to achive better time complexity.
   4.523      /// \param i The item.
   4.524      /// \param st The state. It should not be \c IN_HEAP.
   4.525      void state(const Item& i, State st) {
   4.526 @@ -348,7 +357,7 @@
   4.527        case POST_HEAP:
   4.528        case PRE_HEAP:
   4.529          if (state(i) == IN_HEAP) erase(i);
   4.530 -        iimap[i]=st;
   4.531 +        _iim[i]=st;
   4.532          break;
   4.533        case IN_HEAP:
   4.534          break;
   4.535 @@ -359,95 +368,95 @@
   4.536  
   4.537      void cut(int a, int b) {
   4.538        int child_a;
   4.539 -      switch (container[a].degree) {
   4.540 +      switch (_data[a].degree) {
   4.541          case 2:
   4.542 -          child_a = container[container[a].child].parent;
   4.543 -          if( container[a].left_child ) {
   4.544 -            container[child_a].left_child=true;
   4.545 -            container[b].child=child_a;
   4.546 -            container[child_a].parent=container[a].parent;
   4.547 +          child_a = _data[_data[a].child].parent;
   4.548 +          if( _data[a].left_child ) {
   4.549 +            _data[child_a].left_child=true;
   4.550 +            _data[b].child=child_a;
   4.551 +            _data[child_a].parent=_data[a].parent;
   4.552            }
   4.553            else {
   4.554 -            container[child_a].left_child=false;
   4.555 -            container[child_a].parent=b;
   4.556 -            if( a!=container[b].child )
   4.557 -              container[container[b].child].parent=child_a;
   4.558 +            _data[child_a].left_child=false;
   4.559 +            _data[child_a].parent=b;
   4.560 +            if( a!=_data[b].child )
   4.561 +              _data[_data[b].child].parent=child_a;
   4.562              else
   4.563 -              container[b].child=child_a;
   4.564 +              _data[b].child=child_a;
   4.565            }
   4.566 -          --container[a].degree;
   4.567 -          container[container[a].child].parent=a;
   4.568 +          --_data[a].degree;
   4.569 +          _data[_data[a].child].parent=a;
   4.570            break;
   4.571  
   4.572          case 1:
   4.573 -          child_a = container[a].child;
   4.574 -          if( !container[child_a].left_child ) {
   4.575 -            --container[a].degree;
   4.576 -            if( container[a].left_child ) {
   4.577 -              container[child_a].left_child=true;
   4.578 -              container[child_a].parent=container[a].parent;
   4.579 -              container[b].child=child_a;
   4.580 +          child_a = _data[a].child;
   4.581 +          if( !_data[child_a].left_child ) {
   4.582 +            --_data[a].degree;
   4.583 +            if( _data[a].left_child ) {
   4.584 +              _data[child_a].left_child=true;
   4.585 +              _data[child_a].parent=_data[a].parent;
   4.586 +              _data[b].child=child_a;
   4.587              }
   4.588              else {
   4.589 -              container[child_a].left_child=false;
   4.590 -              container[child_a].parent=b;
   4.591 -              if( a!=container[b].child )
   4.592 -                container[container[b].child].parent=child_a;
   4.593 +              _data[child_a].left_child=false;
   4.594 +              _data[child_a].parent=b;
   4.595 +              if( a!=_data[b].child )
   4.596 +                _data[_data[b].child].parent=child_a;
   4.597                else
   4.598 -                container[b].child=child_a;
   4.599 +                _data[b].child=child_a;
   4.600              }
   4.601 -            container[a].child=-1;
   4.602 +            _data[a].child=-1;
   4.603            }
   4.604            else {
   4.605 -            --container[b].degree;
   4.606 -            if( container[a].left_child ) {
   4.607 -              container[b].child =
   4.608 -                (1==container[b].degree) ? container[a].parent : -1;
   4.609 +            --_data[b].degree;
   4.610 +            if( _data[a].left_child ) {
   4.611 +              _data[b].child =
   4.612 +                (1==_data[b].degree) ? _data[a].parent : -1;
   4.613              } else {
   4.614 -              if (1==container[b].degree)
   4.615 -                container[container[b].child].parent=b;
   4.616 +              if (1==_data[b].degree)
   4.617 +                _data[_data[b].child].parent=b;
   4.618                else
   4.619 -                container[b].child=-1;
   4.620 +                _data[b].child=-1;
   4.621              }
   4.622            }
   4.623            break;
   4.624  
   4.625          case 0:
   4.626 -          --container[b].degree;
   4.627 -          if( container[a].left_child ) {
   4.628 -            container[b].child =
   4.629 -              (0!=container[b].degree) ? container[a].parent : -1;
   4.630 +          --_data[b].degree;
   4.631 +          if( _data[a].left_child ) {
   4.632 +            _data[b].child =
   4.633 +              (0!=_data[b].degree) ? _data[a].parent : -1;
   4.634            } else {
   4.635 -            if( 0!=container[b].degree )
   4.636 -              container[container[b].child].parent=b;
   4.637 +            if( 0!=_data[b].degree )
   4.638 +              _data[_data[b].child].parent=b;
   4.639              else
   4.640 -              container[b].child=-1;
   4.641 +              _data[b].child=-1;
   4.642            }
   4.643            break;
   4.644        }
   4.645 -      container[a].parent=-1;
   4.646 -      container[a].left_child=false;
   4.647 +      _data[a].parent=-1;
   4.648 +      _data[a].left_child=false;
   4.649      }
   4.650  
   4.651      void fuse(int a, int b) {
   4.652 -      int child_a = container[a].child;
   4.653 -      int child_b = container[b].child;
   4.654 -      container[a].child=b;
   4.655 -      container[b].parent=a;
   4.656 -      container[b].left_child=true;
   4.657 +      int child_a = _data[a].child;
   4.658 +      int child_b = _data[b].child;
   4.659 +      _data[a].child=b;
   4.660 +      _data[b].parent=a;
   4.661 +      _data[b].left_child=true;
   4.662  
   4.663        if( -1!=child_a ) {
   4.664 -        container[b].child=child_a;
   4.665 -        container[child_a].parent=b;
   4.666 -        container[child_a].left_child=false;
   4.667 -        ++container[b].degree;
   4.668 +        _data[b].child=child_a;
   4.669 +        _data[child_a].parent=b;
   4.670 +        _data[child_a].left_child=false;
   4.671 +        ++_data[b].degree;
   4.672  
   4.673          if( -1!=child_b ) {
   4.674 -           container[b].child=child_b;
   4.675 -           container[child_b].parent=child_a;
   4.676 +           _data[b].child=child_b;
   4.677 +           _data[child_b].parent=child_a;
   4.678          }
   4.679        }
   4.680 -      else { ++container[a].degree; }
   4.681 +      else { ++_data[a].degree; }
   4.682      }
   4.683  
   4.684      class store {