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