COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/heap.h @ 757:f1fe0ddad6f7

Last change on this file since 757:f1fe0ddad6f7 was 757:f1fe0ddad6f7, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Move the heaps to a separate group (#299)

File size: 9.6 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
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_CONCEPTS_HEAP_H
20#define LEMON_CONCEPTS_HEAP_H
21
22///\ingroup concept
23///\file
24///\brief The concept of heaps.
25
26#include <lemon/core.h>
27#include <lemon/concept_check.h>
28
29namespace lemon {
30
31  namespace concepts {
32
33    /// \addtogroup concept
34    /// @{
35
36    /// \brief The heap concept.
37    ///
38    /// This concept class describes the main interface of heaps.
39    /// The various \ref heaps "heap structures" are efficient
40    /// implementations of the abstract data type \e priority \e queue.
41    /// They store items with specified values called \e priorities
42    /// in such a way that finding and removing the item with minimum
43    /// priority are efficient. The basic operations are adding and
44    /// erasing items, changing the priority of an item, etc.
45    ///
46    /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
47    /// Any class that conforms to this concept can be used easily in such
48    /// algorithms.
49    ///
50    /// \tparam PR Type of the priorities of the items.
51    /// \tparam IM A read-writable item map with \c int values, used
52    /// internally to handle the cross references.
53    /// \tparam CMP A functor class for comparing the priorities.
54    /// The default is \c std::less<PR>.
55#ifdef DOXYGEN
56    template <typename PR, typename IM, typename CMP>
57#else
58    template <typename PR, typename IM, typename CMP = std::less<PR> >
59#endif
60    class Heap {
61    public:
62
63      /// Type of the item-int map.
64      typedef IM ItemIntMap;
65      /// Type of the priorities.
66      typedef PR Prio;
67      /// Type of the items stored in the heap.
68      typedef typename ItemIntMap::Key Item;
69
70      /// \brief Type to represent the states of the items.
71      ///
72      /// Each item has a state associated to it. It can be "in heap",
73      /// "pre-heap" or "post-heap". The latter two are indifferent from the
74      /// heap's point of view, but may be useful to the user.
75      ///
76      /// The item-int map must be initialized in such way that it assigns
77      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
78      enum State {
79        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
80        PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
81        POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
82      };
83
84      /// \brief Constructor.
85      ///
86      /// Constructor.
87      /// \param map A map that assigns \c int values to keys of type
88      /// \c Item. It is used internally by the heap implementations to
89      /// handle the cross references. The assigned value must be
90      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
91      explicit Heap(ItemIntMap &map) {}
92
93      /// \brief Constructor.
94      ///
95      /// Constructor.
96      /// \param map A map that assigns \c int values to keys of type
97      /// \c Item. It is used internally by the heap implementations to
98      /// handle the cross references. The assigned value must be
99      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
100      /// \param comp The function object used for comparing the priorities.
101      explicit Heap(ItemIntMap &map, const CMP &comp) {}
102
103      /// \brief The number of items stored in the heap.
104      ///
105      /// This function returns the number of items stored in the heap.
106      int size() const { return 0; }
107
108      /// \brief Check if the heap is empty.
109      ///
110      /// This function returns \c true if the heap is empty.
111      bool empty() const { return false; }
112
113      /// \brief Make the heap empty.
114      ///
115      /// This functon makes the heap empty.
116      /// It does not change the cross reference map. If you want to reuse
117      /// a heap that is not surely empty, you should first clear it and
118      /// then you should set the cross reference map to \c PRE_HEAP
119      /// for each item.
120      void clear() {}
121
122      /// \brief Insert an item into the heap with the given priority.
123      ///
124      /// This function inserts the given item into the heap with the
125      /// given priority.
126      /// \param i The item to insert.
127      /// \param p The priority of the item.
128      /// \pre \e i must not be stored in the heap.
129      void push(const Item &i, const Prio &p) {}
130
131      /// \brief Return the item having minimum priority.
132      ///
133      /// This function returns the item having minimum priority.
134      /// \pre The heap must be non-empty.
135      Item top() const {}
136
137      /// \brief The minimum priority.
138      ///
139      /// This function returns the minimum priority.
140      /// \pre The heap must be non-empty.
141      Prio prio() const {}
142
143      /// \brief Remove the item having minimum priority.
144      ///
145      /// This function removes the item having minimum priority.
146      /// \pre The heap must be non-empty.
147      void pop() {}
148
149      /// \brief Remove the given item from the heap.
150      ///
151      /// This function removes the given item from the heap if it is
152      /// already stored.
153      /// \param i The item to delete.
154      /// \pre \e i must be in the heap.
155      void erase(const Item &i) {}
156
157      /// \brief The priority of the given item.
158      ///
159      /// This function returns the priority of the given item.
160      /// \param i The item.
161      /// \pre \e i must be in the heap.
162      Prio operator[](const Item &i) const {}
163
164      /// \brief Set the priority of an item or insert it, if it is
165      /// not stored in the heap.
166      ///
167      /// This method sets the priority of the given item if it is
168      /// already stored in the heap. Otherwise it inserts the given
169      /// item into the heap with the given priority.
170      ///
171      /// \param i The item.
172      /// \param p The priority.
173      void set(const Item &i, const Prio &p) {}
174
175      /// \brief Decrease the priority of an item to the given value.
176      ///
177      /// This function decreases the priority of an item to the given value.
178      /// \param i The item.
179      /// \param p The priority.
180      /// \pre \e i must be stored in the heap with priority at least \e p.
181      void decrease(const Item &i, const Prio &p) {}
182
183      /// \brief Increase the priority of an item to the given value.
184      ///
185      /// This function increases the priority of an item to the given value.
186      /// \param i The item.
187      /// \param p The priority.
188      /// \pre \e i must be stored in the heap with priority at most \e p.
189      void increase(const Item &i, const Prio &p) {}
190
191      /// \brief Return the state of an item.
192      ///
193      /// This method returns \c PRE_HEAP if the given item has never
194      /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
195      /// and \c POST_HEAP otherwise.
196      /// In the latter case it is possible that the item will get back
197      /// to the heap again.
198      /// \param i The item.
199      State state(const Item &i) const {}
200
201      /// \brief Set the state of an item in the heap.
202      ///
203      /// This function sets the state of the given item in the heap.
204      /// It can be used to manually clear the heap when it is important
205      /// to achive better time complexity.
206      /// \param i The item.
207      /// \param st The state. It should not be \c IN_HEAP.
208      void state(const Item& i, State st) {}
209
210
211      template <typename _Heap>
212      struct Constraints {
213      public:
214        void constraints() {
215          typedef typename _Heap::Item OwnItem;
216          typedef typename _Heap::Prio OwnPrio;
217          typedef typename _Heap::State OwnState;
218
219          Item item;
220          Prio prio;
221          item=Item();
222          prio=Prio();
223          ignore_unused_variable_warning(item);
224          ignore_unused_variable_warning(prio);
225
226          OwnItem own_item;
227          OwnPrio own_prio;
228          OwnState own_state;
229          own_item=Item();
230          own_prio=Prio();
231          ignore_unused_variable_warning(own_item);
232          ignore_unused_variable_warning(own_prio);
233          ignore_unused_variable_warning(own_state);
234
235          _Heap heap1(map);
236          _Heap heap2 = heap1;
237          ignore_unused_variable_warning(heap1);
238          ignore_unused_variable_warning(heap2);
239
240          int s = heap.size();
241          ignore_unused_variable_warning(s);
242          bool e = heap.empty();
243          ignore_unused_variable_warning(e);
244
245          prio = heap.prio();
246          item = heap.top();
247          prio = heap[item];
248          own_prio = heap.prio();
249          own_item = heap.top();
250          own_prio = heap[own_item];
251
252          heap.push(item, prio);
253          heap.push(own_item, own_prio);
254          heap.pop();
255
256          heap.set(item, prio);
257          heap.decrease(item, prio);
258          heap.increase(item, prio);
259          heap.set(own_item, own_prio);
260          heap.decrease(own_item, own_prio);
261          heap.increase(own_item, own_prio);
262
263          heap.erase(item);
264          heap.erase(own_item);
265          heap.clear();
266
267          own_state = heap.state(own_item);
268          heap.state(own_item, own_state);
269
270          own_state = _Heap::PRE_HEAP;
271          own_state = _Heap::IN_HEAP;
272          own_state = _Heap::POST_HEAP;
273        }
274
275        _Heap& heap;
276        ItemIntMap& map;
277      };
278    };
279
280    /// @}
281  } // namespace lemon
282}
283#endif
Note: See TracBrowser for help on using the repository browser.