home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / llist.zip / LLIST.CPP < prev   
Text File  |  1994-04-09  |  8KB  |  294 lines
  1. /*----------------------------------------------------------------------------*/
  2. /*  (c) Larry Morley, 1994                                                    */
  3. /*                                                                            */
  4. /*  Module:      llist.cpp                                                    */
  5. /*  Description: Linked list class definitions                                */
  6. /*                                                                            */
  7. /*  ListObject          : An element in a list.                               */
  8. /*  LinkedList          : A doubly linked list of ListObject                  */
  9. /*                                                                            */
  10. /*----------------------------------------------------------------------------*/
  11.  
  12. #include <stdio.h>
  13. #include <string.h>
  14. #include "cpptype.h"
  15.  
  16. class   ListObject;
  17. class   LinkedList;
  18. typedef ListObject *pListObject;
  19.  
  20. //----------------------------------------------------------------------------//
  21.  
  22. class ListObject
  23. {
  24.  
  25.    friend class LinkedList;
  26.  
  27.    protected:
  28.  
  29.       // Pointers for list object's linkage
  30.       ListObject *pNext;
  31.       ListObject *pPrevious;
  32.  
  33.    public:
  34.  
  35.       ListObject()
  36.       {
  37.          pNext     =
  38.          pPrevious = (ListObject *)0;
  39.       }
  40.  
  41.       // Test for equality with
  42.       // another ListObject
  43.       virtual BOOLEAN IsEqual(ListObject *p)
  44.       {
  45.          // Do a byte-level compare:
  46.          // If zero, the objects match.
  47.          if (memcmp((void *)this,(void *)p,sizeof(ListObject)))
  48.             return FALSE;
  49.          return TRUE;
  50.       }
  51.  
  52.       // Return the next object in the list
  53.       ListObject *Next(void)
  54.       {
  55.          return pNext;
  56.       };
  57.  
  58.       // Return the previous object in the list
  59.       ListObject *Previous(void)
  60.       {
  61.          return pPrevious;
  62.       };
  63.  
  64. };
  65.  
  66. //----------------------------------------------------------------------------//
  67.  
  68. class LinkedList
  69. {
  70.  
  71.    protected:
  72.  
  73.       // Pointers to first and last
  74.       // object in the list
  75.       ListObject *pFirst;
  76.       ListObject *pLast;
  77.  
  78.    public:
  79.  
  80.       // Set the head and tail pointers to NULL
  81.       // (empty list).
  82.       LinkedList()
  83.       {
  84.          pFirst =
  85.          pLast  = (ListObject *)NULL;
  86.       };
  87.  
  88.       // Add an object to the list
  89.       virtual void AddObject(ListObject *p);
  90.  
  91.       // Remove an object from the list
  92.       // Returns TRUE if object is found;
  93.       // FALSE otherwise.
  94.       virtual BOOLEAN DeleteObject(ListObject *p);
  95.  
  96.       // Return the first item in the list
  97.       ListObject *GetFirst(void)
  98.       {
  99.          return pFirst;
  100.       };
  101.  
  102.       // IsEmpty() - is list empty?
  103.       // Returns TRUE if pFirst and pLast are both NULL
  104.       BOOLEAN IsEmpty(void)
  105.       {
  106.         return (BOOLEAN)((!pFirst) && (!pLast)) ? TRUE : FALSE;
  107.       };
  108.  
  109. };
  110.  
  111. //----------------------------------------------------------------------------//
  112.  
  113. void LinkedList :: AddObject(ListObject *p)
  114. {
  115.    if (!pFirst) // If list is empty, set the list ptrs
  116.    {            // to point to the object
  117.       pFirst =
  118.       pLast  = p;
  119.  
  120.       // Set the object's linkage ptrs to NULL
  121.       p->pNext     =
  122.       p->pPrevious = (ListObject *)0;
  123.  
  124.       return;
  125.    }
  126.    else // Add the object to the head of the list
  127.    {    // and adust the head of list pointer to
  128.         // point to the new object.  Update the
  129.         // pPrevious pointer of the former head
  130.         // of the list.
  131.  
  132.       pFirst->pPrevious = p;  // The former head of list now
  133.                               // has a previous item.
  134.       p->pNext          = pFirst;
  135.       p->pPrevious      = (ListObject *)0;
  136.       pFirst            = p;
  137.  
  138.    };
  139.  
  140.    return;
  141.  
  142. }
  143.  
  144. //----------------------------------------------------------------------------//
  145. class MyObject;
  146.  
  147. BOOLEAN LinkedList :: DeleteObject(ListObject *p)
  148. {
  149.    ListObject *q;
  150.  
  151.    // Walk through the list, and
  152.    // try to find the desired object
  153.  
  154.    for (q=pFirst;q;q=q->pNext)
  155.    {
  156.       if (q->IsEqual(p))  // Ask the ListObject if it's the same
  157.       {                   // as the current one using the
  158.                           // IsEqual() member function of ListObject.
  159.          // Case 1:
  160.          // One item in list
  161.          if ((!(q->pPrevious))&&(!(q->pNext)))
  162.          {
  163.             pFirst = pLast = (ListObject *)0;
  164.             return TRUE;
  165.          }
  166.  
  167.          // Case 2:
  168.          // Last item in list
  169.          if (!(q->pNext))
  170.          {
  171.             pLast = q->pPrevious;
  172.             if (q->pPrevious)
  173.                (q->pPrevious)->pNext = (ListObject *)0;
  174.             return TRUE;
  175.          }
  176.  
  177.          // Case 3:
  178.          // First item in list
  179.          if (!(q->pPrevious))
  180.          {
  181.             pFirst = q->pNext;
  182.             if (q->pNext)
  183.                (q->pNext)->pPrevious = (ListObject *)0;
  184.             return TRUE;
  185.          }
  186.  
  187.          // Case 4:
  188.          // "Normal" item
  189.          (q->pPrevious)->pNext = q->pNext;
  190.          (q->pNext)->pPrevious = q->pPrevious;
  191.          return TRUE;
  192.  
  193.          // Catch-All Case:
  194.          // If this code is ever reached then
  195.          // something is drastically wrong...
  196.          printf(
  197.             "Unexpected case encountered in LinkedList::DeleteObject().\n");
  198.          return FALSE;
  199.  
  200.       }
  201.    }
  202.  
  203.    // Object not found
  204.    return FALSE;
  205.  
  206. }
  207.  
  208. //----------------------------------------------------------------------------//
  209. // Derive a class from type ListObject with some text                         //
  210. //----------------------------------------------------------------------------//
  211.  
  212. class MyObject : public ListObject
  213. {
  214.  
  215.    public:
  216.  
  217.       char *szItemText;
  218.  
  219.       MyObject(char *szText)
  220.       {
  221.          szItemText = szText;
  222.       };
  223.  
  224.       BOOLEAN IsEqual(ListObject *p)
  225.       {
  226.          if (!(strcmp(((MyObject *)p)->szItemText,szItemText)))
  227.             return TRUE;
  228.          return FALSE;
  229.       };
  230.  
  231. };
  232.  
  233. //----------------------------------------------------------------------------//
  234. // Try out our new classes.                                                   //
  235. //----------------------------------------------------------------------------//
  236.  
  237. int main()
  238. {
  239.  
  240.    // Declare a pointer to a list
  241.    LinkedList *pMyList;
  242.    // Declare a pointer to an object
  243.    MyObject   *pMyObj;
  244.  
  245.    // Create the list
  246.    pMyList = new LinkedList;
  247.  
  248.    // Add some objects to the list
  249.    pMyObj  = new MyObject("Text String 0");
  250.    pMyList->AddObject(pMyObj);
  251.    pMyObj  = new MyObject("Text String 1");
  252.    pMyList->AddObject(pMyObj);
  253.    pMyObj  = new MyObject("Text String 2");
  254.    pMyList->AddObject(pMyObj);
  255.    pMyObj  = new MyObject("Text String 3");
  256.    pMyList->AddObject(pMyObj);
  257.    pMyObj  = new MyObject("Text String 4");
  258.    pMyList->AddObject(pMyObj);
  259.  
  260.    // Remove an object from the list
  261.    pMyObj  = new MyObject("Text String 2");
  262.    pMyList->DeleteObject(pMyObj);
  263.  
  264.    // And, print the list's contents and
  265.    // the linkage among the objects.
  266.    pMyObj = (MyObject *)pMyList->GetFirst();
  267.  
  268.    while (pMyObj)
  269.    {
  270.       printf("\nList Contents and Object Linkage:\n");
  271.       printf("-------------------------------------------\n");
  272.       printf("Object Text   :  %s\n",pMyObj->szItemText);
  273.       printf("       Address:  %lX\n",pMyObj);
  274.       printf("       Next Obj: %lX\n",pMyObj->Next());
  275.       printf("       Prev Obj: %lX\n",pMyObj->Previous());
  276.       pMyObj = (MyObject *)pMyObj->Next();
  277.    }
  278.  
  279.    printf("-------------------------------------------\n");
  280.  
  281.    MyObject *p;
  282.    pMyObj = (MyObject *)pMyList->GetFirst();
  283.    while (pMyObj)
  284.    {
  285.       p = (MyObject *)pMyObj->Next();
  286.       delete pMyObj;
  287.       pMyObj = p;
  288.    }
  289.  
  290.    return 0;
  291. }
  292.  
  293. //----------------------------------------------------------------------------//
  294.