uheap.h

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