/storage/packages/gcc/5.3.0/include/c++/5.3.0/bits/stl_algobase.h

// Core algorithmic facilities -*- C++ -*-

// Copyright (C) 2001-2015 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 3, 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.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

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

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// <http://www.gnu.org/licenses/>.

/*

 *

 * 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-1998

 * 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 bits/stl_algobase.h

 *  This is an internal header file, included by other library headers.

 *  Do not attempt to use it directly. @headername{algorithm}

 */

#ifndef _STL_ALGOBASE_H

#define _STL_ALGOBASE_H 1

#include <bits/c++config.h>

#include <bits/functexcept.h>

#include <bits/cpp_type_traits.h>

#include <ext/type_traits.h>

#include <ext/numeric_traits.h>

#include <bits/stl_pair.h>

#include <bits/stl_iterator_base_types.h>

#include <bits/stl_iterator_base_funcs.h>

#include <bits/stl_iterator.h>

#include <bits/concept_check.h>

#include <debug/debug.h>

#include <bits/move.h> // For std::swap and _GLIBCXX_MOVE

#include <bits/predefined_ops.h>

namespace std _GLIBCXX_VISIBILITY(default)

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

#if __cplusplus < 201103L

  // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a

  // nutshell, we are partially implementing the resolution of DR 187,

  // when it's safe, i.e., the value_types are equal.

  template<bool _BoolType>

    struct __iter_swap

    {

      template<typename _ForwardIterator1, typename _ForwardIterator2>

        static void

        iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)

        {

          typedef typename iterator_traits<_ForwardIterator1>::value_type

            _ValueType1;

          _ValueType1 __tmp = _GLIBCXX_MOVE(*__a);

          *__a = _GLIBCXX_MOVE(*__b);

          *__b = _GLIBCXX_MOVE(__tmp);

	}

    };

  template<>

    struct __iter_swap<true>

    {

      template<typename _ForwardIterator1, typename _ForwardIterator2>

        static void 

        iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)

        {

          swap(*__a, *__b);

        }

    };

#endif

  /**

   *  @brief Swaps the contents of two iterators.

   *  @ingroup mutating_algorithms

   *  @param  __a  An iterator.

   *  @param  __b  Another iterator.

   *  @return   Nothing.

   *

   *  This function swaps the values pointed to by two iterators, not the

   *  iterators themselves.

  */

  template<typename _ForwardIterator1, typename _ForwardIterator2>

    inline void

    iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)

    {

      // concept requirements

      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

				  _ForwardIterator1>)

      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

				  _ForwardIterator2>)

#if __cplusplus < 201103L

      typedef typename iterator_traits<_ForwardIterator1>::value_type

	_ValueType1;

      typedef typename iterator_traits<_ForwardIterator2>::value_type

	_ValueType2;

      __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,

				  _ValueType2>)

      __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,

				  _ValueType1>)

      typedef typename iterator_traits<_ForwardIterator1>::reference

	_ReferenceType1;

      typedef typename iterator_traits<_ForwardIterator2>::reference

	_ReferenceType2;

      std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value

	&& __are_same<_ValueType1&, _ReferenceType1>::__value

	&& __are_same<_ValueType2&, _ReferenceType2>::__value>::

	iter_swap(__a, __b);

#else

      swap(*__a, *__b);

#endif

    }

  /**

   *  @brief Swap the elements of two sequences.

   *  @ingroup mutating_algorithms

   *  @param  __first1  A forward iterator.

   *  @param  __last1   A forward iterator.

   *  @param  __first2  A forward iterator.

   *  @return   An iterator equal to @p first2+(last1-first1).

   *

   *  Swaps each element in the range @p [first1,last1) with the

   *  corresponding element in the range @p [first2,(last1-first1)).

   *  The ranges must not overlap.

  */

  template<typename _ForwardIterator1, typename _ForwardIterator2>

    _ForwardIterator2

    swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

		_ForwardIterator2 __first2)

    {

      // concept requirements

      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

				  _ForwardIterator1>)

      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

				  _ForwardIterator2>)

      __glibcxx_requires_valid_range(__first1, __last1);

      for (; __first1 != __last1; ++__first1, ++__first2)

	std::iter_swap(__first1, __first2);

      return __first2;

    }

  /**

   *  @brief This does what you think it does.

   *  @ingroup sorting_algorithms

   *  @param  __a  A thing of arbitrary type.

   *  @param  __b  Another thing of arbitrary type.

   *  @return   The lesser of the parameters.

   *

   *  This is the simple classic generic implementation.  It will work on

   *  temporary expressions, since they are only evaluated once, unlike a

   *  preprocessor macro.

  */

  template<typename _Tp>

    _GLIBCXX14_CONSTEXPR

    inline const _Tp&

    min(const _Tp& __a, const _Tp& __b)

    {

      // concept requirements

      __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)

      //return __b < __a ? __b : __a;

      if (__b < __a)

	return __b;

      return __a;

    }

  /**

   *  @brief This does what you think it does.

   *  @ingroup sorting_algorithms

   *  @param  __a  A thing of arbitrary type.

   *  @param  __b  Another thing of arbitrary type.

   *  @return   The greater of the parameters.

   *

   *  This is the simple classic generic implementation.  It will work on

   *  temporary expressions, since they are only evaluated once, unlike a

   *  preprocessor macro.

  */

  template<typename _Tp>

    _GLIBCXX14_CONSTEXPR

    inline const _Tp&

    max(const _Tp& __a, const _Tp& __b)

    {

      // concept requirements

      __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)

      //return  __a < __b ? __b : __a;

      if (__a < __b)

	return __b;

      return __a;

    }

  /**

   *  @brief This does what you think it does.

   *  @ingroup sorting_algorithms

   *  @param  __a  A thing of arbitrary type.

   *  @param  __b  Another thing of arbitrary type.

   *  @param  __comp  A @link comparison_functors comparison functor@endlink.

   *  @return   The lesser of the parameters.

   *

   *  This will work on temporary expressions, since they are only evaluated

   *  once, unlike a preprocessor macro.

  */

  template<typename _Tp, typename _Compare>

    _GLIBCXX14_CONSTEXPR

    inline const _Tp&

    min(const _Tp& __a, const _Tp& __b, _Compare __comp)

    {

      //return __comp(__b, __a) ? __b : __a;

      if (__comp(__b, __a))

	return __b;

      return __a;

    }

  /**

   *  @brief This does what you think it does.

   *  @ingroup sorting_algorithms

   *  @param  __a  A thing of arbitrary type.

   *  @param  __b  Another thing of arbitrary type.

   *  @param  __comp  A @link comparison_functors comparison functor@endlink.

   *  @return   The greater of the parameters.

   *

   *  This will work on temporary expressions, since they are only evaluated

   *  once, unlike a preprocessor macro.

  */

  template<typename _Tp, typename _Compare>

    _GLIBCXX14_CONSTEXPR

    inline const _Tp&

    max(const _Tp& __a, const _Tp& __b, _Compare __comp)

    {

      //return __comp(__a, __b) ? __b : __a;

      if (__comp(__a, __b))

	return __b;

      return __a;

    }

  // If _Iterator is a __normal_iterator return its base (a plain pointer,

  // normally) otherwise return it untouched.  See copy, fill, ... 

  template<typename _Iterator>

    struct _Niter_base

    : _Iter_base<_Iterator, __is_normal_iterator<_Iterator>::__value>

    { };

  template<typename _Iterator>

    inline typename _Niter_base<_Iterator>::iterator_type

    __niter_base(_Iterator __it)

    { return std::_Niter_base<_Iterator>::_S_base(__it); }

  // Likewise, for move_iterator.

  template<typename _Iterator>

    struct _Miter_base

    : _Iter_base<_Iterator, __is_move_iterator<_Iterator>::__value>

    { };

  template<typename _Iterator>

    inline typename _Miter_base<_Iterator>::iterator_type

    __miter_base(_Iterator __it)

    { return std::_Miter_base<_Iterator>::_S_base(__it); }

  // All of these auxiliary structs serve two purposes.  (1) Replace

  // calls to copy with memmove whenever possible.  (Memmove, not memcpy,

  // because the input and output ranges are permitted to overlap.)

  // (2) If we're using random access iterators, then write the loop as

  // a for loop with an explicit count.

  template<bool, bool, typename>

    struct __copy_move

    {

      template<typename _II, typename _OI>

        static _OI

        __copy_m(_II __first, _II __last, _OI __result)

        {

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

	    *__result = *__first;

	  return __result;

	}

    };

#if __cplusplus >= 201103L

  template<typename _Category>

    struct __copy_move<true, false, _Category>

    {

      template<typename _II, typename _OI>

        static _OI

        __copy_m(_II __first, _II __last, _OI __result)

        {

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

	    *__result = std::move(*__first);

	  return __result;

	}

    };

#endif

  template<>

    struct __copy_move<false, false, random_access_iterator_tag>

    {

      template<typename _II, typename _OI>

        static _OI

        __copy_m(_II __first, _II __last, _OI __result)

        { 

	  typedef typename iterator_traits<_II>::difference_type _Distance;

	  for(_Distance __n = __last - __first; __n > 0; --__n)

	    {

	      *__result = *__first;

	      ++__first;

	      ++__result;

	    }

	  return __result;

	}

    };

#if __cplusplus >= 201103L

  template<>

    struct __copy_move<true, false, random_access_iterator_tag>

    {

      template<typename _II, typename _OI>

        static _OI

        __copy_m(_II __first, _II __last, _OI __result)

        { 

	  typedef typename iterator_traits<_II>::difference_type _Distance;

	  for(_Distance __n = __last - __first; __n > 0; --__n)

	    {

	      *__result = std::move(*__first);

	      ++__first;

	      ++__result;

	    }

	  return __result;

	}

    };

#endif

  template<bool _IsMove>

    struct __copy_move<_IsMove, true, random_access_iterator_tag>

    {

      template<typename _Tp>

        static _Tp*

        __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)

        {

#if __cplusplus >= 201103L

	  // trivial types can have deleted assignment

	  static_assert( is_copy_assignable<_Tp>::value,

	                 "type is not assignable" );

#endif

	  const ptrdiff_t _Num = __last - __first;

	  if (_Num)

	    __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);

	  return __result + _Num;

	}

    };

  template<bool _IsMove, typename _II, typename _OI>

    inline _OI

    __copy_move_a(_II __first, _II __last, _OI __result)

    {

      typedef typename iterator_traits<_II>::value_type _ValueTypeI;

      typedef typename iterator_traits<_OI>::value_type _ValueTypeO;

      typedef typename iterator_traits<_II>::iterator_category _Category;

      const bool __simple = (__is_trivial(_ValueTypeI)

	                     && __is_pointer<_II>::__value

	                     && __is_pointer<_OI>::__value

			     && __are_same<_ValueTypeI, _ValueTypeO>::__value);

      return std::__copy_move<_IsMove, __simple,

	                      _Category>::__copy_m(__first, __last, __result);

    }

  // Helpers for streambuf iterators (either istream or ostream).

  // NB: avoid including <iosfwd>, relatively large.

  template<typename _CharT>

    struct char_traits;

  template<typename _CharT, typename _Traits>

    class istreambuf_iterator;

  template<typename _CharT, typename _Traits>

    class ostreambuf_iterator;

  template<bool _IsMove, typename _CharT>

    typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 

	     ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type

    __copy_move_a2(_CharT*, _CharT*,

		   ostreambuf_iterator<_CharT, char_traits<_CharT> >);

  template<bool _IsMove, typename _CharT>

    typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 

	     ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type

    __copy_move_a2(const _CharT*, const _CharT*,

		   ostreambuf_iterator<_CharT, char_traits<_CharT> >);

  template<bool _IsMove, typename _CharT>

    typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,

				    _CharT*>::__type

    __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,

		   istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);

  template<bool _IsMove, typename _II, typename _OI>

    inline _OI

    __copy_move_a2(_II __first, _II __last, _OI __result)

    {

      return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),

					     std::__niter_base(__last),

					     std::__niter_base(__result)));

    }

  /**

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

   *  @ingroup mutating_algorithms

   *  @param  __first  An input iterator.

   *  @param  __last   An input iterator.

   *  @param  __result An output iterator.

   *  @return   result + (first - last)

   *

   *  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).  Result may not be contained within

   *  [first,last); the copy_backward function should be used instead.

   *

   *  Note that the end of the output range is permitted to be contained

   *  within [first,last).

  */

  template<typename _II, typename _OI>

    inline _OI

    copy(_II __first, _II __last, _OI __result)

    {

      // concept requirements

      __glibcxx_function_requires(_InputIteratorConcept<_II>)

      __glibcxx_function_requires(_OutputIteratorConcept<_OI,

	    typename iterator_traits<_II>::value_type>)

      __glibcxx_requires_valid_range(__first, __last);

      return (std::__copy_move_a2<__is_move_iterator<_II>::__value>

	      (std::__miter_base(__first), std::__miter_base(__last),

	       __result));

    }

#if __cplusplus >= 201103L

  /**

   *  @brief Moves the range [first,last) into result.

   *  @ingroup mutating_algorithms

   *  @param  __first  An input iterator.

   *  @param  __last   An input iterator.

   *  @param  __result An output iterator.

   *  @return   result + (first - last)

   *

   *  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).  Result may not be contained within

   *  [first,last); the move_backward function should be used instead.

   *

   *  Note that the end of the output range is permitted to be contained

   *  within [first,last).

  */

  template<typename _II, typename _OI>

    inline _OI

    move(_II __first, _II __last, _OI __result)

    {

      // concept requirements

      __glibcxx_function_requires(_InputIteratorConcept<_II>)

      __glibcxx_function_requires(_OutputIteratorConcept<_OI,

	    typename iterator_traits<_II>::value_type>)

      __glibcxx_requires_valid_range(__first, __last);

      return std::__copy_move_a2<true>(std::__miter_base(__first),

				       std::__miter_base(__last), __result);

    }

#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)

#else

#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)

#endif

  template<bool, bool, typename>

    struct __copy_move_backward

    {

      template<typename _BI1, typename _BI2>

        static _BI2

        __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)

        {

	  while (__first != __last)

	    *--__result = *--__last;

	  return __result;

	}

    };

#if __cplusplus >= 201103L

  template<typename _Category>

    struct __copy_move_backward<true, false, _Category>

    {

      template<typename _BI1, typename _BI2>

        static _BI2

        __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)

        {

	  while (__first != __last)

	    *--__result = std::move(*--__last);

	  return __result;

	}

    };

#endif

  template<>

    struct __copy_move_backward<false, false, random_access_iterator_tag>

    {

      template<typename _BI1, typename _BI2>

        static _BI2

        __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)

        {

	  typename iterator_traits<_BI1>::difference_type __n;

	  for (__n = __last - __first; __n > 0; --__n)

	    *--__result = *--__last;

	  return __result;

	}

    };

#if __cplusplus >= 201103L

  template<>

    struct __copy_move_backward<true, false, random_access_iterator_tag>

    {

      template<typename _BI1, typename _BI2>

        static _BI2

        __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)

        {

	  typename iterator_traits<_BI1>::difference_type __n;

	  for (__n = __last - __first; __n > 0; --__n)

	    *--__result = std::move(*--__last);

	  return __result;

	}

    };

#endif

  template<bool _IsMove>

    struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>

    {

      template<typename _Tp>

        static _Tp*

        __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)

        {

#if __cplusplus >= 201103L

	  // trivial types can have deleted assignment

	  static_assert( is_copy_assignable<_Tp>::value,

	                 "type is not assignable" );

#endif

	  const ptrdiff_t _Num = __last - __first;

	  if (_Num)

	    __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);

	  return __result - _Num;

	}

    };

  template<bool _IsMove, typename _BI1, typename _BI2>

    inline _BI2

    __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)

    {

      typedef typename iterator_traits<_BI1>::value_type _ValueType1;

      typedef typename iterator_traits<_BI2>::value_type _ValueType2;

      typedef typename iterator_traits<_BI1>::iterator_category _Category;

      const bool __simple = (__is_trivial(_ValueType1)

	                     && __is_pointer<_BI1>::__value

	                     && __is_pointer<_BI2>::__value

			     && __are_same<_ValueType1, _ValueType2>::__value);

      return std::__copy_move_backward<_IsMove, __simple,

	                               _Category>::__copy_move_b(__first,

								 __last,

								 __result);

    }

  template<bool _IsMove, typename _BI1, typename _BI2>

    inline _BI2

    __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)

    {

      return _BI2(std::__copy_move_backward_a<_IsMove>

		  (std::__niter_base(__first), std::__niter_base(__last),

		   std::__niter_base(__result)));

    }

  /**

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

   *  @ingroup mutating_algorithms

   *  @param  __first  A bidirectional iterator.

   *  @param  __last   A bidirectional iterator.

   *  @param  __result A bidirectional iterator.

   *  @return   result - (first - last)

   *

   *  The function has the same effect as copy, but starts at the end of the

   *  range and works its way to the start, returning the start of the result.

   *  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).

   *

   *  Result may not be in the range (first,last].  Use copy instead.  Note

   *  that the start of the output range may overlap [first,last).

  */

  template<typename _BI1, typename _BI2>

    inline _BI2

    copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)

    {

      // concept requirements

      __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)

      __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)

      __glibcxx_function_requires(_ConvertibleConcept<

	    typename iterator_traits<_BI1>::value_type,

	    typename iterator_traits<_BI2>::value_type>)

      __glibcxx_requires_valid_range(__first, __last);

      return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>

	      (std::__miter_base(__first), std::__miter_base(__last),

	       __result));

    }

#if __cplusplus >= 201103L

  /**

   *  @brief Moves the range [first,last) into result.

   *  @ingroup mutating_algorithms

   *  @param  __first  A bidirectional iterator.

   *  @param  __last   A bidirectional iterator.

   *  @param  __result A bidirectional iterator.

   *  @return   result - (first - last)

   *

   *  The function has the same effect as move, but starts at the end of the

   *  range and works its way to the start, returning the start of the result.

   *  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).

   *

   *  Result may not be in the range (first,last].  Use move instead.  Note

   *  that the start of the output range may overlap [first,last).

  */

  template<typename _BI1, typename _BI2>

    inline _BI2

    move_backward(_BI1 __first, _BI1 __last, _BI2 __result)

    {

      // concept requirements

      __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)

      __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)

      __glibcxx_function_requires(_ConvertibleConcept<

	    typename iterator_traits<_BI1>::value_type,

	    typename iterator_traits<_BI2>::value_type>)

      __glibcxx_requires_valid_range(__first, __last);

      return std::__copy_move_backward_a2<true>(std::__miter_base(__first),

						std::__miter_base(__last),

						__result);

    }

#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)

#else

#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)

#endif

  template<typename _ForwardIterator, typename _Tp>

    inline typename

    __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type

    __fill_a(_ForwardIterator __first, _ForwardIterator __last,

 	     const _Tp& __value)

    {

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

	*__first = __value;

    }

  template<typename _ForwardIterator, typename _Tp>

    inline typename

    __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type

    __fill_a(_ForwardIterator __first, _ForwardIterator __last,

	     const _Tp& __value)

    {

      const _Tp __tmp = __value;

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

	*__first = __tmp;

    }

  // Specialization: for char types we can use memset.

  template<typename _Tp>

    inline typename

    __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type

    __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)

    {

      const _Tp __tmp = __c;

      if (const size_t __len = __last - __first)

	__builtin_memset(__first, static_cast<unsigned char>(__tmp), __len);

    }

  /**

   *  @brief Fills the range [first,last) with copies of value.

   *  @ingroup mutating_algorithms

   *  @param  __first  A forward iterator.

   *  @param  __last   A forward iterator.

   *  @param  __value  A reference-to-const of arbitrary type.

   *  @return   Nothing.

   *

   *  This function fills a range with copies of the same value.  For char

   *  types filling contiguous areas of memory, this becomes an inline call

   *  to @c memset or @c wmemset.

  */

  template<typename _ForwardIterator, typename _Tp>

    inline void

    fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)

    {

      // concept requirements

      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

				  _ForwardIterator>)

      __glibcxx_requires_valid_range(__first, __last);

      std::__fill_a(std::__niter_base(__first), std::__niter_base(__last),

		    __value);

    }

  template<typename _OutputIterator, typename _Size, typename _Tp>

    inline typename

    __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type

    __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)

    {

      for (__decltype(__n + 0) __niter = __n;

	   __niter > 0; --__niter, ++__first)

	*__first = __value;

      return __first;

    }

  template<typename _OutputIterator, typename _Size, typename _Tp>

    inline typename

    __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type

    __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)

    {

      const _Tp __tmp = __value;

      for (__decltype(__n + 0) __niter = __n;

	   __niter > 0; --__niter, ++__first)

      return __first;

    }

  template<typename _Size, typename _Tp>

    inline typename

    __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type

    __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c)

    {

      std::__fill_a(__first, __first + __n, __c);

      return __first + __n;

    }

  /**

   *  @brief Fills the range [first,first+n) with copies of value.

   *  @ingroup mutating_algorithms

   *  @param  __first  An output iterator.

   *  @param  __n      The count of copies to perform.

   *  @param  __value  A reference-to-const of arbitrary type.

   *  @return   The iterator at first+n.

   *

   *  This function fills a range with copies of the same value.  For char

   *  types filling contiguous areas of memory, this becomes an inline call

   *  to @c memset or @ wmemset.

   *

   *  _GLIBCXX_RESOLVE_LIB_DEFECTS

   *  DR 865. More algorithms that throw away information

  */

  template<typename _OI, typename _Size, typename _Tp>

    inline _OI

    fill_n(_OI __first, _Size __n, const _Tp& __value)

    {

      // concept requirements

      __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)

      return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));

    }

  template<bool _BoolType>

    struct __equal

    {

      template<typename _II1, typename _II2>

        static bool

        equal(_II1 __first1, _II1 __last1, _II2 __first2)

        {

	  for (; __first1 != __last1; ++__first1, ++__first2)

	    if (!(*__first1 == *__first2))

	      return false;

	  return true;

	}

    };

  template<>

    struct __equal<true>

    {

      template<typename _Tp>

        static bool

        equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)

        {

	  if (const size_t __len = (__last1 - __first1))

	    return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) * __len);

	  return true;

	}

    };

  template<typename _II1, typename _II2>

    inline bool

    __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)

    {

      typedef typename iterator_traits<_II1>::value_type _ValueType1;

      typedef typename iterator_traits<_II2>::value_type _ValueType2;

      const bool __simple = ((__is_integer<_ValueType1>::__value

			      || __is_pointer<_ValueType1>::__value)

	                     && __is_pointer<_II1>::__value

	                     && __is_pointer<_II2>::__value

			     && __are_same<_ValueType1, _ValueType2>::__value);

      return std::__equal<__simple>::equal(__first1, __last1, __first2);

    }

  template<typename, typename>

    struct __lc_rai

    {

      template<typename _II1, typename _II2>

        static _II1

        __newlast1(_II1, _II1 __last1, _II2, _II2)

        { return __last1; }

      template<typename _II>

        static bool

        __cnd2(_II __first, _II __last)

        { return __first != __last; }

    };

  template<>

    struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>

    {

      template<typename _RAI1, typename _RAI2>

        static _RAI1

        __newlast1(_RAI1 __first1, _RAI1 __last1,

		   _RAI2 __first2, _RAI2 __last2)

        {

	  const typename iterator_traits<_RAI1>::difference_type

	    __diff1 = __last1 - __first1;

	  const typename iterator_traits<_RAI2>::difference_type

	    __diff2 = __last2 - __first2;

	  return __diff2 < __diff1 ? __first1 + __diff2 : __last1;

	}

      template<typename _RAI>

        static bool

        __cnd2(_RAI, _RAI)

        { return true; }

    };

  template<typename _II1, typename _II2, typename _Compare>

    bool

    __lexicographical_compare_impl(_II1 __first1, _II1 __last1,

				   _II2 __first2, _II2 __last2,

				   _Compare __comp)

    {

      typedef typename iterator_traits<_II1>::iterator_category _Category1;

      typedef typename iterator_traits<_II2>::iterator_category _Category2;

      typedef std::__lc_rai<_Category1, _Category2> __rai_type;

      __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);

      for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);

	   ++__first1, ++__first2)

	{

	  if (__comp(__first1, __first2))

	    return true;

	  if (__comp(__first2, __first1))

	    return false;

	}

      return __first1 == __last1 && __first2 != __last2;

    }

  template<bool _BoolType>

    struct __lexicographical_compare

    {

      template<typename _II1, typename _II2>

        static bool __lc(_II1, _II1, _II2, _II2);

    };

  template<bool _BoolType>

    template<typename _II1, typename _II2>

      bool

      __lexicographical_compare<_BoolType>::

      __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)

      {

	return std::__lexicographical_compare_impl(__first1, __last1,

						   __first2, __last2,

					__gnu_cxx::__ops::__iter_less_iter());

      }

  template<>

    struct __lexicographical_compare<true>

    {

      template<typename _Tp, typename _Up>

        static bool

        __lc(const _Tp* __first1, const _Tp* __last1,

	     const _Up* __first2, const _Up* __last2)

	{

	  const size_t __len1 = __last1 - __first1;

	  const size_t __len2 = __last2 - __first2;

	  if (const size_t __len = std::min(__len1, __len2))

	    if (int __result = __builtin_memcmp(__first1, __first2, __len))

	      return __result < 0;

	  return __len1 < __len2;

	}

    };

  template<typename _II1, typename _II2>

    inline bool

    __lexicographical_compare_aux(_II1 __first1, _II1 __last1,

				  _II2 __first2, _II2 __last2)

    {

      typedef typename iterator_traits<_II1>::value_type _ValueType1;

      typedef typename iterator_traits<_II2>::value_type _ValueType2;

      const bool __simple =

	(__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value

	 && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed

	 && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed

	 && __is_pointer<_II1>::__value

	 && __is_pointer<_II2>::__value);

      return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,

							    __first2, __last2);

    }

  template<typename _ForwardIterator, typename _Tp, typename _Compare>

    _ForwardIterator

    __lower_bound(_ForwardIterator __first, _ForwardIterator __last,

		  const _Tp& __val, _Compare __comp)

    {

      typedef typename iterator_traits<_ForwardIterator>::difference_type