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 /** @file stl_heap.h
  56  *  This is an internal header file, included by other library headers.
  57  *  You should not attempt to use it directly.
  58  */
  59
  60 #ifndef _CPP_BITS_STL_HEAP_H
  61 #define _CPP_BITS_STL_HEAP_H 1
  62
  63 namespace std
  64 {
  65
  66   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
  67
  68   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
  69     void
  70     __push_heap(_RandomAccessIterator __first,
  71                 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
  72     {
  73       _Distance __parent = (__holeIndex - 1) / 2;
  74       while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
  75         *(__first + __holeIndex) = *(__first + __parent);
  76         __holeIndex = __parent;
  77         __parent = (__holeIndex - 1) / 2;
  78       }
  79       *(__first + __holeIndex) = __value;
  80     }
  81
  82   template<typename _RandomAccessIterator>
  83     inline void
  84     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  85     {
  86       typedef typename iterator_traits<_RandomAccessIterator>::value_type
  87           _ValueType;
  88       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  89           _DistanceType;
  90
  91       // concept requirements
  92       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  93             _RandomAccessIterator>)
  94       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
  95
  96       __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0),
  97                   _ValueType(*(__last - 1)));
  98     }
  99
 100   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
 101             typename _Compare>
 102     void
 103     __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 104                 _Distance __topIndex, _Tp __value, _Compare __comp)
 105     {
 106       _Distance __parent = (__holeIndex - 1) / 2;
 107       while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
 108         *(__first + __holeIndex) = *(__first + __parent);
 109         __holeIndex = __parent;
 110         __parent = (__holeIndex - 1) / 2;
 111       }
 112       *(__first + __holeIndex) = __value;
 113     }
 114
 115   template<typename _RandomAccessIterator, typename _Compare>
 116     inline void
 117     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 118               _Compare __comp)
 119     {
 120       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 121           _ValueType;
 122       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 123           _DistanceType;
 124
 125       // concept requirements
 126       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 127             _RandomAccessIterator>)
 128
 129       __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0),
 130                   _ValueType(*(__last - 1)), __comp);
 131     }
 132
 133   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
 134     void
 135     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 136                   _Distance __len, _Tp __value)
 137     {
 138       _Distance __topIndex = __holeIndex;
 139       _Distance __secondChild = 2 * __holeIndex + 2;
 140       while (__secondChild < __len) {
 141         if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
 142           __secondChild--;
 143         *(__first + __holeIndex) = *(__first + __secondChild);
 144         __holeIndex = __secondChild;
 145         __secondChild = 2 * (__secondChild + 1);
 146       }
 147       if (__secondChild == __len) {
 148         *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 149         __holeIndex = __secondChild - 1;
 150       }
 151       __push_heap(__first, __holeIndex, __topIndex, __value);
 152     }
 153
 154   template<typename _RandomAccessIterator, typename _Tp>
 155     inline void
 156     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 157                _RandomAccessIterator __result, _Tp __value)
 158     {
 159       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
 160       *__result = *__first;
 161       __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
 162     }
 163
 164   template<typename _RandomAccessIterator>
 165     inline void
 166     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 167     {
 168       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
 169
 170       // concept requirements
 171       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 172             _RandomAccessIterator>)
 173       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
 174
 175       __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)));
 176     }
 177
 178   template<typename _RandomAccessIterator, typename _Distance,
 179            typename _Tp, typename _Compare>
 180     void
 181     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 182                   _Distance __len, _Tp __value, _Compare __comp)
 183     {
 184       _Distance __topIndex = __holeIndex;
 185       _Distance __secondChild = 2 * __holeIndex + 2;
 186       while (__secondChild < __len) {
 187         if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
 188           __secondChild--;
 189         *(__first + __holeIndex) = *(__first + __secondChild);
 190         __holeIndex = __secondChild;
 191         __secondChild = 2 * (__secondChild + 1);
 192       }
 193       if (__secondChild == __len) {
 194         *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 195         __holeIndex = __secondChild - 1;
 196       }
 197       __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
 198     }
 199
 200   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
 201     inline void
 202     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 203                _RandomAccessIterator __result, _Tp __value, _Compare __comp)
 204     {
 205       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
 206       *__result = *__first;
 207       __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
 208                     __value, __comp);
 209     }
 210
 211   template<typename _RandomAccessIterator, typename _Compare>
 212     inline void
 213     pop_heap(_RandomAccessIterator __first,
 214              _RandomAccessIterator __last, _Compare __comp)
 215     {
 216       // concept requirements
 217       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 218             _RandomAccessIterator>)
 219
 220       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
 221       __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)), __comp);
 222     }
 223
 224   template<typename _RandomAccessIterator>
 225     void
 226     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 227     {
 228       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 229           _ValueType;
 230       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 231           _DistanceType;
 232
 233       // concept requirements
 234       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 235             _RandomAccessIterator>)
 236       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
 237
 238       if (__last - __first < 2) return;
 239       _DistanceType __len = __last - __first;
 240       _DistanceType __parent = (__len - 2)/2;
 241
 242       while (true) {
 243         __adjust_heap(__first, __parent, __len, _ValueType(*(__first + __parent)));
 244         if (__parent == 0) return;
 245         __parent--;
 246       }
 247     }
 248
 249   template<typename _RandomAccessIterator, typename _Compare>
 250     inline void
 251     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 252               _Compare __comp)
 253     {
 254       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 255           _ValueType;
 256       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 257           _DistanceType;
 258
 259       // concept requirements
 260       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 261             _RandomAccessIterator>)
 262
 263       if (__last - __first < 2) return;
 264       _DistanceType __len = __last - __first;
 265       _DistanceType __parent = (__len - 2)/2;
 266
 267       while (true) {
 268         __adjust_heap(__first, __parent, __len,
 269                       _ValueType(*(__first + __parent)), __comp);
 270         if (__parent == 0) return;
 271         __parent--;
 272       }
 273     }
 274
 275   template<typename _RandomAccessIterator>
 276     void
 277     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 278     {
 279       // concept requirements
 280       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 281             _RandomAccessIterator>)
 282       __glibcpp_function_requires(_LessThanComparableConcept<
 283             typename iterator_traits<_RandomAccessIterator>::value_type>)
 284
 285       while (__last - __first > 1)
 286         pop_heap(__first, __last--);
 287     }
 288
 289   template<typename _RandomAccessIterator, typename _Compare>
 290     void
 291     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 292               _Compare __comp)
 293     {
 294       // concept requirements
 295       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 296             _RandomAccessIterator>)
 297
 298       while (__last - __first > 1)
 299         pop_heap(__first, __last--, __comp);
 300     }
 301
 302 } // namespace std
 303
 304 #endif /* _CPP_BITS_STL_HEAP_H */
 305
 306 // Local Variables:
 307 // mode:C++
 308 // End: