- Main Page
- Classes
- Files
- Directories
- Related Pages

# 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