glcirclelist.h

00001 /*
00002 Copyright (c) 2000-2003 Lee Thomason (www.grinninglizard.com)
00003 
00004 Grinning Lizard Utilities. Note that software that uses the 
00005 utility package (including Lilith3D and Kyra) have more restrictive
00006 licences which applies to code outside of the utility package.
00007 
00008 This software is provided 'as-is', without any express or implied 
00009 warranty. In no event will the authors be held liable for any 
00010 damages arising from the use of this software.
00011 
00012 Permission is granted to anyone to use this software for any 
00013 purpose, including commercial applications, and to alter it and 
00014 redistribute it freely, subject to the following restrictions:
00015 
00016 1. The origin of this software must not be misrepresented; you must 
00017 not claim that you wrote the original software. If you use this 
00018 software in a product, an acknowledgment in the product documentation 
00019 would be appreciated but is not required.
00020 
00021 2. Altered source versions must be plainly marked as such, and 
00022 must not be misrepresented as being the original software.
00023 
00024 3. This notice may not be removed or altered from any source 
00025 distribution.
00026 */
00027 
00028 
00029 #ifndef KYRA_CIRCLELIST_INCLUDED
00030 #define KYRA_CIRCLELIST_INCLUDED
00031 
00032 #ifdef _MSC_VER
00033 // Disable the no-exception handling warning.
00034 #pragma warning( disable : 4530 )
00035 #pragma warning( disable : 4786 )
00036 #endif
00037 
00038 #include "../../grinliz/gldebug.h"
00039 
00040 // OPT improvements:
00041 // - add memory allocator
00042 // - remove the 'data' from circle node, so the overhead isn't in
00043 //       the sentinels.
00044 
00045 template <class T>
00046 struct GlCircleNode
00047 {
00048         T data;
00049 
00050         GlCircleNode<T>* next;
00051         GlCircleNode<T>* prev;
00052 };
00053 
00054 /*
00055         A circular, double linked list.
00056 */
00057 template <class T>
00058 class GlCircleList
00059 {
00060   public:
00061         GlCircleList()          { sentinel.next = &sentinel; sentinel.prev = &sentinel; }
00062         ~GlCircleList()         { Clear(); }
00063 
00064         bool    Empty() const   { return sentinel.next == &sentinel; }
00065         T&              Front() const   { return sentinel.next->data; }
00066         T&              Back()  const   { return sentinel.prev->data; }
00067         GlCircleNode<T>* FrontNode() const      { return sentinel.next; }
00068         GlCircleNode<T>* BackNode()  const      { return sentinel.prev; }
00069 
00070         void Clear()                    {       GlCircleNode<T>* temp;
00071                                                                 while( sentinel.next != &sentinel )
00072                                                                 {
00073                                                                         temp = sentinel.next;
00074                                                                         sentinel.next = sentinel.next->next;
00075                                                                         delete temp;
00076                                                                 }
00077                                                                 sentinel.prev = &sentinel;
00078                                                         }
00079         void PushFront( const T& insert ) {
00080                                                                 GlCircleNode<T>* node = new GlCircleNode<T>;
00081                                                                 node->data = insert;
00082 
00083                                                                 node->prev = &sentinel;
00084                                                                 node->next = sentinel.next;
00085                                                                 sentinel.next->prev = node;
00086                                                                 sentinel.next = node;
00087                                                         }
00088         void PushBack( const T& insert ) {
00089                                                                 GlCircleNode<T>* node = new GlCircleNode<T>;
00090                                                                 node->data = insert;
00091 
00092                                                                 node->prev = sentinel.prev;
00093                                                                 node->next = &sentinel;
00094                                                                 sentinel.prev->next = node;
00095                                                                 sentinel.prev = node;
00096                                                         }
00097         void PopFront()                 {
00098                                                                 GLASSERT( sentinel.next != &sentinel );
00099                                                                 GlCircleNode<T>* node = sentinel.next;
00100 //                                                              node->prev->next = node->next;
00101 //                                                              node->next->prev = node->prev;
00102 //                                                              delete node;
00103                                                                 Delete( node );
00104                                                         }
00105         void PopBack()                  {
00106                                                                 GLASSERT( sentinel.prev != &sentinel );
00107                                                                 GlCircleNode<T>* node = sentinel.prev;
00108 //                                                              node->prev->next = node->next;
00109 //                                                              node->next->prev = node->prev;
00110 //                                                              delete node;
00111                                                                 Delete( node );
00112                                                         }
00113 
00114         void Delete( GlCircleNode<T>* node )    {
00115                                                                                                 GLASSERT( node != &sentinel );
00116                                                                                                 node->prev->next = node->next;
00117                                                                                                 node->next->prev = node->prev;
00118                                                                                                 delete node;
00119                                                                                         }
00120         GlCircleNode<T>* Find( T value )                {
00121                                                                                                 GlCircleNode<T>* node = sentinel.next;
00122                                                                                                 while ( node != &sentinel )
00123                                                                                                 {
00124                                                                                                         if ( node->data == value )
00125                                                                                                                 return node;
00126                                                                                                         node = node->next;
00127                                                                                                 }
00128                                                                                                 return 0;
00129                                                                                         }
00130 
00131         // Scoping problems. Pretend this is private.
00132         GlCircleNode<T> sentinel;
00133 };
00134 
00135 
00136 template <class T>
00137 class GlCircleListIterator
00138 {
00139   public:
00140         GlCircleListIterator( GlCircleList<T>& _list ) : current( 0 ), list( &_list )   {}
00141 
00142         void Begin()            { current = list->sentinel.next; }
00143         void Next()                     { current = current->next; }
00144         void Prev()                     { current = current->prev; }
00145         bool Done()                     { return ( current == &(list->sentinel) ); }
00146 
00148         T& Current()                                    { return (current->data); }
00149 
00150         void InsertBefore( const T& addMe )
00151         {
00152                 GlCircleNode<T>* node = new GlCircleNode<T>;
00153                 node->data = addMe;
00154 
00155                 node->prev = current->prev;
00156                 node->next = current;
00157                 current->prev->next = node;
00158                 current->prev = node;
00159         }
00160 
00161         void InsertAfter( const T& addMe )
00162         {
00163                 GlCircleNode<T>* node = new GlCircleNode<T>;
00164                 node->data = addMe;
00165 
00166                 node->prev = current;
00167                 node->next = current->next;
00168                 current->next->prev = node;
00169                 current->next = node;
00170         }
00171 
00172         void Remove()
00173         {
00174                 GLASSERT( current != &(list->sentinel) );
00175 
00176                 GlCircleNode<T>* temp = current;
00177                 current = current->next;
00178 
00179                 temp->prev->next = temp->next;
00180                 temp->next->prev = temp->prev;
00181                 delete temp;
00182         }
00183 
00184   private:
00185         GlCircleNode<T>* current;       
00186         GlCircleList<T>* list;
00187 };
00188 
00189 
00190 #endif

Generated on Thu Jul 20 20:45:31 2006 for Kyra by  doxygen 1.4.7