list.h
Go to the documentation of this file.
00001 #ifndef MEGATREE_LIST_H_
00002 #define MEGATREE_LIST_H_
00003 
00004 #include <boost/shared_ptr.hpp>
00005 #include <stdexcept>
00006 
00007 namespace megatree
00008 {
00009 
00010   template <typename T>
00011   struct ListNode
00012   {
00013     ListNode<T>(const T& _object, ListNode<T>* _previous, ListNode<T>* _next) 
00014     : object(_object), previous(_previous), next(_next)
00015     {}
00016 
00017     T object;
00018     ListNode<T>* previous;
00019     ListNode<T>* next;
00020 
00021   };
00022 
00023   //forward declare the list iterator so that the list can use it
00024   template <typename T>
00025   class ListIterator;
00026 
00027   template <typename T>
00028   class List
00029   {
00030   public:
00031     List<T>():
00032     list_front(NULL),
00033     list_back(NULL)
00034     {}
00035 
00036     ~List<T>()
00037     {
00038       ListNode<T>* node = list_front;
00039       while(node)
00040       {
00041         ListNode<T>* next_node = node->next;
00042         delete node;
00043         node = next_node;
00044       }
00045     }
00046 
00047     ListIterator<T> frontIterator()
00048     {
00049       return ListIterator<T>(list_front);
00050     }
00051 
00052     ListIterator<T> backIterator()
00053     {
00054       return ListIterator<T>(list_back);
00055     }
00056 
00057 
00058     ListNode<T>* getFrontPointer()
00059     {
00060       return list_front;
00061     }
00062 
00063     ListNode<T>* getBackPointer()
00064     {
00065       return list_back;
00066     }
00067 
00068     void push_front(const T& object)
00069     {
00070       //create the new node
00071       ListNode<T>* node = new ListNode<T>(object, NULL, list_front);
00072 
00073       //make sure the front of the list points to it as its previous
00074       if(list_front)
00075         list_front->previous = node;
00076 
00077       //make sure the list stores this node as the new front
00078       list_front = node;
00079 
00080       //we also want to make this node the back if there's nothing on the back
00081       //of the list
00082       if(!list_back)
00083         list_back = node;
00084     }
00085 
00086     void push_back(const T& object)
00087     {
00088       //create the new node
00089       ListNode<T>* node = new ListNode<T>(object, list_back, NULL);
00090 
00091       //make sure the back of the list points to it as its next
00092       if(list_back)
00093         list_back->next = node;
00094 
00095       //make sure the list stores this node as the new back
00096       list_back = node;
00097 
00098       //we also want to make this node the front if there's nothing on the back
00099       //of the list
00100       if(!list_front)
00101         list_front = node;
00102     }
00103 
00104     T& front()
00105     {
00106       if(!list_front)
00107         throw std::runtime_error("You called front on an empty list!");
00108 
00109       return list_front->object;
00110     }
00111 
00112     void pop_front()
00113     {
00114       if(!list_front)
00115         return;
00116 
00117       //remove the front node from the list
00118       ListNode<T>* new_front = list_front->next;
00119 
00120       if(new_front)
00121         new_front->previous = NULL;
00122 
00123       //if the front and the back of the list are the same, then we need to set
00124       //the back to NULL
00125       if(list_front == list_back)
00126         list_back = NULL;
00127 
00128       delete list_front;
00129       list_front = new_front;
00130     }
00131 
00132     T& back()
00133     {
00134       if(!list_back)
00135         throw std::runtime_error("You called back on an empty list!");
00136 
00137       return list_back->object;
00138     }
00139 
00140 
00141     void pop_back()
00142     {
00143       if(!list_back)
00144         return;
00145 
00146       //remove the back node from the list
00147       ListNode<T>* new_back = list_back->previous;
00148 
00149       //if the front and the back of the list are the same, then we need to set
00150       //the back to NULL
00151       if(list_front == list_back)
00152         list_front = NULL;
00153 
00154 
00155       if(new_back)
00156         new_back->next = NULL;
00157 
00158       delete list_back;
00159       list_back = new_back;
00160     }
00161 
00162     void erase(ListNode<T>* node)
00163     {
00164       assert(node);
00165 
00166       if (node == list_front && node == list_back)
00167       {
00168         list_front = list_back = NULL;
00169       }
00170       else if (node == list_front)
00171       {
00172         list_front = node->next;
00173         node->next->previous = NULL;
00174       }
00175       else if (node == list_back)
00176       {
00177         list_back = node->previous;
00178         node->previous->next = NULL;
00179       }
00180       else
00181       {
00182         node->previous->next = node->next;
00183         node->next->previous = node->previous;
00184       }
00185 
00186       delete node;
00187       node = NULL;
00188     }
00189 
00190     void moveToFront(ListNode<T>* node)
00191     {
00192       assert(node);
00193 
00194       //if the node is already on the front, we'll just return
00195       if(node == list_front)
00196         return;
00197 
00198       //first, we want to remove the node from its current location in the list
00199       node->previous->next = node->next;
00200 
00201       //if the node is the back, we need to change that pointer
00202       if(node == list_back)
00203         list_back = node->previous;
00204       else
00205         node->next->previous = node->previous;
00206 
00207       //next, we want to put the node on the front of the list
00208       node->previous = NULL;
00209       node->next = list_front;
00210 
00211       list_front->previous = node;
00212       list_front = node;
00213     }
00214 
00215     void moveToBack(ListNode<T>* node)
00216     {
00217       assert(node);
00218 
00219       //if the node is already on the back, we'll just return
00220       if(node == list_back)
00221         return;
00222 
00223       //first, we want to remove the node from its current location in the list
00224       if(node->previous)
00225         node->previous->next = node->next;
00226 
00227       if(node->next)
00228         node->next->previous = node->previous;
00229 
00230       //if the node is the front, we need to change that pointer
00231       if(node == list_front)
00232         list_front = node->next;
00233 
00234       //next, we want to put the node on the back of the list
00235       node->next = NULL;
00236       node->previous = list_back;
00237 
00238       if(list_back)
00239         list_back->next = node;
00240 
00241       list_back = node;
00242     }
00243 
00244     void spliceToBack(List& splice_list)
00245     {
00246       //make sure the back of the list points to the spliced list as its next
00247       if(list_back && splice_list.list_front)
00248         list_back->next = splice_list.list_front;
00249 
00250       //make sure the list stores the back of the spliced list as the new back
00251       if(splice_list.list_back)
00252         list_back = splice_list.list_back;
00253 
00254       //we also want to make the spliced list the front if there's nothing on the back
00255       //of the list
00256       if(!list_front && splice_list.list_front)
00257         list_front = splice_list.list_front;
00258 
00259       //now, the spliced list needs to be invalidated
00260       splice_list.list_front = NULL;
00261       splice_list.list_back = NULL;
00262     }
00263 
00264     bool empty()
00265     {
00266       return list_front == NULL && list_back == NULL;
00267     }
00268 
00269 
00270   private:
00271     ListNode<T>* list_front;
00272     ListNode<T>* list_back;
00273   };
00274 
00275   template <class T>
00276   class ListIterator
00277   {
00278   public:
00279     ListIterator() : node(NULL) {}
00280     ListIterator(ListNode<T>* _node)
00281       : node(_node)
00282     {}
00283 
00284     ListIterator(const ListIterator<T> &o)
00285       : node(o.node)
00286     {
00287     }
00288 
00289     void next()
00290     {
00291       node = node->next;
00292     }
00293 
00294     void previous()
00295     {
00296       node = node->previous;
00297     }
00298 
00299     bool finished()
00300     {
00301       return !node;
00302     }
00303 
00304     ListNode<T>* getNode()
00305     {
00306       return node;
00307     }
00308 
00309     T& get()
00310     {
00311       return node->object;
00312     }
00313 
00314     bool operator==(const ListIterator<T>& o) const
00315     {
00316       return node == o.node;
00317     }
00318 
00319   private:
00320     ListNode<T>* node;
00321   };
00322 
00323 }
00324 
00325 #endif


megatree_core
Author(s): Stuart Glaser
autogenerated on Thu Nov 28 2013 11:30:23