home *** CD-ROM | disk | FTP | other *** search
/ Programming a Multiplayer FPS in DirectX / Programming a Multiplayer FPS in DirectX (Companion CD).iso / Source / Chapter 13 / Engine / LinkedList.h < prev    next >
Encoding:
C/C++ Source or Header  |  2004-10-01  |  9.3 KB  |  354 lines
  1. //-----------------------------------------------------------------------------
  2. // Implementation of a linked list collection.
  3. //
  4. // Programming a Multiplayer First Person Shooter in DirectX
  5. // Copyright (c) 2004 Vaughan Young
  6. //-----------------------------------------------------------------------------
  7. #ifndef LINKED_LIST_H
  8. #define LINKED_LIST_H
  9.  
  10. //-----------------------------------------------------------------------------
  11. // Linked List Class
  12. //-----------------------------------------------------------------------------
  13. template< class Type > class LinkedList
  14. {
  15. public:
  16.     //-------------------------------------------------------------------------
  17.     // Element Structure
  18.     //-------------------------------------------------------------------------
  19.     struct Element
  20.     {
  21.         Type *data; // Pointer to the data held in the element.
  22.         Element *next; // Pointer to the next element in the list.
  23.         Element *prev; // Pointer to the previous element in the list.
  24.  
  25.         //---------------------------------------------------------------------
  26.         // The element structure constructor.
  27.         //---------------------------------------------------------------------
  28.         Element( Type *element )
  29.         {
  30.             data = element;
  31.             next = prev = NULL;
  32.         }
  33.  
  34.         //---------------------------------------------------------------------
  35.         // The element structure destructor.
  36.         //---------------------------------------------------------------------
  37.         ~Element()
  38.         {
  39.             SAFE_DELETE( data );
  40.  
  41.             if( next )
  42.                 next->prev = prev;
  43.             if( prev )
  44.                 prev->next = next;
  45.         }
  46.     };
  47.  
  48.     //-------------------------------------------------------------------------
  49.     // The linked list class constructor.
  50.     //-------------------------------------------------------------------------
  51.     LinkedList()
  52.     {
  53.         m_first = m_last = m_iterate = m_temp = NULL;
  54.         m_totalElements = 0;
  55.     }
  56.  
  57.     //-------------------------------------------------------------------------
  58.     // The linked list class destructor.
  59.     //-------------------------------------------------------------------------
  60.     ~LinkedList()
  61.     {
  62.         Empty();
  63.     }
  64.  
  65.     //-------------------------------------------------------------------------
  66.     // Adds the given element to the end of the linked list.
  67.     //-------------------------------------------------------------------------
  68.     Type *Add( Type *element )
  69.     {
  70.         if( element == NULL )
  71.             return NULL;
  72.  
  73.         if( m_first == NULL )
  74.         {
  75.             m_first = new Element( element );
  76.             m_last = m_first;
  77.         }
  78.         else
  79.         {
  80.             m_last->next = new Element( element );
  81.             m_last->next->prev = m_last;
  82.             m_last = m_last->next;
  83.         }
  84.  
  85.         m_totalElements++;
  86.  
  87.         return m_last->data;
  88.     }
  89.  
  90.     //-------------------------------------------------------------------------
  91.     // Inserts the given element into the linked list just before nextElement.
  92.     //-------------------------------------------------------------------------
  93.     Type *InsertBefore( Type *element, Element *nextElement )
  94.     {
  95.         m_temp = nextElement->prev;
  96.  
  97.         m_totalElements++;
  98.  
  99.         if( m_temp == NULL )
  100.         {
  101.             m_first = new Element( element );
  102.             m_first->next = nextElement;
  103.             nextElement->prev = m_first;
  104.  
  105.             return m_first->data;
  106.         }
  107.         else
  108.         {
  109.             m_temp->next = new Element( element );
  110.             m_temp->next->prev = m_temp;
  111.             m_temp->next->next = nextElement;
  112.             nextElement->prev = m_temp->next;
  113.  
  114.             return m_temp->next->data;
  115.         }
  116.     }
  117.  
  118.     //-------------------------------------------------------------------------
  119.     // Removes the given element from the linked list and destroys its data.
  120.     //-------------------------------------------------------------------------
  121.     void Remove( Type **element )
  122.     {
  123.         m_temp = m_first;
  124.         while( m_temp != NULL )
  125.         {
  126.             if( m_temp->data == *element )
  127.             {
  128.                 if( m_temp == m_first )
  129.                 {
  130.                     m_first = m_first->next;
  131.                     if( m_first )
  132.                         m_first->prev = NULL;
  133.                 }
  134.                 if( m_temp == m_last )
  135.                 {
  136.                     m_last = m_last->prev;
  137.                     if( m_last )
  138.                         m_last->next = NULL;
  139.                 }
  140.  
  141.                 SAFE_DELETE( m_temp );
  142.  
  143.                 *element = NULL;
  144.  
  145.                 m_totalElements--;
  146.  
  147.                 return;
  148.             }
  149.  
  150.             m_temp = m_temp->next;
  151.         }
  152.     }
  153.  
  154.     //-------------------------------------------------------------------------
  155.     // Destroys all the elements in the linked list as well as their data.
  156.     //-------------------------------------------------------------------------
  157.     void Empty()
  158.     {
  159.         while( m_last != NULL )
  160.         {
  161.             m_temp = m_last;
  162.             m_last = m_last->prev;
  163.             SAFE_DELETE( m_temp );
  164.         }
  165.         m_first = m_last = m_iterate = m_temp = NULL;
  166.         m_totalElements = 0;
  167.     }
  168.  
  169.     //-------------------------------------------------------------------------
  170.     // Removes all the elements and clears their data pointers.
  171.     // Warning: This function does not destroy the data held be each element.
  172.     //-------------------------------------------------------------------------
  173.     void ClearPointers()
  174.     {
  175.         while( m_last != NULL )
  176.         {
  177.             m_temp = m_last;
  178.             m_temp->data = NULL;
  179.             m_last = m_last->prev;
  180.             SAFE_DELETE( m_temp );
  181.         }
  182.         m_first = m_last = m_iterate = m_temp = NULL;
  183.         m_totalElements = 0;
  184.     }
  185.  
  186.     //-------------------------------------------------------------------------
  187.     // Removes the given element and clears its data pointer.
  188.     // Warning: This function does not destroy the data held by the element.
  189.     //-------------------------------------------------------------------------
  190.     void ClearPointer( Type **element )
  191.     {
  192.         m_temp = m_first;
  193.         while( m_temp != NULL )
  194.         {
  195.             if( m_temp->data == *element )
  196.             {
  197.                 if( m_temp == m_first )
  198.                 {
  199.                     m_first = m_first->next;
  200.                     if( m_first )
  201.                         m_first->prev = NULL;
  202.                 }
  203.                 if( m_temp == m_last )
  204.                 {
  205.                     m_last = m_last->prev;
  206.                     if( m_last )
  207.                         m_last->next = NULL;
  208.                 }
  209.  
  210.                 m_temp->data = NULL;
  211.  
  212.                 SAFE_DELETE( m_temp );
  213.  
  214.                 *element = NULL;
  215.  
  216.                 m_totalElements--;
  217.  
  218.                 return;
  219.             }
  220.  
  221.             m_temp = m_temp->next;
  222.         }
  223.     }
  224.  
  225.     //-------------------------------------------------------------------------
  226.     // Iterates through the elements in the linked list.
  227.     //-------------------------------------------------------------------------
  228.     Type *Iterate( bool restart = false )
  229.     {
  230.         if( restart )
  231.             m_iterate = NULL;
  232.         else
  233.         {
  234.             if( m_iterate == NULL )
  235.                 m_iterate = m_first;
  236.             else
  237.                 m_iterate = m_iterate->next;
  238.         }
  239.  
  240.         if( m_iterate == NULL )
  241.             return NULL;
  242.         else
  243.             return m_iterate->data;
  244.     }
  245.  
  246.     //-------------------------------------------------------------------------
  247.     // Returns the currently iterated element in the linked list.
  248.     //-------------------------------------------------------------------------
  249.     Type *GetCurrent()
  250.     {
  251.         if( m_iterate )
  252.             return m_iterate->data;
  253.         else
  254.             return NULL;
  255.     }
  256.  
  257.     //-------------------------------------------------------------------------
  258.     // Returns the first element in the linked list.
  259.     //-------------------------------------------------------------------------
  260.     Type *GetFirst()
  261.     {
  262.         if( m_first )
  263.             return m_first->data;
  264.         else
  265.             return NULL;
  266.     }
  267.  
  268.     //-------------------------------------------------------------------------
  269.     // Returns the last element in the linked list.
  270.     //-------------------------------------------------------------------------
  271.     Type *GetLast()
  272.     {
  273.         if( m_last )
  274.             return m_last->data;
  275.         else
  276.             return NULL;
  277.     }
  278.  
  279.     //-------------------------------------------------------------------------
  280.     // Returns the next element in the linked list from the given element.
  281.     //-------------------------------------------------------------------------
  282.     Type *GetNext( Type *element )
  283.     {
  284.         m_temp = m_first;
  285.         while( m_temp != NULL )
  286.         {
  287.             if( m_temp->data == element )
  288.             {
  289.                 if( m_temp->next == NULL )
  290.                     return NULL;
  291.                 else
  292.                     return m_temp->next->data;
  293.             }
  294.  
  295.             m_temp = m_temp->next;
  296.         }
  297.  
  298.         return NULL;
  299.     }
  300.  
  301.     //-------------------------------------------------------------------------
  302.     // Returns a random element from the linked list.
  303.     //-------------------------------------------------------------------------
  304.     Type *GetRandom()
  305.     {
  306.         if( m_totalElements == 0 )
  307.             return NULL;
  308.         else if( m_totalElements == 1 )
  309.             return m_first->data;
  310.  
  311.         unsigned long element = rand() * m_totalElements / RAND_MAX;
  312.  
  313.         m_temp = m_first;
  314.         for( unsigned long e = 0; e < element; e++ )
  315.             m_temp = m_temp->next;
  316.  
  317.         return m_temp->data;
  318.     }
  319.  
  320.     //-------------------------------------------------------------------------
  321.     // Returns the complete element (including its next and previous pointers).
  322.     //-------------------------------------------------------------------------
  323.     Element *GetCompleteElement( Type *element )
  324.     {
  325.         m_temp = m_first;
  326.         while( m_temp != NULL )
  327.         {
  328.             if( m_temp->data == element )
  329.                     return m_temp;
  330.  
  331.             m_temp = m_temp->next;
  332.         }
  333.  
  334.         return NULL;
  335.     }
  336.  
  337.     //-------------------------------------------------------------------------
  338.     // Returns the total number of elements in the linked list.
  339.     //-------------------------------------------------------------------------
  340.     unsigned long GetTotalElements()
  341.     {
  342.         return m_totalElements;
  343.     }
  344.  
  345. private:
  346.     Element *m_first; // First element in the linked list.
  347.     Element *m_last; // Last element in the linked list.
  348.     Element *m_iterate; // Used for iterating the linked list.
  349.     Element *m_temp; // Used for temporary storage in various operations.
  350.  
  351.     unsigned long m_totalElements; // Total number of elements in the linked list.
  352. };
  353.  
  354. #endif