ceph/src/boost/boost/heap/heap_concepts.hpp

   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
  30     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 {
  69     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
  83     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 */