///////////////////////////////////////////////////////////////////////////
// FILE: list (Definition of std::list)
//
//                          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
//              provides the list sequence container.
///////////////////////////////////////////////////////////////////////////
#ifndef _LIST_INCLUDED
#define _LIST_INCLUDED

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


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

#ifndef _ITERATOR_INCLUDED
    #include <iterator>
#endif

#ifndef _MEMORY_INCLUDED
    #include <memory>
#endif

namespace std {

/* ==================================================================
 * list class template
 */
template< class Type, class Allocator = allocator< Type > >
class list {
public:
    typedef Type                                value_type;
    typedef unsigned int                        size_type;
    typedef int                                 difference_type;
    typedef Allocator                           allocator_type;
    typedef typename Allocator::reference       reference;
    typedef typename Allocator::const_reference const_reference;
    typedef typename Allocator::pointer         pointer;
    typedef typename Allocator::const_pointer   const_pointer;

private:
    struct DoubleLink{
        DoubleLink* fwd;
        DoubleLink* bwd;
    };
    struct Node : public DoubleLink{
        value_type value;
        Node( value_type const & v ) : value(v) {}
    };
    DoubleLink *sentinel;   //sentinel->fwd = first element in list
                            //sentinel->bwd = last element in list
    Allocator::rebind< Node >::other mMem; //needs to be up here to stop crash
    Allocator::rebind< DoubleLink >::other dlMem;
    
public:
    explicit list( Allocator const & a = Allocator( ) )
      : mSize(0), mMem(a), dlMem(a)
    {
        sentinel = dlMem.allocate( 1 );
        sentinel->fwd = sentinel->bwd = sentinel;
    }

    list( list const& );
   ~list( );
    list &operator=( list const & );
    #ifdef _NEVER
    template< class InputIterator >
        void assign( InputIterator, InputIterator );
    #endif
    void assign( size_type, value_type const & );

    allocator_type get_allocator() const 
        { allocator_type a( mMem ); return( mMem ); }

    
    /* ------------------------------------------------------------------
     * iterators
     */
    class iterator_base {
    public:
        iterator_base( ) { }
        iterator_base( DoubleLink *d ) : self( d ) { }
        bool operator==( iterator_base it )
            { return( it.self == self ); }
        bool operator!=( iterator_base it )
            { return( it.self != self ); }
    protected:
        DoubleLink *self;
    };

    class iterator :
        public iterator_base,
        public std::iterator< std::bidirectional_iterator_tag, value_type >{
        friend class list;
    public:
        iterator( )
            : iterator_base( ) { }
        iterator( DoubleLink* d )
            : iterator_base( d ) { }
        value_type& operator*( )
            { return( static_cast< Node *>( self )->value ); }
        value_type* operator->( )
            { return( &( static_cast< Node * >( self )->value ) ); }
        iterator& operator++( )
            { self = self->fwd; return( *this ); }
        iterator& operator--( )
            { self = self->bwd; return( *this ); }
        iterator  operator++( int )
            { iterator it( *this ); operator++( ); return( it ); };
        iterator  operator--( int )
            { iterator it( *this ); operator--( ); return( it ); };
    };

    class const_iterator :
        public iterator_base,
        public std::iterator< std::bidirectional_iterator_tag, const value_type >{
        friend class list;
    public:
        const_iterator( iterator_base it )
            : iterator_base( it ) { }

        const_iterator( )
            : iterator_base( ) { }
        const_iterator( DoubleLink const* d )
            : iterator_base( const_cast< DoubleLink *>( d ) ) { }
        value_type& operator*( )
            { return( static_cast< Node const *>( self )->value ); }
        value_type* operator->( )
            { return( &( static_cast< Node const * >( self )->value ) ); }
        const_iterator& operator++( )
            { self = self->fwd; return( *this ); }
        const_iterator& operator--( )
            { self = self->bwd; return( *this ); }
        const_iterator  operator++( int )
            { const_iterator it( *this ); operator++( ); return( it ); };
        const_iterator  operator--( int )
            { const_iterator it( *this ); operator--( ); return( it ); };
    };

    typedef std::reverse_iterator< iterator >       reverse_iterator;
    typedef std::reverse_iterator< const_iterator > const_reverse_iterator;
    /*
     * end of iterators
     * ------------------------------------------------------------------ */
    
    iterator begin( )
        { return( iterator( sentinel->fwd ) ); }
    iterator end( )
        { return( iterator( sentinel ) ); }
    const_iterator begin( ) const
        { return( const_iterator( sentinel->fwd ) ); }
    const_iterator end( ) const
        { return( const_iterator( sentinel ) ); }

    reverse_iterator rbegin( )
        { return( reverse_iterator( iterator( sentinel ) ) ); }
    reverse_iterator rend( )
        { return( reverse_iterator( iterator( sentinel->fwd ) ) ); }
    const_reverse_iterator rbegin( ) const
        { return( const_reverse_iterator( const_iterator( sentinel ) ) ); }
    const_reverse_iterator rend ( ) const
        { return( const_reverse_iterator( const_iterator( sentinel->fwd ) ) ); }
    
    //capacity
    size_type  size( )  { return( mSize );      }
    bool       empty( ) { return( mSize == 0 ); }

    //element access
    reference  front( )
        { return( static_cast< Node* >( sentinel->fwd )->value ); }
    reference  back( )
        { return( static_cast< Node* >( sentinel->bwd )->value ); }

    //modifiers
    void push_front( value_type const & x )
        { push( static_cast< Node* >( sentinel->fwd ), x ); }
    void pop_front( )
        { pop( static_cast< Node* >( sentinel->fwd ) ); }
    void push_back( value_type const & x )
        { push( static_cast< Node* >( sentinel ), x ); }
    void pop_back( )
        { pop( static_cast< Node* >( sentinel->bwd ) ); }

    iterator insert( iterator, value_type const & );
    iterator erase( iterator it );
    iterator erase( iterator first, iterator last );
    void swap( list & );
    void clear( );
    void remove( value_type const & );

    void splice( iterator it, list &other );
    void splice( iterator it, list &other, iterator other_it );
    void splice( iterator it, list &other, iterator first, iterator last );

    void reverse( );

    //ow extentions
    bool _Sane( );

private:
    inline void  pop( Node* );
    inline Node* push( Node*, value_type const & );

    //Allocator::rebind< Node >::other mMem;
        //moved above constructors for the time being
        //as this seems to stop compiler crashing !?
    size_type mSize;
};

/* ------------------------------------------------------------------
 * copy ctor
 */
template< class Type, class Allocator > 
list< Type, Allocator >::list( list const& that )
  : mMem(that.mMem), dlMem(that.dlMem)
{
    sentinel = dlMem.allocate( 1 );

    DoubleLink const * o = that.sentinel;
    DoubleLink* n = sentinel;
    mSize = 0;
    while( o->fwd != that.sentinel ){
        try{
            n->fwd = mMem.allocate( 1 );
            try{
                mMem.construct( static_cast< Node* >( n->fwd ),
                                Node(static_cast< Node* >( o->fwd )->value ));
            }catch(...){
                mMem.deallocate( static_cast<Node*>( n->fwd ), 1 );
                throw;
            }
        }catch(...){
            //unwind - can't finish copy construction so remove all elements
            DoubleLink* delme;
            while( n != sentinel ){
                delme = n;
                n = n->bwd;
                mMem.destroy( static_cast< Node* >( delme ) );
                mMem.deallocate( static_cast< Node* >( delme ), 1 );
            };
            dlMem.deallocate( sentinel, 1 );
            throw;
        }
        n->fwd->bwd = n;
        n = n->fwd;
        o = o->fwd;
    };
    n->fwd = sentinel;
    sentinel->bwd = n;
    mSize = that.mSize;
}

/* ------------------------------------------------------------------
 * ~dtor
 */
template< class Type, class Allocator >
list< Type, Allocator >::~list()
{
    clear();
    dlMem.deallocate( sentinel, 1 );
}

/* ------------------------------------------------------------------
 * operator=( lst )
 * assign incoming list to this list
 */
template< class Type, class Allocator >
list< Type, Allocator > &
list< Type, Allocator >::operator=( list const & other )
{
    if( &other == this ) return( *this );

    clear( );
    const_iterator it = other.begin( );
    while( it != other.end( ) ) {
      push_back( *it );
      ++it;
    }
    return( *this );
}

#ifdef _NEVER
/* ------------------------------------------------------------------
 * assign( first, last )
 * assigns items in range [first, last) to this list
 */
template< class Type, class Allocator >
template< class InputIterator >
void list< Type, Allocator >::assign(
    InputIterator first,
    InputIterator last )
{
    clear( );
    while( first != last ) {
        push_back( *first );
        ++first;
    }
}
#endif

/* ------------------------------------------------------------------
 * assign( n, v )
 * assigns n copies of v to this list
 */
template< class Type, class Allocator >
void list< Type, Allocator >::assign( size_type n, value_type const &v )
{
    clear( );
    for( size_type i = 0; i < n; ++i ) {
        push_back( v );
    }
}

/* ------------------------------------------------------------------
 * insert( i, x )
 * insert type x in list just before element identified by iterator i
 */
template< class Type, class Allocator >
list< Type, Allocator >::iterator
list< Type, Allocator >::insert( iterator it, Type const & x )
{
    Node* n = push( static_cast< Node* >( it.self ), x );
    return iterator( n );
}

/* ------------------------------------------------------------------
 * erase( i )
 * erase element identified by iterator i
 */
template< class Type, class Allocator >
list< Type, Allocator >::iterator
list< Type, Allocator >::erase( iterator it )
{
    iterator temp( it );
    ++temp;
    pop( static_cast< Node * >( it.self ) );
    return( temp );
}

/* ------------------------------------------------------------------
 * erase( first, last )
 * erase all list items in range [first, last)
 */
template< class Type, class Allocator >
list< Type, Allocator >::iterator
list< Type, Allocator >::erase( iterator first, iterator last )
{
    while( first != last ) {
        first = erase( first );
    }
    return( last );
}

/* ------------------------------------------------------------------
 * swap
 * swaps two lists
 */
template< class Type, class Allocator >
void list< Type, Allocator >::swap( list &other )
{
  DoubleLink *sen_temp( sentinel );
  sentinel = other.sentinel;
  other.sentinel = sen_temp;

  Allocator::rebind< Node >::other m_temp( mMem );
  mMem = other.mMem;
  other.mMem = m_temp;

  Allocator::rebind< DoubleLink >::other dl_temp( dlMem );
  dlMem = other.dlMem;
  other.dlMem = dl_temp;

  size_type siz_temp( mSize );
  mSize = other.mSize;
  other.mSize = siz_temp;
}

/* ------------------------------------------------------------------
 * clear
 * remove all elements
 */
template< class Type, class Allocator >
void list< Type, Allocator >::clear()
{
    Node* n;
    Node* delme;
    n = ( Node* )sentinel->fwd;
    while( n != ( Node* )sentinel ){
        delme = n;
        n = ( Node* )n->fwd;
        mMem.destroy( delme );
        mMem.deallocate( delme, 1 );
    };
    sentinel->fwd = sentinel->bwd = sentinel;
    mSize = 0;
}

/* ------------------------------------------------------------------
 * remove( v )
 * remove all occurances of v in the list.
 */
template< class Type, class Allocator >
void list< Type, Allocator >::remove( value_type const &v )
{
    iterator it( begin( ) );
    while( it != end( ) ) {
        if( *it == v ) it = erase( it );
        else ++it;
    }
}

/* ------------------------------------------------------------------
 * splice( it, other )
 * splices the entire contents of other before it
 */
template< class Type, class Allocator >
void list< Type, Allocator >::splice( iterator it, list &other )
{
    if( other.mSize == 0 ) return;
    DoubleLink *head = other.sentinel->fwd;
    DoubleLink *tail = other.sentinel->bwd;
    //do the splice
    head->bwd = it.self->bwd;
    it.self->bwd->fwd = head;
    tail->fwd = it.self;
    it.self->bwd = tail;
    //fix up other's sentinel
    other.sentinel->fwd = other.sentinel;
    other.sentinel->bwd = other.sentinel;
    //fix up list sizes
    mSize += other.mSize;
    other.mSize = 0;
}

/* ------------------------------------------------------------------
 * splice( it, other, other_it )
 * splices *other_it before it
 */
template< class Type, class Allocator >
void list< Type, Allocator >::splice(
    iterator it,
    list    &other,
    iterator other_it )
{
    if( it.self == other_it.self ||
        it.self == other_it.self->fwd ) return;
    //do the splice
    DoubleLink *spliced_node = other_it.self;
    spliced_node->bwd->fwd = spliced_node->fwd;
    spliced_node->fwd->bwd = spliced_node->bwd;
    spliced_node->bwd = it.self->bwd;
    it.self->bwd->fwd = spliced_node;
    spliced_node->fwd = it.self;
    it.self->bwd = spliced_node;
    //fix up list sizes
    mSize++;
    other.mSize--;
}

/* ------------------------------------------------------------------
 * splice( it, other, first last )
 * splices [first, last) before it
 */
template< class Type, class Allocator >
void list< Type, Allocator >::splice(
    iterator it,
    list    &other,
    iterator first,
    iterator last )
{
    size_type count = 0;
    for( iterator i( first ); i != last; ++i ) ++count;
    if( count == 0 ) return;
    DoubleLink *head = first.self;
    DoubleLink *tail = last.self->bwd;
    //do the splice
    head->bwd->fwd = tail->fwd;
    tail->fwd->bwd = head->bwd;
    head->bwd = it.self->bwd;
    it.self->bwd->fwd = head;
    tail->fwd = it.self;
    it.self->bwd = tail;
    //fix up list sizes
    mSize += count;
    other.mSize -= count;    
}

/* ------------------------------------------------------------------
 * reverse( )
 * reverses the elements in the list
 */
template< class Type, class Allocator >
void list< Type, Allocator >::reverse( )
{
    DoubleLink *temp;
    //(carefully) reverse pointers in each node
    DoubleLink *current = sentinel->fwd;
    while( current != sentinel ) {
        temp = current->fwd;
        current->fwd = current->bwd;
        current->bwd = temp;
        current = temp;
    }
    //reverse pointers in sentinel (to flip head and tail of list)
    temp = sentinel->fwd;
    sentinel->fwd = sentinel->bwd;
    sentinel->bwd = temp;
}

/* ------------------------------------------------------------------
 * push( node*, x ) (private)
 * insert type x in list just before element identified by node* 
 */
template< class Type, class Allocator >
list< Type, Allocator >::Node*
list< Type, Allocator >::push( Node* o, Type const & x )
{
    Node* n = mMem.allocate( 1 );
    try{
        mMem.construct( n, Node(x) );
    }catch( ... ){
        mMem.deallocate( n, 1 );
        throw;
    }
    n->fwd = o;
    n->bwd = o->bwd;
    o->bwd->fwd = n;
    o->bwd = n;
    ++mSize;
    return( n );
}

/* ------------------------------------------------------------------
 * pop( Node* ) (private)
 * remove (destroy and deallocate) an element
 */
template< class Type, class Allocator >
void list< Type, Allocator >::pop( Node* n )
{
    n->fwd->bwd = n->bwd;
    n->bwd->fwd = n->fwd;
    mMem.destroy( n );
    mMem.deallocate( n, 1 );
    --mSize;
}

/* ------------------------------------------------------------------
 * _Sane( )
 * returns true if invariants check out ok
 */
template< class Type, class Allocator >
bool
list< Type, Allocator >::_Sane( )
{
    //sentinel can't have null links
    if( !sentinel->fwd || !sentinel->bwd ) return( false );
    
    DoubleLink* d = sentinel->fwd;
    size_type c = 0;
    
    while( d != sentinel ){
        c++;
        //if exceeded size, something is wrong so abort now
        if( c > mSize) return( false );

        if( !(d->fwd) || !(d->bwd) ) return( false );  //can't have null links
        if( d->bwd->fwd != d ) return( false );        //broken links
        if( d->fwd->bwd != d ) return( false );        //broken links
        d = d->fwd;
    };
    if( c != mSize ) return( false );                  //check size
    return( true );
}

}; // End of namespace std.

#endif
