ccutil/elst.cpp

Go to the documentation of this file.
00001 
00020 #include          "mfcpch.h"     //precompiled headers
00021 #include <stdlib.h>
00022 #include "elst.h"
00023 
00024 /* ==================
00025  *  MEMBER FUNCTIONS OF CLASS: ELIST_LINK
00026  *  =====================================
00027  ==================== */
00028 
00032 void ELIST_LINK::serialise_asc(  //default serialise
00033                                FILE *f) {
00034   SERIALISE_LINKS.error ("ELIST_LINK::serialise_asc", ABORT,
00035     "Don't call this, override!");
00036 }
00037 
00038 
00039 void ELIST_LINK::de_serialise_asc(  //default de_serialise
00040                                   FILE *f) {
00041   SERIALISE_LINKS.error ("ELIST_LINK::de_serialise_asc", ABORT,
00042     "Don't call this, override!");
00043 }
00044 
00045 
00046 /* ==================
00047  *  MEMBER FUNCTIONS OF CLASS: ELIST
00048  *  ================================
00049  ==================== */
00050 
00061 void
00062 ELIST::internal_clear (          //destroy all links
00063 void (*zapper) (ELIST_LINK *)) {
00064                                  //ptr to zapper functn
00065   ELIST_LINK *ptr;
00066   ELIST_LINK *next;
00067 
00068   #ifdef _DEBUG
00069   if (!this)
00070     NULL_OBJECT.error ("ELIST::internal_clear", ABORT, NULL);
00071   #endif
00072 
00073   if (!empty ()) {
00074     ptr = last->next;            //set to first
00075     last->next = NULL;           //break circle
00076     last = NULL;                 //set list empty
00077     while (ptr) {
00078       next = ptr->next;
00079       zapper(ptr);
00080       ptr = next;
00081     }
00082   }
00083 }
00084 
00085 
00095 void ELIST::internal_deep_copy (
00096    ELIST_LINK * (*copier) (ELIST_LINK *), //ptr to copier functn
00097    const ELIST * list) {            //list being copied
00098   ELIST_ITERATOR from_it ((ELIST *) list);
00099   ELIST_ITERATOR to_it(this);
00100 
00101   #ifdef _DEBUG
00102   if (!this)
00103     NULL_OBJECT.error ("ELIST::internal_deep_copy", ABORT, NULL);
00104   if (!list)
00105     BAD_PARAMETER.error ("ELIST::internal_deep_copy", ABORT,
00106       "source list is NULL");
00107   #endif
00108 
00109   for (from_it.mark_cycle_pt (); !from_it.cycled_list (); from_it.forward ())
00110     to_it.add_after_then_move (copier (from_it.data ()));
00111 }
00112 
00113 
00127 void ELIST::assign_to_sublist(                           //to this list
00128                               ELIST_ITERATOR *start_it,  //from list start
00129                               ELIST_ITERATOR *end_it) {  //from list end
00130   const ERRCODE LIST_NOT_EMPTY =
00131     "Destination list must be empty before extracting a sublist";
00132 
00133   #ifdef _DEBUG
00134   if (!this)
00135     NULL_OBJECT.error ("ELIST::assign_to_sublist", ABORT, NULL);
00136   #endif
00137 
00138   if (!empty ())
00139     LIST_NOT_EMPTY.error ("ELIST.assign_to_sublist", ABORT, NULL);
00140 
00141   last = start_it->extract_sublist (end_it);
00142 }
00143 
00144 
00148 INT32 ELIST::length() {  //count elements
00149   ELIST_ITERATOR it(this);
00150   INT32 count = 0;
00151 
00152   #ifdef _DEBUG
00153   if (!this)
00154     NULL_OBJECT.error ("ELIST::length", ABORT, NULL);
00155   #endif
00156 
00157   for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
00158     count++;
00159   return count;
00160 }
00161 
00162 
00169 void
00170 ELIST::sort (                    //sort elements
00171 int comparator (                 //comparison routine
00172 const void *, const void *)) {
00173   ELIST_ITERATOR it(this);
00174   INT32 count;
00175   ELIST_LINK **base;             //ptr array to sort
00176   ELIST_LINK **current;
00177   INT32 i;
00178 
00179   #ifdef _DEBUG
00180   if (!this)
00181     NULL_OBJECT.error ("ELIST::sort", ABORT, NULL);
00182   #endif
00183 
00184   /* Allocate an array of pointers, one per list element */
00185   count = length ();
00186   base = (ELIST_LINK **) malloc (count * sizeof (ELIST_LINK *));
00187 
00188   /* Extract all elements, putting the pointers in the array */
00189   current = base;
00190   for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) {
00191     *current = it.extract ();
00192     current++;
00193   }
00194 
00195   /* Sort the pointer array */
00196   qsort ((char *) base, count, sizeof (*base), comparator);
00197 
00198   /* Rebuild the list from the sorted pointers */
00199   current = base;
00200   for (i = 0; i < count; i++) {
00201     it.add_to_end (*current);
00202     current++;
00203   }
00204   free(base);
00205 }
00206 
00207 
00215 void ELIST::prep_serialise() {
00216   ELIST_ITERATOR this_it(this);
00217   INT32 count = 0;
00218 
00219   #ifdef _DEBUG
00220   if (!this)
00221     NULL_OBJECT.error ("ELIST::prep_serialise", ABORT, NULL);
00222   #endif
00223 
00224   count = 0;
00225   if (!empty ())
00226     for (this_it.mark_cycle_pt ();
00227     !this_it.cycled_list (); this_it.forward ())
00228   count++;
00229   last = (ELIST_LINK *) count;
00230 }
00231 
00232 
00241 void
00242 ELIST::internal_dump (FILE * f,
00243 void element_serialiser (FILE *, ELIST_LINK *)) {
00244   ELIST_ITERATOR this_it(this);
00245 
00246   #ifdef _DEBUG
00247   if (!this)
00248     NULL_OBJECT.error ("ELIST::internal_dump", ABORT, NULL);
00249   #endif
00250 
00251   if (!empty ())
00252     for (this_it.mark_cycle_pt ();
00253     !this_it.cycled_list (); this_it.forward ())
00254   element_serialiser (f, this_it.data ());
00255 }
00256 
00257 
00265 void
00266 ELIST::internal_de_dump (FILE * f,
00267 ELIST_LINK * element_de_serialiser (FILE *)) {
00268   INT32 count = (ptrdiff_t) last;
00269   ELIST_ITERATOR this_it;
00270   ELIST_LINK *de_serialised_element;
00271 
00272   #ifdef _DEBUG
00273   if (!this)
00274     NULL_OBJECT.error ("ELIST::internal_de_dump", ABORT, NULL);
00275   #endif
00276 
00277   last = NULL;
00278   this_it.set_to_list (this);
00279   for (; count > 0; count--) {
00280     de_serialised_element = element_de_serialiser (f);
00281                                  //ignore old ptr
00282     de_serialised_element->next = NULL;
00283     this_it.add_to_end (de_serialised_element);
00284   }
00285 }
00286 
00287 
00288 /* ==================
00289  *  MEMBER FUNCTIONS OF CLASS: ELIST_ITERATOR
00290  *  =========================================
00291  ==================== */
00292 
00298 ELIST_LINK *ELIST_ITERATOR::forward() {
00299   #ifdef _DEBUG
00300   if (!this)
00301     NULL_OBJECT.error ("ELIST_ITERATOR::forward", ABORT, NULL);
00302   if (!list)
00303     NO_LIST.error ("ELIST_ITERATOR::forward", ABORT, NULL);
00304   #endif
00305   if (list->empty ())
00306     return NULL;
00307 
00308   if (current) {                 //not removed so
00309                                  //set previous
00310     prev = current;
00311     started_cycling = TRUE;
00312   }
00313   else {
00314     if (ex_current_was_cycle_pt)
00315       cycle_pt = next;
00316   }
00317   current = next;
00318   next = current->next;
00319 
00320   #ifdef _DEBUG
00321   if (!current)
00322     NULL_DATA.error ("ELIST_ITERATOR::forward", ABORT, NULL);
00323   if (!next)
00324     NULL_NEXT.error ("ELIST_ITERATOR::forward", ABORT,
00325       "This is: %i  Current is: %i",
00326       (int) this, (int) current);
00327   #endif
00328   return current;
00329 }
00330 
00331 
00338 ELIST_LINK *ELIST_ITERATOR::data_relative(   //get data + or - ...
00339        INT8 offset) {  //offset from current
00340   ELIST_LINK *ptr;
00341 
00342   #ifdef _DEBUG
00343   if (!this)
00344     NULL_OBJECT.error ("ELIST_ITERATOR::data_relative", ABORT, NULL);
00345   if (!list)
00346     NO_LIST.error ("ELIST_ITERATOR::data_relative", ABORT, NULL);
00347   if (list->empty ())
00348     EMPTY_LIST.error ("ELIST_ITERATOR::data_relative", ABORT, NULL);
00349   if (offset < -1)
00350     BAD_PARAMETER.error ("ELIST_ITERATOR::data_relative", ABORT,
00351       "offset < -l");
00352   #endif
00353 
00354   if (offset == -1)
00355     ptr = prev;
00356   else
00357     for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next);
00358 
00359   #ifdef _DEBUG
00360   if (!ptr)
00361     NULL_DATA.error ("ELIST_ITERATOR::data_relative", ABORT, NULL);
00362   #endif
00363 
00364   return ptr;
00365 }
00366 
00367 
00374 ELIST_LINK *ELIST_ITERATOR::move_to_last() {
00375   #ifdef _DEBUG
00376   if (!this)
00377     NULL_OBJECT.error ("ELIST_ITERATOR::move_to_last", ABORT, NULL);
00378   if (!list)
00379     NO_LIST.error ("ELIST_ITERATOR::move_to_last", ABORT, NULL);
00380   #endif
00381 
00382   while (current != list->last)
00383     forward();
00384 
00385   return current;
00386 }
00387 
00388 
00401 void ELIST_ITERATOR::exchange(    //positions of 2 links
00402          ELIST_ITERATOR *other_it) {  //other iterator
00403   const ERRCODE DONT_EXCHANGE_DELETED =
00404     "Can't exchange deleted elements of lists";
00405 
00406   ELIST_LINK *old_current;
00407 
00408   #ifdef _DEBUG
00409   if (!this)
00410     NULL_OBJECT.error ("ELIST_ITERATOR::exchange", ABORT, NULL);
00411   if (!list)
00412     NO_LIST.error ("ELIST_ITERATOR::exchange", ABORT, NULL);
00413   if (!other_it)
00414     BAD_PARAMETER.error ("ELIST_ITERATOR::exchange", ABORT, "other_it NULL");
00415   if (!(other_it->list))
00416     NO_LIST.error ("ELIST_ITERATOR::exchange", ABORT, "other_it");
00417   #endif
00418 
00419   /* Do nothing if either list is empty or if both iterators
00420   reference the same link */
00421 
00422   if ((list->empty ()) ||
00423     (other_it->list->empty ()) || (current == other_it->current))
00424     return;
00425 
00426   /* Error if either current element is deleted */
00427 
00428   if (!current || !other_it->current)
00429     DONT_EXCHANGE_DELETED.error ("ELIST_ITERATOR.exchange", ABORT, NULL);
00430 
00431   /* Now handle the 4 cases:
00432     doubleton list;
00433     non-doubleton adjacent elements (other before this);
00434     non-doubleton adjacent elements (this before other);
00435     non-adjacent elements. */
00436 
00437                                  //adjacent links
00438   if ((next == other_it->current) ||
00439   (other_it->next == current)) {
00440                                  //doubleton list
00441     if ((next == other_it->current) &&
00442     (other_it->next == current)) {
00443       prev = next = current;
00444       other_it->prev = other_it->next = other_it->current;
00445     }
00446     else {                       //non-doubleton with
00447                                  //adjacent links
00448                                  //other before this
00449       if (other_it->next == current) {
00450         other_it->prev->next = current;
00451         other_it->current->next = next;
00452         current->next = other_it->current;
00453         other_it->next = other_it->current;
00454         prev = current;
00455       }
00456       else {                     //this before other
00457         prev->next = other_it->current;
00458         current->next = other_it->next;
00459         other_it->current->next = current;
00460         next = current;
00461         other_it->prev = other_it->current;
00462       }
00463     }
00464   }
00465   else {                         //no overlap
00466     prev->next = other_it->current;
00467     current->next = other_it->next;
00468     other_it->prev->next = current;
00469     other_it->current->next = next;
00470   }
00471 
00472   /* update end of list pointer when necessary (remember that the
00473   2 iterators may iterate over different lists!) */
00474 
00475   if (list->last == current)
00476     list->last = other_it->current;
00477   if (other_it->list->last == other_it->current)
00478     other_it->list->last = current;
00479 
00480   if (current == cycle_pt)
00481     cycle_pt = other_it->cycle_pt;
00482   if (other_it->current == other_it->cycle_pt)
00483     other_it->cycle_pt = cycle_pt;
00484 
00485   /* The actual exchange - in all cases*/
00486 
00487   old_current = current;
00488   current = other_it->current;
00489   other_it->current = old_current;
00490 }
00491 
00492 
00502 ELIST_LINK *ELIST_ITERATOR::extract_sublist(  //from this current
00503         ELIST_ITERATOR *other_it) {  //to other current
00504   #ifdef _DEBUG
00505   const ERRCODE BAD_EXTRACTION_PTS =
00506     "Can't extract sublist from points on different lists";
00507   const ERRCODE DONT_EXTRACT_DELETED =
00508     "Can't extract a sublist marked by deleted points";
00509   #endif
00510   const ERRCODE BAD_SUBLIST = "Can't find sublist end point in original list";
00511 
00512   ELIST_ITERATOR temp_it = *this;
00513   ELIST_LINK *end_of_new_list;
00514 
00515   #ifdef _DEBUG
00516   if (!this)
00517     NULL_OBJECT.error ("ELIST_ITERATOR::extract_sublist", ABORT, NULL);
00518   if (!other_it)
00519     BAD_PARAMETER.error ("ELIST_ITERATOR::extract_sublist", ABORT,
00520       "other_it NULL");
00521   if (!list)
00522     NO_LIST.error ("ELIST_ITERATOR::extract_sublist", ABORT, NULL);
00523   if (list != other_it->list)
00524     BAD_EXTRACTION_PTS.error ("ELIST_ITERATOR.extract_sublist", ABORT, NULL);
00525   if (list->empty ())
00526     EMPTY_LIST.error ("ELIST_ITERATOR::extract_sublist", ABORT, NULL);
00527 
00528   if (!current || !other_it->current)
00529     DONT_EXTRACT_DELETED.error ("ELIST_ITERATOR.extract_sublist", ABORT,
00530       NULL);
00531   #endif
00532 
00533   ex_current_was_last = other_it->ex_current_was_last = FALSE;
00534   ex_current_was_cycle_pt = FALSE;
00535   other_it->ex_current_was_cycle_pt = FALSE;
00536 
00537   temp_it.mark_cycle_pt ();
00538   do {                           //walk sublist
00539     if (temp_it.cycled_list ())  //cant find end pt
00540       BAD_SUBLIST.error ("ELIST_ITERATOR.extract_sublist", ABORT, NULL);
00541 
00542     if (temp_it.at_last ()) {
00543       list->last = prev;
00544       ex_current_was_last = other_it->ex_current_was_last = TRUE;
00545     }
00546 
00547     if (temp_it.current == cycle_pt)
00548       ex_current_was_cycle_pt = TRUE;
00549 
00550     if (temp_it.current == other_it->cycle_pt)
00551       other_it->ex_current_was_cycle_pt = TRUE;
00552 
00553     temp_it.forward ();
00554   }
00555   while (temp_it.prev != other_it->current);
00556 
00557                                  //circularise sublist
00558   other_it->current->next = current;
00559   end_of_new_list = other_it->current;
00560 
00561                                  //sublist = whole list
00562   if (prev == other_it->current) {
00563     list->last = NULL;
00564     prev = current = next = NULL;
00565     other_it->prev = other_it->current = other_it->next = NULL;
00566   }
00567   else {
00568     prev->next = other_it->next;
00569     current = other_it->current = NULL;
00570     next = other_it->next;
00571     other_it->prev = prev;
00572   }
00573   return end_of_new_list;
00574 }

Generated on Wed Feb 28 19:49:09 2007 for Tesseract by  doxygen 1.5.1