home *** CD-ROM | disk | FTP | other *** search
/ C++ Games Programming / CPPGAMES.ISO / thx / include / linklist.h < prev    next >
C/C++ Source or Header  |  1995-05-08  |  6KB  |  270 lines
  1. // ------------ linklist.h
  2. // a template for a linked list
  3.  
  4. #ifndef LINKLIST_H
  5. #define LINKLIST_H
  6.  
  7. // --- the linked list entry
  8. template <class T>
  9. class ListEntry  {
  10.   friend class LinkedList<T>;
  11.   T *thisentry;
  12.   ListEntry<T> *nextentry;
  13.   ListEntry<T> *preventry;
  14.   ListEntry(T *entry);
  15. };
  16.  
  17. template <class T>
  18. // ---- the linked list
  19. class LinkedList  {
  20.   // --- the listhead
  21.   ListEntry<T> *firstentry;
  22.   ListEntry<T> *lastentry;
  23.   ListEntry<T> *iterator;
  24.   short int entrycount;
  25.   T *CurrentEntry();
  26.   void RemoveEntry(ListEntry<T> *entry);
  27.   void InsertEntry(T *entry);
  28.   void InsertEntry(T *entry, short int pos);
  29.   void RemoveEntry(short int pos);
  30. public:
  31.   LinkedList();
  32.   virtual ~LinkedList()
  33.     { ClearList(); }
  34.   void AppendEntry(T *entry);
  35.   void InsertEntry(T *entry, T *curr);
  36.   void RemoveEntry(T *entry = 0);
  37.   T *FindEntry(short int pos);
  38.   short int FindEntry(T *entry);
  39.   T *FirstEntry();
  40.   T *LastEntry();
  41.   T *NextEntry();
  42.   T *PrevEntry();
  43.   T *NextEntry(T *entry);
  44.   T *PrevEntry(T *entry);
  45.   void ClearList();
  46.   short int EntryCount() const
  47.     { return entrycount; }
  48. };
  49.  
  50. template <class T>
  51. // ---- construct a linked list
  52. LinkedList<T>::LinkedList()
  53. {
  54.   iterator = 0;
  55.   firstentry = 0;
  56.   lastentry = 0;
  57.   entrycount = 0;
  58. }
  59.  
  60. template <class T>
  61. // ---- remove all entries from a linked list
  62. void LinkedList<T>::ClearList()
  63. {
  64.   ListEntry<T> *lentry = firstentry;
  65.   while (lentry != 0)  {
  66.     ListEntry<T> *nxt = lentry->nextentry;
  67.     delete lentry;
  68.     lentry = nxt;
  69.   }
  70.   iterator = 0;
  71.   firstentry = 0;
  72.   lastentry = 0;
  73.   entrycount = 0;
  74. }
  75.  
  76. // ---- construct a linked list entry
  77. template <class T>
  78. ListEntry<T>::ListEntry(T *entry)
  79. {
  80.   thisentry = entry;
  81.   nextentry = 0;
  82.   preventry = 0;
  83. }
  84.  
  85. template <class T>
  86. // ---- append an entry to the linked list
  87. void LinkedList<T>::AppendEntry(T *entry)
  88. {
  89.   ListEntry<T> *newentry = new ListEntry<T>(entry);
  90.   newentry->preventry = lastentry;
  91.   if (lastentry)
  92.     lastentry->nextentry = newentry;
  93.   if (firstentry == 0)
  94.     firstentry = newentry;
  95.   lastentry = newentry;
  96.   entrycount++;
  97. }
  98.  
  99. template <class T>
  100. // ---- return the current linked list entry
  101. T *LinkedList<T>::CurrentEntry()
  102. {
  103.   return iterator ? iterator->thisentry : 0;
  104. }
  105.  
  106. template <class T>
  107. // ---- return the first entry in the linked list
  108. T *LinkedList<T>::FirstEntry()
  109. {
  110.   iterator = firstentry;
  111.   return CurrentEntry();
  112. }
  113.  
  114. template <class T>
  115. // ---- return the last entry in the linked list
  116. T *LinkedList<T>::LastEntry()
  117. {
  118.   iterator = lastentry;
  119.   return CurrentEntry();
  120. }
  121.  
  122. template <class T>
  123. // ---- return the next entry following the specified one
  124. T *LinkedList<T>::NextEntry(T *entry)
  125. {
  126.   FindEntry(entry);
  127.   return NextEntry();
  128. }
  129.  
  130. template <class T>
  131. // ---- return the next entry in the linked list
  132. T *LinkedList<T>::NextEntry()
  133. {
  134.   if (iterator == 0)
  135.     iterator = firstentry;
  136.   else
  137.     iterator = iterator->nextentry;
  138.   return CurrentEntry();
  139. }
  140.  
  141. template <class T>
  142. // ---- return the previous entry ahead of the specified one
  143. T *LinkedList<T>::PrevEntry(T *entry)
  144. {
  145.   FindEntry(entry);
  146.   return PrevEntry();
  147. }
  148.  
  149. template <class T>
  150. // ---- return the previous entry in the linked list
  151. T *LinkedList<T>::PrevEntry()
  152. {
  153.   if (iterator == 0)
  154.     iterator = lastentry;
  155.   else
  156.     iterator = iterator->preventry;
  157.   return CurrentEntry();
  158. }
  159.  
  160. template <class T>
  161. // ---- remove an entry from the linked list by position
  162. void LinkedList<T>::RemoveEntry(short int pos)
  163. {
  164.   FindEntry(pos);
  165.   if (iterator != 0)
  166.     RemoveEntry(iterator);
  167. }
  168.  
  169. template <class T>
  170. // ---- remove an entry from the linked list by entry address
  171. void LinkedList<T>::RemoveEntry(ListEntry<T> *lentry)
  172. {
  173.   if (lentry == 0)
  174.     return;
  175.   if (lentry == iterator)
  176.     iterator = lentry->preventry;
  177.   // ---- repair any break made by this removal
  178.   if (lentry->nextentry)
  179.     lentry->nextentry->preventry = lentry->preventry;
  180.   if (lentry->preventry)
  181.     lentry->preventry->nextentry = lentry->nextentry;
  182.   // --- maintain listhead if this is last and/or first
  183.   if (lentry == lastentry)
  184.     lastentry = lentry->preventry;
  185.   if (lentry == firstentry)
  186.     firstentry = lentry->nextentry;
  187.   delete lentry;
  188.   --entrycount;
  189. }
  190.  
  191. template <class T>
  192. // ---- remove current or specified entry from linked list
  193. void LinkedList<T>::RemoveEntry(T *entry)
  194. {
  195.   if (entry != 0)
  196.     FindEntry(entry);
  197.   RemoveEntry(iterator);
  198. }
  199.  
  200. template <class T>
  201. // ---- insert an entry into the linked list ahead of another
  202. void LinkedList<T>::InsertEntry(T *entry, T *curr)
  203. {
  204.   FindEntry(curr);
  205.   InsertEntry(entry);
  206. }
  207.  
  208. template <class T>
  209. // ---- insert an entry into the linked list by position
  210. void LinkedList<T>::InsertEntry(T *entry, short int pos)
  211. {
  212.   FindEntry(pos);
  213.   InsertEntry(entry);
  214. }
  215.  
  216. template <class T>
  217. // ---- insert an entry into the linked list ahead of iterator
  218. void LinkedList<T>::InsertEntry(T *entry)
  219. {
  220.   if (iterator == 0)
  221.     AppendEntry(entry);
  222.   else  {
  223.     ListEntry<T> *newentry = new ListEntry<T>(entry);
  224.     newentry->nextentry = iterator;
  225.     if (iterator)  {
  226.       newentry->preventry = iterator->preventry;
  227.       iterator->preventry = newentry;
  228.     }
  229.     if (newentry->preventry)
  230.       newentry->preventry->nextentry = newentry;
  231.     if (iterator == firstentry)
  232.       firstentry = newentry;
  233.     iterator = newentry;
  234.     entrycount++;
  235.   }
  236. }
  237.  
  238. template <class T>
  239. // ---- return a specific linked list entry
  240. T *LinkedList<T>::FindEntry(short int pos)
  241. {
  242.   iterator = firstentry;
  243.   while (iterator && pos--)
  244.     iterator = iterator->nextentry;
  245.   return CurrentEntry();
  246. }
  247.  
  248. template <class T>
  249. // ---- return a specific linked list entry number
  250. short int LinkedList<T>::FindEntry(T *entry)
  251. {
  252.   short int pos = 0;
  253.   if (entry == 0)  {
  254.     pos = entrycount;
  255.     iterator = 0;
  256.   }
  257.   else  {
  258.     iterator = firstentry;
  259.     while (iterator)  {
  260.       if (entry == iterator->thisentry)
  261.         break;
  262.       iterator = iterator->nextentry;
  263.       pos++;
  264.     }
  265.   }
  266.   return pos;
  267. }
  268.  
  269. #endif
  270.