00001 // 00002 // List.cc 00003 // 00004 // List: A List class which holds objects of type Object. 00005 // 00006 // Part of the ht://Dig package <http://www.htdig.org/> 00007 // Copyright (c) 1999, 2000, 2001 The ht://Dig Group 00008 // For copyright details, see the file COPYING in your distribution 00009 // or the GNU General Public License version 2 or later 00010 // <http://www.gnu.org/copyleft/gpl.html> 00011 // 00012 // $Id: List_8cc-source.html,v 1.1 2008年06月08日 10:12:54 sebdiaz Exp $ 00013 // 00014 00015 #ifdef HAVE_CONFIG_H 00016 #include "config.h" 00017 #endif /* HAVE_CONFIG_H */ 00018 00019 #include "List.h" 00020 00021 class listnode 00022 { 00023 public: 00024 00025 listnode *next; 00026 listnode *prev; 00027 Object *object; 00028 }; 00029 00030 00031 //********************************************************************* 00032 // List::List() 00033 // Constructor 00034 // 00035 List::List() 00036 { 00037 head = tail = 0; 00038 number = 0; 00039 } 00040 00041 00042 //********************************************************************* 00043 // List::~List() 00044 // Destructor 00045 // 00046 List::~List() 00047 { 00048 Destroy(); 00049 } 00050 00051 00052 //********************************************************************* 00053 // void List::Release() 00054 // Release all the objects from our list. 00055 // 00056 void List::Release() 00057 { 00058 listnode *node; 00059 while (head) 00060 { 00061 node = head; 00062 head = head->next; 00063 delete node; 00064 } 00065 head = tail = 0; 00066 number = 0; 00067 cursor.Clear(); 00068 } 00069 00070 00071 //********************************************************************* 00072 // void List::Destroy() 00073 // Delete all the objects from our list. 00074 // 00075 void List::Destroy() 00076 { 00077 listnode *node; 00078 while (head) 00079 { 00080 node = head; 00081 head = head->next; 00082 delete node->object; 00083 delete node; 00084 } 00085 head = tail = 0; 00086 number = 0; 00087 cursor.Clear(); 00088 } 00089 00090 00091 //********************************************************************* 00092 // void List::Add(Object *object) 00093 // Add an object to the list. 00094 // 00095 void List::Add(Object *object) 00096 { 00097 listnode *node = new listnode; 00098 node->next = 0; 00099 node->prev = tail; 00100 node->object = object; 00101 if (tail) 00102 { 00103 tail->next = node; 00104 tail = node; 00105 } 00106 else 00107 { 00108 head = tail = node; 00109 } 00110 00111 number++; 00112 } 00113 00114 00115 //********************************************************************* 00116 // void List::Insert(Object *object, int position) 00117 // Add an object to the list. 00118 // 00119 void List::Insert(Object *object, int position) 00120 { 00121 listnode *node = new listnode; 00122 node->next = 0; 00123 node->prev = 0; 00124 node->object = object; 00125 00126 listnode *ln = head; 00127 00128 for (int i = 0; i < position && ln; i++, ln = ln->next) 00129 ; 00130 if (!ln) 00131 { 00132 node->prev = tail; 00133 if (tail) 00134 tail->next = node; 00135 tail = node; 00136 00137 // 00138 // The list is empty. This is a simple case, then. 00139 // 00140 if (!head) 00141 head = node; 00142 } 00143 else 00144 { 00145 if (ln == head) 00146 { 00147 node->next = head; 00148 node->next->prev = node; 00149 head = node; 00150 } 00151 else 00152 { 00153 node->next = ln; 00154 node->prev = ln->prev; 00155 node->prev->next = node; 00156 node->next->prev = node; 00157 } 00158 } 00159 00160 cursor.current_index = -1; 00161 number++; 00162 } 00163 00164 00165 //********************************************************************* 00166 // void List::Assign(Object *object, int position) 00167 // Assign a new value to an index. 00168 // 00169 void List::Assign(Object *object, int position) 00170 { 00171 // 00172 // First make sure that there is something there! 00173 // 00174 while (number < position + 1) 00175 { 00176 Add(0); 00177 } 00178 00179 // 00180 // Now find the listnode to put the new object in 00181 // 00182 listnode *temp = head; 00183 00184 for (int i = 0; temp && i < position; i++) 00185 { 00186 temp = temp->next; 00187 } 00188 00189 cursor.current_index = -1; 00190 delete temp->object; 00191 temp->object = object; 00192 } 00193 00194 00195 //********************************************************************* 00196 // int List::Remove(Object *object) 00197 // Remove an object from the list. 00198 // 00199 int List::Remove(Object *object) 00200 { 00201 listnode *node = head; 00202 while (node) 00203 { 00204 if (node->object == object) 00205 { 00206 // 00207 // Found it! 00208 // 00209 // 00210 // If we are in the middle of a Get_Next() sequence, we need to 00211 // fix up any problems with the current node. 00212 // 00213 if (cursor.current == node) 00214 { 00215 cursor.current = node->next; 00216 } 00217 00218 if (head == tail) 00219 { 00220 head = tail = 0; 00221 } 00222 else if (head == node) 00223 { 00224 head = head->next; 00225 head->prev = 0; 00226 } 00227 else if (tail == node) 00228 { 00229 tail = tail->prev; 00230 tail->next = 0; 00231 } 00232 else 00233 { 00234 node->next->prev = node->prev; 00235 node->prev->next = node->next; 00236 } 00237 00238 delete node; 00239 number--; 00240 cursor.current_index = -1; 00241 return 1; 00242 } 00243 node = node->next; 00244 } 00245 return 0; 00246 } 00247 00248 //********************************************************************* 00249 // 00250 int List::Remove(int position, int action /* = LIST_REMOVE_DESTROY */) 00251 { 00252 Object *o = List::operator[](position); 00253 if(action == LIST_REMOVE_DESTROY) delete o; 00254 return List::Remove(o); 00255 } 00256 00257 //********************************************************************* 00258 // Object *List::Get_Next() 00259 // Return the next object in the list. 00260 // 00261 Object *List::Get_Next(ListCursor& cursor) const 00262 { 00263 listnode *temp = cursor.current; 00264 00265 if (cursor.current) 00266 { 00267 cursor.current = cursor.current->next; 00268 if (cursor.current_index >= 0) 00269 cursor.current_index++; 00270 } 00271 else 00272 return 0; 00273 return temp->object; 00274 } 00275 00276 00277 //********************************************************************* 00278 // Object *List::Get_First() 00279 // Return the first object in the list. 00280 // 00281 Object *List::Get_First() 00282 { 00283 if (head) 00284 return head->object; 00285 else 00286 return 0; 00287 } 00288 00289 00290 //********************************************************************* 00291 // int List::Index(Object *obj) 00292 // Return the index of an object in the list. 00293 // 00294 int List::Index(Object *obj) 00295 { 00296 listnode *temp = head; 00297 int index = 0; 00298 00299 while (temp && temp->object != obj) 00300 { 00301 temp = temp->next; 00302 index++; 00303 } 00304 if (index >= number) 00305 return -1; 00306 else 00307 return index; 00308 } 00309 00310 00311 //********************************************************************* 00312 // Object *List::Next(Object *prev) 00313 // Return the next object in the list. Using this, the list will 00314 // appear as a circular list. 00315 // 00316 Object *List::Next(Object *prev) 00317 { 00318 listnode *node = head; 00319 while (node) 00320 { 00321 if (node->object == prev) 00322 { 00323 node = node->next; 00324 if (!node) 00325 return head->object; 00326 else 00327 return node->object; 00328 } 00329 node = node->next; 00330 } 00331 00332 return 0; 00333 } 00334 00335 00336 //********************************************************************* 00337 // Object *List::Previous(Object *prev) 00338 // Return the previous object in the list. Using this, the list will 00339 // appear as a circular list. 00340 // 00341 Object *List::Previous(Object *prev) 00342 { 00343 listnode *node = tail; 00344 while (node) 00345 { 00346 if (node->object == prev) 00347 { 00348 node = node->prev; 00349 if (!node) 00350 return tail->object; 00351 else 00352 return node->object; 00353 } 00354 node = node->prev; 00355 } 00356 00357 return 0; 00358 } 00359 00360 00361 //********************************************************************* 00362 // Return the nth object in the list. 00363 // 00364 const Object *List::Nth(ListCursor& cursor, int n) const 00365 { 00366 if (n < 0 || n >= number) 00367 return 0; 00368 00369 listnode *temp = head; 00370 00371 if (cursor.current_index == n) 00372 return cursor.current->object; 00373 00374 if (cursor.current && cursor.current_index >= 0 && n == cursor.current_index + 1) 00375 { 00376 cursor.current = cursor.current->next; 00377 if (!cursor.current) 00378 { 00379 cursor.current_index = -1; 00380 return 0; 00381 } 00382 cursor.current_index = n; 00383 return cursor.current->object; 00384 } 00385 00386 for (int i = 0; temp && i < n; i++) 00387 { 00388 temp = temp->next; 00389 } 00390 00391 if (temp) 00392 { 00393 cursor.current_index = n; 00394 cursor.current = temp; 00395 return temp->object; 00396 } 00397 else 00398 return 0; 00399 } 00400 00401 00402 //********************************************************************* 00403 // Object *List::Last() 00404 // Return the last object inserted. 00405 // 00406 Object *List::Last() 00407 { 00408 if (tail) 00409 { 00410 return tail->object; 00411 } 00412 00413 return 0; 00414 } 00415 00416 //********************************************************************* 00417 // 00418 Object *List::Pop(int action /* = LIST_REMOVE_DESTROY */) 00419 { 00420 Object *o = 0; 00421 00422 if (tail) { 00423 if(action == LIST_REMOVE_DESTROY) { 00424 delete tail->object; 00425 } else { 00426 o = tail->object; 00427 } 00428 if(head == tail) { 00429 head = tail = 0; 00430 } else { 00431 tail = tail->prev; 00432 tail->next = 0; 00433 } 00434 } 00435 00436 return o; 00437 } 00438 00439 00440 //********************************************************************* 00441 // Object *List::Copy() const 00442 // Return a deep copy of the list. 00443 // 00444 Object *List::Copy() const 00445 { 00446 List *list = new List; 00447 ListCursor cursor; 00448 00449 Start_Get(cursor); 00450 Object *obj; 00451 while ((obj = Get_Next(cursor))) 00452 { 00453 list->Add(obj->Copy()); 00454 } 00455 return list; 00456 } 00457 00458 00459 //********************************************************************* 00460 // List &List::operator=(List &list) 00461 // Return a deep copy of the list. 00462 // 00463 List &List::operator=(List &list) 00464 { 00465 Destroy(); 00466 list.Start_Get(); 00467 Object *obj; 00468 while ((obj = list.Get_Next())) 00469 { 00470 Add(obj->Copy()); 00471 } 00472 return *this; 00473 } 00474 00475 00476 //********************************************************************* 00477 // void AppendList(List &list) 00478 // Move contents of other list to the end of this list, and empty the 00479 // other list. 00480 // 00481 void List::AppendList(List &list) 00482 { 00483 // Never mind an empty list or ourselves. 00484 if (list.number == 0 || &list == this) 00485 return; 00486 00487 // Correct our pointers in head and tail. 00488 if (tail) 00489 { 00490 // Link in other list. 00491 tail->next = list.head; 00492 list.head->prev = tail; 00493 00494 // Update members for added contents. 00495 number += list.number; 00496 tail = list.tail; 00497 } 00498 else 00499 { 00500 head = list.head; 00501 tail = list.tail; 00502 number = list.number; 00503 } 00504 00505 // Clear others members to be an empty list. 00506 list.head = list.tail = 0; 00507 list.cursor.current = 0; 00508 list.cursor.current_index = -1; 00509 list.number = 0; 00510 }