COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bucket_heap.h @ 2110:4b8153513f34

Last change on this file since 2110:4b8153513f34 was 2110:4b8153513f34, checked in by Balazs Dezso, 18 years ago

Smaller Simple Bucket Heap

  • the list node does not store the value
  • trade off: linear time operator[]
File size: 21.2 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));
606      } else {
607        idx = free;
608        free = data[idx].next;
609        data[idx].item = i;
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    /// \warning This operator is not a constant time function
663    /// because it scans the whole data structure to find the proper
664    /// value. 
665    /// \pre \c i must be in the heap.
666    /// \param i The item.
667    Prio operator[](const Item &i) const {
668      for (int k = 0; k < first.size(); ++k) {
669        int idx = first[k];
670        while (idx != -1) {
671          if (data[idx].item == i) {
672            return k;
673          }
674          idx = data[idx].next;
675        }
676      }
677      return -1;
678    }
679
680    /// \brief Returns if \c item is in, has already been in, or has
681    /// never been in the heap.
682    ///
683    /// This method returns PRE_HEAP if \c item has never been in the
684    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
685    /// otherwise. In the latter case it is possible that \c item will
686    /// get back to the heap again.
687    /// \param i The item.
688    state_enum state(const Item &i) const {
689      int idx = index[i];
690      if (idx >= 0) idx = 0;
691      return state_enum(idx);
692    }
693
694  private:
695
696    struct BucketItem {
697      BucketItem(const Item& _item)
698        : item(_item) {}
699
700      Item item;
701      int next;
702    };
703
704    ItemIntMap& index;
705    std::vector<int> first;
706    std::vector<BucketItem> data;
707    int free, num;
708    mutable int minimal;
709
710  }; // class SimpleBucketHeap
711
712  template <typename _Item, typename _ItemIntMap>
713  class SimpleBucketHeap<_Item, _ItemIntMap, false> {
714
715  public:
716    typedef _Item Item;
717    typedef int Prio;
718    typedef std::pair<Item, Prio> Pair;
719    typedef _ItemIntMap ItemIntMap;
720
721    enum state_enum {
722      IN_HEAP = 0,
723      PRE_HEAP = -1,
724      POST_HEAP = -2
725    };
726
727  public:
728
729    explicit SimpleBucketHeap(ItemIntMap &_index)
730      : index(_index), free(-1), num(0), maximal(0) {}
731   
732    int size() const { return num; }
733   
734    bool empty() const { return num == 0; }
735
736    void clear() {
737      data.clear(); first.clear(); free = -1; num = 0; maximal = 0;
738    }
739
740    void push(const Pair& p) {
741      push(p.first, p.second);
742    }
743
744    void push(const Item &i, const Prio &p) {
745      int idx;
746      if (free == -1) {
747        idx = data.size();
748        data.push_back(BucketItem(i));
749      } else {
750        idx = free;
751        free = data[idx].next;
752        data[idx].item = i;
753      }
754      index[i] = idx;
755      if (p >= (int)first.size()) first.resize(p + 1, -1);
756      data[idx].next = first[p];
757      first[p] = idx;
758      if (p > maximal) {
759        maximal = p;
760      }
761      ++num;
762    }
763
764    Item top() const {
765      while (first[maximal] == -1) {
766        --maximal;
767      }
768      return data[first[maximal]].item;
769    }
770
771    Prio prio() const {
772      while (first[maximal] == -1) {
773        --maximal;
774      }
775      return maximal;
776    }
777
778    void pop() {
779      while (first[maximal] == -1) {
780        --maximal;
781      }
782      int idx = first[maximal];
783      index[data[idx].item] = -2;
784      first[maximal] = data[idx].next;
785      data[idx].next = free;
786      free = idx;
787      --num;
788    }
789   
790    Prio operator[](const Item &i) const {
791      for (int k = 0; k < first.size(); ++k) {
792        int idx = first[k];
793        while (idx != -1) {
794          if (data[idx].item == i) {
795            return k;
796          }
797          idx = data[idx].next;
798        }
799      }
800      return -1;
801    }
802
803    state_enum state(const Item &i) const {
804      int idx = index[i];
805      if (idx >= 0) idx = 0;
806      return state_enum(idx);
807    }
808
809  private:
810
811    struct BucketItem {
812      BucketItem(const Item& _item) : item(_item) {}
813
814      Item item;
815
816      int next;
817    };
818
819    ItemIntMap& index;
820    std::vector<int> first;
821    std::vector<BucketItem> data;
822    int free, num;
823    mutable int maximal;
824
825  };
826
827}
828 
829#endif
Note: See TracBrowser for help on using the repository browser.