// List.cc
// Jesse B. Dooley
// 28 May 1996
// template double linked List class
// The following overloaded operators are
// assumed for the L data type.
// < less than
// > greater than
// == equals
// << output stream
// >> input stream
// = assignment
// List.cpp
#ifndef LIST_CPP
#define LIST_CPP
#include <iostream.h> // UNIX
// prototype class
template <class L> class List;
// prototype input function
template <class L> istream& operator >> (istream&, List<L>&);
// prototype output function
template <class L> ostream& operator << (ostream&, List<L>& );
template<class L> class List {
struct node {
L ListData;
node *next, *previous;
};
node *first, *current, *last;
unsigned int m_ulPopulation;
unsigned int Counter_unsigned_int;
friend istream& operator >> (istream &IS , List<L> &A);
friend ostream& operator << (ostream &OS , List<L>& A );
public:
bool offEOL ()
{
return (current == NULL);
} // offEOL
bool push_front( L d )
{
// case 1. List is empty
if( empty() )
{
node *newnode = new node;
if (newnode == NULL)
return false;
newnode->next = NULL;
newnode->previous = NULL;
newnode->ListData = d;
first = newnode;
current = newnode;
last = newnode;
m_ulPopulation++;
return true;
}
// case 2. one or more nodes in the List
if( first->ListData < d )
return push_back( d );
node *newnode = new node;
if (newnode == NULL)
return false;
newnode->next = NULL;
newnode->previous = NULL;
newnode->ListData = d;
first->previous = newnode;
newnode->next = first;
current = newnode;
first = newnode;
m_ulPopulation++;
return true;
} // push_front
bool push_current( L d )
{
// case 1. List is empty
if( size() == 0 )
return push_front( d );
if( offEOL() )
return push_back( d );
// case 2. one node in List
if( size() == 1 )
{
// case 2.1 new node is less
if( first->ListData > d )
return push_front( d );
// case 2.2 new node is greater
if( first->ListData < d )
return push_back( d );
}
// case 3. two or more nodes. push BEFORE current
if( current == NULL )
return push_back( d );
node *newnode = new node;
if (newnode == NULL)
return 0;
node *Prev = current->previous;
newnode->ListData = d;
newnode->next = current;
newnode->previous = Prev;
Prev->next = newnode;
current->previous = newnode;
m_ulPopulation++;
return true;
} //
bool push_back( L d )
{
// case 1. no nodes in the List.
if( size() == 0 )
{
node *newnode = new node;
if (newnode == NULL)
return false;
newnode->next = NULL;
newnode->previous = NULL;
newnode->ListData = d;
first = newnode;
current = newnode;
last = newnode;
m_ulPopulation++;
return true;
}
// case 2. one node in the List
if( size() >= 1 )
{
node *newnode = new node;
if (newnode == NULL)
return false;
newnode->next = NULL;
newnode->previous = last;
newnode->ListData = d;
last->next = newnode;
current = newnode;
last = newnode;
m_ulPopulation++;
return true;
}
return false;
} // push_back
bool pop_back()
{
if (last == NULL)
return false;
if( last == first )
{
delete last;
first = NULL;
current = NULL;
last = NULL;
m_ulPopulation--;
return true;
}
current = last->previous;
current->next = NULL;
delete last;
last = current;
begin();
m_ulPopulation--;
return true;
}
bool pop_front()
{
if (first == NULL)
return false;
begin();
first = current->next;
if (first != NULL)
first->previous = NULL;
if (last == current)
last = NULL;
delete current;
begin();
m_ulPopulation--;
return true;
}
void begin()
{
current = first;
}
void end()
{
current = last;
}
void next()
{
if( current != NULL )
current = current->next;
}
void previous ()
{
if( current != NULL )
current = current->previous;
}
bool pop_current()
{
if(current == NULL)
return false;
if( current == first )
return pop_front();
if( current == last )
return pop_back();
current->previous->next = current->next;
current->next->previous = current->previous;
delete current;
begin();
m_ulPopulation--;
return true;
}
List()
{
first = current = last = NULL;
m_ulPopulation = 0;
Counter_unsigned_int = 0;
}
List( const List<L> &P )
// copy List P to List *this
{
if (P.first) {
first = new node;
first->ListData = P.first->ListData;
first->next = NULL;
first->previous = NULL;
current = first;
node *currL = P.first->next;
while (currL) {
current->next = new node;
current->previous = current;
current = current->next;
current->ListData = currL->ListData;
current->next = NULL;
currL = currL->next;
}
last = current;
}
else
{
first = NULL;
current = NULL;
last = NULL;
}
m_ulPopulation = P.m_ulPopulation;
Counter_unsigned_int = P.Counter_unsigned_int;
}
~List()
// deletes and frees List nodes from first to last
{
while (first)
{
node *ptr = first;
first = first ->next;
delete ptr;
}
first = NULL;
last = NULL;
current = NULL;
m_ulPopulation = 0;
}
List<L> operator = ( const List<L> &P )
{
if( P.first )
{
erase();
first = new node;
first->ListData = P.first->ListData;
first->next = NULL;
first->previous = NULL;
current = first;
node *currL = P.first->next;
while( currL )
{
current->next = new node;
current->previous = current;
current = current->next;
current->ListData = currL->ListData;
current->next = NULL;
currL = currL->next;
}
last = current;
}
else
{
first = NULL;
current = NULL;
last = NULL;
}
m_ulPopulation = P.m_ulPopulation;
Counter_unsigned_int = P.Counter_unsigned_int;
return *this;
} // =
List<L> operator += ( List<L> P )
{
node *currL = P.first;
while( currL )
{
AddToList( currL->ListData );
currL = currL->next;
}
return *this;
}
List<L> operator += ( L d)
{
if ( !find( d ) )
AddToList( d );
return *this;
}
int operator -= ( List<L> &D )
{
D.begin();
int hold_population = D.size();
while ( !D.offEOL() )
{
if( *this -= D.current->ListData)
{
hold_population--;
}
D.next();
}
return (hold_population == 0);
}
bool operator -= ( L d )
{
if (find( d ))
{
if (current == first)
return pop_front();
else if (current == last)
return pop_back();
else
return pop_current();
}
return false;
}
bool operator==( List<L>& List2 )
{
unsigned int i_List1size = size();
unsigned int i_List2size = List2.size();
if (i_List1size != i_List2size)
return 0;
while( i_List1size >= 0 )
{
L Temp1;
L Temp2;
getcurrent(Temp1);
List2.getcurrent(Temp2);
if (Temp2 != Temp1)
return 0;
next();
List2.next();
}
return true;
}
bool AddToList( L d )
{
if( find( d ) )
return false;
// d > first
if( current == first )
return push_front( d );
if( offEOL() )
return push_back( d );
return push_current( d );
}
unsigned int size()
{
// if( Counter_unsigned_int > 0 &&
// Counter_unsigned_int < m_ulPopulation )
// Counter_unsigned_int++;
// else
// Counter_unsigned_int = 0;
return m_ulPopulation;
}
void erase()
{
while( first )
pop_front();
}
bool empty ()
{
return (first == NULL);
}
bool find( L K )
{
begin();
while ( current != NULL )
{
if ( current->ListData == K )
return true;
if ( current->ListData > K )
return false;
next();
}
return false;
} // find
int findnum( const L &K )
{
int i_ReturnCount = 0;
node *p_Temp = NULL;
begin();
if ( !empty() )
{
while ( !offEOL() )
{
if ( current->ListData == K )
{
i_ReturnCount++;
p_Temp = current;
}
next();
}
}
current = p_Temp;
return i_ReturnCount;
} // findnum
L* getcurrent ()
{
if (current != NULL)
return ¤t->ListData;
return NULL;
}
bool getcurrent ( L &d )
{
if (current != NULL)
{
d = current->ListData;
return true;
}
return false;
}
int setcurrent ( L d )
{
if (current != NULL)
{
current->ListData = d;
return 1;
}
return 0;
}
L* front ( )
{
if (first != NULL)
return &first->ListData;
else
return NULL;
}
L* back()
{
if (last != NULL)
return &last->ListData;
return NULL;
}
void OutPut()
{
begin();
for( int i = 0; i < size(); i++ )
{
getcurrent()->OutPut();
next();
}
}
};
template <class L> istream& operator >> (istream &IS , List<L> &A)
{
if( IS )
{
L D;
IS >> D;
A += D;
}
return IS;
}
template <class L> ostream& operator << (ostream &OS , List<L>& A )
{
A.begin();
for( int i = 0; i < A.size(); i++ )
{
OS << A.getcurrent();
A.next();
}
return OS;
}
#endif // LIST_CPP
