1 // boost heap: concepts 2 // 3 // Copyright (C) 2010 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_CONCEPTS_HPP 10 #define BOOST_HEAP_CONCEPTS_HPP 11 12 #include <boost/concept_check.hpp> 13 14 namespace boost { 15 namespace heap { 16 17 18 template <class C> 19 struct PriorityQueue: 20 boost::ForwardContainer<C> 21 { 22 typedef typename C::iterator iterator; 23 typedef typename C::const_iterator const_iterator; 24 typedef typename C::allocator_type allocator_type; 25 typedef typename C::value_compare value_compare; 26 typedef typename C::value_type value_type; 27 typedef typename C::const_reference const_reference; 28 29 BOOST_CONCEPT_USAGEboost::heap::PriorityQueue30 BOOST_CONCEPT_USAGE(PriorityQueue) 31 { 32 BOOST_CONCEPT_ASSERT((boost::Assignable<value_type>)); 33 BOOST_CONCEPT_ASSERT((boost::Container<C>)); 34 BOOST_CONCEPT_ASSERT((boost::EqualityComparable<C>)); 35 BOOST_CONCEPT_ASSERT((boost::Comparable<C>)); 36 37 BOOST_CONCEPT_ASSERT((boost::Const_BinaryPredicate<value_compare, value_type, value_type>)); 38 39 c.swap(c2); 40 c.clear(); 41 a = c.get_allocator(); 42 43 typename PriorityQueue::value_type v; 44 c.push(v); 45 46 v = c.top(); 47 c.pop(); 48 49 cmp = c.value_comp(); 50 51 // verify tags 52 has_ordered_iterators = C::has_ordered_iterators; 53 is_mergable = C::is_mergable; 54 is_stable = C::is_stable; 55 } 56 57 private: 58 C c, c2; 59 allocator_type a; 60 typename C::value_type v; 61 value_compare cmp; 62 bool has_ordered_iterators, is_mergable, is_stable; 63 }; 64 65 template <class C> 66 struct MergablePriorityQueue: 67 PriorityQueue<C> 68 { BOOST_CONCEPT_USAGEboost::heap::MergablePriorityQueue69 BOOST_CONCEPT_USAGE(MergablePriorityQueue) 70 { 71 C c, c2; 72 c.merge(c2); 73 } 74 }; 75 76 77 template <class C> 78 struct MutablePriorityQueue: 79 PriorityQueue<C> 80 { 81 typedef typename C::handle_type handle_type; 82 BOOST_CONCEPT_USAGEboost::heap::MutablePriorityQueue83 BOOST_CONCEPT_USAGE(MutablePriorityQueue) 84 { 85 BOOST_CONCEPT_ASSERT((boost::Assignable<typename MutablePriorityQueue::handle_type>)); 86 87 typename MutablePriorityQueue::value_type v; 88 typename MutablePriorityQueue::handle_type h = c.push(v); 89 typename MutablePriorityQueue::handle_type h2 = c.push(v); 90 c.update(h, v); 91 c.increase(h, v); 92 c.decrease(h, v); 93 94 c.update(h); 95 c.increase(h); 96 c.decrease(h); 97 98 equal = (h == h2); 99 not_equal = (h != h2); 100 101 h2 = h; 102 } 103 104 C c; 105 bool equal, not_equal; 106 }; 107 108 }} 109 110 #endif /* BOOST_HEAP_CONCEPTS_HPP */ 111