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 void DeleteAll() = 0;
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 //  virtual void DeleteAll() {pMyNext->DeleteAll(); delete pThisObject; delete this;}
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 //      delete pThisObject;
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 //  virtual void DeleteAll() {};
00108 //  virtual T * Get(int val) {T * pNewObject = new T(); pNewObject->linkPosition = val; pMyHead->Insert(pNewObject, pMyHead); return pNewObject;}
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 //  virtual void DeleteAll() {pMyNext->DeleteAll(); pMyNext = pMyTail;}
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 //  void DeleteAll() {pMyHead->DeleteAll();}
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

Generated on Fri Dec 23 05:15:48 2005 for Constructive Solid Geometry by doxygen1.2.15