Chris@16: // boost heap: concepts
Chris@16: //
Chris@16: // Copyright (C) 2010 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_CONCEPTS_HPP
Chris@16: #define BOOST_HEAP_CONCEPTS_HPP
Chris@16: 
Chris@16: #include <boost/concept_check.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace heap  {
Chris@16: 
Chris@16: 
Chris@16: template <class C>
Chris@16: struct PriorityQueue:
Chris@16:     boost::ForwardContainer<C>
Chris@16: {
Chris@16:     typedef typename C::iterator iterator;
Chris@16:     typedef typename C::const_iterator const_iterator;
Chris@16:     typedef typename C::allocator_type allocator_type;
Chris@16:     typedef typename C::value_compare value_compare;
Chris@16:     typedef typename C::value_type value_type;
Chris@16:     typedef typename C::const_reference const_reference;
Chris@16: 
Chris@16: 
Chris@16:     BOOST_CONCEPT_USAGE(PriorityQueue)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT((boost::Assignable<value_type>));
Chris@16:         BOOST_CONCEPT_ASSERT((boost::Container<C>));
Chris@16:         BOOST_CONCEPT_ASSERT((boost::EqualityComparable<C>));
Chris@16:         BOOST_CONCEPT_ASSERT((boost::Comparable<C>));
Chris@16: 
Chris@16:         BOOST_CONCEPT_ASSERT((boost::Const_BinaryPredicate<value_compare, value_type, value_type>));
Chris@16: 
Chris@16:         c.swap(c2);
Chris@16:         c.clear();
Chris@16:         a = c.get_allocator();
Chris@16: 
Chris@16:         typename PriorityQueue::value_type v;
Chris@16:         c.push(v);
Chris@16: 
Chris@16:         v = c.top();
Chris@16:         c.pop();
Chris@16: 
Chris@16:         cmp = c.value_comp();
Chris@16: 
Chris@16:         // verify tags
Chris@16:         has_ordered_iterators = C::has_ordered_iterators;
Chris@16:         is_mergable = C::is_mergable;
Chris@16:         is_stable   = C::is_stable;
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     C c, c2;
Chris@16:     allocator_type a;
Chris@16:     typename C::value_type v;
Chris@16:     value_compare cmp;
Chris@16:     bool has_ordered_iterators, is_mergable, is_stable;
Chris@16: };
Chris@16: 
Chris@16: template <class C>
Chris@16: struct MergablePriorityQueue:
Chris@16:     PriorityQueue<C>
Chris@16: {
Chris@16:     BOOST_CONCEPT_USAGE(MergablePriorityQueue)
Chris@16:     {
Chris@16:         C c, c2;
Chris@16:         c.merge(c2);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <class C>
Chris@16: struct MutablePriorityQueue:
Chris@16:     PriorityQueue<C>
Chris@16: {
Chris@16:     typedef typename C::handle_type handle_type;
Chris@16: 
Chris@16:     BOOST_CONCEPT_USAGE(MutablePriorityQueue)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT((boost::Assignable<typename MutablePriorityQueue::handle_type>));
Chris@16: 
Chris@16:         typename MutablePriorityQueue::value_type v;
Chris@16:         typename MutablePriorityQueue::handle_type h  = c.push(v);
Chris@16:         typename MutablePriorityQueue::handle_type h2 = c.push(v);
Chris@16:         c.update(h, v);
Chris@16:         c.increase(h, v);
Chris@16:         c.decrease(h, v);
Chris@16: 
Chris@16:         c.update(h);
Chris@16:         c.increase(h);
Chris@16:         c.decrease(h);
Chris@16: 
Chris@16:         equal = (h == h2);
Chris@16:         not_equal = (h != h2);
Chris@16: 
Chris@16:         h2 = h;
Chris@16:     }
Chris@16: 
Chris@16:     C c;
Chris@16:     bool equal, not_equal;
Chris@16: };
Chris@16: 
Chris@16: }}
Chris@16: 
Chris@16: #endif /* BOOST_HEAP_CONCEPTS_HPP */