home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Shareware BBS: 10 Tools
/
10-Tools.zip
/
llist.zip
/
LLIST.CPP
< prev
Wrap
Text File
|
1994-04-09
|
8KB
|
294 lines
/*----------------------------------------------------------------------------*/
/* (c) Larry Morley, 1994 */
/* */
/* Module: llist.cpp */
/* Description: Linked list class definitions */
/* */
/* ListObject : An element in a list. */
/* LinkedList : A doubly linked list of ListObject */
/* */
/*----------------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include "cpptype.h"
class ListObject;
class LinkedList;
typedef ListObject *pListObject;
//----------------------------------------------------------------------------//
class ListObject
{
friend class LinkedList;
protected:
// Pointers for list object's linkage
ListObject *pNext;
ListObject *pPrevious;
public:
ListObject()
{
pNext =
pPrevious = (ListObject *)0;
}
// Test for equality with
// another ListObject
virtual BOOLEAN IsEqual(ListObject *p)
{
// Do a byte-level compare:
// If zero, the objects match.
if (memcmp((void *)this,(void *)p,sizeof(ListObject)))
return FALSE;
return TRUE;
}
// Return the next object in the list
ListObject *Next(void)
{
return pNext;
};
// Return the previous object in the list
ListObject *Previous(void)
{
return pPrevious;
};
};
//----------------------------------------------------------------------------//
class LinkedList
{
protected:
// Pointers to first and last
// object in the list
ListObject *pFirst;
ListObject *pLast;
public:
// Set the head and tail pointers to NULL
// (empty list).
LinkedList()
{
pFirst =
pLast = (ListObject *)NULL;
};
// Add an object to the list
virtual void AddObject(ListObject *p);
// Remove an object from the list
// Returns TRUE if object is found;
// FALSE otherwise.
virtual BOOLEAN DeleteObject(ListObject *p);
// Return the first item in the list
ListObject *GetFirst(void)
{
return pFirst;
};
// IsEmpty() - is list empty?
// Returns TRUE if pFirst and pLast are both NULL
BOOLEAN IsEmpty(void)
{
return (BOOLEAN)((!pFirst) && (!pLast)) ? TRUE : FALSE;
};
};
//----------------------------------------------------------------------------//
void LinkedList :: AddObject(ListObject *p)
{
if (!pFirst) // If list is empty, set the list ptrs
{ // to point to the object
pFirst =
pLast = p;
// Set the object's linkage ptrs to NULL
p->pNext =
p->pPrevious = (ListObject *)0;
return;
}
else // Add the object to the head of the list
{ // and adust the head of list pointer to
// point to the new object. Update the
// pPrevious pointer of the former head
// of the list.
pFirst->pPrevious = p; // The former head of list now
// has a previous item.
p->pNext = pFirst;
p->pPrevious = (ListObject *)0;
pFirst = p;
};
return;
}
//----------------------------------------------------------------------------//
class MyObject;
BOOLEAN LinkedList :: DeleteObject(ListObject *p)
{
ListObject *q;
// Walk through the list, and
// try to find the desired object
for (q=pFirst;q;q=q->pNext)
{
if (q->IsEqual(p)) // Ask the ListObject if it's the same
{ // as the current one using the
// IsEqual() member function of ListObject.
// Case 1:
// One item in list
if ((!(q->pPrevious))&&(!(q->pNext)))
{
pFirst = pLast = (ListObject *)0;
return TRUE;
}
// Case 2:
// Last item in list
if (!(q->pNext))
{
pLast = q->pPrevious;
if (q->pPrevious)
(q->pPrevious)->pNext = (ListObject *)0;
return TRUE;
}
// Case 3:
// First item in list
if (!(q->pPrevious))
{
pFirst = q->pNext;
if (q->pNext)
(q->pNext)->pPrevious = (ListObject *)0;
return TRUE;
}
// Case 4:
// "Normal" item
(q->pPrevious)->pNext = q->pNext;
(q->pNext)->pPrevious = q->pPrevious;
return TRUE;
// Catch-All Case:
// If this code is ever reached then
// something is drastically wrong...
printf(
"Unexpected case encountered in LinkedList::DeleteObject().\n");
return FALSE;
}
}
// Object not found
return FALSE;
}
//----------------------------------------------------------------------------//
// Derive a class from type ListObject with some text //
//----------------------------------------------------------------------------//
class MyObject : public ListObject
{
public:
char *szItemText;
MyObject(char *szText)
{
szItemText = szText;
};
BOOLEAN IsEqual(ListObject *p)
{
if (!(strcmp(((MyObject *)p)->szItemText,szItemText)))
return TRUE;
return FALSE;
};
};
//----------------------------------------------------------------------------//
// Try out our new classes. //
//----------------------------------------------------------------------------//
int main()
{
// Declare a pointer to a list
LinkedList *pMyList;
// Declare a pointer to an object
MyObject *pMyObj;
// Create the list
pMyList = new LinkedList;
// Add some objects to the list
pMyObj = new MyObject("Text String 0");
pMyList->AddObject(pMyObj);
pMyObj = new MyObject("Text String 1");
pMyList->AddObject(pMyObj);
pMyObj = new MyObject("Text String 2");
pMyList->AddObject(pMyObj);
pMyObj = new MyObject("Text String 3");
pMyList->AddObject(pMyObj);
pMyObj = new MyObject("Text String 4");
pMyList->AddObject(pMyObj);
// Remove an object from the list
pMyObj = new MyObject("Text String 2");
pMyList->DeleteObject(pMyObj);
// And, print the list's contents and
// the linkage among the objects.
pMyObj = (MyObject *)pMyList->GetFirst();
while (pMyObj)
{
printf("\nList Contents and Object Linkage:\n");
printf("-------------------------------------------\n");
printf("Object Text : %s\n",pMyObj->szItemText);
printf(" Address: %lX\n",pMyObj);
printf(" Next Obj: %lX\n",pMyObj->Next());
printf(" Prev Obj: %lX\n",pMyObj->Previous());
pMyObj = (MyObject *)pMyObj->Next();
}
printf("-------------------------------------------\n");
MyObject *p;
pMyObj = (MyObject *)pMyList->GetFirst();
while (pMyObj)
{
p = (MyObject *)pMyObj->Next();
delete pMyObj;
pMyObj = p;
}
return 0;
}
//----------------------------------------------------------------------------//