uheap.h

// This file is part of the uSTL library, an STL implementation.
//
// Copyright (c) 2005 by Mike Sharov <msharov@users.sourceforge.net>
// This file is free software, distributed under the MIT License.

#pragma once
#include "ualgobase.h"

namespace ustl {

/// \brief Returns true if the given range is a heap under \p comp.
/// A heap is a sequentially encoded binary tree where for every node
/// comp(node,child1) is false and comp(node,child2) is false.
/// \ingroup HeapAlgorithms
/// \ingroup ConditionAlgorithms
///
template <typename RandomAccessIterator, typename Compare>
bool is_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    RandomAccessIterator iChild (first);
    for (; ++iChild < last; ++first)
	if (comp (*first, *iChild) || (++iChild < last && comp (*first, *iChild)))
	    return (false);
    return (true);
}

/// \brief make_heap turns the range [first, last) into a heap
/// At completion, is_heap (first, last, comp) is true.
/// The algorithm is adapted from "Classic Data Structures in C++" by Timothy Budd.
/// \ingroup HeapAlgorithms
/// \ingroup SortingAlgorithms
///
template <typename RandomAccessIterator, typename Compare>
void make_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
    const value_type v (*first);
    uoff_t iChild, iHole = 0, iEnd (distance (first, last));
    while ((iChild = 2 * iHole + 1) < iEnd) {
	if (iChild + 1 < iEnd)	// Pick the greater child
	    iChild += comp (first[iChild], first[iChild + 1]);
	if (comp (first[iChild], v))
	    break;		// Done when parent is greater than both children.
	first[iHole] = first[iChild];
	iHole = iChild;
    }
    if (iHole < iEnd)
	first[iHole] = v;
}

/// \brief Inserts the *--last into the preceeding range assumed to be a heap.
/// \ingroup HeapAlgorithms
/// \ingroup MutatingAlgorithms
template <typename RandomAccessIterator, typename Compare>
void push_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    if (last <= first)
	return;
    typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
    const value_type v (*--last);
    while (first < last) {
	RandomAccessIterator iParent = first + (distance(first, last) - 1) / 2;
	if (comp (v, *iParent))
	    break;
	*last = *iParent;
	last = iParent;
    }
    *last = v;
}

/// Removes the largest element from the heap (*first) and places it at *(last-1)
/// [first, last-1) is a heap after this operation.
/// \ingroup HeapAlgorithms
/// \ingroup MutatingAlgorithms
template <typename RandomAccessIterator, typename Compare>
void pop_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    if (--last <= first)
	return;
    iter_swap (first, last);
    make_heap (first, last, comp);
}

/// Sorts heap [first, last) in descending order according to comp.
/// \ingroup HeapAlgorithms
/// \ingroup SortingAlgorithms
template <typename RandomAccessIterator, typename Compare>
void sort_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    for (; first < last; --last)
	pop_heap (first, last, comp);
}

#define HEAP_FN_WITH_LESS(rtype, name)	\
template <typename RandomAccessIterator>\
inline rtype name (RandomAccessIterator first, RandomAccessIterator last)		\
{											\
    typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;	\
    return (name (first, last, less<value_type>()));					\
}
HEAP_FN_WITH_LESS (bool, is_heap)
HEAP_FN_WITH_LESS (void, make_heap)
HEAP_FN_WITH_LESS (void, push_heap)
HEAP_FN_WITH_LESS (void, pop_heap)
HEAP_FN_WITH_LESS (void, sort_heap)
#undef HEAP_FN_WITH_LESS

/// \class priority_queue uheap.h ustl.h
/// \ingroup Sequences
///
/// \brief Sorted queue adapter to uSTL containers.
///
/// Acts just like the queue adapter, but keeps the elements sorted by priority
/// specified by the given comparison operator.
///
template <typename T, typename Ctr = vector<T>, typename Comp = less<typename Ctr::value_type> >
class priority_queue {
public:
    typedef Ctr					base_ctr;
    typedef typename base_ctr::value_type	value_type;
    typedef typename base_ctr::size_type	size_type;
    typedef typename base_ctr::const_pointer	const_pointer;
    typedef typename base_ctr::const_reference	reference;
public:
			priority_queue (const Comp& c = Comp()) : m_v(), m_c (c) {}
			priority_queue (const_pointer f, const_pointer l, const Comp& c = Comp())
			    : m_v (f, l), m_c (c) { make_heap (m_v.begin(), m_v.end(), m_c); }
    inline size_type	size (void) const	{ return (m_v.size()); }
    inline bool		empty (void) const	{ return (m_v.empty()); }
    inline reference	top (void) const	{ return (m_v.at(0)); }
    inline void		push (reference v)	{ m_v.push_back (v); make_heap (m_v.begin(), m_v.end(), m_c); }
    inline void		pop (void)		{ pop_heap (m_v.begin(), m_v.end()); m_v.pop_back(); }
private:
    base_ctr		m_v;	///< Element container.
    Comp		m_c;	///< Comparison functor by value.
};

} // namespace ustl