//============================================================= // Doubly-Linked Lists dlist.h v1.00 // Defines templates for classes of doubly-linked lists // Copyright 1995 Scott Robert Ladd //============================================================= #ifndef DLIST_H #define DLIST_H #include "simple.h" #include "limits.h" #include "contx.h" //--------------------- // doubly-linked list //--------------------- template class DList { public: // constructors DList ( Boolean circ = BOOL_FALSE ); // copy constructor DList ( const DList & dlst, Boolean shallow = BOOL_FALSE ); // construct from array DList ( const T * array, size_t no ); // destructor ~DList(); // assignment operator (deep copy) void operator = ( const DList & dlst ); // conversion to array operator operator T * (); // append new item void Append ( const T & item ); // append an array of new items void Append ( const T * array, size_t no ); void Append ( const DList & dlst ); // delete current item void Delete(); // insert new item in current location void InsertBefore ( const T & item ); void InsertBefore ( const T * array, size_t no ); void InsertBefore ( const DList & dlst ); void InsertAfter ( const T & item ); void InsertAfter ( const T * array, size_t no ); void InsertAfter ( const DList & dlst ); // remove all items from the list void Erase(); // get current item T Get() const; // directly reference current item T & operator * (); // TRUE if current item is last item Boolean AtHead() const; Boolean AtTail() const; // set current item to head of list void ToHead() const; void ToTail() const; // move to next item in list Boolean ToNext() const; Boolean ToPrev() const; // interrogate list size_t GetCount() const; Boolean IsShallow() const; Boolean IsCircular() const; protected: // type defining a node in the list struct Node { T Data; Node * Next; Node * Prev; }; size_t Count; // # of items in list Node * Head; // first item Node * Tail; // last item Node * Work; // current item Boolean Shallow; // Is this a shallow copy? Boolean Circular; // is this a circular list? // internal utility functions void DeepCopy ( const DList & dlst ); void ShallowCopy ( const DList & dlst ); void SetNull(); }; // implement utility functions template void DList::DeepCopy ( const DList & dlst ) { if (dlst.Count == 0) return; Node * n = dlst.Head; while (n != NULL) { Append(n->Data); n = n->Next; } Work = Head; Shallow = BOOL_FALSE; Circular = dlst.Circular; } template inline void DList::ShallowCopy ( const DList & dlst ) { Head = dlst.Head; Tail = dlst.Tail; Work = dlst.Work; Count = dlst.Count; Shallow = BOOL_TRUE; Circular = dlst.Circular; } template inline void DList::SetNull() { Head = NULL; Tail = NULL; Work = NULL; Count = 0; } // constructors template inline DList::DList ( Boolean circ ) { SetNull(); Shallow = BOOL_FALSE; Circular = circ; } // copy constructor template DList::DList ( const DList & dlst, Boolean shallow ) { if (shallow) ShallowCopy(dlst); else { SetNull(); DeepCopy(dlst); } } // construct from array template DList::DList ( const T * array, size_t no ) { SetNull(); Circular = BOOL_FALSE; Shallow = BOOL_FALSE; if ((array == NULL) || (no == 0)) throw ContainerEx(CX_NULLARRAY); const T * aptr = array; for (size_t n = 0; n < no; ++n) { Append(*aptr); ++aptr; } } // destructor template inline DList::~DList() { Erase(); } // assignment operator (deep copy) template void DList::operator = ( const DList & dlst ) { Erase(); DeepCopy(dlst); } // conversion to array operator template DList::operator T * () { if (Count == 0) return NULL; T * result = new T [Count]; if (result == NULL) throw ContainerEx(CX_ARRAYALLOC); Node * temp = Head; T * aptr = result; while (temp != NULL) { *aptr = temp->Data; ++aptr; temp = temp->Next; } // note: caller must delete this array! return result; } // append new item template void DList::Append ( const T & item ) { Node * n = new Node; if (n == NULL) throw ContainerEx(CX_ALLOC); n->Data = item; n->Next = NULL; n->Prev = Tail; if (Count == 0) { Head = n; Tail = n; Work = n; } else { Tail->Next = n; Tail = n; } ++Count; } template void DList::Append ( const T * array, size_t no ) { if ((array == NULL) || (no == 0)) throw ContainerEx(CX_NULLARRAY); const T * aptr = array; for (size_t n = 0; n < no; ++n) { Append(*aptr); ++aptr; } } template void DList::Append ( const DList & dlst ) { const Node * n = dlst.Head; while (n != NULL) { Append(n->Data); n = n->Next; } } // delete current item template void DList::Delete() { if (Count == 0) throw ContainerEx(CX_NULL); if (Work == NULL) throw ContainerEx(CX_NOTREADY); if (Work == Head) { if (Work->Next == NULL) { delete Work; SetNull(); } else { Head = Work->Next; Head->Prev = NULL; delete Work; Work = Head; } } else { if (Work == Tail) { if (Work->Prev == NULL) { delete Work; SetNull(); } else { Tail = Work->Prev; Tail->Next = NULL; delete Work; Work = Tail; } } else { Node * n = Work->Next; Work->Prev->Next = Work->Next; Work->Next->Prev = Work->Prev; delete Work; Work = n; } } --Count; } // insert new item in current location template void DList::InsertBefore ( const T & item ) { if (Count == 0) throw ContainerEx(CX_NULL); if (Work == NULL) throw ContainerEx(CX_NOTREADY); Node * newnode = new Node; if (newnode == NULL) throw ContainerEx(CX_ALLOC); newnode->Data = item; if (Work == Head) { newnode->Next = Head; newnode->Prev = NULL; Head->Prev = newnode; Head = newnode; } else { Work->Prev->Next = newnode; newnode->Prev = Work->Prev; newnode->Next = Work; Work->Prev = newnode; } ++Count; } template void DList::InsertBefore ( const T * array, size_t no ) { for (size_t n = 0; n < no; ++n) InsertBefore(array[n]); } template void DList::InsertBefore ( const DList & dlst ) { const Node * n = dlst.Head; while (n != NULL) { InsertBefore(n->Data); n = n->Next; } } template void DList::InsertAfter ( const T & item ) { if (Count == 0) throw ContainerEx(CX_NULL); if (Work == NULL) throw ContainerEx(CX_NOTREADY); Node * newnode = new Node; if (newnode == NULL) throw ContainerEx(CX_ALLOC); newnode->Data = item; if (Work == Tail) { newnode->Next = NULL; newnode->Prev = Tail; Tail->Next = newnode; Tail = newnode; } else { Work->Next->Prev = newnode; newnode->Next = Work->Next; newnode->Prev = Work; Work->Next = newnode; } ++Count; } template void DList::InsertAfter ( const T * array, size_t no ) { // insert in reverse order, so they're stored in order for (size_t n = no; n > 0; --n) InsertAfter(array[n-1]); } template void DList::InsertAfter ( const DList & dlst ) { const Node * n = dlst.Tail; while (n != NULL) { InsertAfter(n->Data); n = n->Prev; } } // remove all items from the list template void DList::Erase() { if (!Shallow) { Work = Head; while (Work != NULL) { Head = Work->Next; delete Work; Work = Head; } } SetNull(); Shallow = BOOL_FALSE; } // get current item template T DList::Get() const { if (Count == 0) throw ContainerEx(CX_NULL); if (Work == NULL) throw ContainerEx(CX_NOTREADY); return Work->Data; } // directly reference current item template T & DList::operator * () { if (Count == 0) throw ContainerEx(CX_NULL); if (Work == NULL) throw ContainerEx(CX_NOTREADY); return Work->Data; } // TRUE if current item is last item template inline Boolean DList::AtHead() const { if (Work == Head) return BOOL_TRUE; else return BOOL_FALSE; } template inline Boolean DList::AtTail() const { if (Work == Tail) return BOOL_TRUE; else return BOOL_FALSE; } // set current item to head of list template inline void DList::ToHead() const { const_cast(Work) = Head; } template inline void DList::ToTail() const { const_cast(Work) = Tail; } // move to next item in list template Boolean DList::ToNext() const { if (Count == 0) throw ContainerEx(CX_NULL); if (Work == NULL) throw ContainerEx(CX_NOTREADY); if (Work == Tail) { if (Circular) const_cast(Work) = Head; else return BOOL_FALSE; } else const_cast(Work) = Work->Next; return BOOL_TRUE; } template Boolean DList::ToPrev() const { if (Count == 0) throw ContainerEx(CX_NULL); if (Work == NULL) throw ContainerEx(CX_NOTREADY); if (Work == Head) { if (Circular) const_cast(Work) = Tail; else return BOOL_FALSE; } else const_cast(Work) = Work->Prev; return BOOL_TRUE; } // interrogate list template inline size_t DList::GetCount() const { return Count; } template inline Boolean DList::IsShallow() const { return Shallow; } template inline Boolean DList::IsCircular() const { return Circular; } #endif