COIN-OR::LEMON - Graph Library

Changeset 2547:f393a8162688 in lemon-0.x for lemon/bin_heap.h


Ignore:
Timestamp:
12/27/07 14:40:16 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3424
Message:

Renaming state_enum to State
Removing "Type" suffix from typedefs
Moving implementation into the class definition

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bin_heap.h

    r2546 r2547  
    4040  ///one can change the priority of an item, add or erase an item, etc.
    4141  ///
    42   ///\param Prio Type of the priority of the items.
    43   ///\param ItemIntMap A read and writable Item int map, used internally
     42  ///\param _Prio Type of the priority of the items.
     43  ///\param _ItemIntMap A read and writable Item int map, used internally
    4444  ///to handle the cross references.
    45   ///\param Compare A class for the ordering of the priorities. The
    46   ///default is \c std::less<Prio>.
     45  ///\param _Compare A class for the ordering of the priorities. The
     46  ///default is \c std::less<_Prio>.
    4747  ///
    4848  ///\sa FibHeap
    4949  ///\sa Dijkstra
    50   template <typename Prio, typename ItemIntMap,
    51             typename Compare = std::less<Prio> >
     50  template <typename _Prio, typename _ItemIntMap,
     51            typename _Compare = std::less<_Prio> >
    5252  class BinHeap {
    5353
    5454  public:
    55     typedef typename ItemIntMap::Key         ItemType;
    56     typedef Prio                             PrioType;
    57     typedef std::pair<ItemType,PrioType>     PairType;
    58     typedef ItemIntMap                       ItemIntMapType;
    59     typedef Compare                          PrioCompare;
     55    typedef _ItemIntMap ItemIntMap;
     56    typedef _Prio Prio;
     57    typedef typename ItemIntMap::Key Item;
     58    typedef std::pair<Item,Prio> Pair;
     59    typedef _Compare Compare;
    6060
    6161    /// \brief Type to represent the items states.
     
    6767    /// The ItemIntMap \e should be initialized in such way that it maps
    6868    /// PRE_HEAP (-1) to any element to be put in the heap...
    69     enum state_enum {
     69    enum State {
    7070      IN_HEAP = 0,
    7171      PRE_HEAP = -1,
     
    7474
    7575  private:
    76     std::vector<PairType> data;
     76    std::vector<Pair> data;
    7777    Compare comp;
    7878    ItemIntMap &iim;
     
    123123
    124124    static int second_child(int i) { return 2*i+2; }
    125     bool less(const PairType &p1, const PairType &p2) const {
     125    bool less(const Pair &p1, const Pair &p2) const {
    126126      return comp(p1.second, p2.second);
    127127    }
    128128
    129     int bubble_up(int hole, PairType p) {
     129    int bubble_up(int hole, Pair p) {
    130130      int par = parent(hole);
    131131      while( hole>0 && less(p,data[par]) ) {
     
    138138    }
    139139
    140     int bubble_down(int hole, PairType p, int length) {
     140    int bubble_down(int hole, Pair p, int length) {
    141141      int child = second_child(hole);
    142142      while(child < length) {
     
    160160    }
    161161
    162     void move(const PairType &p, int i) {
     162    void move(const Pair &p, int i) {
    163163      data[i] = p;
    164164      iim.set(p.first, i);
     
    170170    /// Adds \c p.first to the heap with priority \c p.second.
    171171    /// \param p The pair to insert.
    172     void push(const PairType &p) {
     172    void push(const Pair &p) {
    173173      int n = data.size();
    174174      data.resize(n+1);
     
    181181    /// \param i The item to insert.
    182182    /// \param p The priority of the item.
    183     void push(const ItemType &i, const Prio &p) { push(PairType(i,p)); }
     183    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    184184
    185185    /// \brief Returns the item with minimum priority relative to \c Compare.
     
    188188    /// Compare. 
    189189    /// \pre The heap must be nonempty. 
    190     ItemType top() const {
     190    Item top() const {
    191191      return data[0].first;
    192192    }
     
    219219    /// \param i The item to erase.
    220220    /// \pre The item should be in the heap.
    221     void erase(const ItemType &i) {
     221    void erase(const Item &i) {
    222222      int h = iim[i];
    223223      int n = data.size()-1;
     
    237237    /// \pre \c i must be in the heap.
    238238    /// \param i The item.
    239     Prio operator[](const ItemType &i) const {
     239    Prio operator[](const Item &i) const {
    240240      int idx = iim[i];
    241241      return data[idx].second;
     
    249249    /// \param i The item.
    250250    /// \param p The priority.
    251     void set(const ItemType &i, const Prio &p) {
     251    void set(const Item &i, const Prio &p) {
    252252      int idx = iim[i];
    253253      if( idx < 0 ) {
     
    255255      }
    256256      else if( comp(p, data[idx].second) ) {
    257         bubble_up(idx, PairType(i,p));
     257        bubble_up(idx, Pair(i,p));
    258258      }
    259259      else {
    260         bubble_down(idx, PairType(i,p), data.size());
     260        bubble_down(idx, Pair(i,p), data.size());
    261261      }
    262262    }
     
    269269    /// \param i The item.
    270270    /// \param p The priority.
    271     void decrease(const ItemType &i, const Prio &p) {
     271    void decrease(const Item &i, const Prio &p) {
    272272      int idx = iim[i];
    273       bubble_up(idx, PairType(i,p));
     273      bubble_up(idx, Pair(i,p));
    274274    }
    275275   
     
    281281    /// \param i The item.
    282282    /// \param p The priority.
    283     void increase(const ItemType &i, const Prio &p) {
     283    void increase(const Item &i, const Prio &p) {
    284284      int idx = iim[i];
    285       bubble_down(idx, PairType(i,p), data.size());
     285      bubble_down(idx, Pair(i,p), data.size());
    286286    }
    287287
     
    294294    /// get back to the heap again.
    295295    /// \param i The item.
    296     state_enum state(const ItemType &i) const {
     296    State state(const Item &i) const {
    297297      int s = iim[i];
    298298      if( s>=0 )
    299299        s=0;
    300       return state_enum(s);
     300      return State(s);
    301301    }
    302302
     
    308308    /// \param i The item.
    309309    /// \param st The state. It should not be \c IN_HEAP.
    310     void state(const ItemType& i, state_enum st) {
     310    void state(const Item& i, State st) {
    311311      switch (st) {
    312312      case POST_HEAP:
Note: See TracChangeset for help on using the changeset viewer.