00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef __CS_UTIL_LIST_H__
00021 #define __CS_UTIL_LIST_H__
00022
00023
00024
00025
00026
00027
00028 template <class T> class csList
00029 {
00030 protected:
00031
00032
00033
00034
00035 struct csListElement
00036 {
00038 csListElement(const T& d, csListElement* newnext,
00039 csListElement* newprev)
00040 : next(newnext), prev(newprev), data(d)
00041 {}
00042
00044 csListElement* next;
00045
00047 csListElement* prev;
00048
00050 T data;
00051 };
00052
00054 void Delete (csListElement *el);
00055
00056 public:
00058 csList()
00059 : head(0), tail(0)
00060 {}
00061
00063 csList(const csList &other);
00064
00066 ~csList()
00067 { DeleteAll (); }
00068
00070 class Iterator
00071 {
00072 public:
00073 Iterator()
00074 : ptr(0)
00075 { }
00076 Iterator(const Iterator& other)
00077 { ptr = other.ptr; }
00078 Iterator(const csList<T> &list, bool reverse = false)
00079 {
00080 reversed=reverse;
00081 if(reverse) ptr = list.tail;
00082 else ptr = list.head;
00083 }
00084 const Iterator& operator= (const Iterator& other)
00085 { ptr = other.ptr; return *this; }
00086
00087 bool HasCurrent() const
00088 { return ptr != 0; }
00089 bool HasNext() const
00090 { return ptr && ptr->next; }
00091 bool HasPrevious() const
00092 { return ptr && ptr->prev; }
00093 bool IsFirst() const
00094 { return ptr && ptr->prev == 0; }
00095 bool IsLast() const
00096 { return ptr && ptr->next == 0; }
00097 bool IsReverse() const
00098 { return reversed; }
00099
00100 operator T*() const
00101 { return &ptr->data; }
00102 T &operator *() const
00103 { return ptr->data; }
00104 T *operator->() const
00105 { return &ptr->data; }
00106
00108 inline void Clear ()
00109 {
00110 ptr = NULL;
00111 }
00112
00113 inline Iterator operator++(int)
00114 {
00115 ptr = ptr->next;
00116 return Iterator(ptr);
00117 }
00118 inline Iterator operator--(int)
00119 {
00120 ptr = ptr->prev;
00121 return Iterator(ptr);
00122 }
00123 protected:
00124 friend class csList;
00125 Iterator (csListElement* element)
00126 : ptr(element)
00127 { }
00128
00129 private:
00130 csListElement* ptr;
00131 bool reversed;
00132 };
00133
00135 csList &operator=(const csList& other);
00136
00138 Iterator PushFront (const T & item);
00139
00141 Iterator PushBack (const T & item);
00142
00144 void Delete (Iterator &it);
00145
00147 void DeleteAll();
00148
00150 const T& Front () const
00151 { return head->data; }
00153 const T& Last () const
00154 { return tail->data; }
00155
00157 bool PopFront ()
00158 {
00159 if (!head)
00160 return false;
00161
00162 Delete (head);
00163 return true;
00164 }
00165
00167 bool PopBack ()
00168 {
00169 if (!tail)
00170 return false;
00171
00172 Delete (tail);
00173 return true;
00174 }
00175
00176 private:
00177 friend class Iterator;
00178 csListElement *head, *tail;
00179 };
00180
00182 template <class T> csList<T>::csList(const csList<T> &other)
00183 : head(0), tail(0)
00184 {
00185 csListElement* e = other.head;
00186 while( e != 0)
00187 {
00188 PushBack (e->data);
00189 e = e->next;
00190 }
00191 }
00192
00194 template <class T> csList<T>& csList<T>::operator =(const csList<T> &other)
00195 {
00196 DeleteAll ();
00197
00198 csListElement* e = other.head;
00199 while( e != 0)
00200 {
00201 PushBack (e->data);
00202 e = e->next;
00203 }
00204
00205 return *this;
00206 }
00207
00209 template <class T> void csList<T>::DeleteAll ()
00210 {
00211 csListElement *cur = head, *next = 0;
00212
00213 while(cur != 0)
00214 {
00215 next = cur->next;
00216 delete cur;
00217 cur = next;
00218 }
00219 head = tail = 0;
00220 }
00221
00223 template <class T> typename csList<T>::Iterator csList<T>::PushBack (const T& item)
00224 {
00225 csListElement* el = new csListElement (item, NULL, tail);
00226 if (tail)
00227 tail->next = el;
00228 else
00229 head = el;
00230 tail = el;
00231
00232 return Iterator(el);
00233 }
00234
00236 template <class T> typename csList<T>::Iterator csList<T>::PushFront (const T& item)
00237 {
00238 csListElement* el = new csListElement (item, head, NULL);
00239 if (head)
00240 head->prev = el;
00241 else
00242 tail = el;
00243 head = el;
00244
00245 return Iterator (el);
00246 }
00247
00248
00249 template <class T> void csList<T>::Delete (Iterator &it)
00250 {
00251 csListElement* el = it.ptr;
00252
00253 if (!el)
00254 return;
00255
00256
00257 if (it.IsReverse())
00258 it--;
00259 else
00260 it++;
00261
00262 Delete(el);
00263 }
00264
00265 template <class T> void csList<T>::Delete (csListElement *el)
00266 {
00267 CS_ASSERT(el);
00268
00269
00270 if (el->prev)
00271 el->prev->next = el->next;
00272 else
00273 head = el->next;
00274
00275 if (el->next)
00276 el->next->prev = el->prev;
00277 else
00278 tail = el->prev;
00279
00280 delete el;
00281 }
00282
00283 #endif //__CS_UTIL_LIST_H__