libstdc++/stl/heap.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Hewlett-Packard Company makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  */
  15
  16 #ifndef __SGI_STL_HEAP_H
  17 #define __SGI_STL_HEAP_H
  18
  19 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  20 #pragma set woff 1209
  21 #endif
  22
  23 template <class RandomAccessIterator, class Distance, class T>
  24 void __push_heap(RandomAccessIterator first, Distance holeIndex,
  25                  Distance topIndex, T value) {
  26     Distance parent = (holeIndex - 1) / 2;
  27     while (holeIndex > topIndex && *(first + parent) < value) {
  28         *(first + holeIndex) = *(first + parent);
  29         holeIndex = parent;
  30         parent = (holeIndex - 1) / 2;
  31     }
  32     *(first + holeIndex) = value;
  33 }
  34
  35 template <class RandomAccessIterator, class Distance, class T>
  36 inline void __push_heap_aux(RandomAccessIterator first,
  37                             RandomAccessIterator last, Distance*, T*) {
  38     __push_heap(first, Distance((last - first) - 1), Distance(0),
  39                 T(*(last - 1)));
  40 }
  41
  42 template <class RandomAccessIterator>
  43 inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
  44     __push_heap_aux(first, last, distance_type(first), value_type(first));
  45 }
  46
  47 template <class RandomAccessIterator, class Distance, class T, class Compare>
  48 void __push_heap(RandomAccessIterator first, Distance holeIndex,
  49                  Distance topIndex, T value, Compare comp) {
  50     Distance parent = (holeIndex - 1) / 2;
  51     while (holeIndex > topIndex && comp(*(first + parent), value)) {
  52         *(first + holeIndex) = *(first + parent);
  53         holeIndex = parent;
  54         parent = (holeIndex - 1) / 2;
  55     }
  56     *(first + holeIndex) = value;
  57 }
  58
  59 template <class RandomAccessIterator, class Compare, class Distance, class T>
  60 inline void __push_heap_aux(RandomAccessIterator first,
  61                             RandomAccessIterator last, Compare comp,
  62                             Distance*, T*) {
  63     __push_heap(first, Distance((last - first) - 1), Distance(0),
  64                 T(*(last - 1)), comp);
  65 }
  66
  67 template <class RandomAccessIterator, class Compare>
  68 inline void push_heap(RandomAccessIterator first, RandomAccessIterator last,
  69                       Compare comp) {
  70     __push_heap_aux(first, last, comp, distance_type(first), value_type(first));
  71 }
  72
  73 template <class RandomAccessIterator, class Distance, class T>
  74 void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
  75                    Distance len, T value) {
  76     Distance topIndex = holeIndex;
  77     Distance secondChild = 2 * holeIndex + 2;
  78     while (secondChild < len) {
  79         if (*(first + secondChild) < *(first + (secondChild - 1)))
  80             secondChild--;
  81         *(first + holeIndex) = *(first + secondChild);
  82         holeIndex = secondChild;
  83         secondChild = 2 * (secondChild + 1);
  84     }
  85     if (secondChild == len) {
  86         *(first + holeIndex) = *(first + (secondChild - 1));
  87         holeIndex = secondChild - 1;
  88     }
  89     __push_heap(first, holeIndex, topIndex, value);
  90 }
  91
  92 template <class RandomAccessIterator, class T, class Distance>
  93 inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
  94                        RandomAccessIterator result, T value, Distance*) {
  95     *result = *first;
  96     __adjust_heap(first, Distance(0), Distance(last - first), value);
  97 }
  98
  99 template <class RandomAccessIterator, class T>
 100 inline void __pop_heap_aux(RandomAccessIterator first,
 101                            RandomAccessIterator last, T*) {
 102     __pop_heap(first, last - 1, last - 1, T(*(last - 1)), distance_type(first));
 103 }
 104
 105 template <class RandomAccessIterator>
 106 inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
 107     __pop_heap_aux(first, last, value_type(first));
 108 }
 109
 110 template <class RandomAccessIterator, class Distance, class T, class Compare>
 111 void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
 112                    Distance len, T value, Compare comp) {
 113     Distance topIndex = holeIndex;
 114     Distance secondChild = 2 * holeIndex + 2;
 115     while (secondChild < len) {
 116         if (comp(*(first + secondChild), *(first + (secondChild - 1))))
 117             secondChild--;
 118         *(first + holeIndex) = *(first + secondChild);
 119         holeIndex = secondChild;
 120         secondChild = 2 * (secondChild + 1);
 121     }
 122     if (secondChild == len) {
 123         *(first + holeIndex) = *(first + (secondChild - 1));
 124         holeIndex = secondChild - 1;
 125     }
 126     __push_heap(first, holeIndex, topIndex, value, comp);
 127 }
 128
 129 template <class RandomAccessIterator, class T, class Compare, class Distance>
 130 inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
 131                        RandomAccessIterator result, T value, Compare comp,
 132                        Distance*) {
 133     *result = *first;
 134     __adjust_heap(first, Distance(0), Distance(last - first), value, comp);
 135 }
 136
 137 template <class RandomAccessIterator, class T, class Compare>
 138 inline void __pop_heap_aux(RandomAccessIterator first,
 139                            RandomAccessIterator last, T*, Compare comp) {
 140     __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,
 141                distance_type(first));
 142 }
 143
 144 template <class RandomAccessIterator, class Compare>
 145 inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
 146                      Compare comp) {
 147     __pop_heap_aux(first, last, value_type(first), comp);
 148 }
 149
 150 template <class RandomAccessIterator, class T, class Distance>
 151 void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
 152                  Distance*) {
 153     if (last - first < 2) return;
 154     Distance len = last - first;
 155     Distance parent = (len - 2)/2;
 156
 157     while (true) {
 158         __adjust_heap(first, parent, len, T(*(first + parent)));
 159         if (parent == 0) return;
 160         parent--;
 161     }
 162 }
 163
 164 template <class RandomAccessIterator>
 165 inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
 166     __make_heap(first, last, value_type(first), distance_type(first));
 167 }
 168
 169 template <class RandomAccessIterator, class Compare, class T, class Distance>
 170 void __make_heap(RandomAccessIterator first, RandomAccessIterator last,
 171                  Compare comp, T*, Distance*) {
 172     if (last - first < 2) return;
 173     Distance len = last - first;
 174     Distance parent = (len - 2)/2;
 175
 176     while (true) {
 177         __adjust_heap(first, parent, len, T(*(first + parent)), comp);
 178         if (parent == 0) return;
 179         parent--;
 180     }
 181 }
 182
 183 template <class RandomAccessIterator, class Compare>
 184 inline void make_heap(RandomAccessIterator first, RandomAccessIterator last,
 185                       Compare comp) {
 186     __make_heap(first, last, comp, value_type(first), distance_type(first));
 187 }
 188
 189 template <class RandomAccessIterator>
 190 void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
 191     while (last - first > 1) pop_heap(first, last--);
 192 }
 193
 194 template <class RandomAccessIterator, class Compare>
 195 void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
 196                Compare comp) {
 197     while (last - first > 1) pop_heap(first, last--, comp);
 198 }
 199
 200 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
 201 #pragma reset woff 1209
 202 #endif
 203
 204 #endif /* __SGI_STL_HEAP_H */