filters
list.h00001
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
00030
00031
00032 #ifndef __MSWRITE_LIST_H__
00033 #define __MSWRITE_LIST_H__
00034
00035 #ifndef NULL
00036 #define NULL 0
00037 #endif
00038
00039 #include <assert.h>
00040
00041 namespace MSWrite
00042 {
00043 template <class dtype> class List;
00044 template <class dtype> class ListIterator;
00045 template <class dtype>
00046 class ListElement
00047 {
00048 private:
00049 dtype m_data;
00050 ListElement *m_prev, *m_next;
00051
00052 public:
00053 ListElement ()
00054 {
00055 m_prev = m_next = NULL;
00056 }
00057
00058 ListElement (dtype &data)
00059 {
00060 m_prev = m_next = NULL;
00061 m_data = data;
00062 }
00063
00064 ~ListElement ()
00065 {
00066 }
00067
00068 dtype &getData (void) const
00069 {
00070 return m_data;
00071 }
00072 dtype &operator* (void) const
00073 {
00074 return m_data;
00075 }
00076 bool operator== (const dtype &rhs)
00077 {
00078 return this->data == rhs.data;
00079 }
00080
00081 void setData (const dtype &data)
00082 {
00083 m_data = data;
00084 }
00085 dtype &operator= (const dtype &rhs)
00086 {
00087 if (this == &rhs)
00088 return *this;
00089
00090 this->data = rhs.data;
00091 return this->data;
00092 }
00093
00094 friend class List <dtype>;
00095 friend class ListIterator <dtype>;
00096 };
00097
00098 template <class dtype> class List;
00099 template <class dtype>
00100 class ListIterator
00101 {
00102 private:
00103 bool m_forward;
00104 ListElement <dtype> *m_upto;
00105
00106 void setPtr (ListElement <dtype> *ptr)
00107 {
00108 m_upto = ptr;
00109 }
00110
00111 public:
00112 ListIterator (const bool forward = true)
00113 {
00114 m_forward = forward;
00115 }
00116
00117 ListIterator <dtype> &prev (void)
00118 {
00119 if (m_forward)
00120 m_upto = m_upto->m_prev;
00121 else
00122 m_upto = m_upto->m_next;
00123
00124 return *this;
00125 }
00126
00127 ~ListIterator ()
00128 {
00129 }
00130
00131 ListIterator <dtype> &operator-- (void)
00132 {
00133 return prev ();
00134 }
00135
00136 ListIterator <dtype> &operator-- (int)
00137 {
00138 return prev ();
00139 }
00140
00141 ListIterator <dtype> &next (void)
00142 {
00143 if (m_forward)
00144 m_upto = m_upto->m_next;
00145 else
00146 m_upto = m_upto->m_prev;
00147
00148 return *this;
00149 }
00150
00151 ListIterator <dtype> &operator++ (void)
00152 {
00153 return next ();
00154 }
00155
00156 ListIterator <dtype> &operator++ (int)
00157 {
00158 return next ();
00159 }
00160
00161 bool operator== (const ListIterator <dtype> &rhs)
00162 {
00163 return this->m_upto == rhs.m_upto;
00164 }
00165
00166 bool operator!= (const ListIterator <dtype> &rhs)
00167 {
00168 return this->m_upto != rhs.m_upto;
00169 }
00170
00171 dtype &operator* (void)
00172 {
00173
00174 return m_upto->m_data;
00175 }
00176
00177 friend class List <dtype>;
00178 };
00179
00180 template <class dtype>
00181 class List
00182 {
00183 private:
00184 ListElement <dtype> *m_head, *m_tail;
00185 int m_num;
00186 bool m_good;
00187
00188 public:
00189 List ()
00190 {
00191 m_head = m_tail = (ListElement <dtype> *) NULL;
00192 m_num = 0;
00193 m_good = true;
00194 }
00195
00196 virtual ~List ()
00197 {
00198 killself ();
00199 }
00200
00201 void killself (void)
00202 {
00203 ListElement <dtype> *e = m_head;
00204 ListElement <dtype> *nexte;
00205 while (e)
00206 {
00207 nexte = e->m_next;
00208 delete e;
00209 e = nexte;
00210 }
00211 m_head = m_tail = NULL;
00212 m_num = 0;
00213 m_good = true;
00214 }
00215
00216 bool empty (void) const
00217 {
00218 return m_head;
00219 }
00220
00221 bool good (void) const
00222 {
00223 return m_good;
00224 }
00225
00226 bool bad (void) const
00227 {
00228 return !good ();
00229 }
00230
00231 bool addToFront (dtype &data)
00232 {
00233 ListElement <dtype> *e = new ListElement <dtype> (data);
00234 if (!e)
00235 {
00236 m_good = false;
00237 return false;
00238 }
00239
00240 if (m_head)
00241 {
00242 e->next = m_head;
00243 m_head->prev = e;
00244 m_head = e;
00245 }
00246
00247 else
00248 {
00249 m_head = m_tail = e;
00250 }
00251
00252 m_num++;
00253 return true;
00254 }
00255
00256 bool addToBack (void)
00257 {
00258 ListElement <dtype> *e = new ListElement <dtype> ();
00259 if (!e)
00260 {
00261 m_good = false;
00262 return false;
00263 }
00264
00265 if (m_tail)
00266 {
00267 e->m_prev = m_tail;
00268 m_tail->m_next = e;
00269 m_tail = e;
00270 }
00271
00272 else
00273 {
00274 m_head = m_tail = e;
00275 }
00276
00277 m_num++;
00278 return true;
00279 }
00280
00281
00282
00283 bool addToBack (const dtype &data)
00284 {
00285 if (!addToBack ())
00286 return false;
00287 m_tail->setData (data);
00288 return true;
00289 }
00290
00291 int getNumElements (void) const
00292 {
00293 return m_num;
00294 }
00295
00296 List <dtype> &operator= (const List <dtype> &rhs)
00297 {
00298 if (this == &rhs)
00299 return *this;
00300
00301 killself ();
00302
00303 m_num = rhs.m_num;
00304 m_good = rhs.m_good;
00305
00306 ListElement <dtype> *e = rhs.m_head;
00307 while (e)
00308 {
00309 if (!addToBack (e->m_data)) break;
00310 e = e->m_next;
00311 }
00312
00313 return *this;
00314 }
00315
00316 typedef ListIterator <dtype> Iterator;
00317 friend class ListIterator <dtype>;
00318
00319 ListIterator <dtype> begin (const bool forward = true) const
00320 {
00321 ListIterator <dtype> ret (forward);
00322 if (forward)
00323 ret.setPtr (m_head);
00324 else
00325 ret.setPtr (m_tail);
00326 return ret;
00327 }
00328
00329 ListIterator <dtype> end (void) const
00330 {
00331 ListIterator <dtype> ret;
00332 ret.setPtr (NULL);
00333 return ret;
00334 }
00335
00336 ListIterator <dtype> erase (ListIterator <dtype> &it)
00337 {
00338
00339 ListElement <dtype> *eat = it.m_upto;
00340 ListElement <dtype> *prevElement = it.m_upto->m_prev;
00341 ListElement <dtype> *nextElement = it.m_upto->m_next;
00342 it++;
00343 delete (eat);
00344
00345 if (prevElement)
00346 prevElement->m_next = nextElement;
00347 else
00348 m_head = nextElement;
00349
00350 if (nextElement)
00351 nextElement->m_prev = prevElement;
00352 else
00353 m_tail = prevElement;
00354
00355 m_num--;
00356 return it;
00357 }
00358
00359 ListIterator <dtype> search (const dtype &value) const
00360 {
00361 ListIterator <dtype> it;
00362 for (it = begin (); it != end (); it++)
00363 {
00364 if ((*it) == value)
00365 break;
00366 }
00367
00368
00369 return it;
00370 }
00371 };
00372 }
00373
00374 #endif // #ifndef __MSWRITE_LIST_H__
00375
00376
|