Subversion Repositories scarts

// Algorithm extensions -*- C++ -*-

// Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 2, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along

// with this library; see the file COPYING.  If not, write to the Free

// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,

// USA.

// As a special exception, you may use this file as part of a free software

// library without restriction.  Specifically, if other files instantiate

// templates or use macros or inline functions from this file, or you compile

// this file and link it with other files to produce an executable, this

// file does not by itself cause the resulting executable to be covered by

// the GNU General Public License.  This exception does not however

// invalidate any other reasons why the executable file might be covered by

// the GNU General Public License.

/*

 *

 * Copyright (c) 1994

 * Hewlett-Packard Company

 *

 * Permission to use, copy, modify, distribute and sell this software

 * and its documentation for any purpose is hereby granted without fee,

 * provided that the above copyright notice appear in all copies and

 * that both that copyright notice and this permission notice appear

 * in supporting documentation.  Hewlett-Packard Company makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 *

 *

 * Copyright (c) 1996

 * Silicon Graphics Computer Systems, Inc.

 *

 * Permission to use, copy, modify, distribute and sell this software

 * and its documentation for any purpose is hereby granted without fee,

 * provided that the above copyright notice appear in all copies and

 * that both that copyright notice and this permission notice appear

 * in supporting documentation.  Silicon Graphics makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 */

/** @file ext/algorithm

 *  This file is a GNU extension to the Standard C++ Library (possibly

 *  containing extensions from the HP/SGI STL subset).

 */

#ifndef _EXT_ALGORITHM

#define _EXT_ALGORITHM 1

#pragma GCC system_header

#include 

namespace __gnu_cxx

{

  using std::ptrdiff_t;

  using std::min;

  using std::pair;

  using std::input_iterator_tag;

  using std::random_access_iterator_tag;

  using std::iterator_traits;

  //--------------------------------------------------

  // copy_n (not part of the C++ standard)

  template

    pair<_InputIterator, _OutputIterator>

    __copy_n(_InputIterator __first, _Size __count,

             _OutputIterator __result,

             input_iterator_tag)

    {

      for ( ; __count > 0; --__count)

        {

          *__result = *__first;

          ++__first;

          ++__result;

        }

      return pair<_InputIterator, _OutputIterator>(__first, __result);

    }

  template

    inline pair<_RAIterator, _OutputIterator>

    __copy_n(_RAIterator __first, _Size __count,

             _OutputIterator __result,

             random_access_iterator_tag)

    {

      _RAIterator __last = __first + __count;

      return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,

                                                                  __last,

                                                                  __result));

    }

  /**

   *  @brief Copies the range [first,first+count) into [result,result+count).

   *  @param  first  An input iterator.

   *  @param  count  The number of elements to copy.

   *  @param  result An output iterator.

   *  @return   A std::pair composed of first+count and result+count.

   *

   *  This is an SGI extension.

   *  This inline function will boil down to a call to @c memmove whenever

   *  possible.  Failing that, if random access iterators are passed, then the

   *  loop count will be known (and therefore a candidate for compiler

   *  optimizations such as unrolling).

   *  @ingroup SGIextensions

  */

  template

    inline pair<_InputIterator, _OutputIterator>

    copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)

    {

      // concept requirements

      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

            typename iterator_traits<_InputIterator>::value_type>)

      return __copy_n(__first, __count, __result,

                      std::__iterator_category(__first));

    }

  template

    int

    __lexicographical_compare_3way(_InputIterator1 __first1,

                                   _InputIterator1 __last1,

                                   _InputIterator2 __first2,

                                   _InputIterator2 __last2)

    {

      while (__first1 != __last1 && __first2 != __last2)

        {

          if (*__first1 < *__first2)

            return -1;

          if (*__first2 < *__first1)

            return 1;

          ++__first1;

          ++__first2;

        }

      if (__first2 == __last2)

        return !(__first1 == __last1);

      else

        return -1;

    }

  inline int

  __lexicographical_compare_3way(const unsigned char* __first1,

                                 const unsigned char* __last1,

                                 const unsigned char* __first2,

                                 const unsigned char* __last2)

  {

    const ptrdiff_t __len1 = __last1 - __first1;

    const ptrdiff_t __len2 = __last2 - __first2;

    const int __result = std::memcmp(__first1, __first2, min(__len1, __len2));

    return __result != 0 ? __result

                         : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));

  }

  inline int

  __lexicographical_compare_3way(const char* __first1, const char* __last1,

                                 const char* __first2, const char* __last2)

  {

#if CHAR_MAX == SCHAR_MAX

    return __lexicographical_compare_3way((const signed char*) __first1,

                                          (const signed char*) __last1,

                                          (const signed char*) __first2,

                                          (const signed char*) __last2);

#else

    return __lexicographical_compare_3way((const unsigned char*) __first1,

                                          (const unsigned char*) __last1,

                                          (const unsigned char*) __first2,

                                          (const unsigned char*) __last2);

#endif

  }

  /**

   *  @brief @c memcmp on steroids.

   *  @param  first1  An input iterator.

   *  @param  last1   An input iterator.

   *  @param  first2  An input iterator.

   *  @param  last2   An input iterator.

   *  @return   An int, as with @c memcmp.

   *

   *  The return value will be less than zero if the first range is

   *  "lexigraphically less than" the second, greater than zero if the second

   *  range is "lexigraphically less than" the first, and zero otherwise.

   *  This is an SGI extension.

   *  @ingroup SGIextensions

  */

  template

    int

    lexicographical_compare_3way(_InputIterator1 __first1,

                                 _InputIterator1 __last1,

                                 _InputIterator2 __first2,

                                 _InputIterator2 __last2)

    {

      // concept requirements

      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

      __glibcxx_function_requires(_LessThanComparableConcept<

            typename iterator_traits<_InputIterator1>::value_type>)

      __glibcxx_function_requires(_LessThanComparableConcept<

            typename iterator_traits<_InputIterator2>::value_type>)

      __glibcxx_requires_valid_range(__first1, __last1);

      __glibcxx_requires_valid_range(__first2, __last2);

      return __lexicographical_compare_3way(__first1, __last1, __first2,

                                            __last2);

    }

  // count and count_if: this version, whose return type is void, was present

  // in the HP STL, and is retained as an extension for backward compatibility.

  template

    void

    count(_InputIterator __first, _InputIterator __last,

          const _Tp& __value,

          _Size& __n)

    {

      // concept requirements

      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

      __glibcxx_function_requires(_EqualityComparableConcept<

            typename iterator_traits<_InputIterator>::value_type >)

      __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)

      __glibcxx_requires_valid_range(__first, __last);

      for ( ; __first != __last; ++__first)

        if (*__first == __value)

          ++__n;

    }

  template

    void

    count_if(_InputIterator __first, _InputIterator __last,

             _Predicate __pred,

             _Size& __n)

    {

      // concept requirements

      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

      __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

            typename iterator_traits<_InputIterator>::value_type>)

      __glibcxx_requires_valid_range(__first, __last);

      for ( ; __first != __last; ++__first)

        if (__pred(*__first))

          ++__n;

    }

  // random_sample and random_sample_n (extensions, not part of the standard).

  /**

   *  This is an SGI extension.

   *  @ingroup SGIextensions

   *  @doctodo

  */

  template

           typename _Distance>

    _OutputIterator

    random_sample_n(_ForwardIterator __first, _ForwardIterator __last,

                    _OutputIterator __out, const _Distance __n)

    {

      // concept requirements

      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

                typename iterator_traits<_ForwardIterator>::value_type>)

      __glibcxx_requires_valid_range(__first, __last);

      _Distance __remaining = std::distance(__first, __last);

      _Distance __m = min(__n, __remaining);

      while (__m > 0)

        {

          if ((std::rand() % __remaining) < __m)

            {

              *__out = *__first;

              ++__out;

              --__m;

            }

          --__remaining;

          ++__first;

        }

      return __out;

    }

  /**

   *  This is an SGI extension.

   *  @ingroup SGIextensions

   *  @doctodo

  */

  template

           typename _Distance, typename _RandomNumberGenerator>

    _OutputIterator

    random_sample_n(_ForwardIterator __first, _ForwardIterator __last,

                   _OutputIterator __out, const _Distance __n,

                   _RandomNumberGenerator& __rand)

    {

      // concept requirements

      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

                typename iterator_traits<_ForwardIterator>::value_type>)

      __glibcxx_function_requires(_UnaryFunctionConcept<

                _RandomNumberGenerator, _Distance, _Distance>)

      __glibcxx_requires_valid_range(__first, __last);

      _Distance __remaining = std::distance(__first, __last);

      _Distance __m = min(__n, __remaining);

      while (__m > 0)

        {

          if (__rand(__remaining) < __m)

            {

              *__out = *__first;

              ++__out;

              --__m;

            }

          --__remaining;

          ++__first;

        }

      return __out;

    }

  template

           typename _Distance>

    _RandomAccessIterator

    __random_sample(_InputIterator __first, _InputIterator __last,

                    _RandomAccessIterator __out,

                    const _Distance __n)

    {

      _Distance __m = 0;

      _Distance __t = __n;

      for ( ; __first != __last && __m < __n; ++__m, ++__first)

        __out[__m] = *__first;

      while (__first != __last)

        {

          ++__t;

          _Distance __M = std::rand() % (__t);

          if (__M < __n)

            __out[__M] = *__first;

          ++__first;

        }

      return __out + __m;

    }

  template

           typename _RandomNumberGenerator, typename _Distance>

    _RandomAccessIterator

    __random_sample(_InputIterator __first, _InputIterator __last,

                    _RandomAccessIterator __out,

                    _RandomNumberGenerator& __rand,

                    const _Distance __n)

    {

      // concept requirements

      __glibcxx_function_requires(_UnaryFunctionConcept<

            _RandomNumberGenerator, _Distance, _Distance>)

      _Distance __m = 0;

      _Distance __t = __n;

      for ( ; __first != __last && __m < __n; ++__m, ++__first)

        __out[__m] = *__first;

      while (__first != __last)

        {

          ++__t;

          _Distance __M = __rand(__t);

          if (__M < __n)

            __out[__M] = *__first;

          ++__first;

        }

      return __out + __m;

    }

  /**

   *  This is an SGI extension.

   *  @ingroup SGIextensions

   *  @doctodo

  */

  template

    inline _RandomAccessIterator

    random_sample(_InputIterator __first, _InputIterator __last,

                  _RandomAccessIterator __out_first,

                  _RandomAccessIterator __out_last)

    {

      // concept requirements

      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

            _RandomAccessIterator>)

      __glibcxx_requires_valid_range(__first, __last);

      __glibcxx_requires_valid_range(__out_first, __out_last);

      return __random_sample(__first, __last,

                             __out_first, __out_last - __out_first);

    }

  /**

   *  This is an SGI extension.

   *  @ingroup SGIextensions

   *  @doctodo

  */

  template

           typename _RandomNumberGenerator>

    inline _RandomAccessIterator

    random_sample(_InputIterator __first, _InputIterator __last,

                  _RandomAccessIterator __out_first,

                  _RandomAccessIterator __out_last,

                  _RandomNumberGenerator& __rand)

    {

      // concept requirements

      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

            _RandomAccessIterator>)

      __glibcxx_requires_valid_range(__first, __last);

      __glibcxx_requires_valid_range(__out_first, __out_last);

      return __random_sample(__first, __last,

                             __out_first, __rand,

                             __out_last - __out_first);

    }

  /**

   *  This is an SGI extension.

   *  @ingroup SGIextensions

   *  @doctodo

  */

  template

    inline bool

    is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)

    {

      // concept requirements

      __glibcxx_function_requires(_RandomAccessIteratorConcept<

                                  _RandomAccessIterator>)

      __glibcxx_function_requires(_LessThanComparableConcept<

            typename iterator_traits<_RandomAccessIterator>::value_type>)

      __glibcxx_requires_valid_range(__first, __last);

      return std::__is_heap(__first, __last - __first);

    }

  /**

   *  This is an SGI extension.

   *  @ingroup SGIextensions

   *  @doctodo

  */

  template

    inline bool

    is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,

            _StrictWeakOrdering __comp)

    {

      // concept requirements

      __glibcxx_function_requires(_RandomAccessIteratorConcept<

                                  _RandomAccessIterator>)

      __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,

            typename iterator_traits<_RandomAccessIterator>::value_type,

            typename iterator_traits<_RandomAccessIterator>::value_type>)

      __glibcxx_requires_valid_range(__first, __last);

      return std::__is_heap(__first, __comp, __last - __first);

    }

  // is_sorted, a predicated testing whether a range is sorted in

  // nondescending order.  This is an extension, not part of the C++

  // standard.

  /**

   *  This is an SGI extension.

   *  @ingroup SGIextensions

   *  @doctodo

  */

  template

    bool

    is_sorted(_ForwardIterator __first, _ForwardIterator __last)

    {

      // concept requirements

      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

      __glibcxx_function_requires(_LessThanComparableConcept<

            typename iterator_traits<_ForwardIterator>::value_type>)

      __glibcxx_requires_valid_range(__first, __last);

      if (__first == __last)

        return true;

      _ForwardIterator __next = __first;

      for (++__next; __next != __last; __first = __next, ++__next)

        if (*__next < *__first)

          return false;

      return true;

    }

  /**

   *  This is an SGI extension.

   *  @ingroup SGIextensions

   *  @doctodo

  */

  template

    bool

    is_sorted(_ForwardIterator __first, _ForwardIterator __last,

              _StrictWeakOrdering __comp)

    {

      // concept requirements

      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

      __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,

            typename iterator_traits<_ForwardIterator>::value_type,

            typename iterator_traits<_ForwardIterator>::value_type>)

      __glibcxx_requires_valid_range(__first, __last);

      if (__first == __last)

        return true;

      _ForwardIterator __next = __first;

      for (++__next; __next != __last; __first = __next, ++__next)

        if (__comp(*__next, *__first))

          return false;

      return true;

    }

} // namespace __gnu_cxx

#endif /* _EXT_ALGORITHM */