14 * express or implied, and with no claim as to its suitability for any |
14 * express or implied, and with no claim as to its suitability for any |
15 * purpose. |
15 * purpose. |
16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 #ifndef LEMON_FOURARY_HEAP_H |
19 #ifndef LEMON_QUAD_HEAP_H |
20 #define LEMON_FOURARY_HEAP_H |
20 #define LEMON_QUAD_HEAP_H |
21 |
21 |
22 ///\ingroup heaps |
22 ///\ingroup heaps |
23 ///\file |
23 ///\file |
24 ///\brief Fourary heap implementation. |
24 ///\brief Fourary (quaternary) heap implementation. |
25 |
25 |
26 #include <vector> |
26 #include <vector> |
27 #include <utility> |
27 #include <utility> |
28 #include <functional> |
28 #include <functional> |
29 |
29 |
30 namespace lemon { |
30 namespace lemon { |
31 |
31 |
32 /// \ingroup heaps |
32 /// \ingroup heaps |
33 /// |
33 /// |
34 ///\brief Fourary heap data structure. |
34 ///\brief Fourary (quaternary) heap data structure. |
35 /// |
35 /// |
36 /// This class implements the \e fourary \e heap data structure. |
36 /// This class implements the \e Fourary (\e quaternary) \e heap |
|
37 /// data structure. |
37 /// It fully conforms to the \ref concepts::Heap "heap concept". |
38 /// It fully conforms to the \ref concepts::Heap "heap concept". |
38 /// |
39 /// |
39 /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap" |
40 /// The fourary heap is a specialization of the \ref DHeap "D-ary heap" |
40 /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap", |
41 /// for <tt>D=4</tt>. It is similar to the \ref BinHeap "binary heap", |
41 /// but its nodes have at most four children, instead of two. |
42 /// but its nodes have at most four children, instead of two. |
42 /// |
43 /// |
43 /// \tparam PR Type of the priorities of the items. |
44 /// \tparam PR Type of the priorities of the items. |
44 /// \tparam IM A read-writable item map with \c int values, used |
45 /// \tparam IM A read-writable item map with \c int values, used |
45 /// internally to handle the cross references. |
46 /// internally to handle the cross references. |
46 /// \tparam CMP A functor class for comparing the priorities. |
47 /// \tparam CMP A functor class for comparing the priorities. |
47 /// The default is \c std::less<PR>. |
48 /// The default is \c std::less<PR>. |
48 /// |
49 /// |
49 ///\sa BinHeap |
50 ///\sa BinHeap |
50 ///\sa KaryHeap |
51 ///\sa DHeap |
51 #ifdef DOXYGEN |
52 #ifdef DOXYGEN |
52 template <typename PR, typename IM, typename CMP> |
53 template <typename PR, typename IM, typename CMP> |
53 #else |
54 #else |
54 template <typename PR, typename IM, typename CMP = std::less<PR> > |
55 template <typename PR, typename IM, typename CMP = std::less<PR> > |
55 #endif |
56 #endif |
56 class FouraryHeap { |
57 class QuadHeap { |
57 public: |
58 public: |
58 /// Type of the item-int map. |
59 /// Type of the item-int map. |
59 typedef IM ItemIntMap; |
60 typedef IM ItemIntMap; |
60 /// Type of the priorities. |
61 /// Type of the priorities. |
61 typedef PR Prio; |
62 typedef PR Prio; |
90 /// |
91 /// |
91 /// Constructor. |
92 /// Constructor. |
92 /// \param map A map that assigns \c int values to the items. |
93 /// \param map A map that assigns \c int values to the items. |
93 /// It is used internally to handle the cross references. |
94 /// It is used internally to handle the cross references. |
94 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
95 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
95 explicit FouraryHeap(ItemIntMap &map) : _iim(map) {} |
96 explicit QuadHeap(ItemIntMap &map) : _iim(map) {} |
96 |
97 |
97 /// \brief Constructor. |
98 /// \brief Constructor. |
98 /// |
99 /// |
99 /// Constructor. |
100 /// Constructor. |
100 /// \param map A map that assigns \c int values to the items. |
101 /// \param map A map that assigns \c int values to the items. |
101 /// It is used internally to handle the cross references. |
102 /// It is used internally to handle the cross references. |
102 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
103 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
103 /// \param comp The function object used for comparing the priorities. |
104 /// \param comp The function object used for comparing the priorities. |
104 FouraryHeap(ItemIntMap &map, const Compare &comp) |
105 QuadHeap(ItemIntMap &map, const Compare &comp) |
105 : _iim(map), _comp(comp) {} |
106 : _iim(map), _comp(comp) {} |
106 |
107 |
107 /// \brief The number of items stored in the heap. |
108 /// \brief The number of items stored in the heap. |
108 /// |
109 /// |
109 /// This function returns the number of items stored in the heap. |
110 /// This function returns the number of items stored in the heap. |