list.mh

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

    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