00001
00002
00003 #ifndef TLLH
00004 #define TLLH
00005
00006
00007 template <class T> class Node;
00008 template <class T> class HeadNode;
00009 template <class T> class InternalNode;
00010 template <class T> class TailNode;
00011
00012 enum {smaller, bigger, same};
00013
00014 template <class T>
00015 class Node
00016 {
00017 public:
00018 Node() {};
00019 virtual ~Node() {};
00020 virtual Node * Insert(T * pNewObject, Node<T> * pPrevious) = 0;
00021 virtual void ModifyLinkPosition() = 0;
00022 virtual void SetPrevious(Node<T> * pPrevious) = 0;
00023 virtual void SetNext(Node<T> * pNext) = 0;
00024 virtual void DeleteList() = 0;
00025
00026 virtual T * Get(int val) = 0;
00027 virtual void Delete(int val) = 0;
00028 private:
00029 };
00030
00031 template <class T>
00032 class InternalNode: public Node<T>
00033 {
00034 public:
00035 InternalNode(T * pNewObject, Node<T> * pNext, Node<T> * pPrevious);
00036 ~InternalNode() {}
00037 virtual Node<T> * Insert(T * pNewObject, Node<T> * pPrevious);
00038 virtual void DeleteList() {pMyNext->DeleteList(); delete pThisObject; delete this;}
00039
00040 virtual void ModifyLinkPosition() {pMyNext->ModifyLinkPosition(); pThisObject->linkPosition--;}
00041 virtual void SetPrevious(Node<T> * pPrevious) {pMyPrevious = pPrevious;}
00042 virtual void SetNext(Node<T> * pNext) {pMyNext = pNext;}
00043 virtual T * Get(int val)
00044 {
00045 if (pThisObject->GetMyPosition() == val)
00046 return pThisObject;
00047 else
00048 return pMyNext->Get(val);
00049 }
00050 virtual void Delete(int val)
00051 {
00052 if (pThisObject->GetMyPosition() == val)
00053 {
00054 this->ModifyLinkPosition();
00055
00056 pMyNext->SetPrevious(pMyPrevious);
00057 pMyPrevious->SetNext(pMyNext);
00058 delete this;
00059 }
00060 else
00061 pMyNext->Delete(val);
00062 }
00063 private:
00064 T * pThisObject;
00065 Node<T> * pMyNext;
00066 Node<T> * pMyPrevious;
00067 };
00068
00069 template <class T>
00070 InternalNode<T>::InternalNode(T * pNewObject, Node<T> * pNext, Node<T> * pPrevious):
00071 pThisObject(pNewObject),pMyNext(pNext),pMyPrevious(pPrevious)
00072 {
00073 }
00074
00075 template <class T>
00076 Node<T> * InternalNode<T>::Insert(T * pNewObject, Node<T> * pPrevious)
00077 {
00078 int answer = pThisObject->Compare(*pNewObject);
00079 switch(answer)
00080 {
00081 case same:
00082 case bigger:
00083 {
00084 InternalNode<T> * internal = new InternalNode<T>(pNewObject, this, pPrevious);
00085 pMyPrevious->SetNext(internal);
00086 pMyPrevious = internal;
00087 return internal;
00088 }
00089 case smaller:
00090 pMyNext = pMyNext->Insert(pNewObject, this);
00091 return this;
00092 }
00093 return this;
00094 }
00095
00096 template <class T>
00097 class TailNode: public Node<T>
00098 {
00099 public:
00100 TailNode(HeadNode<T> * pHead);
00101 ~TailNode() {}
00102 virtual Node<T> * Insert(T * pNewObject, Node<T> * pPrevious);
00103 virtual void ModifyLinkPosition() {};
00104 virtual void SetPrevious(Node<T> * pPrevious) {};
00105 virtual void SetNext(Node<T> * pNext) {};
00106 virtual void DeleteList() {delete this;}
00107
00108
00109 virtual T * Get(int val) {return NULL;}
00110 virtual void Delete(int val) {};
00111 private:
00112 HeadNode<T> * pMyHead;
00113 };
00114
00115 template <class T>
00116 TailNode<T>::TailNode(HeadNode<T> * pHead):
00117 pMyHead(pHead)
00118 {
00119 }
00120
00121 template <class T>
00122 Node<T> * TailNode<T>::Insert(T * pNewObject, Node<T> * pPrevious)
00123 {
00124 InternalNode<T> * internal = new InternalNode<T>(pNewObject, this, pPrevious);
00125 return internal;
00126 }
00127
00128 template <class T>
00129 class HeadNode: public Node<T>
00130 {
00131 public:
00132 HeadNode();
00133 ~HeadNode() {};
00134 virtual Node<T> * Insert(T * pNewObject, Node<T> * pPrevious);
00135 virtual void ModifyLinkPosition() {};
00136 virtual void SetPrevious(Node<T> * pPrevious) {};
00137 virtual void SetNext(Node<T> * pNext) {pMyNext = pNext;}
00138 virtual void DeleteList() {pMyNext->DeleteList(); delete this;}
00139
00140 virtual T * Get(int val) {return pMyNext->Get(val);}
00141 virtual void Delete(int val) {pMyNext->Delete(val);}
00142 private:
00143 Node<T> * pMyNext;
00144 Node<T> * pMyTail;
00145 };
00146
00147 template <class T>
00148 HeadNode<T>::HeadNode()
00149 {
00150 pMyTail = new TailNode<T>(this);
00151 pMyNext = pMyTail;
00152 }
00153
00154 template <class T>
00155 Node<T> * HeadNode<T>::Insert(T * pNewObject, Node<T> * pPrevious)
00156 {
00157 pMyNext = pMyNext->Insert(pNewObject, pPrevious);
00158 return this;
00159 }
00160
00161 template <class T>
00162 class LinkedList
00163 {
00164 public:
00165 LinkedList();
00166 ~LinkedList() {pMyHead->DeleteList();}
00167 void Insert(T * pNewObject);
00168 T * Get(int val) {return pMyHead->Get(val);}
00169 void Delete(int val) {pMyHead->Delete(val);}
00170
00171 int numObjects;
00172 private:
00173 HeadNode<T> * pMyHead;
00174 };
00175
00176 template <class T>
00177 LinkedList<T>::LinkedList()
00178 {
00179 numObjects = 0;
00180 pMyHead = new HeadNode<T>;
00181 }
00182
00183 template <class T>
00184 void LinkedList<T>::Insert(T * pNewObject)
00185 {
00186 pMyHead->Insert(pNewObject, pMyHead);
00187 }
00188
00189 #endif