Chris@16: // boost heap
Chris@16: //
Chris@16: // Copyright (C) 2010-2011 Tim Blechmann
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_HEAP_POLICIES_HPP
Chris@16: #define BOOST_HEAP_POLICIES_HPP
Chris@16: 
Chris@16: #include <boost/parameter.hpp>
Chris@16: #include <boost/mpl/bool.hpp>
Chris@16: #include <boost/mpl/int.hpp>
Chris@16: #include <boost/mpl/void.hpp>
Chris@16: #include <boost/concept_check.hpp>
Chris@16: 
Chris@101: #ifdef BOOST_HAS_PRAGMA_ONCE
Chris@101: #pragma once
Chris@101: #endif
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace heap {
Chris@16: 
Chris@16: #ifndef BOOST_DOXYGEN_INVOKED
Chris@16: BOOST_PARAMETER_TEMPLATE_KEYWORD(allocator)
Chris@16: BOOST_PARAMETER_TEMPLATE_KEYWORD(compare)
Chris@16: 
Chris@16: namespace tag { struct stable; }
Chris@16: 
Chris@16: template <bool T>
Chris@16: struct stable:
Chris@16:     boost::parameter::template_keyword<tag::stable, boost::mpl::bool_<T> >
Chris@16: {};
Chris@16: 
Chris@16: namespace tag { struct mutable_; }
Chris@16: 
Chris@16: template <bool T>
Chris@16: struct mutable_:
Chris@16:     boost::parameter::template_keyword<tag::mutable_, boost::mpl::bool_<T> >
Chris@16: {};
Chris@16: 
Chris@16: 
Chris@16: namespace tag { struct constant_time_size; }
Chris@16: 
Chris@16: template <bool T>
Chris@16: struct constant_time_size:
Chris@16:     boost::parameter::template_keyword<tag::constant_time_size, boost::mpl::bool_<T> >
Chris@16: {};
Chris@16: 
Chris@16: namespace tag { struct store_parent_pointer; }
Chris@16: 
Chris@16: template <bool T>
Chris@16: struct store_parent_pointer:
Chris@16:     boost::parameter::template_keyword<tag::store_parent_pointer, boost::mpl::bool_<T> >
Chris@16: {};
Chris@16: 
Chris@16: namespace tag { struct arity; }
Chris@16: 
Chris@16: template <unsigned int T>
Chris@16: struct arity:
Chris@16:     boost::parameter::template_keyword<tag::arity, boost::mpl::int_<T> >
Chris@16: {};
Chris@16: 
Chris@16: namespace tag { struct objects_per_page; }
Chris@16: 
Chris@16: template <unsigned int T>
Chris@16: struct objects_per_page:
Chris@16:     boost::parameter::template_keyword<tag::objects_per_page, boost::mpl::int_<T> >
Chris@16: {};
Chris@16: 
Chris@16: BOOST_PARAMETER_TEMPLATE_KEYWORD(stability_counter_type)
Chris@16: 
Chris@16: namespace detail {
Chris@16: 
Chris@16: namespace mpl = boost::mpl;
Chris@16: 
Chris@16: template <typename bound_args, typename tag_type>
Chris@16: struct has_arg
Chris@16: {
Chris@16:     typedef typename boost::parameter::binding<bound_args, tag_type, mpl::void_>::type type;
Chris@16:     static const bool value = mpl::is_not_void_<type>::type::value;
Chris@16: };
Chris@16: 
Chris@16: template <typename bound_args>
Chris@16: struct extract_stable
Chris@16: {
Chris@16:     static const bool has_stable = has_arg<bound_args, tag::stable>::value;
Chris@16: 
Chris@16:     typedef typename mpl::if_c<has_stable,
Chris@16:                                typename has_arg<bound_args, tag::stable>::type,
Chris@16:                                mpl::bool_<false>
Chris@16:                               >::type stable_t;
Chris@16: 
Chris@16:     static const bool value = stable_t::value;
Chris@16: };
Chris@16: 
Chris@16: template <typename bound_args>
Chris@16: struct extract_mutable
Chris@16: {
Chris@16:     static const bool has_mutable = has_arg<bound_args, tag::mutable_>::value;
Chris@16: 
Chris@16:     typedef typename mpl::if_c<has_mutable,
Chris@16:                                typename has_arg<bound_args, tag::mutable_>::type,
Chris@16:                                mpl::bool_<false>
Chris@16:                               >::type mutable_t;
Chris@16: 
Chris@16:     static const bool value = mutable_t::value;
Chris@16: };
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: #else
Chris@16: 
Chris@16: /** \brief Specifies the predicate for the heap order
Chris@16:  */
Chris@16: template <typename T>
Chris@16: struct compare{};
Chris@16: 
Chris@16: /** \brief Configure heap as mutable
Chris@16:  *
Chris@16:  *  Certain heaps need to be configured specifically do be mutable.
Chris@16:  *
Chris@16:  * */
Chris@16: template <bool T>
Chris@16: struct mutable_{};
Chris@16: 
Chris@16: /** \brief Specifies allocator for the internal memory management
Chris@16:  */
Chris@16: template <typename T>
Chris@16: struct allocator{};
Chris@16: 
Chris@16: /** \brief Configure a heap as \b stable
Chris@16:  *
Chris@16:  * A priority queue is stable, if elements with the same priority are popped from the heap, in the same order as
Chris@16:  * they are inserted.
Chris@16:  * */
Chris@16: template <bool T>
Chris@16: struct stable{};
Chris@16: 
Chris@16: /** \brief Specifies the type for stability counter
Chris@16:  *
Chris@16:  * */
Chris@16: template <typename IntType>
Chris@16: struct stability_counter_type{};
Chris@16: 
Chris@16: /** \brief Configures complexity of <tt> size() </tt>
Chris@16:  *
Chris@16:  * Specifies, whether size() should have linear or constant complexity.
Chris@16:  * */
Chris@16: template <bool T>
Chris@16: struct constant_time_size{};
Chris@16: 
Chris@16: /** \brief Store parent pointer in heap node.
Chris@16:  *
Chris@16:  * Maintaining a parent pointer adds some maintenance and size overhead, but iterating a heap is more efficient.
Chris@16:  * */
Chris@16: template <bool T>
Chris@16: struct store_parent_pointer{};
Chris@16: 
Chris@16: /** \brief Specify arity.
Chris@16:  *
Chris@16:  * Specifies the arity of a D-ary heap
Chris@16:  * */
Chris@16: template <unsigned int T>
Chris@16: struct arity{};
Chris@16: #endif
Chris@16: 
Chris@16: } /* namespace heap */
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif /* BOOST_HEAP_POLICIES_HPP */