radix_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_RADIX_HEAP_H
00020 #define LEMON_RADIX_HEAP_H
00021 
00025 
00026 #include <vector>
00027 #include <lemon/error.h>
00028 
00029 namespace lemon {
00030 
00037 
00038   class UnderFlowPriorityError : public RuntimeError {
00039   public:
00040     virtual const char* exceptionName() const {
00041       return "lemon::UnderFlowPriorityError";
00042     }  
00043   };
00044 
00064 
00065   template <typename _Item, typename _ItemIntMap>
00066   class RadixHeap {
00067 
00068   public:
00069     typedef _Item Item;
00070     typedef int Prio;
00071     typedef _ItemIntMap ItemIntMap;
00072 
00081     enum state_enum {
00082       IN_HEAP = 0,
00083       PRE_HEAP = -1,
00084       POST_HEAP = -2
00085     };
00086 
00087   private:
00088     
00089     struct RadixItem {
00090       int prev, next, box;
00091       Item item;
00092       int prio;
00093       RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
00094     };
00095 
00096     struct RadixBox {
00097       int first;
00098       int min, size;
00099       RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
00100     };
00101 
00102     std::vector<RadixItem> data;
00103     std::vector<RadixBox> boxes;
00104 
00105     ItemIntMap &iim;
00106 
00107 
00108   public:
00119     RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0) 
00120       : iim(_iim) {
00121       boxes.push_back(RadixBox(minimal, 1));
00122       boxes.push_back(RadixBox(minimal + 1, 1));
00123       while (lower(boxes.size() - 1, capacity + minimal - 1)) {
00124         extend();
00125       }
00126     }
00127 
00131     int size() const { return data.size(); }
00135     bool empty() const { return data.empty(); }
00136 
00140     void clear(int minimal = 0, int capacity = 0) { 
00141       for (int i = 0; i < (int)data.size(); ++i) {
00142         iim[data[i].item] = -2;
00143       }
00144       data.clear(); boxes.clear(); 
00145       boxes.push_back(RadixBox(minimal, 1));
00146       boxes.push_back(RadixBox(minimal + 1, 1));
00147       while (lower(boxes.size() - 1, capacity + minimal - 1)) {
00148         extend();
00149       }
00150     }
00151 
00152   private:
00153 
00154     bool upper(int box, Prio prio) {
00155       return prio < boxes[box].min;
00156     }
00157 
00158     bool lower(int box, Prio prio) {
00159       return prio >= boxes[box].min + boxes[box].size;
00160     }
00161 
00163     void remove(int index) {
00164       if (data[index].prev >= 0) {
00165         data[data[index].prev].next = data[index].next;
00166       } else {
00167         boxes[data[index].box].first = data[index].next;
00168       }
00169       if (data[index].next >= 0) {
00170         data[data[index].next].prev = data[index].prev;
00171       }
00172     }
00173 
00175     void insert(int box, int index) {
00176       if (boxes[box].first == -1) {
00177         boxes[box].first = index;
00178         data[index].next = data[index].prev = -1;
00179       } else {
00180         data[index].next = boxes[box].first;
00181         data[boxes[box].first].prev = index;
00182         data[index].prev = -1;
00183         boxes[box].first = index;
00184       }
00185       data[index].box = box;
00186     }
00187 
00189     void extend() {
00190       int min = boxes.back().min + boxes.back().size;
00191       int size = 2 * boxes.back().size;
00192       boxes.push_back(RadixBox(min, size));
00193     }
00194 
00196     void bubble_up(int index) {
00197       if (!lower(data[index].box, data[index].prio)) return;
00198       remove(index);
00199       int box = findUp(data[index].box, data[index].prio);
00200       insert(box, index);      
00201     }
00202 
00204     int findUp(int start, int prio) {
00205       while (lower(start, prio)) {
00206         if (++start == (int)boxes.size()) {
00207           extend();
00208         }
00209       }
00210       return start;
00211     }
00212 
00214     void bubble_down(int index) {
00215       if (!upper(data[index].box, data[index].prio)) return;
00216       remove(index);
00217       int box = findDown(data[index].box, data[index].prio);
00218       insert(box, index);
00219     }
00220 
00222     int findDown(int start, int prio) {
00223       while (upper(start, prio)) {
00224         if (--start < 0) throw UnderFlowPriorityError();
00225       }
00226       return start;
00227     }
00228 
00230     int findFirst() {
00231       int first = 0;
00232       while (boxes[first].first == -1) ++first;
00233       return first;
00234     }
00235 
00237     int minValue(int box) {
00238       int min = data[boxes[box].first].prio;
00239       for (int k = boxes[box].first; k != -1; k = data[k].next) {
00240         if (data[k].prio < min) min = data[k].prio;
00241       }
00242       return min;
00243     }
00244 
00247     void moveDown() {
00248       int box = findFirst();
00249       if (box == 0) return;
00250       int min = minValue(box);
00251       for (int i = 0; i <= box; ++i) {
00252         boxes[i].min = min;
00253         min += boxes[i].size;
00254       }
00255       int curr = boxes[box].first, next;
00256       while (curr != -1) {
00257         next = data[curr].next;
00258         bubble_down(curr);
00259         curr = next;
00260       }      
00261     }
00262 
00263     void relocate_last(int index) {
00264       if (index != (int)data.size() - 1) {
00265         data[index] = data.back();
00266         if (data[index].prev != -1) {
00267           data[data[index].prev].next = index;
00268         } else {
00269           boxes[data[index].box].first = index;
00270         }
00271         if (data[index].next != -1) {
00272           data[data[index].next].prev = index;
00273         }
00274         iim[data[index].item] = index;
00275       }
00276       data.pop_back();
00277     }
00278 
00279   public:
00280 
00286     void push(const Item &i, const Prio &p) {
00287       int n = data.size();
00288       iim.set(i, n);
00289       data.push_back(RadixItem(i, p));
00290       while (lower(boxes.size() - 1, p)) {
00291         extend();
00292       }
00293       int box = findDown(boxes.size() - 1, p);
00294       insert(box, n);
00295     }
00296 
00301     Item top() const {
00302       const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
00303       return data[boxes[0].first].item;
00304     }
00305 
00310     Prio prio() const {
00311       const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
00312       return data[boxes[0].first].prio;
00313      }
00314 
00319     void pop() {
00320       moveDown();
00321       int index = boxes[0].first;
00322       iim[data[index].item] = POST_HEAP;
00323       remove(index);
00324       relocate_last(index);
00325     }
00326 
00332     void erase(const Item &i) {
00333       int index = iim[i];
00334       iim[i] = POST_HEAP;
00335       remove(index);
00336       relocate_last(index);
00337    }
00338 
00344     Prio operator[](const Item &i) const {
00345       int idx = iim[i];
00346       return data[idx].prio;
00347     }
00348 
00357     void set(const Item &i, const Prio &p) {
00358       int idx = iim[i];
00359       if( idx < 0 ) {
00360         push(i, p);
00361       }
00362       else if( p >= data[idx].prio ) {
00363         data[idx].prio = p;
00364         bubble_up(idx);
00365       } else {
00366         data[idx].prio = p;
00367         bubble_down(idx);
00368       }
00369     }
00370 
00371 
00379     void decrease(const Item &i, const Prio &p) {
00380       int idx = iim[i];
00381       data[idx].prio = p;
00382       bubble_down(idx);
00383     }
00384 
00391     void increase(const Item &i, const Prio &p) {
00392       int idx = iim[i];
00393       data[idx].prio = p;
00394       bubble_up(idx);
00395     }
00396 
00405     state_enum state(const Item &i) const {
00406       int s = iim[i];
00407       if( s >= 0 ) s = 0;
00408       return state_enum(s);
00409     }
00410 
00418     void state(const Item& i, state_enum st) {
00419       switch (st) {
00420       case POST_HEAP:
00421       case PRE_HEAP:
00422         if (state(i) == IN_HEAP) {
00423           erase(i);
00424         }
00425         iim[i] = st;
00426         break;
00427       case IN_HEAP:
00428         break;
00429       }
00430     }
00431 
00432   }; // class RadixHeap
00433 
00434 } // namespace lemon
00435 
00436 #endif // LEMON_RADIX_HEAP_H

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