libstdc++-v3/include/bits/stl_heap.h

   1 // Heap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  *
  32  * Copyright (c) 1994
  33  * Hewlett-Packard Company
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Hewlett-Packard Company makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  * Copyright (c) 1997
  44  * Silicon Graphics Computer Systems, Inc.
  45  *
  46  * Permission to use, copy, modify, distribute and sell this software
  47  * and its documentation for any purpose is hereby granted without fee,
  48  * provided that the above copyright notice appear in all copies and
  49  * that both that copyright notice and this permission notice appear
  50  * in supporting documentation.  Silicon Graphics makes no
  51  * representations about the suitability of this software for any
  52  * purpose.  It is provided "as is" without express or implied warranty.
  53  */
  54
  55 /* NOTE: This is an internal header file, included by other STL headers.
  56  *   You should not attempt to use it directly.
  57  */
  58
  59 #ifndef _CPP_BITS_STL_HEAP_H
  60 #define _CPP_BITS_STL_HEAP_H 1
  61
  62 namespace std
  63 {
  64
  65   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
  66
  67   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
  68     void
  69     __push_heap(_RandomAccessIterator __first,
  70                 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
  71     {
  72       _Distance __parent = (__holeIndex - 1) / 2;
  73       while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
  74         *(__first + __holeIndex) = *(__first + __parent);
  75         __holeIndex = __parent;
  76         __parent = (__holeIndex - 1) / 2;
  77       }
  78       *(__first + __holeIndex) = __value;
  79     }
  80
  81   template<typename _RandomAccessIterator>
  82     inline void
  83     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  84     {
  85       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  86           _ValueType;
  87       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  88           _DistanceType;
  89
  90       // concept requirements
  91       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  92             _RandomAccessIterator>)
  93       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
  94
  95       __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0),
  96                   _ValueType(*(__last - 1)));
  97     }
  98
  99   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
 100             typename _Compare>
 101     void
 102     __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 103                 _Distance __topIndex, _Tp __value, _Compare __comp)
 104     {
 105       _Distance __parent = (__holeIndex - 1) / 2;
 106       while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
 107         *(__first + __holeIndex) = *(__first + __parent);
 108         __holeIndex = __parent;
 109         __parent = (__holeIndex - 1) / 2;
 110       }
 111       *(__first + __holeIndex) = __value;
 112     }
 113
 114   template<typename _RandomAccessIterator, typename _Compare>
 115     inline void
 116     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 117               _Compare __comp)
 118     {
 119       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 120           _ValueType;
 121       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 122           _DistanceType;
 123
 124       // concept requirements
 125       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 126             _RandomAccessIterator>)
 127
 128       __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0),
 129                   _ValueType(*(__last - 1)), __comp);
 130     }
 131
 132   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
 133     void
 134     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 135                   _Distance __len, _Tp __value)
 136     {
 137       _Distance __topIndex = __holeIndex;
 138       _Distance __secondChild = 2 * __holeIndex + 2;
 139       while (__secondChild < __len) {
 140         if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
 141           __secondChild--;
 142         *(__first + __holeIndex) = *(__first + __secondChild);
 143         __holeIndex = __secondChild;
 144         __secondChild = 2 * (__secondChild + 1);
 145       }
 146       if (__secondChild == __len) {
 147         *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 148         __holeIndex = __secondChild - 1;
 149       }
 150       __push_heap(__first, __holeIndex, __topIndex, __value);
 151     }
 152
 153   template<typename _RandomAccessIterator, typename _Tp>
 154     inline void
 155     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 156                _RandomAccessIterator __result, _Tp __value)
 157     {
 158       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
 159       *__result = *__first;
 160       __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
 161     }
 162
 163   template<typename _RandomAccessIterator>
 164     inline void
 165     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 166     {
 167       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
 168
 169       // concept requirements
 170       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 171             _RandomAccessIterator>)
 172       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
 173
 174       __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)));
 175     }
 176
 177   template<typename _RandomAccessIterator, typename _Distance,
 178            typename _Tp, typename _Compare>
 179     void
 180     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 181                   _Distance __len, _Tp __value, _Compare __comp)
 182     {
 183       _Distance __topIndex = __holeIndex;
 184       _Distance __secondChild = 2 * __holeIndex + 2;
 185       while (__secondChild < __len) {
 186         if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
 187           __secondChild--;
 188         *(__first + __holeIndex) = *(__first + __secondChild);
 189         __holeIndex = __secondChild;
 190         __secondChild = 2 * (__secondChild + 1);
 191       }
 192       if (__secondChild == __len) {
 193         *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 194         __holeIndex = __secondChild - 1;
 195       }
 196       __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
 197     }
 198
 199   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
 200     inline void
 201     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 202                _RandomAccessIterator __result, _Tp __value, _Compare __comp)
 203     {
 204       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
 205       *__result = *__first;
 206       __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
 207                     __value, __comp);
 208     }
 209
 210   template<typename _RandomAccessIterator, typename _Compare>
 211     inline void
 212     pop_heap(_RandomAccessIterator __first,
 213              _RandomAccessIterator __last, _Compare __comp)
 214     {
 215       // concept requirements
 216       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 217             _RandomAccessIterator>)
 218
 219       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
 220       __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)), __comp);
 221     }
 222
 223   template<typename _RandomAccessIterator>
 224     void
 225     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 226     {
 227       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 228           _ValueType;
 229       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 230           _DistanceType;
 231
 232       // concept requirements
 233       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 234             _RandomAccessIterator>)
 235       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
 236
 237       if (__last - __first < 2) return;
 238       _DistanceType __len = __last - __first;
 239       _DistanceType __parent = (__len - 2)/2;
 240
 241       while (true) {
 242         __adjust_heap(__first, __parent, __len, _ValueType(*(__first + __parent)));
 243         if (__parent == 0) return;
 244         __parent--;
 245       }
 246     }
 247
 248   template<typename _RandomAccessIterator, typename _Compare>
 249     inline void
 250     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 251               _Compare __comp)
 252     {
 253       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 254           _ValueType;
 255       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 256           _DistanceType;
 257
 258       // concept requirements
 259       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 260             _RandomAccessIterator>)
 261
 262       if (__last - __first < 2) return;
 263       _DistanceType __len = __last - __first;
 264       _DistanceType __parent = (__len - 2)/2;
 265
 266       while (true) {
 267         __adjust_heap(__first, __parent, __len,
 268                       _ValueType(*(__first + __parent)), __comp);
 269         if (__parent == 0) return;
 270         __parent--;
 271       }
 272     }
 273
 274   template<typename _RandomAccessIterator>
 275     void
 276     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 277     {
 278       // concept requirements
 279       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 280             _RandomAccessIterator>)
 281       __glibcpp_function_requires(_LessThanComparableConcept<
 282             typename iterator_traits<_RandomAccessIterator>::value_type>)
 283
 284       while (__last - __first > 1)
 285         pop_heap(__first, __last--);
 286     }
 287
 288   template<typename _RandomAccessIterator, typename _Compare>
 289     void
 290     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 291               _Compare __comp)
 292     {
 293       // concept requirements
 294       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 295             _RandomAccessIterator>)
 296
 297       while (__last - __first > 1)
 298         pop_heap(__first, __last--, __comp);
 299     }
 300
 301 } // namespace std
 302
 303 #endif /* _CPP_BITS_STL_HEAP_H */
 304
 305 // Local Variables:
 306 // mode:C++
 307 // End: