00001
00002
00004
00005 #if !defined(AFX_TLISTNODE_H__B2E86785_EEDB_42AA_9CDE_C8B27A5756FC__INCLUDED_)
00006 #define AFX_TLISTNODE_H__B2E86785_EEDB_42AA_9CDE_C8B27A5756FC__INCLUDED_
00007
00008 #if _MSC_VER > 1000
00009 #pragma once
00010 #endif // _MSC_VER > 1000
00011
00012 #include <fcntl.h>
00013 #include <io.h>
00014 #include <stdlib.h>
00015 #include <windows.h>
00016 #include <gl/gl.h>
00017
00018 #include "TIteratorInterface.h"
00019
00020 template <class T> class TLinkedList
00021 {
00022
00023 protected:
00024 class TListNode
00025 {
00026
00027 protected:
00028
00029 BOOLEAN ownData;
00030
00031 TListNode* next;
00032 TListNode* prev;
00033
00034
00035 public:
00036 T* data;
00037 void setPrev(TListNode* p)
00038 {
00039 prev=p;
00040 };
00041 TListNode* getPrev()
00042 {
00043 return prev;
00044 };
00045 inline TListNode* setNext(TListNode* n)
00046 {
00047 TListNode* buff=next;
00048 next=n;
00049 return buff;
00050 };
00051 virtual T* peek(int i)
00052 {
00053 if (i>0)
00054 return next->peek(i-1);
00055 else
00056 return data;
00057 };
00058 void setOwnData(BOOLEAN d)
00059 {
00060 ownData=d;
00061 };
00062 TListNode (TListNode* n, T* d, BOOLEAN ownD)
00063 {
00064 next=n;
00065
00066 data=d;
00067 ownData=ownD;
00068 };
00069 virtual ~TListNode()
00070 {
00071 if (ownData)
00072 delete data;
00073 if (next)
00074 delete next;
00075 };
00076 TListNode* getNext()
00077 {
00078 return next;
00079 };
00080 };
00081
00082 TListNode* listStart;
00083 TListNode* listEnd;
00084 int itemCount;
00085 public:
00086 class TListIterator: public TIteratorInterface<T>
00087 {
00088 protected:
00089 TLinkedList<T>* parent;
00090 int aktPos;
00091 TListNode* aktNode;
00092 public:
00093 TListIterator(TLinkedList<T>* par)
00094 {
00095 aktPos=-1;
00096 parent=par;
00097 aktNode=NULL;
00098 };
00099 BOOLEAN hasNext()
00100 {
00101 if (((aktNode)&&(aktNode->getNext()))||((aktPos==-1)&&(parent->getListStart())))
00102 return TRUE;
00103 else
00104 return FALSE;
00105 };
00106 T* getNext()
00107 {
00108
00109
00110 if (hasNext())
00111 {
00112
00113 if ((aktPos==-1)&&(parent->getListStart()))
00114 aktNode=parent->getListStart();
00115 else
00116 aktNode=aktNode->getNext();
00117 aktPos++;
00118 return aktNode->peek(0);
00119 }
00120 else
00121 return NULL;
00122 };
00123 };
00124 TListIterator* getIterator();
00125 void push(T* d, BOOLEAN ownData);
00126 void pushLast(T* d, BOOLEAN ownData);
00127 void insert(T* d, int ind, BOOLEAN ownData);
00128 TListNode* getNode(int index);
00129 T* pop(BOOLEAN delData);
00130 T* peek(int i);
00131 T* popLast(BOOLEAN delData);
00132 T* peekLast();
00133 TListNode* getListStart();
00134 virtual ~TLinkedList();
00135 TLinkedList();
00136 int getItemCount();
00137 void deleteItem(TListNode* i);
00138 void insertSorted(T* d, BOOLEAN ownData)
00139 {
00140 TIteratorInterface<T>* it=getIterator();
00141 int insPos=0;
00142 while (it->hasNext()&&((*it->getNext())<=*d))
00143 {
00144 insPos++;
00145 }
00146 insert(d, insPos, ownData);
00147 delete it;
00148 }
00149
00150
00151 };
00152
00153
00154
00155
00156
00157
00158 template <class T> TLinkedList<T>::TListIterator* TLinkedList<T>::getIterator()
00159 {
00160 return new TListIterator(this);
00161 }
00162
00163 template <class T> void TLinkedList<T>::push(T* d, BOOLEAN ownData)
00164 {
00165 TListNode* lBuff=listStart;
00166 listStart=new TListNode(listStart,d,ownData);
00167 if (itemCount==-1)
00168 listEnd=listStart;
00169 itemCount++;
00170 if(lBuff)
00171 lBuff->setPrev(listStart);
00172 listStart->setPrev(NULL);
00173
00174 }
00175 template <class T> void TLinkedList<T>::insert(T* d, int ind, BOOLEAN ownData)
00176 {
00177
00178 TListNode* lBuff=listStart;
00179 if (itemCount==-1)
00180 {
00181
00182 push(d,ownData);
00183 return;
00184 }
00185 if (ind>itemCount)
00186 {
00187 pushLast(d,ownData);
00188 return;
00189 }
00190
00191 for (int i=0;i<ind;i++)
00192 lBuff=lBuff->getNext();
00193
00194 TListNode* newBuff;
00195 if (lBuff)
00196 {
00197 itemCount++;
00198 newBuff=new TListNode(lBuff,d,ownData);
00199 newBuff->setPrev(lBuff->getPrev());
00200 lBuff->setPrev(newBuff);
00201 }
00202 if (ind==0)
00203 listStart=newBuff;
00204
00205 }
00206 template <class T> void TLinkedList<T>::pushLast(T* d, BOOLEAN ownData)
00207 {
00208 TListNode* lBuff=listEnd;
00209 listEnd->setNext(new TListNode(listEnd,d,ownData));
00210 listEnd=listEnd->getNext();
00211 listEnd->setPrev(lBuff);
00212 listEnd->setNext(NULL);
00213 itemCount++;
00214 }
00215 template <class T> TLinkedList<T>::TListNode* TLinkedList<T>::getListStart()
00216 {
00217 return listStart;
00218 }
00219 template <class T> TLinkedList<T>::TListNode* TLinkedList<T>::getNode(int index)
00220 {
00221 TListNode* lBuff;
00222 lBuff=listStart;
00223 for (int i=1;i<=index;i++)
00224 {
00225 lBuff=lBuff->getNext();
00226 }
00227 return lBuff;
00228 }
00229
00230 template <class T> void TLinkedList<T>::deleteItem(TListNode* i)
00231 {
00232 TListNode* newNext=i->getNext();
00233 TListNode* newPrev=i->getPrev();
00234 if (newPrev)
00235 {
00236 newPrev->setNext(newNext);
00237
00238 }
00239 else
00240 {
00241 listStart=newNext;
00242 }
00243 if (newNext)
00244 {
00245 newNext->setPrev(newPrev);
00246 }
00247 else
00248 {
00249 listEnd=newPrev;
00250 }
00251 itemCount--;
00252 i->setNext(NULL);
00253 delete i;
00254 }
00255 template <class T> T* TLinkedList<T>::pop(BOOLEAN delData)
00256 {
00257 if (listStart)
00258 {
00259 T* dataBuff;
00260 TListNode* buff=listStart;
00261 listStart=listStart->setNext(NULL);
00262 if (listStart)
00263 listStart->setPrev(NULL);
00264 else
00265 listEnd=NULL;
00266 itemCount--;
00267 if (delData)
00268 {
00269 buff->setOwnData(TRUE);
00270 delete buff;
00271 return NULL;
00272 }
00273 else
00274 {
00275 dataBuff=buff->data;
00276 buff->setOwnData(FALSE);
00277 delete buff;
00278 return dataBuff;
00279 }
00280
00281 }
00282 else
00283 return NULL;
00284
00285 }
00286 template <class T> T* TLinkedList<T>::popLast(BOOLEAN delData)
00287 {
00288 if (listEnd)
00289 {
00290 T* dataBuff;
00291 TListNode* buff=listEnd;
00292 listEnd=listEnd->getPrev();
00293 if (listEnd)
00294 listEnd->setNext(NULL);
00295 else
00296 listStart=NULL;
00297 itemCount--;
00298 if (delData)
00299 {
00300 buff->setOwnData(TRUE);
00301 delete buff;
00302 return NULL;
00303 }
00304 else
00305 {
00306 dataBuff=buff->data;
00307 buff->setOwnData(FALSE);
00308 delete buff;
00309 return dataBuff;
00310 }
00311
00312 }
00313 else
00314 return NULL;
00315 }
00316 template <class T> T* TLinkedList<T>::peekLast()
00317 {
00318 return listEnd->data;
00319 }
00320 template <class T> T* TLinkedList<T>::peek(int i)
00321 {
00322 if (listStart)
00323 return listStart->peek(i);
00324 else
00325 return NULL;
00326 }
00327 template <class T> TLinkedList<T>::~TLinkedList()
00328 {
00329 if (listStart)
00330 delete listStart;
00331 }
00332 template <class T> TLinkedList<T>::TLinkedList()
00333 {
00334 itemCount=-1;
00335 listStart=NULL;
00336 listEnd=NULL;
00337 }
00338 template <class T> int TLinkedList<T>::getItemCount()
00339 {
00340 return itemCount;
00341 }
00342
00343
00344
00345 #endif // !defined(AFX_TLISTNODE_H__B2E86785_EEDB_42AA_9CDE_C8B27A5756FC__INCLUDED_)
