Changeset 606:c5fd2d996909 in lemon for lemon/concepts/heap.h
 Timestamp:
 03/29/09 23:08:20 (10 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/concepts/heap.h
r576 r606 36 36 /// \brief The heap concept. 37 37 /// 38 /// Concept class describing the main interface of heaps. 39 template <typename Priority, typename ItemIntMap> 38 /// Concept class describing the main interface of heaps. A \e heap 39 /// is a data structure for storing items with specified values called 40 /// \e priorities in such a way that finding the item with minimum 41 /// priority is efficient. In a heap one can change the priority of an 42 /// item, add or erase an item, etc. 43 /// 44 /// \tparam PR Type of the priority of the items. 45 /// \tparam IM A read and writable item map with int values, used 46 /// internally to handle the cross references. 47 /// \tparam Comp A functor class for the ordering of the priorities. 48 /// The default is \c std::less<PR>. 49 #ifdef DOXYGEN 50 template <typename PR, typename IM, typename Comp = std::less<PR> > 51 #else 52 template <typename PR, typename IM> 53 #endif 40 54 class Heap { 41 55 public: 42 56 57 /// Type of the itemint map. 58 typedef IM ItemIntMap; 59 /// Type of the priorities. 60 typedef PR Prio; 43 61 /// Type of the items stored in the heap. 44 62 typedef typename ItemIntMap::Key Item; 45 46 /// Type of the priorities.47 typedef Priority Prio;48 63 49 64 /// \brief Type to represent the states of the items. … … 54 69 /// the user. 55 70 /// 56 /// The \c ItemIntMap must be initialized in such a way, that it57 /// assigns \c PRE_HEAP (<tt>1</tt>) to every item.71 /// The itemint map must be initialized in such way that it assigns 72 /// \c PRE_HEAP (<tt>1</tt>) to any element to be put in the heap. 58 73 enum State { 59 IN_HEAP = 0, 60 PRE_HEAP = 1, 61 POST_HEAP = 2 74 IN_HEAP = 0, ///< The "in heap" state constant. 75 PRE_HEAP = 1, ///< The "pre heap" state constant. 76 POST_HEAP = 2 ///< The "post heap" state constant. 62 77 }; 63 78 … … 120 135 /// 121 136 /// Returns the priority of the given item. 137 /// \param i The item. 122 138 /// \pre \c i must be in the heap. 123 /// \param i The item.124 139 Prio operator[](const Item &i) const {} 125 140 … … 138 153 /// 139 154 /// Decreases the priority of an item to the given value. 155 /// \param i The item. 156 /// \param p The priority. 140 157 /// \pre \c i must be stored in the heap with priority at least \c p. 158 void decrease(const Item &i, const Prio &p) {} 159 160 /// \brief Increases the priority of an item to the given value. 161 /// 162 /// Increases the priority of an item to the given value. 141 163 /// \param i The item. 142 164 /// \param p The priority. 143 void decrease(const Item &i, const Prio &p) {}144 145 /// \brief Increases the priority of an item to the given value.146 ///147 /// Increases the priority of an item to the given value.148 165 /// \pre \c i must be stored in the heap with priority at most \c p. 149 /// \param i The item.150 /// \param p The priority.151 166 void increase(const Item &i, const Prio &p) {} 152 167
Note: See TracChangeset
for help on using the changeset viewer.