# HG changeset patch # User deba # Date 1129286400 0 # Node ID 75fe24093ded8253beeafada591efdfd7ff36d48 # Parent d8c28868f074c9bb029fdb4de43f17dced99990c Added clear function to heaps and concept diff -r d8c28868f074 -r 75fe24093ded lemon/bin_heap.h --- a/lemon/bin_heap.h Fri Oct 07 11:05:35 2005 +0000 +++ b/lemon/bin_heap.h Fri Oct 14 10:40:00 2005 +0000 @@ -109,6 +109,16 @@ /// Returns \c true if and only if the heap stores no items. bool empty() const { return data.empty(); } + /// \brief Make empty this heap. + /// + /// Make empty this heap. + void clear() { + for (int i = 0; i < (int)data.size(); ++i) { + iim.set(data[i].first, POST_HEAP); + } + data.clear(); + } + private: static int parent(int i) { return (i-1)/2; } static int second_child(int i) { return 2*i+2; } diff -r d8c28868f074 -r 75fe24093ded lemon/concept/heap.h --- a/lemon/concept/heap.h Fri Oct 07 11:05:35 2005 +0000 +++ b/lemon/concept/heap.h Fri Oct 14 10:40:00 2005 +0000 @@ -61,15 +61,21 @@ /// should be PRE_HEAP (-1) for each element. explicit Heap(ItemIntMap &_iim) {} - /// The number of items stored in the heap. + /// \brief The number of items stored in the heap. /// - /// \brief Returns the number of items stored in the heap. + /// Returns the number of items stored in the heap. int size() const { return 0; } + /// \brief Checks if the heap stores no items. /// /// Returns \c true if and only if the heap stores no items. bool empty() const { return false; } + /// \brief Makes empty this heap. + /// + /// Makes this heap empty. + void clear(); + /// \brief Insert an item into the heap with the given heap. /// /// Adds \c i to the heap with priority \c p. @@ -189,6 +195,8 @@ state = _Heap::PRE_HEAP; state = _Heap::IN_HEAP; state = _Heap::POST_HEAP; + + heap.clear(); } _Heap& heap; diff -r d8c28868f074 -r 75fe24093ded lemon/fib_heap.h --- a/lemon/fib_heap.h Fri Oct 07 11:05:35 2005 +0000 +++ b/lemon/fib_heap.h Fri Oct 14 10:40:00 2005 +0000 @@ -88,143 +88,125 @@ POST_HEAP = -2 }; - ///The constructor - - /** - \c _iimap should be given to the constructor, since it is - used internally to handle the cross references. - */ + /// \brief The constructor + /// + /// \c _iimap should be given to the constructor, since it is + /// used internally to handle the cross references. explicit FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} - ///The constructor - - /** - \c _iimap should be given to the constructor, since it is used - internally to handle the cross references. \c _comp is an - object for ordering of the priorities. - */ + /// \brief The constructor + /// + /// \c _iimap should be given to the constructor, since it is used + /// internally to handle the cross references. \c _comp is an + /// object for ordering of the priorities. FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), iimap(_iimap), comp(_comp), num_items() {} - ///The number of items stored in the heap. - - /** - Returns the number of items stored in the heap. - */ + /// \brief The number of items stored in the heap. + /// + /// Returns the number of items stored in the heap. int size() const { return num_items; } - ///Checks if the heap stores no items. - - /** - Returns \c true if and only if the heap stores no items. - */ + /// \brief Checks if the heap stores no items. + /// + /// Returns \c true if and only if the heap stores no items. bool empty() const { return num_items==0; } - ///\c item gets to the heap with priority \c value independently if \c item was already there. + /// \brief Make empty this heap. + /// + /// Make empty this heap. + void clear() { + for (int i = 0; i < (int)container.size(); ++i) { + iimap[container[i].name] = -2; + } + container.clear(); minimum = 0; num_items = 0; + } - /** - This method calls \ref push(\c item, \c value) if \c item is not - stored in the heap and it calls \ref decrease(\c item, \c value) or - \ref increase(\c item, \c value) otherwise. - */ + /// \brief \c item gets to the heap with priority \c value independently + /// if \c item was already there. + /// + /// This method calls \ref push(\c item, \c value) if \c item is not + /// stored in the heap and it calls \ref decrease(\c item, \c value) or + /// \ref increase(\c item, \c value) otherwise. void set (Item const item, PrioType const value); - ///Adds \c item to the heap with priority \c value. - - /** - Adds \c item to the heap with priority \c value. - \pre \c item must not be stored in the heap. - */ + /// \brief Adds \c item to the heap with priority \c value. + /// + /// Adds \c item to the heap with priority \c value. + /// \pre \c item must not be stored in the heap. void push (Item const item, PrioType const value); - ///Returns the item with minimum priority relative to \c Compare. - - /** - This method returns the item with minimum priority relative to \c - Compare. - \pre The heap must be nonempty. - */ + /// \brief Returns the item with minimum priority relative to \c Compare. + /// + /// This method returns the item with minimum priority relative to \c + /// Compare. + /// \pre The heap must be nonempty. Item top() const { return container[minimum].name; } - ///Returns the minimum priority relative to \c Compare. - - /** - It returns the minimum priority relative to \c Compare. - \pre The heap must be nonempty. - */ + /// \brief Returns the minimum priority relative to \c Compare. + /// + /// It returns the minimum priority relative to \c Compare. + /// \pre The heap must be nonempty. PrioType prio() const { return container[minimum].prio; } - ///Returns the priority of \c item. - - /** - This function returns the priority of \c item. - \pre \c item must be in the heap. - */ + /// \brief Returns the priority of \c item. + /// + /// This function returns the priority of \c item. + /// \pre \c item must be in the heap. PrioType& operator[](const Item& item) { return container[iimap[item]].prio; } - ///Returns the priority of \c item. - - /** - It returns the priority of \c item. - \pre \c item must be in the heap. - */ + /// \brief Returns the priority of \c item. + /// + /// It returns the priority of \c item. + /// \pre \c item must be in the heap. const PrioType& operator[](const Item& item) const { return container[iimap[item]].prio; } - ///Deletes the item with minimum priority relative to \c Compare. - - /** - This method deletes the item with minimum priority relative to \c - Compare from the heap. - \pre The heap must be non-empty. - */ + /// \brief Deletes the item with minimum priority relative to \c Compare. + /// + /// This method deletes the item with minimum priority relative to \c + /// Compare from the heap. + /// \pre The heap must be non-empty. void pop(); - ///Deletes \c item from the heap. - - /** - This method deletes \c item from the heap, if \c item was already - stored in the heap. It is quite inefficient in Fibonacci heaps. - */ + /// \brief Deletes \c item from the heap. + /// + /// This method deletes \c item from the heap, if \c item was already + /// stored in the heap. It is quite inefficient in Fibonacci heaps. void erase (const Item& item); - ///Decreases the priority of \c item to \c value. - - /** - This method decreases the priority of \c item to \c value. - \pre \c item must be stored in the heap with priority at least \c - value relative to \c Compare. - */ + /// \brief Decreases the priority of \c item to \c value. + /// + /// This method decreases the priority of \c item to \c value. + /// \pre \c item must be stored in the heap with priority at least \c + /// value relative to \c Compare. void decrease (Item item, PrioType const value); - ///Increases the priority of \c item to \c value. - - /** - This method sets the priority of \c item to \c value. Though - there is no precondition on the priority of \c item, this - method should be used only if it is indeed necessary to increase - (relative to \c Compare) the priority of \c item, because this - method is inefficient. - */ + /// \brief Increases the priority of \c item to \c value. + /// + /// This method sets the priority of \c item to \c value. Though + /// there is no precondition on the priority of \c item, this + /// method should be used only if it is indeed necessary to increase + /// (relative to \c Compare) the priority of \c item, because this + /// method is inefficient. void increase (Item item, PrioType const value) { erase(item); push(item, value); } - ///Returns if \c item is in, has already been in, or has never been in the heap. - - /** - This method returns PRE_HEAP if \c item has never been in the - heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP - otherwise. In the latter case it is possible that \c item will - get back to the heap again. - */ + /// \brief Returns if \c item is in, has already been in, or has never + /// been in the heap. + /// + /// This method returns PRE_HEAP if \c item has never been in the + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP + /// otherwise. In the latter case it is possible that \c item will + /// get back to the heap again. state_enum state(const Item &item) const { int i=iimap[item]; if( i>=0 ) { diff -r d8c28868f074 -r 75fe24093ded lemon/radix_heap.h --- a/lemon/radix_heap.h Fri Oct 07 11:05:35 2005 +0000 +++ b/lemon/radix_heap.h Fri Oct 14 10:40:00 2005 +0000 @@ -26,9 +26,6 @@ namespace lemon { - /// \addtogroup auxdat - /// @{ - /// \brief Exception thrown by RadixHeap. /// /// This Exception is thrown when a smaller priority @@ -43,6 +40,8 @@ } }; + /// \ingroup auxdata + /// /// \brief A Radix Heap implementation. /// /// This class implements the \e radix \e heap data structure. A \e heap @@ -108,27 +107,18 @@ /// \brief The constructor. /// /// The constructor. - /// \param _iim should be given to the constructor, since it is used - /// internally to handle the cross references. The value of the map - /// should be PRE_HEAP (-1) for each element. - explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) { - boxes.push_back(RadixBox(0, 1)); - boxes.push_back(RadixBox(1, 1)); - } - - /// \brief The constructor. - /// - /// The constructor. /// /// \param _iim It should be given to the constructor, since it is used /// internally to handle the cross references. The value of the map /// should be PRE_HEAP (-1) for each element. /// + /// \param minimal The initial minimal value of the heap. /// \param capacity It determines the initial capacity of the heap. - RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) { - boxes.push_back(RadixBox(0, 1)); - boxes.push_back(RadixBox(1, 1)); - while (upper(boxes.back(), capacity)) { + RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0) + : iim(_iim) { + boxes.push_back(RadixBox(minimal, 1)); + boxes.push_back(RadixBox(minimal + 1, 1)); + while (lower(boxes.size() - 1, capacity + minimal - 1)) { extend(); } } @@ -142,6 +132,21 @@ /// Returns \c true if and only if the heap stores no items. bool empty() const { return data.empty(); } + /// \brief Make empty this heap. + /// + /// Make empty this heap. + void clear(int minimal = 0, int capacity = 0) { + for (int i = 0; i < (int)data.size(); ++i) { + iim[data[i].item] = -2; + } + data.clear(); boxes.clear(); + boxes.push_back(RadixBox(minimal, 1)); + boxes.push_back(RadixBox(minimal + 1, 1)); + while (lower(boxes.size() - 1, capacity + minimal - 1)) { + extend(); + } + } + private: bool upper(int box, Prio prio) { @@ -271,7 +276,7 @@ public: - /// \brief Insert an item into the heap with the given heap. + /// \brief Insert an item into the heap with the given priority. /// /// Adds \c i to the heap with priority \c p. /// \param i The item to insert. @@ -292,7 +297,7 @@ /// This method returns the item with minimum priority. /// \pre The heap must be nonempty. Item top() const { - const_cast*>(this)->moveDown(); + const_cast&>(*this).moveDown(); return data[boxes[0].first].item; } @@ -301,7 +306,7 @@ /// It returns the minimum priority. /// \pre The heap must be nonempty. Prio prio() const { - const_cast*>(this)->moveDown(); + const_cast&>(*this).moveDown(); return data[boxes[0].first].prio; }