home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_300 / 308_01 / sgl_list.cpp < prev    next >
C/C++ Source or Header  |  1990-09-21  |  8KB  |  352 lines
  1.  
  2. /*
  3.     TITLE:          Singly-linked list object;
  4.     DESCRIPTION:    "C++ singly-linked list object;
  5.     VERSION:        1.0;
  6.     DATE:           9/21/90;
  7.     COMPILERS:      Borland Turbo C++ V.1.0;
  8.     KEYWORDS:       C++ linked list object;
  9.     FILENAME:       Sgl_List.cpp;
  10.     SEE-ALSO:    Sgl_List.hpp, BaseList.hpp;
  11.  
  12.     AUTHOR:         Michael Kelly
  13.             254 Gold St. Boston Ma. 02127
  14.             Copyright 1990;
  15.  
  16.     COPYRIGHT:    This code may not be commercially distributed
  17.             without prior arrangement with the author.  It
  18.             may be used by programmers, without royalty, for
  19.             their personal programs and for "one of a kind"
  20.             or "custom" applications, provided that said
  21.             programmers assume all liability concerning
  22.             same.
  23. */
  24.  
  25.  
  26.  //                 ----------< SingleList Object >----------
  27.  
  28. #include <stdlib.h>
  29. #include "sgl_list.hpp"
  30.  
  31.  
  32. //                ----------< Public Methods >----------
  33.  
  34. /********************
  35. SingleList::~SingleList(void):
  36.      Description: destructor
  37.      ********************/
  38.  
  39. SingleList::~SingleList(void)
  40. {
  41.     while(delete_item())
  42.     ;       // empty loop -- deletes every link in list
  43.  
  44.     if(lerror == EMPTY_LIST)
  45.     lerror = OK;
  46. }
  47.  
  48.  
  49. /********************
  50. Boolean SingleList::add_item(void *item, size_t itemsize, Place place):
  51.      Description: add a new item to list at Place place
  52.      ********************/
  53.  
  54. Boolean SingleList::add_item(void *item, size_t itemsize, Place place)
  55. {
  56.     Entry *newentry;
  57.     SingleLink *newlink;
  58.     void *ptr = item;   // avoids empty char array being flagged as NULL ptr
  59.  
  60.     lerror = OK;
  61.  
  62.     if(! ptr)
  63.     lerror = NULL_PTR;
  64.     if(itemsize < 1)
  65.     lerror = INV_SIZE;
  66.  
  67.     if(lerror)
  68.     return False;
  69.  
  70.     if(! (newlink = new SingleLink))  {
  71.     lerror = NO_MEM;
  72.     return False;
  73.     }
  74.     if(! (newentry = new Entry))  {
  75.     delete newlink;
  76.     lerror = NO_MEM;
  77.     return False;
  78.     }
  79.     if(! (newentry->item = new char[itemsize]))  {
  80.     delete newentry;
  81.     delete newlink;
  82.     lerror = NO_MEM;
  83.     return False;
  84.     }
  85.  
  86.     memmove(newentry->item, item, itemsize);
  87.     newentry->itemsize = itemsize;
  88.     newlink->entry = newentry;
  89.  
  90.     if(! entries)  {                            // adding to empty list
  91.     newlink->Next = NULL;
  92.     First = Last = Current = newlink;
  93.         entries = 1;
  94.     return True;
  95.     }
  96.  
  97.     if(place == FirstPlace)  {
  98.     newlink->Next = First;
  99.     First = newlink;
  100.     }
  101.     else if(place == LastPlace  ||  Current == Last)  {
  102.     newlink->Next = NULL;
  103.     Last->Next = newlink;
  104.     Last = newlink;
  105.     }
  106.     else  {
  107.     newlink->Next = Current->Next;
  108.     Current->Next = newlink;
  109.     }
  110.  
  111.     Current = newlink;
  112.     entries++;
  113.     return True;
  114. }
  115.  
  116.  
  117. /********************
  118. Boolean SingleList::delete_item(void):
  119.      Description: delete the current item from the list
  120.      ********************/
  121.  
  122. Boolean SingleList::delete_item(void)
  123. {
  124.     lerror = OK;
  125.  
  126.     if(! entries)
  127.     lerror = EMPTY_LIST;
  128.     if(entries  &&  ! Current)
  129.         lerror = NULL_PTR;
  130.  
  131.     if(lerror)
  132.     return False;
  133.  
  134.     delete Current->entry->item;
  135.     delete Current->entry;
  136.  
  137.     if(entries == 1)  {        // deleting the only item in the list
  138.     delete First;
  139.     First = Last = Current = NULL;
  140.     entries = 0;
  141.     return True;
  142.     }
  143.  
  144.     if(Current == First)  {
  145.     First = First->Next;
  146.     }
  147.     else if(Current == Last)  {
  148.       SingleLink *save_first = First;
  149.     while(First->Next  &&  First->Next != Last)
  150.         First = First->Next;
  151.     First->Next = NULL;
  152.     Last = First;
  153.     First = save_first;
  154.     }
  155.     else  {
  156.       SingleLink *save_first = First;
  157.     while(First->Next  &&  First->Next != Current)
  158.         First = First->Next;
  159.     First->Next = Current->Next;
  160.     First = save_first;
  161.     }
  162.  
  163.     delete Current;
  164.     Current = First;
  165.     entries--;
  166.     return True;
  167. }
  168.  
  169.  
  170. /********************
  171. Boolean SingleList::get_item(void *itembuf):
  172.      Description: copy the current item in the list to itembuf
  173.      ********************/
  174.  
  175. Boolean SingleList::get_item(void *itembuf)
  176. {
  177.     void *ptr = itembuf;
  178.  
  179.     lerror = OK;
  180.  
  181.     if(! entries)
  182.     lerror = EMPTY_LIST;
  183.     if(entries  &&  (! ptr  ||  ! Current))
  184.     lerror = NULL_PTR;
  185.  
  186.     if(lerror)
  187.     return False;
  188.  
  189.     memmove(itembuf, Current->entry->item, Current->entry->itemsize);
  190.     return True;
  191. }
  192.  
  193.  
  194. /********************
  195. Boolean SingleList::prev(void):
  196.      Description: make previous item the "current" item
  197.      ********************/
  198.  
  199. Boolean SingleList::prev(void)
  200. {
  201.     if(Current == First)
  202.     return False;
  203.     else  {
  204.       SingleLink *save_first = First;
  205.     while(First->Next  &&  First->Next != Current)
  206.         First = First->Next;
  207.     Current = First;
  208.     First = save_first;
  209.     }
  210.  
  211.     return True;
  212. }
  213.  
  214. /********************
  215. int SingleList::compare_item(void *item1):
  216.      Description: compare item1 with current item in list
  217.      ********************/
  218.  
  219. int SingleList::compare_item(void *item1)
  220. {
  221.     void *ptr = item1;
  222.  
  223.     lerror = OK;
  224.  
  225.     if(! entries)
  226.     lerror = EMPTY_LIST;
  227.     if(entries  &&  (! Current  ||  ! ptr))
  228.     lerror = NULL_PTR;
  229.  
  230.     if(lerror)
  231.     return 0;
  232.  
  233.     return compare(item1, Current->entry->item);
  234. }
  235.  
  236.  
  237. /********************
  238. Boolean SingleList::find_item(void *item1):
  239.      Description: search the list for item that matches item1
  240.      ********************/
  241.  
  242. Boolean SingleList::find_item(void *item1)
  243. {
  244.     int dif;
  245.     void *ptr = item1;
  246.  
  247.     lerror = OK;
  248.  
  249.  
  250.     if(! entries)
  251.     lerror = EMPTY_LIST;
  252.     if(entries  &&  (! first() || ! ptr))
  253.         lerror = NULL_PTR;
  254.  
  255.     if(lerror)
  256.     return False;
  257.  
  258.     while((dif = compare_item(item1))  &&  SingleList::next())
  259.     ;    // empty loop -- sequential search for match
  260.  
  261.     return (Boolean) !dif; // logically convert integer result to boolean
  262. }
  263.  
  264.  
  265. /********************
  266. Boolean SingleList::replace_item(void *newitem, size_t newsize):
  267.      Description: replace the "current" item in list with newitem
  268.      ********************/
  269.  
  270. Boolean SingleList::replace_item(void *newitem, size_t newsize)
  271. {
  272.     void *ptr = newitem;
  273.     void *tmp;
  274.  
  275.     lerror = OK;
  276.  
  277.     if(! entries)
  278.     lerror = EMPTY_LIST;
  279.     if(entries  &&  ! ptr)
  280.         lerror = NULL_PTR;
  281.     if(! newsize)
  282.         lerror = INV_SIZE;
  283.  
  284.     if(lerror)
  285.     return False;
  286.  
  287.     if(! (tmp = new char[newsize]))  {
  288.     lerror = NO_MEM;
  289.     return False;
  290.     }
  291.     delete Current->entry->item;
  292.     Current->entry->item = tmp;
  293.     Current->entry->itemsize = newsize;
  294.     memmove(Current->entry->item, newitem, newsize);
  295.     return True;
  296. }
  297.  
  298. /*
  299.  *  sort() uses compare() function indirectly through qcompare()
  300.  *  with host qsort() function to sort the SingleList
  301.  *
  302.  *  returns:        0   if SingleList is empty or not enough memory
  303.  *            for sorting table
  304.  *
  305.  *            sets lerror to error code
  306.  *
  307.  *
  308.  *                  1   if sort completed
  309.  *
  310.  *            first item in SingleList is "current" item
  311.  */
  312. Boolean SingleList::sort(void)
  313. {
  314.     Entry **entry_array;
  315.     Entry **save_array_base;
  316.  
  317.     lerror = (entries > 0) ? OK : EMPTY_LIST;
  318.  
  319.     if(entries < 2)
  320.     return (Boolean) entries;
  321.  
  322.     if(! (save_array_base =
  323.     (Entry **) new char[entries * sizeof(Entry *)]))  {
  324.         lerror = NO_MEM;
  325.         return False;
  326.     }
  327.     entry_array = save_array_base;
  328.  
  329.     Current = First;
  330.  
  331.     do  {
  332.  
  333.     *entry_array++ = Current->entry;
  334.     }
  335.     while(Current = Current->Next);
  336.  
  337.     Current = First;
  338.     entry_array = save_array_base;
  339.     this_list = this;
  340.     qsort(entry_array, entries, sizeof entry_array[0], qcompare);
  341.  
  342.     do  {
  343.  
  344.     Current->entry = *entry_array++;
  345.     }
  346.     while(Current = Current->Next);
  347.  
  348.     Current = First;
  349.     delete save_array_base;
  350.     return True;
  351. }
  352.