00001 #pragma once
00002
00003 #include <stdarg.h>
00004
00006 const int INSERT_AFTER = 0;
00007 const int INSERT_BEFORE = 1;
00008
00009 template<class T>
00010 class CTList
00011 {
00012 private:
00013
00014 struct node
00015 {
00016 T item;
00017 node * next;
00018 node * prev;
00019
00020 };
00021
00022 node * m_root;
00023 node * m_last;
00024
00025 public:
00026 bool (*CmpFn)(T, T);
00027
00028
00029 class iterator
00030 {
00031 node * m_iterator;
00032
00033 public:
00034
00035 iterator(node * nodeptr = NULL) : m_iterator(nodeptr)
00036 {}
00037
00038 ~iterator()
00039 {
00040 m_iterator = NULL;
00041 }
00042
00043 iterator& operator++()
00044 {
00045 m_iterator = m_iterator->next;
00046 return *this;
00047 }
00048
00049 iterator& operator++(int)
00050 {
00051
00052
00053
00054 return (++*this);
00055 }
00056
00057 iterator& operator--()
00058 {
00059 m_iterator = m_iterator->prev;
00060 return *this;
00061 }
00062
00063 iterator& operator--(int)
00064 {
00065 iterator _temp = *this;
00066 --*this;
00067 return _temp;
00068 }
00069
00070 T& operator*()
00071 {
00072 return m_iterator->item;
00073 }
00074
00075 T& operator->()
00076 {
00077 return m_iterator->item;
00078 }
00079
00080 bool operator!=(const iterator &r)
00081 {
00082 if (this->m_iterator == r.m_iterator)
00083 return false;
00084 else
00085 return true;
00086
00087 }
00088 bool operator==(const iterator &r)
00089 {
00090 if (this->m_iterator == r.m_iterator)
00091 return true;
00092 else
00093 return false;
00094
00095 }
00096 node * GetNode()
00097 {
00098 return m_iterator;
00099 }
00100
00101
00102
00103 };
00104
00105 CTList()
00106 {
00107 m_root = NULL;
00108 m_last = NULL;
00109 }
00110
00111 ~CTList();
00112
00113 void operator+=(T p_item)
00114 {
00115 Insert(INSERT_AFTER, iterator(m_last), p_item);
00116 }
00117
00118 void operator-=(iterator &p_it)
00119 {
00120 Remove(p_it);
00121 }
00122
00123 iterator begin()
00124 {
00125 return iterator(m_root);
00126 }
00127 iterator end()
00128 {
00129 return iterator(m_last->next);
00130 }
00131 iterator last()
00132 {
00133 return iterator(m_last);
00134 }
00135
00136 iterator InsFront(const T p_item)
00137 {
00138 return Insert(INSERT_BEFORE, iterator(m_root), p_item);
00139 }
00140 iterator InsBack(const T p_item)
00141 {
00142 return Insert(INSERT_AFTER, iterator(m_last), p_item);
00143 }
00144 void RemFront()
00145 {
00146 Remove(iterator(m_root));
00147 }
00148 void RemBack()
00149 {
00150 Remove(iterator(m_last));
00151 }
00152 void RemoveAll();
00153
00154 iterator Find(T p_item);
00155
00156 void RemoveItem(T p_item);
00157
00158 bool IsEmpty()
00159 {
00160 if (m_root == NULL)
00161 return true;
00162 else
00163 return false;
00164 }
00165
00166 void Sort();
00167 int Count();
00168
00169 iterator Insert(const int method, iterator &p_it, const T p_item);
00170 void Remove(iterator &p_it);
00171 void Swap(iterator &p_it0, iterator &p_it1);
00172
00173 };
00174
00176
00177 template<class T>
00178 CTList<T>::~CTList()
00179 {
00180 node * n = m_root;
00181 while (n)
00182 {
00183 node * o = n;
00184 n = n->next;
00185 delete o;
00186
00187 }
00188 m_root = m_last = NULL;
00189 }
00191 template<class T>
00192 void CTList<T>::RemoveAll()
00193 {
00194 node * n = m_root;
00195 while (n)
00196 {
00197 node * o = n;
00198 n = n->next;
00199 delete o;
00200
00201 }
00202
00203 m_root = m_last = NULL;
00204
00205 }
00207 template<class T>
00208 CTList<T>::iterator CTList<T>::Insert(const int method, iterator &p_it, const T p_item)
00209 {
00210 node * _node = p_it.GetNode();
00211
00212 node * _new_node = new node;
00213
00214 if (!_new_node)
00215 {
00216 return iterator(NULL);
00217 }
00218
00219 _new_node->item = p_item;
00220 _new_node->next = NULL;
00221 _new_node->prev = NULL;
00222
00223
00224 if (m_root == NULL)
00225 {
00226 m_root = _new_node;
00227 m_last = m_root;
00228
00229 return iterator(_new_node);
00230 }
00231
00232 if (method == INSERT_BEFORE)
00233 {
00234 if (_node == m_root)
00235 {
00236 _new_node->next = m_root;
00237 m_root->prev = _new_node;
00238 m_root = _new_node;
00239
00240 }
00241 else
00242 {
00243 _new_node->next = _node;
00244 _new_node->prev = _node->prev;
00245 _node->prev->next = _new_node;
00246
00247 }
00248 }
00249 else
00250 {
00251 if (_node == m_last)
00252 {
00253 _new_node->prev = _node;
00254 _node->next = _new_node;
00255 m_last = _new_node;
00256
00257 }
00258 else
00259 {
00260 _new_node->next = _node->next;
00261 _new_node->prev = _node;
00262 _node->next = _new_node;
00263 }
00264 }
00265
00266 return iterator(_new_node);
00267
00268 }
00270 template<class T>
00271 void CTList<T>::Remove(iterator &p_it)
00272 {
00273 if (p_it == NULL) return;
00274
00275 node * _node = p_it.GetNode();
00276 node * _temp = _node;
00277
00278 if (_node == m_root)
00279 {
00280 m_root = m_root->next;
00281 if (m_root != NULL)
00282 m_root->prev = NULL;
00283 else
00284 m_last = NULL;
00285
00286 }
00287 else
00288 if (_node == m_last)
00289 {
00290 m_last = m_last->prev;
00291 if (m_last != NULL) m_last->next = NULL;
00292 }
00293 else
00294 {
00295 _node->prev->next = _node->next;
00296 _node->next->prev = _node->prev;
00297 }
00298
00299 delete _temp;
00300
00301 }
00303 template<class T>
00304 void CTList<T>::Swap(iterator &p_it0, iterator &p_it1)
00305 {
00306 node * _node0 = p_it0.GetNode();
00307 node * _node1 = p_it1.GetNode();
00308
00309 T _el_temp = _node0->item;
00310 _node0->item = _node1->item;
00311 _node1->item = _el_temp;
00312
00313 }
00315 template<class T>
00316 int CTList<T>::Count()
00317 {
00318 int n = 0;
00319 iterator it = begin();
00320
00321 while (it != NULL)
00322 {
00323 ++it;
00324 ++n;
00325 }
00326
00327 return n;
00328 }
00330 template<class T>
00331 CTList<T>::iterator CTList<T>::Find(T p_item)
00332 {
00333 iterator it = begin();
00334
00335 while (it != NULL && *it != p_item) ++it;
00336
00337 return it;
00338 }
00340 template<class T>
00341 void CTList<T>::RemoveItem(T p_item)
00342 {
00343 iterator it = Find(p_item);
00344 Remove(it);
00345 }
00347
00348
00349
00350 template<class T>
00351 void CTList<T>::Sort()
00352 {
00353 iterator it0;
00354 iterator it1;
00355
00356 for (it0 = begin(); it0 != NULL; it0++)
00357 {
00358 for (it1 = begin(); it1 != NULL; it1++)
00359 {
00360 if (it0 != it1 && CmpFn(*it0, *it1))
00361 Swap(it0, it1);
00362 }
00363 }
00364
00365
00366 }