// Core algorithmic facilities -*- C++ -*-
	
	// Copyright (C) 2001-2013 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
	
	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>
	    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>
	    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>
	    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>
	    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)
	        {
		  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)
	        {
		  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;
	      __builtin_memset(__first, static_cast<unsigned char>(__tmp),
			       __last - __first);
	    }
	
	  /**
	   *  @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)
		*__first = __tmp;
	      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)
	        {
		  return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
					   * (__last1 - __first1));
		}
	    };
	
	  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<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)
	      {
		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 (*__first1 < *__first2)
		      return true;
		    if (*__first2 < *__first1)
		      return false;
		  }
		return __first1 == __last1 && __first2 != __last2;
	      }
	
	  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;
		  const int __result = __builtin_memcmp(__first1, __first2,
							std::min(__len1, __len2));
		  return __result != 0 ? __result < 0 : __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);
	    }
	
	  /**
	   *  @brief Finds the first position in which @a val could be inserted
	   *         without changing the ordering.
	   *  @param  __first   An iterator.
	   *  @param  __last    Another iterator.
	   *  @param  __val     The search term.
	   *  @return         An iterator pointing to the first element <em>not less
	   *                  than</em> @a val, or end() if every element is less than 
	   *                  @a val.
	   *  @ingroup binary_search_algorithms
	  */
	  template<typename _ForwardIterator, typename _Tp>
	    _ForwardIterator
	    lower_bound(_ForwardIterator __first, _ForwardIterator __last,
			const _Tp& __val)
	    {
	#ifdef _GLIBCXX_CONCEPT_CHECKS
	      typedef typename iterator_traits<_ForwardIterator>::value_type
		_ValueType;
	#endif
	      typedef typename iterator_traits<_ForwardIterator>::difference_type
		_DistanceType;
	
	      // concept requirements
	      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
	      __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
	      __glibcxx_requires_partitioned_lower(__first, __last, __val);
	
	      _DistanceType __len = std::distance(__first, __last);
	
	      while (__len > 0)
		{
		  _DistanceType __half = __len >> 1;
		  _ForwardIterator __middle = __first;
		  std::advance(__middle, __half);
		  if (*__middle < __val)
		    {
		      __first = __middle;
		      ++__first;
		      __len = __len - __half - 1;
		    }
		  else
		    __len = __half;
		}
	      return __first;
	    }
	
	  /// This is a helper function for the sort routines and for random.tcc.
	  //  Precondition: __n > 0.
	  inline _GLIBCXX_CONSTEXPR int
	  __lg(int __n)
	  { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
	
	  inline _GLIBCXX_CONSTEXPR unsigned
	  __lg(unsigned __n)
	  { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
	
	  inline _GLIBCXX_CONSTEXPR long
	  __lg(long __n)
	  { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
	
	  inline _GLIBCXX_CONSTEXPR unsigned long
	  __lg(unsigned long __n)
	  { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
	
	  inline _GLIBCXX_CONSTEXPR long long
	  __lg(long long __n)
	  { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
	
	  inline _GLIBCXX_CONSTEXPR unsigned long long
	  __lg(unsigned long long __n)
	  { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
	
	_GLIBCXX_END_NAMESPACE_VERSION
	
	_GLIBCXX_BEGIN_NAMESPACE_ALGO
	
	  /**
	   *  @brief Tests a range for element-wise equality.
	   *  @ingroup non_mutating_algorithms
	   *  @param  __first1  An input iterator.
	   *  @param  __last1   An input iterator.
	   *  @param  __first2  An input iterator.
	   *  @return   A boolean true or false.
	   *
	   *  This compares the elements of two ranges using @c == and returns true or
	   *  false depending on whether all of the corresponding elements of the
	   *  ranges are equal.
	  */
	  template<typename _II1, typename _II2>
	    inline bool
	    equal(_II1 __first1, _II1 __last1, _II2 __first2)
	    {
	      // concept requirements
	      __glibcxx_function_requires(_InputIteratorConcept<_II1>)
	      __glibcxx_function_requires(_InputIteratorConcept<_II2>)
	      __glibcxx_function_requires(_EqualOpConcept<
		    typename iterator_traits<_II1>::value_type,
		    typename iterator_traits<_II2>::value_type>)
	      __glibcxx_requires_valid_range(__first1, __last1);
	
	      return std::__equal_aux(std::__niter_base(__first1),
				      std::__niter_base(__last1),
				      std::__niter_base(__first2));
	    }
	
	  /**
	   *  @brief Tests a range for element-wise equality.
	   *  @ingroup non_mutating_algorithms
	   *  @param  __first1  An input iterator.
	   *  @param  __last1   An input iterator.
	   *  @param  __first2  An input iterator.
	   *  @param __binary_pred A binary predicate @link functors
	   *                  functor@endlink.
	   *  @return         A boolean true or false.
	   *
	   *  This compares the elements of two ranges using the binary_pred
	   *  parameter, and returns true or
	   *  false depending on whether all of the corresponding elements of the
	   *  ranges are equal.
	  */
	  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
	    inline bool
	    equal(_IIter1 __first1, _IIter1 __last1,
		  _IIter2 __first2, _BinaryPredicate __binary_pred)
	    {
	      // concept requirements
	      __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
	      __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
	      __glibcxx_requires_valid_range(__first1, __last1);
	
	      for (; __first1 != __last1; ++__first1, ++__first2)
		if (!bool(__binary_pred(*__first1, *__first2)))
		  return false;
	      return true;
	    }
	
	  /**
	   *  @brief Performs @b dictionary comparison on ranges.
	   *  @ingroup sorting_algorithms
	   *  @param  __first1  An input iterator.
	   *  @param  __last1   An input iterator.
	   *  @param  __first2  An input iterator.
	   *  @param  __last2   An input iterator.
	   *  @return   A boolean true or false.
	   *
	   *  <em>Returns true if the sequence of elements defined by the range
	   *  [first1,last1) is lexicographically less than the sequence of elements
	   *  defined by the range [first2,last2).  Returns false otherwise.</em>
	   *  (Quoted from [25.3.8]/1.)  If the iterators are all character pointers,
	   *  then this is an inline call to @c memcmp.
	  */
	  template<typename _II1, typename _II2>
	    inline bool
	    lexicographical_compare(_II1 __first1, _II1 __last1,
				    _II2 __first2, _II2 __last2)
	    {
	#ifdef _GLIBCXX_CONCEPT_CHECKS
	      // concept requirements
	      typedef typename iterator_traits<_II1>::value_type _ValueType1;
	      typedef typename iterator_traits<_II2>::value_type _ValueType2;
	#endif
	      __glibcxx_function_requires(_InputIteratorConcept<_II1>)
	      __glibcxx_function_requires(_InputIteratorConcept<_II2>)
	      __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
	      __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
	      __glibcxx_requires_valid_range(__first1, __last1);
	      __glibcxx_requires_valid_range(__first2, __last2);
	
	      return std::__lexicographical_compare_aux(std::__niter_base(__first1),
							std::__niter_base(__last1),
							std::__niter_base(__first2),
							std::__niter_base(__last2));
	    }
	
	  /**
	   *  @brief Performs @b dictionary comparison on ranges.
	   *  @ingroup sorting_algorithms
	   *  @param  __first1  An input iterator.
	   *  @param  __last1   An input iterator.
	   *  @param  __first2  An input iterator.
	   *  @param  __last2   An input iterator.
	   *  @param  __comp  A @link comparison_functors comparison functor@endlink.
	   *  @return   A boolean true or false.
	   *
	   *  The same as the four-parameter @c lexicographical_compare, but uses the
	   *  comp parameter instead of @c <.
	  */
	  template<typename _II1, typename _II2, typename _Compare>
	    bool
	    lexicographical_compare(_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;
	
	      // concept requirements
	      __glibcxx_function_requires(_InputIteratorConcept<_II1>)
	      __glibcxx_function_requires(_InputIteratorConcept<_II2>)
	      __glibcxx_requires_valid_range(__first1, __last1);
	      __glibcxx_requires_valid_range(__first2, __last2);
	
	      __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;
	    }
	
	  /**
	   *  @brief Finds the places in ranges which don't match.
	   *  @ingroup non_mutating_algorithms
	   *  @param  __first1  An input iterator.
	   *  @param  __last1   An input iterator.
	   *  @param  __first2  An input iterator.
	   *  @return   A pair of iterators pointing to the first mismatch.
	   *
	   *  This compares the elements of two ranges using @c == and returns a pair
	   *  of iterators.  The first iterator points into the first range, the
	   *  second iterator points into the second range, and the elements pointed
	   *  to by the iterators are not equal.
	  */
	  template<typename _InputIterator1, typename _InputIterator2>
	    pair<_InputIterator1, _InputIterator2>
	    mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
		     _InputIterator2 __first2)
	    {
	      // concept requirements
	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
	      __glibcxx_function_requires(_EqualOpConcept<
		    typename iterator_traits<_InputIterator1>::value_type,
		    typename iterator_traits<_InputIterator2>::value_type>)
	      __glibcxx_requires_valid_range(__first1, __last1);
	
	      while (__first1 != __last1 && *__first1 == *__first2)
	        {
		  ++__first1;
		  ++__first2;
	        }
	      return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
	    }
	
	  /**
	   *  @brief Finds the places in ranges which don't match.
	   *  @ingroup non_mutating_algorithms
	   *  @param  __first1  An input iterator.
	   *  @param  __last1   An input iterator.
	   *  @param  __first2  An input iterator.
	   *  @param __binary_pred A binary predicate @link functors
	   *         functor@endlink.
	   *  @return   A pair of iterators pointing to the first mismatch.
	   *
	   *  This compares the elements of two ranges using the binary_pred
	   *  parameter, and returns a pair
	   *  of iterators.  The first iterator points into the first range, the
	   *  second iterator points into the second range, and the elements pointed
	   *  to by the iterators are not equal.
	  */
	  template<typename _InputIterator1, typename _InputIterator2,
		   typename _BinaryPredicate>
	    pair<_InputIterator1, _InputIterator2>
	    mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
		     _InputIterator2 __first2, _BinaryPredicate __binary_pred)
	    {
	      // concept requirements
	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
	      __glibcxx_requires_valid_range(__first1, __last1);
	
	      while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
	        {
		  ++__first1;
		  ++__first2;
	        }
	      return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
	    }
	
	_GLIBCXX_END_NAMESPACE_ALGO
	} // namespace std
	
	// NB: This file is included within many other C++ includes, as a way
	// of getting the base algorithms. So, make sure that parallel bits
	// come in too if requested. 
	#ifdef _GLIBCXX_PARALLEL
	# include <parallel/algobase.h>
	#endif
	
	#endif