COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/concept/heap.h @ 1359:1581f961cfaa

Last change on this file since 1359:1581f961cfaa was 1359:1581f961cfaa, checked in by Alpar Juttner, 15 years ago

Correct the english name of EGRES.

File size: 5.9 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/concept/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///\ingroup concept
18///\file
19///\brief Classes for representing heaps.
20///
21
22#ifndef LEMON_CONCEPT_HEAP_H
23#define LEMON_CONCEPT_HEAP_H
24
25#include <lemon/invalid.h>
26
27namespace lemon {
28  namespace concept {
29    /// \addtogroup concept
30    /// @{
31
32
33    /// \brief A concept structure describes the main interface of heaps.
34    ///
35    /// A concept structure describes the main interface of heaps.
36    ///
37    template <typename Item, typename Prio, typename ItemIntMap>
38    class Heap {
39    public:
40 
41
42      /// \brief Type to represent the items states.
43      ///
44      /// Each Item element have a state associated to it. It may be "in heap",
45      /// "pre heap" or "post heap". The later two are indifferent from the
46      /// heap's point of view, but may be useful to the user.
47      ///
48      /// The ItemIntMap _should_ be initialized in such way, that it maps
49      /// PRE_HEAP (-1) to any element to be put in the heap...
50      enum state_enum {
51        IN_HEAP = 0,
52        PRE_HEAP = -1,
53        POST_HEAP = -2
54      };
55     
56      /// \brief The constructor.
57      ///
58      /// The constructor.
59      /// \param _iim should be given to the constructor, since it is used
60      /// internally to handle the cross references. The value of the map
61      /// should be PRE_HEAP (-1) for each element.
62      explicit Heap(ItemIntMap &_iim) {}
63
64      /// The number of items stored in the heap.
65      ///
66      /// \brief Returns the number of items stored in the heap.
67      int size() const { return 0; }
68      /// \brief Checks if the heap stores no items.
69      ///
70      /// Returns \c true if and only if the heap stores no items.
71      bool empty() const { return false; }
72
73      /// \brief Insert an item into the heap with the given heap.
74      ///   
75      /// Adds \c i to the heap with priority \c p.
76      /// \param i The item to insert.
77      /// \param p The priority of the item.
78      void push(const Item &i, const Prio &p) {}
79
80      /// \brief Returns the item with minimum priority.
81      ///
82      /// This method returns the item with minimum priority. 
83      /// \pre The heap must be nonempty. 
84      Item top() const {}
85
86      /// \brief Returns the minimum priority.
87      ///
88      /// It returns the minimum priority.
89      /// \pre The heap must be nonempty.
90      Prio prio() const {}
91
92      /// \brief Deletes the item with minimum priority.
93      ///
94      /// This method deletes the item with minimum priority.
95      /// \pre The heap must be non-empty. 
96      void pop() {}
97
98      /// \brief Deletes \c i from the heap.
99      ///
100      /// This method deletes item \c i from the heap, if \c i was
101      /// already stored in the heap.
102      /// \param i The item to erase.
103      void erase(const Item &i) {}
104
105      /// \brief Returns the priority of \c i.
106      ///
107      /// This function returns the priority of item \c i. 
108      /// \pre \c i must be in the heap.
109      /// \param i The item.
110      Prio operator[](const Item &i) const {}
111
112      /// \brief \c i gets to the heap with priority \c p independently
113      /// if \c i was already there.
114      ///
115      /// This method calls \ref push(\c i, \c p) if \c i is not stored
116      /// in the heap and sets the priority of \c i to \c p otherwise.
117      /// It may throw an \e UnderFlowPriorityException.
118      /// \param i The item.
119      /// \param p The priority.
120      void set(const Item &i, const Prio &p) {}
121     
122      /// \brief Decreases the priority of \c i to \c p.
123      ///
124      /// This method decreases the priority of item \c i to \c p.
125      /// \pre \c i must be stored in the heap with priority at least \c p.
126      /// \param i The item.
127      /// \param p The priority.
128      void decrease(const Item &i, const Prio &p) {}
129
130      /// \brief Increases the priority of \c i to \c p.
131      ///
132      /// This method sets the priority of item \c i to \c p.
133      /// \pre \c i must be stored in the heap with priority at most \c
134      /// p relative to \c Compare.
135      /// \param i The item.
136      /// \param p The priority.
137      void increase(const Item &i, const Prio &p) {}
138
139      /// \brief Returns if \c item is in, has already been in, or has
140      /// never been in the heap.
141      ///
142      /// This method returns PRE_HEAP if \c item has never been in the
143      /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
144      /// otherwise. In the latter case it is possible that \c item will
145      /// get back to the heap again.
146      /// \param i The item.
147      state_enum state(const Item &i) const {}
148
149
150      template <typename _Heap>
151      struct Constraints {
152      public:
153   
154        void constraints() {
155          Item item;
156          Prio prio;
157
158          ignore_unused_variable_warning(item);
159          ignore_unused_variable_warning(prio);
160
161          typedef typename _Heap::state_enum state_enum;
162          state_enum state;
163
164          ignore_unused_variable_warning(state);
165     
166          _Heap heap1 = _Heap(map);
167
168          ignore_unused_variable_warning(heap1);
169     
170          heap.push(item, prio);
171
172          prio = heap.prio();
173          item = heap.top();
174
175          heap.pop();
176
177          heap.set(item, prio);
178          heap.decrease(item, prio);
179          heap.increase(item, prio);
180          prio = heap[item];
181
182          heap.erase(item);
183
184          state = heap.state(item);
185
186          state = _Heap::PRE_HEAP;
187          state = _Heap::IN_HEAP;
188          state = _Heap::POST_HEAP;
189        }
190   
191        _Heap& heap;
192        ItemIntMap& map;
193
194        Constraints() : heap(0), map(0) {}
195      };
196    };
197
198    /// @}
199  } // namespace lemon
200}
201#endif // LEMON_CONCEPT_PATH_H
Note: See TracBrowser for help on using the repository browser.