COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bucket_heap.h @ 2091:c8ccc1f8fd51

Last change on this file since 2091:c8ccc1f8fd51 was 2089:fce8db723736, checked in by Balazs Dezso, 14 years ago

SimpleBucketHeap? added

It does not supports erasing, decreasing, increasing.
It contains single linked lists

It can be used to store levels for push-relabel algorithms

File size: 20.8 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_BUCKET_HEAP_H
20#define LEMON_BUCKET_HEAP_H
21
22///\ingroup auxdat
23///\file
24///\brief Bucket Heap implementation.
25
26#include <vector>
27#include <utility>
28#include <functional>
29
30namespace lemon {
31
32  /// \ingroup auxdat
33  ///
34  /// \brief A Bucket Heap implementation.
35  ///
36  /// This class implements the \e bucket \e heap data structure. A \e heap
37  /// is a data structure for storing items with specified values called \e
38  /// priorities in such a way that finding the item with minimum priority is
39  /// efficient. The bucket heap is very simple implementation, it can store
40  /// only integer priorities and it stores for each priority in the
41  /// \f$ [0..C) \f$ range a list of items. So it should be used only when
42  /// the priorities are small. It is not intended to use as dijkstra heap.
43  ///
44  /// \param _Item Type of the items to be stored. 
45  /// \param _ItemIntMap A read and writable Item int map, used internally
46  /// to handle the cross references.
47  /// \param minimize If the given parameter is true then the heap gives back
48  /// the lowest priority.
49  template <typename _Item, typename _ItemIntMap, bool minimize = true >
50  class BucketHeap {
51
52  public:
53    typedef _Item Item;
54    typedef int Prio;
55    typedef std::pair<Item, Prio> Pair;
56    typedef _ItemIntMap ItemIntMap;
57
58    /// \brief Type to represent the items states.
59    ///
60    /// Each Item element have a state associated to it. It may be "in heap",
61    /// "pre heap" or "post heap". The latter two are indifferent from the
62    /// heap's point of view, but may be useful to the user.
63    ///
64    /// The ItemIntMap \e should be initialized in such way that it maps
65    /// PRE_HEAP (-1) to any element to be put in the heap...
66    enum state_enum {
67      IN_HEAP = 0,
68      PRE_HEAP = -1,
69      POST_HEAP = -2
70    };
71
72  public:
73    /// \brief The constructor.
74    ///
75    /// The constructor.
76    /// \param _index should be given to the constructor, since it is used
77    /// internally to handle the cross references. The value of the map
78    /// should be PRE_HEAP (-1) for each element.
79    explicit BucketHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
80   
81    /// The number of items stored in the heap.
82    ///
83    /// \brief Returns the number of items stored in the heap.
84    int size() const { return data.size(); }
85   
86    /// \brief Checks if the heap stores no items.
87    ///
88    /// Returns \c true if and only if the heap stores no items.
89    bool empty() const { return data.empty(); }
90
91    /// \brief Make empty this heap.
92    ///
93    /// Make empty this heap. It does not change the cross reference
94    /// map.  If you want to reuse a heap what is not surely empty you
95    /// should first clear the heap and after that you should set the
96    /// cross reference map for each item to \c PRE_HEAP.
97    void clear() {
98      data.clear(); first.clear(); minimal = 0;
99    }
100
101  private:
102
103    void relocate_last(int idx) {
104      if (idx + 1 < (int)data.size()) {
105        data[idx] = data.back();
106        if (data[idx].prev != -1) {
107          data[data[idx].prev].next = idx;
108        } else {
109          first[data[idx].value] = idx;
110        }
111        if (data[idx].next != -1) {
112          data[data[idx].next].prev = idx;
113        }
114        index[data[idx].item] = idx;
115      }
116      data.pop_back();
117    }
118
119    void unlace(int idx) {
120      if (data[idx].prev != -1) {
121        data[data[idx].prev].next = data[idx].next;
122      } else {
123        first[data[idx].value] = data[idx].next;
124      }
125      if (data[idx].next != -1) {
126        data[data[idx].next].prev = data[idx].prev;
127      }
128    }
129
130    void lace(int idx) {
131      if ((int)first.size() <= data[idx].value) {
132        first.resize(data[idx].value + 1, -1);
133      }
134      data[idx].next = first[data[idx].value];
135      if (data[idx].next != -1) {
136        data[data[idx].next].prev = idx;
137      }
138      first[data[idx].value] = idx;
139      data[idx].prev = -1;
140    }
141
142  public:
143    /// \brief Insert a pair of item and priority into the heap.
144    ///
145    /// Adds \c p.first to the heap with priority \c p.second.
146    /// \param p The pair to insert.
147    void push(const Pair& p) {
148      push(p.first, p.second);
149    }
150
151    /// \brief Insert an item into the heap with the given priority.
152    ///   
153    /// Adds \c i to the heap with priority \c p.
154    /// \param i The item to insert.
155    /// \param p The priority of the item.
156    void push(const Item &i, const Prio &p) {
157      int idx = data.size();
158      index[i] = idx;
159      data.push_back(BucketItem(i, p));
160      lace(idx);
161      if (p < minimal) {
162        minimal = p;
163      }
164    }
165
166    /// \brief Returns the item with minimum priority.
167    ///
168    /// This method returns the item with minimum priority.
169    /// \pre The heap must be nonempty. 
170    Item top() const {
171      while (first[minimal] == -1) {
172        ++minimal;
173      }
174      return data[first[minimal]].item;
175    }
176
177    /// \brief Returns the minimum priority.
178    ///
179    /// It returns the minimum priority.
180    /// \pre The heap must be nonempty.
181    Prio prio() const {
182      while (first[minimal] == -1) {
183        ++minimal;
184      }
185      return minimal;
186    }
187
188    /// \brief Deletes the item with minimum priority.
189    ///
190    /// This method deletes the item with minimum priority from the heap. 
191    /// \pre The heap must be non-empty. 
192    void pop() {
193      while (first[minimal] == -1) {
194        ++minimal;
195      }
196      int idx = first[minimal];
197      index[data[idx].item] = -2;
198      unlace(idx);
199      relocate_last(idx);
200    }
201
202    /// \brief Deletes \c i from the heap.
203    ///
204    /// This method deletes item \c i from the heap, if \c i was
205    /// already stored in the heap.
206    /// \param i The item to erase.
207    void erase(const Item &i) {
208      int idx = index[i];
209      index[data[idx].item] = -2;
210      unlace(idx);
211      relocate_last(idx);
212    }
213
214   
215    /// \brief Returns the priority of \c i.
216    ///
217    /// This function returns the priority of item \c i. 
218    /// \pre \c i must be in the heap.
219    /// \param i The item.
220    Prio operator[](const Item &i) const {
221      int idx = index[i];
222      return data[idx].value;
223    }
224
225    /// \brief \c i gets to the heap with priority \c p independently
226    /// if \c i was already there.
227    ///
228    /// This method calls \ref push(\c i, \c p) if \c i is not stored
229    /// in the heap and sets the priority of \c i to \c p otherwise.
230    /// \param i The item.
231    /// \param p The priority.
232    void set(const Item &i, const Prio &p) {
233      int idx = index[i];
234      if (idx < 0) {
235        push(i,p);
236      } else if (p > data[idx].value) {
237        increase(i, p);
238      } else {
239        decrease(i, p);
240      }
241    }
242
243    /// \brief Decreases the priority of \c i to \c p.
244    ///
245    /// This method decreases the priority of item \c i to \c p.
246    /// \pre \c i must be stored in the heap with priority at least \c
247    /// p relative to \c Compare.
248    /// \param i The item.
249    /// \param p The priority.
250    void decrease(const Item &i, const Prio &p) {
251      int idx = index[i];
252      unlace(idx);
253      data[idx].value = p;
254      if (p < minimal) {
255        minimal = p;
256      }
257      lace(idx);
258    }
259   
260    /// \brief Increases the priority of \c i to \c p.
261    ///
262    /// This method sets the priority of item \c i to \c p.
263    /// \pre \c i must be stored in the heap with priority at most \c
264    /// p relative to \c Compare.
265    /// \param i The item.
266    /// \param p The priority.
267    void increase(const Item &i, const Prio &p) {
268      int idx = index[i];
269      unlace(idx);
270      data[idx].value = p;
271      lace(idx);
272    }
273
274    /// \brief Returns if \c item is in, has already been in, or has
275    /// never been in the heap.
276    ///
277    /// This method returns PRE_HEAP if \c item has never been in the
278    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
279    /// otherwise. In the latter case it is possible that \c item will
280    /// get back to the heap again.
281    /// \param i The item.
282    state_enum state(const Item &i) const {
283      int idx = index[i];
284      if (idx >= 0) idx = 0;
285      return state_enum(idx);
286    }
287
288    /// \brief Sets the state of the \c item in the heap.
289    ///
290    /// Sets the state of the \c item in the heap. It can be used to
291    /// manually clear the heap when it is important to achive the
292    /// better time complexity.
293    /// \param i The item.
294    /// \param st The state. It should not be \c IN_HEAP.
295    void state(const Item& i, state_enum st) {
296      switch (st) {
297      case POST_HEAP:
298      case PRE_HEAP:
299        if (state(i) == IN_HEAP) {
300          erase(i);
301        }
302        index[i] = st;
303        break;
304      case IN_HEAP:
305        break;
306      }
307    }
308
309  private:
310
311    struct BucketItem {
312      BucketItem(const Item& _item, int _value)
313        : item(_item), value(_value) {}
314
315      Item item;
316      int value;
317
318      int prev, next;
319    };
320
321    ItemIntMap& index;
322    std::vector<int> first;
323    std::vector<BucketItem> data;
324    mutable int minimal;
325
326  }; // class BucketHeap
327
328
329  template <typename _Item, typename _ItemIntMap>
330  class BucketHeap<_Item, _ItemIntMap, false> {
331
332  public:
333    typedef _Item Item;
334    typedef int Prio;
335    typedef std::pair<Item, Prio> Pair;
336    typedef _ItemIntMap ItemIntMap;
337
338    enum state_enum {
339      IN_HEAP = 0,
340      PRE_HEAP = -1,
341      POST_HEAP = -2
342    };
343
344  public:
345
346    explicit BucketHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
347
348    int size() const { return data.size(); }
349    bool empty() const { return data.empty(); }
350
351    void clear() {
352      data.clear(); first.clear(); maximal = -1;
353    }
354
355  private:
356
357    void relocate_last(int idx) {
358      if (idx + 1 != (int)data.size()) {
359        data[idx] = data.back();
360        if (data[idx].prev != -1) {
361          data[data[idx].prev].next = idx;
362        } else {
363          first[data[idx].value] = idx;
364        }
365        if (data[idx].next != -1) {
366          data[data[idx].next].prev = idx;
367        }
368        index[data[idx].item] = idx;
369      }
370      data.pop_back();
371    }
372
373    void unlace(int idx) {
374      if (data[idx].prev != -1) {
375        data[data[idx].prev].next = data[idx].next;
376      } else {
377        first[data[idx].value] = data[idx].next;
378      }
379      if (data[idx].next != -1) {
380        data[data[idx].next].prev = data[idx].prev;
381      }
382    }
383
384    void lace(int idx) {
385      if ((int)first.size() <= data[idx].value) {
386        first.resize(data[idx].value + 1, -1);
387      }
388      data[idx].next = first[data[idx].value];
389      if (data[idx].next != -1) {
390        data[data[idx].next].prev = idx;
391      }
392      first[data[idx].value] = idx;
393      data[idx].prev = -1;
394    }
395
396  public:
397
398    void push(const Pair& p) {
399      push(p.first, p.second);
400    }
401
402    void push(const Item &i, const Prio &p) {
403      int idx = data.size();
404      index[i] = idx;
405      data.push_back(BucketItem(i, p));
406      lace(idx);
407      if (data[idx].value > maximal) {
408        maximal = data[idx].value;
409      }
410    }
411
412    Item top() const {
413      while (first[maximal] == -1) {
414        --maximal;
415      }
416      return data[first[maximal]].item;
417    }
418
419    Prio prio() const {
420      while (first[maximal] == -1) {
421        --maximal;
422      }
423      return maximal;
424    }
425
426    void pop() {
427      while (first[maximal] == -1) {
428        --maximal;
429      }
430      int idx = first[maximal];
431      index[data[idx].item] = -2;
432      unlace(idx);
433      relocate_last(idx);
434    }
435
436    void erase(const Item &i) {
437      int idx = index[i];
438      index[data[idx].item] = -2;
439      unlace(idx);
440      relocate_last(idx);
441    }
442
443    Prio operator[](const Item &i) const {
444      int idx = index[i];
445      return data[idx].value;
446    }
447
448    void set(const Item &i, const Prio &p) {
449      int idx = index[i];
450      if (idx < 0) {
451        push(i,p);
452      } else if (p > data[idx].value) {
453        decrease(i, p);
454      } else {
455        increase(i, p);
456      }
457    }
458
459    void decrease(const Item &i, const Prio &p) {
460      int idx = index[i];
461      unlace(idx);
462      data[idx].value = p;
463      if (p > maximal) {
464        maximal = p;
465      }
466      lace(idx);
467    }
468   
469    void increase(const Item &i, const Prio &p) {
470      int idx = index[i];
471      unlace(idx);
472      data[idx].value = p;
473      lace(idx);
474    }
475
476    state_enum state(const Item &i) const {
477      int idx = index[i];
478      if (idx >= 0) idx = 0;
479      return state_enum(idx);
480    }
481
482    void state(const Item& i, state_enum st) {
483      switch (st) {
484      case POST_HEAP:
485      case PRE_HEAP:
486        if (state(i) == IN_HEAP) {
487          erase(i);
488        }
489        index[i] = st;
490        break;
491      case IN_HEAP:
492        break;
493      }
494    }
495
496  private:
497
498    struct BucketItem {
499      BucketItem(const Item& _item, int _value)
500        : item(_item), value(_value) {}
501
502      Item item;
503      int value;
504
505      int prev, next;
506    };
507
508    ItemIntMap& index;
509    std::vector<int> first;
510    std::vector<BucketItem> data;
511    mutable int maximal;
512
513  }; // class BucketHeap
514
515  /// \ingroup auxdat
516  ///
517  /// \brief A Simplified Bucket Heap implementation.
518  ///
519  /// This class implements a simplified \e bucket \e heap data
520  /// structure.  It does not provide some functionality but it faster
521  /// and simplier data structure than the BucketHeap. The main
522  /// difference is that the BucketHeap stores for every key a double
523  /// linked list while this class stores just simple lists. In the
524  /// other way it does not supports erasing each elements just the
525  /// minimal and it does not supports key increasing, decreasing.
526  ///
527  /// \param _Item Type of the items to be stored. 
528  /// \param _ItemIntMap A read and writable Item int map, used internally
529  /// to handle the cross references.
530  /// \param minimize If the given parameter is true then the heap gives back
531  /// the lowest priority.
532  ///
533  /// \sa BucketHeap
534  template <typename _Item, typename _ItemIntMap, bool minimize = true >
535  class SimpleBucketHeap {
536
537  public:
538    typedef _Item Item;
539    typedef int Prio;
540    typedef std::pair<Item, Prio> Pair;
541    typedef _ItemIntMap ItemIntMap;
542
543    /// \brief Type to represent the items states.
544    ///
545    /// Each Item element have a state associated to it. It may be "in heap",
546    /// "pre heap" or "post heap". The latter two are indifferent from the
547    /// heap's point of view, but may be useful to the user.
548    ///
549    /// The ItemIntMap \e should be initialized in such way that it maps
550    /// PRE_HEAP (-1) to any element to be put in the heap...
551    enum state_enum {
552      IN_HEAP = 0,
553      PRE_HEAP = -1,
554      POST_HEAP = -2
555    };
556
557  public:
558
559    /// \brief The constructor.
560    ///
561    /// The constructor.
562    /// \param _index should be given to the constructor, since it is used
563    /// internally to handle the cross references. The value of the map
564    /// should be PRE_HEAP (-1) for each element.
565    explicit SimpleBucketHeap(ItemIntMap &_index)
566      : index(_index), free(-1), num(0), minimal(0) {}
567   
568    /// \brief Returns the number of items stored in the heap.
569    ///
570    /// The number of items stored in the heap.
571    int size() const { return num; }
572   
573    /// \brief Checks if the heap stores no items.
574    ///
575    /// Returns \c true if and only if the heap stores no items.
576    bool empty() const { return num == 0; }
577
578    /// \brief Make empty this heap.
579    ///
580    /// Make empty this heap. It does not change the cross reference
581    /// map.  If you want to reuse a heap what is not surely empty you
582    /// should first clear the heap and after that you should set the
583    /// cross reference map for each item to \c PRE_HEAP.
584    void clear() {
585      data.clear(); first.clear(); free = -1; num = 0; minimal = 0;
586    }
587
588    /// \brief Insert a pair of item and priority into the heap.
589    ///
590    /// Adds \c p.first to the heap with priority \c p.second.
591    /// \param p The pair to insert.
592    void push(const Pair& p) {
593      push(p.first, p.second);
594    }
595
596    /// \brief Insert an item into the heap with the given priority.
597    ///   
598    /// Adds \c i to the heap with priority \c p.
599    /// \param i The item to insert.
600    /// \param p The priority of the item.
601    void push(const Item &i, const Prio &p) {
602      int idx;
603      if (free == -1) {
604        idx = data.size();
605        data.push_back(BucketItem(i, p));
606      } else {
607        idx = free;
608        free = data[idx].next;
609        data[idx].item = i; data[idx].value = p;
610      }
611      index[i] = idx;
612      if (p >= (int)first.size()) first.resize(p + 1, -1);
613      data[idx].next = first[p];
614      first[p] = idx;
615      if (p < minimal) {
616        minimal = p;
617      }
618      ++num;
619    }
620
621    /// \brief Returns the item with minimum priority.
622    ///
623    /// This method returns the item with minimum priority.
624    /// \pre The heap must be nonempty. 
625    Item top() const {
626      while (first[minimal] == -1) {
627        ++minimal;
628      }
629      return data[first[minimal]].item;
630    }
631
632    /// \brief Returns the minimum priority.
633    ///
634    /// It returns the minimum priority.
635    /// \pre The heap must be nonempty.
636    Prio prio() const {
637      while (first[minimal] == -1) {
638        ++minimal;
639      }
640      return minimal;
641    }
642
643    /// \brief Deletes the item with minimum priority.
644    ///
645    /// This method deletes the item with minimum priority from the heap. 
646    /// \pre The heap must be non-empty. 
647    void pop() {
648      while (first[minimal] == -1) {
649        ++minimal;
650      }
651      int idx = first[minimal];
652      index[data[idx].item] = -2;
653      first[minimal] = data[idx].next;
654      data[idx].next = free;
655      free = idx;
656      --num;
657    }
658   
659    /// \brief Returns the priority of \c i.
660    ///
661    /// This function returns the priority of item \c i. 
662    /// \pre \c i must be in the heap.
663    /// \param i The item.
664    Prio operator[](const Item &i) const {
665      int idx = index[i];
666      return data[idx].value;
667    }
668
669    /// \brief Returns if \c item is in, has already been in, or has
670    /// never been in the heap.
671    ///
672    /// This method returns PRE_HEAP if \c item has never been in the
673    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
674    /// otherwise. In the latter case it is possible that \c item will
675    /// get back to the heap again.
676    /// \param i The item.
677    state_enum state(const Item &i) const {
678      int idx = index[i];
679      if (idx >= 0) idx = 0;
680      return state_enum(idx);
681    }
682
683  private:
684
685    struct BucketItem {
686      BucketItem(const Item& _item, int _value)
687        : item(_item), value(_value) {}
688
689      Item item;
690      int value;
691
692      int next;
693    };
694
695    ItemIntMap& index;
696    std::vector<int> first;
697    std::vector<BucketItem> data;
698    int free, num;
699    mutable int minimal;
700
701  }; // class SimpleBucketHeap
702
703  template <typename _Item, typename _ItemIntMap>
704  class SimpleBucketHeap<_Item, _ItemIntMap, false> {
705
706  public:
707    typedef _Item Item;
708    typedef int Prio;
709    typedef std::pair<Item, Prio> Pair;
710    typedef _ItemIntMap ItemIntMap;
711
712    enum state_enum {
713      IN_HEAP = 0,
714      PRE_HEAP = -1,
715      POST_HEAP = -2
716    };
717
718  public:
719
720    explicit SimpleBucketHeap(ItemIntMap &_index)
721      : index(_index), free(-1), num(0), maximal(0) {}
722   
723    int size() const { return num; }
724   
725    bool empty() const { return num == 0; }
726
727    void clear() {
728      data.clear(); first.clear(); free = -1; num = 0; maximal = 0;
729    }
730
731    void push(const Pair& p) {
732      push(p.first, p.second);
733    }
734
735    void push(const Item &i, const Prio &p) {
736      int idx;
737      if (free == -1) {
738        idx = data.size();
739        data.push_back(BucketItem(i, p));
740      } else {
741        idx = free;
742        free = data[idx].next;
743        data[idx].item = i; data[idx].value = p;
744      }
745      index[i] = idx;
746      if (p >= (int)first.size()) first.resize(p + 1, -1);
747      data[idx].next = first[p];
748      first[p] = idx;
749      if (p > maximal) {
750        maximal = p;
751      }
752      ++num;
753    }
754
755    Item top() const {
756      while (first[maximal] == -1) {
757        --maximal;
758      }
759      return data[first[maximal]].item;
760    }
761
762    Prio prio() const {
763      while (first[maximal] == -1) {
764        --maximal;
765      }
766      return maximal;
767    }
768
769    void pop() {
770      while (first[maximal] == -1) {
771        --maximal;
772      }
773      int idx = first[maximal];
774      index[data[idx].item] = -2;
775      first[maximal] = data[idx].next;
776      data[idx].next = free;
777      free = idx;
778      --num;
779    }
780   
781    Prio operator[](const Item &i) const {
782      int idx = index[i];
783      return data[idx].value;
784    }
785
786    state_enum state(const Item &i) const {
787      int idx = index[i];
788      if (idx >= 0) idx = 0;
789      return state_enum(idx);
790    }
791
792  private:
793
794    struct BucketItem {
795      BucketItem(const Item& _item, int _value)
796        : item(_item), value(_value) {}
797
798      Item item;
799      int value;
800
801      int next;
802    };
803
804    ItemIntMap& index;
805    std::vector<int> first;
806    std::vector<BucketItem> data;
807    int free, num;
808    mutable int maximal;
809
810  };
811
812}
813 
814#endif
Note: See TracBrowser for help on using the repository browser.