/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Copyright (c) 1997
 * Moscow Center for SPARC Technology
 *
 * Copyright (c) 1999
 * Boris Fomitchev
 *
 * This material is provided "as is", with absolutely no warranty expressed
 * or implied. Any use is at your own risk.
 *
 * Permission to use or copy this software for any purpose is hereby granted
 * without fee, provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 *
 */

/* NOTE: This is an internal header file, included by other STL headers.
 *   You should not attempt to use it directly.
 */

#ifndef _STLP_INTERNAL_UNINITIALIZED_H
#define _STLP_INTERNAL_UNINITIALIZED_H

#ifndef _STLP_INTERNAL_CSTRING
#  include <stl/_cstring.h>
#endif

#ifndef _STLP_INTERNAL_ALGOBASE_H
#  include <stl/_algobase.h>
#endif

#ifndef _STLP_INTERNAL_CONSTRUCT_H
#  include <stl/_construct.h>
#endif

_STLP_BEGIN_NAMESPACE

_STLP_MOVE_TO_PRIV_NAMESPACE

// uninitialized_copy

template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __ucopy(_InputIter __first, _InputIter __last,
                           _OutputIter __result, _Distance*) {
  _OutputIter __cur = __result;
  _STLP_TRY {
    for ( ; __first != __last; ++__first, ++__cur)
      _Param_Construct(&*__cur, *__first);
    return __cur;
  }
  _STLP_UNWIND(_STLP_STD::_Destroy_Range(__result, __cur))
  _STLP_RET_AFTER_THROW(__cur)
}

template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __ucopy(_InputIter __first, _InputIter __last,
                           _OutputIter __result, const input_iterator_tag &, _Distance* __d)
{ return __ucopy(__first, __last, __result, __d); }

#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __ucopy(_InputIter __first, _InputIter __last,
                           _OutputIter __result, const forward_iterator_tag &, _Distance* __d)
{ return __ucopy(__first, __last, __result, __d); }

template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __ucopy(_InputIter __first, _InputIter __last,
                           _OutputIter __result, const bidirectional_iterator_tag &, _Distance* __d)
{ return __ucopy(__first, __last, __result, __d); }
#endif

template <class _RandomAccessIter, class _OutputIter, class _Distance>
inline _OutputIter __ucopy(_RandomAccessIter __first, _RandomAccessIter __last,
                           _OutputIter __result, const random_access_iterator_tag &, _Distance*) {
  _OutputIter __cur = __result;
  _STLP_TRY {
    for (_Distance __n = __last - __first; __n > 0; --__n) {
      _Param_Construct(&*__cur, *__first);
      ++__first;
      ++__cur;
    }
    return __cur;
  }
  _STLP_UNWIND(_STLP_STD::_Destroy_Range(__result, __cur))
  _STLP_RET_AFTER_THROW(__cur)
}

//Used internaly
template <class _RandomAccessIter, class _OutputIter>
inline _OutputIter __ucopy(_RandomAccessIter __first, _RandomAccessIter __last, _OutputIter __result)
{ return __ucopy(__first, __last, __result, random_access_iterator_tag(), (ptrdiff_t*)0); }

inline void*
__ucopy_trivial(const void* __first, const void* __last, void* __result) {
  //dums: this version can use memcpy (__copy_trivial can't)
  return (__last == __first) ? __result :
    ((char*)memcpy(__result, __first, ((const char*)__last - (const char*)__first))) +
    ((const char*)__last - (const char*)__first);
}

template <class _InputIter, class _OutputIter>
inline _OutputIter __ucopy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result,
                                const __false_type& /*TrivialUCopy*/)
{ return __ucopy(__first, __last, __result, random_access_iterator_tag(), (ptrdiff_t*)0); }

template <class _InputIter, class _OutputIter>
inline _OutputIter __ucopy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result,
                                const __true_type& /*TrivialUCopy*/) {
  // we know they all pointers, so this cast is OK
  //  return (_OutputIter)__copy_trivial(&(*__first), &(*__last), &(*__result));
  return (_OutputIter)__ucopy_trivial(__first, __last, __result);
}

template <class _InputIter, class _OutputIter>
inline _OutputIter __ucopy_aux(_InputIter __first, _InputIter __last, _OutputIter __result,
                               const __true_type& /*BothPtrType*/) {
  return __ucopy_ptrs(__first, __last, __result,
                      _UseTrivialUCopy(_STLP_VALUE_TYPE(__first, _InputIter),
                                       _STLP_VALUE_TYPE(__result, _OutputIter))._Answer());
}

template <class _InputIter, class _OutputIter>
inline _OutputIter __ucopy_aux(_InputIter __first, _InputIter __last, _OutputIter __result,
                               const __false_type& /*BothPtrType*/) {
  return __ucopy(__first, __last, __result,
                 _STLP_ITERATOR_CATEGORY(__first, _InputIter),
                 _STLP_DISTANCE_TYPE(__first, _InputIter));
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _InputIter, class _ForwardIter>
inline _ForwardIter
uninitialized_copy(_InputIter __first, _InputIter __last, _ForwardIter __result)
{ return _STLP_PRIV __ucopy_aux(__first, __last, __result, _BothPtrType< _InputIter, _ForwardIter>::_Answer()); }

inline char*
uninitialized_copy(const char* __first, const char* __last, char* __result)
{ return  (char*)_STLP_PRIV __ucopy_trivial(__first, __last, __result); }

#  if defined (_STLP_HAS_WCHAR_T) // dwa 8/15/97
inline wchar_t*
uninitialized_copy(const wchar_t* __first, const wchar_t* __last, wchar_t* __result)
{ return  (wchar_t*)_STLP_PRIV __ucopy_trivial (__first, __last, __result); }
#  endif

// uninitialized_copy_n (not part of the C++ standard)
_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _InputIter, class _Size, class _ForwardIter>
_STLP_INLINE_LOOP
pair<_InputIter, _ForwardIter>
__ucopy_n(_InputIter __first, _Size __count, _ForwardIter __result,
          const input_iterator_tag &) {
  _ForwardIter __cur = __result;
  _STLP_TRY {
    for ( ; __count > 0 ; --__count, ++__first, ++__cur)
      _Param_Construct(&*__cur, *__first);
    return pair<_InputIter, _ForwardIter>(__first, __cur);
  }
  _STLP_UNWIND(_STLP_STD::_Destroy_Range(__result, __cur))
  _STLP_RET_AFTER_THROW((pair<_InputIter, _ForwardIter>(__first, __cur)))
}

#  if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
template <class _InputIter, class _Size, class _ForwardIterator>
inline pair<_InputIter, _ForwardIterator>
__ucopy_n(_InputIter __first, _Size __count,
                       _ForwardIterator __result,
                       const forward_iterator_tag &)
{ return __ucopy_n(__first, __count, __result, input_iterator_tag()); }

template <class _InputIter, class _Size, class _ForwardIterator>
inline pair<_InputIter, _ForwardIterator>
__ucopy_n(_InputIter __first, _Size __count,
                       _ForwardIterator __result,
                       const bidirectional_iterator_tag &)
{ return __ucopy_n(__first, __count, __result, input_iterator_tag()); }
#  endif

template <class _RandomAccessIter, class _Size, class _ForwardIter>
inline pair<_RandomAccessIter, _ForwardIter>
__ucopy_n(_RandomAccessIter __first, _Size __count, _ForwardIter __result,
                       const random_access_iterator_tag &) {
  _RandomAccessIter __last = __first + __count;
  return pair<_RandomAccessIter, _ForwardIter>(__last, uninitialized_copy(__first, __last, __result));
}

// This is used internally in <rope> , which is extension itself.
template <class _InputIter, class _Size, class _ForwardIter>
inline pair<_InputIter, _ForwardIter>
__ucopy_n(_InputIter __first, _Size __count, _ForwardIter __result)
{ return _STLP_PRIV __ucopy_n(__first, __count, __result, _STLP_ITERATOR_CATEGORY(__first, _InputIter)); }

#if !defined (_STLP_NO_EXTENSIONS)

_STLP_MOVE_TO_STD_NAMESPACE

template <class _InputIter, class _Size, class _ForwardIter>
inline pair<_InputIter, _ForwardIter>
uninitialized_copy_n(_InputIter __first, _Size __count, _ForwardIter __result)
{ return _STLP_PRIV __ucopy_n(__first, __count, __result); }

_STLP_MOVE_TO_PRIV_NAMESPACE

#endif

template <class _ForwardIter, class _Tp, class _Distance>
inline void __ufill(_ForwardIter __first, _ForwardIter __last, const _Tp& __x, _Distance*) {
  _ForwardIter __cur = __first;
  _STLP_TRY {
    for ( ; __cur != __last; ++__cur)
      _Param_Construct(&*__cur, __x);
  }
  _STLP_UNWIND(_STLP_STD::_Destroy_Range(__first, __cur))
}

template <class _ForwardIter, class _Tp, class _Distance>
inline void __ufill(_ForwardIter __first, _ForwardIter __last,
                    const _Tp& __x, const input_iterator_tag &, _Distance* __d)
{ __ufill(__first, __last, __x, __d); }

#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
template <class _ForwardIter, class _Tp, class _Distance>
inline void __ufill(_ForwardIter __first, _ForwardIter __last,
                    const _Tp& __x, const forward_iterator_tag &, _Distance* __d)
{ __ufill(__first, __last, __x, __d); }

template <class _ForwardIter, class _Tp, class _Distance>
inline void __ufill(_ForwardIter __first, _ForwardIter __last,
                    const _Tp& __x, const bidirectional_iterator_tag &, _Distance* __d)
{ __ufill(__first, __last, __x, __d); }
#endif

template <class _ForwardIter, class _Tp, class _Distance>
inline void __ufill(_ForwardIter __first, _ForwardIter __last,
                    const _Tp& __x, const random_access_iterator_tag &, _Distance*) {
  _ForwardIter __cur = __first;
  _STLP_TRY {
    for (_Distance __n = __last - __first; __n > 0; --__n, ++__cur)
      _Param_Construct(&*__cur, __x);
  }
  _STLP_UNWIND(_STLP_STD::_Destroy_Range(__first, __cur))
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _ForwardIter, class _Tp>
inline void uninitialized_fill(_ForwardIter __first, _ForwardIter __last,  const _Tp& __x) {
  _STLP_PRIV __ufill(__first, __last, __x,
                     _STLP_ITERATOR_CATEGORY(__first, _ForwardIter),
                     _STLP_DISTANCE_TYPE(__first, _ForwardIter));
}

// Specialization: for one-byte types we can use memset.
inline void uninitialized_fill(unsigned char* __first, unsigned char* __last,
                               const unsigned char& __val) {
  unsigned char __tmp = __val;
  memset(__first, __tmp, __last - __first);
}
#if !defined (_STLP_NO_SIGNED_BUILTINS)
inline void uninitialized_fill(signed char* __first, signed char* __last,
                               const signed char& __val) {
  signed char __tmp = __val;
  memset(__first, __STATIC_CAST(unsigned char,__tmp), __last - __first);
}
#endif
inline void uninitialized_fill(char* __first, char* __last, const char& __val) {
  char __tmp = __val;
  memset(__first, __STATIC_CAST(unsigned char,__tmp), __last - __first);
}

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __ufill_n(_ForwardIter __first, _Size __n, const _Tp& __x) {
  _ForwardIter __cur = __first;
  _STLP_TRY {
    for ( ; __n > 0; --__n, ++__cur)
      _Param_Construct(&*__cur, __x);
  }
  _STLP_UNWIND(_STLP_STD::_Destroy_Range(__first, __cur))
  return __cur;
}

template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __ufill_n(_ForwardIter __first, _Size __n, const _Tp& __x,
                              const input_iterator_tag &)
{ return __ufill_n(__first, __n, __x); }

#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __ufill_n(_ForwardIter __first, _Size __n, const _Tp& __x,
                              const forward_iterator_tag &)
{ return __ufill_n(__first, __n, __x); }

template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __ufill_n(_ForwardIter __first, _Size __n, const _Tp& __x,
                              const bidirectional_iterator_tag &)
{ return __ufill_n(__first, __n, __x); }
#endif

template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x) {
  _ForwardIter __last = __first + __n;
  __ufill(__first, __last, __x, random_access_iterator_tag(), (ptrdiff_t*)0);
  return __last;
}

template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __ufill_n(_ForwardIter __first, _Size __n, const _Tp& __x,
                              const random_access_iterator_tag &)
{ return __uninitialized_fill_n(__first, __n, __x); }

/* __uninitialized_init is an internal algo to init a range with a value
 * built using default constructor. It is only called with pointer as
 * iterator.
 */
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uinit_aux_aux(_ForwardIter __first, _Size __n, const _Tp& __val,
                                    const __false_type& /*_HasDefaultZero*/)
{ return __uninitialized_fill_n(__first, __n, __val); }

template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uinit_aux_aux(_ForwardIter __first, _Size __n, const _Tp& /* __val */,
                                    const __true_type& /*_HasDefaultZero*/) {
  memset((unsigned char*)__first, 0, __n * sizeof(_Tp));
  return __first + __n;
}

template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uinit_aux(_ForwardIter __first, _Size __n, const _Tp&,
                                const __true_type& /*_TrivialInit*/)
{ return __first + __n; }

template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uinit_aux(_ForwardIter __first, _Size __n, const _Tp& __val,
                                const __false_type& /*_TrivialInit*/)
{ return __uinit_aux_aux(__first, __n, __val, _HasDefaultZeroValue(__first)._Answer()); }

template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uninitialized_init(_ForwardIter __first, _Size __n, const _Tp& __val)
{ return __uinit_aux(__first, __n, __val, _UseTrivialInit(__first)._Answer()); }

_STLP_MOVE_TO_STD_NAMESPACE

template <class _ForwardIter, class _Size, class _Tp>
inline void
uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x)
{ _STLP_PRIV __ufill_n(__first, __n, __x, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); }

// Extensions: __uninitialized_copy_copy, __uninitialized_copy_fill,
// __uninitialized_fill_copy.

// __uninitialized_copy_copy
// Copies [first1, last1) into [result, result + (last1 - first1)), and
//  copies [first2, last2) into
//  [result + (last1 - first1), result + (last1 - first1) + (last2 - first2)).

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _InputIter1, class _InputIter2, class _ForwardIter>
inline _ForwardIter
__uninitialized_copy_copy(_InputIter1 __first1, _InputIter1 __last1,
                          _InputIter2 __first2, _InputIter2 __last2,
                          _ForwardIter __result) {
  _ForwardIter __new_result = uninitialized_copy(__first1, __last1, __result);
  _STLP_TRY {
    return uninitialized_copy(__first2, __last2, __new_result);
  }
  _STLP_UNWIND(_STLP_STD::_Destroy_Range(__result, __new_result))
  _STLP_RET_AFTER_THROW(__result)
}

// __uninitialized_fill_copy
// Fills [result, mid) with x, and copies [first, last) into
//  [mid, mid + (last - first)).
template <class _ForwardIter, class _Tp, class _InputIter>
inline _ForwardIter
__uninitialized_fill_copy(_ForwardIter __result, _ForwardIter __mid, const _Tp& __x,
                          _InputIter __first, _InputIter __last) {
  uninitialized_fill(__result, __mid, __x);
  _STLP_TRY {
    return uninitialized_copy(__first, __last, __mid);
  }
  _STLP_UNWIND(_STLP_STD::_Destroy_Range(__result, __mid))
  _STLP_RET_AFTER_THROW(__result)
}

// __uninitialized_copy_fill
// Copies [first1, last1) into [first2, first2 + (last1 - first1)), and
//  fills [first2 + (last1 - first1), last2) with x.
template <class _Iter, class _Tp>
inline void
__uninitialized_copy_fill(_Iter __first1, _Iter __last1, _Iter __first2, _Iter __last2,
                          const _Tp& __x) {
  _Iter __mid2 = uninitialized_copy(__first1, __last1, __first2);
  _STLP_TRY {
    uninitialized_fill(__mid2, __last2, __x);
  }
  _STLP_UNWIND(_STLP_STD::_Destroy_Range(__first2, __mid2))
}

/* __uninitialized_move:
 * This function is used internaly and only with pointers as iterators.
 */
template <class _InputIter, class _ForwardIter, class _TrivialUCpy>
inline _ForwardIter
__uninitialized_move(_InputIter __first, _InputIter __last, _ForwardIter __result,
                     _TrivialUCpy __trivial_ucpy, const __false_type& /*_Movable*/)
{ return __ucopy_ptrs(__first, __last, __result, __trivial_ucpy); }

template <class _InputIter, class _ForwardIter, class _TrivialUCpy>
_STLP_INLINE_LOOP
_ForwardIter
__uninitialized_move(_InputIter __first, _InputIter __last, _ForwardIter __result,
                     _TrivialUCpy , const __true_type& /*_Movable*/) {
  //Move constructor should not throw so we do not need to take care of exceptions here.
  for (ptrdiff_t __n = __last - __first ; __n > 0; --__n) {
    _Move_Construct(&*__result, *__first);
    ++__first; ++__result;
  }
  return __result;
}

_STLP_MOVE_TO_STD_NAMESPACE

_STLP_END_NAMESPACE

#endif /* _STLP_INTERNAL_UNINITIALIZED_H */

// Local Variables:
// mode:C++
// End: