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
00028 template <class T>
00029 class csList
00030 {
00031 protected:
00032
00033
00034
00035
00036 struct csListElement
00037 {
00039 csListElement(const T& d, csListElement* newnext,
00040 csListElement* newprev)
00041 : next(newnext), prev(newprev), data(d)
00042 {}
00043
00045 csListElement* next;
00046
00048 csListElement* prev;
00049
00051 T data;
00052 };
00053
00055 void Delete (csListElement *el);
00056
00057 public:
00059 csList()
00060 : head(0), tail(0)
00061 {}
00062
00064 csList(const csList &other);
00065
00067 ~csList()
00068 { DeleteAll (); }
00069
00071 class Iterator
00072 {
00073 public:
00074 Iterator() : 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 = 0;
00111 }
00112
00113 inline T* Next ()
00114 {
00115 ptr = ptr->next;
00116 return *this;
00117 }
00118
00119 inline Iterator& operator++()
00120 {
00121 ptr = ptr->next;
00122 return *this;
00123 }
00124 inline Iterator& operator--()
00125 {
00126 ptr = ptr->prev;
00127 return *this;
00128 }
00129 protected:
00130 friend class csList;
00131 Iterator (csListElement* element)
00132 : ptr(element)
00133 { }
00134
00135 private:
00136 csListElement* ptr;
00137 bool reversed;
00138 };
00139
00141 csList &operator=(const csList& other);
00142
00144 Iterator PushFront (const T & item);
00145
00147 Iterator PushBack (const T & item);
00148
00150 void Delete (Iterator &it);
00151
00153 void DeleteAll();
00154
00156 const T& Front () const
00157 { return head->data; }
00159 const T& Last () const
00160 { return tail->data; }
00161
00163 bool PopFront ()
00164 {
00165 if (!head)
00166 return false;
00167
00168 Delete (head);
00169 return true;
00170 }
00171
00173 bool PopBack ()
00174 {
00175 if (!tail)
00176 return false;
00177
00178 Delete (tail);
00179 return true;
00180 }
00181
00182 private:
00183 friend class Iterator;
00184 csListElement *head, *tail;
00185 };
00186
00188 template <class T> csList<T>::csList(const csList<T> &other)
00189 : head(0), tail(0)
00190 {
00191 csListElement* e = other.head;
00192 while( e != 0)
00193 {
00194 PushBack (e->data);
00195 e = e->next;
00196 }
00197 }
00198
00200 template <class T> csList<T>& csList<T>::operator =(const csList<T> &other)
00201 {
00202 DeleteAll ();
00203
00204 csListElement* e = other.head;
00205 while( e != 0)
00206 {
00207 PushBack (e->data);
00208 e = e->next;
00209 }
00210
00211 return *this;
00212 }
00213
00215 template <class T> void csList<T>::DeleteAll ()
00216 {
00217 csListElement *cur = head, *next = 0;
00218
00219 while(cur != 0)
00220 {
00221 next = cur->next;
00222 delete cur;
00223 cur = next;
00224 }
00225 head = tail = 0;
00226 }
00227
00229 template <class T> typename csList<T>::Iterator csList<T>::PushBack (
00230 const T& item)
00231 {
00232 csListElement* el = new csListElement (item, 0, tail);
00233 if (tail)
00234 tail->next = el;
00235 else
00236 head = el;
00237 tail = el;
00238
00239 return Iterator(el);
00240 }
00241
00243 template <class T> typename csList<T>::Iterator csList<T>::PushFront (
00244 const T& item)
00245 {
00246 csListElement* el = new csListElement (item, head, 0);
00247 if (head)
00248 head->prev = el;
00249 else
00250 tail = el;
00251 head = el;
00252
00253 return Iterator (el);
00254 }
00255
00256
00257 template <class T> void csList<T>::Delete (Iterator &it)
00258 {
00259 csListElement* el = it.ptr;
00260
00261 if (!el)
00262 return;
00263
00264
00265 if (it.IsReverse())
00266 --it;
00267 else
00268 ++it;
00269
00270 Delete(el);
00271 }
00272
00273 template <class T> void csList<T>::Delete (csListElement *el)
00274 {
00275 CS_ASSERT(el);
00276
00277
00278 if (el->prev)
00279 el->prev->next = el->next;
00280 else
00281 head = el->next;
00282
00283 if (el->next)
00284 el->next->prev = el->prev;
00285 else
00286 tail = el->prev;
00287
00288 delete el;
00289 }
00290
00291 #endif //__CS_UTIL_LIST_H__