• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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