Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / General Programming / help needed to complete open source buffered linked list class Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
bloodlocust

May 18, 2005, 03:41 PM

Dear community,

I humbly ask for your assistence in completing this opensource buffered linked list class by David Maziarka. Whats missing is the AddLast function, and I am not experienced enough to add it.

Perhaps someone with five minutes to spare, could look at AddFirst, and perhaps see how AddLast could be added.

I just love the way this linked list system works and it's a shame I haven't been able to get AddLast working.

Many thanks for your kind assistance.

  1.  
  2. ///////////////////////////////////////////////////////////////////////////////
  3. // BList.h
  4. //
  5. //      AUTHOR: David Maziarka 08-15-99
  6. // DESCRIPTION: A templated buffered list engine.
  7. //     WARNING: Does not contain copy constructors or overloaded assignment
  8. //              operators, yet.
  9. //       NOTES: In this class the word 'item' is synonymous with element.
  10. ///////////////////////////////////////////////////////////////////////////////
  11.  
  12.  
  13. /*
  14.  
  15. //example code:
  16.  
  17. //your type
  18. class Bullet
  19. {
  20.         public:
  21.     int         x;              // x coordinate
  22.     int         y;              // y coordinate
  23.    
  24. };
  25.  
  26. BList   <Bullet>        bullets(100);           // allocate space for 100 bullets.
  27. Bullet  *                       mybullet;                       // global pointer to any bullet object.
  28.  
  29. //add an item at the start of the list with parameters
  30. if ( mybullet = bullets.AddFirst())
  31. {
  32.         mybullet->x = 10;
  33.         mybullet->y = 20;
  34. };
  35.  
  36. //add an item normally at the end of the list
  37. mybullet = bullets.AddLast()
  38. mybullet->x = 10;
  39.  
  40. //remove an item (internal pointer is set using nextitem, first item etc)
  41. bullets.RemoveItem();
  42.  
  43. //loop through items
  44. bullets.ResetList();
  45. while( mybullet = bullets.NextItem() )
  46. {
  47.  
  48.         if ( mybullet->x > 640 )
  49.         {
  50.                 bullets.RemoveItem();
  51.         }else
  52.         {
  53.                 p_bullet->x += 2;
  54.         }
  55. }
  56.  
  57.  
  58.  
  59. */
  60.  
  61.  
  62.  
  63.  
  64. #ifndef MAZ_BLIST_H
  65. #define MAZ_BLIST_H
  66.  
  67. ///////////////////////////////////////////////////////////////////////////////
  68. // Stack class
  69. //
  70. //      AUTHOR: David Maziarka 08-15-99
  71. // DESCRIPTION: This is a simple class template for a stack.
  72. //     WARNING: Does not contain a copy constructor or overloaded assignment
  73. //              operators.
  74. ///////////////////////////////////////////////////////////////////////////////
  75. #ifndef MAZ_STACK_H
  76. #define MAZ_STACK_H
  77.  
  78. #include <windows.h>
  79.  
  80. template <class T>
  81. class Stack
  82. {
  83.         private:
  84.                 T *             st;
  85.                 int             top;
  86.                 int             smax;
  87.  
  88.         public:
  89.                 Stack(const int i) : smax(i), top(-1)
  90.                 {
  91.                         st = new T[smax];
  92.                 }
  93.                 ~Stack(void)
  94.                 {
  95.                         delete[] st;
  96.                 }
  97.  
  98.                 bool push(T var)
  99.                 {
  100.                         if(top+1 >= smax) return false;
  101.                         st[++top] = var;
  102.                         return true;
  103.                 }
  104.  
  105.                 bool pop(T & var)
  106.                 {
  107.                         if(top < 0) return false;
  108.                         var = st[top--];
  109.                         return true;
  110.                 }
  111. };
  112.  
  113. #endif
  114.  
  115. ///////////////////////////////////////////////////////////////////////////////
  116.  
  117. enum { BLCURRENT, BLFIRST, BLLAST };
  118.  
  119. template <class T>
  120. class BList
  121. {
  122.         public:
  123.                 struct BListData {
  124.                         T                               UserType;               // user defined type.
  125.  
  126.                         private:
  127.                         friend class    BList<T>;
  128.                         int                             ident;                  // used for the stack index.
  129.                         BListData *             p_next;                 // pointer to the next item in the list.
  130.                         BListData *             p_prev;                 // pointer to the previous item in the list.
  131.                 };
  132.  
  133.         private:
  134.                 BListData *                     p_blData;               // pointer to the the array.
  135.                 BListData *                     p_blFirst;              // pointer to the first item in the list.
  136.                 BListData *                     p_blLast;               // pointer to the last item in the list.
  137.                 BListData *                     p_blCurrent;    // points to the current item. ( NULL = list empty ).
  138.                 BListData *                     p_blNext;               // points to the next item. ( NULL = end of list ).
  139.                 BListData *                     p_blTmp;                // temp work pointer.
  140.                 int                                     blTotal;                // number of items in the list right now.
  141.                 int                                     blNew;                  // temp work location.
  142.                 int                                     blMax;                  // maxium number of items allowed in this list ( slots are 0 thru pmax - 1).
  143.                 Stack<int> *            p_blStack;              // this stack holds which slots are open.
  144.        
  145.         public:
  146.                 BList(const int BListMax);
  147.                 ~BList();
  148.  
  149.                 void ResetList(void);                                           // Reset to begining for NextItem.
  150.                 void ClearList(void);                                           // Empty the list.
  151.                 int  GetItemTotal(void) { return blTotal; }     // Return number of items currently in the list.
  152.  
  153.                 T *             CurrentItem(void);                      // Returns pointer of the current item.
  154.                 bool    FirstItem(void);                        // Set the current item to the first one in the list.
  155.                 bool    LastItem(void);                         // Set the current item to the last one in the list.
  156.                 T *             AddFirst(void);                         // Push an item on the begining.
  157.                 T *             AddLast(void);                          // Add an item to the end.
  158.                 bool    AddBefore(void);                        // Add an item before the current item.
  159.                 bool    AddAfter(void);                         // Add an item after the current item ( NextItem will return this one ).
  160.                 T *             NextItem(void);                         // Return the current item, then set the current item to the next one
  161.                                                                                         // in the list.
  162.                 bool    RemoveItem(const int item = BLCURRENT); // Remove the current item from the list, then set the current item
  163.                                                                                                                 // to the previous one.
  164. //              bool    RemoveItem(BList::BListData * p_pd);    // Remove the specified item.
  165. };
  166.  
  167. ///////////////////////////////////////////////////////////////////////////////
  168. // BList
  169. ///////////////////////////////////////////////////////////////////////////////
  170. template <class T>
  171. BList<T>::BList(const int pm) : blMax(pm), blNew(-1), blTotal(0),
  172.                                                                 p_blData(NULL), p_blFirst(NULL), p_blLast(NULL),
  173.                                                                 p_blCurrent(NULL), p_blNext(NULL), p_blTmp(NULL),
  174.                                                                 p_blStack(NULL)
  175. {
  176.         // init the stack
  177.         p_blStack = new Stack<int>(blMax);
  178.         for(int i=blMax-1; i>-1; i--) {
  179.                 if(p_blStack->push(i) == false) exit(1);
  180.         }
  181.  
  182.         // init the list
  183.         p_blData = new BListData[blMax];
  184. }
  185.  
  186. ///////////////////////////////////////////////////////////////////////////////
  187. // ~BList
  188. ///////////////////////////////////////////////////////////////////////////////
  189. template <class T>
  190. BList<T>::~BList()
  191. {
  192.         delete[] p_blData;
  193.         delete p_blStack;
  194. }
  195.  
  196. ///////////////////////////////////////////////////////////////////////////////
  197. // ResetList
  198. // Reset current particle to NULL so that NextItem will return the first.
  199. ///////////////////////////////////////////////////////////////////////////////
  200. template <class T>
  201. void BList<T>::ResetList(void)
  202. {
  203.         p_blCurrent = NULL;
  204. }
  205.  
  206. ///////////////////////////////////////////////////////////////////////////////
  207. // ClearList
  208. ///////////////////////////////////////////////////////////////////////////////
  209. template <class T>
  210. void BList<T>::ClearList(void)
  211. {
  212.         true;
  213. }
  214.  
  215. ///////////////////////////////////////////////////////////////////////////////
  216. // CurrentItem
  217. // Will return a pointer to the current item.  If at the beginning of the
  218. // list, you must first set the current item with NextItem, FirstItem
  219. // or LastItem.
  220. ///////////////////////////////////////////////////////////////////////////////
  221. template <class T>
  222. T * BList<T>::CurrentItem(void)
  223. {
  224.         return &p_blCurrent->UserType;
  225. }
  226.  
  227. ///////////////////////////////////////////////////////////////////////////////
  228. // FirstItem
  229. ///////////////////////////////////////////////////////////////////////////////
  230. template <class T>
  231. bool BList<T>::FirstItem(void)
  232. {
  233.         return true;
  234. }
  235.  
  236. ///////////////////////////////////////////////////////////////////////////////
  237. // LastItem
  238. ///////////////////////////////////////////////////////////////////////////////
  239. template <class T>
  240. bool BList<T>::LastItem(void)
  241. {
  242.         return true;
  243. }
  244.  
  245. ///////////////////////////////////////////////////////////////////////////////
  246. // AddFirst
  247. // Add an item to the begining of the list.
  248. ///////////////////////////////////////////////////////////////////////////////
  249. template <class T>
  250. T * BList<T>::AddFirst(void)
  251. {
  252.         if(!p_blStack->pop(blNew)) return NULL;
  253.  
  254.         p_blTmp = &p_blData[blNew];                     // tmp pointer for new particle.
  255.         p_blTmp->ident = blNew;
  256.  
  257.         if(p_blFirst == NULL) {        
  258.                 // we are adding to an empty list.
  259.                 p_blNext = p_blTmp;                             // only change p_pnext if list was empty.
  260.                 p_blLast = p_blTmp;
  261.                 p_blTmp->p_next = NULL;
  262.         } else {
  263.                 // already had a first entry.
  264.                 p_blFirst->p_prev = p_blTmp;            // change the old first's prev to the NEW first.
  265.                 p_blTmp->p_next = p_blFirst;            // change the NEW first's next to the old first.
  266.         }
  267.         p_blTmp->p_prev = NULL;
  268.  
  269.         p_blFirst = p_blTmp;
  270.         blTotal++;
  271.  
  272.         return &p_blFirst->UserType;
  273. }
  274.  
  275. ///////////////////////////////////////////////////////////////////////////////
  276. // AddLast - NEEDS CODING
  277. ///////////////////////////////////////////////////////////////////////////////
  278. template <class T>
  279. T * BList<T>::AddLast(void)
  280. {
  281.         return true;
  282. }
  283.  
  284. ///////////////////////////////////////////////////////////////////////////////
  285. // AddBefore - NEEDS CODING
  286. ///////////////////////////////////////////////////////////////////////////////
  287. template <class T>
  288. bool BList<T>::AddBefore(void)
  289. {
  290.         return true;
  291. }
  292.  
  293. ///////////////////////////////////////////////////////////////////////////////
  294. // AddAfter - NEEDS CODING
  295. ///////////////////////////////////////////////////////////////////////////////
  296. template <class T>
  297. bool BList<T>::AddAfter(void)
  298. {
  299.         return true;
  300. }
  301.  
  302. ///////////////////////////////////////////////////////////////////////////////
  303. // NextItem
  304. ///////////////////////////////////////////////////////////////////////////////
  305. template <class T>
  306. T * BList<T>::NextItem(void)
  307. {
  308.         if(p_blCurrent == NULL) {
  309.                 p_blCurrent = p_blFirst;
  310.         } else {
  311.                 p_blCurrent = p_blCurrent->p_next;
  312.         }
  313.         return &p_blCurrent->UserType;
  314. }
  315.  
  316. ///////////////////////////////////////////////////////////////////////////////
  317. // RemoveItem
  318. // Removes the current item from the list.  After executing RemoveItem, the
  319. // current item will be set to the item BEFORE the the one just removed.
  320. // This is so we may continue with normal NextItem processing.
  321. ///////////////////////////////////////////////////////////////////////////////
  322. template <class T>
  323. bool BList<T>::RemoveItem(const int item)
  324. {
  325.         switch(item) {
  326.                 case BLFIRST:
  327.                         p_blTmp = p_blFirst;
  328.                         break;
  329.                 case BLLAST:
  330.                         p_blTmp = p_blLast;
  331.                         break;
  332.                 case BLCURRENT:
  333.                 default:
  334.                         p_blTmp = p_blCurrent;
  335.                         break;
  336.         }
  337.  
  338.         if(p_blTmp == NULL) return false;       // Empty list or the beginning.  If
  339.                                                                                 // beginning, this needs a NextItem.
  340.  
  341.         if(p_blStack->push(p_blTmp->ident) == false) exit(1);
  342.        
  343.         if(p_blTmp == p_blLast && p_blTmp == p_blFirst) {
  344.                 p_blLast = NULL;
  345.                 p_blFirst = NULL;
  346.                 p_blCurrent = NULL;
  347.         } else if(p_blTmp == p_blLast) {
  348.                 p_blLast = p_blTmp->p_prev;
  349.                 p_blTmp->p_prev->p_next = NULL;
  350.                 p_blCurrent = p_blTmp->p_prev;
  351.         } else if(p_blTmp == p_blFirst) {
  352.                 p_blFirst = p_blTmp->p_next;
  353.                 p_blTmp->p_next->p_prev = NULL;
  354.                 p_blCurrent = NULL;
  355.         } else {
  356.                 p_blTmp->p_next->p_prev = p_blTmp->p_prev;
  357.                 p_blTmp->p_prev->p_next = p_blTmp->p_next;
  358.                 p_blCurrent = p_blTmp->p_prev;
  359.         }
  360.        
  361.         blTotal--;
  362.  
  363.         return true;
  364. }
  365. #endif
  366.  

 
Betelgeuse

May 18, 2005, 07:10 PM

For a regular doubly linked list, addlast is as such...

old_last_item -> next = new_item
new_item -> previous = old_last_item
new_item -> next = 0

optionally, if you're keeping track of the list end, then...
list_end = new_item

SO something like

  1.  
  2. else {
  3.                 // already had a first entry.
  4.                 p_blLast->p_next = p_blTmp;            
  5.                 p_blTmp->p_prev = p_blLast;
  6.         }
  7.         p_blTmp->p_next = 0;
  8.  
  9.         p_blLast = p_blTmp;
  10.  


Just so you know, NULL is deprecated in C++. You should use 0.

 
bloodlocust

May 19, 2005, 07:04 AM

Hiya,

Thanks for taking the time out to reply. I have changed over to 0 as you suggest - thanks for that!

Your code snippet doesn't seem to work for me though - maybe I'm missing something? Here is the full modified version of AddLast - with your suggested change. I would appreciate it if you could tell me where I am going wrong.

  1.  
  2. template <class T>
  3. T * BList<T>::AddLast(void)
  4. {
  5.  
  6.         if(!p_blStack->pop(blNew)) return 0;
  7.  
  8.         p_blTmp = &p_blData[blNew];                     // tmp pointer for new particle.
  9.         p_blTmp->ident = blNew;
  10.  
  11.         if (p_blFirst == 0)
  12.         {              
  13.                 // we are adding to an empty list.
  14.                 p_blNext = p_blTmp;                             // only change p_pnext if list was empty.
  15.                 p_blLast = p_blTmp;
  16.                 p_blTmp->p_next = 0;
  17.         }
  18.         else
  19.         {
  20.                 // already had a first entry.
  21.                 p_blLast->p_next = p_blTmp;            
  22.                 p_blTmp->p_prev = p_blLast;
  23.        
  24.         }
  25.         p_blTmp->p_next = 0;
  26.  
  27.         p_blLast = p_blTmp;
  28.         blTotal++;
  29.  
  30.         return &p_blFirst->UserType;
  31. }
  32.  

 
This thread contains 3 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.