COIN-OR::LEMON - Graph Library

Changeset 2263:9273fe7d850c in lemon-0.x for lemon/bin_heap.h


Ignore:
Timestamp:
10/26/06 16:20:17 (14 years ago)
Author:
mqrelly
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3021
Message:

Bug #46 fixed: Superfluous template parameter in Heap concept
NOTE: Not every affected file tested.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bin_heap.h

    r2258 r2263  
    4040  ///one can change the priority of an item, add or erase an item, etc.
    4141  ///
    42   ///\param Item Type of the items to be stored. 
    4342  ///\param Prio Type of the priority of the items.
    4443  ///\param ItemIntMap A read and writable Item int map, used internally
     
    4948  ///\sa FibHeap
    5049  ///\sa Dijkstra
    51   template <typename Item, typename Prio, typename ItemIntMap,
     50  template <typename Prio, typename ItemIntMap,
    5251            typename Compare = std::less<Prio> >
    5352  class BinHeap {
    5453
    5554  public:
    56     typedef Item                             ItemType;
     55    typedef typename ItemIntMap::Key         ItemType;
    5756    typedef Prio                             PrioType;
    5857    typedef std::pair<ItemType,PrioType>     PairType;
     
    162161    /// \param i The item to insert.
    163162    /// \param p The priority of the item.
    164     void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
     163    void push(const ItemType &i, const Prio &p) { push(PairType(i,p)); }
    165164
    166165    /// \brief Returns the item with minimum priority relative to \c Compare.
     
    169168    /// Compare. 
    170169    /// \pre The heap must be nonempty. 
    171     Item top() const {
     170    ItemType top() const {
    172171      return data[0].first;
    173172    }
     
    195194    /// already stored in the heap.
    196195    /// \param i The item to erase.
    197     void erase(const Item &i) {
     196    void erase(const ItemType &i) {
    198197      rmidx(iim[i]);
    199198    }
     
    205204    /// \pre \c i must be in the heap.
    206205    /// \param i The item.
    207     Prio operator[](const Item &i) const {
     206    Prio operator[](const ItemType &i) const {
    208207      int idx = iim[i];
    209208      return data[idx].second;
     
    217216    /// \param i The item.
    218217    /// \param p The priority.
    219     void set(const Item &i, const Prio &p) {
     218    void set(const ItemType &i, const Prio &p) {
    220219      int idx = iim[i];
    221220      if( idx < 0 ) {
     
    237236    /// \param i The item.
    238237    /// \param p The priority.
    239     void decrease(const Item &i, const Prio &p) {
     238    void decrease(const ItemType &i, const Prio &p) {
    240239      int idx = iim[i];
    241240      bubble_up(idx, PairType(i,p));
     
    249248    /// \param i The item.
    250249    /// \param p The priority.
    251     void increase(const Item &i, const Prio &p) {
     250    void increase(const ItemType &i, const Prio &p) {
    252251      int idx = iim[i];
    253252      bubble_down(idx, PairType(i,p), data.size());
     
    262261    /// get back to the heap again.
    263262    /// \param i The item.
    264     state_enum state(const Item &i) const {
     263    state_enum state(const ItemType &i) const {
    265264      int s = iim[i];
    266265      if( s>=0 )
     
    276275    /// \param i The item.
    277276    /// \param st The state. It should not be \c IN_HEAP.
    278     void state(const Item& i, state_enum st) {
     277    void state(const ItemType& i, state_enum st) {
    279278      switch (st) {
    280279      case POST_HEAP:
     
    293292
    294293 
    295   template <typename K, typename V, typename M, typename C>
    296   int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
     294  template <typename V, typename M, typename C>
     295  int BinHeap<V,M,C>::bubble_up(int hole, PairType p) {
    297296    int par = parent(hole);
    298297    while( hole>0 && less(p,data[par]) ) {
     
    305304  }
    306305
    307   template <typename K, typename V, typename M, typename C>
    308   int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
     306  template <typename V, typename M, typename C>
     307  int BinHeap<V,M,C>::bubble_down(int hole, PairType p, int length) {
    309308    int child = second_child(hole);
    310309    while(child < length) {
Note: See TracChangeset for help on using the changeset viewer.