Changes in lemon/concepts/heap.h [529:f5bc148f7e1f:584:33c6b6e755cd] in lemon-main
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/concepts/heap.h
r529 r584 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 item-int 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 item-int 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, ///< = 0. The "in heap" state constant. 75 PRE_HEAP = -1, ///< = -1. The "pre heap" state constant. 76 POST_HEAP = -2 ///< = -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.