1.1 --- a/src/include/fib_heap.h Thu Apr 22 14:11:28 2004 +0000
1.2 +++ b/src/include/fib_heap.h Thu Apr 22 14:50:24 2004 +0000
1.3 @@ -1,55 +1,7 @@
1.4 // -*- C++ -*-
1.5 -/*
1.6 - *template <typename Item,
1.7 - * typename Prio,
1.8 - * typename ItemIntMap,
1.9 - * typename Compare = std::less<Prio> >
1.10 - *
1.11 - *constructors:
1.12 - *
1.13 - *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare)
1.14 - *
1.15 - *Member functions:
1.16 - *
1.17 - *int size() : returns the number of elements in the heap
1.18 - *
1.19 - *bool empty() : true iff size()=0
1.20 - *
1.21 - *void set(Item, Prio) : calls push(Item, Prio) if Item is not
1.22 - * in the heap, and calls decrease/increase(Item, Prio) otherwise
1.23 - *
1.24 - *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
1.25 - * mustn't be in the heap.
1.26 - *
1.27 - *Item top() : returns the Item with least Prio.
1.28 - * Must be called only if heap is nonempty.
1.29 - *
1.30 - *Prio prio() : returns the least Prio
1.31 - * Must be called only if heap is nonempty.
1.32 - *
1.33 - *Prio get(Item) : returns Prio of Item
1.34 - * Must be called only if Item is in heap.
1.35 - *
1.36 - *void pop() : deletes the Item with least Prio
1.37 - *
1.38 - *void erase(Item) : deletes Item from the heap if it was already there
1.39 - *
1.40 - *void decrease(Item, P) : decreases prio of Item to P.
1.41 - * Item must be in the heap with prio at least P.
1.42 - *
1.43 - *void increase(Item, P) : sets prio of Item to P.
1.44 - *
1.45 - *state_enum state(Item) : returns PRE_HEAP if Item has not been in the
1.46 - * heap until now, IN_HEAP if it is in the heap at the moment, and
1.47 - * POST_HEAP otherwise. In the latter case it is possible that Item
1.48 - * will get back to the heap again.
1.49 - *
1.50 - *In Fibonacci heaps, increase and erase are not efficient, in case of
1.51 - *many calls to these operations, it is better to use bin_heap.
1.52 - */
1.53
1.54 -#ifndef FIB_HEAP_H
1.55 -#define FIB_HEAP_H
1.56 +#ifndef HUGO_FIB_HEAP_H
1.57 +#define HUGO_FIB_HEAP_H
1.58
1.59 ///\file
1.60 ///\brief Fibonacci Heap implementation.
1.61 @@ -60,13 +12,44 @@
1.62
1.63 namespace hugo {
1.64
1.65 - /// A Fibonacci Heap implementation.
1.66 - template <typename Item, typename Prio, typename ItemIntMap,
1.67 + /// An implementation of the Fibonacci Heap.
1.68 +
1.69 + /**
1.70 + This class implements the \e Fibonacci \e heap data structure. A \e
1.71 + heap is a data structure for storing items with specified priorities,
1.72 + such that finding the item with minimum priority is efficient. In a
1.73 + heap one can change the priority of an item, and to add or erase an
1.74 + item.
1.75 +
1.76 + The methods \ref increase and \ref erase are not efficient, in
1.77 + case of many calls to these operations, it is better to use
1.78 + a binary heap.
1.79 +
1.80 + /param Item The type of the items to be stored.
1.81 + /param Prio The type of the priority of the items.
1.82 + /param ItemIntMap A read and writable Item int map, for the usage of
1.83 + the heap.
1.84 + /param Compare A class for the comparison of the priorities. The
1.85 + default is \c std::less<Prio>.
1.86 +
1.87 + */
1.88 +
1.89 +#ifdef DOXYGEN
1.90 + template <typename Item,
1.91 + typename Prio,
1.92 + typename ItemIntMap,
1.93 + typename Compare>
1.94 +#else
1.95 + template <typename Item,
1.96 + typename Prio,
1.97 + typename ItemIntMap,
1.98 typename Compare = std::less<Prio> >
1.99 +#endif
1.100 class FibHeap {
1.101 -
1.102 + public:
1.103 typedef Prio PrioType;
1.104
1.105 + private:
1.106 class store;
1.107
1.108 std::vector<store> container;
1.109 @@ -74,7 +57,7 @@
1.110 ItemIntMap &iimap;
1.111 Compare comp;
1.112 int num_items;
1.113 -
1.114 +
1.115 ///\todo It is use nowhere
1.116 ///\todo It doesn't conform to the naming conventions.
1.117 public:
1.118 @@ -86,18 +69,137 @@
1.119
1.120 public :
1.121
1.122 - FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {}
1.123 - FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
1.124 + FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
1.125 + FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
1.126 iimap(_iimap), comp(_comp), num_items() {}
1.127
1.128 + ///The number of items stored in the heap.
1.129 +
1.130 + /**
1.131 + Returns the number of items stored in the heap.
1.132 + */
1.133 + int size() const { return num_items; }
1.134 +
1.135 + ///Checks if the heap stores no items.
1.136
1.137 - int size() const {
1.138 - return num_items;
1.139 + /**
1.140 + Returns true iff the heap stores no items.
1.141 + */
1.142 + bool empty() const { return num_items==0; }
1.143 +
1.144 + ///Item \c item gets to the heap with priority \c value independently if \c item was already there.
1.145 +
1.146 + /**
1.147 + This method calls \ref push(item, value) if \c item is not
1.148 + stored in the heap, and it calls \ref decrease(it, \c value) or
1.149 + \ref increase(it, \c value) otherwise.
1.150 + */
1.151 + void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van
1.152 +
1.153 + ///Adds \c item to the heap with priority \c value.
1.154 +
1.155 + /**
1.156 + Adds \c item to the heap with priority \c value.
1.157 + \pre \c item must not be stored in the heap.
1.158 + */
1.159 + void push (Item const it, PrioType const value); /*vigyazat: az implementacioban it van*/
1.160 +
1.161 +
1.162 + ///Returns the item having the minimum priority w.r.t. Compare.
1.163 +
1.164 + /**
1.165 + This method returns the item having the minimum priority w.r.t. Compare.
1.166 + \pre The heap must be nonempty.
1.167 + */
1.168 + Item top() const { return container[minimum].name; }
1.169 +
1.170 +
1.171 + ///Returns the minimum priority w.r.t. Compare.
1.172 +
1.173 + /**
1.174 + It returns the minimum priority w.r.t. Compare.
1.175 + \pre The heap must be nonempty.
1.176 + */
1.177 + PrioType prio() const { return container[minimum].prio; }
1.178 +
1.179 +
1.180 + ///Returns the priority of \c item.
1.181 +
1.182 + /**
1.183 + It returns the priority of \c item.
1.184 + \pre \c item must be in the heap.
1.185 + */
1.186 + PrioType& operator[](const Item& it) { return container[iimap[it]].prio; }
1.187 +
1.188 + ///Returns the priority of \c item.
1.189 +
1.190 + /**
1.191 + It returns the priority of \c item.
1.192 + \pre \c item must be in the heap.
1.193 + */
1.194 + const PrioType& operator[](const Item& it) const {
1.195 + return container[iimap[it]].prio;
1.196 }
1.197
1.198
1.199 - bool empty() const { return num_items==0; }
1.200 + ///Deletes the item with minimum priority w.r.t. Compare.
1.201
1.202 + /**
1.203 + This method deletes the item with minimum priority w.r.t.
1.204 + Compare from the heap.
1.205 + \pre The heap must be non-empty.
1.206 + */
1.207 + void pop();
1.208 +
1.209 + ///Deletes \c item from the heap.
1.210 +
1.211 + /**
1.212 + This method deletes \c item from the heap, if \c item was already
1.213 + stored in the heap. It is quite inefficient in Fibonacci heaps.
1.214 + */
1.215 + void erase (const Item& item); /*vigyazat: az implementacioban it van*/
1.216 +
1.217 + ///Decreases the priority of \c item to \c value.
1.218 +
1.219 + /**
1.220 + This method decreases the priority of \c item to \c value.
1.221 + \pre \c item must be stored in the heap with priority at least \c
1.222 + value w.r.t. Compare.
1.223 + */
1.224 + void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/
1.225 +
1.226 +
1.227 + ///Increases the priority of \c item to \c value.
1.228 +
1.229 + /**
1.230 + This method sets the priority of \c item to \c value. Though
1.231 + there is no precondition on the priority of \c item, this
1.232 + method should be used only if one wants to \e increase
1.233 + (w.r.t. Compare) the priority of \c item, because this
1.234 + method is inefficient.
1.235 + */
1.236 + void increase (Item it, PrioType const value) {
1.237 + erase(it);
1.238 + push(it, value);
1.239 + }
1.240 +
1.241 +
1.242 + ///Tells if \c item is in, was in, or has not been in the heap.
1.243 +
1.244 + /**
1.245 + This method returns PRE_HEAP if \c item has never been in the
1.246 + heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
1.247 + otherwise. In the latter case it is possible that \c item will
1.248 + get back to the heap again.
1.249 + */
1.250 + state_enum state(const Item &it); /*vigyazat: az implementacioban it van*/
1.251 +
1.252 +
1.253 +
1.254 + // **********************************************************************
1.255 + // IMPLEMENTATIONS
1.256 + // **********************************************************************
1.257 +
1.258
1.259 void set (Item const it, PrioType const value) {
1.260 int i=iimap[it];
1.261 @@ -139,30 +241,6 @@
1.262 }
1.263
1.264
1.265 - Item top() const {
1.266 - return container[minimum].name;
1.267 - }
1.268 -
1.269 -
1.270 - PrioType prio() const {
1.271 - return container[minimum].prio;
1.272 - }
1.273 -
1.274 -
1.275 -
1.276 -
1.277 - PrioType& operator[](const Item& it) {
1.278 - return container[iimap[it]].prio;
1.279 - }
1.280 -
1.281 - const PrioType& operator[](const Item& it) const {
1.282 - return container[iimap[it]].prio;
1.283 - }
1.284 -
1.285 -// const PrioType get(const Item& it) const {
1.286 -// return container[iimap[it]].prio;
1.287 -// }
1.288 -
1.289 void pop() {
1.290 /*The first case is that there are only one root.*/
1.291 if ( container[minimum].left_neighbor==minimum ) {
1.292 @@ -223,12 +301,6 @@
1.293 }
1.294
1.295
1.296 - void increase (Item it, PrioType const value) {
1.297 - erase(it);
1.298 - push(it, value);
1.299 - }
1.300 -
1.301 -
1.302 state_enum state(const Item &it) const {
1.303 int i=iimap[it];
1.304 if( i>=0 ) {