913 lines
28 KiB
Plaintext
913 lines
28 KiB
Plaintext
///////////////////////////////////////////////////////////////////////////
|
|
// FILE: list (Definition of std::list)
|
|
//
|
|
// =========================================================================
|
|
//
|
|
// Open Watcom Project
|
|
//
|
|
// Copyright (c) 2004-2010 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
|
|
|
|
#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 _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 );
|
|
}
|
|
|
|
} // namespace std
|
|
|
|
#endif
|