///////////////////////////////////////////////////////////////////////////
// FILE: list (Definition of std::forward_list)
//
// =========================================================================
//
//                          Open Watcom Project
//
// Copyright (c) 2004-2014 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.
///////////////////////////////////////////////////////////////////////////
#ifndef _FORWARD_LIST_INCLUDED
#define _FORWARD_LIST_INCLUDED

#ifndef _ENABLE_AUTODEPEND
 #pragma read_only_file;
#endif

#ifndef __cplusplus
 #error This header file requires C++
#endif

#ifndef _ITERATOR_INCLUDED
 #include <iterator>
#endif

#ifndef _MEMORY_INCLUDED
 #include <memory>
#endif

#ifndef _TYPE_TRAITS_INCLUDED
 #include <type_tra>
#endif

#ifndef _LIMITS_INCLUDED
 #include <limits>
#endif

#ifndef _FUNCTIONAL_INCLUDED
 #include <function>
#endif

#ifndef __META_H_INCLUDED
 #include <_meta.h>
#endif

namespace std {

    template< class T, class A  = allocator< T > >
    class forward_list{
    public:
        typedef T                           value_type;
        typedef typename A::size_type       size_type;
        typedef typename A::difference_type difference_type;
        typedef A                           allocator_type;
        typedef typename A::reference       reference;
        typedef typename A::const_reference const_reference;
        typedef typename A::pointer         pointer;
        typedef typename A::const_pointer   const_pointer;
    private:
        struct Node;
        typedef typename A::rebind<Node>::other::pointer n_ptr;
        struct Node {
            n_ptr fwd;
            T value;
            Node( T const & v ) : value( v ) { }
        };
        A::rebind<Node>::other nmem;

        //---------------------------------------------------------------
        // iterators
        // todo: move definition outside class
        struct iterator_base:
            public std::iterator< forward_iterator_tag, T > {
            n_ptr self;
            iterator_base( n_ptr x ) : self(x){}
            iterator_base( ) : self(0) {}
            iterator_base( iterator_base const & that ) { self = that.self; }
            bool operator==( iterator_base const & that ){ return( self == that.self ); }
            bool operator!=( iterator_base const & that ){ return( self != that.self ); }
        };
    public:
        struct const_iterator;
        struct iterator :
            public iterator_base,
            public std::iterator< forward_iterator_tag, value_type, difference_type, pointer, reference > {
            iterator( n_ptr x ) : iterator_base( x ) {}
            iterator( ) : iterator_base () {}
            iterator& operator++() { self = self->fwd; return *this; }
            iterator operator++( int ) { iterator old = *this; self = self->fwd; return old; }
            reference operator*() { return( self->value ); }
        };
        struct const_iterator:
            public iterator_base,
            public std::iterator< forward_iterator_tag, value_type const, difference_type, const_pointer, const_reference > {
            const_iterator( n_ptr x ) : iterator_base( x ) {}
            const_iterator( ) : iterator_base () {}
            const_iterator( forward_list::iterator const & that ) : iterator_base( that.self ){}
            const_iterator& operator++() { self = self->fwd; return *this; }
            const_iterator operator++( int ) { const_iterator old = *this; self = self->fwd; return old; }
            const_reference operator*(){ return( self->value ); }
        };
        // end of iterators
        //-----------------------------------------------------------------

    public:
        // construct/copy/destroy
        explicit forward_list( A const & a = A() ) : mSize(0), nmem(a) { first = NULL; }
        explicit forward_list( size_type );
        forward_list( size_type, T const &, A const & = A() );
        template< class InputIt > forward_list( InputIt f, InputIt l )//, A const & = A() )
            : mSize( 0 ), first( 0 )
            { helper_assign( f, l, is_integral< InputIt >::type() ); }
        forward_list( forward_list<T,A> const & );
        //forward_list( forward_list&& );
        ~forward_list(){ clear(); }
        forward_list<T,A>& operator=( forward_list<T,A> const & );
        //forward_list<T,A>& operator=( forward_list<T,A> && );
        template < class InputIt > void assign( InputIt f, InputIt l )
            { helper_assign( f, l, is_integral< InputIt >::type() ); }
        void assign( size_type, T const & );
        allocator_type get_allocator() const { allocator_type a(nmem); return( a ); }

        // iterators
        iterator        begin() { return( iterator( first ) ); }
        const_iterator  begin() const { return( const_iterator( first ) ); }
        iterator        end(){ return( iterator( 0 ) ); }
        const_iterator  end() const { return( const_iterator( 0 ) ); }
        const_iterator  cbegin() const { return( const_iterator( first ) ); }
        const_iterator  cend() const{ return( const_iterator( 0 ) ); }
        iterator        previous( iterator it )
            { return( previous(it.self) ); } //special for SLL
        const_iterator  previous( const_iterator it ) const
            { return( previous(it.self) ); }; //special for SLL

        // capacity
        bool        empty() const { return( mSize == 0 ); }
        size_type   size() const { return mSize; }
        size_type   max_size() const;
        void        resize( size_type, T );
        void        resize( size_type s ) { resize( s, T() ); }

        // access
        reference       front() { return( first->value ); }
        const_reference front() const { return( first->value ); }

        // modifiers
        void pop_front();
        void push_front( T const & v );
        //template< class... Args> void push_front( Args&&... );
        //template < class... Args> iterator emplace( const_iterator, ARgs&&... );
        iterator insert( const_iterator, T const & );
        //iterator insert( const_iterator, T&& );
        void insert( const_iterator, size_type, T const & );
        template< class InputIt >
        void insert( const_iterator it, InputIt f, InputIt l )
            { helper_insert( it, f, l, is_integral< InputIt >::type() ); }
        iterator insert_after( const_iterator, T const & ); //special for SLL
        void insert_after( const_iterator, size_type, T const & );
        template< class InputIt >
        void insert_after( const_iterator it, InputIt f, InputIt l )
            { helper_insert_after( it, f, l, is_integral< InputIt >::type() ); }

        iterator erase( const_iterator );
        iterator erase( const_iterator, const_iterator );
        iterator erase_after( const_iterator ); //special for SLL
        iterator erase_after( const_iterator, const_iterator ); //special for SSL
        //void swap( forward_list<T,A>&& );
        void swap( forward_list<T,A>& );
        void clear();

        //operations
        void splice( const_iterator, forward_list& );
        void splice( const_iterator, forward_list&, const_iterator );
        //void splice( const_iterator, forward_list<T,A>&&, const_iterator, const_iterator);
        void splice_after( const_iterator pos, forward_list&, const_iterator prev );
        void splice_after( const_iterator pos, forward_list&,
                           const_iterator before_first,
                           const_iterator before_last );
        void remove( T const& );
        void unique() { unique( equal_to< T >() ); }
        void merge( forward_list<T,A>& other ) { merge( other, less< T >() ); }
        void sort() { sort( less< T >() ); }
        void reverse();

        template< class U, class V >
        friend bool operator==( forward_list<U,V> const & a, forward_list<U,V> const & b );
        template< class U, class V >
        friend bool operator!=( forward_list<U,V> const & a, forward_list<U,V> const & b );
        template< class U, class V >
        friend bool operator<=( forward_list<U,V> const & a, forward_list<U,V> const & b );
        template< class U, class V >
        friend bool operator>=( forward_list<U,V> const & a, forward_list<U,V> const & b );
        template< class U, class V >
        friend bool operator<( forward_list<U,V> const & a, forward_list<U,V> const & b );
        template< class U, class V >
        friend bool operator>( forward_list<U,V> const & a, forward_list<U,V> const & b );

        //OW special
        bool _Sane();

        /* ------------------------------------------------------------------
         * remove_if( Predicate )
         * inline due to missing compiler feature
         * exception safety: strong only if Predicate can't throw
         */
        template< class Predicate >
        void remove_if( Predicate pred )
        {
            n_ptr p = first;
            n_ptr n = first;
            while( n != 0 ) {
                if( pred( n->value ) != false ) {
                    if( n == first ) {
                        first = n->fwd;
                        nmem.destroy( n );
                        nmem.deallocate( n, 1 );
                        --mSize;
                        p = n = first;
                    }
                    else {
                        p->fwd = n->fwd;
                        nmem.destroy( n );
                        nmem.deallocate( n, 1 );
                        --mSize;
                        n = p->fwd;
                    }
                }
                else {
                    p = n;
                    n = n->fwd;
                }
            }
        }

        /* ------------------------------------------------------------------
         * unique( BinaryPredicate )
         * inline due to missing compiler feature
         * exception safety: nothing only if Predicate can't throw
         */
        template< class Predicate >
        void unique( Predicate cmp )
        {
            n_ptr p = first;
            n_ptr n = p->fwd;
            while( p && n ) {
                if( cmp( n->value, p->value ) ) {
                    n_ptr del = n;
                    p->fwd = n->fwd;
                    nmem.destroy( del );
                    nmem.deallocate( del, 1 );
                    --mSize;
                }
                else {
                    p = p->fwd;
                }
                n = p->fwd;
            }
        }

        /* ------------------------------------------------------------------
         * merge( forward_list, compare )
         * inline due to missing compiler feature
         * exception saftey: to do, what can throw?
         */
        template< class Compare >
        void merge( forward_list<T,A>& other, Compare cmp )
        {
            n_ptr o = other.first;
            n_ptr t = first;
            n_ptr m = first;
            // do first element
            if( !o ) return;
            if( o && !t ) {
                first = other.first;
                other.first = 0;
                mSize = other.mSize;
                other.mSize = 0;
                return;
            }
            if( cmp( o->value, t->value ) ) {
                first = o;
                m = o;
                o = o->fwd;
            }
            else {
                t = t->fwd;
            }
            // do main block
            while( o && t ) {
                if( cmp( o->value, t->value ) ) {
                    m->fwd = o;
                    m = m->fwd;
                    o = o->fwd;
                }
                else {
                    m->fwd = t;
                    m = m->fwd;
                    t = t->fwd;
                }
            }

            // do tails
            if( o ) m->fwd = o;
            if( t ) m->fwd = t;

            // fix sizes and unlink other
            mSize += other.mSize;
            other.mSize = 0;
            other.first = 0;
        }

        /* ------------------------------------------------------------------
         * sort( compare )
         * inline due to missing compiler feature
         *
         * following is a list of reasons for the features used in this vesion
         * of merge sort:
         * > iterative :
         *          to over come additional call overhead of iterative version
         *          and give the optimiser more of a chance to do it's stuff
         * > same walk order as an iterative implementation :
         *          use an explicit stack to keep track of data so nodes are
         *          visited as if it were iterative, this gives good (optimal?)
         *          cache usage as there is good locality of visiting the nodes
         * > take as much sorted list in one go:
         *          instead dividing down to list of size 1 and then merging
         *          take as much sorted list as possible in one go and then merge
         *          these sublist.  This gives a massive improvement on
         *          lists that are already (partially) sorted in exchange for
         *          a few (my limited testing surgests 2-5%) extra comparisions
         *          when presented with random data
         *
         * Before changing this algorithm do some benchmarking to prove improvements
         *
         * exception safety: to do: what can throw???
         */
        template< class Compare >
        void sort( Compare cmp )
        {
            if( mSize < 2 ) return;
            
            struct StackData {
                n_ptr data;
                int depth;
            };

            // Ideally stack would be log2 of current container size
            // but don't want dynamic alloc overhead, thus a little memory
            // is wasted here but in most cases it will be insignificant.
            // Do log2 of max_size() instead - this is currently making
            // somewhat dodgey assumptions
            StackData stack[ numeric_limits< difference_type >::digits -
                             ::_ow::log2_floor< sizeof( T ) >::value ];
            int top = 0; // index the empty top element which is next to be filled
            bool input_done = false;
            n_ptr input = first; // keep track of next element of unsorted data

            do {
                if( (top >= 2 && stack[top-1].depth == stack[top-2].depth) || input_done ) {
                    // merge top two
                    n_ptr a,b,prev,merged;
                    a = stack[top-2].data;
                    b = stack[top-1].data;

                    // compare the first a or b separately to set up head
                    if( cmp( b->value, a->value ) ) {
                        merged = b;
                        prev = b;
                        b = b->fwd;
                    }
                    else {
                        merged = a;
                        prev = a;
                        a = a->fwd;
                    }
                    // add next a or b in turn until one is exhausted
                    while( a && b ) {
                        if( cmp( b->value,  a->value ) ) {
                            // move b into place location
                            prev->fwd = b;
                            prev=prev->fwd;
                            b = b->fwd;
                        }
                        else {
                            // move a into merged list
                            prev->fwd = a;
                            prev=prev->fwd;
                            a = a->fwd;
                        }
                    }
                    // link in tails
                    if( a ) prev->fwd = a;
                    if( b ) prev->fwd = b;

                    // replace stack entry
                    stack[top-2].data = merged;
                    stack[top-2].depth++;
                    top--;
                }
                else { // top < 2 || stack[top].depth != stack[top-1].depth
                       // get another piece of sorted input data
                    n_ptr fst = input;
                    n_ptr next = input->fwd;
                    n_ptr temp;
                    int c = 1;
                    while( next != 0 ) {
                        if( !cmp( next->value, input->value ) ) { // next>=input
                            c++;
                            input = next;
                            next = next->fwd;
                        }
                        else if( c == 1 ) {
                            // swap two elements
                            fst = next;
                            temp = next->fwd;
                            next->fwd = input;
                            next = temp;
                            input->fwd = next;
                            c = 2;
                            //#define _SLIST_do_place3 //this doesn't improve matters
#ifndef _SLIST_do_place3
                            break;
#endif
#ifdef _SLIST_do_place3
                        }
                        else if( c == 2 ) {
                            // only one more compare needed to insert third
                            // element in correct place so we might as well do it
                            temp = next->fwd;
                            if( !cmp( next->value, fst->value ) ) {
                                next->fwd = input;
                                fst->fwd = next;
                            }
                            else {
                                next->fwd = fst;
                                fst = next;
                            }
                            next = temp;
                            break;
#undef _SLIST_do_place3
#endif
                        }
                        else { // input > next, finish sublist
                            break;
                        }
                    }
                    input->fwd = 0; // mark end of subsection
                    input = next;   // set ready for next bit of list
                    if( next == 0 ) input_done = true;
                    // push onto stack
                    stack[top].data = fst;
                    stack[top].depth = 1;
                    ++top;
                }
            } while( top != 1 || !input_done );
            first = stack[0].data;
        }

    private:
        size_type mSize;    // so counting is fast
        n_ptr first;        // single linked listed with first element held here (no sentinals)
        inline n_ptr previous( n_ptr ) const;   // find previous node
        inline n_ptr copy( n_ptr, size_type );  // copy a number of nodes
        inline n_ptr make( size_type, T const &, n_ptr& );  // make a number of new nodes

        /* ------------------------------------------------------------------
         * make_from
         * make a list of nodes holding [ *f, *l )
         * set c to number of elements and ft to first node and return last node
         * for use by strong safe functions
         */
        template< class InputIt > n_ptr make_from( InputIt f, InputIt l, n_ptr& ft, size_type & c )
        {
            n_ptr n, p;
            ft = 0;
            c = 0;
            if( f == l ) return( 0 );
            try {
                // do first element
                ft = nmem.allocate( 1 );
                nmem.construct( ft, Node(*f) );
                c++;
                ++f;
                p = ft;
                // do the rest
                while( f != l ) {
                    n = nmem.allocate( 1 );
                    nmem.construct( n, Node(*f) );
                    c++;
                    ++f;
                    p->fwd = n;
                    p = n;
                }
            }
            catch( ... ) {
                while( ft ) {
                    n = ft->fwd;
                    if( c-- ) nmem.destroy( ft ); // possibly alloc ok but construct failed
                    nmem.deallocate( ft, 1 );
                    ft = n;
                }
            }
            n->fwd = 0;
            return( n );
        }

        /* ------------------------------------------------------------------
         * helper functions that are overloaded so can be called depending on InputIt type
         * have to be inline at mo due to compiler
         * exception safety: strong (although standard says multi inserts don't have to be)
         */
        template< class InputIt >
        void helper_assign( InputIt f, InputIt l, true_type )
        {
            //cout<<"true_type\n";
            assign( static_cast<size_type>(f), static_cast<T const>(l) );
        }
        template< class InputIt >
        void helper_assign( InputIt f, InputIt l, false_type )
        {
            //cout<<"false_type\n";
            size_type c;
            n_ptr temp;
            make_from( f, l, temp, c );
            // exception safe
            clear();
            first = temp;
            mSize = c;
        }
        template< class InputIt >
        void helper_insert( const_iterator it, InputIt f, InputIt l, true_type )
        {
            //cout<<"insert true\n";
            insert( it, static_cast<size_type>(f), static_cast<T const>(l) );
        }
        template< class InputIt >
        void helper_insert( const_iterator cit, InputIt f, InputIt l, false_type )
        {
            //cout<<"insert false\n";
            size_type c;
            n_ptr n;
            n_ptr e = make_from( f, l, n, c );

            if( cit.self == first ) {
                e->fwd = first;
                first = n;
            }
            else {
                n_ptr p = previous( cit.self );
                p->fwd = n;
                e->fwd = cit.self;
            }
            mSize += c;
        }
        template< class InputIt >
        void helper_insert_after( const_iterator it, InputIt f, InputIt l, true_type )
        {
            //cout<<"insert after true\n";
            insert_after( it, static_cast<size_type>(f), static_cast<T const>(l) );
        }
        template< class InputIt >
        void helper_insert_after( const_iterator cit, InputIt f, InputIt l, false_type )
        {
            //cout<<"insert after false\n";
            size_type c;
            n_ptr n;
            n_ptr e = make_from( f, l, n, c );
            e->fwd = (cit.self)->fwd;
            (cit.self)->fwd = n;
            mSize += c;
        }

    }; //end class forward_list

    /* ------------------------------------------------------------------
     * previous(n_ptr) private
     * used by previous( iterator ), previous( const_iterator ) and internally
     * not explicit from sgi docs what previous( begin() ) should return
     * sgi code uses a header node so ++previous( begin() ) = begin()
     * we will not allow previous( begin() ), but this implementation will
     * actually return end()
     */
    template< class T, class A >
    inline
    forward_list<T,A>::n_ptr forward_list<T,A>::previous( n_ptr n ) const
    {
        n_ptr p = first;
        while( (p != 0) && (p->fwd != n ) ) p = p->fwd;
        return( p );
    }

    /* ------------------------------------------------------------------
     * copy( n_ptr, size_type )
     * helper to make copy chain of links
     * unwinds on exception for use by other strong excption safe methods
     * returns ptr to first in new chain
     */
    template< class T, class A >
    forward_list<T,A>::n_ptr forward_list<T,A>::copy( n_ptr src, size_type i )
    {
        n_ptr dst = 0;
        if( src == 0 ) return dst;
        //do the first element separately
        size_type a = 0;
        size_type c = 0;
        n_ptr n = nmem.allocate( 1 );
        a++;
        dst = n;
        try {
            nmem.construct( n, *src );
            c++;
            n_ptr p = n;    // previous element for loop
            src = src->fwd;
            // now the rest of the elements
            while( c < i ) {
                n = nmem.allocate( 1 );
                a++;
                p->fwd = n;
                nmem.construct( n, *src );
                c++;
                p = n;
                src = src->fwd;
            }
        }
        catch( ... ) {
            // something failed, unwind the completed elements
            while( a ) {
                n = dst->fwd;
                //last element might have been alloced but not constructed
                if( c ) nmem.destroy( dst );
                nmem.deallocate( dst, 1 );
                dst = n;
                c--;
                a--;
            }
            throw;
        }

        n->fwd=0;
        return dst;
    }

    /* ------------------------------------------------------------------
     * n_ptr make(  size_type, Tconst&, nptr& f )
     * helper to make chain of links initialised to T
     * unwinds on exception for use by other strong excption safe methods
     * sets pointer param to first and returns last in new chain
     */
    template< class T, class A >
    forward_list<T,A>::n_ptr forward_list<T,A>::make( size_type i, T const & t, n_ptr& f )
    {
        n_ptr p = 0;
        n_ptr l = 0;
        f = 0;
        try {
            // build links backwards
            for( int c = 0; c < i; c++ ) {
                f = nmem.allocate( 1 );
                try {
                    nmem.construct( f, Node(t) );
                }
                catch( ... ) {
                    nmem.deallocate( f, 1 );
                    throw;
                }
                if( c == 0 ) l = f; // save ptr last
                f->fwd = p;
                p = f;
            }
        } catch( ... ) {
            while( p ) {
                f = p->fwd;
                nmem.destroy( p );
                nmem.deallocate( p, 1 );
                p = f;
            }
        }
        return( l );
    }

    /* ------------------------------------------------------------------
     * ctor( size_type n )
     * construct list with n default constructed elements
     * exception safety: strong
     */
    template< class T, class A >
    forward_list<T,A>::forward_list( size_type i ) : mSize( i )
    {
        make( i, T(), first );
    }

    /* ------------------------------------------------------------------
     * cpyctor( forward_list & )
     * strong exception safety
     */
    template< class T, class A >
    forward_list<T,A>::forward_list( forward_list const & that ) : mSize( that.mSize )
    {
        first = copy( that.first, mSize );
    }

    /* ------------------------------------------------------------------
     * assignment operator
     * exception safety: strong
     */
    template< class T, class A >
    forward_list<T,A>& forward_list<T,A>::operator=( forward_list<T,A> const & that )
    {
        if( this == &that ) return( *this );
        n_ptr temp = copy( that.first, that.mSize );
        // following can't throw
        clear();
        first = temp;
        mSize = that.mSize;
        return( *this );
    }

    /* ------------------------------------------------------------------
     * assign( size_type, T const & )
     * exception safety: strong
     */
    template< class T, class A >
    void forward_list<T,A>::assign( size_type s, T const & t )
    {
        n_ptr temp;
        make( s, t, temp );
        // following can't throw
        clear();
        first = temp;
        mSize = s;
    }

    /* ------------------------------------------------------------------
     * max_size
     */
    template< class T, class A >
    typename forward_list<T,A>::size_type forward_list<T,A>::max_size() const
    {
        return( numeric_limits< difference_type >::max() /
                sizeof( T ) ); // hmm
    }

    /* ------------------------------------------------------------------
     * resize
     * exception safety: strong
     */
    template< class T, class A >
    void forward_list<T,A>::resize( size_type s, T t )
    {
        if( s == 0 ) {
            clear();
        }
        else if( s < mSize ) {
            n_ptr del, p = first;
            int i;
            for( i = 1; i < s; i++ ) p = p->fwd;    // find previous to sth element
            del = p->fwd;
            p->fwd = 0;                             // new end
            while( del != 0 ) {
                p = del->fwd;                       // save next
                nmem.destroy( del );
                nmem.deallocate( del, 1 );
                del = p;
            }
            mSize = s;
        }
        else { // s > size
            n_ptr n;
            make( s - mSize, t, n );  // alloc new nodes
            if( mSize == 0 ) {
                first = n;
            }
            else {
                // find last
                n_ptr last = first;
                while( last->fwd ) last = last->fwd;
                last->fwd = n;              // link in new nodes
            }
            mSize = s;
        }
    }

    /* ------------------------------------------------------------------
     * pop_front( )
     * destroy front node
     */
    template< class T, class A >
    void forward_list<T,A>::pop_front( )
    {
        n_ptr o = first;
        first = first->fwd;
        --mSize;
        nmem.destroy( o );
        nmem.deallocate( o, 1 );
    }

    /* ------------------------------------------------------------------
     * push_front( T const & )
     * insert a new node at front
     */
    template< class T, class A >
    void forward_list<T,A>::push_front( T const & v )
    {
        n_ptr n = nmem.allocate( 1 );
        try {
            nmem.construct( n, Node(v) );
        }
        catch( ... ) {
            nmem.deallocate( n, 1 );
            throw;
        }
        n->fwd = first;
        first = n;
        ++mSize;
    }

    /* ------------------------------------------------------------------
     * insert( iterator, T const & )
     * insert a new node before it
     * Note this is slow for ssl
     */
    template< class T, class A >
    forward_list<T,A>::iterator forward_list<T,A>::insert( const_iterator it , T const & v )
    {
        n_ptr n = nmem.allocate( 1 );
        try {
            nmem.construct( n, Node(v) );
        }
        catch( ... ) {
            nmem.deallocate( n, 1 );
            throw;
        }

        if( it.self == first ) {
            n->fwd = first;
            first = n;
        }
        else {
            n_ptr p = previous( it.self );
            
            n->fwd = p->fwd;
            p->fwd = n;
        }
        ++mSize;
        return( iterator( n ) );
    }

    /* ------------------------------------------------------------------
     * insert_after( Node* o, T const & )
     * insert a new node after node o
     * NOTE this op is constant time for sll
     */
    template< class T, class A >
    forward_list<T,A>::iterator forward_list<T,A>::insert_after( const_iterator it, T const & v )
    {
        n_ptr n = nmem.allocate( 1 );
        try {
            nmem.construct( n, Node(v) );
        }
        catch( ... ) {
            nmem.deallocate( n, 1 );
            throw;
        }
        n_ptr p = it.self;
        n->fwd = p->fwd;
        p->fwd = n;
        ++mSize;
        return( n );
    }

    /* ------------------------------------------------------------------
     * insert( const_iterator, size_type s, T const & )
     * insert s new nodes before it
     * Note this is slow for ssl
     */
    template< class T, class A >
    void forward_list<T,A>::insert( const_iterator cit, size_type s, T const & t )
    {
        if( s == 0 ) return;
        n_ptr n;
        n_ptr e = make( s, t, n );
        
        n_ptr l = cit.self;
        if( l == first ) {
            e->fwd = first;
            first = n;
        }
        else {
            n_ptr p = previous( l );
            p->fwd = n;
            e->fwd = l;
        }
        mSize += s;
    }

    /* ------------------------------------------------------------------
     * insert_after( const_iterator, size_type s, T const & )
     * insert s new nodes before it
     * Note this is special/fast for ssl
     */
    template< class T, class A >
    void forward_list<T,A>::insert_after( const_iterator cit, size_type s, T const & t )
    {
        if( s == 0 ) return;
        n_ptr n;
        n_ptr e = make( s, t, n );

        n_ptr o = cit.self;
        e->fwd = o->fwd;
        o->fwd = n;
        mSize += s;
    }
    
    /* ------------------------------------------------------------------
     * erase( iterator )
     * NOTE this op is slow for sll
     */
    template< class T, class A >
    forward_list<T,A>::iterator forward_list<T,A>::erase( const_iterator it )
    {
        n_ptr ret;
        if( it.self == first ) {
            first = it.self->fwd;
            ret = it.self->fwd;
        }
        else {
            n_ptr p = previous( it.self );
            p->fwd = (it.self)->fwd;
            ret = p->fwd;
        }
        --mSize;
        nmem.destroy( it.self );
        nmem.deallocate( it.self, 1 );
        return( ret );
    }

    /* ------------------------------------------------------------------
     * erase_after( iterator )
     * this op is special/constant time for sll
     */
    template< class T, class A >
    forward_list<T,A>::iterator forward_list<T,A>::erase_after( const_iterator it )
    {
        n_ptr t = it.self;
        n_ptr del = t->fwd;
        n_ptr next = del->fwd;
        t->fwd = next;
        --mSize;
        nmem.destroy( del );
        nmem.deallocate( del, 1 );
        return( next );
    }

    /* ------------------------------------------------------------------
     * erase( iterator first , iterator last )
     * erase all list items in range [first, last)
     */
    template< class T, class A >
    forward_list<T,A>::iterator forward_list<T,A>::erase( const_iterator fit, const_iterator lit )
    {
        n_ptr b,del;

        if( fit.self == first ) {
            del = fit.self;
            while( del != lit.self ) {
                first = del->fwd;
                nmem.destroy( del );
                nmem.deallocate( del, 1 );
                del = first;
                --mSize;
            }
        }
        else {
            b = previous( fit ).self;
            del = fit.self;
            while( del != lit.self ) {
                b->fwd = del->fwd;
                nmem.destroy( del );
                nmem.deallocate( del, 1 );
                del = b->fwd;
                --mSize;
            }
        }
        return( del );
    }

    /* ------------------------------------------------------------------
     * erase_after( iterator first , iterator last )
     * erase all list items in range [first+1, last)
     */
    template< class T, class A >
    forward_list<T,A>::iterator forward_list<T,A>::erase_after( const_iterator fit, const_iterator lit )
    {
        n_ptr s, del;
        del = fit.self->fwd;
        while( del != lit.self ) {
            s = del->fwd;
            nmem.destroy( del );
            nmem.deallocate( del, 1 );
            del = s;
            --mSize;
        }
        fit.self->fwd = lit.self;
        return( s );
    }

    /* ------------------------------------------------------------------
     * swap
     * exception safety : no throw
     */
    template< class T, class A >
    void forward_list<T,A>::swap( forward_list& other )
    {
        n_ptr tempn = first;
        first = other.first;
        other.first = tempn;
        size_type tempi = mSize;
        mSize = other.mSize;
        other.mSize = tempi;
    }

    /* ------------------------------------------------------------------
     * clear
     * exception safety : no throw
     */
    template< class T, class A >
    void forward_list<T,A>::clear( )
    {
        n_ptr del;
        n_ptr x = first;
        while( x != 0 ) {
            del = x;
            x = x->fwd;
            nmem.destroy( del );
            nmem.deallocate( del, 1 );
        }
        mSize = 0;
        first = 0;
    }

    /* ------------------------------------------------------------------
     * splice( iterator, forward_list& )
     * exception safety: no throw
     */
    template< class T, class A >
    void forward_list<T,A>::splice( const_iterator it, forward_list& that )
    {
        if( that.mSize == 0 ) return;

        // link this to start of that
        n_ptr n = it.self;
        if( n == first ) {
            first = that.first;
        }
        else { // n != first
            n_ptr p = previous( n );
            p->fwd = that.first;
        }

        // find end of that and link to rest of this
        n_ptr e = that.first;
        while( e->fwd ) e = e->fwd;
        e->fwd = n;

        mSize += that.mSize;
        
        // remove links from that
        that.mSize = 0;
        that.first = 0;
    }

    /* ------------------------------------------------------------------
     * splice( iterator, forward_list, iterator )
     * splice node src before dst
     * src can point to this container or another forward_list
     * exception safety: no throw
     */
    template< class T, class A >
    void forward_list<T,A>::splice( const_iterator dst, forward_list& that, const_iterator src )
    {
        // check not splicing on top of itself
        if( ( this == &that ) &&
            ( src.self == dst.self || src.self->fwd == dst.self ) ) return;

        // unlink src from src container
        if( src.self == that.first ) {
            that.first = src.self->fwd;
        }
        else {
            that.previous( src.self )->fwd = src.self->fwd;
        }

        // link in new node
        if( dst.self == first ) {
            first = src.self;
        }
        else {
            previous( dst.self )->fwd = src.self;
        }

        // link back in the tail of this list
        src.self->fwd = dst.self;

        --that.mSize;
        ++mSize;
    }

    /* ------------------------------------------------------------------
     * splice_after( iterator, forward_list, iterator )
     * splice node ++src after dst, constant time
     * dst & src must be dereferenceable, ++src must be dereferenceable
     * ( it doesn't seem to make sense to splice "end" of one list into another list )
     * that can be this container or another forward_list
     * differs from sgi in that it takes a ref to the other list
     * (so iterators don't need to store list reference)
     * exception safety: no throw
     */
    template< class T, class A >
    void forward_list<T,A>:: splice_after( const_iterator dst, forward_list& that, const_iterator src )
    {
        // check not splicing on top of itself
        if( src.self->fwd == dst.self->fwd ||
            src.self->fwd == src.self ) return;

        // link in ++src node after dst ( can't be first node )
        n_ptr spliceme = src.self->fwd;
        n_ptr tail = dst.self->fwd;
        dst.self->fwd = spliceme;
        
        // unlink ++src from src container ( can't be first node or end )
        src.self->fwd = src.self->fwd->fwd;

        // link back in the tail of this list
        spliceme->fwd = tail;

        --that.mSize;
        ++mSize;
    }

    /* ------------------------------------------------------------------
     * splice_after( iterator dst, forward_list, iterator b4_first, iterator b4_last )
     * splice nodes [++b4_first, ++b4_last) after dst, constant time
     * dst b4_first b4_last iterators must be dereferenceable
     * that can be this container or another forward_list
     * bad things will happen if dst is in range[first, last )
     * differs from sgi in that it takes a ref to the other list
     * (so iterators don't need to store list reference)
     * exception safety: no throw
     */
    template< class T, class A >
    void forward_list<T,A>::splice_after( const_iterator dst, forward_list& that,
                                          const_iterator b4_first,
                                          const_iterator b4_last )
    {
        if( &that != this ) {
            // count elements
            int c = 0;
            const_iterator it = b4_first;
            while( it != b4_last ) { ++it; ++c; }
            that.mSize -= c;
            mSize += c;
        }

        n_ptr tail = dst.self->fwd;             //save tail
        dst.self->fwd = b4_first.self->fwd;     //splice in
        b4_first.self->fwd = b4_last.self->fwd; //splice out
        b4_last.self->fwd = tail;               //join tail

    }

    /* ------------------------------------------------------------------
     * remove( T const & )
     * exception safety: strong only if operator== can't throw
     */
    template< class T, class A >
    void forward_list<T,A>::remove( T const & v )
    {
        n_ptr p = first;
        n_ptr n = first;
        while( n != 0 ) {
            if( n->value == v ) {
                if( n == first ) {
                    first = n->fwd;
                    nmem.destroy( n );
                    nmem.deallocate( n, 1 );
                    --mSize;
                    p = n = first;
                }
                else {
                    p->fwd = n->fwd;
                    nmem.destroy( n );
                    nmem.deallocate( n, 1 );
                    --mSize;
                    n = p->fwd;
                }
            }
            else {
                p = n;
                n = n->fwd;
            }
        }
    }

    /* ------------------------------------------------------------------
     * reverse( )
     * exception safety: strong
     */
    template< class T, class A >
    void forward_list<T,A>::reverse( )
    {
        n_ptr n = first;
        n_ptr p = 0;
        n_ptr s;
        while( n != 0 ) {
            s = n->fwd;     // save next link
            n->fwd = p;     // link this to previous
            p = n;          // advance previous to this
            n = s;          // advance this to saved next
        }
        first = p;
    }

    /* ------------------------------------------------------------------
     * _Sane
     * check internal structure of list ok
     */
    template< class T, class A >
    bool forward_list<T,A>::_Sane()
    {
        if( ( mSize == 0 ) && ( first != NULL ) ) return( false );
        n_ptr n = first;
        for( int i = 0; i < mSize; ++i ) {
            if( n == NULL ) return( false );
            n = n->fwd;
        }
        if( n != NULL ) return( false );

        return( true );
    }

    // lexicographical comparisons

    template< class T, class A >
    bool operator==( forward_list<T,A> const & a, forward_list<T,A> const & b )
    {
        if( a.mSize != b.mSize ) return( false );
        forward_list<T,A>::n_ptr n = a.first;
        forward_list<T,A>::n_ptr m = b.first;
        while( n && m ) {
            if( !( n->value == m->value ) ) return( false );
            n = n->fwd;
            m = m->fwd;
        }
        return( true );
    }

    template< class T, class A >
    bool operator<( forward_list<T,A> const & a, forward_list<T,A> const & b )
    {
        forward_list<T,A>::n_ptr n = a.first;
        forward_list<T,A>::n_ptr m = b.first;
        while( n && m ) {
            if( n->value < m->value ) return( true );
            if( m->value < n->value ) return( false );
            n = n->fwd;
            m = m->fwd;
        }
        return( !n && m );
    }

    template< class T, class A >
    bool operator>( forward_list<T,A> const & a, forward_list<T,A> const & b )
    {
        return( b < a );
    }

    template< class T, class A>
    bool operator!=( forward_list<T,A> const & a, forward_list<T,A> const & b)
    {
        return( !( a == b ) );
    }

    template< class T, class A>
    bool operator<=( forward_list<T,A> const & a, forward_list<T,A> const & b )
    {
        return( !( b < a ) );
    }

    template< class T, class A>
    bool operator>=( forward_list<T,A> const & a, forward_list<T,A> const & b )
    {
        return( !( a < b ) );
    }

    // specialised algorithms
    template< class T, class A>
    void swap( forward_list<T,A> const & x, forward_list<T,A> const & y )
    {
        x.swap( y );
    }
    //template< class T, class A> void swap( forward_list<T,A> const &&, forward_list<T,A> const & );
    //template< class T, class A> void swap( forward_list<T,A> const &, forward_list<T,A> const && );

} // namespace std

#endif
