///////////////////////////////////////////////////////////////////////////
// FILE: vector (Definition of std::vector)
//
//                          Open Watcom Project
//
//    Portions Copyright (c) 1983-2002 Sybase, Inc. 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 <stdexcept>
#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 reverse_iterator< iterator >        reverse_iterator;
    typedef 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.

  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( ), n - vec_length, 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

} // End of namespace std.

#endif
