Code:
namespace psi {
template <class type>
class Node { public:
type value;
Node * next;
Node * prev;
Node( type data )
: value(data),
prev(0),
next(0)
{ }
Node( void )
: value(0),
prev(0),
next(0)
{ }
Node * head(){
Node * p = this;
while(p->prev) p = p->prev;
return p;
}
Node * begin(){
return head()->next;
}
Node * end(){
Node * p = this;
while(p->next)
p = p->next;
return p;
}
void repoint( Node * prv, Node * nxt ){
prev = prv;
next = nxt;
return;
}
void repoint_neighbors( Node * prv, Node * nxt ){
if(prev)
prev->next = prv;
if(next)
next->prev = nxt;
return;
}
Node * detach(){
repoint_neighbors( prev, next );
repoint(0, 0);
return this;
}
Node * insert_between( Node * prv, Node * nxt ){
repoint(prv, nxt);
repoint_neighbors( this, this );
return this;
}
Node * invisible(){ //...hide from list, NOTE: store a pointer OR ELSE!
repoint_neighbors( prev, next );
return this;
}
Node * make_visible(){ //...call from a stored pointer...
repoint_neighbors( this, this );
return this;
}
~Node(){
this->detach();
}
};
template <class type>
class List : public Node <type> { public:
Node <type> * the_end;
Node <type> * iter;
List()
: deletion_instructions(&List::place_holder){
the_end = new_node();
the_end->insert_between(this, 0);
}
~List(){
destroy_list();
}
Node <type> * end(){ //...more efficient than the Node version...
return the_end;
}
Node <type> * new_node( type data = 0 ){
return new Node<type>(data);
}
Node <type> * insert_front( Node <type> * node ){
return node->insert_between( head(), begin() );
}
Node <type> * insert_end( Node <type> * node ){
return node->insert_between( end()->prev, end() );
}
Node <type> * insert( Node <type> * node ){
return insert_end( node );
}
type insert_front( type data ){
return insert_front( new_node(data) );
}
type insert_end( type data ){
insert_end( new_node(data) );
return data;
}
type insert( type data ){
return insert_end( data );
}
bool advance(Node <type> *& iterator){
if(iterator == 0) return false;
iterator = iterator->next;
if(iterator == 0) return false;
return true;
}
bool retreat(Node <type> *& iterator){
if(iterator == 0) return false;
iterator = iterator->prev;
if(!iterator || iterator->prev == 0) {
iter = 0;
return false;
}
return true;
}
int count( Node <type> * beg, Node <type> * nd ){
int total = 0;
for( iter = beg; iter != nd; advance(iter) ) ++total;
return total;
}
int count(){
return count( begin(), end() );
}
Node <type> * find( type data, Node <type> * beg, Node <type> * nd ){
for( iter = beg; iter != nd; advance(iter) )
if( iter->value == data ) return iter;
return 0;
}
Node <type> * find( type data ){
return find( data, begin(), end() );
}
int count( type data, Node <type> * beg, Node <type> * nd ){
int total = 0;
for( iter = beg; iter != nd ; advance(iter) )
if( iter->value == data ) ++total;
return total;
}
int count( type data ){
return count( data, begin(), end() );
}
void feed( type array[], int max, Node <type> * beg, Node <type> * nd ){
int index = 0;
for( iter = beg; iter != nd && index < max; advance(iter) )
array[index++] = iter->value;
}
void feed( type array[], int max ){
feed( array, max, begin(), end() );
}
void copy( type array[], int max, Node <type> * beg, Node <type> * nd ){
int index = 0;
for( iter = beg; iter != nd && index < max ; advance(iter) )
iter->value = array[index++]; //...use what we have...
for( ; index < max ; advance(iter) )
new_node(array[index++])->insert_between(end()->prev, end()); //...make some room...
}
void copy( type array[], int max ){
copy(array, max, begin(), end() );
}
void destroy( type data ){
destroy( find( data ) );
}
void destroy( Node <type> * item ){
(*this.*deletion_instructions)( item );
}
void use_cell_delete(){
deletion_instructions = &List::cell_delete;
}
void use_stack_delete(){
deletion_instructions = &List::stack_delete;
}
void destroy_list(){
Node <type> * node = begin();
if( node == 0 ) {
return;
}
for( iter = node->next; iter ; advance(iter) ){
destroy(node);
node = iter;
}
destroy(node);
}
private:
void place_holder( Node <type> * item ){
delete item;
}
void cell_delete( Node <type> * item ){
delete item->value;
delete item;
}
void stack_delete( Node <type> * item ){
delete [] item->value;
delete item;
}
void (List::*deletion_instructions)( Node <type> * item );
};
}// namespace