Changeset 683:9f529abcaebf in lemon1.2 for lemon/radix_heap.h
 Timestamp:
 06/11/09 23:13:24 (12 years ago)
 Branch:
 default
 Children:
 686:7439dc5fe1b9, 691:9e54e3b27db0, 693:7bda7860e0a8, 696:c9b9da1a90a0, 701:d1a9224f1e30, 709:0747f332c478, 713:4ac30454f1c1, 718:703ebf476a1d, 758:b31e130db13d
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/radix_heap.h
r681 r683 42 42 /// item's priority. 43 43 /// 44 /// \param _ItemIntMapA read and writable Item int map, used internally44 /// \param IM A read and writable Item int map, used internally 45 45 /// to handle the cross references. 46 46 /// 47 47 /// \see BinHeap 48 48 /// \see Dijkstra 49 template <typename _ItemIntMap>49 template <typename IM> 50 50 class RadixHeap { 51 51 52 52 public: 53 typedef typename _ItemIntMap::Key Item;53 typedef typename IM::Key Item; 54 54 typedef int Prio; 55 typedef _ItemIntMapItemIntMap;55 typedef IM ItemIntMap; 56 56 57 57 /// \brief Exception thrown by RadixHeap. … … 100 100 std::vector<RadixBox> boxes; 101 101 102 ItemIntMap & iim;102 ItemIntMap &_iim; 103 103 104 104 … … 108 108 /// The constructor. 109 109 /// 110 /// \param _iimIt should be given to the constructor, since it is used110 /// \param map It should be given to the constructor, since it is used 111 111 /// internally to handle the cross references. The value of the map 112 112 /// should be PRE_HEAP (1) for each element. … … 114 114 /// \param minimal The initial minimal value of the heap. 115 115 /// \param capacity It determines the initial capacity of the heap. 116 RadixHeap(ItemIntMap & _iim, int minimal = 0, int capacity = 0)117 : iim(_iim) {116 RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0) 117 : _iim(map) { 118 118 boxes.push_back(RadixBox(minimal, 1)); 119 119 boxes.push_back(RadixBox(minimal + 1, 1)); … … 269 269 data[data[index].next].prev = index; 270 270 } 271 iim[data[index].item] = index;271 _iim[data[index].item] = index; 272 272 } 273 273 data.pop_back(); … … 283 283 void push(const Item &i, const Prio &p) { 284 284 int n = data.size(); 285 iim.set(i, n);285 _iim.set(i, n); 286 286 data.push_back(RadixItem(i, p)); 287 287 while (lower(boxes.size()  1, p)) { … … 317 317 moveDown(); 318 318 int index = boxes[0].first; 319 iim[data[index].item] = POST_HEAP;319 _iim[data[index].item] = POST_HEAP; 320 320 remove(index); 321 321 relocate_last(index); … … 328 328 /// \param i The item to erase. 329 329 void erase(const Item &i) { 330 int index = iim[i];331 iim[i] = POST_HEAP;330 int index = _iim[i]; 331 _iim[i] = POST_HEAP; 332 332 remove(index); 333 333 relocate_last(index); … … 340 340 /// \param i The item. 341 341 Prio operator[](const Item &i) const { 342 int idx = iim[i];342 int idx = _iim[i]; 343 343 return data[idx].prio; 344 344 } … … 353 353 /// \param p The priority. 354 354 void set(const Item &i, const Prio &p) { 355 int idx = iim[i];355 int idx = _iim[i]; 356 356 if( idx < 0 ) { 357 357 push(i, p); … … 375 375 /// \param p The priority. 376 376 void decrease(const Item &i, const Prio &p) { 377 int idx = iim[i];377 int idx = _iim[i]; 378 378 data[idx].prio = p; 379 379 bubble_down(idx); … … 387 387 /// \param p The priority. 388 388 void increase(const Item &i, const Prio &p) { 389 int idx = iim[i];389 int idx = _iim[i]; 390 390 data[idx].prio = p; 391 391 bubble_up(idx); … … 401 401 /// \param i The item. 402 402 State state(const Item &i) const { 403 int s = iim[i];403 int s = _iim[i]; 404 404 if( s >= 0 ) s = 0; 405 405 return State(s); … … 420 420 erase(i); 421 421 } 422 iim[i] = st;422 _iim[i] = st; 423 423 break; 424 424 case IN_HEAP:
Note: See TracChangeset
for help on using the changeset viewer.