COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/heap.h @ 1875:98698b69a902

Last change on this file since 1875:98698b69a902 was 1875:98698b69a902, checked in by Alpar Juttner, 14 years ago

Happy new year to LEMON

File size: 6.0 KB
Line 
1/* -*- C++ -*-
2 * lemon/concept/heap.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2006 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      /// \brief The number of items stored in the heap.
65      ///
66      /// Returns the number of items stored in the heap.
67      int size() const { return 0; }
68
69      /// \brief Checks if the heap stores no items.
70      ///
71      /// Returns \c true if and only if the heap stores no items.
72      bool empty() const { return false; }
73
74      /// \brief Makes empty this heap.
75      ///
76      /// Makes this heap empty.
77      void clear();
78
79      /// \brief Insert an item into the heap with the given heap.
80      ///   
81      /// Adds \c i to the heap with priority \c p.
82      /// \param i The item to insert.
83      /// \param p The priority of the item.
84      void push(const Item &i, const Prio &p) {}
85
86      /// \brief Returns the item with minimum priority.
87      ///
88      /// This method returns the item with minimum priority. 
89      /// \pre The heap must be nonempty. 
90      Item top() const {}
91
92      /// \brief Returns the minimum priority.
93      ///
94      /// It returns the minimum priority.
95      /// \pre The heap must be nonempty.
96      Prio prio() const {}
97
98      /// \brief Deletes the item with minimum priority.
99      ///
100      /// This method deletes the item with minimum priority.
101      /// \pre The heap must be non-empty. 
102      void pop() {}
103
104      /// \brief Deletes \c i from the heap.
105      ///
106      /// This method deletes item \c i from the heap, if \c i was
107      /// already stored in the heap.
108      /// \param i The item to erase.
109      void erase(const Item &i) {}
110
111      /// \brief Returns the priority of \c i.
112      ///
113      /// This function returns the priority of item \c i. 
114      /// \pre \c i must be in the heap.
115      /// \param i The item.
116      Prio operator[](const Item &i) const {}
117
118      /// \brief \c i gets to the heap with priority \c p independently
119      /// if \c i was already there.
120      ///
121      /// This method calls \ref push(\c i, \c p) if \c i is not stored
122      /// in the heap and sets the priority of \c i to \c p otherwise.
123      /// It may throw an \e UnderFlowPriorityException.
124      /// \param i The item.
125      /// \param p The priority.
126      void set(const Item &i, const Prio &p) {}
127     
128      /// \brief Decreases the priority of \c i to \c p.
129      ///
130      /// This method decreases the priority of item \c i to \c p.
131      /// \pre \c i must be stored in the heap with priority at least \c p.
132      /// \param i The item.
133      /// \param p The priority.
134      void decrease(const Item &i, const Prio &p) {}
135
136      /// \brief Increases the priority of \c i to \c p.
137      ///
138      /// This method sets the priority of item \c i to \c p.
139      /// \pre \c i must be stored in the heap with priority at most \c
140      /// p relative to \c Compare.
141      /// \param i The item.
142      /// \param p The priority.
143      void increase(const Item &i, const Prio &p) {}
144
145      /// \brief Returns if \c item is in, has already been in, or has
146      /// never been in the heap.
147      ///
148      /// This method returns PRE_HEAP if \c item has never been in the
149      /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
150      /// otherwise. In the latter case it is possible that \c item will
151      /// get back to the heap again.
152      /// \param i The item.
153      state_enum state(const Item &i) const {}
154
155
156      template <typename _Heap>
157      struct Constraints {
158      public:
159   
160        void constraints() {
161          Item item;
162          Prio prio;
163
164          item=Item();
165          prio=Prio();
166
167          ignore_unused_variable_warning(item);
168          ignore_unused_variable_warning(prio);
169
170          typedef typename _Heap::state_enum state_enum;
171          state_enum state;
172
173          ignore_unused_variable_warning(state);
174     
175          _Heap heap1 = _Heap(map);
176
177          ignore_unused_variable_warning(heap1);
178     
179          heap.push(item, prio);
180
181          prio = heap.prio();
182          item = heap.top();
183
184          heap.pop();
185
186          heap.set(item, prio);
187          heap.decrease(item, prio);
188          heap.increase(item, prio);
189          prio = heap[item];
190
191          heap.erase(item);
192
193          state = heap.state(item);
194
195          state = _Heap::PRE_HEAP;
196          state = _Heap::IN_HEAP;
197          state = _Heap::POST_HEAP;
198
199          heap.clear();
200        }
201   
202        _Heap& heap;
203        ItemIntMap& map;
204
205        Constraints() : heap(0), map(0) {}
206      };
207    };
208
209    /// @}
210  } // namespace lemon
211}
212#endif // LEMON_CONCEPT_PATH_H
Note: See TracBrowser for help on using the repository browser.