linear_heap.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_LINEAR_HEAP_H
00020 #define LEMON_LINEAR_HEAP_H
00021 
00025 
00026 #include <vector>
00027 #include <utility>
00028 #include <functional>
00029 
00030 namespace lemon {
00031 
00033 
00049   template <typename _Item, typename _ItemIntMap, bool minimize = true >
00050   class LinearHeap {
00051 
00052   public:
00053     typedef _Item Item;
00054     typedef int Prio;
00055     typedef std::pair<Item, Prio> Pair;
00056     typedef _ItemIntMap ItemIntMap;
00057 
00066     enum state_enum {
00067       IN_HEAP = 0,
00068       PRE_HEAP = -1,
00069       POST_HEAP = -2
00070     };
00071 
00072   public:
00079     explicit LinearHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
00080     
00084     int size() const { return data.size(); }
00085     
00089     bool empty() const { return data.empty(); }
00090 
00094     void clear() { 
00095       for (int i = 0; i < (int)data.size(); ++i) {
00096         index[data[i].item] = -2;
00097       }
00098       data.clear(); first.clear(); minimal = 0;
00099     }
00100 
00101   private:
00102 
00103     void relocate_last(int idx) {
00104       if (idx + 1 < (int)data.size()) {
00105         data[idx] = data.back();
00106         if (data[idx].prev != -1) {
00107           data[data[idx].prev].next = idx;
00108         } else {
00109           first[data[idx].value] = idx;
00110         }
00111         if (data[idx].next != -1) {
00112           data[data[idx].next].prev = idx;
00113         }
00114         index[data[idx].item] = idx;
00115       }
00116       data.pop_back();
00117     }
00118 
00119     void unlace(int idx) {
00120       if (data[idx].prev != -1) {
00121         data[data[idx].prev].next = data[idx].next;
00122       } else {
00123         first[data[idx].value] = data[idx].next;
00124       }
00125       if (data[idx].next != -1) {
00126         data[data[idx].next].prev = data[idx].prev;
00127       }
00128     }
00129 
00130     void lace(int idx) {
00131       if ((int)first.size() <= data[idx].value) {
00132         first.resize(data[idx].value + 1, -1);
00133       }
00134       data[idx].next = first[data[idx].value];
00135       if (data[idx].next != -1) {
00136         data[data[idx].next].prev = idx;
00137       }
00138       first[data[idx].value] = idx;
00139       data[idx].prev = -1;
00140     }
00141 
00142   public:
00147     void push(const Pair& p) {
00148       push(p.first, p.second);
00149     }
00150 
00156     void push(const Item &i, const Prio &p) { 
00157       int idx = data.size();
00158       index[i] = idx;
00159       data.push_back(LinearItem(i, p));
00160       lace(idx);
00161       if (p < minimal) {
00162         minimal = p;
00163       }
00164     }
00165 
00170     Item top() const {
00171       while (first[minimal] == -1) {
00172         ++minimal;
00173       }
00174       return data[first[minimal]].item;
00175     }
00176 
00181     Prio prio() const {
00182       while (first[minimal] == -1) {
00183         ++minimal;
00184       }
00185       return minimal;
00186     }
00187 
00192     void pop() {
00193       while (first[minimal] == -1) {
00194         ++minimal;
00195       }
00196       int idx = first[minimal];
00197       index[data[idx].item] = -2;
00198       unlace(idx);
00199       relocate_last(idx);
00200     }
00201 
00207     void erase(const Item &i) {
00208       int idx = index[i];
00209       index[data[idx].item] = -2;
00210       unlace(idx);
00211       relocate_last(idx);
00212     }
00213 
00214     
00220     Prio operator[](const Item &i) const {
00221       int idx = index[i];
00222       return data[idx].value;
00223     }
00224 
00232     void set(const Item &i, const Prio &p) {
00233       int idx = index[i];
00234       if (idx < 0) {
00235         push(i,p);
00236       } else if (p > data[idx].value) {
00237         increase(i, p);
00238       } else {
00239         decrease(i, p);
00240       }
00241     }
00242 
00244 
00250     void decrease(const Item &i, const Prio &p) {
00251       int idx = index[i];
00252       unlace(idx);
00253       data[idx].value = p;
00254       if (p < minimal) {
00255         minimal = p;
00256       }
00257       lace(idx);
00258     }
00259     
00267     void increase(const Item &i, const Prio &p) {
00268       int idx = index[i];
00269       unlace(idx);
00270       data[idx].value = p;
00271       lace(idx);
00272     }
00273 
00282     state_enum state(const Item &i) const {
00283       int idx = index[i];
00284       if (idx >= 0) idx = 0;
00285       return state_enum(idx);
00286     }
00287 
00295     void state(const Item& i, state_enum st) {
00296       switch (st) {
00297       case POST_HEAP:
00298       case PRE_HEAP:
00299         if (state(i) == IN_HEAP) {
00300           erase(i);
00301         }
00302         index[i] = st;
00303         break;
00304       case IN_HEAP:
00305         break;
00306       }
00307     }
00308 
00309   private:
00310 
00311     struct LinearItem {
00312       LinearItem(const Item& _item, int _value) 
00313         : item(_item), value(_value) {}
00314 
00315       Item item;
00316       int value;
00317 
00318       int prev, next;
00319     };
00320 
00321     ItemIntMap& index;
00322     std::vector<int> first;
00323     std::vector<LinearItem> data;
00324     mutable int minimal;
00325 
00326   }; // class LinearHeap
00327 
00328 
00329   template <typename _Item, typename _ItemIntMap>
00330   class LinearHeap<_Item, _ItemIntMap, false> {
00331 
00332   public:
00333     typedef _Item Item;
00334     typedef int Prio;
00335     typedef std::pair<Item, Prio> Pair;
00336     typedef _ItemIntMap ItemIntMap;
00337 
00338     enum state_enum {
00339       IN_HEAP = 0,
00340       PRE_HEAP = -1,
00341       POST_HEAP = -2
00342     };
00343 
00344   public:
00345 
00346     explicit LinearHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
00347 
00348     int size() const { return data.size(); }
00349     bool empty() const { return data.empty(); }
00350 
00351     void clear() { 
00352       for (int i = 0; i < (int)data.size(); ++i) {
00353         index[data[i].item] = -2;
00354       }
00355       data.clear(); first.clear(); maximal = -1; 
00356     }
00357 
00358   private:
00359 
00360     void relocate_last(int idx) {
00361       if (idx + 1 != (int)data.size()) {
00362         data[idx] = data.back();
00363         if (data[idx].prev != -1) {
00364           data[data[idx].prev].next = idx;
00365         } else {
00366           first[data[idx].value] = idx;
00367         }
00368         if (data[idx].next != -1) {
00369           data[data[idx].next].prev = idx;
00370         }
00371         index[data[idx].item] = idx;
00372       }
00373       data.pop_back();
00374     }
00375 
00376     void unlace(int idx) {
00377       if (data[idx].prev != -1) {
00378         data[data[idx].prev].next = data[idx].next;
00379       } else {
00380         first[data[idx].value] = data[idx].next;
00381       }
00382       if (data[idx].next != -1) {
00383         data[data[idx].next].prev = data[idx].prev;
00384       }
00385     }
00386 
00387     void lace(int idx) {
00388       if ((int)first.size() <= data[idx].value) {
00389         first.resize(data[idx].value + 1, -1);
00390       }
00391       data[idx].next = first[data[idx].value];
00392       if (data[idx].next != -1) {
00393         data[data[idx].next].prev = idx;
00394       }
00395       first[data[idx].value] = idx;
00396       data[idx].prev = -1;
00397     }
00398 
00399   public:
00400 
00401     void push(const Pair& p) {
00402       push(p.first, p.second);
00403     }
00404 
00405     void push(const Item &i, const Prio &p) { 
00406       int idx = data.size();
00407       index[i] = idx;
00408       data.push_back(LinearItem(i, p));
00409       lace(idx);
00410       if (data[idx].value > maximal) {
00411         maximal = data[idx].value;
00412       }
00413     }
00414 
00415     Item top() const {
00416       while (first[maximal] == -1) {
00417         --maximal;
00418       }
00419       return data[first[maximal]].item;
00420     }
00421 
00422     Prio prio() const {
00423       while (first[maximal] == -1) {
00424         --maximal;
00425       }
00426       return maximal;
00427     }
00428 
00429     void pop() {
00430       while (first[maximal] == -1) {
00431         --maximal;
00432       }
00433       int idx = first[maximal];
00434       index[data[idx].item] = -2;
00435       unlace(idx);
00436       relocate_last(idx);
00437     }
00438 
00439     void erase(const Item &i) {
00440       int idx = index[i];
00441       index[data[idx].item] = -2;
00442       unlace(idx);
00443       relocate_last(idx);
00444     }
00445 
00446     Prio operator[](const Item &i) const {
00447       int idx = index[i];
00448       return data[idx].value;
00449     }
00450 
00451     void set(const Item &i, const Prio &p) {
00452       int idx = index[i];
00453       if (idx < 0) {
00454         push(i,p);
00455       } else if (p > data[idx].value) {
00456         decrease(i, p);
00457       } else {
00458         increase(i, p);
00459       }
00460     }
00461 
00462     void decrease(const Item &i, const Prio &p) {
00463       int idx = index[i];
00464       unlace(idx);
00465       data[idx].value = p;
00466       if (p > maximal) {
00467         maximal = p;
00468       }
00469       lace(idx);
00470     }
00471     
00472     void increase(const Item &i, const Prio &p) {
00473       int idx = index[i];
00474       unlace(idx);
00475       data[idx].value = p;
00476       lace(idx);
00477     }
00478 
00479     state_enum state(const Item &i) const {
00480       int idx = index[i];
00481       if (idx >= 0) idx = 0;
00482       return state_enum(idx);
00483     }
00484 
00485     void state(const Item& i, state_enum st) {
00486       switch (st) {
00487       case POST_HEAP:
00488       case PRE_HEAP:
00489         if (state(i) == IN_HEAP) {
00490           erase(i);
00491         }
00492         index[i] = st;
00493         break;
00494       case IN_HEAP:
00495         break;
00496       }
00497     }
00498 
00499   private:
00500 
00501     struct LinearItem {
00502       LinearItem(const Item& _item, int _value) 
00503         : item(_item), value(_value) {}
00504 
00505       Item item;
00506       int value;
00507 
00508       int prev, next;
00509     };
00510 
00511     ItemIntMap& index;
00512     std::vector<int> first;
00513     std::vector<LinearItem> data;
00514     mutable int maximal;
00515 
00516   }; // class LinearHeap
00517 
00518 }
00519   
00520 #endif

Generated on Fri Feb 3 18:38:39 2006 for LEMON by  doxygen 1.4.6