# Changeset 1331:7e93d3f0406d in lemon-0.x for src/lemon/bin_heap.h

Ignore:
Timestamp:
04/09/05 21:30:49 (15 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1770
Message:

Documentation improvments.

File:
1 edited

Unmodified
Added
Removed
• ## src/lemon/bin_heap.h

 r1270 typedef Compare                          PrioCompare; /** * Each Item element have a state associated to it. It may be "in heap", * "pre heap" or "post heap". The later two are indifferent from the * heap's point of view, but may be useful to the user. * * The ItemIntMap _should_ be initialized in such way, that it maps * PRE_HEAP (-1) to any element to be put in the heap... */ ///\todo it is used nowhere /// /// \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 later two are indifferent from the /// heap's point of view, but may be useful to the user. /// /// The ItemIntMap _should_ be initialized in such way, that it maps /// PRE_HEAP (-1) to any element to be put in the heap... enum state_enum { IN_HEAP = 0, std::vector data; Compare comp; // FIXME: jo ez igy??? ItemIntMap &iim; public: ///The constructor /** \c _iim should be given to the constructor, since it is used internally to handle the cross references. */ /// \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 BinHeap(ItemIntMap &_iim) : iim(_iim) {} ///The constructor /** \c _iim 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. /// /// 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. /// /// \param _comp The comparator function object. BinHeap(ItemIntMap &_iim, const Compare &_comp) : iim(_iim), comp(_comp) {} ///The number of items stored in the heap. /** Returns the number of items stored in the heap. */ /// The number of items stored in the heap. /// /// \brief Returns the number of items stored in the heap. int size() const { return data.size(); } ///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 data.empty(); } public: ///Adds \c p.first to the heap with priority \c p.second. /** Adds \c p.first to the heap with priority \c p.second. \c p.first must not be stored in the heap. */ /// \brief Insert a pair of item and priority into the heap. /// /// Adds \c p.first to the heap with priority \c p.second. /// \param p The pair to insert. void push(const PairType &p) { int n = data.size(); } ///Adds \c i to the heap with priority \c p. /** Adds \c i to the heap with priority \c p. \pre \c i must not be stored in the heap. */ /// \brief Insert an item into the heap with the given heap. /// /// Adds \c i to the heap with priority \c p. /// \param i The item to insert. /// \param p The priority of the item. void push(const Item &i, const Prio &p) { push(PairType(i,p)); } ///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 data[0].first; } ///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. Prio prio() const { return data[0].second; } ///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() { rmidx(0); } ///Deletes \c i from the heap. /** This method deletes item \c i from the heap, if \c i was already stored in the heap. */ /// \brief Deletes \c i from the heap. /// /// This method deletes item \c i from the heap, if \c i was /// already stored in the heap. /// \param i The item to erase. void erase(const Item &i) { rmidx(iim[i]); ///Returns the priority of \c i. /** This function returns the priority of item \c i. \pre \c i must be in the heap. */ /// \brief Returns the priority of \c i. /// /// This function returns the priority of item \c i. /// \pre \c i must be in the heap. /// \param i The item. Prio operator[](const Item &i) const { int idx = iim[i]; } ///\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 \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. /// \param i The item. /// \param p The priority. void set(const Item &i, const Prio &p) { int idx = iim[i]; } ///Decreases the priority of \c i to \c p. /** This method decreases the priority of item \c i to \c p. \pre \c i must be stored in the heap with priority at least \c p relative to \c Compare. */ /// \brief Decreases the priority of \c i to \c p. /// This method decreases the priority of item \c i to \c p. /// \pre \c i must be stored in the heap with priority at least \c /// p relative to \c Compare. /// \param i The item. /// \param p The priority. void decrease(const Item &i, const Prio &p) { int idx = iim[i]; } ///Increases the priority of \c i to \c p. /** This method sets the priority of item \c i to \c p. \pre \c i must be stored in the heap with priority at most \c p relative to \c Compare. */ /// \brief Increases the priority of \c i to \c p. /// /// This method sets the priority of item \c i to \c p. /// \pre \c i must be stored in the heap with priority at most \c /// p relative to \c Compare. /// \param i The item. /// \param p The priority. void increase(const Item &i, const Prio &p) { int idx = iim[i]; } ///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. /// \param i The item. state_enum state(const Item &i) const { int s = iim[i];
Note: See TracChangeset for help on using the changeset viewer.