COIN-OR::LEMON - Graph Library

Changeset 730:9f529abcaebf in lemon for lemon/radix_heap.h


Ignore:
Timestamp:
06/11/09 23:13:24 (10 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Children:
733:7439dc5fe1b9, 738:9e54e3b27db0, 740:7bda7860e0a8, 743:c9b9da1a90a0, 748:d1a9224f1e30, 756:0747f332c478, 760:4ac30454f1c1, 765:703ebf476a1d, 805:b31e130db13d
Phase:
public
Message:

Unification of names in heaps (#50)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/radix_heap.h

    r728 r730  
    4242  /// item's priority.
    4343  ///
    44   /// \param _ItemIntMap A read and writable Item int map, used internally
     44  /// \param IM A read and writable Item int map, used internally
    4545  /// to handle the cross references.
    4646  ///
    4747  /// \see BinHeap
    4848  /// \see Dijkstra
    49   template <typename _ItemIntMap>
     49  template <typename IM>
    5050  class RadixHeap {
    5151
    5252  public:
    53     typedef typename _ItemIntMap::Key Item;
     53    typedef typename IM::Key Item;
    5454    typedef int Prio;
    55     typedef _ItemIntMap ItemIntMap;
     55    typedef IM ItemIntMap;
    5656
    5757    /// \brief Exception thrown by RadixHeap.
     
    100100    std::vector<RadixBox> boxes;
    101101
    102     ItemIntMap &iim;
     102    ItemIntMap &_iim;
    103103
    104104
     
    108108    /// The constructor.
    109109    ///
    110     /// \param _iim It should be given to the constructor, since it is used
     110    /// \param map It should be given to the constructor, since it is used
    111111    /// internally to handle the cross references. The value of the map
    112112    /// should be PRE_HEAP (-1) for each element.
     
    114114    /// \param minimal The initial minimal value of the heap.
    115115    /// \param capacity It determines the initial capacity of the heap.
    116     RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
    117       : iim(_iim) {
     116    RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
     117      : _iim(map) {
    118118      boxes.push_back(RadixBox(minimal, 1));
    119119      boxes.push_back(RadixBox(minimal + 1, 1));
     
    269269          data[data[index].next].prev = index;
    270270        }
    271         iim[data[index].item] = index;
     271        _iim[data[index].item] = index;
    272272      }
    273273      data.pop_back();
     
    283283    void push(const Item &i, const Prio &p) {
    284284      int n = data.size();
    285       iim.set(i, n);
     285      _iim.set(i, n);
    286286      data.push_back(RadixItem(i, p));
    287287      while (lower(boxes.size() - 1, p)) {
     
    317317      moveDown();
    318318      int index = boxes[0].first;
    319       iim[data[index].item] = POST_HEAP;
     319      _iim[data[index].item] = POST_HEAP;
    320320      remove(index);
    321321      relocate_last(index);
     
    328328    /// \param i The item to erase.
    329329    void erase(const Item &i) {
    330       int index = iim[i];
    331       iim[i] = POST_HEAP;
     330      int index = _iim[i];
     331      _iim[i] = POST_HEAP;
    332332      remove(index);
    333333      relocate_last(index);
     
    340340    /// \param i The item.
    341341    Prio operator[](const Item &i) const {
    342       int idx = iim[i];
     342      int idx = _iim[i];
    343343      return data[idx].prio;
    344344    }
     
    353353    /// \param p The priority.
    354354    void set(const Item &i, const Prio &p) {
    355       int idx = iim[i];
     355      int idx = _iim[i];
    356356      if( idx < 0 ) {
    357357        push(i, p);
     
    375375    /// \param p The priority.
    376376    void decrease(const Item &i, const Prio &p) {
    377       int idx = iim[i];
     377      int idx = _iim[i];
    378378      data[idx].prio = p;
    379379      bubble_down(idx);
     
    387387    /// \param p The priority.
    388388    void increase(const Item &i, const Prio &p) {
    389       int idx = iim[i];
     389      int idx = _iim[i];
    390390      data[idx].prio = p;
    391391      bubble_up(idx);
     
    401401    /// \param i The item.
    402402    State state(const Item &i) const {
    403       int s = iim[i];
     403      int s = _iim[i];
    404404      if( s >= 0 ) s = 0;
    405405      return State(s);
     
    420420          erase(i);
    421421        }
    422         iim[i] = st;
     422        _iim[i] = st;
    423423        break;
    424424      case IN_HEAP:
Note: See TracChangeset for help on using the changeset viewer.