C++ Pointer List
//====================================================================
// PtrList.h -- Generic doubly-linked lists of type void*
//
// CPtrList(er), CPtrStack(er), CPtrQueue(r)
//
// Implementation:
// Doubly-linked circular list of void pointers.
//
// USAGE: (Note: user would derive a class from CPtrList(er) to
// return pointers to the class rather than void*
//
// someStructureOrClass data1;
// CPtrList list;
// CPtrLister next (list);
// void* ptr;
//
// list.Insert (&data1);
// ...
//
// while (ptr = next ()) cout << *(int*) ptr << ' ';
//
// Revision History:
// 12/22/95 Skews Me Created
//====================================================================
#ifndef _PTRLIST_H_
#define _PTRLIST_H_
#ifndef _INC_IOSTREAM
#include <iostream.h>
#endif
typedef int BOOL;
//====================================================================
// CPtrList -- Container class for list of type void*
//
// Implementation:
// Doubly-linked circular list of void pointers.
// The curr->data member is compared against NULL
// to determine whether the current pointer is at the head.
//====================================================================
class CPtrList
{
public:
friend class CPtrLister;
CPtrList (void) { Init (); }
CPtrList (const CPtrList& list) { Init (); *this = list; }
~CPtrList (void) { Clear (); }
inline const BOOL IsEmpty (void) const { return &head == head.next; }
BOOL Insert (const void* data); // before element
void* Remove (void);
void Clear (void);
inline void* Reset (void) { ResetCurr (); return GetData (); }
inline void* Next (void) { curr = curr->next; return GetData (); }
inline void* Prev (void) { curr = curr->prev; return GetData (); }
void* Find (const void* key,
BOOL fun (const void* key,
void* data));
// Searches the list given a key with callback function of form:
// BOOL CallbackFunction (const void* key, void* data);
// The callback function should return TRUE if the item matches.
// Otherwise the callback function should return FALSE to
// continue searching.
// Returns the found data item if successful, otherwise NULL.
const CPtrList& operator = (const CPtrList& list);
friend ostream& operator << (ostream& output, CPtrList& list);
protected:
inline void* GetData (void) const { return (void*) curr->data; }
inline void ResetCurr (void) { curr = head.next; }
void Init (void);
struct PtrNode
{
PtrNode (const void* data = NULL) : data (data) { }
~PtrNode () { }
const void* data;
PtrNode* next;
PtrNode* prev;
};
PtrNode* curr;
PtrNode head;
}; // CPtrList
//====================================================================
// CPtrLister
//
// Implementation:
// Iterator for CPtrList
//====================================================================
class CPtrLister
{
public:
CPtrLister (const CPtrList& list) : list (&list) { Reset (); }
~CPtrLister (void) { }
inline void* operator () (void) // Next ()
{ curr = curr->next; return (void*) curr->data; }
inline void Reset (void) { curr = (CPtrList::PtrNode*) &list->head; }
protected:
const CPtrList* list;
CPtrList::PtrNode* curr;
}; // PtrLister
//====================================================================
// CPtrStack -- LIFO (Last In First Out) list
//====================================================================
class CPtrStack : private CPtrList
{
public:
friend class CPtrStacker;
CPtrStack (void) : CPtrList () { }
CPtrStack (const CPtrStack& stack) : CPtrList (stack) { }
~CPtrStack (void) { }
inline const BOOL IsEmpty (void) const { return CPtrList::IsEmpty (); }
inline BOOL Push (const void* data)
{ if (CPtrList::Insert (data)) { CPtrList::Prev (); return TRUE; }
else return FALSE;
}
inline void* Pop (void) { return CPtrList::Remove (); }
inline void Clear (void) { CPtrList::Clear (); }
inline void* Top (void)
{ CPtrList::ResetCurr (); return CPtrList::GetData (); }
inline const CPtrStack& operator = (const CPtrStack& stack)
{ return (CPtrStack&) CPtrList::operator = (stack); }
inline friend ostream& operator << (ostream& output, CPtrStack& stack)
{ return operator << (output, (CPtrList&) stack); }
}; // CPtrStack
//====================================================================
// CPtrStacker
//
// Implementation:
// Iterator for CPtrStack
//====================================================================
class CPtrStacker : CPtrLister
{
public:
CPtrStacker (const CPtrStack& stack) : CPtrLister (stack) { }
~CPtrStacker (void) { }
inline void* operator () (void) // Next ()
{ return CPtrLister::operator () (); }
inline void Top (void) { CPtrLister::Reset (); }
}; // PtrStacker
//====================================================================
// CPtrQueue -- FIFO (First In First Out) list
//====================================================================
class CPtrQueue : private CPtrList
{
public:
friend class CPtrQueuer;
CPtrQueue (void) : CPtrList () { }
CPtrQueue (const CPtrQueue& queue) : CPtrList (queue) { }
~CPtrQueue (void) { }
inline const BOOL IsEmpty (void) const { return CPtrList::IsEmpty (); }
inline BOOL Enqueue (const void* data) { return CPtrList::Insert (data); }
inline void* Dequeue (void) { return CPtrList::Remove (); }
inline void Clear (void) { CPtrList::Clear (); }
inline void* Front (void) { CPtrList::ResetCurr (); return CPtrList::GetData (); }
inline const CPtrQueue& operator = (const CPtrQueue& queue)
{ return (CPtrQueue&) CPtrList::operator = (queue); }
inline friend ostream& operator << (ostream& output, CPtrQueue& queue)
{ return operator << (output, (CPtrList&) queue); }
}; // CPtrStack
//====================================================================
// CPtrQueuer
//
// Implementation:
// Iterator for CPtrQueue
//====================================================================
class CPtrQueuer : CPtrLister
{
public:
CPtrQueuer (const CPtrQueue& queue) : CPtrLister (queue) { }
~CPtrQueuer (void) { }
inline void* operator () (void) // Next ()
{ return CPtrLister::operator () (); }
inline void Front (void) { CPtrLister::Reset (); }
}; // PtrQueuer
#endif // _PTRLIST_H_
|
//====================================================================
// PtrList.cpp -- Generic list of type void*
//
// Implementation:
// Doubly-linked circular list of void pointers.
// The curr->data member is compared against NULL
// to determine whether the current pointer is at the head.
//
// USAGE:
// CPtrLister next (list);
// void* ptr;
//
// while (ptr = next ()) cout << *(int*) ptr << ' ';
//
// Revision History:
// 12/22/95 Skews Me Created
//====================================================================
#include <iostream.h>
#include <string.h>
#ifndef _PTRLIST_H_
#include "PtrList.h"
#endif
//====================================================================
// Init
//====================================================================
void CPtrList::Init (void)
{
head.data = NULL;
head.prev = head.next = &head;
Reset ();
return;
} // Init
//====================================================================
// Insert
//
// Allocates and inserts a new node into the list
// before the current node.
//
// LOGIC:
// Point to new's current and previous nodes
// and fix-up previous and next nodes
//====================================================================
BOOL CPtrList::Insert (const void* data)
{
PtrNode* node;
if ((node = new PtrNode (data)) != NULL)
{
node->next = curr;
node->prev = curr->prev;
curr->prev = node->prev->next = node;
return TRUE;
}
else
return FALSE;
} // Insert
//====================================================================
// Remove
//
// Deletes the current node from the list
// and returns its data.
//====================================================================
void* CPtrList::Remove (void)
{
void* data = GetData ();
if (data != NULL)
{
PtrNode* prev = curr->prev;
prev->next = curr->next;
prev->next->prev = curr->prev;
delete curr;
curr = prev->next;
}
return data;
} // Remove
//====================================================================
// Clear
//====================================================================
void CPtrList::Clear (void)
{
ResetCurr ();
while (! IsEmpty () && Remove ());
return;
} // Clear
//====================================================================
// operator =
//
// UNDONE: While Insert shouldn't fail here because that much memory
// has just been freed, a try...catch exception handler
// should be added.
//====================================================================
const CPtrList& CPtrList::operator = (const CPtrList& list)
{
if (this != &list)
{
Clear ();
CPtrLister next (list);
void* data;
while ((data = next ()) != NULL)
{
Insert (data);
}
}
return *this;
} // operator =
//====================================================================
// Find
//====================================================================
void* CPtrList::Find (const void* key, BOOL FindKeyProc (const void* key, void* data))
{
CPtrLister next (*this);
void* data;
while ((data = next ()) != NULL)
{
if ((*FindKeyProc) (key, data))
{
return data;
}
}
return NULL;
} // Find
//====================================================================
// operator <<
//====================================================================
ostream& operator << (ostream& output, CPtrList& list)
{
CPtrLister next (list);
void* data;
while ((data = next ()) != NULL)
{
output << (char*) data << ' ';
}
return output << '\n';
} // operator <<
|
|