COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/heap.h @ 1902:e9af75c90c28

Last change on this file since 1902:e9af75c90c28 was 1902:e9af75c90c28, checked in by Balazs Dezso, 14 years ago

state setting function for heaps

If we know that which elements were in the heap then
we can clear it in better time complexity.

File size: 6.4 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      /// \brief Sets the state of the \c item in the heap.
156      ///
157      /// Sets the state of the \c item in the heap. It can be used to
158      /// manually clear the heap when it is important to achive the
159      /// better time complexity.
160      /// \param i The item.
161      /// \param st The state. It should not be \c IN_HEAP.
162      void state(const Item& i, state_enum st) {}
163
164
165      template <typename _Heap>
166      struct Constraints {
167      public:
168   
169        void constraints() {
170          Item item;
171          Prio prio;
172
173          item=Item();
174          prio=Prio();
175
176          ignore_unused_variable_warning(item);
177          ignore_unused_variable_warning(prio);
178
179          typedef typename _Heap::state_enum state_enum;
180          state_enum state;
181
182          ignore_unused_variable_warning(state);
183     
184          _Heap heap1 = _Heap(map);
185
186          ignore_unused_variable_warning(heap1);
187     
188          heap.push(item, prio);
189
190          prio = heap.prio();
191          item = heap.top();
192
193          heap.pop();
194
195          heap.set(item, prio);
196          heap.decrease(item, prio);
197          heap.increase(item, prio);
198          prio = heap[item];
199
200          heap.erase(item);
201
202          state = heap.state(item);
203
204          state = _Heap::PRE_HEAP;
205          state = _Heap::IN_HEAP;
206          state = _Heap::POST_HEAP;
207
208          heap.clear();
209        }
210   
211        _Heap& heap;
212        ItemIntMap& map;
213
214        Constraints() : heap(0), map(0) {}
215      };
216    };
217
218    /// @}
219  } // namespace lemon
220}
221#endif // LEMON_CONCEPT_PATH_H
Note: See TracBrowser for help on using the repository browser.