Merge #301
authorAlpar Juttner <alpar@cs.elte.hu>
Wed, 03 Mar 2010 17:22:13 +0000
changeset 859ac5f72c48367
parent 858 9f6ed854d409
parent 855 65a0521e744e
child 861 ab21ca093745
Merge #301
lemon/Makefile.am
lemon/binom_heap.h
lemon/fourary_heap.h
lemon/kary_heap.h
     1.1 --- a/lemon/Makefile.am	Tue Mar 02 10:27:47 2010 +0100
     1.2 +++ b/lemon/Makefile.am	Wed Mar 03 17:22:13 2010 +0000
     1.3 @@ -60,7 +60,7 @@
     1.4  	lemon/bellman_ford.h \
     1.5  	lemon/bfs.h \
     1.6  	lemon/bin_heap.h \
     1.7 -	lemon/binom_heap.h \
     1.8 +	lemon/binomial_heap.h \
     1.9  	lemon/bucket_heap.h \
    1.10  	lemon/capacity_scaling.h \
    1.11  	lemon/cbc.h \
    1.12 @@ -75,6 +75,7 @@
    1.13  	lemon/cplex.h \
    1.14  	lemon/cycle_canceling.h \
    1.15  	lemon/dfs.h \
    1.16 +	lemon/dheap.h \
    1.17  	lemon/dijkstra.h \
    1.18  	lemon/dim2.h \
    1.19  	lemon/dimacs.h \
    1.20 @@ -83,7 +84,6 @@
    1.21  	lemon/error.h \
    1.22  	lemon/euler.h \
    1.23  	lemon/fib_heap.h \
    1.24 -	lemon/fourary_heap.h \
    1.25  	lemon/full_graph.h \
    1.26  	lemon/glpk.h \
    1.27  	lemon/gomory_hu.h \
    1.28 @@ -93,7 +93,6 @@
    1.29  	lemon/howard.h \
    1.30  	lemon/hypercube_graph.h \
    1.31  	lemon/karp.h \
    1.32 -	lemon/kary_heap.h \
    1.33  	lemon/kruskal.h \
    1.34  	lemon/hao_orlin.h \
    1.35  	lemon/lgf_reader.h \
    1.36 @@ -112,6 +111,7 @@
    1.37  	lemon/path.h \
    1.38  	lemon/planarity.h \
    1.39  	lemon/preflow.h \
    1.40 +	lemon/quad_heap.h \
    1.41  	lemon/radix_heap.h \
    1.42  	lemon/radix_sort.h \
    1.43  	lemon/random.h \
     2.1 --- a/lemon/binom_heap.h	Tue Mar 02 10:27:47 2010 +0100
     2.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.3 @@ -1,445 +0,0 @@
     2.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2.5 - *
     2.6 - * This file is a part of LEMON, a generic C++ optimization library.
     2.7 - *
     2.8 - * Copyright (C) 2003-2009
     2.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    2.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
    2.11 - *
    2.12 - * Permission to use, modify and distribute this software is granted
    2.13 - * provided that this copyright notice appears in all copies. For
    2.14 - * precise terms see the accompanying LICENSE file.
    2.15 - *
    2.16 - * This software is provided "AS IS" with no warranty of any kind,
    2.17 - * express or implied, and with no claim as to its suitability for any
    2.18 - * purpose.
    2.19 - *
    2.20 - */
    2.21 -
    2.22 -#ifndef LEMON_BINOM_HEAP_H
    2.23 -#define LEMON_BINOM_HEAP_H
    2.24 -
    2.25 -///\file
    2.26 -///\ingroup heaps
    2.27 -///\brief Binomial Heap implementation.
    2.28 -
    2.29 -#include <vector>
    2.30 -#include <utility>
    2.31 -#include <functional>
    2.32 -#include <lemon/math.h>
    2.33 -#include <lemon/counter.h>
    2.34 -
    2.35 -namespace lemon {
    2.36 -
    2.37 -  /// \ingroup heaps
    2.38 -  ///
    2.39 -  ///\brief Binomial heap data structure.
    2.40 -  ///
    2.41 -  /// This class implements the \e binomial \e heap data structure.
    2.42 -  /// It fully conforms to the \ref concepts::Heap "heap concept".
    2.43 -  ///
    2.44 -  /// The methods \ref increase() and \ref erase() are not efficient
    2.45 -  /// in a binomial heap. In case of many calls of these operations,
    2.46 -  /// it is better to use other heap structure, e.g. \ref BinHeap
    2.47 -  /// "binary heap".
    2.48 -  ///
    2.49 -  /// \tparam PR Type of the priorities of the items.
    2.50 -  /// \tparam IM A read-writable item map with \c int values, used
    2.51 -  /// internally to handle the cross references.
    2.52 -  /// \tparam CMP A functor class for comparing the priorities.
    2.53 -  /// The default is \c std::less<PR>.
    2.54 -#ifdef DOXYGEN
    2.55 -  template <typename PR, typename IM, typename CMP>
    2.56 -#else
    2.57 -  template <typename PR, typename IM, typename CMP = std::less<PR> >
    2.58 -#endif
    2.59 -  class BinomHeap {
    2.60 -  public:
    2.61 -    /// Type of the item-int map.
    2.62 -    typedef IM ItemIntMap;
    2.63 -    /// Type of the priorities.
    2.64 -    typedef PR Prio;
    2.65 -    /// Type of the items stored in the heap.
    2.66 -    typedef typename ItemIntMap::Key Item;
    2.67 -    /// Functor type for comparing the priorities.
    2.68 -    typedef CMP Compare;
    2.69 -
    2.70 -    /// \brief Type to represent the states of the items.
    2.71 -    ///
    2.72 -    /// Each item has a state associated to it. It can be "in heap",
    2.73 -    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    2.74 -    /// heap's point of view, but may be useful to the user.
    2.75 -    ///
    2.76 -    /// The item-int map must be initialized in such way that it assigns
    2.77 -    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    2.78 -    enum State {
    2.79 -      IN_HEAP = 0,    ///< = 0.
    2.80 -      PRE_HEAP = -1,  ///< = -1.
    2.81 -      POST_HEAP = -2  ///< = -2.
    2.82 -    };
    2.83 -
    2.84 -  private:
    2.85 -    class Store;
    2.86 -
    2.87 -    std::vector<Store> _data;
    2.88 -    int _min, _head;
    2.89 -    ItemIntMap &_iim;
    2.90 -    Compare _comp;
    2.91 -    int _num_items;
    2.92 -
    2.93 -  public:
    2.94 -    /// \brief Constructor.
    2.95 -    ///
    2.96 -    /// Constructor.
    2.97 -    /// \param map A map that assigns \c int values to the items.
    2.98 -    /// It is used internally to handle the cross references.
    2.99 -    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   2.100 -    explicit BinomHeap(ItemIntMap &map)
   2.101 -      : _min(0), _head(-1), _iim(map), _num_items(0) {}
   2.102 -
   2.103 -    /// \brief Constructor.
   2.104 -    ///
   2.105 -    /// Constructor.
   2.106 -    /// \param map A map that assigns \c int values to the items.
   2.107 -    /// It is used internally to handle the cross references.
   2.108 -    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   2.109 -    /// \param comp The function object used for comparing the priorities.
   2.110 -    BinomHeap(ItemIntMap &map, const Compare &comp)
   2.111 -      : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
   2.112 -
   2.113 -    /// \brief The number of items stored in the heap.
   2.114 -    ///
   2.115 -    /// This function returns the number of items stored in the heap.
   2.116 -    int size() const { return _num_items; }
   2.117 -
   2.118 -    /// \brief Check if the heap is empty.
   2.119 -    ///
   2.120 -    /// This function returns \c true if the heap is empty.
   2.121 -    bool empty() const { return _num_items==0; }
   2.122 -
   2.123 -    /// \brief Make the heap empty.
   2.124 -    ///
   2.125 -    /// This functon makes the heap empty.
   2.126 -    /// It does not change the cross reference map. If you want to reuse
   2.127 -    /// a heap that is not surely empty, you should first clear it and
   2.128 -    /// then you should set the cross reference map to \c PRE_HEAP
   2.129 -    /// for each item.
   2.130 -    void clear() {
   2.131 -      _data.clear(); _min=0; _num_items=0; _head=-1;
   2.132 -    }
   2.133 -
   2.134 -    /// \brief Set the priority of an item or insert it, if it is
   2.135 -    /// not stored in the heap.
   2.136 -    ///
   2.137 -    /// This method sets the priority of the given item if it is
   2.138 -    /// already stored in the heap. Otherwise it inserts the given
   2.139 -    /// item into the heap with the given priority.
   2.140 -    /// \param item The item.
   2.141 -    /// \param value The priority.
   2.142 -    void set (const Item& item, const Prio& value) {
   2.143 -      int i=_iim[item];
   2.144 -      if ( i >= 0 && _data[i].in ) {
   2.145 -        if ( _comp(value, _data[i].prio) ) decrease(item, value);
   2.146 -        if ( _comp(_data[i].prio, value) ) increase(item, value);
   2.147 -      } else push(item, value);
   2.148 -    }
   2.149 -
   2.150 -    /// \brief Insert an item into the heap with the given priority.
   2.151 -    ///
   2.152 -    /// This function inserts the given item into the heap with the
   2.153 -    /// given priority.
   2.154 -    /// \param item The item to insert.
   2.155 -    /// \param value The priority of the item.
   2.156 -    /// \pre \e item must not be stored in the heap.
   2.157 -    void push (const Item& item, const Prio& value) {
   2.158 -      int i=_iim[item];
   2.159 -      if ( i<0 ) {
   2.160 -        int s=_data.size();
   2.161 -        _iim.set( item,s );
   2.162 -        Store st;
   2.163 -        st.name=item;
   2.164 -        st.prio=value;
   2.165 -        _data.push_back(st);
   2.166 -        i=s;
   2.167 -      }
   2.168 -      else {
   2.169 -        _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
   2.170 -        _data[i].degree=0;
   2.171 -        _data[i].in=true;
   2.172 -        _data[i].prio=value;
   2.173 -      }
   2.174 -
   2.175 -      if( 0==_num_items ) {
   2.176 -        _head=i;
   2.177 -        _min=i;
   2.178 -      } else {
   2.179 -        merge(i);
   2.180 -        if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
   2.181 -      }
   2.182 -      ++_num_items;
   2.183 -    }
   2.184 -
   2.185 -    /// \brief Return the item having minimum priority.
   2.186 -    ///
   2.187 -    /// This function returns the item having minimum priority.
   2.188 -    /// \pre The heap must be non-empty.
   2.189 -    Item top() const { return _data[_min].name; }
   2.190 -
   2.191 -    /// \brief The minimum priority.
   2.192 -    ///
   2.193 -    /// This function returns the minimum priority.
   2.194 -    /// \pre The heap must be non-empty.
   2.195 -    Prio prio() const { return _data[_min].prio; }
   2.196 -
   2.197 -    /// \brief The priority of the given item.
   2.198 -    ///
   2.199 -    /// This function returns the priority of the given item.
   2.200 -    /// \param item The item.
   2.201 -    /// \pre \e item must be in the heap.
   2.202 -    const Prio& operator[](const Item& item) const {
   2.203 -      return _data[_iim[item]].prio;
   2.204 -    }
   2.205 -
   2.206 -    /// \brief Remove the item having minimum priority.
   2.207 -    ///
   2.208 -    /// This function removes the item having minimum priority.
   2.209 -    /// \pre The heap must be non-empty.
   2.210 -    void pop() {
   2.211 -      _data[_min].in=false;
   2.212 -
   2.213 -      int head_child=-1;
   2.214 -      if ( _data[_min].child!=-1 ) {
   2.215 -        int child=_data[_min].child;
   2.216 -        int neighb;
   2.217 -        while( child!=-1 ) {
   2.218 -          neighb=_data[child].right_neighbor;
   2.219 -          _data[child].parent=-1;
   2.220 -          _data[child].right_neighbor=head_child;
   2.221 -          head_child=child;
   2.222 -          child=neighb;
   2.223 -        }
   2.224 -      }
   2.225 -
   2.226 -      if ( _data[_head].right_neighbor==-1 ) {
   2.227 -        // there was only one root
   2.228 -        _head=head_child;
   2.229 -      }
   2.230 -      else {
   2.231 -        // there were more roots
   2.232 -        if( _head!=_min )  { unlace(_min); }
   2.233 -        else { _head=_data[_head].right_neighbor; }
   2.234 -        merge(head_child);
   2.235 -      }
   2.236 -      _min=findMin();
   2.237 -      --_num_items;
   2.238 -    }
   2.239 -
   2.240 -    /// \brief Remove the given item from the heap.
   2.241 -    ///
   2.242 -    /// This function removes the given item from the heap if it is
   2.243 -    /// already stored.
   2.244 -    /// \param item The item to delete.
   2.245 -    /// \pre \e item must be in the heap.
   2.246 -    void erase (const Item& item) {
   2.247 -      int i=_iim[item];
   2.248 -      if ( i >= 0 && _data[i].in ) {
   2.249 -        decrease( item, _data[_min].prio-1 );
   2.250 -        pop();
   2.251 -      }
   2.252 -    }
   2.253 -
   2.254 -    /// \brief Decrease the priority of an item to the given value.
   2.255 -    ///
   2.256 -    /// This function decreases the priority of an item to the given value.
   2.257 -    /// \param item The item.
   2.258 -    /// \param value The priority.
   2.259 -    /// \pre \e item must be stored in the heap with priority at least \e value.
   2.260 -    void decrease (Item item, const Prio& value) {
   2.261 -      int i=_iim[item];
   2.262 -      int p=_data[i].parent;
   2.263 -      _data[i].prio=value;
   2.264 -      
   2.265 -      while( p!=-1 && _comp(value, _data[p].prio) ) {
   2.266 -        _data[i].name=_data[p].name;
   2.267 -        _data[i].prio=_data[p].prio;
   2.268 -        _data[p].name=item;
   2.269 -        _data[p].prio=value;
   2.270 -        _iim[_data[i].name]=i;
   2.271 -        i=p;
   2.272 -        p=_data[p].parent;
   2.273 -      }
   2.274 -      _iim[item]=i;
   2.275 -      if ( _comp(value, _data[_min].prio) ) _min=i;
   2.276 -    }
   2.277 -
   2.278 -    /// \brief Increase the priority of an item to the given value.
   2.279 -    ///
   2.280 -    /// This function increases the priority of an item to the given value.
   2.281 -    /// \param item The item.
   2.282 -    /// \param value The priority.
   2.283 -    /// \pre \e item must be stored in the heap with priority at most \e value.
   2.284 -    void increase (Item item, const Prio& value) {
   2.285 -      erase(item);
   2.286 -      push(item, value);
   2.287 -    }
   2.288 -
   2.289 -    /// \brief Return the state of an item.
   2.290 -    ///
   2.291 -    /// This method returns \c PRE_HEAP if the given item has never
   2.292 -    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   2.293 -    /// and \c POST_HEAP otherwise.
   2.294 -    /// In the latter case it is possible that the item will get back
   2.295 -    /// to the heap again.
   2.296 -    /// \param item The item.
   2.297 -    State state(const Item &item) const {
   2.298 -      int i=_iim[item];
   2.299 -      if( i>=0 ) {
   2.300 -        if ( _data[i].in ) i=0;
   2.301 -        else i=-2;
   2.302 -      }
   2.303 -      return State(i);
   2.304 -    }
   2.305 -
   2.306 -    /// \brief Set the state of an item in the heap.
   2.307 -    ///
   2.308 -    /// This function sets the state of the given item in the heap.
   2.309 -    /// It can be used to manually clear the heap when it is important
   2.310 -    /// to achive better time complexity.
   2.311 -    /// \param i The item.
   2.312 -    /// \param st The state. It should not be \c IN_HEAP.
   2.313 -    void state(const Item& i, State st) {
   2.314 -      switch (st) {
   2.315 -      case POST_HEAP:
   2.316 -      case PRE_HEAP:
   2.317 -        if (state(i) == IN_HEAP) {
   2.318 -          erase(i);
   2.319 -        }
   2.320 -        _iim[i] = st;
   2.321 -        break;
   2.322 -      case IN_HEAP:
   2.323 -        break;
   2.324 -      }
   2.325 -    }
   2.326 -
   2.327 -  private:
   2.328 -    
   2.329 -    // Find the minimum of the roots
   2.330 -    int findMin() {
   2.331 -      if( _head!=-1 ) {
   2.332 -        int min_loc=_head, min_val=_data[_head].prio;
   2.333 -        for( int x=_data[_head].right_neighbor; x!=-1;
   2.334 -             x=_data[x].right_neighbor ) {
   2.335 -          if( _comp( _data[x].prio,min_val ) ) {
   2.336 -            min_val=_data[x].prio;
   2.337 -            min_loc=x;
   2.338 -          }
   2.339 -        }
   2.340 -        return min_loc;
   2.341 -      }
   2.342 -      else return -1;
   2.343 -    }
   2.344 -
   2.345 -    // Merge the heap with another heap starting at the given position
   2.346 -    void merge(int a) {
   2.347 -      if( _head==-1 || a==-1 ) return;
   2.348 -      if( _data[a].right_neighbor==-1 &&
   2.349 -          _data[a].degree<=_data[_head].degree ) {
   2.350 -        _data[a].right_neighbor=_head;
   2.351 -        _head=a;
   2.352 -      } else {
   2.353 -        interleave(a);
   2.354 -      }
   2.355 -      if( _data[_head].right_neighbor==-1 ) return;
   2.356 -      
   2.357 -      int x=_head;
   2.358 -      int x_prev=-1, x_next=_data[x].right_neighbor;
   2.359 -      while( x_next!=-1 ) {
   2.360 -        if( _data[x].degree!=_data[x_next].degree ||
   2.361 -            ( _data[x_next].right_neighbor!=-1 &&
   2.362 -              _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
   2.363 -          x_prev=x;
   2.364 -          x=x_next;
   2.365 -        }
   2.366 -        else {
   2.367 -          if( _comp(_data[x_next].prio,_data[x].prio) ) {
   2.368 -            if( x_prev==-1 ) {
   2.369 -              _head=x_next;
   2.370 -            } else {
   2.371 -              _data[x_prev].right_neighbor=x_next;
   2.372 -            }
   2.373 -            fuse(x,x_next);
   2.374 -            x=x_next;
   2.375 -          }
   2.376 -          else {
   2.377 -            _data[x].right_neighbor=_data[x_next].right_neighbor;
   2.378 -            fuse(x_next,x);
   2.379 -          }
   2.380 -        }
   2.381 -        x_next=_data[x].right_neighbor;
   2.382 -      }
   2.383 -    }
   2.384 -
   2.385 -    // Interleave the elements of the given list into the list of the roots
   2.386 -    void interleave(int a) {
   2.387 -      int p=_head, q=a;
   2.388 -      int curr=_data.size();
   2.389 -      _data.push_back(Store());
   2.390 -      
   2.391 -      while( p!=-1 || q!=-1 ) {
   2.392 -        if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
   2.393 -          _data[curr].right_neighbor=p;
   2.394 -          curr=p;
   2.395 -          p=_data[p].right_neighbor;
   2.396 -        }
   2.397 -        else {
   2.398 -          _data[curr].right_neighbor=q;
   2.399 -          curr=q;
   2.400 -          q=_data[q].right_neighbor;
   2.401 -        }
   2.402 -      }
   2.403 -      
   2.404 -      _head=_data.back().right_neighbor;
   2.405 -      _data.pop_back();
   2.406 -    }
   2.407 -
   2.408 -    // Lace node a under node b
   2.409 -    void fuse(int a, int b) {
   2.410 -      _data[a].parent=b;
   2.411 -      _data[a].right_neighbor=_data[b].child;
   2.412 -      _data[b].child=a;
   2.413 -
   2.414 -      ++_data[b].degree;
   2.415 -    }
   2.416 -
   2.417 -    // Unlace node a (if it has siblings)
   2.418 -    void unlace(int a) {
   2.419 -      int neighb=_data[a].right_neighbor;
   2.420 -      int other=_head;
   2.421 -
   2.422 -      while( _data[other].right_neighbor!=a )
   2.423 -        other=_data[other].right_neighbor;
   2.424 -      _data[other].right_neighbor=neighb;
   2.425 -    }
   2.426 -
   2.427 -  private:
   2.428 -
   2.429 -    class Store {
   2.430 -      friend class BinomHeap;
   2.431 -
   2.432 -      Item name;
   2.433 -      int parent;
   2.434 -      int right_neighbor;
   2.435 -      int child;
   2.436 -      int degree;
   2.437 -      bool in;
   2.438 -      Prio prio;
   2.439 -
   2.440 -      Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
   2.441 -        in(true) {}
   2.442 -    };
   2.443 -  };
   2.444 -
   2.445 -} //namespace lemon
   2.446 -
   2.447 -#endif //LEMON_BINOM_HEAP_H
   2.448 -
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/lemon/binomial_heap.h	Wed Mar 03 17:22:13 2010 +0000
     3.3 @@ -0,0 +1,445 @@
     3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     3.5 + *
     3.6 + * This file is a part of LEMON, a generic C++ optimization library.
     3.7 + *
     3.8 + * Copyright (C) 2003-2009
     3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    3.11 + *
    3.12 + * Permission to use, modify and distribute this software is granted
    3.13 + * provided that this copyright notice appears in all copies. For
    3.14 + * precise terms see the accompanying LICENSE file.
    3.15 + *
    3.16 + * This software is provided "AS IS" with no warranty of any kind,
    3.17 + * express or implied, and with no claim as to its suitability for any
    3.18 + * purpose.
    3.19 + *
    3.20 + */
    3.21 +
    3.22 +#ifndef LEMON_BINOMIAL_HEAP_H
    3.23 +#define LEMON_BINOMIAL_HEAP_H
    3.24 +
    3.25 +///\file
    3.26 +///\ingroup heaps
    3.27 +///\brief Binomial Heap implementation.
    3.28 +
    3.29 +#include <vector>
    3.30 +#include <utility>
    3.31 +#include <functional>
    3.32 +#include <lemon/math.h>
    3.33 +#include <lemon/counter.h>
    3.34 +
    3.35 +namespace lemon {
    3.36 +
    3.37 +  /// \ingroup heaps
    3.38 +  ///
    3.39 +  ///\brief Binomial heap data structure.
    3.40 +  ///
    3.41 +  /// This class implements the \e binomial \e heap data structure.
    3.42 +  /// It fully conforms to the \ref concepts::Heap "heap concept".
    3.43 +  ///
    3.44 +  /// The methods \ref increase() and \ref erase() are not efficient
    3.45 +  /// in a binomial heap. In case of many calls of these operations,
    3.46 +  /// it is better to use other heap structure, e.g. \ref BinHeap
    3.47 +  /// "binary heap".
    3.48 +  ///
    3.49 +  /// \tparam PR Type of the priorities of the items.
    3.50 +  /// \tparam IM A read-writable item map with \c int values, used
    3.51 +  /// internally to handle the cross references.
    3.52 +  /// \tparam CMP A functor class for comparing the priorities.
    3.53 +  /// The default is \c std::less<PR>.
    3.54 +#ifdef DOXYGEN
    3.55 +  template <typename PR, typename IM, typename CMP>
    3.56 +#else
    3.57 +  template <typename PR, typename IM, typename CMP = std::less<PR> >
    3.58 +#endif
    3.59 +  class BinomialHeap {
    3.60 +  public:
    3.61 +    /// Type of the item-int map.
    3.62 +    typedef IM ItemIntMap;
    3.63 +    /// Type of the priorities.
    3.64 +    typedef PR Prio;
    3.65 +    /// Type of the items stored in the heap.
    3.66 +    typedef typename ItemIntMap::Key Item;
    3.67 +    /// Functor type for comparing the priorities.
    3.68 +    typedef CMP Compare;
    3.69 +
    3.70 +    /// \brief Type to represent the states of the items.
    3.71 +    ///
    3.72 +    /// Each item has a state associated to it. It can be "in heap",
    3.73 +    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    3.74 +    /// heap's point of view, but may be useful to the user.
    3.75 +    ///
    3.76 +    /// The item-int map must be initialized in such way that it assigns
    3.77 +    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    3.78 +    enum State {
    3.79 +      IN_HEAP = 0,    ///< = 0.
    3.80 +      PRE_HEAP = -1,  ///< = -1.
    3.81 +      POST_HEAP = -2  ///< = -2.
    3.82 +    };
    3.83 +
    3.84 +  private:
    3.85 +    class Store;
    3.86 +
    3.87 +    std::vector<Store> _data;
    3.88 +    int _min, _head;
    3.89 +    ItemIntMap &_iim;
    3.90 +    Compare _comp;
    3.91 +    int _num_items;
    3.92 +
    3.93 +  public:
    3.94 +    /// \brief Constructor.
    3.95 +    ///
    3.96 +    /// Constructor.
    3.97 +    /// \param map A map that assigns \c int values to the items.
    3.98 +    /// It is used internally to handle the cross references.
    3.99 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   3.100 +    explicit BinomialHeap(ItemIntMap &map)
   3.101 +      : _min(0), _head(-1), _iim(map), _num_items(0) {}
   3.102 +
   3.103 +    /// \brief Constructor.
   3.104 +    ///
   3.105 +    /// Constructor.
   3.106 +    /// \param map A map that assigns \c int values to the items.
   3.107 +    /// It is used internally to handle the cross references.
   3.108 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   3.109 +    /// \param comp The function object used for comparing the priorities.
   3.110 +    BinomialHeap(ItemIntMap &map, const Compare &comp)
   3.111 +      : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
   3.112 +
   3.113 +    /// \brief The number of items stored in the heap.
   3.114 +    ///
   3.115 +    /// This function returns the number of items stored in the heap.
   3.116 +    int size() const { return _num_items; }
   3.117 +
   3.118 +    /// \brief Check if the heap is empty.
   3.119 +    ///
   3.120 +    /// This function returns \c true if the heap is empty.
   3.121 +    bool empty() const { return _num_items==0; }
   3.122 +
   3.123 +    /// \brief Make the heap empty.
   3.124 +    ///
   3.125 +    /// This functon makes the heap empty.
   3.126 +    /// It does not change the cross reference map. If you want to reuse
   3.127 +    /// a heap that is not surely empty, you should first clear it and
   3.128 +    /// then you should set the cross reference map to \c PRE_HEAP
   3.129 +    /// for each item.
   3.130 +    void clear() {
   3.131 +      _data.clear(); _min=0; _num_items=0; _head=-1;
   3.132 +    }
   3.133 +
   3.134 +    /// \brief Set the priority of an item or insert it, if it is
   3.135 +    /// not stored in the heap.
   3.136 +    ///
   3.137 +    /// This method sets the priority of the given item if it is
   3.138 +    /// already stored in the heap. Otherwise it inserts the given
   3.139 +    /// item into the heap with the given priority.
   3.140 +    /// \param item The item.
   3.141 +    /// \param value The priority.
   3.142 +    void set (const Item& item, const Prio& value) {
   3.143 +      int i=_iim[item];
   3.144 +      if ( i >= 0 && _data[i].in ) {
   3.145 +        if ( _comp(value, _data[i].prio) ) decrease(item, value);
   3.146 +        if ( _comp(_data[i].prio, value) ) increase(item, value);
   3.147 +      } else push(item, value);
   3.148 +    }
   3.149 +
   3.150 +    /// \brief Insert an item into the heap with the given priority.
   3.151 +    ///
   3.152 +    /// This function inserts the given item into the heap with the
   3.153 +    /// given priority.
   3.154 +    /// \param item The item to insert.
   3.155 +    /// \param value The priority of the item.
   3.156 +    /// \pre \e item must not be stored in the heap.
   3.157 +    void push (const Item& item, const Prio& value) {
   3.158 +      int i=_iim[item];
   3.159 +      if ( i<0 ) {
   3.160 +        int s=_data.size();
   3.161 +        _iim.set( item,s );
   3.162 +        Store st;
   3.163 +        st.name=item;
   3.164 +        st.prio=value;
   3.165 +        _data.push_back(st);
   3.166 +        i=s;
   3.167 +      }
   3.168 +      else {
   3.169 +        _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
   3.170 +        _data[i].degree=0;
   3.171 +        _data[i].in=true;
   3.172 +        _data[i].prio=value;
   3.173 +      }
   3.174 +
   3.175 +      if( 0==_num_items ) {
   3.176 +        _head=i;
   3.177 +        _min=i;
   3.178 +      } else {
   3.179 +        merge(i);
   3.180 +        if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
   3.181 +      }
   3.182 +      ++_num_items;
   3.183 +    }
   3.184 +
   3.185 +    /// \brief Return the item having minimum priority.
   3.186 +    ///
   3.187 +    /// This function returns the item having minimum priority.
   3.188 +    /// \pre The heap must be non-empty.
   3.189 +    Item top() const { return _data[_min].name; }
   3.190 +
   3.191 +    /// \brief The minimum priority.
   3.192 +    ///
   3.193 +    /// This function returns the minimum priority.
   3.194 +    /// \pre The heap must be non-empty.
   3.195 +    Prio prio() const { return _data[_min].prio; }
   3.196 +
   3.197 +    /// \brief The priority of the given item.
   3.198 +    ///
   3.199 +    /// This function returns the priority of the given item.
   3.200 +    /// \param item The item.
   3.201 +    /// \pre \e item must be in the heap.
   3.202 +    const Prio& operator[](const Item& item) const {
   3.203 +      return _data[_iim[item]].prio;
   3.204 +    }
   3.205 +
   3.206 +    /// \brief Remove the item having minimum priority.
   3.207 +    ///
   3.208 +    /// This function removes the item having minimum priority.
   3.209 +    /// \pre The heap must be non-empty.
   3.210 +    void pop() {
   3.211 +      _data[_min].in=false;
   3.212 +
   3.213 +      int head_child=-1;
   3.214 +      if ( _data[_min].child!=-1 ) {
   3.215 +        int child=_data[_min].child;
   3.216 +        int neighb;
   3.217 +        while( child!=-1 ) {
   3.218 +          neighb=_data[child].right_neighbor;
   3.219 +          _data[child].parent=-1;
   3.220 +          _data[child].right_neighbor=head_child;
   3.221 +          head_child=child;
   3.222 +          child=neighb;
   3.223 +        }
   3.224 +      }
   3.225 +
   3.226 +      if ( _data[_head].right_neighbor==-1 ) {
   3.227 +        // there was only one root
   3.228 +        _head=head_child;
   3.229 +      }
   3.230 +      else {
   3.231 +        // there were more roots
   3.232 +        if( _head!=_min )  { unlace(_min); }
   3.233 +        else { _head=_data[_head].right_neighbor; }
   3.234 +        merge(head_child);
   3.235 +      }
   3.236 +      _min=findMin();
   3.237 +      --_num_items;
   3.238 +    }
   3.239 +
   3.240 +    /// \brief Remove the given item from the heap.
   3.241 +    ///
   3.242 +    /// This function removes the given item from the heap if it is
   3.243 +    /// already stored.
   3.244 +    /// \param item The item to delete.
   3.245 +    /// \pre \e item must be in the heap.
   3.246 +    void erase (const Item& item) {
   3.247 +      int i=_iim[item];
   3.248 +      if ( i >= 0 && _data[i].in ) {
   3.249 +        decrease( item, _data[_min].prio-1 );
   3.250 +        pop();
   3.251 +      }
   3.252 +    }
   3.253 +
   3.254 +    /// \brief Decrease the priority of an item to the given value.
   3.255 +    ///
   3.256 +    /// This function decreases the priority of an item to the given value.
   3.257 +    /// \param item The item.
   3.258 +    /// \param value The priority.
   3.259 +    /// \pre \e item must be stored in the heap with priority at least \e value.
   3.260 +    void decrease (Item item, const Prio& value) {
   3.261 +      int i=_iim[item];
   3.262 +      int p=_data[i].parent;
   3.263 +      _data[i].prio=value;
   3.264 +      
   3.265 +      while( p!=-1 && _comp(value, _data[p].prio) ) {
   3.266 +        _data[i].name=_data[p].name;
   3.267 +        _data[i].prio=_data[p].prio;
   3.268 +        _data[p].name=item;
   3.269 +        _data[p].prio=value;
   3.270 +        _iim[_data[i].name]=i;
   3.271 +        i=p;
   3.272 +        p=_data[p].parent;
   3.273 +      }
   3.274 +      _iim[item]=i;
   3.275 +      if ( _comp(value, _data[_min].prio) ) _min=i;
   3.276 +    }
   3.277 +
   3.278 +    /// \brief Increase the priority of an item to the given value.
   3.279 +    ///
   3.280 +    /// This function increases the priority of an item to the given value.
   3.281 +    /// \param item The item.
   3.282 +    /// \param value The priority.
   3.283 +    /// \pre \e item must be stored in the heap with priority at most \e value.
   3.284 +    void increase (Item item, const Prio& value) {
   3.285 +      erase(item);
   3.286 +      push(item, value);
   3.287 +    }
   3.288 +
   3.289 +    /// \brief Return the state of an item.
   3.290 +    ///
   3.291 +    /// This method returns \c PRE_HEAP if the given item has never
   3.292 +    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   3.293 +    /// and \c POST_HEAP otherwise.
   3.294 +    /// In the latter case it is possible that the item will get back
   3.295 +    /// to the heap again.
   3.296 +    /// \param item The item.
   3.297 +    State state(const Item &item) const {
   3.298 +      int i=_iim[item];
   3.299 +      if( i>=0 ) {
   3.300 +        if ( _data[i].in ) i=0;
   3.301 +        else i=-2;
   3.302 +      }
   3.303 +      return State(i);
   3.304 +    }
   3.305 +
   3.306 +    /// \brief Set the state of an item in the heap.
   3.307 +    ///
   3.308 +    /// This function sets the state of the given item in the heap.
   3.309 +    /// It can be used to manually clear the heap when it is important
   3.310 +    /// to achive better time complexity.
   3.311 +    /// \param i The item.
   3.312 +    /// \param st The state. It should not be \c IN_HEAP.
   3.313 +    void state(const Item& i, State st) {
   3.314 +      switch (st) {
   3.315 +      case POST_HEAP:
   3.316 +      case PRE_HEAP:
   3.317 +        if (state(i) == IN_HEAP) {
   3.318 +          erase(i);
   3.319 +        }
   3.320 +        _iim[i] = st;
   3.321 +        break;
   3.322 +      case IN_HEAP:
   3.323 +        break;
   3.324 +      }
   3.325 +    }
   3.326 +
   3.327 +  private:
   3.328 +    
   3.329 +    // Find the minimum of the roots
   3.330 +    int findMin() {
   3.331 +      if( _head!=-1 ) {
   3.332 +        int min_loc=_head, min_val=_data[_head].prio;
   3.333 +        for( int x=_data[_head].right_neighbor; x!=-1;
   3.334 +             x=_data[x].right_neighbor ) {
   3.335 +          if( _comp( _data[x].prio,min_val ) ) {
   3.336 +            min_val=_data[x].prio;
   3.337 +            min_loc=x;
   3.338 +          }
   3.339 +        }
   3.340 +        return min_loc;
   3.341 +      }
   3.342 +      else return -1;
   3.343 +    }
   3.344 +
   3.345 +    // Merge the heap with another heap starting at the given position
   3.346 +    void merge(int a) {
   3.347 +      if( _head==-1 || a==-1 ) return;
   3.348 +      if( _data[a].right_neighbor==-1 &&
   3.349 +          _data[a].degree<=_data[_head].degree ) {
   3.350 +        _data[a].right_neighbor=_head;
   3.351 +        _head=a;
   3.352 +      } else {
   3.353 +        interleave(a);
   3.354 +      }
   3.355 +      if( _data[_head].right_neighbor==-1 ) return;
   3.356 +      
   3.357 +      int x=_head;
   3.358 +      int x_prev=-1, x_next=_data[x].right_neighbor;
   3.359 +      while( x_next!=-1 ) {
   3.360 +        if( _data[x].degree!=_data[x_next].degree ||
   3.361 +            ( _data[x_next].right_neighbor!=-1 &&
   3.362 +              _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
   3.363 +          x_prev=x;
   3.364 +          x=x_next;
   3.365 +        }
   3.366 +        else {
   3.367 +          if( _comp(_data[x_next].prio,_data[x].prio) ) {
   3.368 +            if( x_prev==-1 ) {
   3.369 +              _head=x_next;
   3.370 +            } else {
   3.371 +              _data[x_prev].right_neighbor=x_next;
   3.372 +            }
   3.373 +            fuse(x,x_next);
   3.374 +            x=x_next;
   3.375 +          }
   3.376 +          else {
   3.377 +            _data[x].right_neighbor=_data[x_next].right_neighbor;
   3.378 +            fuse(x_next,x);
   3.379 +          }
   3.380 +        }
   3.381 +        x_next=_data[x].right_neighbor;
   3.382 +      }
   3.383 +    }
   3.384 +
   3.385 +    // Interleave the elements of the given list into the list of the roots
   3.386 +    void interleave(int a) {
   3.387 +      int p=_head, q=a;
   3.388 +      int curr=_data.size();
   3.389 +      _data.push_back(Store());
   3.390 +      
   3.391 +      while( p!=-1 || q!=-1 ) {
   3.392 +        if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
   3.393 +          _data[curr].right_neighbor=p;
   3.394 +          curr=p;
   3.395 +          p=_data[p].right_neighbor;
   3.396 +        }
   3.397 +        else {
   3.398 +          _data[curr].right_neighbor=q;
   3.399 +          curr=q;
   3.400 +          q=_data[q].right_neighbor;
   3.401 +        }
   3.402 +      }
   3.403 +      
   3.404 +      _head=_data.back().right_neighbor;
   3.405 +      _data.pop_back();
   3.406 +    }
   3.407 +
   3.408 +    // Lace node a under node b
   3.409 +    void fuse(int a, int b) {
   3.410 +      _data[a].parent=b;
   3.411 +      _data[a].right_neighbor=_data[b].child;
   3.412 +      _data[b].child=a;
   3.413 +
   3.414 +      ++_data[b].degree;
   3.415 +    }
   3.416 +
   3.417 +    // Unlace node a (if it has siblings)
   3.418 +    void unlace(int a) {
   3.419 +      int neighb=_data[a].right_neighbor;
   3.420 +      int other=_head;
   3.421 +
   3.422 +      while( _data[other].right_neighbor!=a )
   3.423 +        other=_data[other].right_neighbor;
   3.424 +      _data[other].right_neighbor=neighb;
   3.425 +    }
   3.426 +
   3.427 +  private:
   3.428 +
   3.429 +    class Store {
   3.430 +      friend class BinomialHeap;
   3.431 +
   3.432 +      Item name;
   3.433 +      int parent;
   3.434 +      int right_neighbor;
   3.435 +      int child;
   3.436 +      int degree;
   3.437 +      bool in;
   3.438 +      Prio prio;
   3.439 +
   3.440 +      Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
   3.441 +        in(true) {}
   3.442 +    };
   3.443 +  };
   3.444 +
   3.445 +} //namespace lemon
   3.446 +
   3.447 +#endif //LEMON_BINOMIAL_HEAP_H
   3.448 +
     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/lemon/dheap.h	Wed Mar 03 17:22:13 2010 +0000
     4.3 @@ -0,0 +1,352 @@
     4.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     4.5 + *
     4.6 + * This file is a part of LEMON, a generic C++ optimization library.
     4.7 + *
     4.8 + * Copyright (C) 2003-2009
     4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    4.11 + *
    4.12 + * Permission to use, modify and distribute this software is granted
    4.13 + * provided that this copyright notice appears in all copies. For
    4.14 + * precise terms see the accompanying LICENSE file.
    4.15 + *
    4.16 + * This software is provided "AS IS" with no warranty of any kind,
    4.17 + * express or implied, and with no claim as to its suitability for any
    4.18 + * purpose.
    4.19 + *
    4.20 + */
    4.21 +
    4.22 +#ifndef LEMON_DHEAP_H
    4.23 +#define LEMON_DHEAP_H
    4.24 +
    4.25 +///\ingroup heaps
    4.26 +///\file
    4.27 +///\brief D-ary heap implementation.
    4.28 +
    4.29 +#include <vector>
    4.30 +#include <utility>
    4.31 +#include <functional>
    4.32 +
    4.33 +namespace lemon {
    4.34 +
    4.35 +  /// \ingroup heaps
    4.36 +  ///
    4.37 +  ///\brief D-ary heap data structure.
    4.38 +  ///
    4.39 +  /// This class implements the \e D-ary \e heap data structure.
    4.40 +  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4.41 +  ///
    4.42 +  /// The \ref DHeap "D-ary heap" is a generalization of the
    4.43 +  /// \ref BinHeap "binary heap" structure, its nodes have at most
    4.44 +  /// \c D children, instead of two.
    4.45 +  /// \ref BinHeap and \ref QuadHeap are specialized implementations
    4.46 +  /// of this structure for <tt>D=2</tt> and <tt>D=4</tt>, respectively.
    4.47 +  ///
    4.48 +  /// \tparam PR Type of the priorities of the items.
    4.49 +  /// \tparam IM A read-writable item map with \c int values, used
    4.50 +  /// internally to handle the cross references.
    4.51 +  /// \tparam D The degree of the heap, each node have at most \e D
    4.52 +  /// children. The default is 16. Powers of two are suggested to use
    4.53 +  /// so that the multiplications and divisions needed to traverse the
    4.54 +  /// nodes of the heap could be performed faster.
    4.55 +  /// \tparam CMP A functor class for comparing the priorities.
    4.56 +  /// The default is \c std::less<PR>.
    4.57 +  ///
    4.58 +  ///\sa BinHeap
    4.59 +  ///\sa FouraryHeap
    4.60 +#ifdef DOXYGEN
    4.61 +  template <typename PR, typename IM, int D, typename CMP>
    4.62 +#else
    4.63 +  template <typename PR, typename IM, int D = 16,
    4.64 +            typename CMP = std::less<PR> >
    4.65 +#endif
    4.66 +  class DHeap {
    4.67 +  public:
    4.68 +    /// Type of the item-int map.
    4.69 +    typedef IM ItemIntMap;
    4.70 +    /// Type of the priorities.
    4.71 +    typedef PR Prio;
    4.72 +    /// Type of the items stored in the heap.
    4.73 +    typedef typename ItemIntMap::Key Item;
    4.74 +    /// Type of the item-priority pairs.
    4.75 +    typedef std::pair<Item,Prio> Pair;
    4.76 +    /// Functor type for comparing the priorities.
    4.77 +    typedef CMP Compare;
    4.78 +
    4.79 +    /// \brief Type to represent the states of the items.
    4.80 +    ///
    4.81 +    /// Each item has a state associated to it. It can be "in heap",
    4.82 +    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    4.83 +    /// heap's point of view, but may be useful to the user.
    4.84 +    ///
    4.85 +    /// The item-int map must be initialized in such way that it assigns
    4.86 +    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    4.87 +    enum State {
    4.88 +      IN_HEAP = 0,    ///< = 0.
    4.89 +      PRE_HEAP = -1,  ///< = -1.
    4.90 +      POST_HEAP = -2  ///< = -2.
    4.91 +    };
    4.92 +
    4.93 +  private:
    4.94 +    std::vector<Pair> _data;
    4.95 +    Compare _comp;
    4.96 +    ItemIntMap &_iim;
    4.97 +
    4.98 +  public:
    4.99 +    /// \brief Constructor.
   4.100 +    ///
   4.101 +    /// Constructor.
   4.102 +    /// \param map A map that assigns \c int values to the items.
   4.103 +    /// It is used internally to handle the cross references.
   4.104 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   4.105 +    explicit DHeap(ItemIntMap &map) : _iim(map) {}
   4.106 +
   4.107 +    /// \brief Constructor.
   4.108 +    ///
   4.109 +    /// Constructor.
   4.110 +    /// \param map A map that assigns \c int values to the items.
   4.111 +    /// It is used internally to handle the cross references.
   4.112 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   4.113 +    /// \param comp The function object used for comparing the priorities.
   4.114 +    DHeap(ItemIntMap &map, const Compare &comp)
   4.115 +      : _iim(map), _comp(comp) {}
   4.116 +
   4.117 +    /// \brief The number of items stored in the heap.
   4.118 +    ///
   4.119 +    /// This function returns the number of items stored in the heap.
   4.120 +    int size() const { return _data.size(); }
   4.121 +
   4.122 +    /// \brief Check if the heap is empty.
   4.123 +    ///
   4.124 +    /// This function returns \c true if the heap is empty.
   4.125 +    bool empty() const { return _data.empty(); }
   4.126 +
   4.127 +    /// \brief Make the heap empty.
   4.128 +    ///
   4.129 +    /// This functon makes the heap empty.
   4.130 +    /// It does not change the cross reference map. If you want to reuse
   4.131 +    /// a heap that is not surely empty, you should first clear it and
   4.132 +    /// then you should set the cross reference map to \c PRE_HEAP
   4.133 +    /// for each item.
   4.134 +    void clear() { _data.clear(); }
   4.135 +
   4.136 +  private:
   4.137 +    int parent(int i) { return (i-1)/D; }
   4.138 +    int firstChild(int i) { return D*i+1; }
   4.139 +
   4.140 +    bool less(const Pair &p1, const Pair &p2) const {
   4.141 +      return _comp(p1.second, p2.second);
   4.142 +    }
   4.143 +
   4.144 +    void bubbleUp(int hole, Pair p) {
   4.145 +      int par = parent(hole);
   4.146 +      while( hole>0 && less(p,_data[par]) ) {
   4.147 +        move(_data[par],hole);
   4.148 +        hole = par;
   4.149 +        par = parent(hole);
   4.150 +      }
   4.151 +      move(p, hole);
   4.152 +    }
   4.153 +
   4.154 +    void bubbleDown(int hole, Pair p, int length) {
   4.155 +      if( length>1 ) {
   4.156 +        int child = firstChild(hole);
   4.157 +        while( child+D<=length ) {
   4.158 +          int min=child;
   4.159 +          for (int i=1; i<D; ++i) {
   4.160 +            if( less(_data[child+i], _data[min]) )
   4.161 +              min=child+i;
   4.162 +          }
   4.163 +          if( !less(_data[min], p) )
   4.164 +            goto ok;
   4.165 +          move(_data[min], hole);
   4.166 +          hole = min;
   4.167 +          child = firstChild(hole);
   4.168 +        }
   4.169 +        if ( child<length ) {
   4.170 +          int min = child;
   4.171 +          while (++child < length) {
   4.172 +            if( less(_data[child], _data[min]) )
   4.173 +              min=child;
   4.174 +          }
   4.175 +          if( less(_data[min], p) ) {
   4.176 +            move(_data[min], hole);
   4.177 +            hole = min;
   4.178 +          }
   4.179 +        }
   4.180 +      }
   4.181 +    ok:
   4.182 +      move(p, hole);
   4.183 +    }
   4.184 +
   4.185 +    void move(const Pair &p, int i) {
   4.186 +      _data[i] = p;
   4.187 +      _iim.set(p.first, i);
   4.188 +    }
   4.189 +
   4.190 +  public:
   4.191 +    /// \brief Insert a pair of item and priority into the heap.
   4.192 +    ///
   4.193 +    /// This function inserts \c p.first to the heap with priority
   4.194 +    /// \c p.second.
   4.195 +    /// \param p The pair to insert.
   4.196 +    /// \pre \c p.first must not be stored in the heap.
   4.197 +    void push(const Pair &p) {
   4.198 +      int n = _data.size();
   4.199 +      _data.resize(n+1);
   4.200 +      bubbleUp(n, p);
   4.201 +    }
   4.202 +
   4.203 +    /// \brief Insert an item into the heap with the given priority.
   4.204 +    ///
   4.205 +    /// This function inserts the given item into the heap with the
   4.206 +    /// given priority.
   4.207 +    /// \param i The item to insert.
   4.208 +    /// \param p The priority of the item.
   4.209 +    /// \pre \e i must not be stored in the heap.
   4.210 +    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
   4.211 +
   4.212 +    /// \brief Return the item having minimum priority.
   4.213 +    ///
   4.214 +    /// This function returns the item having minimum priority.
   4.215 +    /// \pre The heap must be non-empty.
   4.216 +    Item top() const { return _data[0].first; }
   4.217 +
   4.218 +    /// \brief The minimum priority.
   4.219 +    ///
   4.220 +    /// This function returns the minimum priority.
   4.221 +    /// \pre The heap must be non-empty.
   4.222 +    Prio prio() const { return _data[0].second; }
   4.223 +
   4.224 +    /// \brief Remove the item having minimum priority.
   4.225 +    ///
   4.226 +    /// This function removes the item having minimum priority.
   4.227 +    /// \pre The heap must be non-empty.
   4.228 +    void pop() {
   4.229 +      int n = _data.size()-1;
   4.230 +      _iim.set(_data[0].first, POST_HEAP);
   4.231 +      if (n>0) bubbleDown(0, _data[n], n);
   4.232 +      _data.pop_back();
   4.233 +    }
   4.234 +
   4.235 +    /// \brief Remove the given item from the heap.
   4.236 +    ///
   4.237 +    /// This function removes the given item from the heap if it is
   4.238 +    /// already stored.
   4.239 +    /// \param i The item to delete.
   4.240 +    /// \pre \e i must be in the heap.
   4.241 +    void erase(const Item &i) {
   4.242 +      int h = _iim[i];
   4.243 +      int n = _data.size()-1;
   4.244 +      _iim.set(_data[h].first, POST_HEAP);
   4.245 +      if( h<n ) {
   4.246 +        if( less(_data[parent(h)], _data[n]) )
   4.247 +          bubbleDown(h, _data[n], n);
   4.248 +        else
   4.249 +          bubbleUp(h, _data[n]);
   4.250 +      }
   4.251 +      _data.pop_back();
   4.252 +    }
   4.253 +
   4.254 +    /// \brief The priority of the given item.
   4.255 +    ///
   4.256 +    /// This function returns the priority of the given item.
   4.257 +    /// \param i The item.
   4.258 +    /// \pre \e i must be in the heap.
   4.259 +    Prio operator[](const Item &i) const {
   4.260 +      int idx = _iim[i];
   4.261 +      return _data[idx].second;
   4.262 +    }
   4.263 +
   4.264 +    /// \brief Set the priority of an item or insert it, if it is
   4.265 +    /// not stored in the heap.
   4.266 +    ///
   4.267 +    /// This method sets the priority of the given item if it is
   4.268 +    /// already stored in the heap. Otherwise it inserts the given
   4.269 +    /// item into the heap with the given priority.
   4.270 +    /// \param i The item.
   4.271 +    /// \param p The priority.
   4.272 +    void set(const Item &i, const Prio &p) {
   4.273 +      int idx = _iim[i];
   4.274 +      if( idx<0 )
   4.275 +        push(i,p);
   4.276 +      else if( _comp(p, _data[idx].second) )
   4.277 +        bubbleUp(idx, Pair(i,p));
   4.278 +      else
   4.279 +        bubbleDown(idx, Pair(i,p), _data.size());
   4.280 +    }
   4.281 +
   4.282 +    /// \brief Decrease the priority of an item to the given value.
   4.283 +    ///
   4.284 +    /// This function decreases the priority of an item to the given value.
   4.285 +    /// \param i The item.
   4.286 +    /// \param p The priority.
   4.287 +    /// \pre \e i must be stored in the heap with priority at least \e p.
   4.288 +    void decrease(const Item &i, const Prio &p) {
   4.289 +      int idx = _iim[i];
   4.290 +      bubbleUp(idx, Pair(i,p));
   4.291 +    }
   4.292 +
   4.293 +    /// \brief Increase the priority of an item to the given value.
   4.294 +    ///
   4.295 +    /// This function increases the priority of an item to the given value.
   4.296 +    /// \param i The item.
   4.297 +    /// \param p The priority.
   4.298 +    /// \pre \e i must be stored in the heap with priority at most \e p.
   4.299 +    void increase(const Item &i, const Prio &p) {
   4.300 +      int idx = _iim[i];
   4.301 +      bubbleDown(idx, Pair(i,p), _data.size());
   4.302 +    }
   4.303 +
   4.304 +    /// \brief Return the state of an item.
   4.305 +    ///
   4.306 +    /// This method returns \c PRE_HEAP if the given item has never
   4.307 +    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   4.308 +    /// and \c POST_HEAP otherwise.
   4.309 +    /// In the latter case it is possible that the item will get back
   4.310 +    /// to the heap again.
   4.311 +    /// \param i The item.
   4.312 +    State state(const Item &i) const {
   4.313 +      int s = _iim[i];
   4.314 +      if (s>=0) s=0;
   4.315 +      return State(s);
   4.316 +    }
   4.317 +
   4.318 +    /// \brief Set the state of an item in the heap.
   4.319 +    ///
   4.320 +    /// This function sets the state of the given item in the heap.
   4.321 +    /// It can be used to manually clear the heap when it is important
   4.322 +    /// to achive better time complexity.
   4.323 +    /// \param i The item.
   4.324 +    /// \param st The state. It should not be \c IN_HEAP.
   4.325 +    void state(const Item& i, State st) {
   4.326 +      switch (st) {
   4.327 +        case POST_HEAP:
   4.328 +        case PRE_HEAP:
   4.329 +          if (state(i) == IN_HEAP) erase(i);
   4.330 +          _iim[i] = st;
   4.331 +          break;
   4.332 +        case IN_HEAP:
   4.333 +          break;
   4.334 +      }
   4.335 +    }
   4.336 +
   4.337 +    /// \brief Replace an item in the heap.
   4.338 +    ///
   4.339 +    /// This function replaces item \c i with item \c j.
   4.340 +    /// Item \c i must be in the heap, while \c j must be out of the heap.
   4.341 +    /// After calling this method, item \c i will be out of the
   4.342 +    /// heap and \c j will be in the heap with the same prioriority
   4.343 +    /// as item \c i had before.
   4.344 +    void replace(const Item& i, const Item& j) {
   4.345 +      int idx=_iim[i];
   4.346 +      _iim.set(i, _iim[j]);
   4.347 +      _iim.set(j, idx);
   4.348 +      _data[idx].first=j;
   4.349 +    }
   4.350 +
   4.351 +  }; // class DHeap
   4.352 +
   4.353 +} // namespace lemon
   4.354 +
   4.355 +#endif // LEMON_DHEAP_H
     5.1 --- a/lemon/fourary_heap.h	Tue Mar 02 10:27:47 2010 +0100
     5.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.3 @@ -1,342 +0,0 @@
     5.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
     5.5 - *
     5.6 - * This file is a part of LEMON, a generic C++ optimization library.
     5.7 - *
     5.8 - * Copyright (C) 2003-2009
     5.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
    5.11 - *
    5.12 - * Permission to use, modify and distribute this software is granted
    5.13 - * provided that this copyright notice appears in all copies. For
    5.14 - * precise terms see the accompanying LICENSE file.
    5.15 - *
    5.16 - * This software is provided "AS IS" with no warranty of any kind,
    5.17 - * express or implied, and with no claim as to its suitability for any
    5.18 - * purpose.
    5.19 - *
    5.20 - */
    5.21 -
    5.22 -#ifndef LEMON_FOURARY_HEAP_H
    5.23 -#define LEMON_FOURARY_HEAP_H
    5.24 -
    5.25 -///\ingroup heaps
    5.26 -///\file
    5.27 -///\brief Fourary heap implementation.
    5.28 -
    5.29 -#include <vector>
    5.30 -#include <utility>
    5.31 -#include <functional>
    5.32 -
    5.33 -namespace lemon {
    5.34 -
    5.35 -  /// \ingroup heaps
    5.36 -  ///
    5.37 -  ///\brief Fourary heap data structure.
    5.38 -  ///
    5.39 -  /// This class implements the \e fourary \e heap data structure.
    5.40 -  /// It fully conforms to the \ref concepts::Heap "heap concept".
    5.41 -  ///
    5.42 -  /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap"
    5.43 -  /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap",
    5.44 -  /// but its nodes have at most four children, instead of two.
    5.45 -  ///
    5.46 -  /// \tparam PR Type of the priorities of the items.
    5.47 -  /// \tparam IM A read-writable item map with \c int values, used
    5.48 -  /// internally to handle the cross references.
    5.49 -  /// \tparam CMP A functor class for comparing the priorities.
    5.50 -  /// The default is \c std::less<PR>.
    5.51 -  ///
    5.52 -  ///\sa BinHeap
    5.53 -  ///\sa KaryHeap
    5.54 -#ifdef DOXYGEN
    5.55 -  template <typename PR, typename IM, typename CMP>
    5.56 -#else
    5.57 -  template <typename PR, typename IM, typename CMP = std::less<PR> >
    5.58 -#endif
    5.59 -  class FouraryHeap {
    5.60 -  public:
    5.61 -    /// Type of the item-int map.
    5.62 -    typedef IM ItemIntMap;
    5.63 -    /// Type of the priorities.
    5.64 -    typedef PR Prio;
    5.65 -    /// Type of the items stored in the heap.
    5.66 -    typedef typename ItemIntMap::Key Item;
    5.67 -    /// Type of the item-priority pairs.
    5.68 -    typedef std::pair<Item,Prio> Pair;
    5.69 -    /// Functor type for comparing the priorities.
    5.70 -    typedef CMP Compare;
    5.71 -
    5.72 -    /// \brief Type to represent the states of the items.
    5.73 -    ///
    5.74 -    /// Each item has a state associated to it. It can be "in heap",
    5.75 -    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    5.76 -    /// heap's point of view, but may be useful to the user.
    5.77 -    ///
    5.78 -    /// The item-int map must be initialized in such way that it assigns
    5.79 -    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    5.80 -    enum State {
    5.81 -      IN_HEAP = 0,    ///< = 0.
    5.82 -      PRE_HEAP = -1,  ///< = -1.
    5.83 -      POST_HEAP = -2  ///< = -2.
    5.84 -    };
    5.85 -
    5.86 -  private:
    5.87 -    std::vector<Pair> _data;
    5.88 -    Compare _comp;
    5.89 -    ItemIntMap &_iim;
    5.90 -
    5.91 -  public:
    5.92 -    /// \brief Constructor.
    5.93 -    ///
    5.94 -    /// Constructor.
    5.95 -    /// \param map A map that assigns \c int values to the items.
    5.96 -    /// It is used internally to handle the cross references.
    5.97 -    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    5.98 -    explicit FouraryHeap(ItemIntMap &map) : _iim(map) {}
    5.99 -
   5.100 -    /// \brief Constructor.
   5.101 -    ///
   5.102 -    /// Constructor.
   5.103 -    /// \param map A map that assigns \c int values to the items.
   5.104 -    /// It is used internally to handle the cross references.
   5.105 -    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   5.106 -    /// \param comp The function object used for comparing the priorities.
   5.107 -    FouraryHeap(ItemIntMap &map, const Compare &comp)
   5.108 -      : _iim(map), _comp(comp) {}
   5.109 -
   5.110 -    /// \brief The number of items stored in the heap.
   5.111 -    ///
   5.112 -    /// This function returns the number of items stored in the heap.
   5.113 -    int size() const { return _data.size(); }
   5.114 -
   5.115 -    /// \brief Check if the heap is empty.
   5.116 -    ///
   5.117 -    /// This function returns \c true if the heap is empty.
   5.118 -    bool empty() const { return _data.empty(); }
   5.119 -
   5.120 -    /// \brief Make the heap empty.
   5.121 -    ///
   5.122 -    /// This functon makes the heap empty.
   5.123 -    /// It does not change the cross reference map. If you want to reuse
   5.124 -    /// a heap that is not surely empty, you should first clear it and
   5.125 -    /// then you should set the cross reference map to \c PRE_HEAP
   5.126 -    /// for each item.
   5.127 -    void clear() { _data.clear(); }
   5.128 -
   5.129 -  private:
   5.130 -    static int parent(int i) { return (i-1)/4; }
   5.131 -    static int firstChild(int i) { return 4*i+1; }
   5.132 -
   5.133 -    bool less(const Pair &p1, const Pair &p2) const {
   5.134 -      return _comp(p1.second, p2.second);
   5.135 -    }
   5.136 -
   5.137 -    void bubbleUp(int hole, Pair p) {
   5.138 -      int par = parent(hole);
   5.139 -      while( hole>0 && less(p,_data[par]) ) {
   5.140 -        move(_data[par],hole);
   5.141 -        hole = par;
   5.142 -        par = parent(hole);
   5.143 -      }
   5.144 -      move(p, hole);
   5.145 -    }
   5.146 -
   5.147 -    void bubbleDown(int hole, Pair p, int length) {
   5.148 -      if( length>1 ) {
   5.149 -        int child = firstChild(hole);
   5.150 -        while( child+3<length ) {
   5.151 -          int min=child;
   5.152 -          if( less(_data[++child], _data[min]) ) min=child;
   5.153 -          if( less(_data[++child], _data[min]) ) min=child;
   5.154 -          if( less(_data[++child], _data[min]) ) min=child;
   5.155 -          if( !less(_data[min], p) )
   5.156 -            goto ok;
   5.157 -          move(_data[min], hole);
   5.158 -          hole = min;
   5.159 -          child = firstChild(hole);
   5.160 -        }
   5.161 -        if ( child<length ) {
   5.162 -          int min = child;
   5.163 -          if( ++child<length && less(_data[child], _data[min]) ) min=child;
   5.164 -          if( ++child<length && less(_data[child], _data[min]) ) min=child;
   5.165 -          if( less(_data[min], p) ) {
   5.166 -            move(_data[min], hole);
   5.167 -            hole = min;
   5.168 -          }
   5.169 -        }
   5.170 -      }
   5.171 -    ok:
   5.172 -      move(p, hole);
   5.173 -    }
   5.174 -
   5.175 -    void move(const Pair &p, int i) {
   5.176 -      _data[i] = p;
   5.177 -      _iim.set(p.first, i);
   5.178 -    }
   5.179 -
   5.180 -  public:
   5.181 -    /// \brief Insert a pair of item and priority into the heap.
   5.182 -    ///
   5.183 -    /// This function inserts \c p.first to the heap with priority
   5.184 -    /// \c p.second.
   5.185 -    /// \param p The pair to insert.
   5.186 -    /// \pre \c p.first must not be stored in the heap.
   5.187 -    void push(const Pair &p) {
   5.188 -      int n = _data.size();
   5.189 -      _data.resize(n+1);
   5.190 -      bubbleUp(n, p);
   5.191 -    }
   5.192 -
   5.193 -    /// \brief Insert an item into the heap with the given priority.
   5.194 -    ///
   5.195 -    /// This function inserts the given item into the heap with the
   5.196 -    /// given priority.
   5.197 -    /// \param i The item to insert.
   5.198 -    /// \param p The priority of the item.
   5.199 -    /// \pre \e i must not be stored in the heap.
   5.200 -    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
   5.201 -
   5.202 -    /// \brief Return the item having minimum priority.
   5.203 -    ///
   5.204 -    /// This function returns the item having minimum priority.
   5.205 -    /// \pre The heap must be non-empty.
   5.206 -    Item top() const { return _data[0].first; }
   5.207 -
   5.208 -    /// \brief The minimum priority.
   5.209 -    ///
   5.210 -    /// This function returns the minimum priority.
   5.211 -    /// \pre The heap must be non-empty.
   5.212 -    Prio prio() const { return _data[0].second; }
   5.213 -
   5.214 -    /// \brief Remove the item having minimum priority.
   5.215 -    ///
   5.216 -    /// This function removes the item having minimum priority.
   5.217 -    /// \pre The heap must be non-empty.
   5.218 -    void pop() {
   5.219 -      int n = _data.size()-1;
   5.220 -      _iim.set(_data[0].first, POST_HEAP);
   5.221 -      if (n>0) bubbleDown(0, _data[n], n);
   5.222 -      _data.pop_back();
   5.223 -    }
   5.224 -
   5.225 -    /// \brief Remove the given item from the heap.
   5.226 -    ///
   5.227 -    /// This function removes the given item from the heap if it is
   5.228 -    /// already stored.
   5.229 -    /// \param i The item to delete.
   5.230 -    /// \pre \e i must be in the heap.
   5.231 -    void erase(const Item &i) {
   5.232 -      int h = _iim[i];
   5.233 -      int n = _data.size()-1;
   5.234 -      _iim.set(_data[h].first, POST_HEAP);
   5.235 -      if( h<n ) {
   5.236 -        if( less(_data[parent(h)], _data[n]) )
   5.237 -          bubbleDown(h, _data[n], n);
   5.238 -        else
   5.239 -          bubbleUp(h, _data[n]);
   5.240 -      }
   5.241 -      _data.pop_back();
   5.242 -    }
   5.243 -
   5.244 -    /// \brief The priority of the given item.
   5.245 -    ///
   5.246 -    /// This function returns the priority of the given item.
   5.247 -    /// \param i The item.
   5.248 -    /// \pre \e i must be in the heap.
   5.249 -    Prio operator[](const Item &i) const {
   5.250 -      int idx = _iim[i];
   5.251 -      return _data[idx].second;
   5.252 -    }
   5.253 -
   5.254 -    /// \brief Set the priority of an item or insert it, if it is
   5.255 -    /// not stored in the heap.
   5.256 -    ///
   5.257 -    /// This method sets the priority of the given item if it is
   5.258 -    /// already stored in the heap. Otherwise it inserts the given
   5.259 -    /// item into the heap with the given priority.
   5.260 -    /// \param i The item.
   5.261 -    /// \param p The priority.
   5.262 -    void set(const Item &i, const Prio &p) {
   5.263 -      int idx = _iim[i];
   5.264 -      if( idx < 0 )
   5.265 -        push(i,p);
   5.266 -      else if( _comp(p, _data[idx].second) )
   5.267 -        bubbleUp(idx, Pair(i,p));
   5.268 -      else
   5.269 -        bubbleDown(idx, Pair(i,p), _data.size());
   5.270 -    }
   5.271 -
   5.272 -    /// \brief Decrease the priority of an item to the given value.
   5.273 -    ///
   5.274 -    /// This function decreases the priority of an item to the given value.
   5.275 -    /// \param i The item.
   5.276 -    /// \param p The priority.
   5.277 -    /// \pre \e i must be stored in the heap with priority at least \e p.
   5.278 -    void decrease(const Item &i, const Prio &p) {
   5.279 -      int idx = _iim[i];
   5.280 -      bubbleUp(idx, Pair(i,p));
   5.281 -    }
   5.282 -
   5.283 -    /// \brief Increase the priority of an item to the given value.
   5.284 -    ///
   5.285 -    /// This function increases the priority of an item to the given value.
   5.286 -    /// \param i The item.
   5.287 -    /// \param p The priority.
   5.288 -    /// \pre \e i must be stored in the heap with priority at most \e p.
   5.289 -    void increase(const Item &i, const Prio &p) {
   5.290 -      int idx = _iim[i];
   5.291 -      bubbleDown(idx, Pair(i,p), _data.size());
   5.292 -    }
   5.293 -
   5.294 -    /// \brief Return the state of an item.
   5.295 -    ///
   5.296 -    /// This method returns \c PRE_HEAP if the given item has never
   5.297 -    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   5.298 -    /// and \c POST_HEAP otherwise.
   5.299 -    /// In the latter case it is possible that the item will get back
   5.300 -    /// to the heap again.
   5.301 -    /// \param i The item.
   5.302 -    State state(const Item &i) const {
   5.303 -      int s = _iim[i];
   5.304 -      if (s>=0) s=0;
   5.305 -      return State(s);
   5.306 -    }
   5.307 -
   5.308 -    /// \brief Set the state of an item in the heap.
   5.309 -    ///
   5.310 -    /// This function sets the state of the given item in the heap.
   5.311 -    /// It can be used to manually clear the heap when it is important
   5.312 -    /// to achive better time complexity.
   5.313 -    /// \param i The item.
   5.314 -    /// \param st The state. It should not be \c IN_HEAP.
   5.315 -    void state(const Item& i, State st) {
   5.316 -      switch (st) {
   5.317 -        case POST_HEAP:
   5.318 -        case PRE_HEAP:
   5.319 -          if (state(i) == IN_HEAP) erase(i);
   5.320 -          _iim[i] = st;
   5.321 -          break;
   5.322 -        case IN_HEAP:
   5.323 -          break;
   5.324 -      }
   5.325 -    }
   5.326 -
   5.327 -    /// \brief Replace an item in the heap.
   5.328 -    ///
   5.329 -    /// This function replaces item \c i with item \c j.
   5.330 -    /// Item \c i must be in the heap, while \c j must be out of the heap.
   5.331 -    /// After calling this method, item \c i will be out of the
   5.332 -    /// heap and \c j will be in the heap with the same prioriority
   5.333 -    /// as item \c i had before.
   5.334 -    void replace(const Item& i, const Item& j) {
   5.335 -      int idx = _iim[i];
   5.336 -      _iim.set(i, _iim[j]);
   5.337 -      _iim.set(j, idx);
   5.338 -      _data[idx].first = j;
   5.339 -    }
   5.340 -
   5.341 -  }; // class FouraryHeap
   5.342 -
   5.343 -} // namespace lemon
   5.344 -
   5.345 -#endif // LEMON_FOURARY_HEAP_H
     6.1 --- a/lemon/kary_heap.h	Tue Mar 02 10:27:47 2010 +0100
     6.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.3 @@ -1,352 +0,0 @@
     6.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
     6.5 - *
     6.6 - * This file is a part of LEMON, a generic C++ optimization library.
     6.7 - *
     6.8 - * Copyright (C) 2003-2009
     6.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    6.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
    6.11 - *
    6.12 - * Permission to use, modify and distribute this software is granted
    6.13 - * provided that this copyright notice appears in all copies. For
    6.14 - * precise terms see the accompanying LICENSE file.
    6.15 - *
    6.16 - * This software is provided "AS IS" with no warranty of any kind,
    6.17 - * express or implied, and with no claim as to its suitability for any
    6.18 - * purpose.
    6.19 - *
    6.20 - */
    6.21 -
    6.22 -#ifndef LEMON_KARY_HEAP_H
    6.23 -#define LEMON_KARY_HEAP_H
    6.24 -
    6.25 -///\ingroup heaps
    6.26 -///\file
    6.27 -///\brief Fourary heap implementation.
    6.28 -
    6.29 -#include <vector>
    6.30 -#include <utility>
    6.31 -#include <functional>
    6.32 -
    6.33 -namespace lemon {
    6.34 -
    6.35 -  /// \ingroup heaps
    6.36 -  ///
    6.37 -  ///\brief K-ary heap data structure.
    6.38 -  ///
    6.39 -  /// This class implements the \e K-ary \e heap data structure.
    6.40 -  /// It fully conforms to the \ref concepts::Heap "heap concept".
    6.41 -  ///
    6.42 -  /// The \ref KaryHeap "K-ary heap" is a generalization of the
    6.43 -  /// \ref BinHeap "binary heap" structure, its nodes have at most
    6.44 -  /// \c K children, instead of two.
    6.45 -  /// \ref BinHeap and \ref FouraryHeap are specialized implementations
    6.46 -  /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively.
    6.47 -  ///
    6.48 -  /// \tparam PR Type of the priorities of the items.
    6.49 -  /// \tparam IM A read-writable item map with \c int values, used
    6.50 -  /// internally to handle the cross references.
    6.51 -  /// \tparam K The degree of the heap, each node have at most \e K
    6.52 -  /// children. The default is 16. Powers of two are suggested to use
    6.53 -  /// so that the multiplications and divisions needed to traverse the
    6.54 -  /// nodes of the heap could be performed faster.
    6.55 -  /// \tparam CMP A functor class for comparing the priorities.
    6.56 -  /// The default is \c std::less<PR>.
    6.57 -  ///
    6.58 -  ///\sa BinHeap
    6.59 -  ///\sa FouraryHeap
    6.60 -#ifdef DOXYGEN
    6.61 -  template <typename PR, typename IM, int K, typename CMP>
    6.62 -#else
    6.63 -  template <typename PR, typename IM, int K = 16,
    6.64 -            typename CMP = std::less<PR> >
    6.65 -#endif
    6.66 -  class KaryHeap {
    6.67 -  public:
    6.68 -    /// Type of the item-int map.
    6.69 -    typedef IM ItemIntMap;
    6.70 -    /// Type of the priorities.
    6.71 -    typedef PR Prio;
    6.72 -    /// Type of the items stored in the heap.
    6.73 -    typedef typename ItemIntMap::Key Item;
    6.74 -    /// Type of the item-priority pairs.
    6.75 -    typedef std::pair<Item,Prio> Pair;
    6.76 -    /// Functor type for comparing the priorities.
    6.77 -    typedef CMP Compare;
    6.78 -
    6.79 -    /// \brief Type to represent the states of the items.
    6.80 -    ///
    6.81 -    /// Each item has a state associated to it. It can be "in heap",
    6.82 -    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    6.83 -    /// heap's point of view, but may be useful to the user.
    6.84 -    ///
    6.85 -    /// The item-int map must be initialized in such way that it assigns
    6.86 -    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    6.87 -    enum State {
    6.88 -      IN_HEAP = 0,    ///< = 0.
    6.89 -      PRE_HEAP = -1,  ///< = -1.
    6.90 -      POST_HEAP = -2  ///< = -2.
    6.91 -    };
    6.92 -
    6.93 -  private:
    6.94 -    std::vector<Pair> _data;
    6.95 -    Compare _comp;
    6.96 -    ItemIntMap &_iim;
    6.97 -
    6.98 -  public:
    6.99 -    /// \brief Constructor.
   6.100 -    ///
   6.101 -    /// Constructor.
   6.102 -    /// \param map A map that assigns \c int values to the items.
   6.103 -    /// It is used internally to handle the cross references.
   6.104 -    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   6.105 -    explicit KaryHeap(ItemIntMap &map) : _iim(map) {}
   6.106 -
   6.107 -    /// \brief Constructor.
   6.108 -    ///
   6.109 -    /// Constructor.
   6.110 -    /// \param map A map that assigns \c int values to the items.
   6.111 -    /// It is used internally to handle the cross references.
   6.112 -    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   6.113 -    /// \param comp The function object used for comparing the priorities.
   6.114 -    KaryHeap(ItemIntMap &map, const Compare &comp)
   6.115 -      : _iim(map), _comp(comp) {}
   6.116 -
   6.117 -    /// \brief The number of items stored in the heap.
   6.118 -    ///
   6.119 -    /// This function returns the number of items stored in the heap.
   6.120 -    int size() const { return _data.size(); }
   6.121 -
   6.122 -    /// \brief Check if the heap is empty.
   6.123 -    ///
   6.124 -    /// This function returns \c true if the heap is empty.
   6.125 -    bool empty() const { return _data.empty(); }
   6.126 -
   6.127 -    /// \brief Make the heap empty.
   6.128 -    ///
   6.129 -    /// This functon makes the heap empty.
   6.130 -    /// It does not change the cross reference map. If you want to reuse
   6.131 -    /// a heap that is not surely empty, you should first clear it and
   6.132 -    /// then you should set the cross reference map to \c PRE_HEAP
   6.133 -    /// for each item.
   6.134 -    void clear() { _data.clear(); }
   6.135 -
   6.136 -  private:
   6.137 -    int parent(int i) { return (i-1)/K; }
   6.138 -    int firstChild(int i) { return K*i+1; }
   6.139 -
   6.140 -    bool less(const Pair &p1, const Pair &p2) const {
   6.141 -      return _comp(p1.second, p2.second);
   6.142 -    }
   6.143 -
   6.144 -    void bubbleUp(int hole, Pair p) {
   6.145 -      int par = parent(hole);
   6.146 -      while( hole>0 && less(p,_data[par]) ) {
   6.147 -        move(_data[par],hole);
   6.148 -        hole = par;
   6.149 -        par = parent(hole);
   6.150 -      }
   6.151 -      move(p, hole);
   6.152 -    }
   6.153 -
   6.154 -    void bubbleDown(int hole, Pair p, int length) {
   6.155 -      if( length>1 ) {
   6.156 -        int child = firstChild(hole);
   6.157 -        while( child+K<=length ) {
   6.158 -          int min=child;
   6.159 -          for (int i=1; i<K; ++i) {
   6.160 -            if( less(_data[child+i], _data[min]) )
   6.161 -              min=child+i;
   6.162 -          }
   6.163 -          if( !less(_data[min], p) )
   6.164 -            goto ok;
   6.165 -          move(_data[min], hole);
   6.166 -          hole = min;
   6.167 -          child = firstChild(hole);
   6.168 -        }
   6.169 -        if ( child<length ) {
   6.170 -          int min = child;
   6.171 -          while (++child < length) {
   6.172 -            if( less(_data[child], _data[min]) )
   6.173 -              min=child;
   6.174 -          }
   6.175 -          if( less(_data[min], p) ) {
   6.176 -            move(_data[min], hole);
   6.177 -            hole = min;
   6.178 -          }
   6.179 -        }
   6.180 -      }
   6.181 -    ok:
   6.182 -      move(p, hole);
   6.183 -    }
   6.184 -
   6.185 -    void move(const Pair &p, int i) {
   6.186 -      _data[i] = p;
   6.187 -      _iim.set(p.first, i);
   6.188 -    }
   6.189 -
   6.190 -  public:
   6.191 -    /// \brief Insert a pair of item and priority into the heap.
   6.192 -    ///
   6.193 -    /// This function inserts \c p.first to the heap with priority
   6.194 -    /// \c p.second.
   6.195 -    /// \param p The pair to insert.
   6.196 -    /// \pre \c p.first must not be stored in the heap.
   6.197 -    void push(const Pair &p) {
   6.198 -      int n = _data.size();
   6.199 -      _data.resize(n+1);
   6.200 -      bubbleUp(n, p);
   6.201 -    }
   6.202 -
   6.203 -    /// \brief Insert an item into the heap with the given priority.
   6.204 -    ///
   6.205 -    /// This function inserts the given item into the heap with the
   6.206 -    /// given priority.
   6.207 -    /// \param i The item to insert.
   6.208 -    /// \param p The priority of the item.
   6.209 -    /// \pre \e i must not be stored in the heap.
   6.210 -    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
   6.211 -
   6.212 -    /// \brief Return the item having minimum priority.
   6.213 -    ///
   6.214 -    /// This function returns the item having minimum priority.
   6.215 -    /// \pre The heap must be non-empty.
   6.216 -    Item top() const { return _data[0].first; }
   6.217 -
   6.218 -    /// \brief The minimum priority.
   6.219 -    ///
   6.220 -    /// This function returns the minimum priority.
   6.221 -    /// \pre The heap must be non-empty.
   6.222 -    Prio prio() const { return _data[0].second; }
   6.223 -
   6.224 -    /// \brief Remove the item having minimum priority.
   6.225 -    ///
   6.226 -    /// This function removes the item having minimum priority.
   6.227 -    /// \pre The heap must be non-empty.
   6.228 -    void pop() {
   6.229 -      int n = _data.size()-1;
   6.230 -      _iim.set(_data[0].first, POST_HEAP);
   6.231 -      if (n>0) bubbleDown(0, _data[n], n);
   6.232 -      _data.pop_back();
   6.233 -    }
   6.234 -
   6.235 -    /// \brief Remove the given item from the heap.
   6.236 -    ///
   6.237 -    /// This function removes the given item from the heap if it is
   6.238 -    /// already stored.
   6.239 -    /// \param i The item to delete.
   6.240 -    /// \pre \e i must be in the heap.
   6.241 -    void erase(const Item &i) {
   6.242 -      int h = _iim[i];
   6.243 -      int n = _data.size()-1;
   6.244 -      _iim.set(_data[h].first, POST_HEAP);
   6.245 -      if( h<n ) {
   6.246 -        if( less(_data[parent(h)], _data[n]) )
   6.247 -          bubbleDown(h, _data[n], n);
   6.248 -        else
   6.249 -          bubbleUp(h, _data[n]);
   6.250 -      }
   6.251 -      _data.pop_back();
   6.252 -    }
   6.253 -
   6.254 -    /// \brief The priority of the given item.
   6.255 -    ///
   6.256 -    /// This function returns the priority of the given item.
   6.257 -    /// \param i The item.
   6.258 -    /// \pre \e i must be in the heap.
   6.259 -    Prio operator[](const Item &i) const {
   6.260 -      int idx = _iim[i];
   6.261 -      return _data[idx].second;
   6.262 -    }
   6.263 -
   6.264 -    /// \brief Set the priority of an item or insert it, if it is
   6.265 -    /// not stored in the heap.
   6.266 -    ///
   6.267 -    /// This method sets the priority of the given item if it is
   6.268 -    /// already stored in the heap. Otherwise it inserts the given
   6.269 -    /// item into the heap with the given priority.
   6.270 -    /// \param i The item.
   6.271 -    /// \param p The priority.
   6.272 -    void set(const Item &i, const Prio &p) {
   6.273 -      int idx = _iim[i];
   6.274 -      if( idx<0 )
   6.275 -        push(i,p);
   6.276 -      else if( _comp(p, _data[idx].second) )
   6.277 -        bubbleUp(idx, Pair(i,p));
   6.278 -      else
   6.279 -        bubbleDown(idx, Pair(i,p), _data.size());
   6.280 -    }
   6.281 -
   6.282 -    /// \brief Decrease the priority of an item to the given value.
   6.283 -    ///
   6.284 -    /// This function decreases the priority of an item to the given value.
   6.285 -    /// \param i The item.
   6.286 -    /// \param p The priority.
   6.287 -    /// \pre \e i must be stored in the heap with priority at least \e p.
   6.288 -    void decrease(const Item &i, const Prio &p) {
   6.289 -      int idx = _iim[i];
   6.290 -      bubbleUp(idx, Pair(i,p));
   6.291 -    }
   6.292 -
   6.293 -    /// \brief Increase the priority of an item to the given value.
   6.294 -    ///
   6.295 -    /// This function increases the priority of an item to the given value.
   6.296 -    /// \param i The item.
   6.297 -    /// \param p The priority.
   6.298 -    /// \pre \e i must be stored in the heap with priority at most \e p.
   6.299 -    void increase(const Item &i, const Prio &p) {
   6.300 -      int idx = _iim[i];
   6.301 -      bubbleDown(idx, Pair(i,p), _data.size());
   6.302 -    }
   6.303 -
   6.304 -    /// \brief Return the state of an item.
   6.305 -    ///
   6.306 -    /// This method returns \c PRE_HEAP if the given item has never
   6.307 -    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   6.308 -    /// and \c POST_HEAP otherwise.
   6.309 -    /// In the latter case it is possible that the item will get back
   6.310 -    /// to the heap again.
   6.311 -    /// \param i The item.
   6.312 -    State state(const Item &i) const {
   6.313 -      int s = _iim[i];
   6.314 -      if (s>=0) s=0;
   6.315 -      return State(s);
   6.316 -    }
   6.317 -
   6.318 -    /// \brief Set the state of an item in the heap.
   6.319 -    ///
   6.320 -    /// This function sets the state of the given item in the heap.
   6.321 -    /// It can be used to manually clear the heap when it is important
   6.322 -    /// to achive better time complexity.
   6.323 -    /// \param i The item.
   6.324 -    /// \param st The state. It should not be \c IN_HEAP.
   6.325 -    void state(const Item& i, State st) {
   6.326 -      switch (st) {
   6.327 -        case POST_HEAP:
   6.328 -        case PRE_HEAP:
   6.329 -          if (state(i) == IN_HEAP) erase(i);
   6.330 -          _iim[i] = st;
   6.331 -          break;
   6.332 -        case IN_HEAP:
   6.333 -          break;
   6.334 -      }
   6.335 -    }
   6.336 -
   6.337 -    /// \brief Replace an item in the heap.
   6.338 -    ///
   6.339 -    /// This function replaces item \c i with item \c j.
   6.340 -    /// Item \c i must be in the heap, while \c j must be out of the heap.
   6.341 -    /// After calling this method, item \c i will be out of the
   6.342 -    /// heap and \c j will be in the heap with the same prioriority
   6.343 -    /// as item \c i had before.
   6.344 -    void replace(const Item& i, const Item& j) {
   6.345 -      int idx=_iim[i];
   6.346 -      _iim.set(i, _iim[j]);
   6.347 -      _iim.set(j, idx);
   6.348 -      _data[idx].first=j;
   6.349 -    }
   6.350 -
   6.351 -  }; // class KaryHeap
   6.352 -
   6.353 -} // namespace lemon
   6.354 -
   6.355 -#endif // LEMON_KARY_HEAP_H
     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/lemon/quad_heap.h	Wed Mar 03 17:22:13 2010 +0000
     7.3 @@ -0,0 +1,343 @@
     7.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     7.5 + *
     7.6 + * This file is a part of LEMON, a generic C++ optimization library.
     7.7 + *
     7.8 + * Copyright (C) 2003-2009
     7.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    7.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    7.11 + *
    7.12 + * Permission to use, modify and distribute this software is granted
    7.13 + * provided that this copyright notice appears in all copies. For
    7.14 + * precise terms see the accompanying LICENSE file.
    7.15 + *
    7.16 + * This software is provided "AS IS" with no warranty of any kind,
    7.17 + * express or implied, and with no claim as to its suitability for any
    7.18 + * purpose.
    7.19 + *
    7.20 + */
    7.21 +
    7.22 +#ifndef LEMON_QUAD_HEAP_H
    7.23 +#define LEMON_QUAD_HEAP_H
    7.24 +
    7.25 +///\ingroup heaps
    7.26 +///\file
    7.27 +///\brief Fourary (quaternary) heap implementation.
    7.28 +
    7.29 +#include <vector>
    7.30 +#include <utility>
    7.31 +#include <functional>
    7.32 +
    7.33 +namespace lemon {
    7.34 +
    7.35 +  /// \ingroup heaps
    7.36 +  ///
    7.37 +  ///\brief Fourary (quaternary) heap data structure.
    7.38 +  ///
    7.39 +  /// This class implements the \e Fourary (\e quaternary) \e heap
    7.40 +  /// data structure.
    7.41 +  /// It fully conforms to the \ref concepts::Heap "heap concept".
    7.42 +  ///
    7.43 +  /// The fourary heap is a specialization of the \ref DHeap "D-ary heap"
    7.44 +  /// for <tt>D=4</tt>. It is similar to the \ref BinHeap "binary heap",
    7.45 +  /// but its nodes have at most four children, instead of two.
    7.46 +  ///
    7.47 +  /// \tparam PR Type of the priorities of the items.
    7.48 +  /// \tparam IM A read-writable item map with \c int values, used
    7.49 +  /// internally to handle the cross references.
    7.50 +  /// \tparam CMP A functor class for comparing the priorities.
    7.51 +  /// The default is \c std::less<PR>.
    7.52 +  ///
    7.53 +  ///\sa BinHeap
    7.54 +  ///\sa DHeap
    7.55 +#ifdef DOXYGEN
    7.56 +  template <typename PR, typename IM, typename CMP>
    7.57 +#else
    7.58 +  template <typename PR, typename IM, typename CMP = std::less<PR> >
    7.59 +#endif
    7.60 +  class QuadHeap {
    7.61 +  public:
    7.62 +    /// Type of the item-int map.
    7.63 +    typedef IM ItemIntMap;
    7.64 +    /// Type of the priorities.
    7.65 +    typedef PR Prio;
    7.66 +    /// Type of the items stored in the heap.
    7.67 +    typedef typename ItemIntMap::Key Item;
    7.68 +    /// Type of the item-priority pairs.
    7.69 +    typedef std::pair<Item,Prio> Pair;
    7.70 +    /// Functor type for comparing the priorities.
    7.71 +    typedef CMP Compare;
    7.72 +
    7.73 +    /// \brief Type to represent the states of the items.
    7.74 +    ///
    7.75 +    /// Each item has a state associated to it. It can be "in heap",
    7.76 +    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    7.77 +    /// heap's point of view, but may be useful to the user.
    7.78 +    ///
    7.79 +    /// The item-int map must be initialized in such way that it assigns
    7.80 +    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    7.81 +    enum State {
    7.82 +      IN_HEAP = 0,    ///< = 0.
    7.83 +      PRE_HEAP = -1,  ///< = -1.
    7.84 +      POST_HEAP = -2  ///< = -2.
    7.85 +    };
    7.86 +
    7.87 +  private:
    7.88 +    std::vector<Pair> _data;
    7.89 +    Compare _comp;
    7.90 +    ItemIntMap &_iim;
    7.91 +
    7.92 +  public:
    7.93 +    /// \brief Constructor.
    7.94 +    ///
    7.95 +    /// Constructor.
    7.96 +    /// \param map A map that assigns \c int values to the items.
    7.97 +    /// It is used internally to handle the cross references.
    7.98 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    7.99 +    explicit QuadHeap(ItemIntMap &map) : _iim(map) {}
   7.100 +
   7.101 +    /// \brief Constructor.
   7.102 +    ///
   7.103 +    /// Constructor.
   7.104 +    /// \param map A map that assigns \c int values to the items.
   7.105 +    /// It is used internally to handle the cross references.
   7.106 +    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   7.107 +    /// \param comp The function object used for comparing the priorities.
   7.108 +    QuadHeap(ItemIntMap &map, const Compare &comp)
   7.109 +      : _iim(map), _comp(comp) {}
   7.110 +
   7.111 +    /// \brief The number of items stored in the heap.
   7.112 +    ///
   7.113 +    /// This function returns the number of items stored in the heap.
   7.114 +    int size() const { return _data.size(); }
   7.115 +
   7.116 +    /// \brief Check if the heap is empty.
   7.117 +    ///
   7.118 +    /// This function returns \c true if the heap is empty.
   7.119 +    bool empty() const { return _data.empty(); }
   7.120 +
   7.121 +    /// \brief Make the heap empty.
   7.122 +    ///
   7.123 +    /// This functon makes the heap empty.
   7.124 +    /// It does not change the cross reference map. If you want to reuse
   7.125 +    /// a heap that is not surely empty, you should first clear it and
   7.126 +    /// then you should set the cross reference map to \c PRE_HEAP
   7.127 +    /// for each item.
   7.128 +    void clear() { _data.clear(); }
   7.129 +
   7.130 +  private:
   7.131 +    static int parent(int i) { return (i-1)/4; }
   7.132 +    static int firstChild(int i) { return 4*i+1; }
   7.133 +
   7.134 +    bool less(const Pair &p1, const Pair &p2) const {
   7.135 +      return _comp(p1.second, p2.second);
   7.136 +    }
   7.137 +
   7.138 +    void bubbleUp(int hole, Pair p) {
   7.139 +      int par = parent(hole);
   7.140 +      while( hole>0 && less(p,_data[par]) ) {
   7.141 +        move(_data[par],hole);
   7.142 +        hole = par;
   7.143 +        par = parent(hole);
   7.144 +      }
   7.145 +      move(p, hole);
   7.146 +    }
   7.147 +
   7.148 +    void bubbleDown(int hole, Pair p, int length) {
   7.149 +      if( length>1 ) {
   7.150 +        int child = firstChild(hole);
   7.151 +        while( child+3<length ) {
   7.152 +          int min=child;
   7.153 +          if( less(_data[++child], _data[min]) ) min=child;
   7.154 +          if( less(_data[++child], _data[min]) ) min=child;
   7.155 +          if( less(_data[++child], _data[min]) ) min=child;
   7.156 +          if( !less(_data[min], p) )
   7.157 +            goto ok;
   7.158 +          move(_data[min], hole);
   7.159 +          hole = min;
   7.160 +          child = firstChild(hole);
   7.161 +        }
   7.162 +        if ( child<length ) {
   7.163 +          int min = child;
   7.164 +          if( ++child<length && less(_data[child], _data[min]) ) min=child;
   7.165 +          if( ++child<length && less(_data[child], _data[min]) ) min=child;
   7.166 +          if( less(_data[min], p) ) {
   7.167 +            move(_data[min], hole);
   7.168 +            hole = min;
   7.169 +          }
   7.170 +        }
   7.171 +      }
   7.172 +    ok:
   7.173 +      move(p, hole);
   7.174 +    }
   7.175 +
   7.176 +    void move(const Pair &p, int i) {
   7.177 +      _data[i] = p;
   7.178 +      _iim.set(p.first, i);
   7.179 +    }
   7.180 +
   7.181 +  public:
   7.182 +    /// \brief Insert a pair of item and priority into the heap.
   7.183 +    ///
   7.184 +    /// This function inserts \c p.first to the heap with priority
   7.185 +    /// \c p.second.
   7.186 +    /// \param p The pair to insert.
   7.187 +    /// \pre \c p.first must not be stored in the heap.
   7.188 +    void push(const Pair &p) {
   7.189 +      int n = _data.size();
   7.190 +      _data.resize(n+1);
   7.191 +      bubbleUp(n, p);
   7.192 +    }
   7.193 +
   7.194 +    /// \brief Insert an item into the heap with the given priority.
   7.195 +    ///
   7.196 +    /// This function inserts the given item into the heap with the
   7.197 +    /// given priority.
   7.198 +    /// \param i The item to insert.
   7.199 +    /// \param p The priority of the item.
   7.200 +    /// \pre \e i must not be stored in the heap.
   7.201 +    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
   7.202 +
   7.203 +    /// \brief Return the item having minimum priority.
   7.204 +    ///
   7.205 +    /// This function returns the item having minimum priority.
   7.206 +    /// \pre The heap must be non-empty.
   7.207 +    Item top() const { return _data[0].first; }
   7.208 +
   7.209 +    /// \brief The minimum priority.
   7.210 +    ///
   7.211 +    /// This function returns the minimum priority.
   7.212 +    /// \pre The heap must be non-empty.
   7.213 +    Prio prio() const { return _data[0].second; }
   7.214 +
   7.215 +    /// \brief Remove the item having minimum priority.
   7.216 +    ///
   7.217 +    /// This function removes the item having minimum priority.
   7.218 +    /// \pre The heap must be non-empty.
   7.219 +    void pop() {
   7.220 +      int n = _data.size()-1;
   7.221 +      _iim.set(_data[0].first, POST_HEAP);
   7.222 +      if (n>0) bubbleDown(0, _data[n], n);
   7.223 +      _data.pop_back();
   7.224 +    }
   7.225 +
   7.226 +    /// \brief Remove the given item from the heap.
   7.227 +    ///
   7.228 +    /// This function removes the given item from the heap if it is
   7.229 +    /// already stored.
   7.230 +    /// \param i The item to delete.
   7.231 +    /// \pre \e i must be in the heap.
   7.232 +    void erase(const Item &i) {
   7.233 +      int h = _iim[i];
   7.234 +      int n = _data.size()-1;
   7.235 +      _iim.set(_data[h].first, POST_HEAP);
   7.236 +      if( h<n ) {
   7.237 +        if( less(_data[parent(h)], _data[n]) )
   7.238 +          bubbleDown(h, _data[n], n);
   7.239 +        else
   7.240 +          bubbleUp(h, _data[n]);
   7.241 +      }
   7.242 +      _data.pop_back();
   7.243 +    }
   7.244 +
   7.245 +    /// \brief The priority of the given item.
   7.246 +    ///
   7.247 +    /// This function returns the priority of the given item.
   7.248 +    /// \param i The item.
   7.249 +    /// \pre \e i must be in the heap.
   7.250 +    Prio operator[](const Item &i) const {
   7.251 +      int idx = _iim[i];
   7.252 +      return _data[idx].second;
   7.253 +    }
   7.254 +
   7.255 +    /// \brief Set the priority of an item or insert it, if it is
   7.256 +    /// not stored in the heap.
   7.257 +    ///
   7.258 +    /// This method sets the priority of the given item if it is
   7.259 +    /// already stored in the heap. Otherwise it inserts the given
   7.260 +    /// item into the heap with the given priority.
   7.261 +    /// \param i The item.
   7.262 +    /// \param p The priority.
   7.263 +    void set(const Item &i, const Prio &p) {
   7.264 +      int idx = _iim[i];
   7.265 +      if( idx < 0 )
   7.266 +        push(i,p);
   7.267 +      else if( _comp(p, _data[idx].second) )
   7.268 +        bubbleUp(idx, Pair(i,p));
   7.269 +      else
   7.270 +        bubbleDown(idx, Pair(i,p), _data.size());
   7.271 +    }
   7.272 +
   7.273 +    /// \brief Decrease the priority of an item to the given value.
   7.274 +    ///
   7.275 +    /// This function decreases the priority of an item to the given value.
   7.276 +    /// \param i The item.
   7.277 +    /// \param p The priority.
   7.278 +    /// \pre \e i must be stored in the heap with priority at least \e p.
   7.279 +    void decrease(const Item &i, const Prio &p) {
   7.280 +      int idx = _iim[i];
   7.281 +      bubbleUp(idx, Pair(i,p));
   7.282 +    }
   7.283 +
   7.284 +    /// \brief Increase the priority of an item to the given value.
   7.285 +    ///
   7.286 +    /// This function increases the priority of an item to the given value.
   7.287 +    /// \param i The item.
   7.288 +    /// \param p The priority.
   7.289 +    /// \pre \e i must be stored in the heap with priority at most \e p.
   7.290 +    void increase(const Item &i, const Prio &p) {
   7.291 +      int idx = _iim[i];
   7.292 +      bubbleDown(idx, Pair(i,p), _data.size());
   7.293 +    }
   7.294 +
   7.295 +    /// \brief Return the state of an item.
   7.296 +    ///
   7.297 +    /// This method returns \c PRE_HEAP if the given item has never
   7.298 +    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   7.299 +    /// and \c POST_HEAP otherwise.
   7.300 +    /// In the latter case it is possible that the item will get back
   7.301 +    /// to the heap again.
   7.302 +    /// \param i The item.
   7.303 +    State state(const Item &i) const {
   7.304 +      int s = _iim[i];
   7.305 +      if (s>=0) s=0;
   7.306 +      return State(s);
   7.307 +    }
   7.308 +
   7.309 +    /// \brief Set the state of an item in the heap.
   7.310 +    ///
   7.311 +    /// This function sets the state of the given item in the heap.
   7.312 +    /// It can be used to manually clear the heap when it is important
   7.313 +    /// to achive better time complexity.
   7.314 +    /// \param i The item.
   7.315 +    /// \param st The state. It should not be \c IN_HEAP.
   7.316 +    void state(const Item& i, State st) {
   7.317 +      switch (st) {
   7.318 +        case POST_HEAP:
   7.319 +        case PRE_HEAP:
   7.320 +          if (state(i) == IN_HEAP) erase(i);
   7.321 +          _iim[i] = st;
   7.322 +          break;
   7.323 +        case IN_HEAP:
   7.324 +          break;
   7.325 +      }
   7.326 +    }
   7.327 +
   7.328 +    /// \brief Replace an item in the heap.
   7.329 +    ///
   7.330 +    /// This function replaces item \c i with item \c j.
   7.331 +    /// Item \c i must be in the heap, while \c j must be out of the heap.
   7.332 +    /// After calling this method, item \c i will be out of the
   7.333 +    /// heap and \c j will be in the heap with the same prioriority
   7.334 +    /// as item \c i had before.
   7.335 +    void replace(const Item& i, const Item& j) {
   7.336 +      int idx = _iim[i];
   7.337 +      _iim.set(i, _iim[j]);
   7.338 +      _iim.set(j, idx);
   7.339 +      _data[idx].first = j;
   7.340 +    }
   7.341 +
   7.342 +  }; // class QuadHeap
   7.343 +
   7.344 +} // namespace lemon
   7.345 +
   7.346 +#endif // LEMON_FOURARY_HEAP_H
     8.1 --- a/test/heap_test.cc	Tue Mar 02 10:27:47 2010 +0100
     8.2 +++ b/test/heap_test.cc	Wed Mar 03 17:22:13 2010 +0000
     8.3 @@ -30,12 +30,12 @@
     8.4  #include <lemon/maps.h>
     8.5  
     8.6  #include <lemon/bin_heap.h>
     8.7 -#include <lemon/fourary_heap.h>
     8.8 -#include <lemon/kary_heap.h>
     8.9 +#include <lemon/quad_heap.h>
    8.10 +#include <lemon/dheap.h>
    8.11  #include <lemon/fib_heap.h>
    8.12  #include <lemon/pairing_heap.h>
    8.13  #include <lemon/radix_heap.h>
    8.14 -#include <lemon/binom_heap.h>
    8.15 +#include <lemon/binomial_heap.h>
    8.16  #include <lemon/bucket_heap.h>
    8.17  
    8.18  #include "test_tools.h"
    8.19 @@ -185,26 +185,26 @@
    8.20      dijkstraHeapTest<NodeHeap>(digraph, length, source);
    8.21    }
    8.22  
    8.23 -  // FouraryHeap
    8.24 +  // QuadHeap
    8.25    {
    8.26 -    typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
    8.27 +    typedef QuadHeap<Prio, ItemIntMap> IntHeap;
    8.28      checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    8.29      heapSortTest<IntHeap>();
    8.30      heapIncreaseTest<IntHeap>();
    8.31  
    8.32 -    typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
    8.33 +    typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
    8.34      checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    8.35      dijkstraHeapTest<NodeHeap>(digraph, length, source);
    8.36    }
    8.37  
    8.38 -  // KaryHeap
    8.39 +  // DHeap
    8.40    {
    8.41 -    typedef KaryHeap<Prio, ItemIntMap> IntHeap;
    8.42 +    typedef DHeap<Prio, ItemIntMap> IntHeap;
    8.43      checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    8.44      heapSortTest<IntHeap>();
    8.45      heapIncreaseTest<IntHeap>();
    8.46  
    8.47 -    typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
    8.48 +    typedef DHeap<Prio, IntNodeMap > NodeHeap;
    8.49      checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    8.50      dijkstraHeapTest<NodeHeap>(digraph, length, source);
    8.51    }
    8.52 @@ -245,14 +245,14 @@
    8.53      dijkstraHeapTest<NodeHeap>(digraph, length, source);
    8.54    }
    8.55  
    8.56 -  // BinomHeap
    8.57 +  // BinomialHeap
    8.58    {
    8.59 -    typedef BinomHeap<Prio, ItemIntMap> IntHeap;
    8.60 +    typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
    8.61      checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    8.62      heapSortTest<IntHeap>();
    8.63      heapIncreaseTest<IntHeap>();
    8.64  
    8.65 -    typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
    8.66 +    typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
    8.67      checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    8.68      dijkstraHeapTest<NodeHeap>(digraph, length, source);
    8.69    }