1.1 --- a/src/lemon/concept/heap.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,201 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/concept/heap.h - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -///\ingroup concept
1.21 -///\file
1.22 -///\brief Classes for representing heaps.
1.23 -///
1.24 -
1.25 -#ifndef LEMON_CONCEPT_HEAP_H
1.26 -#define LEMON_CONCEPT_HEAP_H
1.27 -
1.28 -#include <lemon/invalid.h>
1.29 -
1.30 -namespace lemon {
1.31 - namespace concept {
1.32 - /// \addtogroup concept
1.33 - /// @{
1.34 -
1.35 -
1.36 - /// \brief A concept structure describes the main interface of heaps.
1.37 - ///
1.38 - /// A concept structure describes the main interface of heaps.
1.39 - ///
1.40 - template <typename Item, typename Prio, typename ItemIntMap>
1.41 - class Heap {
1.42 - public:
1.43 -
1.44 -
1.45 - /// \brief Type to represent the items states.
1.46 - ///
1.47 - /// Each Item element have a state associated to it. It may be "in heap",
1.48 - /// "pre heap" or "post heap". The later two are indifferent from the
1.49 - /// heap's point of view, but may be useful to the user.
1.50 - ///
1.51 - /// The ItemIntMap _should_ be initialized in such way, that it maps
1.52 - /// PRE_HEAP (-1) to any element to be put in the heap...
1.53 - enum state_enum {
1.54 - IN_HEAP = 0,
1.55 - PRE_HEAP = -1,
1.56 - POST_HEAP = -2
1.57 - };
1.58 -
1.59 - /// \brief The constructor.
1.60 - ///
1.61 - /// The constructor.
1.62 - /// \param _iim should be given to the constructor, since it is used
1.63 - /// internally to handle the cross references. The value of the map
1.64 - /// should be PRE_HEAP (-1) for each element.
1.65 - explicit Heap(ItemIntMap &_iim) {}
1.66 -
1.67 - /// The number of items stored in the heap.
1.68 - ///
1.69 - /// \brief Returns the number of items stored in the heap.
1.70 - int size() const { return 0; }
1.71 - /// \brief Checks if the heap stores no items.
1.72 - ///
1.73 - /// Returns \c true if and only if the heap stores no items.
1.74 - bool empty() const { return false; }
1.75 -
1.76 - /// \brief Insert an item into the heap with the given heap.
1.77 - ///
1.78 - /// Adds \c i to the heap with priority \c p.
1.79 - /// \param i The item to insert.
1.80 - /// \param p The priority of the item.
1.81 - void push(const Item &i, const Prio &p) {}
1.82 -
1.83 - /// \brief Returns the item with minimum priority.
1.84 - ///
1.85 - /// This method returns the item with minimum priority.
1.86 - /// \pre The heap must be nonempty.
1.87 - Item top() const {}
1.88 -
1.89 - /// \brief Returns the minimum priority.
1.90 - ///
1.91 - /// It returns the minimum priority.
1.92 - /// \pre The heap must be nonempty.
1.93 - Prio prio() const {}
1.94 -
1.95 - /// \brief Deletes the item with minimum priority.
1.96 - ///
1.97 - /// This method deletes the item with minimum priority.
1.98 - /// \pre The heap must be non-empty.
1.99 - void pop() {}
1.100 -
1.101 - /// \brief Deletes \c i from the heap.
1.102 - ///
1.103 - /// This method deletes item \c i from the heap, if \c i was
1.104 - /// already stored in the heap.
1.105 - /// \param i The item to erase.
1.106 - void erase(const Item &i) {}
1.107 -
1.108 - /// \brief Returns the priority of \c i.
1.109 - ///
1.110 - /// This function returns the priority of item \c i.
1.111 - /// \pre \c i must be in the heap.
1.112 - /// \param i The item.
1.113 - Prio operator[](const Item &i) const {}
1.114 -
1.115 - /// \brief \c i gets to the heap with priority \c p independently
1.116 - /// if \c i was already there.
1.117 - ///
1.118 - /// This method calls \ref push(\c i, \c p) if \c i is not stored
1.119 - /// in the heap and sets the priority of \c i to \c p otherwise.
1.120 - /// It may throw an \e UnderFlowPriorityException.
1.121 - /// \param i The item.
1.122 - /// \param p The priority.
1.123 - void set(const Item &i, const Prio &p) {}
1.124 -
1.125 - /// \brief Decreases the priority of \c i to \c p.
1.126 - ///
1.127 - /// This method decreases the priority of item \c i to \c p.
1.128 - /// \pre \c i must be stored in the heap with priority at least \c p.
1.129 - /// \param i The item.
1.130 - /// \param p The priority.
1.131 - void decrease(const Item &i, const Prio &p) {}
1.132 -
1.133 - /// \brief Increases the priority of \c i to \c p.
1.134 - ///
1.135 - /// This method sets the priority of item \c i to \c p.
1.136 - /// \pre \c i must be stored in the heap with priority at most \c
1.137 - /// p relative to \c Compare.
1.138 - /// \param i The item.
1.139 - /// \param p The priority.
1.140 - void increase(const Item &i, const Prio &p) {}
1.141 -
1.142 - /// \brief Returns if \c item is in, has already been in, or has
1.143 - /// never been in the heap.
1.144 - ///
1.145 - /// This method returns PRE_HEAP if \c item has never been in the
1.146 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
1.147 - /// otherwise. In the latter case it is possible that \c item will
1.148 - /// get back to the heap again.
1.149 - /// \param i The item.
1.150 - state_enum state(const Item &i) const {}
1.151 -
1.152 -
1.153 - template <typename _Heap>
1.154 - struct Constraints {
1.155 - public:
1.156 -
1.157 - void constraints() {
1.158 - Item item;
1.159 - Prio prio;
1.160 -
1.161 - ignore_unused_variable_warning(item);
1.162 - ignore_unused_variable_warning(prio);
1.163 -
1.164 - typedef typename _Heap::state_enum state_enum;
1.165 - state_enum state;
1.166 -
1.167 - ignore_unused_variable_warning(state);
1.168 -
1.169 - _Heap heap1 = _Heap(map);
1.170 -
1.171 - ignore_unused_variable_warning(heap1);
1.172 -
1.173 - heap.push(item, prio);
1.174 -
1.175 - prio = heap.prio();
1.176 - item = heap.top();
1.177 -
1.178 - heap.pop();
1.179 -
1.180 - heap.set(item, prio);
1.181 - heap.decrease(item, prio);
1.182 - heap.increase(item, prio);
1.183 - prio = heap[item];
1.184 -
1.185 - heap.erase(item);
1.186 -
1.187 - state = heap.state(item);
1.188 -
1.189 - state = _Heap::PRE_HEAP;
1.190 - state = _Heap::IN_HEAP;
1.191 - state = _Heap::POST_HEAP;
1.192 - }
1.193 -
1.194 - _Heap& heap;
1.195 - ItemIntMap& map;
1.196 -
1.197 - Constraints() : heap(0), map(0) {}
1.198 - };
1.199 - };
1.200 -
1.201 - /// @}
1.202 - } // namespace lemon
1.203 -}
1.204 -#endif // LEMON_CONCEPT_PATH_H