COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bucket_heap.h @ 681:532697c9fa53

Last change on this file since 681:532697c9fa53 was 681:532697c9fa53, checked in by Balazs Dezso <deba@…>, 15 years ago

Port remaining heaps from SVN -r 3509 (#50)

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