COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/linear_heap.h @ 1750:5c76ebbb4818

Last change on this file since 1750:5c76ebbb4818 was 1724:b20777184ba8, checked in by Balazs Dezso, 14 years ago

Heap not for the dijkstra

It will be used in the minCut algorithm

File size: 12.2 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 relative to \c Compare.
166    ///
167    /// This method returns the item with minimum priority relative to \c
168    /// Compare. 
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 relative to \c Compare.
178    ///
179    /// It returns the minimum priority relative to \c Compare.
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 relative to \c Compare.
189    ///
190    /// This method deletes the item with minimum priority relative to \c
191    /// Compare from the heap. 
192    /// \pre The heap must be non-empty. 
193    void pop() {
194      while (first[minimal] == -1) {
195        ++minimal;
196      }
197      int idx = first[minimal];
198      index[data[idx].item] = -2;
199      unlace(idx);
200      relocate_last(idx);
201    }
202
203    /// \brief Deletes \c i from the heap.
204    ///
205    /// This method deletes item \c i from the heap, if \c i was
206    /// already stored in the heap.
207    /// \param i The item to erase.
208    void erase(const Item &i) {
209      int idx = index[i];
210      index[data[idx].item] = -2;
211      unlace(idx);
212      relocate_last(idx);
213    }
214
215   
216    /// \brief Returns the priority of \c i.
217    ///
218    /// This function returns the priority of item \c i. 
219    /// \pre \c i must be in the heap.
220    /// \param i The item.
221    Prio operator[](const Item &i) const {
222      int idx = index[i];
223      return data[idx].value;
224    }
225
226    /// \brief \c i gets to the heap with priority \c p independently
227    /// if \c i was already there.
228    ///
229    /// This method calls \ref push(\c i, \c p) if \c i is not stored
230    /// in the heap and sets the priority of \c i to \c p otherwise.
231    /// \param i The item.
232    /// \param p The priority.
233    void set(const Item &i, const Prio &p) {
234      int idx = index[i];
235      if (idx < 0) {
236        push(i,p);
237      } else if (p > data[idx].value) {
238        increase(i, p);
239      } else {
240        decrease(i, p);
241      }
242    }
243
244    /// \brief Decreases the priority of \c i to \c p.
245
246    /// This method decreases the priority of item \c i to \c p.
247    /// \pre \c i must be stored in the heap with priority at least \c
248    /// p relative to \c Compare.
249    /// \param i The item.
250    /// \param p The priority.
251    void decrease(const Item &i, const Prio &p) {
252      int idx = index[i];
253      unlace(idx);
254      data[idx].value = p;
255      if (p < minimal) {
256        minimal = p;
257      }
258      lace(idx);
259    }
260   
261    /// \brief Increases the priority of \c i to \c p.
262    ///
263    /// This method sets the priority of item \c i to \c p.
264    /// \pre \c i must be stored in the heap with priority at most \c
265    /// p relative to \c Compare.
266    /// \param i The item.
267    /// \param p The priority.
268    void increase(const Item &i, const Prio &p) {
269      int idx = index[i];
270      unlace(idx);
271      data[idx].value = p;
272      lace(idx);
273    }
274
275    /// \brief Returns if \c item is in, has already been in, or has
276    /// never been in the heap.
277    ///
278    /// This method returns PRE_HEAP if \c item has never been in the
279    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
280    /// otherwise. In the latter case it is possible that \c item will
281    /// get back to the heap again.
282    /// \param i The item.
283    state_enum state(const Item &i) const {
284      int idx = index[i];
285      if (idx >= 0) idx = 0;
286      return state_enum(idx);
287    }
288
289  private:
290
291    struct LinearItem {
292      LinearItem(const Item& _item, int _value)
293        : item(_item), value(_value) {}
294
295      Item item;
296      int value;
297
298      int prev, next;
299    };
300
301    ItemIntMap& index;
302    std::vector<int> first;
303    std::vector<LinearItem> data;
304    mutable int minimal;
305
306  }; // class LinearHeap
307
308
309  template <typename _Item, typename _ItemIntMap>
310  class LinearHeap<_Item, _ItemIntMap, false> {
311
312  public:
313    typedef _Item Item;
314    typedef int Prio;
315    typedef std::pair<Item, Prio> Pair;
316    typedef _ItemIntMap ItemIntMap;
317
318    enum state_enum {
319      IN_HEAP = 0,
320      PRE_HEAP = -1,
321      POST_HEAP = -2
322    };
323
324  public:
325
326    explicit LinearHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
327
328    int size() const { return data.size(); }
329    bool empty() const { return data.empty(); }
330
331    void clear() {
332      for (int i = 0; i < (int)data.size(); ++i) {
333        index[data[i].item] = -2;
334      }
335      data.clear(); first.clear(); maximal = -1;
336    }
337
338  private:
339
340    void relocate_last(int idx) {
341      if (idx + 1 != (int)data.size()) {
342        data[idx] = data.back();
343        if (data[idx].prev != -1) {
344          data[data[idx].prev].next = idx;
345        } else {
346          first[data[idx].value] = idx;
347        }
348        if (data[idx].next != -1) {
349          data[data[idx].next].prev = idx;
350        }
351        index[data[idx].item] = idx;
352      }
353      data.pop_back();
354    }
355
356    void unlace(int idx) {
357      if (data[idx].prev != -1) {
358        data[data[idx].prev].next = data[idx].next;
359      } else {
360        first[data[idx].value] = data[idx].next;
361      }
362      if (data[idx].next != -1) {
363        data[data[idx].next].prev = data[idx].prev;
364      }
365    }
366
367    void lace(int idx) {
368      if ((int)first.size() <= data[idx].value) {
369        first.resize(data[idx].value + 1, -1);
370      }
371      data[idx].next = first[data[idx].value];
372      if (data[idx].next != -1) {
373        data[data[idx].next].prev = idx;
374      }
375      first[data[idx].value] = idx;
376      data[idx].prev = -1;
377    }
378
379  public:
380
381    void push(const Pair& p) {
382      push(p.first, p.second);
383    }
384
385    void push(const Item &i, const Prio &p) {
386      int idx = data.size();
387      index[i] = idx;
388      data.push_back(LinearItem(i, p));
389      lace(idx);
390      if (data[idx].value > maximal) {
391        maximal = data[idx].value;
392      }
393    }
394
395    Item top() const {
396      while (first[maximal] == -1) {
397        --maximal;
398      }
399      return data[first[maximal]].item;
400    }
401
402    Prio prio() const {
403      while (first[maximal] == -1) {
404        --maximal;
405      }
406      return maximal;
407    }
408
409    void pop() {
410      while (first[maximal] == -1) {
411        --maximal;
412      }
413      int idx = first[maximal];
414      index[data[idx].item] = -2;
415      unlace(idx);
416      relocate_last(idx);
417    }
418
419    void erase(const Item &i) {
420      int idx = index[i];
421      index[data[idx].item] = -2;
422      unlace(idx);
423      relocate_last(idx);
424    }
425
426    Prio operator[](const Item &i) const {
427      int idx = index[i];
428      return data[idx].value;
429    }
430
431    void set(const Item &i, const Prio &p) {
432      int idx = index[i];
433      if (idx < 0) {
434        push(i,p);
435      } else if (p > data[idx].value) {
436        decrease(i, p);
437      } else {
438        increase(i, p);
439      }
440    }
441
442    void decrease(const Item &i, const Prio &p) {
443      int idx = index[i];
444      unlace(idx);
445      data[idx].value = p;
446      if (p > maximal) {
447        maximal = p;
448      }
449      lace(idx);
450    }
451   
452    void increase(const Item &i, const Prio &p) {
453      int idx = index[i];
454      unlace(idx);
455      data[idx].value = p;
456      lace(idx);
457    }
458
459    state_enum state(const Item &i) const {
460      int idx = index[i];
461      if (idx >= 0) idx = 0;
462      return state_enum(idx);
463    }
464
465  private:
466
467    struct LinearItem {
468      LinearItem(const Item& _item, int _value)
469        : item(_item), value(_value) {}
470
471      Item item;
472      int value;
473
474      int prev, next;
475    };
476
477    ItemIntMap& index;
478    std::vector<int> first;
479    std::vector<LinearItem> data;
480    mutable int maximal;
481
482  }; // class LinearHeap
483
484}
485 
486#endif
Note: See TracBrowser for help on using the repository browser.