///////////////////////////////////////////////////////////////////////////
// FILE: vector (Definition of std::vector)
//
//                          Open Watcom Project
//
// Copyright (c) 2004-2008 The Open Watcom Contributors. All Rights Reserved.
//
//    This file is automatically generated. Do not edit directly.
//
// =========================================================================
//
// Description: This header is part of the C++ standard library. It
//              defines a vector template that in many cases can be
//              used as a replacement for C-style arrays.
///////////////////////////////////////////////////////////////////////////
#ifndef _VECTOR_INCLUDED
#define _VECTOR_INCLUDED

#if !defined(_ENABLE_AUTODEPEND)
  #pragma read_only_file;
#endif


#ifndef __cplusplus
  #error The header vector requires C++
#endif

#ifndef _ITERATOR_INCLUDED
  #include <iterator>
#endif

#ifndef _LIMITS_INCLUDED
  #include <limits>
#endif

#ifndef _MEMORY_INCLUDED
  #include <memory>
#endif

#ifndef _STDEXCEPT_INCLUDED
  #include <stdexcep>
#endif

#ifndef _TYPE_TRAITS_INCLUDED
  #include <type_tra>
#endif

namespace std {

template<class Type, class Allocator = allocator< Type > >
class vector {
public:
    typedef typename Allocator::reference           reference;
    typedef typename Allocator::const_reference     const_reference;
    typedef typename Allocator::size_type           size_type;
    typedef typename Allocator::difference_type     difference_type;
    typedef Type                                    value_type;
    typedef Allocator                               allocator_type;
    typedef typename Allocator::pointer             pointer;
    typedef typename Allocator::const_pointer       const_pointer;
    typedef pointer                                 iterator;
    typedef const_pointer                           const_iterator;
    typedef std::reverse_iterator< iterator >       reverse_iterator;
    typedef std::reverse_iterator< const_iterator > const_reverse_iterator;

    explicit vector( const Allocator & = Allocator( ) );
    explicit vector( size_type n, const Type &value = Type( ), const Allocator & = Allocator( ) );
    vector( const vector &other );
   ~vector( );
    vector &operator=( const vector &other );
    void assign( size_type n, const Type &value );
    allocator_type get_allocator( ) const;

    iterator               begin( );
    const_iterator         begin( ) const;
    iterator               end( );
    const_iterator         end( ) const;
    reverse_iterator       rbegin( );
    const_reverse_iterator rbegin( ) const;
    reverse_iterator       rend( );
    const_reverse_iterator rend( ) const;

    size_type size( ) const;
    size_type max_size( ) const;
    void      resize( size_type n, Type c = Type( ) );
    size_type capacity( ) const;
    bool      empty( ) const;
    void      reserve( size_type n );

    reference       operator[]( size_type n );
    const_reference operator[]( size_type n ) const;
    reference       at( size_type n );
    const_reference at( size_type n ) const;
    reference       front( );
    const_reference front( ) const;
    reference       back( );
    const_reference back( ) const;

    void     push_back( const Type &x );
    void     pop_back( );
    iterator insert( iterator position, const Type &x );
    void     insert( iterator position, size_type n, const Type &x );
    iterator erase( iterator position );
    iterator erase( iterator first, iterator last );
    void     swap( vector &x );
    void     clear( );

    bool     _Sane( ) const;  // Check invariants.


    template< class InputIterator >
    void assign( InputIterator first, InputIterator last )
    {
        helper_assign( first, last, tr1::is_integral<InputIterator>::type() );
    }

    template< class Integral >
    void helper_assign( Integral count,
                        Integral value,
                        tr1::true_type )
    {
        vector temp;
        for( Integral i = 0; i < count; ++i )
            temp.push_back( value );
        swap( temp );
    }

    template< class InputIterator >
    void helper_assign( InputIterator first,
                        InputIterator last,
                        tr1::false_type )
    {
        vector temp;
        while( first != last ) {
            temp.push_back( *first );
            ++first;
        }
        swap( temp );
    }
    
    template< class InputIterator >
    void insert(iterator position, InputIterator first, InputIterator last )
    {
        helper_insert( position,
                       first,
                       last,
                       tr1::is_integral<InputIterator>::type( ) );
    }
    
    template< class Integral >
    void helper_insert( iterator position,
                        Integral count,
                        Integral value,
                        tr1::true_type )
    {
        insert( position,
                static_cast<size_type>( count ),
                static_cast<const Type &>( value ) );
    }
    
    template< class InputIterator >
    void helper_insert( iterator position,
                        InputIterator first,
                        InputIterator last,
                        tr1::false_type )
    {
        while( first != last ) {
            insert( position, *first );
            ++position;
            ++first;
        }
    }

private:
    // 1. buffer has size buf_length.
    // 2. buffer never shrinks (except in ...).
    // 3. buf_length >= vec_length.
    // 4. buf_length is a power of two.
    // 5. buffer allocated with mem or a copy of mem.
    //
    Allocator mem;         // Object used to get and release memory.
    pointer   buffer;      // Pointer to start of buffer space.
    size_type buf_length;  // Total number of buffer slots.
    size_type vec_length;  // Number of buffer slots in use by objects.

    // This method encapsulates the memory allocation policy.
    pointer alloc( size_type required, size_type &found );
};

// ==========================
// Member functions of vector
// ==========================

template< class Type, class Allocator >
vector< Type, Allocator >::pointer
    vector< Type, Allocator >::alloc(
        size_type required,
        size_type &found )
{
    pointer   result;
    size_type length = 16;

    // Find a power of two that produces a sufficient size.
    while( length < required ) length <<= 1;
    result = mem.allocate( length );

    // Update outputs only if allocation successful.
    found = length;
    return( result );
}

// vector( const Allocator & )
// ***************************
template< class Type, class Allocator >
vector< Type, Allocator >::vector( const Allocator &a ) : mem( a )
{
    buffer = alloc(1, buf_length );
    vec_length = 0;
}

// vector( size_type, const Type &, const Allocator & )
//*****************************************************
template< class Type, class Allocator >
vector< Type, Allocator >::vector(
    size_type n,
    const Type &value,
    const Allocator &a ) : mem( a )
{
    buffer = alloc( n, buf_length );
    try {
        uninitialized_fill_n( buffer, n, value );
    }
    catch( ... ) {
        mem.deallocate( buffer, buf_length );
        throw;
    }
    vec_length = n;
}

// vector( const vector & )
// ************************
template< class Type, class Allocator >
vector< Type, Allocator >::vector( const vector &other )
    : mem( other.mem )
{
    buffer = alloc( other.vec_length, buf_length );
    try {
        uninitialized_copy( other.buffer,
                            other.buffer + other.vec_length,
                            buffer );
    }
    catch( ... ) {
        mem.deallocate( buffer, buf_length );
        throw;
    }
    vec_length = other.vec_length;
}

// ~vector( )
// **********
template< class Type, class Allocator >
vector< Type, Allocator >::~vector( )
{
    // Delete objects actually in use and deallocate the buffer.
    for( size_type i = 0; i < vec_length; ++i ) {
        mem.destroy( &buffer[i] );
    }
    mem.deallocate( buffer, buf_length );
}

// operator=( const vector & )
// ***************************
template< class Type, class Allocator >
vector< Type, Allocator > &vector< Type, Allocator >::operator=(
    const vector &other )
{
    if( this == &other ) return( *this );

    // Don't overwrite our allocator just yet.
    Allocator temp_allocator( other.mem );

    // Allocate buffer space for copy and try to make the copy.
    pointer temp_buffer = temp_allocator.allocate( other.buf_length );
    try {
        uninitialized_copy( other.buffer,
                            other.buffer + other.vec_length,
                            temp_buffer );
    }
    catch( ... ) {
        temp_allocator.deallocate( temp_buffer, other.buf_length );
        throw;
    }

    // New allocation successful.
    for( size_type i = 0; i < vec_length; ++i ) {
        mem.destroy( &buffer[i] );
    }
    mem.deallocate( buffer, buf_length );

    mem        = temp_allocator;
    buffer     = temp_buffer;
    buf_length = other.buf_length;
    vec_length = other.vec_length;

    return( *this );
}

// assign( size_type, const Type & )
// *********************************
template< class Type, class Allocator >
void vector< Type, Allocator >::assign( size_type n, const Type &value )
{
    // Prepare new buffer space.
    size_type temp_length;
    pointer temp_buffer = alloc( n, temp_length );
    try {
        uninitialized_fill_n( temp_buffer, n, value );
    }
    catch( ... ) {
        mem.deallocate( temp_buffer, temp_length );
        throw;
    }

    // New allocation successful.
    for( size_type i = 0; i < vec_length; ++i ) {
        mem.destroy( &buffer[i] );
    }
    mem.deallocate( buffer, buf_length );

    buffer     = temp_buffer;
    buf_length = temp_length;
    vec_length = n;
}

// get_allocator( ) const
// **********************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::allocator_type
    vector<Type, Allocator>::get_allocator( ) const
{
    return( mem );
}

// begin( )
// ********
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::iterator
    vector<Type, Allocator>::begin( )
{
    return( buffer );
}

// begin( ) const
// **************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::const_iterator
    vector<Type, Allocator>::begin( ) const
{
    return( buffer );
}

// end( )
// ******
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::iterator
    vector< Type, Allocator >::end( )
{
    return( buffer + vec_length );
}

// end( ) const
// ************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::const_iterator
    vector< Type, Allocator >::end( ) const
{
    return( buffer + vec_length );
}

// rbegin( )
// *********
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::reverse_iterator
    vector< Type, Allocator >::rbegin( )
{
    return( reverse_iterator( buffer + vec_length ) );
}

// rbegin( ) const
// ***************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::const_reverse_iterator
    vector< Type, Allocator >::rbegin( ) const
{
    return( const_reverse_iterator( buffer + vec_length ) );
}

// rend( )
// *******
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::reverse_iterator
    vector< Type, Allocator >::rend( )
{
    return( reverse_iterator( buffer ) );
}

// rend( ) const
// *************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::const_reverse_iterator
    vector< Type, Allocator >::rend( ) const
{
    return( const_reverse_iterator( buffer ) );
}

// size( ) const
// *************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::size_type
    vector< Type, Allocator >::size( ) const
{
    return( vec_length );
}

// max_size( ) const
// *****************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator>::size_type
    vector< Type, Allocator >::max_size( ) const
{
    return( std::numeric_limits< size_type >::max( ) / sizeof( Type ) );
}

// resize( size_type, Type )
// *************************
template< class Type, class Allocator >
void vector< Type, Allocator >::resize( size_type n, Type c )
{
    if( n > vec_length )
        insert( end( ),
                static_cast<size_type>(n - vec_length),
                static_cast<const Type &>( c ) );
    else if ( n < vec_length )
        erase( begin( ) + n, end( ) );
}

// capacity( ) const
// *****************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::size_type
    vector< Type, Allocator >::capacity( ) const
{
    return( buf_length );
}

// empty( ) const
// **************
template< class Type, class Allocator >
inline
bool vector< Type, Allocator >::empty( ) const
{
    return( vec_length == 0 );
}

// reserve( size_type )
// ********************
template< class Type, class Allocator >
void vector< Type, Allocator>::reserve( size_type new_capacity )
{
    if( new_capacity <= buf_length ) return;
    if( new_capacity > max_size( ) )
        throw length_error( "vector::reserve" );

    size_type temp_length;
    pointer temp_buffer = alloc( new_capacity, temp_length );
    try {
        uninitialized_copy( buffer, buffer + vec_length, temp_buffer );
    }
    catch( ... ) {
        mem.deallocate( temp_buffer, temp_length );
        throw;
    }

    // New allocation successful.
    for( size_type i = 0; i < vec_length; ++i ) {
        mem.destroy( &buffer[i] );
    }
    mem.deallocate( buffer, buf_length );

    buffer     = temp_buffer;
    buf_length = temp_length;
}

// operator[]( size_type )
// ***********************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::reference
    vector< Type, Allocator >::operator[]( size_type n )
{
    return( buffer[n] );
}

// operator[]( size_type ) const
// *****************************
template< class Type, class Allocator >
inline typename vector< Type, Allocator >::const_reference
    vector< Type, Allocator >::operator[]( size_type n ) const
{
    return( buffer[n] );
}

// at( size_type )
// ***************
template< class Type, class Allocator >
typename vector< Type, Allocator >::reference
    vector< Type, Allocator >::at( size_type n )
{
    if( n >= vec_length )
        throw out_of_range( "vector::at" );
    return( buffer[n] );
}

// at( size_type ) const
// *********************
template< class Type, class Allocator >
typename vector< Type, Allocator >::const_reference
    vector< Type, Allocator >::at( size_type n ) const
{
    if( n >= vec_length )
        throw out_of_range( "vector::at" );
    return( buffer[n] );
}

// front( )
// ********
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::reference
    vector< Type, Allocator >::front( )
{
    return( buffer[0] );
}

// front( ) const
// **************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::const_reference
    vector< Type, Allocator >::front( ) const
{
    return( buffer[0] );
}

// back( )
// *******
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::reference
    vector< Type, Allocator >::back( )
{
    return( buffer[vec_length - 1] );
}

// back( ) const
// *************
template< class Type, class Allocator >
inline
typename vector< Type, Allocator >::const_reference
    vector< Type, Allocator >::back( ) const
{
    return( buffer[vec_length - 1] );
}

// push_back( const Type & )
// *************************
template< class Type, class Allocator >
void vector< Type, Allocator >::push_back( const Type &item )
{
    if( vec_length + 1 > buf_length ) {
        reserve( buf_length + 1 );
    }
    new ( static_cast<void *>( buffer + vec_length ) ) Type( item );
    ++vec_length;
}

// pop_back( )
// ***********
template< class Type, class Allocator >
inline
void vector< Type, Allocator >::pop_back( )
{
    mem.destroy( &buffer[vec_length - 1] );
    --vec_length;
}

// insert( iterator, const Type & )
// ********************************
template< class Type, class Allocator >
vector< Type, Allocator >::iterator
    vector< Type, Allocator >::insert( iterator position, const Type &x )
{
    size_type iposition = static_cast< size_type >( position - buffer );
    size_type tail_count = vec_length - iposition;

    // Deal with zero length vector as a special case.
    if( vec_length == 0 ) {
        mem.construct( &buffer[0], x );
        vec_length++;
        return( buffer );
    }

    // Handle case were reallocation isn't necessary.
    if( vec_length + 1 <= buf_length ) {
        mem.construct( &buffer[vec_length], buffer[vec_length - 1] );
        vec_length++;
        for( size_type i = 2; i <= tail_count; ++i ) {
            buffer[vec_length - i] = buffer[vec_length - 1 - i];
        }
        *position = x;
        return( position );
    }

    // Handle case where reallocation is necessary.
    size_type temp_length;
    pointer temp_buffer = alloc( vec_length + 1, temp_length );

    size_type copy_count = 0;
    pointer   src_iterator = buffer;
    pointer   dst_iterator = temp_buffer;
    try {
        while( src_iterator != position ) {
            mem.construct( dst_iterator, *src_iterator );
            ++copy_count; ++src_iterator; ++dst_iterator;
        }
        mem.construct( dst_iterator, x );
        ++copy_count; ++dst_iterator;
        while( src_iterator != buffer + vec_length ) {
            mem.construct( dst_iterator, *src_iterator );
            ++copy_count; ++src_iterator; ++dst_iterator;
        }
    }
    catch( ... ) {
        for( size_type i = 0; i < copy_count; ++i ) {
            mem.destroy( &temp_buffer[i] );
        }
        mem.deallocate( temp_buffer, temp_length );
        throw;
    }

    // It worked. Commit the new value.
    for( size_type i = 0; i < vec_length; ++i ) {
        mem.destroy( &buffer[i] );
    }
    mem.deallocate( buffer, buf_length );
    buffer     = temp_buffer;
    buf_length = temp_length;
    vec_length++;
    return( buffer + iposition );
}

// insert( iterator, size_type, const Type & )
// *******************************************
template< class Type, class Allocator >
void vector< Type, Allocator >::insert(
    iterator position, size_type n, const Type &x
)
{
    size_type iposition = static_cast< size_type >( position - buffer );
    if( n == 0 ) return;

    // Handle the case where reallocation isn't necessary.
    if( vec_length + n <= buf_length ) {

        // FIX ME: This code isn't exception safe.

        // Open a gap of size n.
        size_type copya;  // Number of objects needing assignment.
        size_type copyc;  // Number of objects needing copy construction.

        copya = ( iposition + n < vec_length ) ? vec_length - iposition - n : 0;
        copyc = vec_length - iposition - copya;

        // Copy construct tail of vector into fresh memory.
        uninitialized_copy( position + copya,
                            position + copya + copyc,
                            position + copya + n );

        // Assign remaining elements in reverse order.
        iterator src_iterator( position + copya - 1);
        iterator dst_iterator( buffer + vec_length - 1 );
        for( size_type i = 0; i < copya; ++i ) {
            *dst_iterator = *src_iterator;
            --src_iterator; --dst_iterator;
        }

        // Fill the gap.
        size_type filla;  // Number of objects needing assignment.
        size_type fillc;  // Number of objects needing copy construction.

        filla = ( n >= vec_length - iposition ) ? vec_length - iposition : n;
        fillc = n - filla;

        // Copy construct new objects (if any).
        uninitialized_fill_n( buffer + vec_length, fillc, x );

        // Assign remaining elements.
        dst_iterator = position;
        for( size_type i = 0; i < filla; ++i ) {
            *dst_iterator = x;
          ++dst_iterator;
        }

        vec_length += copyc + fillc;
        return;
    }

    // Handle case where reallocation is necessary.
    size_type temp_length;
    pointer temp_buffer = alloc( vec_length + n, temp_length );

    size_type copy_count = 0;
    pointer   src_iterator = buffer;
    pointer   dst_iterator = temp_buffer;
    try {
        while( src_iterator != position ) {
            mem.construct( dst_iterator, *src_iterator );
            ++copy_count; ++src_iterator; ++dst_iterator;
        }
        for( size_type i = 0; i < n; ++i ) {
            mem.construct( dst_iterator, x );
            ++copy_count; ++dst_iterator;
        }
        while( src_iterator != buffer + vec_length ) {
            mem.construct( dst_iterator, *src_iterator );
            ++copy_count; ++src_iterator; ++dst_iterator;
        }
    }
    catch( ... ) {
        for( size_type i = 0; i < copy_count; ++i ) {
            mem.destroy( &temp_buffer[i] );
        }
        mem.deallocate( temp_buffer, temp_length );
        throw;
    }

    // It worked. Commit the new value.
    for( size_type i = 0; i < vec_length; ++i ) {
        mem.destroy( &buffer[i] );
    }
    mem.deallocate( buffer, buf_length );
    buffer     = temp_buffer;
    buf_length = temp_length;
    vec_length = vec_length + n;
}

  // erase( iterator )
  // *****************
  template< class Type, class Allocator >
  typename vector< Type, Allocator >::iterator
    vector< Type, Allocator >::erase( iterator position )
  {
    iterator return_value( position );

    while( position != buffer + vec_length - 1 ) {
      *position = *( position + 1 );
      ++position;
    }
    mem.destroy( position );
    --vec_length;
    return( return_value );
  }

// erase( iterator, iterator )
// ***************************
template< class Type, class Allocator >
typename vector< Type, Allocator >::iterator
    vector< Type, Allocator >::erase( iterator first, iterator last )
{
    iterator        return_value( first );
    difference_type removed( last - first );

    while( last != buffer + vec_length ) {
        *first = *last;
        ++first; ++last;
    }
    while( first != buffer + vec_length ) {
        mem.destroy( first );
        ++first;
    }
    vec_length -= removed;
    return( return_value );
}

// swap( )
// *******
template< class Type, class Allocator >
void vector< Type, Allocator >::swap( vector &vec )
{
    typename Allocator::pointer ptemp;
    typename Allocator::size_type stemp;
    Allocator atemp;

    ptemp          = buffer;
    buffer         = vec.buffer;
    vec.buffer     = ptemp;

    stemp          = buf_length;
    buf_length     = vec.buf_length;
    vec.buf_length = stemp;

    stemp          = vec_length;
    vec_length     = vec.vec_length;
    vec.vec_length = stemp;

    atemp          = mem;
    mem            = vec.mem;
    vec.mem        = atemp;
}

// clear( )
// ********
template< class Type, class Allocator >
void vector< Type, Allocator >::clear( )
{
    // Delete objects actually in use.
    for( size_type i = 0; i < vec_length; ++i ) {
        mem.destroy( &buffer[i] );
    }
    vec_length = 0;
}

// _Sane( ) const
// **************
template< class Type, class Allocator >
bool vector< Type, Allocator >::_Sane( ) const
{
    if( buf_length == 0 ) return( false );
    if( buf_length < vec_length ) return( false );

    // Is buf_length a power of 2?
    size_type temp = buf_length;
    while( temp != 1 ) {
        if( temp & 0x1 ) return( false );
        temp >>= 1; 
    }
    return( true );
}

// ===============================
// Ordinary functions using vector
// ===============================

// operator==( const vector &, const vector & )
// ********************************************
template< class Type, class Allocator >
bool operator==(
    const vector< Type, Allocator > &x,
    const vector< Type, Allocator > &y )
{
    if( x.size( ) != y.size( ) ) return( false );

    vector< Type, Allocator>::size_type index = 0;
    while( index < x.size( ) ) {
        if( x[index] != y[index] ) return( false );
        ++index;
    }
    return( true );
}

// operator!=( const vector &, const vector & )
// ********************************************
template< class Type, class Allocator >
inline
bool operator!=(
    const vector< Type, Allocator > &x,
    const vector< Type, Allocator > &y )
{
    return( !(x == y) );
}

// operator<( const vector &, const vector & )
// *******************************************
template< class Type, class Allocator >
bool operator<(
    const vector< Type, Allocator > &x,
    const vector< Type, Allocator > &y )
 {
    vector< Type, Allocator>::size_type index = 0;
    while( index != x.size( ) && index != y.size( ) ) {
        if( x[index] < y[index] ) return( true );
        if( y[index] < x[index] ) return( false );
        ++index;
    }
    return( index == x.size( ) && index != y.size( ) );
}

// operator<=( const vector &, const vector & )
// ********************************************
template< class Type, class Allocator >
inline
bool operator<=(
    const vector< Type, Allocator > &x,
    const vector< Type, Allocator > &y )
{
    return( !( x > y) );
}

// operator>( const vector &, const vector & )
// *******************************************
template< class Type, class Allocator >
inline
bool operator>(
    const vector< Type, Allocator > &x,
    const vector< Type, Allocator > &y )
{
    return( y < x);
}

// operator>=( const vector &, const vector & )
// ********************************************
template< class Type, class Allocator >
inline
bool operator>=(
    const vector< Type, Allocator > &x,
    const vector< Type, Allocator > &y )
{
    return( !(x < y) );
}

#ifdef __NEVER
// swap( vector &, vector & )
// **************************
template< class Type, class Allocator >
inline
void swap( vector< Type, Allocator > &x, vector< Type, Allocator > &y )
{
    x.swap( y );
}
#endif

} // namespace std

#endif