ELIST Class Reference

#include <elst.h>

List of all members.

Detailed Description

Singly linked lists with embedded links; generic list class.

Note:
dump() and de_dump() are not required as calls to dump/de_dump a list class should be handled by a class derived from this. make_serialise is not required for a similar reason.

Definition at line 117 of file elst.h.

Public Member Functions

Private Member Functions

Private Attributes

Friends

Constructor & Destructor Documentation

ELIST::ELIST (  )  [inline]

Definition at line 128 of file elst.h.

References last(), and NULL.

00128             {  //constructor
00129       last = NULL;
00130     }

Member Function Documentation

void ELIST::assign_to_sublist ( ELIST_ITERATOR *  start_it,
ELIST_ITERATOR *  end_it 
)

The list is set to a sublist of another list.

"This" list must be empty before this function is invoked. The two iterators passed must refer to the same list, different from "this" one. The sublist removed is the inclusive list from start_it's current position to end_it's current position. If this range passes over the end of the source list then the source list has its end set to the previous element of start_it.

The extracted sublist is unaffected by the end point of the source list, its end point is always the end_it position.

Definition at line 127 of file elst.cpp.

References ABORT, empty(), ERRCODE::error(), ELIST_ITERATOR::extract_sublist(), last, and NULL.

00129                                                       {  //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 }

BOOL8 ELIST::empty (  )  [inline]

Definition at line 136 of file elst.h.

References last().

Referenced by ELIST_ITERATOR::add_after_stay_put(), ELIST_ITERATOR::add_after_then_move(), ELIST_ITERATOR::add_before_stay_put(), ELIST_ITERATOR::add_before_then_move(), ELIST_ITERATOR::add_list_after(), ELIST_ITERATOR::add_list_before(), assign_to_sublist(), ELIST_ITERATOR::at_first(), ELIST_ITERATOR::at_last(), ELIST_ITERATOR::cycled_list(), ELIST_ITERATOR::data_relative(), ELIST_ITERATOR::exchange(), ELIST_ITERATOR::extract_sublist(), ELIST_ITERATOR::forward(), internal_clear(), internal_dump(), and prep_serialise().

00136                   {  //is list empty?
00137       return !last;
00138     }

ELIST_LINK* ELIST::First (  )  [inline, private]

Definition at line 123 of file elst.h.

References last(), list_rec::next, and NULL.

Referenced by ELIST_ITERATOR::add_list_after(), ELIST_ITERATOR::add_list_before(), ELIST_ITERATOR::at_first(), ELIST_ITERATOR::move_to_first(), and ELIST_ITERATOR::set_to_list().

00123                       {  // return first
00124     return last ? last->next : NULL;
00125   }

void ELIST::internal_clear ( void(*)(ELIST_LINK *)  zapper  ) 

Used by the destructor and the "clear" member function of derived list classes to destroy all the elements on the list.

The calling function passes a "zapper" function which can be called to delete each element of the list, regardless of its derived type. This technique permits a generic clear function to destroy elements of different derived types correctly, without requiring virtual functions and the consequential memory overhead.

Definition at line 62 of file elst.cpp.

References ABORT, empty(), last, ELIST_LINK::next, and NULL.

00063                                {
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 }

void ELIST::internal_de_dump ( FILE *  f,
ELIST_LINK *  element_de_serialiser(FILE *) 
)

Cause each element on the list to be de_serialised by extracting the count of elements on the list, (held in the last member of the dumped version of the list object), and then de-serialising that number of list elements, adding each to the end of the reconstructed list.

Note:
New for v1.03 is 64-bit safety

Definition at line 266 of file elst.cpp.

References ABORT, ELIST_ITERATOR::add_to_end(), count(), last, ELIST_LINK::next, NULL, and ELIST_ITERATOR::set_to_list().

00267                                              {
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 }

void ELIST::internal_deep_copy ( ELIST_LINK *(*)(ELIST_LINK *)  copier,
const ELIST *  list 
)

Used during explict deep copy of a list.

The "copier" function passed allows each element to be correctly deep copied (assuming that each class in the inheritance hierarchy does properly deep copies its members).

The function passing technique is as for "internal_clear".

Definition at line 95 of file elst.cpp.

References ABORT, ELIST_ITERATOR::add_after_then_move(), ELIST_ITERATOR::cycled_list(), ELIST_ITERATOR::data(), ELIST_ITERATOR::forward(), ELIST_ITERATOR::mark_cycle_pt(), and NULL.

00097                        {            //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 }

void ELIST::internal_dump ( FILE *  f,
void   element_serialiser(FILE *, ELIST_LINK *) 
)

Cause each element on the list to be serialised by walking the list and calling the element_serialiser function for each element.

The element_serialiser simply does the appropriate coercion of the element to its real type and then invokes the elements serialise function

Definition at line 242 of file elst.cpp.

References ABORT, ELIST_ITERATOR::cycled_list(), ELIST_ITERATOR::data(), empty(), ELIST_ITERATOR::forward(), ELIST_ITERATOR::mark_cycle_pt(), and NULL.

00243                                                 {
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 }

INT32 ELIST::length (  ) 

Return count of elements on list.

Definition at line 148 of file elst.cpp.

References ABORT, count(), ELIST_ITERATOR::cycled_list(), ELIST_ITERATOR::forward(), ELIST_ITERATOR::mark_cycle_pt(), and NULL.

Referenced by ELIST_ITERATOR::length(), and sort().

00148                     {  //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 }

void ELIST::prep_serialise (  ) 

Replace the last member with a count of elements for serialisation.

This is used on list objects which are members of objects being serialised. The containing object has been shallow copied and this member function is invoked on the COPY.

Definition at line 215 of file elst.cpp.

References ABORT, count(), ELIST_ITERATOR::cycled_list(), empty(), ELIST_ITERATOR::forward(), last, ELIST_ITERATOR::mark_cycle_pt(), and NULL.

00215                            {
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 }

void ELIST::shallow_copy ( ELIST *  from_list  )  [inline]

Definition at line 144 of file elst.h.

References last, and last().

00145                                         {  //beware destructors!!
00146       last = from_list->last;
00147     }

BOOL8 ELIST::singleton (  )  [inline]

Definition at line 140 of file elst.h.

References FALSE, last(), and list_rec::next.

Referenced by ELIST_ITERATOR::extract().

00140                       {
00141       return last ? (last == last->next) : FALSE;
00142     }

void ELIST::sort ( int   comparator(const void *, const void *)  ) 

Sort elements on list.

NB If you dont like the const declarations in the comparator, coerce yours: ( int (*)(const void *, const void *)

Definition at line 170 of file elst.cpp.

References ABORT, ELIST_ITERATOR::add_to_end(), count(), ELIST_ITERATOR::cycled_list(), ELIST_ITERATOR::extract(), ELIST_ITERATOR::forward(), length(), ELIST_ITERATOR::mark_cycle_pt(), and NULL.

Referenced by ELIST_ITERATOR::sort().

00172                              {
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 }

Friends And Related Function Documentation

friend class ELIST_ITERATOR [friend]

Definition at line 119 of file elst.h.

Member Data Documentation

ELIST_LINK* ELIST::last [private]

Definition at line 121 of file elst.h.

Referenced by ELIST_ITERATOR::add_after_stay_put(), ELIST_ITERATOR::add_after_then_move(), ELIST_ITERATOR::add_before_stay_put(), ELIST_ITERATOR::add_before_then_move(), ELIST_ITERATOR::add_list_after(), ELIST_ITERATOR::add_list_before(), ELIST_ITERATOR::add_to_end(), assign_to_sublist(), ELIST_ITERATOR::at_first(), ELIST_ITERATOR::at_last(), ELIST_ITERATOR::exchange(), ELIST_ITERATOR::extract(), ELIST_ITERATOR::extract_sublist(), internal_clear(), internal_de_dump(), ELIST_ITERATOR::move_to_first(), ELIST_ITERATOR::move_to_last(), prep_serialise(), ELIST_ITERATOR::set_to_list(), and shallow_copy().

The documentation for this class was generated from the following files:
Generated on Wed Feb 28 19:49:31 2007 for Tesseract by  doxygen 1.5.1