COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/linear_heap.h @ 1902:e9af75c90c28

Last change on this file since 1902:e9af75c90c28 was 1902:e9af75c90c28, checked in by Balazs Dezso, 14 years ago

state setting function for heaps

If we know that which elements were in the heap then
we can clear it in better time complexity.

File size: 12.8 KB
RevLine 
[1724]1/* -*- C++ -*-
2 * lemon/linear_heap.h - Part of LEMON, a generic C++ optimization library
3 *
[1875]4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1724]5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_LINEAR_HEAP_H
18#define LEMON_LINEAR_HEAP_H
19
20///\ingroup auxdat
21///\file
22///\brief Binary Heap implementation.
23
24#include <vector>
25#include <utility>
26#include <functional>
27
28namespace lemon {
29
[1834]30  /// \ingroup auxdat
[1724]31
32  /// \brief A Linear Heap implementation.
33  ///
34  /// This class implements the \e linear \e heap data structure. A \e heap
35  /// is a data structure for storing items with specified values called \e
36  /// priorities in such a way that finding the item with minimum priority is
37  /// efficient. The linear heap is very simple implementation, it can store
38  /// only integer priorities and it stores for each priority in the [0..C]
39  /// range a list of items. So it should be used only when the priorities
40  /// are small. It is not intended to use as dijkstra heap.
41  ///
42  /// \param _Item Type of the items to be stored. 
43  /// \param _ItemIntMap A read and writable Item int map, used internally
44  /// to handle the cross references.
45  /// \param minimize If the given parameter is true then the heap gives back
46  /// the lowest priority.
47  template <typename _Item, typename _ItemIntMap, bool minimize = true >
48  class LinearHeap {
49
50  public:
51    typedef _Item Item;
52    typedef int Prio;
53    typedef std::pair<Item, Prio> Pair;
54    typedef _ItemIntMap ItemIntMap;
55
56    /// \brief Type to represent the items states.
57    ///
58    /// Each Item element have a state associated to it. It may be "in heap",
59    /// "pre heap" or "post heap". The latter two are indifferent from the
60    /// heap's point of view, but may be useful to the user.
61    ///
62    /// The ItemIntMap \e should be initialized in such way that it maps
63    /// PRE_HEAP (-1) to any element to be put in the heap...
64    enum state_enum {
65      IN_HEAP = 0,
66      PRE_HEAP = -1,
67      POST_HEAP = -2
68    };
69
70  public:
71    /// \brief The constructor.
72    ///
73    /// The constructor.
74    /// \param _index should be given to the constructor, since it is used
75    /// internally to handle the cross references. The value of the map
76    /// should be PRE_HEAP (-1) for each element.
77    explicit LinearHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
78   
79    /// The number of items stored in the heap.
80    ///
81    /// \brief Returns the number of items stored in the heap.
82    int size() const { return data.size(); }
83   
84    /// \brief Checks if the heap stores no items.
85    ///
86    /// Returns \c true if and only if the heap stores no items.
87    bool empty() const { return data.empty(); }
88
89    /// \brief Make empty this heap.
90    ///
91    /// Make empty this heap.
92    void clear() {
93      for (int i = 0; i < (int)data.size(); ++i) {
94        index[data[i].item] = -2;
95      }
96      data.clear(); first.clear(); minimal = 0;
97    }
98
99  private:
100
101    void relocate_last(int idx) {
102      if (idx + 1 < (int)data.size()) {
103        data[idx] = data.back();
104        if (data[idx].prev != -1) {
105          data[data[idx].prev].next = idx;
106        } else {
107          first[data[idx].value] = idx;
108        }
109        if (data[idx].next != -1) {
110          data[data[idx].next].prev = idx;
111        }
112        index[data[idx].item] = idx;
113      }
114      data.pop_back();
115    }
116
117    void unlace(int idx) {
118      if (data[idx].prev != -1) {
119        data[data[idx].prev].next = data[idx].next;
120      } else {
121        first[data[idx].value] = data[idx].next;
122      }
123      if (data[idx].next != -1) {
124        data[data[idx].next].prev = data[idx].prev;
125      }
126    }
127
128    void lace(int idx) {
129      if ((int)first.size() <= data[idx].value) {
130        first.resize(data[idx].value + 1, -1);
131      }
132      data[idx].next = first[data[idx].value];
133      if (data[idx].next != -1) {
134        data[data[idx].next].prev = idx;
135      }
136      first[data[idx].value] = idx;
137      data[idx].prev = -1;
138    }
139
140  public:
141    /// \brief Insert a pair of item and priority into the heap.
142    ///
143    /// Adds \c p.first to the heap with priority \c p.second.
144    /// \param p The pair to insert.
145    void push(const Pair& p) {
146      push(p.first, p.second);
147    }
148
149    /// \brief Insert an item into the heap with the given priority.
150    ///   
151    /// Adds \c i to the heap with priority \c p.
152    /// \param i The item to insert.
153    /// \param p The priority of the item.
154    void push(const Item &i, const Prio &p) {
155      int idx = data.size();
156      index[i] = idx;
157      data.push_back(LinearItem(i, p));
158      lace(idx);
159      if (p < minimal) {
160        minimal = p;
161      }
162    }
163
[1758]164    /// \brief Returns the item with minimum priority.
[1724]165    ///
[1758]166    /// This method returns the item with minimum priority.
[1724]167    /// \pre The heap must be nonempty. 
168    Item top() const {
169      while (first[minimal] == -1) {
170        ++minimal;
171      }
172      return data[first[minimal]].item;
173    }
174
[1758]175    /// \brief Returns the minimum priority.
[1724]176    ///
[1758]177    /// It returns the minimum priority.
[1724]178    /// \pre The heap must be nonempty.
179    Prio prio() const {
180      while (first[minimal] == -1) {
181        ++minimal;
182      }
183      return minimal;
184    }
185
[1758]186    /// \brief Deletes the item with minimum priority.
[1724]187    ///
[1758]188    /// This method deletes the item with minimum priority from the heap. 
[1724]189    /// \pre The heap must be non-empty. 
190    void pop() {
191      while (first[minimal] == -1) {
192        ++minimal;
193      }
194      int idx = first[minimal];
195      index[data[idx].item] = -2;
196      unlace(idx);
197      relocate_last(idx);
198    }
199
200    /// \brief Deletes \c i from the heap.
201    ///
202    /// This method deletes item \c i from the heap, if \c i was
203    /// already stored in the heap.
204    /// \param i The item to erase.
205    void erase(const Item &i) {
206      int idx = index[i];
207      index[data[idx].item] = -2;
208      unlace(idx);
209      relocate_last(idx);
210    }
211
212   
213    /// \brief Returns the priority of \c i.
214    ///
215    /// This function returns the priority of item \c i. 
216    /// \pre \c i must be in the heap.
217    /// \param i The item.
218    Prio operator[](const Item &i) const {
219      int idx = index[i];
220      return data[idx].value;
221    }
222
223    /// \brief \c i gets to the heap with priority \c p independently
224    /// if \c i was already there.
225    ///
226    /// This method calls \ref push(\c i, \c p) if \c i is not stored
227    /// in the heap and sets the priority of \c i to \c p otherwise.
228    /// \param i The item.
229    /// \param p The priority.
230    void set(const Item &i, const Prio &p) {
231      int idx = index[i];
232      if (idx < 0) {
233        push(i,p);
234      } else if (p > data[idx].value) {
235        increase(i, p);
236      } else {
237        decrease(i, p);
238      }
239    }
240
241    /// \brief Decreases the priority of \c i to \c p.
242
243    /// This method decreases the priority of item \c i to \c p.
244    /// \pre \c i must be stored in the heap with priority at least \c
245    /// p relative to \c Compare.
246    /// \param i The item.
247    /// \param p The priority.
248    void decrease(const Item &i, const Prio &p) {
249      int idx = index[i];
250      unlace(idx);
251      data[idx].value = p;
252      if (p < minimal) {
253        minimal = p;
254      }
255      lace(idx);
256    }
257   
258    /// \brief Increases the priority of \c i to \c p.
259    ///
260    /// This method sets the priority of item \c i to \c p.
261    /// \pre \c i must be stored in the heap with priority at most \c
262    /// p relative to \c Compare.
263    /// \param i The item.
264    /// \param p The priority.
265    void increase(const Item &i, const Prio &p) {
266      int idx = index[i];
267      unlace(idx);
268      data[idx].value = p;
269      lace(idx);
270    }
271
272    /// \brief Returns if \c item is in, has already been in, or has
273    /// never been in the heap.
274    ///
275    /// This method returns PRE_HEAP if \c item has never been in the
276    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
277    /// otherwise. In the latter case it is possible that \c item will
278    /// get back to the heap again.
279    /// \param i The item.
280    state_enum state(const Item &i) const {
281      int idx = index[i];
282      if (idx >= 0) idx = 0;
283      return state_enum(idx);
284    }
285
[1902]286    /// \brief Sets the state of the \c item in the heap.
287    ///
288    /// Sets the state of the \c item in the heap. It can be used to
289    /// manually clear the heap when it is important to achive the
290    /// better time complexity.
291    /// \param i The item.
292    /// \param st The state. It should not be \c IN_HEAP.
293    void state(const Item& i, state_enum st) {
294      switch (st) {
295      case POST_HEAP:
296      case PRE_HEAP:
297        if (state(i) == IN_HEAP) {
298          erase(i);
299        }
300        index[i] = st;
301        break;
302      }
303    }
304
[1724]305  private:
306
307    struct LinearItem {
308      LinearItem(const Item& _item, int _value)
309        : item(_item), value(_value) {}
310
311      Item item;
312      int value;
313
314      int prev, next;
315    };
316
317    ItemIntMap& index;
318    std::vector<int> first;
319    std::vector<LinearItem> data;
320    mutable int minimal;
321
322  }; // class LinearHeap
323
324
325  template <typename _Item, typename _ItemIntMap>
326  class LinearHeap<_Item, _ItemIntMap, false> {
327
328  public:
329    typedef _Item Item;
330    typedef int Prio;
331    typedef std::pair<Item, Prio> Pair;
332    typedef _ItemIntMap ItemIntMap;
333
334    enum state_enum {
335      IN_HEAP = 0,
336      PRE_HEAP = -1,
337      POST_HEAP = -2
338    };
339
340  public:
341
342    explicit LinearHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
343
344    int size() const { return data.size(); }
345    bool empty() const { return data.empty(); }
346
347    void clear() {
348      for (int i = 0; i < (int)data.size(); ++i) {
349        index[data[i].item] = -2;
350      }
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(LinearItem(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
[1902]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      }
491    }
492
[1724]493  private:
494
495    struct LinearItem {
496      LinearItem(const Item& _item, int _value)
497        : item(_item), value(_value) {}
498
499      Item item;
500      int value;
501
502      int prev, next;
503    };
504
505    ItemIntMap& index;
506    std::vector<int> first;
507    std::vector<LinearItem> data;
508    mutable int maximal;
509
510  }; // class LinearHeap
511
512}
513 
514#endif
Note: See TracBrowser for help on using the repository browser.