// -*- C++ -*-
#ifndef __STD_MEMORY 
#define __STD_MEMORY

// Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved.
/***************************************************************************
 *
 * memory - declarations for the Standard Library memory implementation
 *
 ***************************************************************************
 *
 * 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) 1994-1999 Rogue Wave Software, Inc.  All Rights Reserved.
 *
 * This computer software is owned by Rogue Wave Software, Inc. and is
 * protected by U.S. copyright laws and other laws and by international
 * treaties.  This computer software is furnished by Rogue Wave Software,
 * Inc. pursuant to a written license agreement and may be used, copied,
 * transmitted, and stored only in accordance with the terms of such
 * license and with the inclusion of the above copyright notice.  This
 * computer software or any other copies thereof may not be provided or
 * otherwise made available to any other person.
 *
 * U.S. Government Restricted Rights.  This computer software is provided
 * with Restricted Rights.  Use, duplication, or disclosure by the
 * Government is subject to restrictions as set forth in subparagraph (c)
 * (1) (ii) of The Rights in Technical Data and Computer Software clause
 * at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the
 * Commercial Computer Software � Restricted Rights at 48 CFR 52.227-19,
 * as applicable.  Manufacturer is Rogue Wave Software, Inc., 5500
 * Flatiron Parkway, Boulder, Colorado 80301 USA.
 *
 **************************************************************************/ 

#include <stdcomp.h>

#ifndef _RWSTD_NO_NEW_HEADER
#include <cstddef>
#include <cstdlib>
#include <climits>
#else
#include <stddef.h>
#include <stdlib.h>
#include <limits.h>

#endif //_RWSTD_NO_NEW_HEADER

#include <new>
#include <rw/iterator>
#include <utility>
#include <rw/rwstderr.h>
#include <rw/stdmutex.h>


//
// Turn off the warnings under the MSVC compiler that
// say 'bool reserved for future use' and turn off warnings
// that say 'debug information truncated to 256 characters'
//
#ifdef _RWSTD_MSVC_BOOL_WARNING
#pragma warning ( disable : 4237 )
#endif

#ifdef _RWSTD_NO_NEW_DECL
extern void _RWSTDExportFunc(*) operator new(size_t size, void* ptr);
#endif

#ifdef _RWSTD_NO_NEW_HEADER
#include <exception>
#endif

#pragma disable_warn

#ifndef _RWSTD_NO_NAMESPACE
namespace __rwstd {
#endif

//
// Template used for empty base optimization
//
  template <class _Tt , class _Base>
  class __rw_basis : public _Base
  {
    _Tt __data_;
  public:
    __rw_basis(const __rw_basis& b) : _Base(b), __data_(b.__data_) {;}
    __rw_basis(const _Tt& t, const _Base& b) : _Base(b), __data_(t) {;}
    __rw_basis(int t, const _Base& b) : _Base(b), __data_((_Tt)t) {;}   // TEMP
    __rw_basis operator=(const _Tt& t) { __data_ = t; return *this; }
    __rw_basis operator=(int t) { __data_ = (_Tt)t; return *this; }   // TEMP
    __rw_basis operator=(const __rw_basis& r) 
    { __data_ = r.__data_; return *this; }
    __rw_basis operator=(const _Base& b) 
    { *this = __rw_basis<_Tt,_Base>(__data_,b); return *this; }
    operator _Tt() { return __data_; }
    _Tt data() const { return __data_; }
  };

// Default buffer size for containers.    
#ifndef _RWSTD_CONTAINER_BUFFER_SIZE 
#define _RWSTD_CONTAINER_BUFFER_SIZE 64
#endif

#ifndef _RWSTD_VECTOR_CONST_ENLARGE
  // This function returns a suggested new capacity for a container needing
  // more room; see stddefs.h for an explanation of these macro parameters.
  // Return new buffer size in bytes.
  // Third parameter not used.
  template <class _Tt, class _Size>
  inline _Size __rw_allocation_size(_Tt*,_Size cursize, _Size)
  {
    _Size cap = _RWSTD_STATIC_CAST(_Size, cursize * _RWSTD_NEW_CAPACITY_RATIO);
    _Size sz = (cursize += _RWSTD_MINIMUM_NEW_CAPACITY) > cap ? cursize : cap;
    return sz;
  }
#else
  // Increment the buffer size by a set amount
  // indicated by __delta (if __delta is 0 then
  // get delta size from _RWSTD_CONTAINER_BUFFER_SIZE 
  // if __n is zero then  get initial buffer size from
  // _RWSTD_CONTAINER_BUFFER_SIZE.  Only vector calls 
  // this function with a non-zero value for cursize.  
  // Return new buffer size in bytes.
  template <class _Tt, class _size>
  inline _size __rw_allocation_size(_Tt*,_size __n, _size __delta)
  {
    if (__n) 
      return __n + (__delta ? 
             __delta : _RWSTD_CONTAINER_BUFFER_SIZE/sizeof(_Tt));
    else
      return  (_RWSTD_CONTAINER_BUFFER_SIZE>sizeof(_Tt)) ?
              (_RWSTD_CONTAINER_BUFFER_SIZE/sizeof(_Tt)) : 1;
  }
#endif // _RWSTD_CONTAINER_CONST_ENLARGE



#if defined(_RWSTD_NO_DESTROY_NONBUILTIN)
  template <class _Tt> struct __FS : public _T
  {
    __FS() { ; }
    //
    // Calls destructor, but does not free the space.
    //
    void operator delete (void*) {;} 
  };
#endif // _RWSTD_NO_DESTROY_NONBUILTIN


  template <class _Tt>
  inline void __destroy (_Tt* pointer)
  {
#if defined(_RWSTD_NO_DESTROY_NONBUILTIN)
    delete (__FS<_Tt>*) (pointer);
#else
#if defined(_RWSTD_EXPLICIT_SCOPE_DESTROY)
    pointer->_Tt::~_Tt();
#else
    pointer->~_Tt();
#endif // _RWSTD_EXPLICIT_SCOPE_DESTROY
#endif // _RWSTD_NO_DESTROY_NONBUILTIN
  }


  template <class _T1, class _T2>
  inline void __construct (_T1* p, const _T2& value)
  {
    ::new (p) _T1(value);
  }

  template <class _ForwardIterator> 
  _RWSTD_TRICKY_INLINE void __destroy (_ForwardIterator first, _ForwardIterator last)
  {
     for ( ; first != last; ++first)
        __destroy(&*first);
  }


#if defined(_RWSTD_NO_DESTROY_BUILTIN) || defined(_RWSTD_NO_DESTROY_NONBUILTIN)
//
// Some specializations of STL destroy for builtin types.f
//
  inline void __destroy (void*)             {;}
  inline void __destroy (char*)             {;}
  inline void __destroy (unsigned char*)    {;}
  inline void __destroy (short*)            {;}
  inline void __destroy (unsigned short*)   {;}
  inline void __destroy (int*)              {;}
  inline void __destroy (unsigned int*)     {;}
  inline void __destroy (long*)             {;}
  inline void __destroy (unsigned long*)    {;}
  inline void __destroy (float*)            {;}
  inline void __destroy (double*)           {;}
  inline void __destroy (void**)            {;}
  inline void __destroy (char**)            {;}
  inline void __destroy (unsigned char**)   {;}
  inline void __destroy (short**)           {;}
  inline void __destroy (unsigned short**)  {;}
  inline void __destroy (int**)             {;}
  inline void __destroy (unsigned int**)    {;}
  inline void __destroy (long**)            {;}
  inline void __destroy (unsigned long**)   {;}
  inline void __destroy (float**)           {;}
  inline void __destroy (double**)          {;}
  inline void __destroy (void***)           {;}
  inline void __destroy (char***)           {;}
  inline void __destroy (unsigned char***)  {;}
  inline void __destroy (short***)          {;}
  inline void __destroy (unsigned short***) {;}
  inline void __destroy (int***)            {;}
  inline void __destroy (unsigned int***)   {;}
  inline void __destroy (long***)           {;}
  inline void __destroy (unsigned long***)  {;}
  inline void __destroy (float***)          {;}
  inline void __destroy (double***)         {;}
#ifndef _RWSTD_NO_BOOL
  inline void __destroy (bool*)             {;}
  inline void __destroy (bool**)            {;}
  inline void __destroy (bool***)           {;}
#endif
#ifndef _RWSTD_NO_LONGDOUBLE
  inline void __destroy (long double*)      {;}
  inline void __destroy (long double**)     {;}
  inline void __destroy (long double***)    {;}
#endif 
#ifndef _RWSTD_NO_OVERLOAD_WCHAR
  inline void __destroy (wchar_t*)          {;}
  inline void __destroy (wchar_t**)         {;}
  inline void __destroy (wchar_t***)        {;}
#endif
#endif /*_RWSTD_NO_DESTROY_BUILTIN || _RWSTD_NO_DESTROY_NONBUILTIN*/

#ifdef _RWSTD_LOCALIZED_ERRORS
  extern const unsigned int _RWSTDExport rwse_OutOfRange;
#else
  extern const char _RWSTDExportFunc(*) rwse_OutOfRange;
#endif // _RWSTD_LOCALIZED_ERRORS

#ifndef _RWSTD_NO_NAMESPACE
} // __rwstd namespace

namespace std {
#endif

//
// The default allocator.
//


#ifdef _RWSTD_ALLOCATOR

  template <class _Tt> class allocator;

//
// void specialization of allocator
//
  _RWSTD_TEMPLATE
  class allocator<void> {  
  public:
    typedef void*       pointer;
    typedef const void* const_pointer;
    typedef void        value_type;
   
    template <class _U2> 
    struct rebind { typedef allocator<_U2> other; };
    
  };


  template <class _Tt>
  class allocator
  {
  public:
    typedef size_t     size_type;
    typedef ptrdiff_t  difference_type;
    typedef _Tt*        pointer;
    typedef const _Tt*  const_pointer;
    typedef _Tt&        reference;
    typedef const _Tt&  const_reference;
    typedef _Tt         value_type;

    template <class _U2> struct rebind
    { typedef allocator<_U2> other; };

    allocator()  _RWSTD_THROW_SPEC_NULL
    { ; }

    allocator(const allocator&)  _RWSTD_THROW_SPEC_NULL
    { ; }

    template <class _U2>
    allocator(const allocator<_U2>&)  _RWSTD_THROW_SPEC_NULL
    { ; }

    template <class _U2>
    allocator<_Tt>& operator=(const allocator<_U2>& a)  _RWSTD_THROW_SPEC_NULL
    { return *this; }
    
    pointer address(reference x) const
    { 
      return _RWSTD_STATIC_CAST(pointer,&x); 
    }
    const_pointer address(const_reference x) const
    { 
      return _RWSTD_STATIC_CAST(const_pointer,&x); 
    }
    pointer allocate(size_type n, allocator<void>::const_pointer = 0)
    { 
      pointer tmp =
      _RWSTD_STATIC_CAST(pointer,(::operator 
                                  new(_RWSTD_STATIC_CAST(size_t,(n * sizeof(value_type))))));
      _RWSTD_THROW_NO_MSG(tmp == 0, bad_alloc);
      return tmp;
    }

    void deallocate(pointer p, size_type) 
    { 
      ::operator delete(p);
    }
    size_type max_size() const  _RWSTD_THROW_SPEC_NULL
    { 
      return 1 > UINT_MAX/sizeof(_Tt) ? size_type(1) : size_type(UINT_MAX/sizeof(_Tt));
    }
    inline void construct(pointer p, const _Tt& val);

    inline void destroy(_Tt* p);

  };



  template <class _Tt>
  void allocator<_Tt>::construct(pointer p, const _Tt& val)
  {
    __RWSTD::__construct(p,val);
  }

  template <class _Tt>
  void allocator<_Tt>::destroy(_Tt* p)
  {
     __RWSTD::__destroy(p);
  }

#else

//
// Alternate allocator uses an interface class (allocator_interface)
// to get type safety.
//
  template <class _Tt>
  class allocator
  { 
  public:
   
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef _Tt*        pointer;
    typedef const _Tt*  const_pointer;
    typedef _Tt&        reference;
    typedef const _Tt&  const_reference;
    typedef _Tt         value_type;

    allocator()  _RWSTD_THROW_SPEC_NULL { ; }
    allocator(const allocator<_Tt>&)  _RWSTD_THROW_SPEC_NULL
    { ; }
    allocator<_Tt>& operator=(const allocator<_Tt>&)  _RWSTD_THROW_SPEC_NULL
    { return *this; }

    void * allocate (size_type n, void *  = 0)
    { 
      void * tmp = _RWSTD_STATIC_CAST(void*,(::operator new(_RWSTD_STATIC_CAST(size_t,(n)))));
      _RWSTD_THROW_NO_MSG(tmp == 0, bad_alloc);
      return tmp;
    }
    
    void deallocate (void* p, size_type) 
    { 
      ::operator delete(p);
    }
    size_type max_size (size_type size) const
    { 
      return 1 > UINT_MAX/size ? size_type(1) : size_type(UINT_MAX/size);
    }
  };

  _RWSTD_TEMPLATE
  class allocator<void>
  { 
  public:
   
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef void*         pointer;
    typedef const void*   const_pointer;
    typedef void          value_type;

    allocator() _RWSTD_THROW_SPEC_NULL { ; }
    allocator(const allocator<void>&)  _RWSTD_THROW_SPEC_NULL
    { ; }
    allocator<void>& operator=(const allocator<void>&)  _RWSTD_THROW_SPEC_NULL
    { return *this; }

    void * allocate (size_type n, void *  = 0)
    { 
      void * tmp = _RWSTD_STATIC_CAST(void*,(::operator new(_RWSTD_STATIC_CAST(size_t,(n)))));
      _RWSTD_THROW_NO_MSG(tmp == 0, bad_alloc);
      return tmp;
    }
    
    void deallocate (void* p, size_type) 
    { 
      ::operator delete(p);
    }
    size_type max_size (size_type size) const
    { 
      return 1 > UINT_MAX/size ? size_type(1) : size_type(UINT_MAX/size);
    }
  };

//
// allocator_interface provides all types and typed functions.  Memory
// allocated as raw bytes using the class provided by the Allocator
// template parameter.  allocator_interface casts appropriately.
//
// Multiple allocator_interface objects can attach to a single 
// allocator, thus allowing one allocator to allocate all storage
// for a container, regardless of how many types are involved.
//
// The only real restriction is that pointer and reference are
// hard coded as _Tt* and _Tt&.  Partial specialization would 
// get around this.
//
  template <class _Allocator,class _Tt>
  class allocator_interface 
  {
  public:
    typedef _Allocator allocator_type;
    typedef _Tt*         pointer;
    typedef const _Tt*   const_pointer;      
    typedef _Tt&         reference;
    typedef const _Tt&   const_reference;
    typedef _Tt          value_type;
    typedef _TYPENAME _RWSTD_ALLOC_SIZE_TYPE             size_type;
    typedef _TYPENAME _RWSTD_ALLOC_DIFF_TYPE             difference_type;
    typedef void*      void_pointer;
    typedef const void* const_void_pointer;



  protected:
    allocator_type         alloc_;

  public:
    allocator_interface()  _RWSTD_THROW_SPEC_NULL  { ; }
    allocator_interface(const _Allocator& a)  _RWSTD_THROW_SPEC_NULL
    : alloc_(a) { ; }

    pointer address (_Tt& x) 
    { 
      return _RWSTD_STATIC_CAST(pointer,&x); 
    }
  
    size_type max_size ()  const
    { 
      return alloc_.max_size(sizeof(_Tt));
    }

    pointer allocate(size_type n, pointer p  = 0)
    {
      return _RWSTD_STATIC_CAST(pointer,alloc_.allocate(n*sizeof(_Tt),p));
    }

    void deallocate(pointer p, size_type n)
    {
      if ( p != 0 )
          alloc_.deallocate(p,n*sizeof(_Tt));
    }

    inline void construct(pointer p, const _Tt& val);

    inline void destroy(_Tt* p);

  };


  template <class _Allocator, class _Tt>
  inline void 
  allocator_interface<_Allocator,_Tt>::construct(pointer p, const _Tt& val)
  {
     __RWSTD::__construct(p,val);
  }

  template <class _Allocator, class _Tt>
  inline void allocator_interface<_Allocator,_Tt>::destroy(_Tt* p)
  {
     __RWSTD::__destroy(p);
  }

  _RWSTD_TEMPLATE
  class allocator_interface<allocator<void>,void> 
  {
  public:
    typedef allocator<void> allocator_type;
    typedef void*         pointer;
    typedef const void*   const_pointer;      
    typedef void          value_type;
    typedef allocator<void>::size_type       size_type;
    typedef allocator<void>::difference_type difference_type;

  protected:
    allocator_type         alloc_;

  public:
    allocator_interface()  _RWSTD_THROW_SPEC_NULL { ; }
    allocator_interface(const allocator<void>& a) _RWSTD_THROW_SPEC_NULL
    : alloc_(a) { ; }

    size_type max_size ()  const
    { 
      return alloc_.max_size(1);
    }

    pointer allocate(size_type n, pointer  = 0)
    {
      return _RWSTD_STATIC_CAST(pointer,alloc_.allocate(n));
    }

    void deallocate(pointer p, size_type n)
    {
      alloc_.deallocate(p,n);
    }      
  };

#endif  // _RWSTD_ALLOCATOR

// 
// Allocator globals
//
  template <class _Tt, class _U2>
  inline bool operator==(const allocator<_Tt>&, const allocator<_U2>&)  _RWSTD_THROW_SPEC_NULL
  {
    return true;
  }

#ifndef _RWSTD_NO_NAMESPACE
  template <class _Tt, class _U2>
  inline bool operator!=(const allocator<_Tt>&, const allocator<_U2>&)  _RWSTD_THROW_SPEC_NULL
  {
    return false;
  }
#endif

//
// Raw storage iterator.
//

  template <class _OutputIterator, class _Tt>
  class raw_storage_iterator
    : public iterator<output_iterator_tag,_Tt,ptrdiff_t,_Tt*,_Tt&>
  {
  protected:
    _OutputIterator iter;

  public:
    typedef _OutputIterator iterator_type;
    typedef _Tt element_type;

    _EXPLICIT raw_storage_iterator (_OutputIterator x) : iter(x) {}
    raw_storage_iterator<_OutputIterator, _Tt>& operator* () { return *this; }
    raw_storage_iterator<_OutputIterator, _Tt>& operator= (const _Tt& element)
    {
      ::new(&(*iter)) _Tt(element);
      return *this;
    }
    raw_storage_iterator<_OutputIterator, _Tt>& operator++ ()
    {
      ++iter; return *this;
    }
    raw_storage_iterator<_OutputIterator, _Tt> operator++ (int)
    {
      raw_storage_iterator<_OutputIterator, _Tt> tmp = *this;
      ++iter;
      return tmp;
    }
  };


//
// Temporary buffers
//

#ifdef _RWSTD_FAST_TEMP_BUF

#if defined(_RWSTD_SHARED_LIB) && !defined (_RWSTD_MULTI_THREAD)
#error Cannot use fast temporary buffer in this configuration
#endif
#if defined(_RWSTDDLL) && defined (__WIN16__)
#error Cannot use fast temporary buffer in this configuration
#endif

#ifndef __stl_buffer_size
#define __stl_buffer_size 16384  /* 16k */
#endif

#ifndef _RWSTD_NO_NAMESPACE
}

namespace __rwstd {
#endif

  extern char _RWSTDExport stl_temp_buffer[__stl_buffer_size];

#ifdef _RWSTD_MULTI_THREAD
  extern _RWSTDMutex _RWSTDExport stl_temp_buffer_mutex;
  extern bool       _RWSTDExport stl_temp_buffer_being_used;
#endif

#ifndef _RWSTD_NO_NAMESPACE
} // End of __rwstd namespace

namespace std {
#endif

  template <class _Tt>
#ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
  inline pair<_Tt*, ptrdiff_t> get_temporary_buffer (ptrdiff_t len)
#else
  inline pair<_Tt*, ptrdiff_t> get_temporary_buffer (ptrdiff_t len, _Tt*)
#endif
  {
    while (len > __stl_buffer_size / sizeof(_Tt))
    {
      _Tt* tmp = _RWSTD_STATIC_CAST(_Tt*,( ::operator new(_RWSTD_STATIC_CAST(unsigned int,len) * sizeof(_Tt))));
      if (tmp)
      {
        pair<_Tt*, ptrdiff_t> result(tmp, len);
        return result;
      }
      len = len / 2;
    }
    
#ifdef _RWSTD_MULTI_THREAD
    _RWSTDGuard guard(__RWSTD::stl_temp_buffer_mutex);

    if (__RWSTD::stl_temp_buffer_being_used)
    {
      _Tt* tmp = _RWSTD_STATIC_CAST(_Tt*,(   ::operator new(_RWSTD_STATIC_CAST(unsigned int,len) * sizeof(_Tt))));
      pair<_Tt*,ptrdiff_t> result(tmp, len);
      return result;
    }
    else
    {
      __RWSTD::stl_temp_buffer_being_used = true;
      pair<_Tt*, ptrdiff_t> result(_RWSTD_STATIC_CAST(_Tt*,
                                 _RWSTD_STATIC_CAST(void*,__RWSTD::stl_temp_buffer)), 
                                 _RWSTD_STATIC_CAST(ptrdiff_t,(__stl_buffer_size / sizeof(_Tt))));
      return result;
    }
#else
    pair<_Tt*, ptrdiff_t> result(_RWSTD_STATIC_CAST(_Tt*,
                               _RWSTD_STATIC_CAST(void*,__RWSTD::stl_temp_buffer)), 
                               _RWSTD_STATIC_CAST(ptrdiff_t,(__stl_buffer_size / sizeof(_Tt))));
    return result;
#endif /*_RWSTD_MULTI_THREAD*/
  }

  template <class _Tt>
  inline void return_temporary_buffer (_Tt* p)
  {
#ifdef _RWSTD_MULTI_THREAD
    _RWSTDGuard guard(__RWSTD::stl_temp_buffer_mutex);

    if (_RWSTD_STATIC_CAST(char*,
                           _RWSTD_STATIC_CAST(void*,p)) != __RWSTD::stl_temp_buffer) 
      ::operator delete(p);
    else
      __RWSTD::stl_temp_buffer_being_used = false;
#else
    if (_RWSTD_STATIC_CAST(char*,
                           _RWSTD_STATIC_CAST(void*,p)) != __RWSTD::stl_temp_buffer) 
      ::operator delete(p);
#endif /*_RWSTD_MULTI_THREAD*/
  }

#else

  template <class _Tt>
#ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
  inline pair<_Tt*, ptrdiff_t> get_temporary_buffer (ptrdiff_t len)
#else
  inline pair<_Tt*, ptrdiff_t> get_temporary_buffer (ptrdiff_t len, _Tt*)
#endif
  {
    _Tt* tmp = _RWSTD_STATIC_CAST(_Tt*,(   ::operator new(len * sizeof(_Tt))));
    pair<_Tt*,ptrdiff_t> result(tmp, len);
    return result;
  }

  template <class _Tt>
  inline void return_temporary_buffer (_Tt* p)
  {
    ::operator delete(p);
  }

#endif /*_RWSTD_FAST_TEMP_BUF*/


//
// Specialized algorithms.
//

  template <class _InputIterator, class _ForwardIterator>
  _RWSTD_TRICKY_INLINE _ForwardIterator uninitialized_copy (_InputIterator first, _InputIterator last,
                                                           _ForwardIterator result)
  {
    _ForwardIterator start = result;
#ifndef _RWSTD_NO_EXCEPTIONS
    try {
      while (first != last) 
         __RWSTD::__construct(result++, *first++);
    } catch(...) {
       __RWSTD::__destroy(start,result);
      throw;
    }
#else
    while (first != last) 
       __RWSTD::__construct(result++, *first++);
#endif // _RWSTD_NO_EXCEPTIONS

    return result;
  }

  template <class _ForwardIterator, class _Tt>
  _RWSTD_TRICKY_INLINE void uninitialized_fill (_ForwardIterator first, _ForwardIterator last,
                                                const _Tt& x)
  {
    _ForwardIterator start = first;
#ifndef _RWSTD_NO_EXCEPTIONS
    try {
      while (first != last) 
         __RWSTD::__construct(first++, x);
    } catch(...) {
       __RWSTD::__destroy(start,first);
      throw;
    }
#else
    while (first != last) 
       __RWSTD::__construct(first++, x);
#endif // _RWSTD_NO_EXCEPTIONS
  }

  template <class _ForwardIterator, class _Size, class _Tt>
  _RWSTD_TRICKY_INLINE void uninitialized_fill_n (_ForwardIterator first, _Size n, const _Tt& x)
  {
    _ForwardIterator start = first;
#ifndef _RWSTD_NO_EXCEPTIONS
    try {
      while (n--) 
         __RWSTD::__construct(first++, x);
    } catch(...) {
       __RWSTD::__destroy(start,first);
      throw;
    }
#else
    while (n--) 
       __RWSTD::__construct(first++, x);
#endif // _RWSTD_NO_EXCEPTIONS
  }


//
// Template auto_ptr holds onto a pointer obtained via new and deletes that
// object when it itself is destroyed (such as when leaving block scope).
//
// It can be used to make calls to new() exception safe.
//

//#ifndef _RWSTD_NO_MEM_CLASS_TEMPLATES
  template <class _YY> class auto_ptr_ref 
  {
     _YY* p;
  public:
     		auto_ptr_ref(_YY* a) : p(a) {}
     _YY*	release() { _YY* tmp = p; p = 0; return tmp; }	
  };
//#endif    

  template<class _XX> class auto_ptr
  {
  public:
    typedef _XX element_type;

    //
    // construct/copy/destroy
    //
    _EXPLICIT auto_ptr (_XX* p = 0)  _RWSTD_THROW_SPEC_NULL
     : the_p(p)
    { ; }

    auto_ptr (auto_ptr<_XX>& a)  _RWSTD_THROW_SPEC_NULL
     :  the_p((_RWSTD_CONST_CAST(auto_ptr<_XX>&,a)).release()) 
    { ; }

    auto_ptr<_XX>& operator= (auto_ptr<_XX>& rhs)  _RWSTD_THROW_SPEC_NULL
    { 
      reset(rhs.release());
      return *this;
    }
//#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template <class _YY>
    auto_ptr (auto_ptr<_YY>& a)  _RWSTD_THROW_SPEC_NULL
     : the_p((_RWSTD_CONST_CAST(auto_ptr<_YY>&,a)).release()) 
    { ; }

    template <class _YY>
    auto_ptr<_XX>& operator= (auto_ptr<_YY>& rhs)  _RWSTD_THROW_SPEC_NULL
    { 
      reset(rhs.release());
      return *this;
    }
//#endif

    ~auto_ptr () _RWSTD_THROW_SPEC_NULL { delete the_p; }
    //
    // members
    //
    _XX& operator*  ()  const _RWSTD_THROW_SPEC_NULL { return *the_p;   }
    _XX* operator-> ()  const _RWSTD_THROW_SPEC_NULL { return the_p;    }
    _XX* get        ()  const _RWSTD_THROW_SPEC_NULL { return the_p;    }

    _XX* release    ()  _RWSTD_THROW_SPEC_NULL
    { 
      _XX* tmp = the_p;
      the_p = 0; 
      return tmp; 
    }

    void reset (_XX* p = 0) _RWSTD_THROW_SPEC_NULL
    { 
      if (the_p != p)
      {
        delete the_p;
        the_p = p;
      }
    }

//#ifndef _RWSTD_NO_MEM_CLASS_TEMPLATES
    auto_ptr(auto_ptr_ref<_XX> r) _RWSTD_THROW_SPEC_NULL
      : the_p (0)
    {
      reset(r.release());
    }
    auto_ptr<_XX>& operator= (auto_ptr_ref<_XX> r) _RWSTD_THROW_SPEC_NULL
    {
      reset(r.release());
      return *this;	
    }
//#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template <class _YY> operator auto_ptr_ref<_YY>() _RWSTD_THROW_SPEC_NULL
    {
      return auto_ptr_ref<_YY>(release());
    }
    template <class _YY> operator auto_ptr<_YY>() _RWSTD_THROW_SPEC_NULL
    {  
      auto_ptr<_YY> tmp;
      tmp.reset(release());
      return tmp;
    }
//#endif // _RWSTD_NO_MEMBER_TEMPLATES
//#endif // _RWSTD_NO_MEM_CLASS_TEMPLATES

  private:
    _XX* the_p;
  };


#ifndef _RWSTD_NO_NAMESPACE
}
#endif

#pragma enable_warn

#endif /*__STD_MEMORY*/