libstdc++-v3/include/ext/algorithm

   1 // Algorithm extensions -*- 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  *
  44  * Copyright (c) 1996
  45  * Silicon Graphics Computer Systems, Inc.
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Silicon Graphics makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  */
  55
  56 #ifndef _EXT_ALGORITHM
  57 #define _EXT_ALGORITHM
  58
  59 #pragma GCC system_header
  60 #include <bits/std_algorithm.h>
  61
  62 namespace __gnu_cxx
  63 {
  64   using std::ptrdiff_t;
  65   using std::min;
  66   using std::pair;
  67   using std::input_iterator_tag;
  68   using std::random_access_iterator_tag;
  69   using std::iterator_traits;
  70
  71   //--------------------------------------------------
  72   // copy_n (not part of the C++ standard)
  73
  74   template<typename _InputIter, typename _Size, typename _OutputIter>
  75     pair<_InputIter, _OutputIter>
  76     __copy_n(_InputIter __first, _Size __count,
  77              _OutputIter __result,
  78              input_iterator_tag)
  79     {
  80       for ( ; __count > 0; --__count) {
  81         *__result = *__first;
  82         ++__first;
  83         ++__result;
  84       }
  85       return pair<_InputIter, _OutputIter>(__first, __result);
  86     }
  87
  88   template<typename _RAIter, typename _Size, typename _OutputIter>
  89     inline pair<_RAIter, _OutputIter>
  90     __copy_n(_RAIter __first, _Size __count,
  91              _OutputIter __result,
  92              random_access_iterator_tag)
  93     {
  94       _RAIter __last = __first + __count;
  95       return pair<_RAIter, _OutputIter>(__last,
  96                                         std::copy(__first, __last, __result));
  97     }
  98
  99   /**
 100    *  @brief Copies the range [first,first+count) into [result,result+count).
 101    *  @param  first  An input iterator.
 102    *  @param  count  The number of elements to copy.
 103    *  @param  result An output iterator.
 104    *  @return   A std::pair composed of first+count and result+count.
 105    *
 106    *  This is an SGI extension.
 107    *  This inline function will boil down to a call to @c memmove whenever
 108    *  possible.  Failing that, if random access iterators are passed, then the
 109    *  loop count will be known (and therefore a candidate for compiler
 110    *  optimizations such as unrolling).
 111    *  @ingroup SGIextensions
 112   */
 113   template<typename _InputIter, typename _Size, typename _OutputIter>
 114     inline pair<_InputIter, _OutputIter>
 115     copy_n(_InputIter __first, _Size __count, _OutputIter __result)
 116     {
 117       // concept requirements
 118       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 119       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
 120             typename iterator_traits<_InputIter>::value_type>)
 121
 122       return __copy_n(__first, __count, __result,
 123                       std::__iterator_category(__first));
 124     }
 125
 126   template<typename _InputIter1, typename _InputIter2>
 127     int
 128     __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
 129                                    _InputIter2 __first2, _InputIter2 __last2)
 130     {
 131       while (__first1 != __last1 && __first2 != __last2) {
 132         if (*__first1 < *__first2)
 133           return -1;
 134         if (*__first2 < *__first1)
 135           return 1;
 136         ++__first1;
 137         ++__first2;
 138       }
 139       if (__first2 == __last2) {
 140         return !(__first1 == __last1);
 141       }
 142       else {
 143         return -1;
 144       }
 145     }
 146
 147   inline int
 148   __lexicographical_compare_3way(const unsigned char* __first1,
 149                                  const unsigned char* __last1,
 150                                  const unsigned char* __first2,
 151                                  const unsigned char* __last2)
 152   {
 153     const ptrdiff_t __len1 = __last1 - __first1;
 154     const ptrdiff_t __len2 = __last2 - __first2;
 155     const int __result = std::memcmp(__first1, __first2, min(__len1, __len2));
 156     return __result != 0 ? __result
 157                          : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
 158   }
 159
 160   inline int
 161   __lexicographical_compare_3way(const char* __first1, const char* __last1,
 162                                  const char* __first2, const char* __last2)
 163   {
 164 #if CHAR_MAX == SCHAR_MAX
 165     return __lexicographical_compare_3way(
 166                                   (const signed char*) __first1,
 167                                   (const signed char*) __last1,
 168                                   (const signed char*) __first2,
 169                                   (const signed char*) __last2);
 170 #else
 171     return __lexicographical_compare_3way((const unsigned char*) __first1,
 172                                           (const unsigned char*) __last1,
 173                                           (const unsigned char*) __first2,
 174                                           (const unsigned char*) __last2);
 175 #endif
 176   }
 177
 178   /**
 179    *  @brief @c memcmp on steroids.
 180    *  @param  first1  An input iterator.
 181    *  @param  last1   An input iterator.
 182    *  @param  first2  An input iterator.
 183    *  @param  last2   An input iterator.
 184    *  @return   An int, as with @c memcmp.
 185    *
 186    *  The return value will be less than zero if the first range is
 187    *  "lexigraphically less than" the second, greater than zero if the second
 188    *  range is "lexigraphically less than" the first, and zero otherwise.
 189    *  This is an SGI extension.
 190    *  @ingroup SGIextensions
 191   */
 192   template<typename _InputIter1, typename _InputIter2>
 193     int
 194     lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
 195                                  _InputIter2 __first2, _InputIter2 __last2)
 196     {
 197       // concept requirements
 198       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
 199       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
 200       __glibcpp_function_requires(_LessThanComparableConcept<
 201             typename iterator_traits<_InputIter1>::value_type>)
 202       __glibcpp_function_requires(_LessThanComparableConcept<
 203             typename iterator_traits<_InputIter2>::value_type>)
 204
 205       return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
 206     }
 207
 208   // count and count_if: this version, whose return type is void, was present
 209   // in the HP STL, and is retained as an extension for backward compatibility.
 210
 211   template<typename _InputIter, typename _Tp, typename _Size>
 212     void
 213     count(_InputIter __first, _InputIter __last,
 214           const _Tp& __value,
 215           _Size& __n)
 216     {
 217       // concept requirements
 218       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 219       __glibcpp_function_requires(_EqualityComparableConcept<
 220             typename iterator_traits<_InputIter>::value_type >)
 221       __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
 222       for ( ; __first != __last; ++__first)
 223         if (*__first == __value)
 224           ++__n;
 225     }
 226
 227   template<typename _InputIter, typename _Predicate, typename _Size>
 228     void
 229     count_if(_InputIter __first, _InputIter __last,
 230              _Predicate __pred,
 231              _Size& __n)
 232     {
 233       // concept requirements
 234       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 235       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
 236             typename iterator_traits<_InputIter>::value_type>)
 237       for ( ; __first != __last; ++__first)
 238         if (__pred(*__first))
 239           ++__n;
 240     }
 241
 242   // random_sample and random_sample_n (extensions, not part of the standard).
 243
 244   template<typename _ForwardIter, typename _OutputIter, typename _Distance>
 245     _OutputIter
 246     random_sample_n(_ForwardIter __first, _ForwardIter __last,
 247                     _OutputIter __out, const _Distance __n)
 248     {
 249       // concept requirements
 250       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 251       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
 252                 typename iterator_traits<_ForwardIter>::value_type>)
 253
 254       _Distance __remaining = std::distance(__first, __last);
 255       _Distance __m = min(__n, __remaining);
 256
 257       while (__m > 0) {
 258         if (std::__random_number(__remaining) < __m) {
 259               *__out = *__first;
 260               ++__out;
 261               --__m;
 262         }
 263
 264         --__remaining;
 265         ++__first;
 266       }
 267       return __out;
 268     }
 269
 270   template<typename _ForwardIter, typename _OutputIter, typename _Distance,
 271            typename _RandomNumberGenerator>
 272     _OutputIter
 273     random_sample_n(_ForwardIter __first, _ForwardIter __last,
 274                    _OutputIter __out, const _Distance __n,
 275                    _RandomNumberGenerator& __rand)
 276     {
 277       // concept requirements
 278       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 279       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
 280                 typename iterator_traits<_ForwardIter>::value_type>)
 281       __glibcpp_function_requires(_UnaryFunctionConcept<
 282                 _RandomNumberGenerator, _Distance, _Distance>)
 283
 284       _Distance __remaining = std::distance(__first, __last);
 285       _Distance __m = min(__n, __remaining);
 286
 287       while (__m > 0) {
 288         if (__rand(__remaining) < __m) {
 289               *__out = *__first;
 290               ++__out;
 291               --__m;
 292         }
 293
 294         --__remaining;
 295         ++__first;
 296       }
 297       return __out;
 298     }
 299
 300   template<typename _InputIter, typename _RandomAccessIter, typename _Distance>
 301     _RandomAccessIter
 302     __random_sample(_InputIter __first, _InputIter __last,
 303                     _RandomAccessIter __out,
 304                     const _Distance __n)
 305     {
 306       _Distance __m = 0;
 307       _Distance __t = __n;
 308       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 309         __out[__m] = *__first;
 310
 311       while (__first != __last) {
 312         ++__t;
 313         _Distance __M = std::__random_number(__t);
 314         if (__M < __n)
 315           __out[__M] = *__first;
 316         ++__first;
 317       }
 318
 319       return __out + __m;
 320     }
 321
 322   template<typename _InputIter, typename _RandomAccessIter,
 323            typename _RandomNumberGenerator, typename _Distance>
 324     _RandomAccessIter
 325     __random_sample(_InputIter __first, _InputIter __last,
 326                     _RandomAccessIter __out,
 327                     _RandomNumberGenerator& __rand,
 328                     const _Distance __n)
 329     {
 330       // concept requirements
 331       __glibcpp_function_requires(_UnaryFunctionConcept<
 332             _RandomNumberGenerator, _Distance, _Distance>)
 333
 334       _Distance __m = 0;
 335       _Distance __t = __n;
 336       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 337         __out[__m] = *__first;
 338
 339       while (__first != __last) {
 340         ++__t;
 341         _Distance __M = __rand(__t);
 342         if (__M < __n)
 343           __out[__M] = *__first;
 344         ++__first;
 345       }
 346
 347       return __out + __m;
 348     }
 349
 350   template<typename _InputIter, typename _RandomAccessIter>
 351     inline _RandomAccessIter
 352     random_sample(_InputIter __first, _InputIter __last,
 353                   _RandomAccessIter __out_first, _RandomAccessIter __out_last)
 354     {
 355       // concept requirements
 356       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 357       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 358             _RandomAccessIter>)
 359
 360       return __random_sample(__first, __last,
 361                              __out_first, __out_last - __out_first);
 362     }
 363
 364   template<typename _InputIter, typename _RandomAccessIter,
 365            typename _RandomNumberGenerator>
 366     inline _RandomAccessIter
 367     random_sample(_InputIter __first, _InputIter __last,
 368                   _RandomAccessIter __out_first, _RandomAccessIter __out_last,
 369                   _RandomNumberGenerator& __rand)
 370     {
 371       // concept requirements
 372       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 373       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 374             _RandomAccessIter>)
 375
 376       return __random_sample(__first, __last,
 377                              __out_first, __rand,
 378                              __out_last - __out_first);
 379     }
 380
 381   // is_heap, a predicate testing whether or not a range is
 382   // a heap.  This function is an extension, not part of the C++
 383   // standard.
 384
 385   template<typename _RandomAccessIter, typename _Distance>
 386     bool
 387     __is_heap(_RandomAccessIter __first, _Distance __n)
 388     {
 389       _Distance __parent = 0;
 390       for (_Distance __child = 1; __child < __n; ++__child) {
 391         if (__first[__parent] < __first[__child])
 392           return false;
 393         if ((__child & 1) == 0)
 394           ++__parent;
 395       }
 396       return true;
 397     }
 398
 399   template<typename _RandomAccessIter, typename _Distance,
 400            typename _StrictWeakOrdering>
 401     bool
 402     __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
 403               _Distance __n)
 404     {
 405       _Distance __parent = 0;
 406       for (_Distance __child = 1; __child < __n; ++__child) {
 407         if (__comp(__first[__parent], __first[__child]))
 408           return false;
 409         if ((__child & 1) == 0)
 410           ++__parent;
 411       }
 412       return true;
 413     }
 414
 415   template<typename _RandomAccessIter>
 416     inline bool
 417     is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
 418     {
 419       // concept requirements
 420       __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
 421       __glibcpp_function_requires(_LessThanComparableConcept<
 422             typename iterator_traits<_RandomAccessIter>::value_type>)
 423
 424       return __is_heap(__first, __last - __first);
 425     }
 426
 427   template<typename _RandomAccessIter, typename _StrictWeakOrdering>
 428     inline bool
 429     is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
 430             _StrictWeakOrdering __comp)
 431     {
 432       // concept requirements
 433       __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
 434       __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 435             typename iterator_traits<_RandomAccessIter>::value_type,
 436             typename iterator_traits<_RandomAccessIter>::value_type>)
 437
 438       return __is_heap(__first, __comp, __last - __first);
 439     }
 440
 441   // is_sorted, a predicated testing whether a range is sorted in
 442   // nondescending order.  This is an extension, not part of the C++
 443   // standard.
 444
 445   template<typename _ForwardIter>
 446     bool
 447     is_sorted(_ForwardIter __first, _ForwardIter __last)
 448     {
 449       // concept requirements
 450       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 451       __glibcpp_function_requires(_LessThanComparableConcept<
 452             typename iterator_traits<_ForwardIter>::value_type>)
 453
 454       if (__first == __last)
 455         return true;
 456
 457       _ForwardIter __next = __first;
 458       for (++__next; __next != __last; __first = __next, ++__next) {
 459         if (*__next < *__first)
 460           return false;
 461       }
 462
 463       return true;
 464     }
 465
 466   template<typename _ForwardIter, typename _StrictWeakOrdering>
 467     bool
 468     is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp)
 469     {
 470       // concept requirements
 471       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 472       __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 473             typename iterator_traits<_ForwardIter>::value_type,
 474             typename iterator_traits<_ForwardIter>::value_type>)
 475
 476       if (__first == __last)
 477         return true;
 478
 479       _ForwardIter __next = __first;
 480       for (++__next; __next != __last; __first = __next, ++__next) {
 481         if (__comp(*__next, *__first))
 482           return false;
 483       }
 484
 485       return true;
 486     }
 487
 488 } // namespace __gnu_cxx
 489
 490 #endif /* _EXT_ALGORITHM */