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