COIN-OR::LEMON - Graph Library

Changeset 729:bb8c4cd57900 in lemon


Ignore:
Timestamp:
06/11/09 22:16:11 (9 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Message:

Simplified implementation of bucket heaps (#50)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bucket_heap.h

    r728 r729  
    3030namespace lemon { 
    3131 
     32  namespace _bucket_heap_bits { 
     33 
     34    template <bool minimize> 
     35    struct DirectionTraits { 
     36      static bool less(int left, int right) { 
     37        return left < right; 
     38      } 
     39      static void increase(int& value) { 
     40        ++value; 
     41      } 
     42    }; 
     43 
     44    template <> 
     45    struct DirectionTraits<false> { 
     46      static bool less(int left, int right) { 
     47        return left > right; 
     48      } 
     49      static void increase(int& value) { 
     50        --value; 
     51      } 
     52    }; 
     53 
     54  } 
     55 
    3256  /// \ingroup auxdat 
    3357  /// 
     
    4670  /// \param minimize If the given parameter is true then the heap gives back 
    4771  /// the lowest priority. 
    48   template <typename _ItemIntMap, bool minimize = true > 
     72  template <typename _ItemIntMap, bool minimize = true> 
    4973  class BucketHeap { 
    5074 
     
    5882    /// \e 
    5983    typedef _ItemIntMap ItemIntMap; 
     84 
     85  private: 
     86 
     87    typedef _bucket_heap_bits::DirectionTraits<minimize> Direction; 
     88 
     89  public: 
    6090 
    6191    /// \brief Type to represent the items states. 
     
    162192      data.push_back(BucketItem(i, p)); 
    163193      lace(idx); 
    164       if (p < minimal) { 
     194      if (Direction::less(p, minimal)) { 
    165195        minimal = p; 
    166196      } 
     
    173203    Item top() const { 
    174204      while (first[minimal] == -1) { 
    175         ++minimal; 
     205        Direction::increase(minimal); 
    176206      } 
    177207      return data[first[minimal]].item; 
     
    184214    Prio prio() const { 
    185215      while (first[minimal] == -1) { 
    186         ++minimal; 
     216        Direction::increase(minimal); 
    187217      } 
    188218      return minimal; 
     
    195225    void pop() { 
    196226      while (first[minimal] == -1) { 
    197         ++minimal; 
     227        Direction::increase(minimal); 
    198228      } 
    199229      int idx = first[minimal]; 
     
    236266      int idx = index[i]; 
    237267      if (idx < 0) { 
    238         push(i,p); 
    239       } else if (p > data[idx].value) { 
     268        push(i, p); 
     269      } else if (Direction::less(p, data[idx].value)) { 
     270        decrease(i, p); 
     271      } else { 
    240272        increase(i, p); 
    241       } else { 
    242         decrease(i, p); 
    243273      } 
    244274    } 
     
    255285      unlace(idx); 
    256286      data[idx].value = p; 
    257       if (p < minimal) { 
     287      if (Direction::less(p, minimal)) { 
    258288        minimal = p; 
    259289      } 
     
    329359  }; // class BucketHeap 
    330360 
    331  
    332   template <typename _ItemIntMap> 
    333   class BucketHeap<_ItemIntMap, false> { 
    334  
    335   public: 
    336     typedef typename _ItemIntMap::Key Item; 
    337     typedef int Prio; 
    338     typedef std::pair<Item, Prio> Pair; 
    339     typedef _ItemIntMap ItemIntMap; 
    340  
    341     enum State { 
    342       IN_HEAP = 0, 
    343       PRE_HEAP = -1, 
    344       POST_HEAP = -2 
    345     }; 
    346  
    347   public: 
    348  
    349     explicit BucketHeap(ItemIntMap &_index) : index(_index), maximal(-1) {} 
    350  
    351     int size() const { return data.size(); } 
    352     bool empty() const { return data.empty(); } 
    353  
    354     void clear() { 
    355       data.clear(); first.clear(); maximal = -1; 
    356     } 
    357  
    358   private: 
    359  
    360     void relocate_last(int idx) { 
    361       if (idx + 1 != int(data.size())) { 
    362         data[idx] = data.back(); 
    363         if (data[idx].prev != -1) { 
    364           data[data[idx].prev].next = idx; 
    365         } else { 
    366           first[data[idx].value] = idx; 
    367         } 
    368         if (data[idx].next != -1) { 
    369           data[data[idx].next].prev = idx; 
    370         } 
    371         index[data[idx].item] = idx; 
    372       } 
    373       data.pop_back(); 
    374     } 
    375  
    376     void unlace(int idx) { 
    377       if (data[idx].prev != -1) { 
    378         data[data[idx].prev].next = data[idx].next; 
    379       } else { 
    380         first[data[idx].value] = data[idx].next; 
    381       } 
    382       if (data[idx].next != -1) { 
    383         data[data[idx].next].prev = data[idx].prev; 
    384       } 
    385     } 
    386  
    387     void lace(int idx) { 
    388       if (int(first.size()) <= data[idx].value) { 
    389         first.resize(data[idx].value + 1, -1); 
    390       } 
    391       data[idx].next = first[data[idx].value]; 
    392       if (data[idx].next != -1) { 
    393         data[data[idx].next].prev = idx; 
    394       } 
    395       first[data[idx].value] = idx; 
    396       data[idx].prev = -1; 
    397     } 
    398  
    399   public: 
    400  
    401     void push(const Pair& p) { 
    402       push(p.first, p.second); 
    403     } 
    404  
    405     void push(const Item &i, const Prio &p) { 
    406       int idx = data.size(); 
    407       index[i] = idx; 
    408       data.push_back(BucketItem(i, p)); 
    409       lace(idx); 
    410       if (data[idx].value > maximal) { 
    411         maximal = data[idx].value; 
    412       } 
    413     } 
    414  
    415     Item top() const { 
    416       while (first[maximal] == -1) { 
    417         --maximal; 
    418       } 
    419       return data[first[maximal]].item; 
    420     } 
    421  
    422     Prio prio() const { 
    423       while (first[maximal] == -1) { 
    424         --maximal; 
    425       } 
    426       return maximal; 
    427     } 
    428  
    429     void pop() { 
    430       while (first[maximal] == -1) { 
    431         --maximal; 
    432       } 
    433       int idx = first[maximal]; 
    434       index[data[idx].item] = -2; 
    435       unlace(idx); 
    436       relocate_last(idx); 
    437     } 
    438  
    439     void erase(const Item &i) { 
    440       int idx = index[i]; 
    441       index[data[idx].item] = -2; 
    442       unlace(idx); 
    443       relocate_last(idx); 
    444     } 
    445  
    446     Prio operator[](const Item &i) const { 
    447       int idx = index[i]; 
    448       return data[idx].value; 
    449     } 
    450  
    451     void set(const Item &i, const Prio &p) { 
    452       int idx = index[i]; 
    453       if (idx < 0) { 
    454         push(i,p); 
    455       } else if (p > data[idx].value) { 
    456         decrease(i, p); 
    457       } else { 
    458         increase(i, p); 
    459       } 
    460     } 
    461  
    462     void decrease(const Item &i, const Prio &p) { 
    463       int idx = index[i]; 
    464       unlace(idx); 
    465       data[idx].value = p; 
    466       if (p > maximal) { 
    467         maximal = p; 
    468       } 
    469       lace(idx); 
    470     } 
    471  
    472     void increase(const Item &i, const Prio &p) { 
    473       int idx = index[i]; 
    474       unlace(idx); 
    475       data[idx].value = p; 
    476       lace(idx); 
    477     } 
    478  
    479     State state(const Item &i) const { 
    480       int idx = index[i]; 
    481       if (idx >= 0) idx = 0; 
    482       return State(idx); 
    483     } 
    484  
    485     void state(const Item& i, State st) { 
    486       switch (st) { 
    487       case POST_HEAP: 
    488       case PRE_HEAP: 
    489         if (state(i) == IN_HEAP) { 
    490           erase(i); 
    491         } 
    492         index[i] = st; 
    493         break; 
    494       case IN_HEAP: 
    495         break; 
    496       } 
    497     } 
    498  
    499   private: 
    500  
    501     struct BucketItem { 
    502       BucketItem(const Item& _item, int _value) 
    503         : item(_item), value(_value) {} 
    504  
    505       Item item; 
    506       int value; 
    507  
    508       int prev, next; 
    509     }; 
    510  
    511     ItemIntMap& index; 
    512     std::vector<int> first; 
    513     std::vector<BucketItem> data; 
    514     mutable int maximal; 
    515  
    516   }; // class BucketHeap 
    517  
    518361  /// \ingroup auxdat 
    519362  /// 
     
    525368  /// difference is that the BucketHeap stores for every key a double 
    526369  /// linked list while this class stores just simple lists. In the 
    527   /// other way it does not supports erasing each elements just the 
     370  /// other way it does not support erasing each elements just the 
    528371  /// minimal and it does not supports key increasing, decreasing. 
    529372  /// 
     
    542385    typedef std::pair<Item, Prio> Pair; 
    543386    typedef _ItemIntMap ItemIntMap; 
     387 
     388  private: 
     389 
     390    typedef _bucket_heap_bits::DirectionTraits<minimize> Direction; 
     391 
     392  public: 
    544393 
    545394    /// \brief Type to represent the items states. 
     
    615464      data[idx].next = first[p]; 
    616465      first[p] = idx; 
    617       if (p < minimal) { 
     466      if (Direction::less(p, minimal)) { 
    618467        minimal = p; 
    619468      } 
     
    627476    Item top() const { 
    628477      while (first[minimal] == -1) { 
    629         ++minimal; 
     478        Direction::increase(minimal); 
    630479      } 
    631480      return data[first[minimal]].item; 
     
    638487    Prio prio() const { 
    639488      while (first[minimal] == -1) { 
    640         ++minimal; 
     489        Direction::increase(minimal); 
    641490      } 
    642491      return minimal; 
     
    649498    void pop() { 
    650499      while (first[minimal] == -1) { 
    651         ++minimal; 
     500        Direction::increase(minimal); 
    652501      } 
    653502      int idx = first[minimal]; 
     
    712561  }; // class SimpleBucketHeap 
    713562 
    714   template <typename _ItemIntMap> 
    715   class SimpleBucketHeap<_ItemIntMap, false> { 
    716  
    717   public: 
    718     typedef typename _ItemIntMap::Key Item; 
    719     typedef int Prio; 
    720     typedef std::pair<Item, Prio> Pair; 
    721     typedef _ItemIntMap ItemIntMap; 
    722  
    723     enum State { 
    724       IN_HEAP = 0, 
    725       PRE_HEAP = -1, 
    726       POST_HEAP = -2 
    727     }; 
    728  
    729   public: 
    730  
    731     explicit SimpleBucketHeap(ItemIntMap &_index) 
    732       : index(_index), free(-1), num(0), maximal(0) {} 
    733  
    734     int size() const { return num; } 
    735  
    736     bool empty() const { return num == 0; } 
    737  
    738     void clear() { 
    739       data.clear(); first.clear(); free = -1; num = 0; maximal = 0; 
    740     } 
    741  
    742     void push(const Pair& p) { 
    743       push(p.first, p.second); 
    744     } 
    745  
    746     void push(const Item &i, const Prio &p) { 
    747       int idx; 
    748       if (free == -1) { 
    749         idx = data.size(); 
    750         data.push_back(BucketItem(i)); 
    751       } else { 
    752         idx = free; 
    753         free = data[idx].next; 
    754         data[idx].item = i; 
    755       } 
    756       index[i] = idx; 
    757       if (p >= int(first.size())) first.resize(p + 1, -1); 
    758       data[idx].next = first[p]; 
    759       first[p] = idx; 
    760       if (p > maximal) { 
    761         maximal = p; 
    762       } 
    763       ++num; 
    764     } 
    765  
    766     Item top() const { 
    767       while (first[maximal] == -1) { 
    768         --maximal; 
    769       } 
    770       return data[first[maximal]].item; 
    771     } 
    772  
    773     Prio prio() const { 
    774       while (first[maximal] == -1) { 
    775         --maximal; 
    776       } 
    777       return maximal; 
    778     } 
    779  
    780     void pop() { 
    781       while (first[maximal] == -1) { 
    782         --maximal; 
    783       } 
    784       int idx = first[maximal]; 
    785       index[data[idx].item] = -2; 
    786       first[maximal] = data[idx].next; 
    787       data[idx].next = free; 
    788       free = idx; 
    789       --num; 
    790     } 
    791  
    792     Prio operator[](const Item &i) const { 
    793       for (int k = 0; k < first.size(); ++k) { 
    794         int idx = first[k]; 
    795         while (idx != -1) { 
    796           if (data[idx].item == i) { 
    797             return k; 
    798           } 
    799           idx = data[idx].next; 
    800         } 
    801       } 
    802       return -1; 
    803     } 
    804  
    805     State state(const Item &i) const { 
    806       int idx = index[i]; 
    807       if (idx >= 0) idx = 0; 
    808       return State(idx); 
    809     } 
    810  
    811   private: 
    812  
    813     struct BucketItem { 
    814       BucketItem(const Item& _item) : item(_item) {} 
    815  
    816       Item item; 
    817  
    818       int next; 
    819     }; 
    820  
    821     ItemIntMap& index; 
    822     std::vector<int> first; 
    823     std::vector<BucketItem> data; 
    824     int free, num; 
    825     mutable int maximal; 
    826  
    827   }; 
    828  
    829563} 
    830564 
Note: See TracChangeset for help on using the changeset viewer.