uheap.h revision 9066cfe9886ac131c34d59ed0e2d287b0e3c0087 
1// This file is part of the ustl library, an STL implementation.
2//
3// Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
4// This file is free software, distributed under the MIT License.
5//
6// uheap.h
7//
8// Implementation of STL heap algorithms.
9//
10// The function prototypes are copied
11// exactly from the SGI version of STL documentation along with comments about
12// their use. The code is NOT the same, though the functionality is.
13//
14
15#ifndef UHEAP_H_574B9EAF271A1C107190B4D575A356C5
16#define UHEAP_H_574B9EAF271A1C107190B4D575A356C5
17
18#include "uvector.h"
19#include "ualgobase.h"
20
21namespace ustl {
22
23/// \brief Returns true if the given range is a heap under \p comp.
24/// A heap is a sequentially encoded binary tree where for every node
25/// comp(node,child1) is false and comp(node,child2) is false.
26/// \ingroup HeapAlgorithms
27/// \ingroup ConditionAlgorithms
28///
29template <typename RandomAccessIterator, typename Compare>
30bool is_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
31{
32    RandomAccessIterator iChild (first);
33    for (; ++iChild < last; ++first)
34	if (comp (*first, *iChild) || (++iChild < last && comp (*first, *iChild)))
35	    return (false);
36    return (true);
37}
38
39/// \brief make_heap turns the range [first, last) into a heap
40/// At completion, is_heap (first, last, comp) is true.
41/// The algorithm is adapted from "Classic Data Structures in C++" by Timothy Budd.
42/// \ingroup HeapAlgorithms
43/// \ingroup SortingAlgorithms
44///
45template <typename RandomAccessIterator, typename Compare>
46void make_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
47{
48    typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
49    const value_type v (*first);
50    uoff_t iChild, iHole = 0, iEnd (distance (first, last));
51    while ((iChild = 2 * iHole + 1) < iEnd) {
52	if (iChild + 1 < iEnd)	// Pick the greater child
53	    iChild += comp (first[iChild], first[iChild + 1]);
54	if (comp (first[iChild], v))
55	    break;		// Done when parent is greater than both children.
56	first[iHole] = first[iChild];
57	iHole = iChild;
58    }
59    if (iHole < iEnd)
60	first[iHole] = v;
61}
62
63/// \brief Inserts the *--last into the preceeding range assumed to be a heap.
64/// \ingroup HeapAlgorithms
65/// \ingroup MutatingAlgorithms
66template <typename RandomAccessIterator, typename Compare>
67void push_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
68{
69    if (last <= first)
70	return;
71    typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
72    const value_type v (*--last);
73    while (first < last) {
74	RandomAccessIterator iParent = first + (distance(first, last) - 1) / 2;
75	if (comp (v, *iParent))
76	    break;
77	*last = *iParent;
78	last = iParent;
79    }
80    *last = v;
81}
82
83/// Removes the largest element from the heap (*first) and places it at *(last-1)
84/// [first, last-1) is a heap after this operation.
85/// \ingroup HeapAlgorithms
86/// \ingroup MutatingAlgorithms
87template <typename RandomAccessIterator, typename Compare>
88void pop_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
89{
90    if (--last <= first)
91	return;
92    iter_swap (first, last);
93    make_heap (first, last, comp);
94}
95
96/// Sorts heap [first, last) in descending order according to comp.
97/// \ingroup HeapAlgorithms
98/// \ingroup SortingAlgorithms
99template <typename RandomAccessIterator, typename Compare>
100void sort_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
101{
102    for (; first < last; --last)
103	pop_heap (first, last, comp);
104}
105
106#define HEAP_FN_WITH_LESS(rtype, name)	\
107template <typename RandomAccessIterator>\
108inline rtype name (RandomAccessIterator first, RandomAccessIterator last)		\
109{											\
110    typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;	\
111    return (name (first, last, less<value_type>()));					\
112}
113HEAP_FN_WITH_LESS (bool, is_heap)
114HEAP_FN_WITH_LESS (void, make_heap)
115HEAP_FN_WITH_LESS (void, push_heap)
116HEAP_FN_WITH_LESS (void, pop_heap)
117HEAP_FN_WITH_LESS (void, sort_heap)
118#undef HEAP_FN_WITH_LESS
119
120/// \class priority_queue uheap.h ustl.h
121/// \ingroup Sequences
122///
123/// \brief Sorted queue adapter to uSTL containers.
124///
125/// Acts just like the queue adapter, but keeps the elements sorted by priority
126/// specified by the given comparison operator.
127///
128template <typename T, typename Ctr = vector<T>, typename Comp = less<typename Ctr::value_type> >
129class priority_queue {
130public:
131    typedef Ctr					base_ctr;
132    typedef typename base_ctr::value_type	value_type;
133    typedef typename base_ctr::size_type	size_type;
134    typedef typename base_ctr::const_pointer	const_pointer;
135    typedef typename base_ctr::const_reference	reference;
136public:
137			priority_queue (const Comp& c = Comp()) : m_v(), m_c (c) {}
138			priority_queue (const_pointer f, const_pointer l, const Comp& c = Comp())
139			    : m_v (f, l), m_c (c) { make_heap (m_v.begin(), m_v.end(), m_c); }
140    inline size_type	size (void) const	{ return (m_v.size()); }
141    inline bool		empty (void) const	{ return (m_v.empty()); }
142    inline reference	top (void) const	{ return (m_v.at(0)); }
143    inline void		push (reference v)	{ m_v.push_back (v); make_heap (m_v.begin(), m_v.end(), m_c); }
144    inline void		pop (void)		{ pop_heap (m_v.begin(), m_v.end()); m_v.pop_back(); }
145private:
146    base_ctr		m_v;	///< Element container.
147    Comp		m_c;	///< Comparison functor by value.
148};
149
150} // namespace ustl
151
152#endif
153
154