|
Tesseract
3.02
|
|
Tesseract
3.02
|
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 &) { //dont copy link 00073 prev = next = NULL; 00074 } 00075 00076 void operator= ( //dont 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 // Comparision 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); //dont 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 (!this) 00268 NULL_OBJECT.error ("ELIST2_ITERATOR::set_to_list", ABORT, NULL); 00269 if (!list_to_iterate) 00270 BAD_PARAMETER.error ("ELIST2_ITERATOR::set_to_list", ABORT, 00271 "list_to_iterate is NULL"); 00272 #endif 00273 00274 list = list_to_iterate; 00275 prev = list->last; 00276 current = list->First (); 00277 next = current ? current->next : NULL; 00278 cycle_pt = NULL; //await explicit set 00279 started_cycling = FALSE; 00280 ex_current_was_last = FALSE; 00281 ex_current_was_cycle_pt = FALSE; 00282 } 00283 00284 00285 /*********************************************************************** 00286 * ELIST2_ITERATOR::ELIST2_ITERATOR 00287 * 00288 * CONSTRUCTOR - set iterator to specified list; 00289 **********************************************************************/ 00290 00291 inline ELIST2_ITERATOR::ELIST2_ITERATOR(ELIST2 *list_to_iterate) { 00292 set_to_list(list_to_iterate); 00293 } 00294 00295 00296 /*********************************************************************** 00297 * ELIST2_ITERATOR::add_after_then_move 00298 * 00299 * Add a new element to the list after the current element and move the 00300 * iterator to the new element. 00301 **********************************************************************/ 00302 00303 inline void ELIST2_ITERATOR::add_after_then_move( // element to add 00304 ELIST2_LINK *new_element) { 00305 #ifndef NDEBUG 00306 if (!this) 00307 NULL_OBJECT.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL); 00308 if (!list) 00309 NO_LIST.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL); 00310 if (!new_element) 00311 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, 00312 "new_element is NULL"); 00313 if (new_element->next) 00314 STILL_LINKED.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL); 00315 #endif 00316 00317 if (list->empty ()) { 00318 new_element->next = new_element; 00319 new_element->prev = new_element; 00320 list->last = new_element; 00321 prev = next = new_element; 00322 } 00323 else { 00324 new_element->next = next; 00325 next->prev = new_element; 00326 00327 if (current) { //not extracted 00328 new_element->prev = current; 00329 current->next = new_element; 00330 prev = current; 00331 if (current == list->last) 00332 list->last = new_element; 00333 } 00334 else { //current extracted 00335 new_element->prev = prev; 00336 prev->next = new_element; 00337 if (ex_current_was_last) 00338 list->last = new_element; 00339 if (ex_current_was_cycle_pt) 00340 cycle_pt = new_element; 00341 } 00342 } 00343 current = new_element; 00344 } 00345 00346 00347 /*********************************************************************** 00348 * ELIST2_ITERATOR::add_after_stay_put 00349 * 00350 * Add a new element to the list after the current element but do not move 00351 * the iterator to the new element. 00352 **********************************************************************/ 00353 00354 inline void ELIST2_ITERATOR::add_after_stay_put( // element to add 00355 ELIST2_LINK *new_element) { 00356 #ifndef NDEBUG 00357 if (!this) 00358 NULL_OBJECT.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL); 00359 if (!list) 00360 NO_LIST.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL); 00361 if (!new_element) 00362 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, 00363 "new_element is NULL"); 00364 if (new_element->next) 00365 STILL_LINKED.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL); 00366 #endif 00367 00368 if (list->empty ()) { 00369 new_element->next = new_element; 00370 new_element->prev = new_element; 00371 list->last = new_element; 00372 prev = next = new_element; 00373 ex_current_was_last = FALSE; 00374 current = NULL; 00375 } 00376 else { 00377 new_element->next = next; 00378 next->prev = new_element; 00379 00380 if (current) { //not extracted 00381 new_element->prev = current; 00382 current->next = new_element; 00383 if (prev == current) 00384 prev = new_element; 00385 if (current == list->last) 00386 list->last = new_element; 00387 } 00388 else { //current extracted 00389 new_element->prev = prev; 00390 prev->next = new_element; 00391 if (ex_current_was_last) { 00392 list->last = new_element; 00393 ex_current_was_last = FALSE; 00394 } 00395 } 00396 next = new_element; 00397 } 00398 } 00399 00400 00401 /*********************************************************************** 00402 * ELIST2_ITERATOR::add_before_then_move 00403 * 00404 * Add a new element to the list before the current element and move the 00405 * iterator to the new element. 00406 **********************************************************************/ 00407 00408 inline void ELIST2_ITERATOR::add_before_then_move( // element to add 00409 ELIST2_LINK *new_element) { 00410 #ifndef NDEBUG 00411 if (!this) 00412 NULL_OBJECT.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL); 00413 if (!list) 00414 NO_LIST.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL); 00415 if (!new_element) 00416 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, 00417 "new_element is NULL"); 00418 if (new_element->next) 00419 STILL_LINKED.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL); 00420 #endif 00421 00422 if (list->empty ()) { 00423 new_element->next = new_element; 00424 new_element->prev = new_element; 00425 list->last = new_element; 00426 prev = next = new_element; 00427 } 00428 else { 00429 prev->next = new_element; 00430 new_element->prev = prev; 00431 00432 if (current) { //not extracted 00433 new_element->next = current; 00434 current->prev = new_element; 00435 next = current; 00436 } 00437 else { //current extracted 00438 new_element->next = next; 00439 next->prev = new_element; 00440 if (ex_current_was_last) 00441 list->last = new_element; 00442 if (ex_current_was_cycle_pt) 00443 cycle_pt = new_element; 00444 } 00445 } 00446 current = new_element; 00447 } 00448 00449 00450 /*********************************************************************** 00451 * ELIST2_ITERATOR::add_before_stay_put 00452 * 00453 * Add a new element to the list before the current element but dont move the 00454 * iterator to the new element. 00455 **********************************************************************/ 00456 00457 inline void ELIST2_ITERATOR::add_before_stay_put( // element to add 00458 ELIST2_LINK *new_element) { 00459 #ifndef NDEBUG 00460 if (!this) 00461 NULL_OBJECT.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL); 00462 if (!list) 00463 NO_LIST.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL); 00464 if (!new_element) 00465 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, 00466 "new_element is NULL"); 00467 if (new_element->next) 00468 STILL_LINKED.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL); 00469 #endif 00470 00471 if (list->empty ()) { 00472 new_element->next = new_element; 00473 new_element->prev = new_element; 00474 list->last = new_element; 00475 prev = next = new_element; 00476 ex_current_was_last = TRUE; 00477 current = NULL; 00478 } 00479 else { 00480 prev->next = new_element; 00481 new_element->prev = prev; 00482 00483 if (current) { //not extracted 00484 new_element->next = current; 00485 current->prev = new_element; 00486 if (next == current) 00487 next = new_element; 00488 } 00489 else { //current extracted 00490 new_element->next = next; 00491 next->prev = new_element; 00492 if (ex_current_was_last) 00493 list->last = new_element; 00494 } 00495 prev = new_element; 00496 } 00497 } 00498 00499 00500 /*********************************************************************** 00501 * ELIST2_ITERATOR::add_list_after 00502 * 00503 * Insert another list to this list after the current element but dont move the 00504 * iterator. 00505 **********************************************************************/ 00506 00507 inline void ELIST2_ITERATOR::add_list_after(ELIST2 *list_to_add) { 00508 #ifndef NDEBUG 00509 if (!this) 00510 NULL_OBJECT.error ("ELIST2_ITERATOR::add_list_after", ABORT, NULL); 00511 if (!list) 00512 NO_LIST.error ("ELIST2_ITERATOR::add_list_after", ABORT, NULL); 00513 if (!list_to_add) 00514 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_list_after", ABORT, 00515 "list_to_add is NULL"); 00516 #endif 00517 00518 if (!list_to_add->empty ()) { 00519 if (list->empty ()) { 00520 list->last = list_to_add->last; 00521 prev = list->last; 00522 next = list->First (); 00523 ex_current_was_last = TRUE; 00524 current = NULL; 00525 } 00526 else { 00527 if (current) { //not extracted 00528 current->next = list_to_add->First (); 00529 current->next->prev = current; 00530 if (current == list->last) 00531 list->last = list_to_add->last; 00532 list_to_add->last->next = next; 00533 next->prev = list_to_add->last; 00534 next = current->next; 00535 } 00536 else { //current extracted 00537 prev->next = list_to_add->First (); 00538 prev->next->prev = prev; 00539 if (ex_current_was_last) { 00540 list->last = list_to_add->last; 00541 ex_current_was_last = FALSE; 00542 } 00543 list_to_add->last->next = next; 00544 next->prev = list_to_add->last; 00545 next = prev->next; 00546 } 00547 } 00548 list_to_add->last = NULL; 00549 } 00550 } 00551 00552 00553 /*********************************************************************** 00554 * ELIST2_ITERATOR::add_list_before 00555 * 00556 * Insert another list to this list before the current element. Move the 00557 * iterator to the start of the inserted elements 00558 * iterator. 00559 **********************************************************************/ 00560 00561 inline void ELIST2_ITERATOR::add_list_before(ELIST2 *list_to_add) { 00562 #ifndef NDEBUG 00563 if (!this) 00564 NULL_OBJECT.error ("ELIST2_ITERATOR::add_list_before", ABORT, NULL); 00565 if (!list) 00566 NO_LIST.error ("ELIST2_ITERATOR::add_list_before", ABORT, NULL); 00567 if (!list_to_add) 00568 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_list_before", ABORT, 00569 "list_to_add is NULL"); 00570 #endif 00571 00572 if (!list_to_add->empty ()) { 00573 if (list->empty ()) { 00574 list->last = list_to_add->last; 00575 prev = list->last; 00576 current = list->First (); 00577 next = current->next; 00578 ex_current_was_last = FALSE; 00579 } 00580 else { 00581 prev->next = list_to_add->First (); 00582 prev->next->prev = prev; 00583 00584 if (current) { //not extracted 00585 list_to_add->last->next = current; 00586 current->prev = list_to_add->last; 00587 } 00588 else { //current extracted 00589 list_to_add->last->next = next; 00590 next->prev = list_to_add->last; 00591 if (ex_current_was_last) 00592 list->last = list_to_add->last; 00593 if (ex_current_was_cycle_pt) 00594 cycle_pt = prev->next; 00595 } 00596 current = prev->next; 00597 next = current->next; 00598 } 00599 list_to_add->last = NULL; 00600 } 00601 } 00602 00603 00604 /*********************************************************************** 00605 * ELIST2_ITERATOR::extract 00606 * 00607 * Do extraction by removing current from the list, returning it to the 00608 * caller, but NOT updating the iterator. (So that any calling loop can do 00609 * this.) The iterator's current points to NULL. If the extracted element 00610 * is to be deleted, this is the callers responsibility. 00611 **********************************************************************/ 00612 00613 inline ELIST2_LINK *ELIST2_ITERATOR::extract() { 00614 ELIST2_LINK *extracted_link; 00615 00616 #ifndef NDEBUG 00617 if (!this) 00618 NULL_OBJECT.error ("ELIST2_ITERATOR::extract", ABORT, NULL); 00619 if (!list) 00620 NO_LIST.error ("ELIST2_ITERATOR::extract", ABORT, NULL); 00621 if (!current) //list empty or 00622 //element extracted 00623 NULL_CURRENT.error ("ELIST2_ITERATOR::extract", 00624 ABORT, NULL); 00625 #endif 00626 00627 if (list->singleton()) { 00628 // Special case where we do need to change the iterator. 00629 prev = next = list->last = NULL; 00630 } else { 00631 prev->next = next; //remove from list 00632 next->prev = prev; 00633 00634 if (current == list->last) { 00635 list->last = prev; 00636 ex_current_was_last = TRUE; 00637 } else { 00638 ex_current_was_last = FALSE; 00639 } 00640 } 00641 // Always set ex_current_was_cycle_pt so an add/forward will work in a loop. 00642 ex_current_was_cycle_pt = (current == cycle_pt) ? TRUE : FALSE; 00643 extracted_link = current; 00644 extracted_link->next = NULL; //for safety 00645 extracted_link->prev = NULL; //for safety 00646 current = NULL; 00647 return extracted_link; 00648 } 00649 00650 00651 /*********************************************************************** 00652 * ELIST2_ITERATOR::move_to_first() 00653 * 00654 * Move current so that it is set to the start of the list. 00655 * Return data just in case anyone wants it. 00656 **********************************************************************/ 00657 00658 inline ELIST2_LINK *ELIST2_ITERATOR::move_to_first() { 00659 #ifndef NDEBUG 00660 if (!this) 00661 NULL_OBJECT.error ("ELIST2_ITERATOR::move_to_first", ABORT, NULL); 00662 if (!list) 00663 NO_LIST.error ("ELIST2_ITERATOR::move_to_first", ABORT, NULL); 00664 #endif 00665 00666 current = list->First (); 00667 prev = list->last; 00668 next = current ? current->next : NULL; 00669 return current; 00670 } 00671 00672 00673 /*********************************************************************** 00674 * ELIST2_ITERATOR::move_to_last() 00675 * 00676 * Move current so that it is set to the end of the list. 00677 * Return data just in case anyone wants it. 00678 **********************************************************************/ 00679 00680 inline ELIST2_LINK *ELIST2_ITERATOR::move_to_last() { 00681 #ifndef NDEBUG 00682 if (!this) 00683 NULL_OBJECT.error ("ELIST2_ITERATOR::move_to_last", ABORT, NULL); 00684 if (!list) 00685 NO_LIST.error ("ELIST2_ITERATOR::move_to_last", ABORT, NULL); 00686 #endif 00687 00688 current = list->last; 00689 prev = current ? current->prev : NULL; 00690 next = current ? current->next : NULL; 00691 return current; 00692 } 00693 00694 00695 /*********************************************************************** 00696 * ELIST2_ITERATOR::mark_cycle_pt() 00697 * 00698 * Remember the current location so that we can tell whether we've returned 00699 * to this point later. 00700 * 00701 * If the current point is deleted either now, or in the future, the cycle 00702 * point will be set to the next item which is set to current. This could be 00703 * by a forward, add_after_then_move or add_after_then_move. 00704 **********************************************************************/ 00705 00706 inline void ELIST2_ITERATOR::mark_cycle_pt() { 00707 #ifndef NDEBUG 00708 if (!this) 00709 NULL_OBJECT.error ("ELIST2_ITERATOR::mark_cycle_pt", ABORT, NULL); 00710 if (!list) 00711 NO_LIST.error ("ELIST2_ITERATOR::mark_cycle_pt", ABORT, NULL); 00712 #endif 00713 00714 if (current) 00715 cycle_pt = current; 00716 else 00717 ex_current_was_cycle_pt = TRUE; 00718 started_cycling = FALSE; 00719 } 00720 00721 00722 /*********************************************************************** 00723 * ELIST2_ITERATOR::at_first() 00724 * 00725 * Are we at the start of the list? 00726 * 00727 **********************************************************************/ 00728 00729 inline BOOL8 ELIST2_ITERATOR::at_first() { 00730 #ifndef NDEBUG 00731 if (!this) 00732 NULL_OBJECT.error ("ELIST2_ITERATOR::at_first", ABORT, NULL); 00733 if (!list) 00734 NO_LIST.error ("ELIST2_ITERATOR::at_first", ABORT, NULL); 00735 #endif 00736 00737 //we're at a deleted 00738 return ((list->empty ()) || (current == list->First ()) || ((current == NULL) && 00739 (prev == list->last) && //NON-last pt between 00740 !ex_current_was_last)); //first and last 00741 } 00742 00743 00744 /*********************************************************************** 00745 * ELIST2_ITERATOR::at_last() 00746 * 00747 * Are we at the end of the list? 00748 * 00749 **********************************************************************/ 00750 00751 inline BOOL8 ELIST2_ITERATOR::at_last() { 00752 #ifndef NDEBUG 00753 if (!this) 00754 NULL_OBJECT.error ("ELIST2_ITERATOR::at_last", ABORT, NULL); 00755 if (!list) 00756 NO_LIST.error ("ELIST2_ITERATOR::at_last", ABORT, NULL); 00757 #endif 00758 00759 //we're at a deleted 00760 return ((list->empty ()) || (current == list->last) || ((current == NULL) && 00761 (prev == list->last) && //last point between 00762 ex_current_was_last)); //first and last 00763 } 00764 00765 00766 /*********************************************************************** 00767 * ELIST2_ITERATOR::cycled_list() 00768 * 00769 * Have we returned to the cycle_pt since it was set? 00770 * 00771 **********************************************************************/ 00772 00773 inline BOOL8 ELIST2_ITERATOR::cycled_list() { 00774 #ifndef NDEBUG 00775 if (!this) 00776 NULL_OBJECT.error ("ELIST2_ITERATOR::cycled_list", ABORT, NULL); 00777 if (!list) 00778 NO_LIST.error ("ELIST2_ITERATOR::cycled_list", ABORT, NULL); 00779 #endif 00780 00781 return ((list->empty ()) || ((current == cycle_pt) && started_cycling)); 00782 00783 } 00784 00785 00786 /*********************************************************************** 00787 * ELIST2_ITERATOR::length() 00788 * 00789 * Return the length of the list 00790 * 00791 **********************************************************************/ 00792 00793 inline inT32 ELIST2_ITERATOR::length() { 00794 #ifndef NDEBUG 00795 if (!this) 00796 NULL_OBJECT.error ("ELIST2_ITERATOR::length", ABORT, NULL); 00797 if (!list) 00798 NO_LIST.error ("ELIST2_ITERATOR::length", ABORT, NULL); 00799 #endif 00800 00801 return list->length (); 00802 } 00803 00804 00805 /*********************************************************************** 00806 * ELIST2_ITERATOR::sort() 00807 * 00808 * Sort the elements of the list, then reposition at the start. 00809 * 00810 **********************************************************************/ 00811 00812 inline void 00813 ELIST2_ITERATOR::sort ( //sort elements 00814 int comparator ( //comparison routine 00815 const void *, const void *)) { 00816 #ifndef NDEBUG 00817 if (!this) 00818 NULL_OBJECT.error ("ELIST2_ITERATOR::sort", ABORT, NULL); 00819 if (!list) 00820 NO_LIST.error ("ELIST2_ITERATOR::sort", ABORT, NULL); 00821 #endif 00822 00823 list->sort (comparator); 00824 move_to_first(); 00825 } 00826 00827 00828 /*********************************************************************** 00829 * ELIST2_ITERATOR::add_to_end 00830 * 00831 * Add a new element to the end of the list without moving the iterator. 00832 * This is provided because a single linked list cannot move to the last as 00833 * the iterator couldn't set its prev pointer. Adding to the end is 00834 * essential for implementing 00835 queues. 00836 **********************************************************************/ 00837 00838 inline void ELIST2_ITERATOR::add_to_end( // element to add 00839 ELIST2_LINK *new_element) { 00840 #ifndef NDEBUG 00841 if (!this) 00842 NULL_OBJECT.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL); 00843 if (!list) 00844 NO_LIST.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL); 00845 if (!new_element) 00846 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_to_end", ABORT, 00847 "new_element is NULL"); 00848 if (new_element->next) 00849 STILL_LINKED.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL); 00850 #endif 00851 00852 if (this->at_last ()) { 00853 this->add_after_stay_put (new_element); 00854 } 00855 else { 00856 if (this->at_first ()) { 00857 this->add_before_stay_put (new_element); 00858 list->last = new_element; 00859 } 00860 else { //Iteratr is elsewhere 00861 new_element->next = list->last->next; 00862 new_element->prev = list->last; 00863 list->last->next->prev = new_element; 00864 list->last->next = new_element; 00865 list->last = new_element; 00866 } 00867 } 00868 } 00869 00870 00871 /*********************************************************************** 00872 QUOTE_IT MACRO DEFINITION 00873 =========================== 00874 Replace <parm> with "<parm>". <parm> may be an arbitrary number of tokens 00875 ***********************************************************************/ 00876 00877 #define QUOTE_IT( parm ) #parm 00878 00879 /*********************************************************************** 00880 ELIST2IZE( CLASSNAME ) MACRO DEFINITION 00881 ====================================== 00882 00883 CLASSNAME is assumed to be the name of a class which has a baseclass of 00884 ELIST2_LINK. 00885 00886 NOTE: Because we dont use virtual functions in the list code, the list code 00887 will NOT work correctly for classes derived from this. 00888 00889 The macro generates: 00890 - An element deletion function: CLASSNAME##_zapper 00891 - An E_LIST2 subclass: CLASSNAME##_LIST 00892 - An E_LIST2_ITERATOR subclass: 00893 CLASSNAME##_IT 00894 00895 NOTE: Generated names are DELIBERATELY designed to clash with those for 00896 ELISTIZE but NOT with those for CLISTIZE and CLIST2IZE 00897 00898 Two macros are provided: ELIST2IZE and ELIST2IZEH 00899 The ...IZEH macros just define the class names for use in .h files 00900 The ...IZE macros define the code use in .c files 00901 ***********************************************************************/ 00902 00903 /*********************************************************************** 00904 ELIST2IZEH( CLASSNAME ) MACRO 00905 00906 ELIST2IZEH is a concatenation of 3 fragments ELIST2IZEH_A, ELIST2IZEH_B and 00907 ELIST2IZEH_C. 00908 ***********************************************************************/ 00909 00910 #define ELIST2IZEH_A( CLASSNAME ) \ 00911 \ 00912 extern DLLSYM void CLASSNAME##_zapper( /*delete a link*/ \ 00913 ELIST2_LINK* link); /*link to delete*/ 00914 00915 #define ELIST2IZEH_B( CLASSNAME ) \ 00916 \ 00917 /*********************************************************************** \ 00918 * CLASS - CLASSNAME##_LIST \ 00919 * \ 00920 * List class for class CLASSNAME \ 00921 * \ 00922 **********************************************************************/ \ 00923 \ 00924 class DLLSYM CLASSNAME##_LIST : public ELIST2 \ 00925 { \ 00926 public: \ 00927 CLASSNAME##_LIST():ELIST2() {} \ 00928 /* constructor */ \ 00929 \ 00930 CLASSNAME##_LIST( /* dont construct */ \ 00931 const CLASSNAME##_LIST&) /*by initial assign*/\ 00932 { DONT_CONSTRUCT_LIST_BY_COPY.error( QUOTE_IT( CLASSNAME##_LIST ), \ 00933 ABORT, NULL ); } \ 00934 \ 00935 void clear() /* delete elements */\ 00936 { ELIST2::internal_clear( &CLASSNAME##_zapper ); } \ 00937 \ 00938 ~CLASSNAME##_LIST() /* destructor */ \ 00939 { clear(); } \ 00940 \ 00941 /* Become a deep copy of src_list*/ \ 00942 void deep_copy(const CLASSNAME##_LIST* src_list, \ 00943 CLASSNAME* (*copier)(const CLASSNAME*)); \ 00944 \ 00945 void operator=( /* prevent assign */ \ 00946 const CLASSNAME##_LIST&) \ 00947 { DONT_ASSIGN_LISTS.error( QUOTE_IT( CLASSNAME##_LIST ), \ 00948 ABORT, NULL ); } 00949 00950 #define ELIST2IZEH_C( CLASSNAME ) \ 00951 }; \ 00952 \ 00953 \ 00954 \ 00955 /*********************************************************************** \ 00956 * CLASS - CLASSNAME##_IT \ 00957 * \ 00958 * Iterator class for class CLASSNAME##_LIST \ 00959 * \ 00960 * Note: We don't need to coerce pointers to member functions input \ 00961 * parameters as these are automatically converted to the type of the base \ 00962 * type. ("A ptr to a class may be converted to a pointer to a public base \ 00963 * class of that class") \ 00964 **********************************************************************/ \ 00965 \ 00966 class DLLSYM CLASSNAME##_IT : public ELIST2_ITERATOR \ 00967 { \ 00968 public: \ 00969 CLASSNAME##_IT():ELIST2_ITERATOR(){} \ 00970 \ 00971 CLASSNAME##_IT( \ 00972 CLASSNAME##_LIST* list):ELIST2_ITERATOR(list){} \ 00973 \ 00974 CLASSNAME* data() \ 00975 { return (CLASSNAME*) ELIST2_ITERATOR::data(); } \ 00976 \ 00977 CLASSNAME* data_relative( \ 00978 inT8 offset) \ 00979 { return (CLASSNAME*) ELIST2_ITERATOR::data_relative( offset ); } \ 00980 \ 00981 CLASSNAME* forward() \ 00982 { return (CLASSNAME*) ELIST2_ITERATOR::forward(); } \ 00983 \ 00984 CLASSNAME* backward() \ 00985 { return (CLASSNAME*) ELIST2_ITERATOR::backward(); } \ 00986 \ 00987 CLASSNAME* extract() \ 00988 { return (CLASSNAME*) ELIST2_ITERATOR::extract(); } \ 00989 \ 00990 CLASSNAME* move_to_first() \ 00991 { return (CLASSNAME*) ELIST2_ITERATOR::move_to_first(); } \ 00992 \ 00993 CLASSNAME* move_to_last() \ 00994 { return (CLASSNAME*) ELIST2_ITERATOR::move_to_last(); } \ 00995 }; 00996 00997 #define ELIST2IZEH( CLASSNAME ) \ 00998 \ 00999 ELIST2IZEH_A( CLASSNAME ) \ 01000 \ 01001 ELIST2IZEH_B( CLASSNAME ) \ 01002 \ 01003 ELIST2IZEH_C( CLASSNAME ) 01004 01005 01006 /*********************************************************************** 01007 ELIST2IZE( CLASSNAME ) MACRO 01008 ***********************************************************************/ 01009 01010 #define ELIST2IZE( CLASSNAME ) \ 01011 \ 01012 /*********************************************************************** \ 01013 * CLASSNAME##_zapper \ 01014 * \ 01015 * A function which can delete a CLASSNAME element. This is passed to the \ 01016 * generic clear list member function so that when a list is cleared the \ 01017 * elements on the list are properly destroyed from the base class, even \ 01018 * though we dont use a virtual destructor function. \ 01019 **********************************************************************/ \ 01020 \ 01021 DLLSYM void CLASSNAME##_zapper( /*delete a link*/ \ 01022 ELIST2_LINK* link) /*link to delete*/ \ 01023 { \ 01024 delete (CLASSNAME *) link; \ 01025 } \ 01026 \ 01027 /* Become a deep copy of src_list*/ \ 01028 void CLASSNAME##_LIST::deep_copy(const CLASSNAME##_LIST* src_list, \ 01029 CLASSNAME* (*copier)(const CLASSNAME*)) { \ 01030 \ 01031 CLASSNAME##_IT from_it(const_cast<CLASSNAME##_LIST*>(src_list)); \ 01032 CLASSNAME##_IT to_it(this); \ 01033 \ 01034 for (from_it.mark_cycle_pt(); !from_it.cycled_list(); from_it.forward()) \ 01035 to_it.add_after_then_move((*copier)(from_it.data())); \ 01036 } 01037 01038 #endif
1.7.5.1 
