COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 682:bb8c4cd57900 in lemon-main


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

Simplified implementation of bucket heaps (#50)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/bucket_heap.h

    r681 r682  
    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.