Main Page   Namespace List   Class Hierarchy   Compound List   File List   Compound Members   File Members  

tll.h

Go to the documentation of this file.
00001 // Templated Linked List Classes    by Alan Baylis 2001
00002 
00003 #ifndef TLLH
00004 #define TLLH
00005 
00006 // Forward declarations
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};     // Used for the compare functions
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 //  virtual T * Get(int val) {T * pNewObject = new T(); pNewObject->linkPosition = val; pMyHead->Insert(pNewObject, pMyHead); return pNewObject;}
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

Generated on Fri Dec 23 05:20:18 2005 for Portals by doxygen1.2.15