COIN-OR::LEMON - Graph Library

Changeset 209:765619b7cbb2 in lemon-1.2 for lemon/bin_heap.h


Ignore:
Timestamp:
07/13/08 20:51:02 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bin_heap.h

    r157 r209  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
     
    4949  ///\sa Dijkstra
    5050  template <typename _Prio, typename _ItemIntMap,
    51             typename _Compare = std::less<_Prio> >
     51            typename _Compare = std::less<_Prio> >
    5252  class BinHeap {
    5353
     
    9191    /// should be PRE_HEAP (-1) for each element.
    9292    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
    93    
     93
    9494    /// \brief The constructor.
    9595    ///
     
    100100    ///
    101101    /// \param _comp The comparator function object.
    102     BinHeap(ItemIntMap &_iim, const Compare &_comp) 
     102    BinHeap(ItemIntMap &_iim, const Compare &_comp)
    103103      : iim(_iim), comp(_comp) {}
    104104
     
    108108    /// \brief Returns the number of items stored in the heap.
    109109    int size() const { return data.size(); }
    110    
     110
    111111    /// \brief Checks if the heap stores no items.
    112112    ///
     
    115115
    116116    /// \brief Make empty this heap.
    117     /// 
     117    ///
    118118    /// Make empty this heap. It does not change the cross reference map.
    119119    /// If you want to reuse what is not surely empty you should first clear
    120120    /// the heap and after that you should set the cross reference map for
    121121    /// each item to \c PRE_HEAP.
    122     void clear() { 
    123       data.clear(); 
     122    void clear() {
     123      data.clear();
    124124    }
    125125
     
    135135      int par = parent(hole);
    136136      while( hole>0 && less(p,data[par]) ) {
    137         move(data[par],hole);
    138         hole = par;
    139         par = parent(hole);
     137        move(data[par],hole);
     138        hole = par;
     139        par = parent(hole);
    140140      }
    141141      move(p, hole);
     
    146146      int child = second_child(hole);
    147147      while(child < length) {
    148         if( less(data[child-1], data[child]) ) {
    149           --child;
    150         }
    151         if( !less(data[child], p) )
    152           goto ok;
    153         move(data[child], hole);
    154         hole = child;
    155         child = second_child(hole);
     148        if( less(data[child-1], data[child]) ) {
     149          --child;
     150        }
     151        if( !less(data[child], p) )
     152          goto ok;
     153        move(data[child], hole);
     154        hole = child;
     155        child = second_child(hole);
    156156      }
    157157      child--;
    158158      if( child<length && less(data[child], p) ) {
    159         move(data[child], hole);
    160         hole=child;
     159        move(data[child], hole);
     160        hole=child;
    161161      }
    162162    ok:
     
    182182
    183183    /// \brief Insert an item into the heap with the given heap.
    184     ///   
    185     /// Adds \c i to the heap with priority \c p. 
     184    ///
     185    /// Adds \c i to the heap with priority \c p.
    186186    /// \param i The item to insert.
    187187    /// \param p The priority of the item.
     
    191191    ///
    192192    /// This method returns the item with minimum priority relative to \c
    193     /// Compare. 
    194     /// \pre The heap must be nonempty. 
     193    /// Compare.
     194    /// \pre The heap must be nonempty.
    195195    Item top() const {
    196196      return data[0].first;
     
    208208    ///
    209209    /// This method deletes the item with minimum priority relative to \c
    210     /// Compare from the heap. 
    211     /// \pre The heap must be non-empty. 
     210    /// Compare from the heap.
     211    /// \pre The heap must be non-empty.
    212212    void pop() {
    213213      int n = data.size()-1;
    214214      iim.set(data[0].first, POST_HEAP);
    215215      if (n > 0) {
    216         bubble_down(0, data[n], n);
     216        bubble_down(0, data[n], n);
    217217      }
    218218      data.pop_back();
     
    229229      iim.set(data[h].first, POST_HEAP);
    230230      if( h < n ) {
    231         if ( bubble_up(h, data[n]) == h) {
    232           bubble_down(h, data[n], n);
    233         }
     231        if ( bubble_up(h, data[n]) == h) {
     232          bubble_down(h, data[n], n);
     233        }
    234234      }
    235235      data.pop_back();
    236236    }
    237237
    238    
     238
    239239    /// \brief Returns the priority of \c i.
    240240    ///
    241     /// This function returns the priority of item \c i. 
     241    /// This function returns the priority of item \c i.
    242242    /// \pre \c i must be in the heap.
    243243    /// \param i The item.
     
    247247    }
    248248
    249     /// \brief \c i gets to the heap with priority \c p independently 
     249    /// \brief \c i gets to the heap with priority \c p independently
    250250    /// if \c i was already there.
    251251    ///
     
    257257      int idx = iim[i];
    258258      if( idx < 0 ) {
    259         push(i,p);
     259        push(i,p);
    260260      }
    261261      else if( comp(p, data[idx].second) ) {
    262         bubble_up(idx, Pair(i,p));
     262        bubble_up(idx, Pair(i,p));
    263263      }
    264264      else {
    265         bubble_down(idx, Pair(i,p), data.size());
     265        bubble_down(idx, Pair(i,p), data.size());
    266266      }
    267267    }
     
    278278      bubble_up(idx, Pair(i,p));
    279279    }
    280    
     280
    281281    /// \brief Increases the priority of \c i to \c p.
    282282    ///
    283     /// This method sets the priority of item \c i to \c p. 
     283    /// This method sets the priority of item \c i to \c p.
    284284    /// \pre \c i must be stored in the heap with priority at most \c
    285285    /// p relative to \c Compare.
     
    291291    }
    292292
    293     /// \brief Returns if \c item is in, has already been in, or has 
     293    /// \brief Returns if \c item is in, has already been in, or has
    294294    /// never been in the heap.
    295295    ///
     
    302302      int s = iim[i];
    303303      if( s>=0 )
    304         s=0;
     304        s=0;
    305305      return State(s);
    306306    }
     
    312312    /// better time complexity.
    313313    /// \param i The item.
    314     /// \param st The state. It should not be \c IN_HEAP. 
     314    /// \param st The state. It should not be \c IN_HEAP.
    315315    void state(const Item& i, State st) {
    316316      switch (st) {
     
    341341
    342342  }; // class BinHeap
    343  
     343
    344344} // namespace lemon
    345345
Note: See TracChangeset for help on using the changeset viewer.