COIN-OR::LEMON - Graph Library

Changeset 751:7124b2581f72 in lemon for lemon/kary_heap.h


Ignore:
Timestamp:
07/10/09 09:15:22 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Make K a template parameter in KaryHeap? (#301)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/kary_heap.h

    r750 r751  
    4646  /// \tparam IM A read-writable item map with \c int values, used
    4747  /// internally to handle the cross references.
     48  /// \tparam K The degree of the heap, each node have at most \e K
     49  /// children. The default is 16. Powers of two are suggested to use
     50  /// so that the multiplications and divisions needed to traverse the
     51  /// nodes of the heap could be performed faster.
    4852  /// \tparam CMP A functor class for comparing the priorities.
    4953  /// The default is \c std::less<PR>.
     
    5256  ///\sa FouraryHeap
    5357#ifdef DOXYGEN
    54   template <typename PR, typename IM, typename CMP>
     58  template <typename PR, typename IM, int K, typename CMP>
    5559#else
    56   template <typename PR, typename IM, typename CMP = std::less<PR> >
     60  template <typename PR, typename IM, int K = 16,
     61            typename CMP = std::less<PR> >
    5762#endif
    5863  class KaryHeap {
     
    8792    Compare _comp;
    8893    ItemIntMap &_iim;
    89     int _K;
    9094
    9195  public:
     
    96100    /// It is used internally to handle the cross references.
    97101    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    98     explicit KaryHeap(ItemIntMap &map, int K=32) : _iim(map), _K(K) {}
     102    explicit KaryHeap(ItemIntMap &map) : _iim(map) {}
    99103
    100104    /// \brief Constructor.
     
    105109    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    106110    /// \param comp The function object used for comparing the priorities.
    107     KaryHeap(ItemIntMap &map, const Compare &comp, int K=32)
    108       : _iim(map), _comp(comp), _K(K) {}
     111    KaryHeap(ItemIntMap &map, const Compare &comp)
     112      : _iim(map), _comp(comp) {}
    109113
    110114    /// \brief The number of items stored in the heap.
     
    128132
    129133  private:
    130     int parent(int i) { return (i-1)/_K; }
    131     int firstChild(int i) { return _K*i+1; }
     134    int parent(int i) { return (i-1)/K; }
     135    int firstChild(int i) { return K*i+1; }
    132136
    133137    bool less(const Pair &p1, const Pair &p2) const {
     
    137141    int findMin(const int child, const int length) {
    138142      int min=child, i=1;
    139       while( i<_K && child+i<length ) {
     143      while( i<K && child+i<length ) {
    140144        if( less(_data[child+i], _data[min]) )
    141145          min=child+i;
Note: See TracChangeset for help on using the changeset viewer.