1 // boost heap 2 // 3 // Copyright (C) 2010-2011 Tim Blechmann 4 // 5 // Distributed under the Boost Software License, Version 1.0. (See 6 // accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 9 #ifndef BOOST_HEAP_POLICIES_HPP 10 #define BOOST_HEAP_POLICIES_HPP 11 12 #include <boost/concept_check.hpp> 13 #include <boost/parameter/name.hpp> 14 #include <boost/parameter/template_keyword.hpp> 15 #include <boost/parameter/aux_/void.hpp> 16 #include <boost/parameter/binding.hpp> 17 #include <boost/parameter/parameters.hpp> 18 #include <boost/type_traits/conditional.hpp> 19 #include <boost/type_traits/integral_constant.hpp> 20 #include <boost/type_traits/is_void.hpp> 21 22 #ifdef BOOST_HAS_PRAGMA_ONCE 23 #pragma once 24 #endif 25 26 namespace boost { 27 namespace heap { 28 29 #ifndef BOOST_DOXYGEN_INVOKED 30 BOOST_PARAMETER_TEMPLATE_KEYWORD(allocator) 31 BOOST_PARAMETER_TEMPLATE_KEYWORD(compare) 32 33 namespace tag { struct stable; } 34 35 template <bool T> 36 struct stable: 37 boost::parameter::template_keyword<tag::stable, boost::integral_constant<bool, T> > 38 {}; 39 40 namespace tag { struct mutable_; } 41 42 template <bool T> 43 struct mutable_: 44 boost::parameter::template_keyword<tag::mutable_, boost::integral_constant<bool, T> > 45 {}; 46 47 48 namespace tag { struct constant_time_size; } 49 50 template <bool T> 51 struct constant_time_size: 52 boost::parameter::template_keyword<tag::constant_time_size, boost::integral_constant<bool, T> > 53 {}; 54 55 namespace tag { struct store_parent_pointer; } 56 57 template <bool T> 58 struct store_parent_pointer: 59 boost::parameter::template_keyword<tag::store_parent_pointer, boost::integral_constant<bool, T> > 60 {}; 61 62 namespace tag { struct arity; } 63 64 template <unsigned int T> 65 struct arity: 66 boost::parameter::template_keyword<tag::arity, boost::integral_constant<int, T> > 67 {}; 68 69 namespace tag { struct objects_per_page; } 70 71 template <unsigned int T> 72 struct objects_per_page: 73 boost::parameter::template_keyword<tag::objects_per_page, boost::integral_constant<int, T> > 74 {}; 75 76 BOOST_PARAMETER_TEMPLATE_KEYWORD(stability_counter_type) 77 78 namespace detail { 79 80 template <typename bound_args, typename tag_type> 81 struct has_arg 82 { 83 typedef typename boost::parameter::binding<bound_args, tag_type, void>::type type; 84 static const bool value = !boost::is_void<type>::value; 85 }; 86 87 template <typename bound_args> 88 struct extract_stable 89 { 90 static const bool has_stable = has_arg<bound_args, tag::stable>::value; 91 92 typedef typename boost::conditional<has_stable, 93 typename has_arg<bound_args, tag::stable>::type, 94 boost::false_type 95 >::type stable_t; 96 97 static const bool value = stable_t::value; 98 }; 99 100 template <typename bound_args> 101 struct extract_mutable 102 { 103 static const bool has_mutable = has_arg<bound_args, tag::mutable_>::value; 104 105 typedef typename boost::conditional<has_mutable, 106 typename has_arg<bound_args, tag::mutable_>::type, 107 boost::false_type 108 >::type mutable_t; 109 110 static const bool value = mutable_t::value; 111 }; 112 113 } 114 115 #else 116 117 /** \brief Specifies the predicate for the heap order 118 */ 119 template <typename T> 120 struct compare{}; 121 122 /** \brief Configure heap as mutable 123 * 124 * Certain heaps need to be configured specifically do be mutable. 125 * 126 * */ 127 template <bool T> 128 struct mutable_{}; 129 130 /** \brief Specifies allocator for the internal memory management 131 */ 132 template <typename T> 133 struct allocator{}; 134 135 /** \brief Configure a heap as \b stable 136 * 137 * A priority queue is stable, if elements with the same priority are popped from the heap, in the same order as 138 * they are inserted. 139 * */ 140 template <bool T> 141 struct stable{}; 142 143 /** \brief Specifies the type for stability counter 144 * 145 * */ 146 template <typename IntType> 147 struct stability_counter_type{}; 148 149 /** \brief Configures complexity of <tt> size() </tt> 150 * 151 * Specifies, whether size() should have linear or constant complexity. 152 * */ 153 template <bool T> 154 struct constant_time_size{}; 155 156 /** \brief Store parent pointer in heap node. 157 * 158 * Maintaining a parent pointer adds some maintenance and size overhead, but iterating a heap is more efficient. 159 * */ 160 template <bool T> 161 struct store_parent_pointer{}; 162 163 /** \brief Specify arity. 164 * 165 * Specifies the arity of a D-ary heap 166 * */ 167 template <unsigned int T> 168 struct arity{}; 169 #endif 170 171 } /* namespace heap */ 172 } /* namespace boost */ 173 174 #endif /* BOOST_HEAP_POLICIES_HPP */ 175