COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bucket_heap.h @ 2282:9d7b12f83daa

Last change on this file since 2282:9d7b12f83daa was 2263:9273fe7d850c, checked in by mqrelly, 17 years ago

Bug #46 fixed: Superfluous template parameter in Heap concept
NOTE: Not every affected file tested.

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