Chris@16: // boost heap: heap merge algorithms
Chris@16: //
Chris@16: // Copyright (C) 2011 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_MERGE_HPP
Chris@16: #define BOOST_HEAP_MERGE_HPP
Chris@16: 
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: #include <boost/heap/heap_concepts.hpp>
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: 
Chris@101: #ifdef BOOST_HAS_PRAGMA_ONCE
Chris@101: #pragma once
Chris@101: #endif
Chris@101: 
Chris@101: 
Chris@16: namespace boost  {
Chris@16: namespace heap   {
Chris@16: namespace detail {
Chris@16: 
Chris@16: template <typename Heap1, typename Heap2>
Chris@16: struct heap_merge_emulate
Chris@16: {
Chris@16:     struct dummy_reserver
Chris@16:     {
Chris@16:         static void reserve (Heap1 & lhs, std::size_t required_size)
Chris@16:         {}
Chris@16:     };
Chris@16: 
Chris@16:     struct reserver
Chris@16:     {
Chris@16:         static void reserve (Heap1 & lhs, std::size_t required_size)
Chris@16:         {
Chris@16:             lhs.reserve(required_size);
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     typedef typename boost::mpl::if_c<Heap1::has_reserve,
Chris@16:                                       reserver,
Chris@16:                                       dummy_reserver>::type space_reserver;
Chris@16: 
Chris@16:     static void merge(Heap1 & lhs, Heap2 & rhs)
Chris@16:     {
Chris@16:         if (Heap1::constant_time_size && Heap2::constant_time_size) {
Chris@16:             if (Heap1::has_reserve) {
Chris@16:                 std::size_t required_size = lhs.size() + rhs.size();
Chris@16:                 space_reserver::reserve(lhs, required_size);
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         // FIXME: container adaptors could benefit from first appending all elements and then restoring the heap order
Chris@16:         // FIXME: optimize: if we have ordered iterators and we can efficiently insert keys with a below the lowest key in the heap
Chris@16:         //                  d-ary, b and fibonacci heaps fall into this category
Chris@16: 
Chris@16:         while (!rhs.empty()) {
Chris@16:             lhs.push(rhs.top());
Chris@16:             rhs.pop();
Chris@16:         }
Chris@16: 
Chris@16:         lhs.set_stability_count((std::max)(lhs.get_stability_count(),
Chris@16:                                            rhs.get_stability_count()));
Chris@16:         rhs.set_stability_count(0);
Chris@16:     }
Chris@16: 
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename Heap>
Chris@16: struct heap_merge_same_mergable
Chris@16: {
Chris@16:     static void merge(Heap & lhs, Heap & rhs)
Chris@16:     {
Chris@16:         lhs.merge(rhs);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename Heap>
Chris@16: struct heap_merge_same
Chris@16: {
Chris@16:     static const bool is_mergable = Heap::is_mergable;
Chris@16:     typedef typename boost::mpl::if_c<is_mergable,
Chris@16:                                       heap_merge_same_mergable<Heap>,
Chris@16:                                       heap_merge_emulate<Heap, Heap>
Chris@16:                                      >::type heap_merger;
Chris@16: 
Chris@16:     static void merge(Heap & lhs, Heap & rhs)
Chris@16:     {
Chris@16:         heap_merger::merge(lhs, rhs);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: } /* namespace detail */
Chris@16: 
Chris@16: 
Chris@16: /** merge rhs into lhs
Chris@16:  *
Chris@16:  *  \b Effect: lhs contains all elements that have been part of rhs, rhs is empty.
Chris@16:  *
Chris@16:  * */
Chris@16: template <typename Heap1,
Chris@16:           typename Heap2
Chris@16:          >
Chris@16: void heap_merge(Heap1 & lhs, Heap2 & rhs)
Chris@16: {
Chris@16:     BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap1>));
Chris@16:     BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<Heap2>));
Chris@16: 
Chris@16:     // if this assertion is triggered, the value_compare types are incompatible
Chris@16:     BOOST_STATIC_ASSERT((boost::is_same<typename Heap1::value_compare, typename Heap2::value_compare>::value));
Chris@16: 
Chris@16:     const bool same_heaps = boost::is_same<Heap1, Heap2>::value;
Chris@16: 
Chris@16:     typedef typename boost::mpl::if_c<same_heaps,
Chris@16:                                       detail::heap_merge_same<Heap1>,
Chris@16:                                       detail::heap_merge_emulate<Heap1, Heap2>
Chris@16:                                      >::type heap_merger;
Chris@16: 
Chris@16:     heap_merger::merge(lhs, rhs);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: } /* namespace heap */
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif /* BOOST_HEAP_MERGE_HPP */