MichaelAgarkov/CodeBlocksPortable
MichaelAgarkov/CodeBlocksPortable
Archived
1
1
Fork 0
Code Issues Pull requests Actions Packages Projects Releases Wiki Activity
This repository has been archived on 2024-12-16. You can view files and clone it, but cannot push or open issues or pull requests.
CodeBlocksPortable/WATCOM/h/slist

1300 lines
38 KiB
Plaintext
Raw Permalink Blame History

///////////////////////////////////////////////////////////////////////////
// FILE: list (Definition of _watcom::slist)
//
// =========================================================================
//
// 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 OW extentions to the standard
// library. It provides a single link list container.
///////////////////////////////////////////////////////////////////////////
#ifndef _SLIST_INCLUDED
#define _SLIST_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 _watcom {
/* ==================================================================
* slist class template
* see list and SGI slist for inspiration
*/
template< class T, class A = std::allocator< T > >
class slist{
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< std::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< std::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; } //prefix
iterator operator++( int ) { iterator old = *this; self = self->fwd; return old; } //postfix
reference operator*() { return( self->value ); }
};
struct const_iterator:
public iterator_base,
public std::iterator< std::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( slist::iterator const & that ) : iterator_base( that.self ){}
const_iterator& operator++() { self = self->fwd; return *this; } //prefix
const_iterator operator++( int ) { const_iterator old = *this; self = self->fwd; return old; } //postfix
const_reference operator*(){ return( self->value ); }
};
// end of iterators
//-----------------------------------------------------------------
public:
// construct/copy/destroy
explicit slist( A const & a = A() ) : mSize(0), nmem(a) { first = NULL; }
explicit slist( size_type );
slist( size_type, T const &, A const & = A() );
template< class InputIt > slist( InputIt f, InputIt l )//, A const & = A() )
: mSize( 0 ), first( 0 )
{ helper_assign( f, l, std::tr1::is_integral< InputIt >::type() ); }
slist( slist<T,A> const & );
//slist( slist&& );
~slist(){ clear(); }
slist<T,A>& operator=( slist<T,A> const & );
//slist<T,A>& operator=( slist<T,A> && );
template < class InputIt > void assign( InputIt f, InputIt l )
{ helper_assign( f, l, std::tr1::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, std::tr1::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, std::tr1::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( slist<T,A>&& );
void swap( slist<T,A>& );
void clear();
//operations
void splice( const_iterator, slist& );
void splice( const_iterator, slist&, const_iterator );
//void splice( const_iterator, slist<T,A>&&, const_iterator, const_iterator);
void splice_after( const_iterator pos, slist&, const_iterator prev ); // different to sgi interface
void splice_after( const_iterator pos, slist&,
const_iterator before_first,
const_iterator before_last );
void remove( T const& );
void unique() { unique( std::equal_to< T >() ); }
void merge( slist<T,A>& other ) { merge( other, std::less< T >() ); }
void sort() { sort( std::less< T >() ); }
void reverse();
template< class U, class V >
friend bool operator==( slist<U,V> const & a, slist<U,V> const & b );
template< class U, class V >
friend bool operator!=( slist<U,V> const & a, slist<U,V> const & b );
template< class U, class V >
friend bool operator<=( slist<U,V> const & a, slist<U,V> const & b );
template< class U, class V >
friend bool operator>=( slist<U,V> const & a, slist<U,V> const & b );
template< class U, class V >
friend bool operator<( slist<U,V> const & a, slist<U,V> const & b );
template< class U, class V >
friend bool operator>( slist<U,V> const & a, slist<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( slist, compare )
* inline due to missing compiler feature
* exception saftey: to do, what can throw?
*/
template< class Compare >
void merge( slist<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[ std::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, std::tr1::true_type )
{
//std::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, std::tr1::false_type )
{
//std::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, std::tr1::true_type )
{
//std::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, std::tr1::false_type )
{
//std::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, std::tr1::true_type )
{
//std::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, std::tr1::false_type )
{
//std::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 slist
/* ------------------------------------------------------------------
* 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
slist<T,A>::n_ptr slist<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 >
slist<T,A>::n_ptr slist<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 >
slist<T,A>::n_ptr slist<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 >
slist<T,A>::slist( size_type i ) : mSize( i )
{
make( i, T(), first );
}
/* ------------------------------------------------------------------
* cpyctor( slist & )
* strong exception safety
*/
template< class T, class A >
slist<T,A>::slist( slist const & that ) : mSize( that.mSize )
{
first = copy( that.first, mSize );
}
/* ------------------------------------------------------------------
* assignment operator
* exception safety: strong
*/
template< class T, class A >
slist<T,A>& slist<T,A>::operator=( slist<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 slist<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 slist<T,A>::size_type slist<T,A>::max_size() const
{
return( std::numeric_limits< difference_type >::max() /
sizeof( T ) ); // hmm
}
/* ------------------------------------------------------------------
* resize
* exception safety: strong
*/
template< class T, class A >
void slist<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 slist<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 slist<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 >
slist<T,A>::iterator slist<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 >
slist<T,A>::iterator slist<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 slist<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 slist<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 >
slist<T,A>::iterator slist<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 >
slist<T,A>::iterator slist<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 >
slist<T,A>::iterator slist<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 >
slist<T,A>::iterator slist<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 slist<T,A>::swap( slist& 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 slist<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, slist& )
* exception safety: no throw
*/
template< class T, class A >
void slist<T,A>::splice( const_iterator it, slist& 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, slist, iterator )
* splice node src before dst
* src can point to this container or another slist
* exception safety: no throw
*/
template< class T, class A >
void slist<T,A>::splice( const_iterator dst, slist& 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, slist, 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 slist
* 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 slist<T,A>:: splice_after( const_iterator dst, slist& 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, slist, 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 slist
* 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 slist<T,A>::splice_after( const_iterator dst, slist& 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 slist<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 slist<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 slist<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==( slist<T,A> const & a, slist<T,A> const & b )
{
if( a.mSize != b.mSize ) return( false );
slist<T,A>::n_ptr n = a.first;
slist<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<( slist<T,A> const & a, slist<T,A> const & b )
{
slist<T,A>::n_ptr n = a.first;
slist<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>( slist<T,A> const & a, slist<T,A> const & b )
{
return( b < a );
}
template< class T, class A>
bool operator!=( slist<T,A> const & a, slist<T,A> const & b)
{
return( !( a == b ) );
}
template< class T, class A>
bool operator<=( slist<T,A> const & a, slist<T,A> const & b )
{
return( !( b < a ) );
}
template< class T, class A>
bool operator>=( slist<T,A> const & a, slist<T,A> const & b )
{
return( !( a < b ) );
}
// specialised algorithms
template< class T, class A>
void swap( slist<T,A> const & x, slist<T,A> const & y )
{
x.swap( y );
}
//template< class T, class A> void swap( slist<T,A> const &&, slist<T,A> const & );
//template< class T, class A> void swap( slist<T,A> const &, slist<T,A> const && );
} // namespace _watcom
#endif
Reference in a new issue View git blame Copy permalink