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
26namespace boost {
27namespace heap {
28
29#ifndef BOOST_DOXYGEN_INVOKED
30BOOST_PARAMETER_TEMPLATE_KEYWORD(allocator)
31BOOST_PARAMETER_TEMPLATE_KEYWORD(compare)
32
33namespace tag { struct stable; }
34
35template <bool T>
36struct stable:
37 boost::parameter::template_keyword<tag::stable, boost::integral_constant<bool, T> >
38{};
39
40namespace tag { struct mutable_; }
41
42template <bool T>
43struct mutable_:
44 boost::parameter::template_keyword<tag::mutable_, boost::integral_constant<bool, T> >
45{};
46
47
48namespace tag { struct constant_time_size; }
49
50template <bool T>
51struct constant_time_size:
52 boost::parameter::template_keyword<tag::constant_time_size, boost::integral_constant<bool, T> >
53{};
54
55namespace tag { struct store_parent_pointer; }
56
57template <bool T>
58struct store_parent_pointer:
59 boost::parameter::template_keyword<tag::store_parent_pointer, boost::integral_constant<bool, T> >
60{};
61
62namespace tag { struct arity; }
63
64template <unsigned int T>
65struct arity:
66 boost::parameter::template_keyword<tag::arity, boost::integral_constant<int, T> >
67{};
68
69namespace tag { struct objects_per_page; }
70
71template <unsigned int T>
72struct objects_per_page:
73 boost::parameter::template_keyword<tag::objects_per_page, boost::integral_constant<int, T> >
74{};
75
76BOOST_PARAMETER_TEMPLATE_KEYWORD(stability_counter_type)
77
78namespace detail {
79
80template <typename bound_args, typename tag_type>
81struct 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
87template <typename bound_args>
88struct 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
100template <typename bound_args>
101struct 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 */
119template <typename T>
120struct compare{};
121
122/** \brief Configure heap as mutable
123 *
124 * Certain heaps need to be configured specifically do be mutable.
125 *
126 * */
127template <bool T>
128struct mutable_{};
129
130/** \brief Specifies allocator for the internal memory management
131 */
132template <typename T>
133struct 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 * */
140template <bool T>
141struct stable{};
142
143/** \brief Specifies the type for stability counter
144 *
145 * */
146template <typename IntType>
147struct stability_counter_type{};
148
149/** \brief Configures complexity of <tt> size() </tt>
150 *
151 * Specifies, whether size() should have linear or constant complexity.
152 * */
153template <bool T>
154struct 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 * */
160template <bool T>
161struct store_parent_pointer{};
162
163/** \brief Specify arity.
164 *
165 * Specifies the arity of a D-ary heap
166 * */
167template <unsigned int T>
168struct arity{};
169#endif
170
171} /* namespace heap */
172} /* namespace boost */
173
174#endif /* BOOST_HEAP_POLICIES_HPP */
175

source code of boost/libs/heap/include/boost/heap/policies.hpp