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