Subversion Repositories Kolibri OS

/*

 *

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

 */

/* NOTE: This is an internal header file, included by other STL headers.

 *   You should not attempt to use it directly.

 */

#ifndef __SGI_STL_INTERNAL_ALGOBASE_H

#define __SGI_STL_INTERNAL_ALGOBASE_H

#include 

#ifndef __SGI_STL_INTERNAL_PAIR_H

#include 

#endif

#ifndef _CPP_BITS_TYPE_TRAITS_H

#include 

#endif

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

namespace std

{

// swap and iter_swap

template 

inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*)

{

  _Tp __tmp = *__a;

  *__a = *__b;

  *__b = __tmp;

}

template 

inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b)

{

  // concept requirements

  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>);

  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>);

  __glibcpp_function_requires(_ConvertibleConcept<

        typename iterator_traits<_ForwardIter1>::value_type,

        typename iterator_traits<_ForwardIter2>::value_type>);

  __glibcpp_function_requires(_ConvertibleConcept<

        typename iterator_traits<_ForwardIter2>::value_type,

        typename iterator_traits<_ForwardIter1>::value_type>);

  __iter_swap(__a, __b, __value_type(__a));

}

template 

inline void swap(_Tp& __a, _Tp& __b)

{

  // concept requirements

  __glibcpp_function_requires(_SGIAssignableConcept<_Tp>);

  _Tp __tmp = __a;

  __a = __b;

  __b = __tmp;

}

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

// min and max

#undef min

#undef max

template 

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

  // concept requirements

  __glibcpp_function_requires(_LessThanComparableConcept<_Tp>);

  //return __b < __a ? __b : __a;

  if (__b < __a) return __b; return __a;

}

template 

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

  // concept requirements

  __glibcpp_function_requires(_LessThanComparableConcept<_Tp>);

  //return  __a < __b ? __b : __a;

  if (__a < __b) return __b; return __a;

}

template 

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;

}

template 

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;

}

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

// copy

// All of these auxiliary functions 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 

inline _OutputIter __copy(_InputIter __first, _InputIter __last,

                          _OutputIter __result,

                          input_iterator_tag, _Distance*)

{

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

    *__result = *__first;

  return __result;

}

template 

inline _OutputIter

__copy(_RandomAccessIter __first, _RandomAccessIter __last,

       _OutputIter __result, random_access_iterator_tag, _Distance*)

{

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

    *__result = *__first;

    ++__first;

    ++__result;

  }

  return __result;

}

template 

inline _Tp*

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

{

  memmove(__result, __first, sizeof(_Tp) * (__last - __first));

  return __result + (__last - __first);

}

template 

inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,

                               _OutputIter __result, __false_type)

{

  return __copy(__first, __last, __result,

                __iterator_category(__first),

                __distance_type(__first));

}

template 

inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,

                               _OutputIter __result, __true_type)

{

  return __copy(__first, __last, __result,

                __iterator_category(__first),

                __distance_type(__first));

}

template 

inline _Tp* __copy_aux2(_Tp* __first, _Tp* __last, _Tp* __result,

                        __true_type)

{

  return __copy_trivial(__first, __last, __result);

}

template 

inline _Tp* __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result,

                        __true_type)

{

  return __copy_trivial(__first, __last, __result);

}

template 

inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last,

                              _OutputIter __result, _Tp*)

{

  typedef typename __type_traits<_Tp>::has_trivial_assignment_operator

          _Trivial;

  return __copy_aux2(__first, __last, __result, _Trivial());

}

template

inline _OutputIter __copy_ni2(_InputIter __first, _InputIter __last,

                               _OutputIter __result, __true_type)

{

  return _OutputIter(__copy_aux(__first, __last, __result.base(),

                                __value_type(__first)));

}

template

inline _OutputIter __copy_ni2(_InputIter __first, _InputIter __last,

			      _OutputIter __result, __false_type)

{

  return __copy_aux(__first, __last, __result, __value_type(__first));

}

template

inline _OutputIter __copy_ni1(_InputIter __first, _InputIter __last,

                               _OutputIter __result, __true_type)

{

  typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;

  return __copy_ni2(__first.base(), __last.base(), __result, __Normal());

}

template

inline _OutputIter __copy_ni1(_InputIter __first, _InputIter __last,

                               _OutputIter __result, __false_type)

{

  typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;

  return __copy_ni2(__first, __last, __result, __Normal());

}

template 

inline _OutputIter copy(_InputIter __first, _InputIter __last,

                        _OutputIter __result)

{

  // concept requirements

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);

  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,

        typename iterator_traits<_InputIter>::value_type>);

   typedef typename _Is_normal_iterator<_InputIter>::_Normal __Normal;

   return __copy_ni1(__first, __last, __result, __Normal());

}

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

// copy_backward

template 

          class _Distance>

inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first,

                                           _BidirectionalIter1 __last,

                                           _BidirectionalIter2 __result,

                                           bidirectional_iterator_tag,

                                           _Distance*)

{

  while (__first != __last)

    *--__result = *--__last;

  return __result;

}

template 

inline _BidirectionalIter __copy_backward(_RandomAccessIter __first,

                                          _RandomAccessIter __last,

                                          _BidirectionalIter __result,

                                          random_access_iterator_tag,

                                          _Distance*)

{

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

    *--__result = *--__last;

  return __result;

}

// This dispatch class is a workaround for compilers that do not

// have partial ordering of function templates.  All we're doing is

// creating a specialization so that we can turn a call to copy_backward

// into a memmove whenever possible.

template 

          class _BoolType>

struct __copy_backward_dispatch

{

  typedef typename iterator_traits<_BidirectionalIter1>::iterator_category

          _Cat;

  typedef typename iterator_traits<_BidirectionalIter1>::difference_type

          _Distance;

  static _BidirectionalIter2 copy(_BidirectionalIter1 __first,

                                  _BidirectionalIter1 __last,

                                  _BidirectionalIter2 __result) {

    return __copy_backward(__first, __last, __result, _Cat(), (_Distance*) 0);

  }

};

template 

struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>

{

  static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {

    const ptrdiff_t _Num = __last - __first;

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

    return __result - _Num;

  }

};

template 

struct __copy_backward_dispatch

{

  static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {

    return  __copy_backward_dispatch<_Tp*, _Tp*, __true_type>

      ::copy(__first, __last, __result);

  }

};

template 

inline _BI2 __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result) {

  typedef typename __type_traits::value_type>

                        ::has_trivial_assignment_operator

          _Trivial;

  return __copy_backward_dispatch<_BI1, _BI2, _Trivial>

              ::copy(__first, __last, __result);

}

template 

inline _BI2 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,

                                                   _BI2 __result, __true_type) {

  return _BI2(__copy_backward_aux(__first, __last, __result.base()));

}

template 

inline _BI2 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,

                                                   _BI2 __result, __false_type){

  return __copy_backward_aux(__first, __last, __result);

}

template 

inline _BI2 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,

                                                  _BI2 __result, __true_type) {

  typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;

  return __copy_backward_output_normal_iterator(__first.base(), __last.base(),

                                                __result, __Normal());

}

template 

inline _BI2 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,

                                                  _BI2 __result, __false_type) {

  typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;

  return __copy_backward_output_normal_iterator(__first, __last, __result,

                                                __Normal());

}

template 

inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)

{

  // concept requirements

  __glibcpp_function_requires(_BidirectionalIteratorConcept<_BI1>);

  __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>);

  __glibcpp_function_requires(_ConvertibleConcept<

        typename iterator_traits<_BI1>::value_type,

        typename iterator_traits<_BI2>::value_type>);

  typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal;

  return __copy_backward_input_normal_iterator(__first, __last, __result,

                                               __Normal());

}

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

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

template 

pair<_InputIter, _OutputIter> __copy_n(_InputIter __first, _Size __count,

                                       _OutputIter __result,

                                       input_iterator_tag) {

  for ( ; __count > 0; --__count) {

    *__result = *__first;

    ++__first;

    ++__result;

  }

  return pair<_InputIter, _OutputIter>(__first, __result);

}

template 

inline pair<_RAIter, _OutputIter>

__copy_n(_RAIter __first, _Size __count,

         _OutputIter __result,

         random_access_iterator_tag) {

  _RAIter __last = __first + __count;

  return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));

}

template 

inline pair<_InputIter, _OutputIter>

__copy_n(_InputIter __first, _Size __count, _OutputIter __result) {

  return __copy_n(__first, __count, __result,

                  __iterator_category(__first));

}

template 

inline pair<_InputIter, _OutputIter>

copy_n(_InputIter __first, _Size __count, _OutputIter __result)

{

  // concept requirements

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);

  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,

        typename iterator_traits<_InputIter>::value_type>);

  return __copy_n(__first, __count, __result);

}

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

// fill and fill_n

template 

void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value)

{

  // concept requirements

  __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);

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

    *__first = __value;

}

template 

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

{

  // concept requirements

  __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,_Tp>);

  for ( ; __n > 0; --__n, ++__first)

    *__first = __value;

  return __first;

}

// Specialization: for one-byte types we can use memset.

inline void fill(unsigned char* __first, unsigned char* __last,

                 const unsigned char& __c)

{

  unsigned char __tmp = __c;

  memset(__first, __tmp, __last - __first);

}

inline void fill(signed char* __first, signed char* __last,

                 const signed char& __c)

{

  signed char __tmp = __c;

  memset(__first, static_cast(__tmp), __last - __first);

}

inline void fill(char* __first, char* __last, const char& __c)

{

  char __tmp = __c;

  memset(__first, static_cast(__tmp), __last - __first);

}

template 

inline unsigned char* fill_n(unsigned char* __first, _Size __n,

                             const unsigned char& __c)

{

  fill(__first, __first + __n, __c);

  return __first + __n;

}

template 

inline signed char* fill_n(char* __first, _Size __n,

                           const signed char& __c)

{

  fill(__first, __first + __n, __c);

  return __first + __n;

}

template 

inline char* fill_n(char* __first, _Size __n, const char& __c)

{

  fill(__first, __first + __n, __c);

  return __first + __n;

}

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

// equal and mismatch

template 

pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,

                                        _InputIter1 __last1,

                                        _InputIter2 __first2)

{

  // concept requirements

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);

  __glibcpp_function_requires(_EqualityComparableConcept<

        typename iterator_traits<_InputIter1>::value_type>);

  __glibcpp_function_requires(_EqualityComparableConcept<

        typename iterator_traits<_InputIter2>::value_type>);

  while (__first1 != __last1 && *__first1 == *__first2) {

    ++__first1;

    ++__first2;

  }

  return pair<_InputIter1, _InputIter2>(__first1, __first2);

}

template 

pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,

                                        _InputIter1 __last1,

                                        _InputIter2 __first2,

                                        _BinaryPredicate __binary_pred)

{

  // concept requirements

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);

  while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {

    ++__first1;

    ++__first2;

  }

  return pair<_InputIter1, _InputIter2>(__first1, __first2);

}

template 

inline bool equal(_InputIter1 __first1, _InputIter1 __last1,

                  _InputIter2 __first2)

{

  // concept requirements

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);

  __glibcpp_function_requires(_EqualOpConcept<

        typename iterator_traits<_InputIter1>::value_type,

        typename iterator_traits<_InputIter2>::value_type>);

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

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

      return false;

  return true;

}

template 

inline bool equal(_InputIter1 __first1, _InputIter1 __last1,

                  _InputIter2 __first2, _BinaryPredicate __binary_pred)

{

  // concept requirements

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);

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

    if (!__binary_pred(*__first1, *__first2))

      return false;

  return true;

}

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

// lexicographical_compare and lexicographical_compare_3way.

// (the latter is not part of the C++ standard.)

template 

bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,

                             _InputIter2 __first2, _InputIter2 __last2)

{

  // concept requirements

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);

  __glibcpp_function_requires(_LessThanComparableConcept<

        typename iterator_traits<_InputIter1>::value_type>);

  __glibcpp_function_requires(_LessThanComparableConcept<

        typename iterator_traits<_InputIter2>::value_type>);

  for ( ; __first1 != __last1 && __first2 != __last2

        ; ++__first1, ++__first2) {

    if (*__first1 < *__first2)

      return true;

    if (*__first2 < *__first1)

      return false;

  }

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

}

template 

bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,

                             _InputIter2 __first2, _InputIter2 __last2,

                             _Compare __comp)

{

  // concept requirements

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);

  for ( ; __first1 != __last1 && __first2 != __last2

        ; ++__first1, ++__first2) {

    if (__comp(*__first1, *__first2))

      return true;

    if (__comp(*__first2, *__first1))

      return false;

  }

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

}

inline bool

lexicographical_compare(const unsigned char* __first1,

                        const unsigned char* __last1,

                        const unsigned char* __first2,

                        const unsigned char* __last2)

{

  const size_t __len1 = __last1 - __first1;

  const size_t __len2 = __last2 - __first2;

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

  return __result != 0 ? __result < 0 : __len1 < __len2;

}

inline bool lexicographical_compare(const char* __first1, const char* __last1,

                                    const char* __first2, const char* __last2)

{

#if CHAR_MAX == SCHAR_MAX

  return lexicographical_compare((const signed char*) __first1,

                                 (const signed char*) __last1,

                                 (const signed char*) __first2,

                                 (const signed char*) __last2);

#else /* CHAR_MAX == SCHAR_MAX */

  return lexicographical_compare((const unsigned char*) __first1,

                                 (const unsigned char*) __last1,

                                 (const unsigned char*) __first2,

                                 (const unsigned char*) __last2);

#endif /* CHAR_MAX == SCHAR_MAX */

}

template 

int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,

                                   _InputIter2 __first2, _InputIter2 __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 = 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

}

template 

int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,

                                 _InputIter2 __first2, _InputIter2 __last2)

{

  // concept requirements

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);

  __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);

  __glibcpp_function_requires(_LessThanComparableConcept<

        typename iterator_traits<_InputIter1>::value_type>);

  __glibcpp_function_requires(_LessThanComparableConcept<

        typename iterator_traits<_InputIter2>::value_type>);

  return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);

}

} // namespace std

#endif /* __SGI_STL_INTERNAL_ALGOBASE_H */

// Local Variables:

// mode:C++

// End: