|
tesseract 3.04.01
|
|
tesseract 3.04.01
|
00001 /********************************************************************** 00002 * File: elst2.h (Formerly elist2.h) 00003 * Description: Double linked embedded list module include file. 00004 * Author: Phil Cheatle 00005 * Created: Wed Jan 23 11:04:47 GMT 1991 00006 * 00007 * (C) Copyright 1991, Hewlett-Packard Ltd. 00008 ** Licensed under the Apache License, Version 2.0 (the "License"); 00009 ** you may not use this file except in compliance with the License. 00010 ** You may obtain a copy of the License at 00011 ** http://www.apache.org/licenses/LICENSE-2.0 00012 ** Unless required by applicable law or agreed to in writing, software 00013 ** distributed under the License is distributed on an "AS IS" BASIS, 00014 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00015 ** See the License for the specific language governing permissions and 00016 ** limitations under the License. 00017 * 00018 **********************************************************************/ 00019 00020 #ifndef ELST2_H 00021 #define ELST2_H 00022 00023 #include <stdio.h> 00024 #include "host.h" 00025 #include "serialis.h" 00026 #include "lsterr.h" 00027 00028 class ELIST2_ITERATOR; 00029 00030 /********************************************************************** 00031 DESIGN NOTE 00032 =========== 00033 00034 It would probably be possible to implement the ELIST2 classes as derived 00035 classes from ELIST. I haven't done this because: 00036 00037 a) I think it would be harder to understand the code 00038 (Though the problem with not inheriting is that changes to ELIST must be 00039 reflected in ELIST2 and vice versa) 00040 00041 b) Most of the code is inline so: 00042 i) The duplication in source does not affect the run time code size - the 00043 code is copied inline anyway! 00044 00045 ii) The compiler should have a bit less work to do! 00046 **********************************************************************/ 00047 00048 /********************************************************************** 00049 * CLASS - ELIST2_LINK 00050 * 00051 * Generic link class for doubly linked lists with embedded links 00052 * 00053 * Note: No destructor - elements are assumed to be destroyed EITHER after 00054 * they have been extracted from a list OR by the ELIST2 destructor which 00055 * walks the list. 00056 **********************************************************************/ 00057 00058 class DLLSYM ELIST2_LINK 00059 { 00060 friend class ELIST2_ITERATOR; 00061 friend class ELIST2; 00062 00063 ELIST2_LINK *prev; 00064 ELIST2_LINK *next; 00065 00066 public: 00067 ELIST2_LINK() { //constructor 00068 prev = next = NULL; 00069 } 00070 00071 ELIST2_LINK( //copy constructor 00072 const ELIST2_LINK &) { //don't copy link 00073 prev = next = NULL; 00074 } 00075 00076 void operator= ( //don't copy links 00077 const ELIST2_LINK &) { 00078 prev = next = NULL; 00079 } 00080 }; 00081 00082 /********************************************************************** 00083 * CLASS - ELIST2 00084 * 00085 * Generic list class for doubly linked lists with embedded links 00086 **********************************************************************/ 00087 00088 class DLLSYM ELIST2 00089 { 00090 friend class ELIST2_ITERATOR; 00091 00092 ELIST2_LINK *last; //End of list 00093 //(Points to head) 00094 ELIST2_LINK *First() { // return first 00095 return last ? last->next : NULL; 00096 } 00097 00098 public: 00099 ELIST2() { //constructor 00100 last = NULL; 00101 } 00102 00103 void internal_clear ( //destroy all links 00104 void (*zapper) (ELIST2_LINK *)); 00105 //ptr to zapper functn 00106 00107 bool empty() const { //is list empty? 00108 return !last; 00109 } 00110 00111 bool singleton() const { 00112 return last ? (last == last->next) : false; 00113 } 00114 00115 void shallow_copy( //dangerous!! 00116 ELIST2 *from_list) { //beware destructors!! 00117 last = from_list->last; 00118 } 00119 00120 //ptr to copier functn 00121 void internal_deep_copy (ELIST2_LINK * (*copier) (ELIST2_LINK *), 00122 const ELIST2 * list); //list being copied 00123 00124 void assign_to_sublist( //to this list 00125 ELIST2_ITERATOR *start_it, //from list start 00126 ELIST2_ITERATOR *end_it); //from list end 00127 00128 inT32 length() const; // # elements in list 00129 00130 void sort ( //sort elements 00131 int comparator ( //comparison routine 00132 const void *, const void *)); 00133 00134 // Assuming list has been sorted already, insert new_link to 00135 // keep the list sorted according to the same comparison function. 00136 // Comparison function is the same as used by sort, i.e. uses double 00137 // indirection. Time is O(1) to add to beginning or end. 00138 // Time is linear to add pre-sorted items to an empty list. 00139 void add_sorted(int comparator(const void*, const void*), 00140 ELIST2_LINK* new_link); 00141 00142 }; 00143 00144 /*********************************************************************** 00145 * CLASS - ELIST2_ITERATOR 00146 * 00147 * Generic iterator class for doubly linked lists with embedded links 00148 **********************************************************************/ 00149 00150 class DLLSYM ELIST2_ITERATOR 00151 { 00152 friend void ELIST2::assign_to_sublist(ELIST2_ITERATOR *, ELIST2_ITERATOR *); 00153 00154 ELIST2 *list; //List being iterated 00155 ELIST2_LINK *prev; //prev element 00156 ELIST2_LINK *current; //current element 00157 ELIST2_LINK *next; //next element 00158 BOOL8 ex_current_was_last; //current extracted 00159 //was end of list 00160 BOOL8 ex_current_was_cycle_pt; //current extracted 00161 //was cycle point 00162 ELIST2_LINK *cycle_pt; //point we are cycling 00163 //the list to. 00164 BOOL8 started_cycling; //Have we moved off 00165 //the start? 00166 00167 ELIST2_LINK *extract_sublist( //from this current... 00168 ELIST2_ITERATOR *other_it); //to other current 00169 00170 public: 00171 ELIST2_ITERATOR() { //constructor 00172 list = NULL; 00173 } //unassigned list 00174 00175 ELIST2_ITERATOR( //constructor 00176 ELIST2 *list_to_iterate); 00177 00178 void set_to_list( //change list 00179 ELIST2 *list_to_iterate); 00180 00181 void add_after_then_move( //add after current & 00182 ELIST2_LINK *new_link); //move to new 00183 00184 void add_after_stay_put( //add after current & 00185 ELIST2_LINK *new_link); //stay at current 00186 00187 void add_before_then_move( //add before current & 00188 ELIST2_LINK *new_link); //move to new 00189 00190 void add_before_stay_put( //add before current & 00191 ELIST2_LINK *new_link); //stay at current 00192 00193 void add_list_after( //add a list & 00194 ELIST2 *list_to_add); //stay at current 00195 00196 void add_list_before( //add a list & 00197 ELIST2 *list_to_add); //move to it 1st item 00198 00199 ELIST2_LINK *data() { //get current data 00200 #ifndef NDEBUG 00201 if (!current) 00202 NULL_DATA.error ("ELIST2_ITERATOR::data", ABORT, NULL); 00203 if (!list) 00204 NO_LIST.error ("ELIST2_ITERATOR::data", ABORT, NULL); 00205 #endif 00206 return current; 00207 } 00208 00209 ELIST2_LINK *data_relative( //get data + or - ... 00210 inT8 offset); //offset from current 00211 00212 ELIST2_LINK *forward(); //move to next element 00213 00214 ELIST2_LINK *backward(); //move to prev element 00215 00216 ELIST2_LINK *extract(); //remove from list 00217 00218 //go to start of list 00219 ELIST2_LINK *move_to_first(); 00220 00221 ELIST2_LINK *move_to_last(); //go to end of list 00222 00223 void mark_cycle_pt(); //remember current 00224 00225 BOOL8 empty() { //is list empty? 00226 #ifndef NDEBUG 00227 if (!list) 00228 NO_LIST.error ("ELIST2_ITERATOR::empty", ABORT, NULL); 00229 #endif 00230 return list->empty (); 00231 } 00232 00233 BOOL8 current_extracted() { //current extracted? 00234 return !current; 00235 } 00236 00237 BOOL8 at_first(); //Current is first? 00238 00239 BOOL8 at_last(); //Current is last? 00240 00241 BOOL8 cycled_list(); //Completed a cycle? 00242 00243 void add_to_end( //add at end & 00244 ELIST2_LINK *new_link); //don't move 00245 00246 void exchange( //positions of 2 links 00247 ELIST2_ITERATOR *other_it); //other iterator 00248 00249 inT32 length(); //# elements in list 00250 00251 void sort ( //sort elements 00252 int comparator ( //comparison routine 00253 const void *, const void *)); 00254 00255 }; 00256 00257 /*********************************************************************** 00258 * ELIST2_ITERATOR::set_to_list 00259 * 00260 * (Re-)initialise the iterator to point to the start of the list_to_iterate 00261 * over. 00262 **********************************************************************/ 00263 00264 inline void ELIST2_ITERATOR::set_to_list( //change list 00265 ELIST2 *list_to_iterate) { 00266 #ifndef NDEBUG 00267 if (!list_to_iterate) 00268 BAD_PARAMETER.error ("ELIST2_ITERATOR::set_to_list", ABORT, 00269 "list_to_iterate is NULL"); 00270 #endif 00271 00272 list = list_to_iterate; 00273 prev = list->last; 00274 current = list->First (); 00275 next = current ? current->next : NULL; 00276 cycle_pt = NULL; //await explicit set 00277 started_cycling = FALSE; 00278 ex_current_was_last = FALSE; 00279 ex_current_was_cycle_pt = FALSE; 00280 } 00281 00282 00283 /*********************************************************************** 00284 * ELIST2_ITERATOR::ELIST2_ITERATOR 00285 * 00286 * CONSTRUCTOR - set iterator to specified list; 00287 **********************************************************************/ 00288 00289 inline ELIST2_ITERATOR::ELIST2_ITERATOR(ELIST2 *list_to_iterate) { 00290 set_to_list(list_to_iterate); 00291 } 00292 00293 00294 /*********************************************************************** 00295 * ELIST2_ITERATOR::add_after_then_move 00296 * 00297 * Add a new element to the list after the current element and move the 00298 * iterator to the new element. 00299 **********************************************************************/ 00300 00301 inline void ELIST2_ITERATOR::add_after_then_move( // element to add 00302 ELIST2_LINK *new_element) { 00303 #ifndef NDEBUG 00304 if (!list) 00305 NO_LIST.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL); 00306 if (!new_element) 00307 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, 00308 "new_element is NULL"); 00309 if (new_element->next) 00310 STILL_LINKED.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL); 00311 #endif 00312 00313 if (list->empty ()) { 00314 new_element->next = new_element; 00315 new_element->prev = new_element; 00316 list->last = new_element; 00317 prev = next = new_element; 00318 } 00319 else { 00320 new_element->next = next; 00321 next->prev = new_element; 00322 00323 if (current) { //not extracted 00324 new_element->prev = current; 00325 current->next = new_element; 00326 prev = current; 00327 if (current == list->last) 00328 list->last = new_element; 00329 } 00330 else { //current extracted 00331 new_element->prev = prev; 00332 prev->next = new_element; 00333 if (ex_current_was_last) 00334 list->last = new_element; 00335 if (ex_current_was_cycle_pt) 00336 cycle_pt = new_element; 00337 } 00338 } 00339 current = new_element; 00340 } 00341 00342 00343 /*********************************************************************** 00344 * ELIST2_ITERATOR::add_after_stay_put 00345 * 00346 * Add a new element to the list after the current element but do not move 00347 * the iterator to the new element. 00348 **********************************************************************/ 00349 00350 inline void ELIST2_ITERATOR::add_after_stay_put( // element to add 00351 ELIST2_LINK *new_element) { 00352 #ifndef NDEBUG 00353 if (!list) 00354 NO_LIST.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL); 00355 if (!new_element) 00356 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, 00357 "new_element is NULL"); 00358 if (new_element->next) 00359 STILL_LINKED.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL); 00360 #endif 00361 00362 if (list->empty ()) { 00363 new_element->next = new_element; 00364 new_element->prev = new_element; 00365 list->last = new_element; 00366 prev = next = new_element; 00367 ex_current_was_last = FALSE; 00368 current = NULL; 00369 } 00370 else { 00371 new_element->next = next; 00372 next->prev = new_element; 00373 00374 if (current) { //not extracted 00375 new_element->prev = current; 00376 current->next = new_element; 00377 if (prev == current) 00378 prev = new_element; 00379 if (current == list->last) 00380 list->last = new_element; 00381 } 00382 else { //current extracted 00383 new_element->prev = prev; 00384 prev->next = new_element; 00385 if (ex_current_was_last) { 00386 list->last = new_element; 00387 ex_current_was_last = FALSE; 00388 } 00389 } 00390 next = new_element; 00391 } 00392 } 00393 00394 00395 /*********************************************************************** 00396 * ELIST2_ITERATOR::add_before_then_move 00397 * 00398 * Add a new element to the list before the current element and move the 00399 * iterator to the new element. 00400 **********************************************************************/ 00401 00402 inline void ELIST2_ITERATOR::add_before_then_move( // element to add 00403 ELIST2_LINK *new_element) { 00404 #ifndef NDEBUG 00405 if (!list) 00406 NO_LIST.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL); 00407 if (!new_element) 00408 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, 00409 "new_element is NULL"); 00410 if (new_element->next) 00411 STILL_LINKED.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL); 00412 #endif 00413 00414 if (list->empty ()) { 00415 new_element->next = new_element; 00416 new_element->prev = new_element; 00417 list->last = new_element; 00418 prev = next = new_element; 00419 } 00420 else { 00421 prev->next = new_element; 00422 new_element->prev = prev; 00423 00424 if (current) { //not extracted 00425 new_element->next = current; 00426 current->prev = new_element; 00427 next = current; 00428 } 00429 else { //current extracted 00430 new_element->next = next; 00431 next->prev = new_element; 00432 if (ex_current_was_last) 00433 list->last = new_element; 00434 if (ex_current_was_cycle_pt) 00435 cycle_pt = new_element; 00436 } 00437 } 00438 current = new_element; 00439 } 00440 00441 00442 /*********************************************************************** 00443 * ELIST2_ITERATOR::add_before_stay_put 00444 * 00445 * Add a new element to the list before the current element but don't move the 00446 * iterator to the new element. 00447 **********************************************************************/ 00448 00449 inline void ELIST2_ITERATOR::add_before_stay_put( // element to add 00450 ELIST2_LINK *new_element) { 00451 #ifndef NDEBUG 00452 if (!list) 00453 NO_LIST.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL); 00454 if (!new_element) 00455 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, 00456 "new_element is NULL"); 00457 if (new_element->next) 00458 STILL_LINKED.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL); 00459 #endif 00460 00461 if (list->empty ()) { 00462 new_element->next = new_element; 00463 new_element->prev = new_element; 00464 list->last = new_element; 00465 prev = next = new_element; 00466 ex_current_was_last = TRUE; 00467 current = NULL; 00468 } 00469 else { 00470 prev->next = new_element; 00471 new_element->prev = prev; 00472 00473 if (current) { //not extracted 00474 new_element->next = current; 00475 current->prev = new_element; 00476 if (next == current) 00477 next = new_element; 00478 } 00479 else { //current extracted 00480 new_element->next = next; 00481 next->prev = new_element; 00482 if (ex_current_was_last) 00483 list->last = new_element; 00484 } 00485 prev = new_element; 00486 } 00487 } 00488 00489 00490 /*********************************************************************** 00491 * ELIST2_ITERATOR::add_list_after 00492 * 00493 * Insert another list to this list after the current element but don't move the 00494 * iterator. 00495 **********************************************************************/ 00496 00497 inline void ELIST2_ITERATOR::add_list_after(ELIST2 *list_to_add) { 00498 #ifndef NDEBUG 00499 if (!list) 00500 NO_LIST.error ("ELIST2_ITERATOR::add_list_after", ABORT, NULL); 00501 if (!list_to_add) 00502 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_list_after", ABORT, 00503 "list_to_add is NULL"); 00504 #endif 00505 00506 if (!list_to_add->empty ()) { 00507 if (list->empty ()) { 00508 list->last = list_to_add->last; 00509 prev = list->last; 00510 next = list->First (); 00511 ex_current_was_last = TRUE; 00512 current = NULL; 00513 } 00514 else { 00515 if (current) { //not extracted 00516 current->next = list_to_add->First (); 00517 current->next->prev = current; 00518 if (current == list->last) 00519 list->last = list_to_add->last; 00520 list_to_add->last->next = next; 00521 next->prev = list_to_add->last; 00522 next = current->next; 00523 } 00524 else { //current extracted 00525 prev->next = list_to_add->First (); 00526 prev->next->prev = prev; 00527 if (ex_current_was_last) { 00528 list->last = list_to_add->last; 00529 ex_current_was_last = FALSE; 00530 } 00531 list_to_add->last->next = next; 00532 next->prev = list_to_add->last; 00533 next = prev->next; 00534 } 00535 } 00536 list_to_add->last = NULL; 00537 } 00538 } 00539 00540 00541 /*********************************************************************** 00542 * ELIST2_ITERATOR::add_list_before 00543 * 00544 * Insert another list to this list before the current element. Move the 00545 * iterator to the start of the inserted elements 00546 * iterator. 00547 **********************************************************************/ 00548 00549 inline void ELIST2_ITERATOR::add_list_before(ELIST2 *list_to_add) { 00550 #ifndef NDEBUG 00551 if (!list) 00552 NO_LIST.error ("ELIST2_ITERATOR::add_list_before", ABORT, NULL); 00553 if (!list_to_add) 00554 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_list_before", ABORT, 00555 "list_to_add is NULL"); 00556 #endif 00557 00558 if (!list_to_add->empty ()) { 00559 if (list->empty ()) { 00560 list->last = list_to_add->last; 00561 prev = list->last; 00562 current = list->First (); 00563 next = current->next; 00564 ex_current_was_last = FALSE; 00565 } 00566 else { 00567 prev->next = list_to_add->First (); 00568 prev->next->prev = prev; 00569 00570 if (current) { //not extracted 00571 list_to_add->last->next = current; 00572 current->prev = list_to_add->last; 00573 } 00574 else { //current extracted 00575 list_to_add->last->next = next; 00576 next->prev = list_to_add->last; 00577 if (ex_current_was_last) 00578 list->last = list_to_add->last; 00579 if (ex_current_was_cycle_pt) 00580 cycle_pt = prev->next; 00581 } 00582 current = prev->next; 00583 next = current->next; 00584 } 00585 list_to_add->last = NULL; 00586 } 00587 } 00588 00589 00590 /*********************************************************************** 00591 * ELIST2_ITERATOR::extract 00592 * 00593 * Do extraction by removing current from the list, returning it to the 00594 * caller, but NOT updating the iterator. (So that any calling loop can do 00595 * this.) The iterator's current points to NULL. If the extracted element 00596 * is to be deleted, this is the callers responsibility. 00597 **********************************************************************/ 00598 00599 inline ELIST2_LINK *ELIST2_ITERATOR::extract() { 00600 ELIST2_LINK *extracted_link; 00601 00602 #ifndef NDEBUG 00603 if (!list) 00604 NO_LIST.error ("ELIST2_ITERATOR::extract", ABORT, NULL); 00605 if (!current) //list empty or 00606 //element extracted 00607 NULL_CURRENT.error ("ELIST2_ITERATOR::extract", 00608 ABORT, NULL); 00609 #endif 00610 00611 if (list->singleton()) { 00612 // Special case where we do need to change the iterator. 00613 prev = next = list->last = NULL; 00614 } else { 00615 prev->next = next; //remove from list 00616 next->prev = prev; 00617 00618 if (current == list->last) { 00619 list->last = prev; 00620 ex_current_was_last = TRUE; 00621 } else { 00622 ex_current_was_last = FALSE; 00623 } 00624 } 00625 // Always set ex_current_was_cycle_pt so an add/forward will work in a loop. 00626 ex_current_was_cycle_pt = (current == cycle_pt) ? TRUE : FALSE; 00627 extracted_link = current; 00628 extracted_link->next = NULL; //for safety 00629 extracted_link->prev = NULL; //for safety 00630 current = NULL; 00631 return extracted_link; 00632 } 00633 00634 00635 /*********************************************************************** 00636 * ELIST2_ITERATOR::move_to_first() 00637 * 00638 * Move current so that it is set to the start of the list. 00639 * Return data just in case anyone wants it. 00640 **********************************************************************/ 00641 00642 inline ELIST2_LINK *ELIST2_ITERATOR::move_to_first() { 00643 #ifndef NDEBUG 00644 if (!list) 00645 NO_LIST.error ("ELIST2_ITERATOR::move_to_first", ABORT, NULL); 00646 #endif 00647 00648 current = list->First (); 00649 prev = list->last; 00650 next = current ? current->next : NULL; 00651 return current; 00652 } 00653 00654 00655 /*********************************************************************** 00656 * ELIST2_ITERATOR::move_to_last() 00657 * 00658 * Move current so that it is set to the end of the list. 00659 * Return data just in case anyone wants it. 00660 **********************************************************************/ 00661 00662 inline ELIST2_LINK *ELIST2_ITERATOR::move_to_last() { 00663 #ifndef NDEBUG 00664 if (!list) 00665 NO_LIST.error ("ELIST2_ITERATOR::move_to_last", ABORT, NULL); 00666 #endif 00667 00668 current = list->last; 00669 prev = current ? current->prev : NULL; 00670 next = current ? current->next : NULL; 00671 return current; 00672 } 00673 00674 00675 /*********************************************************************** 00676 * ELIST2_ITERATOR::mark_cycle_pt() 00677 * 00678 * Remember the current location so that we can tell whether we've returned 00679 * to this point later. 00680 * 00681 * If the current point is deleted either now, or in the future, the cycle 00682 * point will be set to the next item which is set to current. This could be 00683 * by a forward, add_after_then_move or add_after_then_move. 00684 **********************************************************************/ 00685 00686 inline void ELIST2_ITERATOR::mark_cycle_pt() { 00687 #ifndef NDEBUG 00688 if (!list) 00689 NO_LIST.error ("ELIST2_ITERATOR::mark_cycle_pt", ABORT, NULL); 00690 #endif 00691 00692 if (current) 00693 cycle_pt = current; 00694 else 00695 ex_current_was_cycle_pt = TRUE; 00696 started_cycling = FALSE; 00697 } 00698 00699 00700 /*********************************************************************** 00701 * ELIST2_ITERATOR::at_first() 00702 * 00703 * Are we at the start of the list? 00704 * 00705 **********************************************************************/ 00706 00707 inline BOOL8 ELIST2_ITERATOR::at_first() { 00708 #ifndef NDEBUG 00709 if (!list) 00710 NO_LIST.error ("ELIST2_ITERATOR::at_first", ABORT, NULL); 00711 #endif 00712 00713 //we're at a deleted 00714 return ((list->empty ()) || (current == list->First ()) || ((current == NULL) && 00715 (prev == list->last) && //NON-last pt between 00716 !ex_current_was_last)); //first and last 00717 } 00718 00719 00720 /*********************************************************************** 00721 * ELIST2_ITERATOR::at_last() 00722 * 00723 * Are we at the end of the list? 00724 * 00725 **********************************************************************/ 00726 00727 inline BOOL8 ELIST2_ITERATOR::at_last() { 00728 #ifndef NDEBUG 00729 if (!list) 00730 NO_LIST.error ("ELIST2_ITERATOR::at_last", ABORT, NULL); 00731 #endif 00732 00733 //we're at a deleted 00734 return ((list->empty ()) || (current == list->last) || ((current == NULL) && 00735 (prev == list->last) && //last point between 00736 ex_current_was_last)); //first and last 00737 } 00738 00739 00740 /*********************************************************************** 00741 * ELIST2_ITERATOR::cycled_list() 00742 * 00743 * Have we returned to the cycle_pt since it was set? 00744 * 00745 **********************************************************************/ 00746 00747 inline BOOL8 ELIST2_ITERATOR::cycled_list() { 00748 #ifndef NDEBUG 00749 if (!list) 00750 NO_LIST.error ("ELIST2_ITERATOR::cycled_list", ABORT, NULL); 00751 #endif 00752 00753 return ((list->empty ()) || ((current == cycle_pt) && started_cycling)); 00754 00755 } 00756 00757 00758 /*********************************************************************** 00759 * ELIST2_ITERATOR::length() 00760 * 00761 * Return the length of the list 00762 * 00763 **********************************************************************/ 00764 00765 inline inT32 ELIST2_ITERATOR::length() { 00766 #ifndef NDEBUG 00767 if (!list) 00768 NO_LIST.error ("ELIST2_ITERATOR::length", ABORT, NULL); 00769 #endif 00770 00771 return list->length (); 00772 } 00773 00774 00775 /*********************************************************************** 00776 * ELIST2_ITERATOR::sort() 00777 * 00778 * Sort the elements of the list, then reposition at the start. 00779 * 00780 **********************************************************************/ 00781 00782 inline void 00783 ELIST2_ITERATOR::sort ( //sort elements 00784 int comparator ( //comparison routine 00785 const void *, const void *)) { 00786 #ifndef NDEBUG 00787 if (!list) 00788 NO_LIST.error ("ELIST2_ITERATOR::sort", ABORT, NULL); 00789 #endif 00790 00791 list->sort (comparator); 00792 move_to_first(); 00793 } 00794 00795 00796 /*********************************************************************** 00797 * ELIST2_ITERATOR::add_to_end 00798 * 00799 * Add a new element to the end of the list without moving the iterator. 00800 * This is provided because a single linked list cannot move to the last as 00801 * the iterator couldn't set its prev pointer. Adding to the end is 00802 * essential for implementing 00803 queues. 00804 **********************************************************************/ 00805 00806 inline void ELIST2_ITERATOR::add_to_end( // element to add 00807 ELIST2_LINK *new_element) { 00808 #ifndef NDEBUG 00809 if (!list) 00810 NO_LIST.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL); 00811 if (!new_element) 00812 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_to_end", ABORT, 00813 "new_element is NULL"); 00814 if (new_element->next) 00815 STILL_LINKED.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL); 00816 #endif 00817 00818 if (this->at_last ()) { 00819 this->add_after_stay_put (new_element); 00820 } 00821 else { 00822 if (this->at_first ()) { 00823 this->add_before_stay_put (new_element); 00824 list->last = new_element; 00825 } 00826 else { //Iteratr is elsewhere 00827 new_element->next = list->last->next; 00828 new_element->prev = list->last; 00829 list->last->next->prev = new_element; 00830 list->last->next = new_element; 00831 list->last = new_element; 00832 } 00833 } 00834 } 00835 00836 00837 /*********************************************************************** 00838 QUOTE_IT MACRO DEFINITION 00839 =========================== 00840 Replace <parm> with "<parm>". <parm> may be an arbitrary number of tokens 00841 ***********************************************************************/ 00842 00843 #define QUOTE_IT( parm ) #parm 00844 00845 /*********************************************************************** 00846 ELIST2IZE( CLASSNAME ) MACRO DEFINITION 00847 ====================================== 00848 00849 CLASSNAME is assumed to be the name of a class which has a baseclass of 00850 ELIST2_LINK. 00851 00852 NOTE: Because we don't use virtual functions in the list code, the list code 00853 will NOT work correctly for classes derived from this. 00854 00855 The macro generates: 00856 - An element deletion function: CLASSNAME##_zapper 00857 - An E_LIST2 subclass: CLASSNAME##_LIST 00858 - An E_LIST2_ITERATOR subclass: 00859 CLASSNAME##_IT 00860 00861 NOTE: Generated names are DELIBERATELY designed to clash with those for 00862 ELISTIZE but NOT with those for CLISTIZE and CLIST2IZE 00863 00864 Two macros are provided: ELIST2IZE and ELIST2IZEH 00865 The ...IZEH macros just define the class names for use in .h files 00866 The ...IZE macros define the code use in .c files 00867 ***********************************************************************/ 00868 00869 /*********************************************************************** 00870 ELIST2IZEH( CLASSNAME ) MACRO 00871 00872 ELIST2IZEH is a concatenation of 3 fragments ELIST2IZEH_A, ELIST2IZEH_B and 00873 ELIST2IZEH_C. 00874 ***********************************************************************/ 00875 00876 #define ELIST2IZEH_A( CLASSNAME ) \ 00877 \ 00878 extern DLLSYM void CLASSNAME##_zapper( /*delete a link*/ \ 00879 ELIST2_LINK* link); /*link to delete*/ 00880 00881 #define ELIST2IZEH_B( CLASSNAME ) \ 00882 \ 00883 /*********************************************************************** \ 00884 * CLASS - CLASSNAME##_LIST \ 00885 * \ 00886 * List class for class CLASSNAME \ 00887 * \ 00888 **********************************************************************/ \ 00889 \ 00890 class DLLSYM CLASSNAME##_LIST : public ELIST2 \ 00891 { \ 00892 public: \ 00893 CLASSNAME##_LIST():ELIST2() {} \ 00894 /* constructor */ \ 00895 \ 00896 CLASSNAME##_LIST( /* don't construct */ \ 00897 const CLASSNAME##_LIST&) /*by initial assign*/\ 00898 { DONT_CONSTRUCT_LIST_BY_COPY.error( QUOTE_IT( CLASSNAME##_LIST ), \ 00899 ABORT, NULL ); } \ 00900 \ 00901 void clear() /* delete elements */\ 00902 { ELIST2::internal_clear( &CLASSNAME##_zapper ); } \ 00903 \ 00904 ~CLASSNAME##_LIST() /* destructor */ \ 00905 { clear(); } \ 00906 \ 00907 /* Become a deep copy of src_list*/ \ 00908 void deep_copy(const CLASSNAME##_LIST* src_list, \ 00909 CLASSNAME* (*copier)(const CLASSNAME*)); \ 00910 \ 00911 void operator=( /* prevent assign */ \ 00912 const CLASSNAME##_LIST&) \ 00913 { DONT_ASSIGN_LISTS.error( QUOTE_IT( CLASSNAME##_LIST ), \ 00914 ABORT, NULL ); } 00915 00916 #define ELIST2IZEH_C( CLASSNAME ) \ 00917 }; \ 00918 \ 00919 \ 00920 \ 00921 /*********************************************************************** \ 00922 * CLASS - CLASSNAME##_IT \ 00923 * \ 00924 * Iterator class for class CLASSNAME##_LIST \ 00925 * \ 00926 * Note: We don't need to coerce pointers to member functions input \ 00927 * parameters as these are automatically converted to the type of the base \ 00928 * type. ("A ptr to a class may be converted to a pointer to a public base \ 00929 * class of that class") \ 00930 **********************************************************************/ \ 00931 \ 00932 class DLLSYM CLASSNAME##_IT : public ELIST2_ITERATOR \ 00933 { \ 00934 public: \ 00935 CLASSNAME##_IT():ELIST2_ITERATOR(){} \ 00936 \ 00937 CLASSNAME##_IT( \ 00938 CLASSNAME##_LIST* list):ELIST2_ITERATOR(list){} \ 00939 \ 00940 CLASSNAME* data() \ 00941 { return (CLASSNAME*) ELIST2_ITERATOR::data(); } \ 00942 \ 00943 CLASSNAME* data_relative( \ 00944 inT8 offset) \ 00945 { return (CLASSNAME*) ELIST2_ITERATOR::data_relative( offset ); } \ 00946 \ 00947 CLASSNAME* forward() \ 00948 { return (CLASSNAME*) ELIST2_ITERATOR::forward(); } \ 00949 \ 00950 CLASSNAME* backward() \ 00951 { return (CLASSNAME*) ELIST2_ITERATOR::backward(); } \ 00952 \ 00953 CLASSNAME* extract() \ 00954 { return (CLASSNAME*) ELIST2_ITERATOR::extract(); } \ 00955 \ 00956 CLASSNAME* move_to_first() \ 00957 { return (CLASSNAME*) ELIST2_ITERATOR::move_to_first(); } \ 00958 \ 00959 CLASSNAME* move_to_last() \ 00960 { return (CLASSNAME*) ELIST2_ITERATOR::move_to_last(); } \ 00961 }; 00962 00963 #define ELIST2IZEH( CLASSNAME ) \ 00964 \ 00965 ELIST2IZEH_A( CLASSNAME ) \ 00966 \ 00967 ELIST2IZEH_B( CLASSNAME ) \ 00968 \ 00969 ELIST2IZEH_C( CLASSNAME ) 00970 00971 00972 /*********************************************************************** 00973 ELIST2IZE( CLASSNAME ) MACRO 00974 ***********************************************************************/ 00975 00976 #define ELIST2IZE( CLASSNAME ) \ 00977 \ 00978 /*********************************************************************** \ 00979 * CLASSNAME##_zapper \ 00980 * \ 00981 * A function which can delete a CLASSNAME element. This is passed to the \ 00982 * generic clear list member function so that when a list is cleared the \ 00983 * elements on the list are properly destroyed from the base class, even \ 00984 * though we don't use a virtual destructor function. \ 00985 **********************************************************************/ \ 00986 \ 00987 DLLSYM void CLASSNAME##_zapper( /*delete a link*/ \ 00988 ELIST2_LINK* link) /*link to delete*/ \ 00989 { \ 00990 delete (CLASSNAME *) link; \ 00991 } \ 00992 \ 00993 /* Become a deep copy of src_list*/ \ 00994 void CLASSNAME##_LIST::deep_copy(const CLASSNAME##_LIST* src_list, \ 00995 CLASSNAME* (*copier)(const CLASSNAME*)) { \ 00996 \ 00997 CLASSNAME##_IT from_it(const_cast<CLASSNAME##_LIST*>(src_list)); \ 00998 CLASSNAME##_IT to_it(this); \ 00999 \ 01000 for (from_it.mark_cycle_pt(); !from_it.cycled_list(); from_it.forward()) \ 01001 to_it.add_after_then_move((*copier)(from_it.data())); \ 01002 } 01003 01004 #endif
1.7.3 
