文件位置：young/y_list.hpp
/*
The young Library
Copyright (c) 2005 by 杨桓
Permission to use, copy, modify, distribute and sell this software for any
purpose is hereby granted without fee, provided that the above copyright
notice appear in all copies and that both that copyright notice and this
permission notice appear in supporting documentation.
The author make no representations about the suitability of this software
for any purpose. It is provided "as is" without express or implied warranty.
*/
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_LIST_HEADER_FILE__
#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_LIST_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "y_allocator.hpp"
#include "y_construct.hpp"
#include "y_exception.hpp"
#include "algorithm/y_algorithm_base.hpp"
#include "algorithm/y_algorithm_compare.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_YOUNG_LIBRARY_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
static const int list_sort_array = 32;
struct list_node_base
{
list_node_base* prev;
list_node_base* next;
};
template< typename Value >
struct list_node : public list_node_base
{
Value data;
};
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
def_size_t list_size( const list_node_base* begin,
const list_node_base* end )
{
def_size_t n = 0;
while( begin != end )
{
begin = begin->next;
++n;
}
return n;
}
void list_splice( list_node_base* position,
list_node_base* first,
list_node_base* last )
{
if( position != last )
{
last->prev->next = position;
first->prev->next = last;
position->prev->next = first;
list_node_base* temp = position->prev;
position->prev = last->prev;
last->prev = first->prev;
first->prev = temp;
}
}
inline list_node_base* list_insert_link( list_node_base* position,
list_node_base* new_node )
{
new_node->next = position;
new_node->prev = position->prev;
position->prev->next = new_node;
position->prev = new_node;
return new_node;
}
inline list_node_base* list_erase_node( list_node_base* position )
{
list_node_base* prev_node = position->prev;
list_node_base* next_node = position->next;
prev_node->next = next_node;
next_node->prev = prev_node;
return next_node;
}
void list_reverse_not_POD( list_node_base* header )
{
if( !header || header->next->next == header )
return;
list_node_base* curr_node = header->next->next;
list_node_base* next_node = curr_node->next;
list_node_base* curr_temp;
list_node_base* next_temp;
while( curr_node != header )
{
curr_temp = curr_node;
curr_node = curr_node->next;
next_temp = next_node;
next_node = next_node->next;
list_splice( header->next, curr_temp, next_temp );
}
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template< typename T, typename Ref, typename Ptr, typename Alloc >
class list_iterator;
template< typename T, typename Allocator >
class list;
template< typename T, typename Ref, typename Ptr, typename Alloc >
class list_iterator
{
public:
typedef bidirectional_iterator_tag iterator_category;
typedef def_size_t size_type;
typedef def_ptrdiff_t difference_type;
typedef T value_type;
typedef Ref reference;
typedef Ptr pointer;
typedef list_iterator<T, Ref, Ptr, Alloc> self;
typedef list_iterator<T, T&, T*, Alloc> iterator;
typedef list_iterator<T, const T&, const T*, Alloc> const_iterator;
private:
typedef list_node_base* base_ptr;
typedef list_node<T>* node_ptr;
typedef typename primal_type<Ref>::contrary_const_ref Ref_t;
typedef typename primal_type<Ptr>::contrary_const_ptr Ptr_t;
friend class list<T, Alloc>;
friend class list_iterator<T, Ref_t, Ptr_t, Alloc>;
friend iterator const_iter_cast <> ( const const_iterator& );
base_ptr node;
public:
list_iterator() : node(NULL_POINTER) {}
list_iterator( base_ptr p ) : node(p) {}
list_iterator( node_ptr p ) : node(p) {}
list_iterator( const iterator& x ) : node(x.node) {}
self& operator=( def_nullptr_t n )
{
if( n == NULL_POINTER )
node = NULL_POINTER;
return *this;
}
bool operator!() const { return !node; }
bool operator==( const self& rhs ) const { return node == rhs.node; }
bool operator!=( const self& rhs ) const { return node != rhs.node; }
reference operator*() const
{ return static_cast<node_ptr>(node)->data; }
pointer operator->() const
{ return &( operator*() ); }
self& operator++()
{ node = node->next; return *this; }
self operator++(int)
{ self old = *this; node = node->next; return old; }
self& operator--()
{ node = node->prev; return *this; }
self operator--(int)
{ self old = *this; node = node->prev; return old; }
self& operator+=( difference_type n )
{
if( n > 0 )
increment_n( n );
else
decrement_n( n );
return *this;
}
self& operator-=( difference_type n )
{
if( n > 0 )
decrement_n( n );
else
increment_n( n );
return *this;
}
private:
void increment_n( size_type n )
{
for( ; n > 0; --n )
node = node->next;
}
void decrement_n( size_type n )
{
for( ; n > 0; --n )
node = node->prev;
}
}; //end iterator
template< typename T, typename Ref, typename Ptr, typename Alloc >
inline list_iterator<T, Ref, Ptr, Alloc>
operator+( const list_iterator<T, Ref, Ptr, Alloc>& lhs, def_ptrdiff_t n )
{
list_iterator<T, Ref, Ptr,Alloc> temp( lhs );
return ( temp += n );
}
template< typename T, typename Ref, typename Ptr, typename Alloc >
inline list_iterator<T, Ref, Ptr,Alloc>
operator+( def_ptrdiff_t n, const list_iterator<T, Ref, Ptr, Alloc>& rhs )
{
list_iterator<T, Ref, Ptr, Alloc> temp( rhs );
return ( temp += n );
}
template< typename T, typename Ref, typename Ptr, typename Alloc >
inline list_iterator<T, Ref, Ptr, Alloc>
operator-( const list_iterator<T, Ref, Ptr, Alloc>& lhs, def_ptrdiff_t n )
{
list_iterator<T, Ref, Ptr, Alloc> temp( lhs );
return ( temp -= n );
}
template< typename T, typename Alloc >
inline list_iterator<T, T&, T*, Alloc>
const_iter_cast( const list_iterator<T, const T&, const T*, Alloc>& citer )
{
return list_iterator<T, T&, T*, Alloc>( citer.node );
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template< typename T, typename Allocator = allocator< list_node<T> > >
class list
{
public:
typedef list<T, Allocator> self;
typedef Allocator allocator_type;
typedef T value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef def_size_t size_type;
typedef def_ptrdiff_t difference_type;
typedef list_iterator<T, T&, T*, Allocator> iterator;
typedef list_iterator<T, const T&, const T*, Allocator> const_iterator;
typedef Reverse_Iterator<iterator> reverse_iterator;
typedef Reverse_Iterator<const_iterator> const_reverse_iterator;
protected:
typedef list_node_base base_node_type;
typedef list_node_base* base_ptr;
typedef list_node<T> node_type;
typedef list_node<T>* node_ptr;
typedef typename Allocator::rebind<base_node_type>::other base_node_alloc;
// typedef allocator<base_node_type> base_node_alloc;
base_ptr m_header;
allocator_type m_alloc;
public:
list() { init_header(); }
explicit list( size_type size )
{ fill_init( size, value_type() ); }
list( size_type size, const_reference value )
{ fill_init( size, value ); }
list( int size, const_reference value )
{ fill_init( static_cast<size_type>(size), value ); }
list( long size, const_reference value )
{ fill_init( static_cast<size_type>(size), value ); }
template< typename InputIterator >
list( InputIterator first, InputIterator last )
{
init_header();
try
{
insert( end(), first, last );
}
catch(...)
{
clear();
dealloc_header();
throw;
}
}
list( const self& rhs )
{
init_header();
try
{
insert( end(), rhs.begin(), rhs.end() );
}
catch(...)
{
clear();
dealloc_header();
throw;
}
}
self& operator=( const self& rhs )
{
if( this != &rhs )
assign( rhs.begin(), rhs.end() );
return *this;
}
~list() { clear(); dealloc_header(); }
iterator begin() { return m_header->next; }
iterator end() { return m_header; }
const_iterator begin() const { return m_header->next; }
const_iterator end() const { return m_header; }
reverse_iterator rbegin() { return end(); }
reverse_iterator rend() { return begin(); }
const_reverse_iterator rbegin() const { return end(); }
const_reverse_iterator rend() const { return begin(); }
reference front() { return *begin(); }
reference back() { return *(--end()); }
const_reference front() const { return *begin(); }
const_reference back() const { return *(--end()); }
bool empty() const { return ( m_header->next == m_header ); }
size_type max_size() const { return size_t_max; }
void clear() { erase( begin(), end() ); }
void push_back( const_reference value ) { insert( end(), value ); }
void push_front( const_reference value ) { insert( begin(), value ); }
void pop_back() { erase( --end() ); }
void pop_front() { erase( begin() ); }
reference at( size_type index );
const_reference at( size_type index ) const;
reference operator[]( size_type index )
{
iterator result = begin();
return *( result += index );
}
const_reference operator[]( size_type index ) const
{
const_iterator result = begin();
return *( result += index );
}
size_type size() const
{
return list_size( m_header->next, m_header );
}
void swap( self& rhs )
{
if( this != &rhs )
{
data_swap( m_header, rhs.m_header );
data_swap( m_alloc, rhs.m_alloc );
}
}
void reverse()
{
typedef typename type_traits<value_type>::is_POD_type POD;
list_reverse( POD() );
}
void splice( iterator position, self& rhs )
{
if( !rhs.empty() )
list_splice( position.node, rhs.begin().node, rhs.end().node );
}
void splice( iterator position, self& rhs, iterator first, iterator last )
{
if( first != last )
list_splice( position.node, first.node, last.node );
}
void splice( iterator position, self& rhs, iterator new_node )
{
if( position != new_node )
{
iterator temp = new_node; ++temp;
if( new_node != temp )
list_splice( position.node, new_node.node, temp.node );
}
}
iterator erase( iterator position );
iterator erase( iterator first, iterator last );
iterator insert( iterator position, const_reference value = value_type() );
void insert( iterator position, size_type count, const_reference value );
void insert( iterator position, int count, const_reference value )
{ insert( position, static_cast<size_type>(count), value ); }
void insert( iterator position, long count, const_reference value )
{ insert( position, static_cast<size_type>(count), value ); }
template< typename InputIterator >
void insert( iterator position, InputIterator first, InputIterator last );
void assign( size_type new_size, const_reference value = value_type() );
void assign( int new_size, const_reference value = value_type() )
{ assign( static_cast<size_type>(new_size), value ); }
void assign( long new_size, const_reference value = value_type() )
{ assign( static_cast<size_type>(new_size), value ); }
template< typename InputIterator >
void assign( InputIterator first, InputIterator last );
void resize( size_type new_size, const_reference value = value_type() );
void remove( const_reference value );
void unique();
void merge( self& rhs );
void sort();
template< typename Predicate >
void remove_if( Predicate pred );
template< typename BinaryPredicate >
void unique( BinaryPredicate bin_pred );
template< typename StrictWeakOrdering >
void merge( self& rhs, StrictWeakOrdering comp );
template< typename StrictWeakOrdering >
void sort( StrictWeakOrdering comp );
protected:
void init_header()
{
alloc_header();
m_header->prev = m_header;
m_header->next = m_header;
}
void alloc_header()
{
m_header = base_node_alloc().allocate( 1 );
}
void dealloc_header()
{
base_node_alloc().deallocate( m_header, 1 );
}
node_ptr create_node( const_reference x )
{
node_ptr ptr = m_alloc.allocate( 1 );
try
{
construct( &(ptr->data), x );
}
catch(...)
{
m_alloc.deallocate( ptr, 1 );
throw;
}
return ptr;
}
void destroy_node( node_ptr ptr )
{
destroy( &(ptr->data) );
m_alloc.deallocate( ptr, 1 );
}
void fill_init( size_type n, const_reference value )
{
init_header();
try
{
insert( end(), n, value );
}
catch(...)
{
clear();
dealloc_header();
throw;
}
}
void list_reverse( true_type );
void list_reverse( false_type )
{
list_reverse_not_POD( m_header );
}
value_type& data( base_ptr x )
{
return static_cast<node_ptr>(x)->data;
}
}; //end class
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
typename list<T, Allocator>::reference
list<T, Allocator>::at( size_type index )
{
if( empty() )
throw_out_of_range( "list::at()" );
iterator result = begin();
iterator finish = end();
for( ; index > 0; --index,++result )
{
if( result == finish )
throw_out_of_range( "list::at()" );
}
return *result;
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
typename list<T, Allocator>::const_reference
list<T, Allocator>::at( size_type index ) const
{
if( empty() )
throw_out_of_range( "list::at()" );
const_iterator result = begin();
const_iterator finish = end();
for( ; index > 0; --index,++result )
{
if( result == finish )
throw_out_of_range( "list::at()" );
}
return *result;
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
typename list<T, Allocator>::iterator
list<T, Allocator>::erase( iterator position )
{
if( position == end() )
return position;
base_ptr next_node = list_erase_node( position.node );
destroy_node( static_cast<node_ptr>(position.node) );
return next_node;
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
typename list<T, Allocator>::iterator
list<T, Allocator>::erase( iterator first, iterator last )
{
if( first != last && first != end() )
{
iterator temp_last = last;
--temp_last;
first.node->prev->next = last.node;
last.node->prev = first.node->prev;
iterator temp;
while( temp_last != first )
{
temp = temp_last;
--temp_last;
destroy_node( static_cast<node_ptr>(temp.node) );
}
destroy_node( static_cast<node_ptr>(first.node) );
}
return last;
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
typename list<T, Allocator>::iterator
list<T, Allocator>::insert( iterator position, const_reference value )
{
base_ptr new_node = create_node( value );
return list_insert_link( position.node, new_node );
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
void list<T, Allocator>::insert( iterator position, size_type count,
const_reference value )
{
for( ; count > 0; --count )
insert( position, value );
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
template< typename InputIterator >
void list<T, Allocator>::insert( iterator position,
InputIterator first, InputIterator last )
{
for( ; first != last; ++first )
insert( position, *first );
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
void list<T, Allocator>::resize( size_type new_size, const_reference value )
{
iterator itr1 = begin();
iterator itr2 = end();
while( (itr1 != itr2) && (new_size > 0) )
{
++itr1;
--new_size;
}
if( new_size == 0 )
erase( itr1, itr2 );
else
insert( itr2, new_size, value );
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
void list<T, Allocator>::assign( size_type new_size, const_reference value )
{
if( new_size < 1 )
{
clear();
return;
}
iterator itr1 = begin();
iterator itr2 = end();
for( ; (itr1 != itr2) && (new_size > 0); ++itr1,--new_size )
*itr1 = value;
if( new_size == 0 )
erase( itr1, itr2 );
else
insert( itr1, new_size, value );
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
template< typename InputIterator >
void list<T, Allocator>::assign( InputIterator first, InputIterator last )
{
if( first == last )
{
clear();
return;
}
iterator itr1 = begin();
iterator itr2 = end();
for( ; (itr1 != itr2) && (first != last); ++first,++itr1 )
*itr1 = *first;
if( itr1 != itr2 )
erase( itr1, itr2 );
else
insert( itr1, first, last );
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
void list<T, Allocator>::list_reverse( true_type )
{
if( empty() || m_header->next->next == m_header )
return;
iterator first = begin();
iterator last = --end();
iterator last_next;
for( ; (first != last) && (first != last_next); ++first,--last )
{
last_next = last;
data_swap( data(first.node), data(last.node) );
}
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
void list<T, Allocator>::remove( const_reference value )
{
iterator first = begin();
iterator last = end();
iterator temp;
while( first != last )
{
temp = first;
++first;
if( *temp == value )
erase( temp );
}
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
template< typename Predicate >
void list<T, Allocator>::remove_if( Predicate pred )
{
iterator first = begin();
iterator last = end();
iterator temp;
while( first != last )
{
temp = first;
++first;
if( pred(*temp) )
erase( temp );
}
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
void list<T, Allocator>::unique()
{
if( empty() || m_header->next->next == m_header )
return;
iterator first = begin();
iterator last = end();
iterator next = first;
while( (++next) != last )
{
if( *next == *first )
erase( next );
else
first = next;
next = first;
}
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
template< typename BinaryPredicate >
void list<T, Allocator>::unique( BinaryPredicate bin_pred )
{
if( empty() || m_header->next->next == m_header )
return;
iterator first = begin();
iterator last = end();
iterator next = first;
while( (++next) != last )
{
if( bin_pred(*first, *next) )
erase( next );
else
first = next;
next = first;
}
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
void list<T, Allocator>::merge( self& rhs )
{
if( rhs.empty() )
return;
iterator first1 = begin(), last1 = end();
iterator first2 = rhs.begin(), last2 = rhs.end();
iterator temp;
while( (first1 != last1) && (first2 != last2) )
{
if( *first2 < *first1 )
{
temp = first2;
++first2;
splice( first1, rhs, temp, first2 );
}
else
++first1;
}
if( first2 != last2 )
splice( last1, rhs, first2, last2 );
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
template< typename StrictWeakOrdering >
void list<T, Allocator>::merge( self& rhs, StrictWeakOrdering comp )
{
if( rhs.empty() )
return;
iterator first1 = begin(), last1 = end();
iterator first2 = rhs.begin(), last2 = rhs.end();
iterator temp;
while( (first1 != last1) && (first2 != last2) )
{
if( comp(*first2, *first1) )
{
temp = first2;
++first2;
splice( first1, rhs, temp, first2 );
}
else
++first1;
}
if( first2 != last2 )
splice( last1, rhs, first2, last2 );
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
void list<T, Allocator>::sort()
{
if( empty() || m_header->next->next == m_header )
return;
self result[ list_sort_array ];
self carry;
size_type fill = 0;
while( !empty() )
{
carry.splice( carry.begin(), *this, begin() );
size_type i = 0;
while( (i < fill) && (!result[i].empty()) )
{
result[i].merge( carry );
carry.swap( result[i] );
++i;
}
carry.swap( result[i] );
if( i == fill )
++fill;
}
for( size_type j = 1; j < fill; ++j )
result[j].merge( result[j - 1] );
swap( result[fill - 1] );
}
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
template< typename StrictWeakOrdering >
void list<T, Allocator>::sort( StrictWeakOrdering comp )
{
if( empty() || m_header->next->next == m_header )
return;
self result[ list_sort_array ];
self carry;
size_type fill = 0;
while( !empty() )
{
carry.splice( carry.begin(), *this, begin() );
size_type i = 0;
while( (i < fill) && (!result[i].empty()) )
{
result[i].merge( carry, comp );
carry.swap( result[i] );
++i;
}
carry.swap( result[i] );
if( i == fill )
++fill;
}
for( size_type j = 1; j < fill; ++j )
result[j].merge( result[j - 1], comp );
swap( result[fill - 1] );
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template< typename T, typename Allocator >
inline void swap( list<T, Allocator>& lhs, list<T, Allocator>& rhs )
{
lhs.swap( rhs );
}
template< typename T, typename Allocator >
inline bool operator==( const list<T, Allocator>& lhs,
const list<T, Allocator>& rhs )
{
if( lhs.end() == rhs.end() )
return true;
return matching( lhs.begin(), lhs.end(), rhs.begin(), rhs.end() );
}
template< typename T, typename Allocator >
inline bool operator!=( const list<T, Allocator>& lhs,
const list<T, Allocator>& rhs )
{
return !( lhs == rhs );
}
template< typename T, typename Allocator >
inline bool operator<( const list<T, Allocator>& lhs,
const list<T, Allocator>& rhs )
{
if( lhs.end() == rhs.end() )
return false;
return lexicographical_compare( lhs.begin(), lhs.end(),
rhs.begin(), rhs.end() );
}
template< typename T, typename Allocator >
inline bool operator>( const list<T, Allocator>& lhs,
const list<T, Allocator>& rhs )
{
return ( rhs < lhs );
}
template< typename T, typename Allocator >
inline bool operator<=( const list<T, Allocator>& lhs,
const list<T, Allocator>& rhs )
{
return !( rhs < lhs );
}
template< typename T, typename Allocator >
inline bool operator>=( const list<T, Allocator>& lhs,
const list<T, Allocator>& rhs )
{
return !( lhs < rhs );
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_YOUNG_LIBRARY_END_NAMESPACE__
#endif
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
