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 |
89 | { |
90 | static const bool = 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 ; |
96 | |
97 | static const bool = stable_t::value; |
98 | }; |
99 | |
100 | template <typename bound_args> |
101 | struct |
102 | { |
103 | static const bool = 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 ; |
109 | |
110 | static const bool = 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 | |