# Changeset 709:0747f332c478 in lemon-1.2 for lemon/bin_heap.h

Ignore:
Timestamp:
07/08/09 17:21:30 (12 years ago)
Branch:
default
Phase:
public
Message:

Improve and unify the documentation of heaps (#299)
and avoid a warning in SimpleBucketHeap::operator[].

File:
1 edited

Unmodified
Removed
• ## lemon/bin_heap.h

 r683 ///\ingroup auxdat ///\file ///\brief Binary Heap implementation. ///\brief Binary heap implementation. #include namespace lemon { ///\ingroup auxdat /// \ingroup auxdat /// ///\brief A Binary Heap implementation. /// \brief Binary heap data structure. /// ///This class implements the \e binary \e heap data structure. /// This class implements the \e binary \e heap data structure. /// It fully conforms to the \ref concepts::Heap "heap concept". /// ///A \e heap is a data structure for storing items with specified values ///called \e priorities in such a way that finding the item with minimum ///priority is efficient. \c CMP specifies the ordering of the priorities. ///In a heap one can change the priority of an item, add or erase an ///item, etc. /// ///\tparam PR Type of the priority of the items. ///\tparam IM A read and writable item map with int values, used internally ///to handle the cross references. ///\tparam CMP A functor class for the ordering of the priorities. ///The default is \c std::less. /// ///\sa FibHeap ///\sa Dijkstra /// \tparam PR Type of the priorities of the items. /// \tparam IM A read-writable item map with \c int values, used /// internally to handle the cross references. /// \tparam CMP A functor class for comparing the priorities. /// The default is \c std::less. #ifdef DOXYGEN template #else template > #endif class BinHeap { public: ///\e /// Type of the item-int map. typedef IM ItemIntMap; ///\e /// Type of the priorities. typedef PR Prio; ///\e /// Type of the items stored in the heap. typedef typename ItemIntMap::Key Item; ///\e /// Type of the item-priority pairs. typedef std::pair Pair; ///\e /// Functor type for comparing the priorities. typedef CMP Compare; /// \brief Type to represent the items states. /// /// Each Item element have a state associated to it. It may be "in heap", /// "pre heap" or "post heap". The latter two are indifferent from the /// \brief Type to represent the states of the items. /// /// Each item has a state associated to it. It can be "in heap", /// "pre-heap" or "post-heap". The latter two are indifferent from the /// heap's point of view, but may be useful to the user. /// public: /// \brief The constructor. /// /// The constructor. /// \param map should be given to the constructor, since it is used /// internally to handle the cross references. The value of the map /// must be \c PRE_HEAP (-1) for every item. /// \brief Constructor. /// /// Constructor. /// \param map A map that assigns \c int values to the items. /// It is used internally to handle the cross references. /// The assigned value must be \c PRE_HEAP (-1) for each item. explicit BinHeap(ItemIntMap &map) : _iim(map) {} /// \brief The constructor. /// /// The constructor. /// \param map 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 comp The comparator function object. /// \brief Constructor. /// /// Constructor. /// \param map A map that assigns \c int values to the items. /// It is used internally to handle the cross references. /// The assigned value must be \c PRE_HEAP (-1) for each item. /// \param comp The function object used for comparing the priorities. BinHeap(ItemIntMap &map, const Compare &comp) : _iim(map), _comp(comp) {} /// 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. /// /// This function returns the number of items stored in the heap. int size() const { return _data.size(); } /// \brief Checks if the heap stores no items. /// /// Returns \c true if and only if the heap stores no items. /// \brief Check if the heap is empty. /// /// This function returns \c true if the heap is empty. bool empty() const { return _data.empty(); } /// \brief Make empty this heap. /// /// Make empty this heap. It does not change the cross reference map. /// If you want to reuse what is not surely empty you should first clear /// the heap and after that you should set the cross reference map for /// each item to \c PRE_HEAP. /// \brief Make the heap empty. /// /// This functon makes the heap empty. /// It does not change the cross reference map. If you want to reuse /// a heap that is not surely empty, you should first clear it and /// then you should set the cross reference map to \c PRE_HEAP /// for each item. void clear() { _data.clear(); public: /// \brief Insert a pair of item and priority into the heap. /// /// Adds \c p.first to the heap with priority \c p.second. /// This function inserts \c p.first to the heap with priority /// \c p.second. /// \param p The pair to insert. /// \pre \c p.first must not be stored in the heap. void push(const Pair &p) { int n = _data.size(); } /// \brief Insert an item into the heap with the given heap. /// /// Adds \c i to the heap with priority \c p. /// \brief Insert an item into the heap with the given priority. /// /// This function inserts the given item into the heap with the /// given priority. /// \param i The item to insert. /// \param p The priority of the item. /// \pre \e i must not be stored in the heap. void push(const Item &i, const Prio &p) { push(Pair(i,p)); } /// \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. /// \brief Return the item having minimum priority. /// /// This function returns the item having minimum priority. /// \pre The heap must be non-empty. Item top() const { return _data[0].first; } /// \brief Returns the minimum priority relative to \c Compare. /// /// It returns the minimum priority relative to \c Compare. /// \pre The heap must be nonempty. /// \brief The minimum priority. /// /// This function returns the minimum priority. /// \pre The heap must be non-empty. Prio prio() const { return _data[0].second; } /// \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. /// \brief Remove the item having minimum priority. /// /// This function removes the item having minimum priority. /// \pre The heap must be non-empty. void pop() { } /// \brief Deletes \c i from the heap. /// /// This method deletes item \c i from the heap. /// \param i The item to erase. /// \pre The item should be in the heap. /// \brief Remove the given item from the heap. /// /// This function removes the given item from the heap if it is /// already stored. /// \param i The item to delete. /// \pre \e i must be in the heap. void erase(const Item &i) { int h = _iim[i]; } /// \brief Returns the priority of \c i. /// /// This function returns the priority of item \c i. /// \param i The item. /// \pre \c i must be in the heap. /// \brief The priority of the given item. /// /// This function returns the priority of the given item. /// \param i The item. /// \pre \e i must be in the heap. Prio operator[](const Item &i) const { int idx = _iim[i]; } /// \brief \c i gets to the heap with priority \c p independently /// if \c i was already there. /// /// This method calls \ref push(\c i, \c p) if \c i is not stored /// in the heap and sets the priority of \c i to \c p otherwise. /// \brief Set the priority of an item or insert it, if it is /// not stored in the heap. /// /// This method sets the priority of the given item if it is /// already stored in the heap. Otherwise it inserts the given /// item into the heap with the given priority. /// \param i The item. /// \param p The priority. } /// \brief Decreases the priority of \c i to \c p. /// /// This method decreases the priority of item \c i to \c p. /// \brief Decrease the priority of an item to the given value. /// /// This function decreases the priority of an item to the given value. /// \param i The item. /// \param p The priority. /// \pre \c i must be stored in the heap with priority at least \c /// p relative to \c Compare. /// \pre \e i must be stored in the heap with priority at least \e p. void decrease(const Item &i, const Prio &p) { int idx = _iim[i]; } /// \brief Increases the priority of \c i to \c p. /// /// This method sets the priority of item \c i to \c p. /// \brief Increase the priority of an item to the given value. /// /// This function increases the priority of an item to the given value. /// \param i The item. /// \param p The priority. /// \pre \c i must be stored in the heap with priority at most \c /// p relative to \c Compare. /// \pre \e i must be stored in the heap with priority at most \e p. void increase(const Item &i, const Prio &p) { int idx = _iim[i]; } /// \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. /// \brief Return the state of an item. /// /// This method returns \c PRE_HEAP if the given item has never /// been in the heap, \c IN_HEAP if it is in the heap at the moment, /// and \c POST_HEAP otherwise. /// In the latter case it is possible that the item will get back /// to the heap again. /// \param i The item. State state(const Item &i) const { } /// \brief Sets the state of the \c item in the heap. /// /// Sets the state of the \c item in the heap. It can be used to /// manually clear the heap when it is important to achive the /// better time complexity. /// \brief Set the state of an item in the heap. /// /// This function sets the state of the given item in the heap. /// It can be used to manually clear the heap when it is important /// to achive better time complexity. /// \param i The item. /// \param st The state. It should not be \c IN_HEAP. } /// \brief Replaces an item in the heap. /// /// The \c i item is replaced with \c j item. The \c i item should /// be in the heap, while the \c j should be out of the heap. The /// \c i item will out of the heap and \c j will be in the heap /// with the same prioriority as prevoiusly the \c i item. /// \brief Replace an item in the heap. /// /// This function replaces item \c i with item \c j. /// Item \c i must be in the heap, while \c j must be out of the heap. /// After calling this method, item \c i will be out of the /// heap and \c j will be in the heap with the same prioriority /// as item \c i had before. void replace(const Item& i, const Item& j) { int idx = _iim[i];
Note: See TracChangeset for help on using the changeset viewer.