COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/heap.h

Last change on this file was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 7 years ago

Apply unify-sources.sh to the source tree

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