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