boost/heap/policies.hpp

0001 // boost heap
0002 //
0003 // Copyright (C) 2010-2011 Tim Blechmann
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_HEAP_POLICIES_HPP
0010 #define BOOST_HEAP_POLICIES_HPP
0011
0012 #include <boost/concept_check.hpp>
0013 #include <boost/parameter/aux_/void.hpp>
0014 #include <boost/parameter/binding.hpp>
0015 #include <boost/parameter/name.hpp>
0016 #include <boost/parameter/parameters.hpp>
0017 #include <boost/parameter/template_keyword.hpp>
0018
0019 #include <type_traits>
0020
0021 #ifdef BOOST_HAS_PRAGMA_ONCE
0022 #    pragma once
0023 #endif
0024
0025 namespace boost { namespace heap {
0026
0027 #ifndef BOOST_DOXYGEN_INVOKED
0028 BOOST_PARAMETER_TEMPLATE_KEYWORD( allocator )
0029 BOOST_PARAMETER_TEMPLATE_KEYWORD( compare )
0030
0031 namespace tag {
0032 struct stable;
0033 } // namespace tag
0034
0035 template < bool T >
0036 struct stable : boost::parameter::template_keyword< tag::stable, std::integral_constant< bool, T > >
0037 {};
0038
0039 namespace tag {
0040 struct mutable_;
0041 } // namespace tag
0042
0043 template < bool T >
0044 struct mutable_ : boost::parameter::template_keyword< tag::mutable_, std::integral_constant< bool, T > >
0045 {};
0046
0047
0048 namespace tag {
0049 struct constant_time_size;
0050 } // namespace tag
0051
0052 template < bool T >
0053 struct constant_time_size :
0054     boost::parameter::template_keyword< tag::constant_time_size, std::integral_constant< bool, T > >
0055 {};
0056
0057 namespace tag {
0058 struct store_parent_pointer;
0059 } // namespace tag
0060
0061 template < bool T >
0062 struct store_parent_pointer :
0063     boost::parameter::template_keyword< tag::store_parent_pointer, std::integral_constant< bool, T > >
0064 {};
0065
0066 namespace tag {
0067 struct arity;
0068 } // namespace tag
0069
0070 template < unsigned int T >
0071 struct arity : boost::parameter::template_keyword< tag::arity, std::integral_constant< int, T > >
0072 {};
0073
0074 namespace tag {
0075 struct objects_per_page;
0076 } // namespace tag
0077
0078 template < unsigned int T >
0079 struct objects_per_page : boost::parameter::template_keyword< tag::objects_per_page, std::integral_constant< int, T > >
0080 {};
0081
0082 BOOST_PARAMETER_TEMPLATE_KEYWORD( stability_counter_type )
0083
0084 namespace detail {
0085
0086 template < typename bound_args, typename tag_type >
0087 struct has_arg
0088 {
0089     typedef typename boost::parameter::binding< bound_args, tag_type, void >::type type;
0090     static const bool                                                              value = !std::is_void< type >::value;
0091 };
0092
0093 template < typename bound_args >
0094 struct extract_stable
0095 {
0096     static const bool has_stable = has_arg< bound_args, tag::stable >::value;
0097
0098     typedef
0099         typename std::conditional< has_stable, typename has_arg< bound_args, tag::stable >::type, std::false_type >::type
0100             stable_t;
0101
0102     static const bool value = stable_t::value;
0103 };
0104
0105 template < typename bound_args >
0106 struct extract_mutable
0107 {
0108     static const bool has_mutable = has_arg< bound_args, tag::mutable_ >::value;
0109
0110     typedef
0111         typename std::conditional< has_mutable, typename has_arg< bound_args, tag::mutable_ >::type, std::false_type >::type
0112             mutable_t;
0113
0114     static const bool value = mutable_t::value;
0115 };
0116
0117 } // namespace detail
0118
0119 #else
0120
0121 /** \brief Specifies the predicate for the heap order
0122  */
0123 template < typename T >
0124 struct compare
0125 {};
0126
0127 /** \brief Configure heap as mutable
0128  *
0129  *  Certain heaps need to be configured specifically do be mutable.
0130  *
0131  * */
0132 template < bool T >
0133 struct mutable_
0134 {};
0135
0136 /** \brief Specifies allocator for the internal memory management
0137  */
0138 template < typename T >
0139 struct allocator
0140 {};
0141
0142 /** \brief Configure a heap as \b stable
0143  *
0144  * A priority queue is stable, if elements with the same priority are popped from the heap, in the same order as
0145  * they are inserted.
0146  * */
0147 template < bool T >
0148 struct stable
0149 {};
0150
0151 /** \brief Specifies the type for stability counter
0152  *
0153  * */
0154 template < typename IntType >
0155 struct stability_counter_type
0156 {};
0157
0158 /** \brief Configures complexity of <tt> size() </tt>
0159  *
0160  * Specifies, whether size() should have linear or constant complexity.
0161  * */
0162 template < bool T >
0163 struct constant_time_size
0164 {};
0165
0166 /** \brief Store parent pointer in heap node.
0167  *
0168  * Maintaining a parent pointer adds some maintenance and size overhead, but iterating a heap is more efficient.
0169  * */
0170 template < bool T >
0171 struct store_parent_pointer
0172 {};
0173
0174 /** \brief Specify arity.
0175  *
0176  * Specifies the arity of a D-ary heap
0177  * */
0178 template < unsigned int T >
0179 struct arity
0180 {};
0181 #endif
0182
0183 }}     // namespace boost::heap
0184
0185 #endif /* BOOST_HEAP_POLICIES_HPP */