3 // Copyright (C) 2010-2011 Tim Blechmann
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)
9 #ifndef BOOST_HEAP_POLICIES_HPP
10 #define BOOST_HEAP_POLICIES_HPP
12 #include <boost/parameter.hpp>
13 #include <boost/mpl/bool.hpp>
14 #include <boost/mpl/int.hpp>
15 #include <boost/mpl/void.hpp>
16 #include <boost/concept_check.hpp>
18 #ifdef BOOST_HAS_PRAGMA_ONCE
25 #ifndef BOOST_DOXYGEN_INVOKED
26 BOOST_PARAMETER_TEMPLATE_KEYWORD(allocator)
27 BOOST_PARAMETER_TEMPLATE_KEYWORD(compare)
29 namespace tag { struct stable; }
33 boost::parameter::template_keyword<tag::stable, boost::mpl::bool_<T> >
36 namespace tag { struct mutable_; }
40 boost::parameter::template_keyword<tag::mutable_, boost::mpl::bool_<T> >
44 namespace tag { struct constant_time_size; }
47 struct constant_time_size:
48 boost::parameter::template_keyword<tag::constant_time_size, boost::mpl::bool_<T> >
51 namespace tag { struct store_parent_pointer; }
54 struct store_parent_pointer:
55 boost::parameter::template_keyword<tag::store_parent_pointer, boost::mpl::bool_<T> >
58 namespace tag { struct arity; }
60 template <unsigned int T>
62 boost::parameter::template_keyword<tag::arity, boost::mpl::int_<T> >
65 namespace tag { struct objects_per_page; }
67 template <unsigned int T>
68 struct objects_per_page:
69 boost::parameter::template_keyword<tag::objects_per_page, boost::mpl::int_<T> >
72 BOOST_PARAMETER_TEMPLATE_KEYWORD(stability_counter_type)
76 namespace mpl = boost::mpl;
78 template <typename bound_args, typename tag_type>
81 typedef typename boost::parameter::binding<bound_args, tag_type, mpl::void_>::type type;
82 static const bool value = mpl::is_not_void_<type>::type::value;
85 template <typename bound_args>
88 static const bool has_stable = has_arg<bound_args, tag::stable>::value;
90 typedef typename mpl::if_c<has_stable,
91 typename has_arg<bound_args, tag::stable>::type,
95 static const bool value = stable_t::value;
98 template <typename bound_args>
99 struct extract_mutable
101 static const bool has_mutable = has_arg<bound_args, tag::mutable_>::value;
103 typedef typename mpl::if_c<has_mutable,
104 typename has_arg<bound_args, tag::mutable_>::type,
108 static const bool value = mutable_t::value;
115 /** \brief Specifies the predicate for the heap order
117 template <typename T>
120 /** \brief Configure heap as mutable
122 * Certain heaps need to be configured specifically do be mutable.
128 /** \brief Specifies allocator for the internal memory management
130 template <typename T>
133 /** \brief Configure a heap as \b stable
135 * A priority queue is stable, if elements with the same priority are popped from the heap, in the same order as
141 /** \brief Specifies the type for stability counter
144 template <typename IntType>
145 struct stability_counter_type{};
147 /** \brief Configures complexity of <tt> size() </tt>
149 * Specifies, whether size() should have linear or constant complexity.
152 struct constant_time_size{};
154 /** \brief Store parent pointer in heap node.
156 * Maintaining a parent pointer adds some maintenance and size overhead, but iterating a heap is more efficient.
159 struct store_parent_pointer{};
161 /** \brief Specify arity.
163 * Specifies the arity of a D-ary heap
165 template <unsigned int T>
169 } /* namespace heap */
170 } /* namespace boost */
172 #endif /* BOOST_HEAP_POLICIES_HPP */