COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/linear_heap.h @ 1763:49045f2d28d4

Last change on this file since 1763:49045f2d28d4 was 1758:4bfe670710e0, checked in by Balazs Dezso, 14 years ago

Doc fix

File size: 12.1 KB
Line 
1/* -*- C++ -*-
2 * lemon/linear_heap.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
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
30  /// \addtogroup auxdat
31  /// @{
32
33  /// \brief A Linear Heap implementation.
34  ///
35  /// This class implements the \e linear \e heap data structure. A \e heap
36  /// is a data structure for storing items with specified values called \e
37  /// priorities in such a way that finding the item with minimum priority is
38  /// efficient. The linear heap is very simple implementation, it can store
39  /// only integer priorities and it stores for each priority in the [0..C]
40  /// range a list of items. So it should be used only when the priorities
41  /// are small. It is not intended to use as dijkstra heap.
42  ///
43  /// \param _Item Type of the items to be stored. 
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 _Item, typename _ItemIntMap, bool minimize = true >
49  class LinearHeap {
50
51  public:
52    typedef _Item 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 LinearHeap(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.
93    void clear() {
94      for (int i = 0; i < (int)data.size(); ++i) {
95        index[data[i].item] = -2;
96      }
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(LinearItem(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  private:
288
289    struct LinearItem {
290      LinearItem(const Item& _item, int _value)
291        : item(_item), value(_value) {}
292
293      Item item;
294      int value;
295
296      int prev, next;
297    };
298
299    ItemIntMap& index;
300    std::vector<int> first;
301    std::vector<LinearItem> data;
302    mutable int minimal;
303
304  }; // class LinearHeap
305
306
307  template <typename _Item, typename _ItemIntMap>
308  class LinearHeap<_Item, _ItemIntMap, false> {
309
310  public:
311    typedef _Item Item;
312    typedef int Prio;
313    typedef std::pair<Item, Prio> Pair;
314    typedef _ItemIntMap ItemIntMap;
315
316    enum state_enum {
317      IN_HEAP = 0,
318      PRE_HEAP = -1,
319      POST_HEAP = -2
320    };
321
322  public:
323
324    explicit LinearHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
325
326    int size() const { return data.size(); }
327    bool empty() const { return data.empty(); }
328
329    void clear() {
330      for (int i = 0; i < (int)data.size(); ++i) {
331        index[data[i].item] = -2;
332      }
333      data.clear(); first.clear(); maximal = -1;
334    }
335
336  private:
337
338    void relocate_last(int idx) {
339      if (idx + 1 != (int)data.size()) {
340        data[idx] = data.back();
341        if (data[idx].prev != -1) {
342          data[data[idx].prev].next = idx;
343        } else {
344          first[data[idx].value] = idx;
345        }
346        if (data[idx].next != -1) {
347          data[data[idx].next].prev = idx;
348        }
349        index[data[idx].item] = idx;
350      }
351      data.pop_back();
352    }
353
354    void unlace(int idx) {
355      if (data[idx].prev != -1) {
356        data[data[idx].prev].next = data[idx].next;
357      } else {
358        first[data[idx].value] = data[idx].next;
359      }
360      if (data[idx].next != -1) {
361        data[data[idx].next].prev = data[idx].prev;
362      }
363    }
364
365    void lace(int idx) {
366      if ((int)first.size() <= data[idx].value) {
367        first.resize(data[idx].value + 1, -1);
368      }
369      data[idx].next = first[data[idx].value];
370      if (data[idx].next != -1) {
371        data[data[idx].next].prev = idx;
372      }
373      first[data[idx].value] = idx;
374      data[idx].prev = -1;
375    }
376
377  public:
378
379    void push(const Pair& p) {
380      push(p.first, p.second);
381    }
382
383    void push(const Item &i, const Prio &p) {
384      int idx = data.size();
385      index[i] = idx;
386      data.push_back(LinearItem(i, p));
387      lace(idx);
388      if (data[idx].value > maximal) {
389        maximal = data[idx].value;
390      }
391    }
392
393    Item top() const {
394      while (first[maximal] == -1) {
395        --maximal;
396      }
397      return data[first[maximal]].item;
398    }
399
400    Prio prio() const {
401      while (first[maximal] == -1) {
402        --maximal;
403      }
404      return maximal;
405    }
406
407    void pop() {
408      while (first[maximal] == -1) {
409        --maximal;
410      }
411      int idx = first[maximal];
412      index[data[idx].item] = -2;
413      unlace(idx);
414      relocate_last(idx);
415    }
416
417    void erase(const Item &i) {
418      int idx = index[i];
419      index[data[idx].item] = -2;
420      unlace(idx);
421      relocate_last(idx);
422    }
423
424    Prio operator[](const Item &i) const {
425      int idx = index[i];
426      return data[idx].value;
427    }
428
429    void set(const Item &i, const Prio &p) {
430      int idx = index[i];
431      if (idx < 0) {
432        push(i,p);
433      } else if (p > data[idx].value) {
434        decrease(i, p);
435      } else {
436        increase(i, p);
437      }
438    }
439
440    void decrease(const Item &i, const Prio &p) {
441      int idx = index[i];
442      unlace(idx);
443      data[idx].value = p;
444      if (p > maximal) {
445        maximal = p;
446      }
447      lace(idx);
448    }
449   
450    void increase(const Item &i, const Prio &p) {
451      int idx = index[i];
452      unlace(idx);
453      data[idx].value = p;
454      lace(idx);
455    }
456
457    state_enum state(const Item &i) const {
458      int idx = index[i];
459      if (idx >= 0) idx = 0;
460      return state_enum(idx);
461    }
462
463  private:
464
465    struct LinearItem {
466      LinearItem(const Item& _item, int _value)
467        : item(_item), value(_value) {}
468
469      Item item;
470      int value;
471
472      int prev, next;
473    };
474
475    ItemIntMap& index;
476    std::vector<int> first;
477    std::vector<LinearItem> data;
478    mutable int maximal;
479
480  }; // class LinearHeap
481
482}
483 
484#endif
Note: See TracBrowser for help on using the repository browser.