boost/heap/heap_concepts.hpp

0001 // boost heap: concepts
0002 //
0003 // Copyright (C) 2010 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_CONCEPTS_HPP
0010 #define BOOST_HEAP_CONCEPTS_HPP
0011
0012 #include <boost/concept_check.hpp>
0013
0014 namespace boost { namespace heap {
0015
0016
0017 template < class C >
0018 struct PriorityQueue : boost::ForwardContainer< C >
0019 {
0020     typedef typename C::iterator        iterator;
0021     typedef typename C::const_iterator  const_iterator;
0022     typedef typename C::allocator_type  allocator_type;
0023     typedef typename C::value_compare   value_compare;
0024     typedef typename C::value_type      value_type;
0025     typedef typename C::const_reference const_reference;
0026
0027
0028     BOOST_CONCEPT_USAGE( PriorityQueue )
0029     {
0030         BOOST_CONCEPT_ASSERT( (boost::Assignable< value_type >));
0031         BOOST_CONCEPT_ASSERT( (boost::Container< C >));
0032         BOOST_CONCEPT_ASSERT( (boost::EqualityComparable< C >));
0033         BOOST_CONCEPT_ASSERT( (boost::Comparable< C >));
0034
0035         BOOST_CONCEPT_ASSERT( (boost::Const_BinaryPredicate< value_compare, value_type, value_type >));
0036
0037         c.swap( c2 );
0038         c.clear();
0039         a = c.get_allocator();
0040
0041         typename PriorityQueue::value_type v;
0042         c.push( v );
0043
0044         v = c.top();
0045         c.pop();
0046
0047         cmp = c.value_comp();
0048
0049         // verify tags
0050         has_ordered_iterators = C::has_ordered_iterators;
0051         is_mergable           = C::is_mergable;
0052         is_stable             = C::is_stable;
0053     }
0054
0055 private:
0056     C                      c, c2;
0057     allocator_type         a;
0058     typename C::value_type v;
0059     value_compare          cmp;
0060     bool                   has_ordered_iterators, is_mergable, is_stable;
0061 };
0062
0063 template < class C >
0064 struct MergablePriorityQueue : PriorityQueue< C >
0065 {
0066     BOOST_CONCEPT_USAGE( MergablePriorityQueue )
0067     {
0068         C c, c2;
0069         c.merge( c2 );
0070     }
0071 };
0072
0073
0074 template < class C >
0075 struct MutablePriorityQueue : PriorityQueue< C >
0076 {
0077     typedef typename C::handle_type handle_type;
0078
0079     BOOST_CONCEPT_USAGE( MutablePriorityQueue )
0080     {
0081         BOOST_CONCEPT_ASSERT( (boost::Assignable< typename MutablePriorityQueue::handle_type >));
0082
0083         typename MutablePriorityQueue::value_type  v;
0084         typename MutablePriorityQueue::handle_type h  = c.push( v );
0085         typename MutablePriorityQueue::handle_type h2 = c.push( v );
0086         c.update( h, v );
0087         c.increase( h, v );
0088         c.decrease( h, v );
0089
0090         c.update( h );
0091         c.increase( h );
0092         c.decrease( h );
0093
0094         equal     = ( h == h2 );
0095         not_equal = ( h != h2 );
0096
0097         h2 = h;
0098     }
0099
0100     C    c;
0101     bool equal, not_equal;
0102 };
0103
0104 }}     // namespace boost::heap
0105
0106 #endif /* BOOST_HEAP_CONCEPTS_HPP */