#include <iostream.h>
#include <stdlib.h>
#ifndef LIST
#define LIST
template <class TYPE>
struct ListNode
{
TYPE elem ;
ListNode<TYPE> *next ;
ListNode() : next( 0 ) {}
ListNode( TYPE e, ListNode<TYPE> *n ) : elem( e ), next( n ) {}
ListNode<TYPE> * Next() { return next ; }
TYPE & Elem() { return elem ; }
} ;
template <class TYPE>
class List
{
ListNode<TYPE> *first ;
ListNode<TYPE> *last ;
void Clear() ;
public:
unsigned length ;
List() ;
List( const List<TYPE> & l ) ;
~List() ;
ListNode<TYPE> * First() { return first->next ; }
void AddToBack( TYPE el ) ; void AddToFront( TYPE el ) ; void Add( TYPE el ) { AddToBack( el ) ; }
void OwnsNothing() ; int Empty() { return first == last ; } void Flush() ; TYPE ExtractFromFront() ; void Append( List<TYPE> & l ) ; void Append( List<TYPE> *l ) ; void AppendDeep( List<TYPE> l ) ; unsigned Length() { return length ; }
void Copy( List<TYPE> & source ) ; void Detach( ListNode<TYPE> * l ) ; void Check( ListNode<TYPE> * l ) ;
} ;
template <class TYPE>
List<TYPE>::List()
{
first = new ListNode<TYPE> ;
Check( first ) ;
last = first ;
length = 0 ;
}
template <class TYPE>
List<TYPE>::List( const List<TYPE> & l )
{
ListNode<TYPE> * tmp ;
first = new ListNode<TYPE> ;
Check( first ) ;
last = first ;
length = 0 ;
tmp = l.first->next ;
while( tmp )
{
AddToBack( tmp->elem ) ;
tmp = tmp->next ;
}
}
template <class TYPE>
void List<TYPE>::Copy( List<TYPE> & source )
{
ListNode<TYPE> * tmp ;
tmp = source.First() ;
while( tmp )
{
AddToBack( tmp->elem ) ;
tmp = tmp->next ;
}
}
template <class TYPE>
void List<TYPE>::Clear()
{
ListNode<TYPE> *l1 ;
ListNode<TYPE> *l2 ;
l1 = first ;
while ( l1 )
{
l2 = l1->next ;
delete l1 ;
l1 = l2 ;
}
}
template <class TYPE>
void List<TYPE>::Flush()
{
ListNode<TYPE> *l1 ;
ListNode<TYPE> *l2 ;
l1 = first->next ;
while ( l1 )
{
l2 = l1->next ;
delete l1 ;
l1 = l2 ;
}
OwnsNothing() ;
}
template <class TYPE>
List<TYPE>::~List()
{
Clear() ;
}
template <class TYPE>
void List<TYPE>::AddToBack( TYPE el )
{
ListNode<TYPE> *tmp ;
tmp = new ListNode<TYPE>( el, 0 ) ;
Check( tmp ) ;
last->next = tmp ;
last = last->next ;
length++ ;
}
template <class TYPE>
void List<TYPE>::AddToFront( TYPE el )
{
ListNode<TYPE> *tmp ;
tmp = new ListNode<TYPE>( el, 0 ) ;
Check( tmp ) ;
if( ! tmp )
{
cout << "Allocazione fallita!" << endl ;
abort() ;
}
tmp->next = first->next ;
if ( first == last ) last = tmp ;
first->next = tmp ;
length++ ;
}
template <class TYPE>
TYPE List<TYPE>::ExtractFromFront()
{
TYPE RetValue ;
ListNode<TYPE> * tmp ;
RetValue = first->next->elem ;
tmp = first->next->next ;
delete first->next ;
first->next = tmp ;
length-- ;
if ( ! tmp ) last = first ; return RetValue ;
}
template<class TYPE>
void List<TYPE>::Append( List<TYPE> * l )
{
if ( l )
Append( *l ) ;
}
template <class TYPE>
void List<TYPE>::Append( List<TYPE> & l )
{
if( ! l.Empty() )
{
last->next = l.first->next ;
last = l.last ;
length += l.Length() ;
}
}
template <class TYPE>
void List<TYPE>::AppendDeep( List<TYPE> l )
{
if (!Empty()) {
last->next=l.first; last=l.last;
length+=l.length;
l.first=l.last=NULL; } else {
first=l.first; last=l.last;
length=l.length;
l.first=l.last=NULL;
}
}
template <class TYPE>
void List<TYPE>::OwnsNothing()
{
last = first ;
first->next = 0 ;
length = 0 ;
}
template <class TYPE>
void List<TYPE>::Detach( ListNode<TYPE> * l )
{
ListNode<TYPE> * tmp ;
if( l->next == last )
last = l ;
tmp = l->next->next ;
delete l->next ;
l->next = tmp ;
length-- ;
}
template <class TYPE>
void List<TYPE>::Check( ListNode<TYPE> * l )
{
if( ! l )
{
cout << "List non ha potuto allocare un nodo : " << endl ;
cout << "MEMORIA ESAURITA !" << endl ;
abort() ;
}
}
#endif