# Changeset 1717:75fe24093ded in lemon-0.x

Ignore:
Timestamp:
10/14/05 12:40:00 (16 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2244
Message:

Added clear function to heaps and concept

Location:
lemon
Files:
4 edited

Unmodified
Removed
• ## lemon/bin_heap.h

 r1435 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; }
• ## lemon/concept/heap.h

 r1494 explicit Heap(ItemIntMap &_iim) {} /// The number of items stored in the heap. /// /// \brief 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 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. state = _Heap::IN_HEAP; state = _Heap::POST_HEAP; heap.clear(); }
• ## lemon/fib_heap.h

 r1435 }; ///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. /** 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 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; } /// \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); ///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];