///////////////////////////////////////////////////////////////////////////
// FILE: list (Definition of std::list)
//
//                          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
//              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

#ifndef _TYPE_TRAITS_INCLUDED
    #include <type_tra>
#endif

#ifndef _FUNCTIONAL_INCLUDED
    #include <function>
#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;
    }
    explicit list( size_type, Type const &, Allocator const & = Allocator() );
    // note compiler feature missing 
    // function templates can't have default params
    // also has to be inline as doesn't understand syntax otherwise
    template< class InputIt >
    list( InputIt f, InputIt l, Allocator const & a )// = Allocator() )
        : mSize(0), mMem(a), dlMem(a)
    {
        sentinel = dlMem.allocate( 1 );
        sentinel->fwd = sentinel->bwd = sentinel;
        helper_assign( f, l, tr1::is_integral<InputIt>::type() );
    }
    
    list( list const& );
   ~list( );
    list &operator=( list const & );
    
    template< class InputIterator >
    void assign( InputIterator f, InputIterator l )
    {
        clear();
        helper_assign( f, l, tr1::is_integral<InputIterator>::type() );
    }

    void assign( size_type, value_type const & );

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

    
    /* ------------------------------------------------------------------
     * iterators
     */
    class iterator_base {
    public:
        iterator_base( ) { }
        iterator_base( DoubleLink *d ) : self( d ) { }
        bool operator==( iterator_base const it ) const
            { return( it.self == self ); }
        bool operator!=( iterator_base const it ) const
            { 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 ) { }
        reference operator*( ) const
            { return( static_cast< Node *>( self )->value ); }
        value_type* operator->( ) const
            { 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( )  const { return( mSize );      }
    bool       empty( ) const { 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 & );
    void insert( iterator, size_type, value_type const & );
    template< class InputIt >
    void insert( iterator p, InputIt f, InputIt l )
    {
        helper_insert( p, f, l, tr1::is_integral<InputIt>::type() );
    }
    
    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( );
    void merge( list &other );

    //ow extentions
    bool _Sane( );

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

    /* --------------------------------------------------------------
     * these ones are called when InputIt isn't an integer type
     */
    template< class InputIt >
    void helper_assign( InputIt f, InputIt l, tr1::true_type )
    {
        for( int i = 0; i < static_cast< size_type >( f ); i++ ){
            push_back( static_cast< value_type >( l ) );
        }
    }
    template< class InputIt >
    void helper_insert( iterator i, InputIt f, InputIt l, tr1::true_type )
    { 
        for( size_type n = static_cast< size_type >(f); n > 0; n-- ){
            push( static_cast< Node* >( i.self ),
                  static_cast< value_type >(l) );
        }
    }
    /* --------------------------------------------------------------
     * these ones are called when InputIt is not an integer type 
     */
    template< class InputIt >
    void helper_assign( InputIt f, InputIt l, tr1::false_type )
    {
        for( ; f != l; ++f ) push_back( *f );
    }
    template< class InputIt >
    void helper_insert( iterator p, InputIt f, InputIt l, tr1::false_type )
    {
        // this could probably be optimised to remove
        // unnecessary link rewriting when inserting lots of things
        for( ; f != l; ++f, ++p ) p = insert( p, *f );
    }

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


    // ---------------------------------------------------------------
    // SORT Add-ons by Alexey Kovalenko.
    //
    // recursive merge sort for double-linked list
    // time_optimized, not memory-.
    //
public:
    //Sorts self according to the operator <.
    //sort maintains the relative order of equal elements.

    void sort( )
    {
        if( size() > 1 ) _merge_sort( sentinel->fwd, sentinel->bwd,
                                      size()-1, less< value_type >() );
    }

    template< class Compare >
    void sort( Compare comp )
    {
        if( size() > 1 ) _merge_sort( sentinel->fwd, sentinel->bwd,
                                      size()-1, comp);
    }

private:
    // internal sort module
    template< class Compare >
    void _merge_sort( DoubleLink * first, DoubleLink * last,
                      size_type _distance, Compare comp )
    // first, last - pointers in chain
    // _distance - internal value, distance between first and last,
    //             for first call, it's a size()-1
    // comp - compare function, usually less< value_type >
    //
    // _distance introduced for simplification of calculating the middle of
    // given list's range. I's number of steps to go from first to last.
    // 1 element  in range - _distance is 0
    // 2 elements in range - _distance is 1
    // etc
    //
    // Here we can't make inexpensive check, what _distance
    // corresponds with (last - first).
    // So, using guard check in loop :(
    //
    {
        if( first != last ) // is it one-element list?
        {
            // anchors beyond list borders.
            DoubleLink * first_bwd = first->bwd;
            DoubleLink * last_fwd = last->fwd;
            DoubleLink * middle = first;
            DoubleLink * l2begin = NULL;
            size_type middle_pos = _distance / 2;
            
            // meaning middle = (first + last) / 2
            
            // 2 elements: _distance == 1
            // middle_pos == 0
            // middle == first
            
            // 3 elements: _distance == 2
            // middle_pos == 1
            // middle == first+1
            
            // 4 elements: _distance == 3
            // middle_pos == 1
            // middle == first+1
            
            // etc.
            // moving throw links
            while( ( middle_pos >= 1) && (middle != last) ) {
                middle = middle->fwd;
                middle_pos-=1;
            }
            // Here middle_pos may be not zero. It means, what rounding errors make
            // such binary cut innacurate. Redo it more nicely.
            if( middle_pos ) {
                _distance = _distance / 2 - middle_pos;
                middle_pos = _distance / 2;
                middle = first;
                // moving throw links. Again.
                while( ( middle_pos >= 1) && (middle != last) ) {
                    middle = middle->fwd;
                    middle_pos-=1;
                }
            }
    
            if( _distance > 0 ) {
                // two recursive calls for two subranges
                l2begin = middle->fwd;
                _merge_sort(first, middle, (size_type)_distance/2, comp );
                middle = l2begin->bwd; // can change
                _merge_sort( l2begin, last,(size_type) (_distance - _distance/2 - 1), comp);
                //l2begin = middle->fwd;// can change
                first = first_bwd->fwd; // can change
                last = last_fwd->bwd;   // can change
            }
            _merge_lists( first, middle, /*middle->fwd,*/ last, comp );
        }
        return;
    };
    
    //
    // merge two ajacent sorted ranges in one sorted
    // first is start, middle is end of first subrange (so as middle->fwd is start of
    // other subrange), last is end.
    //
    template< class Compare >
    void _merge_lists( DoubleLink * first, DoubleLink * middle,
                       DoubleLink * last, Compare comp )
    {
        DoubleLink *list1 = first;
        DoubleLink *list2 = middle->fwd;
        DoubleLink *list2end = last->fwd;
        DoubleLink *temp_l2next = NULL;
        
        if( first == last ) return; /* just guard for 1-element lists */
        
        //compare elements on both lists as long as possible.
        do{ // while( (list2 != list2end)  && (list1 != list2) )
            while( !comp( static_cast< Node * >( list2 )->value,
                          static_cast< Node * >( list1 )->value ) ) {
                list1 = list1->fwd;
                if( list1 == list2 ) return;
            }
            
            // *list2 is less than *list1
            // move *list2 _before_ *list1
            temp_l2next = list2->fwd; // store list2 next value
            if( list1->fwd == list2 ) { // ajacent list elements
                list2->bwd      = list1->bwd;
                list1->bwd->fwd = list2;
                list2->fwd->bwd = list1;
                list1->fwd      = list2->fwd;
                list1->bwd      = list2;
                list2->fwd      = list1;
            }else{ // non-ajacent elements
                list2->bwd->fwd = list2->fwd;
                list2->fwd->bwd = list2->bwd;
                list1->bwd->fwd = list2;
                list2->bwd      = list1->bwd;
                list2->fwd      = list1;
                list1->bwd      = list2;
            } // non-ajacent
            list2 = temp_l2next;
        }while( (list2 != list2end) && (list1 != list2) /*guards*/ &&
                (list2 != sentinel) && (list1 != sentinel) );
        return;
    };
    // end of sort code by Alexey Kovalenko.
    // ---------------------------------------------------------------
};

/* ------------------------------------------------------------------
 * ctor( Allocator )
 * construct empty list
 */
/*err, this only seems to work inlined, whats going on?
template< class Type, class Allocator >
list< Type, Allocator >::list( Allocator const & a )
    : mSize(0), mMem(a), dlMem(a)
{
    sentinel = dlMem.allocate( 1 );
    sentinel->fwd = sentinel->bwd = sentinel;
}
*/
/* ------------------------------------------------------------------
 * ctor( size_type, Type, Allocator )
 * construct with n copies of t
 */
template< class Type, class Allocator > 
list< Type, Allocator >::list( size_type n, Type const & t,
                               Allocator const & a )
    : mSize(0), mMem(a), dlMem(a)
{
    sentinel = dlMem.allocate( 1 );
    sentinel->fwd = sentinel->bwd = sentinel;
    for( int i = 0; i < n; i++ ){
        push_back( t );
    }
}

/* ------------------------------------------------------------------
 * 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
// has to be inline as compiler doesn't understand this syntax yet
/* ------------------------------------------------------------------
 * 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 );
}


/* ------------------------------------------------------------------
 * insert( iterator i, size_type n, x )
 * insert type x n times in list just before element identified by iterator i
 */
template< class Type, class Allocator >
void list< Type, Allocator >::insert( iterator i, size_type n,
                    value_type const & x )
{
    while( n > 0 ){
        push( static_cast< Node* >( i.self ), x );
        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;
}

/* ------------------------------------------------------------------
 * merge( list & )
 * Merges the argument list into this list. No nodes are created or
 * destroyed during this process. Only pointers and counters are
 * changed.
 */
template< class Type, class Allocator >
void list< Type, Allocator >::merge( list &other )
{
  DoubleLink *temp_link;
  size_type   temp_size;

  if( other.mSize == 0 ) return;
  if( mSize == 0 ) {
    temp_link      = sentinel;
    sentinel       = other.sentinel;
    other.sentinel = temp_link;
    temp_size      = mSize;
    mSize          = other.mSize;
    other.mSize    = temp_size;
  }

  DoubleLink *list1 = sentinel->fwd;
  DoubleLink *list2 = other.sentinel->fwd;

  //compare elements on both lists as long as possible.
  while( list1 != sentinel && list2 != other.sentinel ) {
    if( !( static_cast< Node * >( list2 )->value <
           static_cast< Node * >( list1 )->value ) ) {
      list1 = list1->fwd;
    }
    else {
      list1->bwd->fwd = list2;
      temp_link       = list1->bwd;
      list1->bwd      = list2;
      list2->bwd->fwd = list2->fwd;
      list2->fwd->bwd = list2->bwd;
      list2           = list2->fwd;
      list1->bwd->fwd = list1;
      list1->bwd->bwd = temp_link;
      mSize++;
      other.mSize--;
    }
  }

  //deal with the tail end of list2 (if anything is left).
  if( list2 != other.sentinel ) {
    list1 = sentinel->bwd;
    list1->fwd               = list2;
    list2->bwd               = list1;
    sentinel->bwd            = other.sentinel->bwd;
    other.sentinel->bwd->fwd = sentinel;
    other.sentinel->bwd      = other.sentinel;
    other.sentinel->fwd      = other.sentinel;
    mSize += other.mSize;
    other.mSize = 0;
  }
}

/* ------------------------------------------------------------------
 * push( Node*, x ) (private)
 * insert copy of 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