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