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