// dlist.cc
// Routines to implement a doubly linked list of arbitrary things.
// The list is dynamic and can have items with values of
// different types. The list can be maintained sorted, or
// sorted later.
#include
#include "dlist.h"
// The following class defines a "dlink" -- an item in a doubly
// linked list of elements with type T
// T is the type of the thing we want to put in the list.
template
class Dlink {
public:
Dlink(T newValue); // initialize the item
~Dlink(); // all local vars
Dlink* Next() { return next; }
Dlink* Prev() { return prev; }
void Prepend(Dlink* p); // add item before p
void Append(Dlink *p); // add item after p
void Remove(); // remove this from list
void Sort(Dlink *p); // sort Dlist by value
T value;
private:
Dlink* next;
Dlink* prev;
};
// ##########################
// # Dlink IMPLEMENTATION #
// ##########################
//----------------------------------------------------------------------
// The constructor for the Dlink class.
//----------------------------------------------------------------------
template
Dlink::Dlink(T newValue) {
value = newValue; // set value to the newValue
next = 0; // the link is not yet in a list,
prev = 0; // so set its next and prev to 0.
}
//----------------------------------------------------------------------
// The destructor for the Dlink class.
//----------------------------------------------------------------------
template
Dlink::~Dlink(T newValue) {
// nothing to do here
}
//----------------------------------------------------------------------
// Prepend for the Dlink class i.e. add "this" to the beginning of list
//----------------------------------------------------------------------
template
void
Dlink::Prepend(Dlink* p) {
if (p == 0) { // if first points to NULL then nothing to do.
return;
}
next = p; // next pointer of new Dlink points to where
// first did
prev = p->prev; // prev pointer of new Dlink points to
// where prev of first did
if (p->prev != 0) { // IF first Dlink's prev pointer is NOT zero
p->prev->next = this; // THEN point next pointer of previous
} // Dlink at this one
p->prev = this; // Point first's previous pointer at this
// one
}
//----------------------------------------------------------------------
// Append for the Dlink class i.e. add item after p
//----------------------------------------------------------------------
template
void
Dlink::Append(Dlink* p) {
if (p == 0) { // IF last points to NULL THEN nothing to do
return;
}
prev = p; // prev pointer of new Dlink points to where
// last did
next = p->next; // next pointer of new Dlink points to
// where next of first did
if (p->next != 0) { // IF last Dlink's next pointer is NOT zero
p->next->prev = this; // THEN point previous pointer of next
} // Dlink at this one
p->next = this; // Point last's next pointer at this
// one
}
//----------------------------------------------------------------------
// Remove for the Dlink class i.e. Take p out of the list and return p.
//----------------------------------------------------------------------
template
void
Dlink::Remove() {
if (this->prev != 0) {
this->prev->next = this->next;
}
if (this->next != 0) {
this->next->prev = this->prev;
}
}
//----------------------------------------------------------------------
// Sort for the Dlink class i.e. sort the Dlinks by value
//----------------------------------------------------------------------
template
void
Dlink::Sort(Dlink* p) {
int swaps;
T temp;
if (p == 0) { // if first points to NULL then nothing to do.
return;
}
// bubble sort -the best sorting algorithm
do {
swaps = 0; // clear our swap marker
while (p->prev != 0) { // go back to first link
p = p->prev;
}
while (p->next != 0) {
if (p->value > p->next->value) {
// IF we get here we have to
// do a swap
temp = p->next->value;
p->next->value = p->value;
p->value = temp;
swaps = 1;
} // end if
p = p->next;
} // end while
} while (swaps != 0);
}
// ########################
// # Dlist IMPLEMENTATION #
// ########################
//----------------------------------------------------------------------
// The constructor for the Dlist class.
//----------------------------------------------------------------------
template
Dlist::Dlist() {
first = 0; // It's a new list so first and last
last = 0; // pointers are set to NULL.
}
//----------------------------------------------------------------------
// The destructor for the Dlist class.
//----------------------------------------------------------------------
template
Dlist::~Dlist() {
// nothing to do here since no space was allocated (i.e. no "new")
}
//----------------------------------------------------------------------
// Prepend for the Dlist class i.e. add "this" to the beginning of list
//----------------------------------------------------------------------
template
void
Dlist::Prepend(T value) {
Dlink *item = new Dlink(value);
item->Prepend(first); // pass pointer to first Dlink::Prepend
first = item; // now first pointer points to this item
if (last == 0) // if last pointer = 0 then point it to
last = first; // the first Dlink just added
}
//----------------------------------------------------------------------
// Postpend for the Dlist class i.e. add "this" to the end of list
//----------------------------------------------------------------------
template
void
Dlist::Postpend(T value) {
Dlink *item = new Dlink(value);
item->Append(last); // pass pointer to last Dlink::Append
last = item; // now last pointer points to this item
if (first == 0) // if first pointer = 0 then point it to
first = last; // the first (last) Dlink just added
}
//----------------------------------------------------------------------
// Append for the Dlist class i.e. add "this" after p
//----------------------------------------------------------------------
template
void
Dlist::Append(T value, Dlink *p) {
Dlink *item = new Dlink(value);
item->Append(p); // pass pointer to p Dlink::Append
if (item->Next() == 0) {
last = item;
}
}
//----------------------------------------------------------------------
// Remove for the Dlist class i.e. Take p out of the list and return p.
//----------------------------------------------------------------------
template
Dlink*
Dlist::Remove(Dlink *p) {
if (p->Next() == 0) {
last = p->Prev();
}
if (p->Prev() == 0) {
first = p->Next();
}
p->Remove(); // pass pointer to Dlink::Remove
return p; // Return the pointer you passed.
}
//----------------------------------------------------------------------
// Sort for the Dlist class i.e. sort the Dlinks by value
//----------------------------------------------------------------------
template
void
Dlist::Sort() {
Dlink *item;
item->Sort(first); // pass pointer to first Dlink::Sort
}
//----------------------------------------------------------------------
// Print for the Dlist class i.e. prints the list
//----------------------------------------------------------------------
template
void
Dlist::Print() {
Dlink* tmp;
int i = 1;
for (tmp = first; tmp != 0; tmp = tmp->Next()) {
cout << " value: "
<< tmp->value <<"\n";
i++;
}
}
//----------------------------------------------------------------------
// SelfTest for the Dlist class i.e. Tests...
//----------------------------------------------------------------------
template
void
Dlist::SelfTest(T start) {
T count = start;
T end = start + 4;
for ( ; count <= end; count = count + 2) {
Prepend(count);
Postpend(count+1);
}
Append(count++,last);
Append(count,first);
cout << "first = " << First()->value <<
" last = " << Last()->value << "\n";
Print();
cout << "Testing Sort \n";
Sort();
Print();
cout << "Remove first item \n";
delete Remove(first);
Print();
cout << "first = " << First()->value <<
" last = " << Last()->value << "\n";
cout << "Remove last item \n";
delete Remove(last);
Print();
cout << "first = " << First()->value <<
" last = " << Last()->value << "\n";
cout << "Remove second item \n";
delete Remove(first->Next());
Print();
for (Dlink* tmp = last; tmp != 0; tmp = last) {
delete Remove(tmp);
}
cout << "Removed all items \n";
Print();
}
int
main() {
Dlist *list1 = new Dlist ();
Dlist *list2 = new Dlist ();
cout << "Testing Dlist \n";
list1->SelfTest(6);
cout << "Testing Dlist \n";
list2->SelfTest('d');
delete list1; // always delete what you allocate
delete list2; // always delete what you allocate
return 0;
}