ccutil/elst2.cpp

Go to the documentation of this file.
00001 
00020 #include          "mfcpch.h"     //precompiled headers
00021 #include <stdlib.h>
00022 #include "host.h"
00023 #include "elst2.h"
00024 
00025 /* ==================
00026  *  MEMBER FUNCTIONS OF CLASS: ELIST2
00027  *  =================================
00028  ==================== */
00029 
00042 void
00043 ELIST2::internal_clear (         //destroy all links
00044 void (*zapper) (ELIST2_LINK *)) {
00045                                  //ptr to zapper functn
00046   ELIST2_LINK *ptr;
00047   ELIST2_LINK *next;
00048 
00049   #ifdef _DEBUG
00050   if (!this)
00051     NULL_OBJECT.error ("ELIST2::internal_clear", ABORT, NULL);
00052   #endif
00053 
00054   if (!empty ()) {
00055     ptr = last->next;            //set to first
00056     last->next = NULL;           //break circle
00057     last = NULL;                 //set list empty
00058     while (ptr) {
00059       next = ptr->next;
00060       zapper(ptr);
00061       ptr = next;
00062     }
00063   }
00064 }
00065 
00066 
00075 void ELIST2::internal_deep_copy (
00076    ELIST2_LINK * (*copier) (ELIST2_LINK *), //ptr to copier functn
00077    const ELIST2 * list) {           //list being copied
00078   ELIST2_ITERATOR from_it ((ELIST2 *) list);
00079   ELIST2_ITERATOR to_it(this);
00080 
00081   #ifdef _DEBUG
00082   if (!this)
00083     NULL_OBJECT.error ("ELIST2::internal_deep_copy", ABORT, NULL);
00084   if (!list)
00085     BAD_PARAMETER.error ("ELIST2::internal_deep_copy", ABORT,
00086       "source list is NULL");
00087   #endif
00088 
00089   for (from_it.mark_cycle_pt (); !from_it.cycled_list (); from_it.forward ())
00090     to_it.add_after_then_move (copier (from_it.data ()));
00091 }
00092 
00093 
00106 void ELIST2::assign_to_sublist(                            //to this list
00107                                ELIST2_ITERATOR *start_it,  //from list start
00108                                ELIST2_ITERATOR *end_it) {  //from list end
00109   const ERRCODE LIST_NOT_EMPTY =
00110     "Destination list must be empty before extracting a sublist";
00111 
00112   #ifdef _DEBUG
00113   if (!this)
00114     NULL_OBJECT.error ("ELIST2::assign_to_sublist", ABORT, NULL);
00115   #endif
00116 
00117   if (!empty ())
00118     LIST_NOT_EMPTY.error ("ELIST2.assign_to_sublist", ABORT, NULL);
00119 
00120   last = start_it->extract_sublist (end_it);
00121 }
00122 
00123 
00127 INT32 ELIST2::length() {  //count elements
00128   ELIST2_ITERATOR it(this);
00129   INT32 count = 0;
00130 
00131   #ifdef _DEBUG
00132   if (!this)
00133     NULL_OBJECT.error ("ELIST2::length", ABORT, NULL);
00134   #endif
00135 
00136   for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
00137     count++;
00138   return count;
00139 }
00140 
00141 
00148 void
00149 ELIST2::sort (                   //sort elements
00150 int comparator (                 //comparison routine
00151 const void *, const void *)) {
00152   ELIST2_ITERATOR it(this);
00153   INT32 count;
00154   ELIST2_LINK **base;            //ptr array to sort
00155   ELIST2_LINK **current;
00156   INT32 i;
00157 
00158   #ifdef _DEBUG
00159   if (!this)
00160     NULL_OBJECT.error ("ELIST2::sort", ABORT, NULL);
00161   #endif
00162 
00163   /* Allocate an array of pointers, one per list element */
00164   count = length ();
00165   base = (ELIST2_LINK **) malloc (count * sizeof (ELIST2_LINK *));
00166 
00167   /* Extract all elements, putting the pointers in the array */
00168   current = base;
00169   for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) {
00170     *current = it.extract ();
00171     current++;
00172   }
00173 
00174   /* Sort the pointer array */
00175   qsort ((char *) base, count, sizeof (*base), comparator);
00176 
00177   /* Rebuild the list from the sorted pointers */
00178   current = base;
00179   for (i = 0; i < count; i++) {
00180     it.add_to_end (*current);
00181     current++;
00182   }
00183   free(base);
00184 }
00185 
00186 
00194 void ELIST2::prep_serialise() {
00195   ELIST2_ITERATOR this_it(this);
00196   INT32 count = 0;
00197 
00198   #ifdef _DEBUG
00199   if (!this)
00200     NULL_OBJECT.error ("ELIST2::prep_serialise", ABORT, NULL);
00201   #endif
00202 
00203   count = 0;
00204   if (!empty ())
00205     for (this_it.mark_cycle_pt ();
00206     !this_it.cycled_list (); this_it.forward ())
00207   count++;
00208   last = (ELIST2_LINK *) count;
00209 }
00210 
00211 
00220 void
00221 ELIST2::internal_dump (FILE * f,
00222 void element_serialiser (FILE *, ELIST2_LINK *)) {
00223   ELIST2_ITERATOR this_it(this);
00224 
00225   #ifdef _DEBUG
00226   if (!this)
00227     NULL_OBJECT.error ("ELIST2::internal_dump", ABORT, NULL);
00228   #endif
00229 
00230   if (!empty ())
00231     for (this_it.mark_cycle_pt ();
00232     !this_it.cycled_list (); this_it.forward ())
00233   element_serialiser (f, this_it.data ());
00234 }
00235 
00236 
00245 void ELIST2::internal_de_dump (FILE * f,
00246 ELIST2_LINK * element_de_serialiser (FILE *)) {
00247   INT32 count = (ptrdiff_t) last;
00248   ELIST2_ITERATOR this_it;
00249   ELIST2_LINK *de_serialised_element;
00250 
00251   #ifdef _DEBUG
00252   if (!this)
00253     NULL_OBJECT.error ("ELIST2::internal_de_dump", ABORT, NULL);
00254   #endif
00255 
00256   last = NULL;
00257   this_it.set_to_list (this);
00258   for (; count > 0; count--) {
00259     de_serialised_element = element_de_serialiser (f);
00260                                  //ignore old ptr
00261     de_serialised_element->next = NULL;
00262                                  //ignore old ptr
00263     de_serialised_element->prev = NULL;
00264     this_it.add_to_end (de_serialised_element);
00265   }
00266 }
00267 
00268 
00269 /* ==================
00270  *  MEMBER FUNCTIONS OF CLASS: ELIST2_ITERATOR
00271  *  ==========================================
00272  ==================== */
00273 
00279 ELIST2_LINK *ELIST2_ITERATOR::forward() {
00280   #ifdef _DEBUG
00281   if (!this)
00282     NULL_OBJECT.error ("ELIST2_ITERATOR::forward", ABORT, NULL);
00283   if (!list)
00284     NO_LIST.error ("ELIST2_ITERATOR::forward", ABORT, NULL);
00285   #endif
00286   if (list->empty ())
00287     return NULL;
00288 
00289   if (current) {                 //not removed so
00290                                  //set previous
00291     prev = current;
00292     started_cycling = TRUE;
00293   }
00294   else {
00295     if (ex_current_was_cycle_pt)
00296       cycle_pt = next;
00297   }
00298   current = next;
00299   next = current->next;
00300 
00301   #ifdef _DEBUG
00302   if (!current)
00303     NULL_DATA.error ("ELIST2_ITERATOR::forward", ABORT, NULL);
00304   if (!next)
00305     NULL_NEXT.error ("ELIST2_ITERATOR::forward", ABORT,
00306       "This is: %i  Current is: %i",
00307       (int) this, (int) current);
00308   #endif
00309   return current;
00310 }
00311 
00312 
00318 ELIST2_LINK *ELIST2_ITERATOR::backward() {
00319   #ifdef _DEBUG
00320   if (!this)
00321     NULL_OBJECT.error ("ELIST2_ITERATOR::backward", ABORT, NULL);
00322   if (!list)
00323     NO_LIST.error ("ELIST2_ITERATOR::backward", ABORT, NULL);
00324   #endif
00325   if (list->empty ())
00326     return NULL;
00327 
00328   if (current) {                 //not removed so
00329                                  //set previous
00330     next = current;
00331     started_cycling = TRUE;
00332   }
00333   else {
00334     if (ex_current_was_cycle_pt)
00335       cycle_pt = prev;
00336   }
00337   current = prev;
00338   prev = current->prev;
00339 
00340   #ifdef _DEBUG
00341   if (!current)
00342     NULL_DATA.error ("ELIST2_ITERATOR::backward", ABORT, NULL);
00343   if (!prev)
00344     NULL_PREV.error ("ELIST2_ITERATOR::backward", ABORT,
00345       "This is: %i  Current is: %i",
00346       (int) this, (int) current);
00347   #endif
00348   return current;
00349 }
00350 
00351 
00357 ELIST2_LINK *ELIST2_ITERATOR::data_relative(    //get data + or - ..
00358       INT8 offset) {  //offset from current
00359   ELIST2_LINK *ptr;
00360 
00361   #ifdef _DEBUG
00362   if (!this)
00363     NULL_OBJECT.error ("ELIST2_ITERATOR::data_relative", ABORT, NULL);
00364   if (!list)
00365     NO_LIST.error ("ELIST2_ITERATOR::data_relative", ABORT, NULL);
00366   if (list->empty ())
00367     EMPTY_LIST.error ("ELIST2_ITERATOR::data_relative", ABORT, NULL);
00368   #endif
00369 
00370   if (offset < 0)
00371     for (ptr = current ? current : next; offset++ < 0; ptr = ptr->prev);
00372   else
00373     for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next);
00374 
00375   #ifdef _DEBUG
00376   if (!ptr)
00377     NULL_DATA.error ("ELIST2_ITERATOR::data_relative", ABORT, NULL);
00378   #endif
00379 
00380   return ptr;
00381 }
00382 
00383 
00393 void ELIST2_ITERATOR::exchange(    //positions of 2 links
00394         ELIST2_ITERATOR *other_it) {  //other iterator
00395   const ERRCODE DONT_EXCHANGE_DELETED =
00396     "Can't exchange deleted elements of lists";
00397 
00398   ELIST2_LINK *old_current;
00399 
00400   #ifdef _DEBUG
00401   if (!this)
00402     NULL_OBJECT.error ("ELIST2_ITERATOR::exchange", ABORT, NULL);
00403   if (!list)
00404     NO_LIST.error ("ELIST2_ITERATOR::exchange", ABORT, NULL);
00405   if (!other_it)
00406     BAD_PARAMETER.error ("ELIST2_ITERATOR::exchange", ABORT, "other_it NULL");
00407   if (!(other_it->list))
00408     NO_LIST.error ("ELIST2_ITERATOR::exchange", ABORT, "other_it");
00409   #endif
00410 
00411   /* Do nothing if either list is empty or if both iterators
00412   reference the same link */
00413 
00414   if ((list->empty ()) ||
00415     (other_it->list->empty ()) || (current == other_it->current))
00416     return;
00417 
00418   /* Error if either current element is deleted */
00419 
00420   if (!current || !other_it->current)
00421     DONT_EXCHANGE_DELETED.error ("ELIST2_ITERATOR.exchange", ABORT, NULL);
00422 
00423   /* Now handle the 4 cases:
00424    doubleton list;
00425    non-doubleton adjacent elements (other before this);
00426    non-doubleton adjacent elements (this before other);
00427     non-adjacent elements. */
00428 
00429                                  //adjacent links
00430   if ((next == other_it->current) ||
00431   (other_it->next == current)) {
00432                                  //doubleton list
00433     if ((next == other_it->current) &&
00434     (other_it->next == current)) {
00435       prev = next = current;
00436       other_it->prev = other_it->next = other_it->current;
00437     }
00438     else {                       //non-doubleton with
00439                                  //adjacent links
00440                                  //other before this
00441       if (other_it->next == current) {
00442         other_it->prev->next = current;
00443         other_it->current->next = next;
00444         other_it->current->prev = current;
00445         current->next = other_it->current;
00446         current->prev = other_it->prev;
00447         next->prev = other_it->current;
00448 
00449         other_it->next = other_it->current;
00450         prev = current;
00451       }
00452       else {                     //this before other
00453         prev->next = other_it->current;
00454         current->next = other_it->next;
00455         current->prev = other_it->current;
00456         other_it->current->next = current;
00457         other_it->current->prev = prev;
00458         other_it->next->prev = current;
00459 
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     current->prev = other_it->prev;
00469     next->prev = other_it->current;
00470     other_it->prev->next = current;
00471     other_it->current->next = next;
00472     other_it->current->prev = prev;
00473     other_it->next->prev = current;
00474   }
00475 
00476   /* update end of list pointer when necessary (remember that the 2
00477   iterators may iterate over different lists!) */
00478 
00479   if (list->last == current)
00480     list->last = other_it->current;
00481   if (other_it->list->last == other_it->current)
00482     other_it->list->last = current;
00483 
00484   if (current == cycle_pt)
00485     cycle_pt = other_it->cycle_pt;
00486   if (other_it->current == other_it->cycle_pt)
00487     other_it->cycle_pt = cycle_pt;
00488 
00489   /* The actual exchange - in all cases*/
00490 
00491   old_current = current;
00492   current = other_it->current;
00493   other_it->current = old_current;
00494 }
00495 
00496 
00505 ELIST2_LINK *ELIST2_ITERATOR::extract_sublist(    //from this current
00506           ELIST2_ITERATOR *other_it) {  //to other current
00507   #ifdef _DEBUG
00508   const ERRCODE BAD_EXTRACTION_PTS =
00509     "Can't extract sublist from points on different lists";
00510   const ERRCODE DONT_EXTRACT_DELETED =
00511     "Can't extract a sublist marked by deleted points";
00512   #endif
00513   const ERRCODE BAD_SUBLIST = "Can't find sublist end point in original list";
00514 
00515   ELIST2_ITERATOR temp_it = *this;
00516   ELIST2_LINK *end_of_new_list;
00517 
00518   #ifdef _DEBUG
00519   if (!this)
00520     NULL_OBJECT.error ("ELIST2_ITERATOR::extract_sublist", ABORT, NULL);
00521   if (!other_it)
00522     BAD_PARAMETER.error ("ELIST2_ITERATOR::extract_sublist", ABORT,
00523       "other_it NULL");
00524   if (!list)
00525     NO_LIST.error ("ELIST2_ITERATOR::extract_sublist", ABORT, NULL);
00526   if (list != other_it->list)
00527     BAD_EXTRACTION_PTS.error ("ELIST2_ITERATOR.extract_sublist", ABORT, NULL);
00528   if (list->empty ())
00529     EMPTY_LIST.error ("ELIST2_ITERATOR::extract_sublist", ABORT, NULL);
00530 
00531   if (!current || !other_it->current)
00532     DONT_EXTRACT_DELETED.error ("ELIST2_ITERATOR.extract_sublist", ABORT,
00533       NULL);
00534   #endif
00535 
00536   ex_current_was_last = other_it->ex_current_was_last = FALSE;
00537   ex_current_was_cycle_pt = FALSE;
00538   other_it->ex_current_was_cycle_pt = FALSE;
00539 
00540   temp_it.mark_cycle_pt ();
00541   do {                           //walk sublist
00542     if (temp_it.cycled_list ())  //cant find end pt
00543       BAD_SUBLIST.error ("ELIST2_ITERATOR.extract_sublist", ABORT, NULL);
00544 
00545     if (temp_it.at_last ()) {
00546       list->last = prev;
00547       ex_current_was_last = other_it->ex_current_was_last = TRUE;
00548     }
00549 
00550     if (temp_it.current == cycle_pt)
00551       ex_current_was_cycle_pt = TRUE;
00552 
00553     if (temp_it.current == other_it->cycle_pt)
00554       other_it->ex_current_was_cycle_pt = TRUE;
00555 
00556     temp_it.forward ();
00557   }
00558                                  //do INCLUSIVE list
00559   while (temp_it.prev != other_it->current);
00560 
00561                                  //circularise sublist
00562   other_it->current->next = current;
00563                                  //circularise sublist
00564   current->prev = other_it->current;
00565   end_of_new_list = other_it->current;
00566 
00567                                  //sublist = whole list
00568   if (prev == other_it->current) {
00569     list->last = NULL;
00570     prev = current = next = NULL;
00571     other_it->prev = other_it->current = other_it->next = NULL;
00572   }
00573   else {
00574     prev->next = other_it->next;
00575     other_it->next->prev = prev;
00576 
00577     current = other_it->current = NULL;
00578     next = other_it->next;
00579     other_it->prev = prev;
00580   }
00581   return end_of_new_list;
00582 }

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