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