00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 #ifndef KYRA_CIRCLELIST_INCLUDED
00030 #define KYRA_CIRCLELIST_INCLUDED
00031
00032 #ifdef _MSC_VER
00033
00034 #pragma warning( disable : 4530 )
00035 #pragma warning( disable : 4786 )
00036 #endif
00037
00038 #include "../../grinliz/gldebug.h"
00039
00040
00041
00042
00043
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
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
00101
00102
00103 Delete( node );
00104 }
00105 void PopBack() {
00106 GLASSERT( sentinel.prev != &sentinel );
00107 GlCircleNode<T>* node = sentinel.prev;
00108
00109
00110
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
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