deque.mh

来自「开放源码的编译器open watcom 1.6.0版的源代码」· MH 代码 · 共 966 行 · 第 1/2 页

///////////////////////////////////////////////////////////////////////////
// FILE: deque (Definition of std::deque)
//
:keep CPP_HDR
:include crwatcnt.sp
//
// Description: This header is part of the C++ standard library. It defines
//              a double ended queue template that provides random access
//              to its elements yet amortized O(1) time push/pop operations
//              on *both* ends.
///////////////////////////////////////////////////////////////////////////
#ifndef _DEQUE_INCLUDED
#define _DEQUE_INCLUDED

:include readonly.sp

#ifndef __cplusplus
#error The header deque 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

namespace std {

  template<class Type, class Allocator = allocator< Type > >
  class deque {
  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;

    // Class iterator
    // --------------
    class iterator :
      public std::iterator< random_access_iterator_tag, Type > {
    public:
      iterator( deque *p, deque::size_type i ) :
        dp( p ), index( i ) { }

      iterator( ) { }

      value_type &operator*( )
        { return( dp->buffer[index] ); }

      value_type *operator->( )
        { return( &dp->buffer[index] ); }

      iterator &operator++( );
      iterator  operator++( int );
      iterator &operator--( );
      iterator  operator--( int );

:: Due to a bug in the compiler (#492) these functions can't be defined
:: outside of the class and must be inline. As a result they must also
:: be friends (even when not otherwise necessary).
      friend bool operator==(iterator lhs, iterator rhs)
        { return( lhs.dp == rhs.dp && lhs.index == rhs.index ); }
      friend bool operator< (iterator lhs, iterator rhs)
      {
        deque::size_type xform1, xform2;
        if( lhs.index >= lhs.dp->head_index )
          xform1 = lhs.index - lhs.dp->head_index;
        else
          xform1 = (lhs.dp->deq_length - lhs.dp->head_index) + lhs.index;

        if( rhs.index >= rhs.dp->head_index )
          xform2 = rhs.index - rhs.dp->head_index;
        else
          xform2 = (rhs.dp->deq_length - rhs.dp->head_index) + rhs.index;

        return( xform1 < xform2 );
      }
      friend bool operator!=(iterator lhs, iterator rhs)
        { return( !( lhs == rhs ) ); }
      friend bool operator>=(iterator lhs, iterator rhs)
        { return( !( lhs < rhs ) ); }
      friend bool operator> (iterator lhs, iterator rhs)
        { return( rhs < lhs ); }
      friend bool operator<=(iterator lhs, iterator rhs)
        { return( !( lhs > rhs ) ); }

      iterator &operator+=( difference_type n );
      iterator &operator-=( difference_type n );
      friend iterator operator+( iterator it, difference_type n )
        { it += n; return( it ); }
      friend iterator operator+( difference_type n, iterator it )
        { it += n; return( it ); }
      friend iterator operator-( iterator it, difference_type n )
        { it -= n; return( it ); }

    private:
      deque *dp;
      deque::size_type index;
    };

    // Class const_iterator
    // --------------------
    class const_iterator :
      public std::iterator< random_access_iterator_tag, const Type > {
    public:
      const_iterator( const deque *p, deque::size_type i ) :
        dp( p ), index( i ) { }

      const_iterator( ) { }

      value_type &operator*( )
        { return( dp->buffer[index] ); }

      value_type *operator->( )
        { return( &dp->buffer[index] ); }

      const_iterator &operator++( );
      const_iterator  operator++( int );
      const_iterator &operator--( );
      const_iterator  operator--( int );

:: Due to a bug in the compiler (#492) these functions can't be defined
:: outside of the class and must be inline. As a result they must also
:: be friends (even when not otherwise necessary).
      friend bool operator==(const_iterator lhs, const_iterator rhs)
        { return( lhs.dp == rhs.dp && lhs.index == rhs.index ); }
      friend bool operator< (const_iterator lhs, const_iterator rhs)
      {
        deque::size_type xform1, xform2;
        if( lhs.index >= lhs.dp->head_index )
          xform1 = lhs.index - lhs.dp->head_index;
        else
          xform1 = (lhs.dp->deq_length - lhs.dp->head_index) + lhs.index;

        if( rhs.index >= rhs.dp->head_index )
          xform2 = rhs.index - rhs.dp->head_index;
        else
          xform2 = (rhs.dp->deq_length - rhs.dp->head_index) + rhs.index;

        return( xform1 < xform2 );
      }
      friend bool operator!=(const_iterator lhs, const_iterator rhs)
        { return( !( lhs == rhs ) ); }
      friend bool operator>=(const_iterator lhs, const_iterator rhs)
        { return( !( lhs < rhs ) ); }
      friend bool operator> (const_iterator lhs, const_iterator rhs)
        { return( rhs < lhs ); }
      friend bool operator<=(const_iterator lhs, const_iterator rhs)
        { return( !( lhs > rhs ) ); }

      const_iterator &operator+=( difference_type n );
      const_iterator &operator-=( difference_type n );
      friend const_iterator operator+( const_iterator it, difference_type n )
        { it += n; return( it ); }
      friend const_iterator operator+( difference_type n, const_iterator it )
        { it += n; return( it ); }
      friend const_iterator operator-( const_iterator it, difference_type n )
        { it -= n; return( it ); }

    private:
      const deque *dp;
      deque::size_type index;
    };

    friend class iterator;
    friend class const_iterator;

    typedef reverse_iterator< iterator >        reverse_iterator;
    typedef reverse_iterator< const_iterator >  const_reverse_iterator;

    explicit deque( const Allocator & = Allocator( ) );
    explicit deque( size_type n, const Type &value = Type( ), const Allocator & = Allocator( ) );
    deque( const deque &other );
   ~deque( );
    deque &operator=( const deque &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;      // Not required by the standard.
    bool      empty( ) const;
    void      reserve( size_type n ); // Not required by the standard.

    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_front( const Type &item );
    void     push_back( const Type &item );
    void     pop_front( );
    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( deque &x );
    void     clear( );

    bool     _Sane( ) const;  // Check invariants.

  private:
    // 1. buffer has size buf_length.
    // 2. buffer never shrinks (except in ...).
    // 3. buf_length > deq_length.
    // 4. buf_length is a power of two.
    // 5. buffer allocated with mem or a copy of mem.
    // 6. tail_index [-] head_index == deq_length (after considering wrap)
    // 7. buffer reallocated when deq_length == buf_length - 1
    //      Note: tail_index == head_index implies buffer is empty, not full.
    //
    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 deq_length;  // Number of buffer slots in use by objects.
    size_type head_index;  // Buffer position of the first object.
    size_type tail_index;  // Buffer position just past the last object.

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

  // ===================================
  // Member functions of deque::iterator
  // ===================================

  // operator++( )
  // *************
  template< class Type, class Allocator >
  typename deque< Type, Allocator >::iterator &
    deque< Type, Allocator >::iterator::operator++( )
  {
    ++index;
    if( index >= dp->buf_length ) index = 0;
    return( *this );
  }

  // operator++( int )
  // *****************
  template< class Type, class Allocator >
  typename deque< Type, Allocator >::iterator
    deque< Type, Allocator >::iterator::operator++( int )
  {
    iterator ret_value( *this );
    ++index;
    if( index >= dp->buf_length ) index = 0;
    return( ret_value );
  }

  // operator--( )
  // *************
  template< class Type, class Allocator >
  typename deque< Type, Allocator >::iterator &
    deque< Type, Allocator >::iterator::operator--( )
  {
    if( index == 0 ) {
      index = dp->buf_length - 1;
    }
    else {
      --index;
    }
    return( *this );
  }
  
  // operator--( int )
  // *****************
  template< class Type, class Allocator >
  typename deque< Type, Allocator >::iterator
    deque< Type, Allocator >::iterator::operator--( int )
  {
    iterator ret_value( *this );
    if( index == 0 ) {
      index = dp->buf_length - 1;
    }
    else {
      --index;
    }
    return( ret_value );
  }

  // operator+=( difference_type )
  // *****************************
  template< class Type, class Allocator >
  typename deque< Type, Allocator >::iterator &
    deque< Type, Allocator >::iterator::operator+=( difference_type n )
  {
    if( n >= 0 ) index = ( index + n ) % dp->buf_length;
    else {
      n = -n;
      if( index >= n ) index -= n;
      else index = dp->buf_length - ( n - index );
    }
    return( *this );
  }

  // operator-=( difference_type )
  // *****************************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::iterator &
    deque< Type, Allocator >::iterator::operator-=( difference_type n )
  {
    return( ( *this ) += -n );
  }

  // =========================================
  // Member functions of deque::const_iterator
  // =========================================

  // operator++( )
  // *************
  template< class Type, class Allocator >
  typename deque< Type, Allocator >::const_iterator &
    deque< Type, Allocator >::const_iterator::operator++( )
  {
    ++index;
    if( index >= dp->buf_length ) index = 0;
    return( *this );
  }

  // operator++( int )
  // *****************
  template< class Type, class Allocator >
  typename deque< Type, Allocator >::const_iterator
    deque< Type, Allocator >::const_iterator::operator++( int )
  {
    const_iterator ret_value( *this );
    ++index;
    if( index >= dp->buf_length ) index = 0;
    return( ret_value );
  }

  // operator--( )
  // *************
  template< class Type, class Allocator >
  typename deque< Type, Allocator >::const_iterator &
    deque< Type, Allocator >::const_iterator::operator--( )
  {
    if( index == 0 ) {
      index = dp->buf_length - 1;
    }
    else {
      --index;
    }
    return( *this );
  }
  
  // operator--( int )
  // *****************
  template< class Type, class Allocator >
  typename deque< Type, Allocator >::const_iterator
    deque< Type, Allocator >::const_iterator::operator--( int )
  {
    const_iterator ret_value( *this );
    if( index == 0 ) {
      index = dp->buf_length - 1;
    }
    else {
      --index;
    }
    return( ret_value );
  }

  // operator+=( difference_type )
  // *****************************
  template< class Type, class Allocator >
  typename deque< Type, Allocator >::const_iterator &
    deque< Type, Allocator >::const_iterator::operator+=( difference_type n )
  {
    if( n >= 0 ) index = ( index + n ) % dp->buf_length;
    else {
      n = -n;
      if( index >= n ) index -= n;
      else index = dp->buf_length - ( n - index );
    }
    return( *this );
  }

  // operator-=( difference_type )
  // *****************************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::const_iterator &
    deque< Type, Allocator >::const_iterator::operator-=( difference_type n )
  {
    return( ( *this ) += -n );
  }

  // =========================
  // Member functions of deque
  // =========================

  template< class Type, class Allocator >
  deque< Type, Allocator >::pointer
    deque< 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 );
  }

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

  // deque( size_type, const Type &, const Allocator & )
  //****************************************************
  template< class Type, class Allocator >
  deque< Type, Allocator >::deque(
    size_type n,
    const Type &value,
    const Allocator &a ) : mem( a )
  {
    buffer = alloc( n + 1, buf_length );
    try {
      uninitialized_fill_n( buffer, n, value );
    }
    catch( ... ) {
      mem.deallocate( buffer, buf_length );
      throw;
    }
    deq_length = n;
    head_index = 0;
    tail_index = n;
  }

  // deque( const deque & )
  // ************************
  template< class Type, class Allocator >
  deque< Type, Allocator >::deque( const deque &other )
    : mem( other.mem )
  {
    buffer = alloc( other.deq_length + 1, buf_length );
    bool      part1_done = false;
    size_type part1_size =  ( ( other.tail_index >= other.head_index ) ?
      other.tail_index : other.buf_length ) - other.head_index;
    try {
      pointer bookmark = uninitialized_copy(