COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/linear_heap.h @ 1964:df0b07457083

Last change on this file since 1964:df0b07457083 was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

File size: 12.9 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_LINEAR_HEAP_H
20#define LEMON_LINEAR_HEAP_H
21
22///\ingroup auxdat
23///\file
24///\brief Binary Heap implementation.
25
26#include <vector>
27#include <utility>
28#include <functional>
29
30namespace lemon {
31
32  /// \ingroup auxdat
33
34  /// \brief A Linear Heap implementation.
35  ///
36  /// This class implements the \e linear \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 linear heap is very simple implementation, it can store
40  /// only integer priorities and it stores for each priority in the [0..C]
41  /// range a list of items. So it should be used only when the priorities
42  /// 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 LinearHeap {
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 LinearHeap(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.
94    void clear() {
95      for (int i = 0; i < (int)data.size(); ++i) {
96        index[data[i].item] = -2;
97      }
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(LinearItem(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 LinearItem {
312      LinearItem(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<LinearItem> data;
324    mutable int minimal;
325
326  }; // class LinearHeap
327
328
329  template <typename _Item, typename _ItemIntMap>
330  class LinearHeap<_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 LinearHeap(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      for (int i = 0; i < (int)data.size(); ++i) {
353        index[data[i].item] = -2;
354      }
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(LinearItem(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_enum state(const Item &i) const {
480      int idx = index[i];
481      if (idx >= 0) idx = 0;
482      return state_enum(idx);
483    }
484
485    void state(const Item& i, state_enum 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 LinearItem {
502      LinearItem(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<LinearItem> data;
514    mutable int maximal;
515
516  }; // class LinearHeap
517
518}
519 
520#endif
Note: See TracBrowser for help on using the repository browser.