00001
00020 #include "mfcpch.h"
00021 #include <stdlib.h>
00022 #include "elst.h"
00023
00024
00025
00026
00027
00028
00032 void ELIST_LINK::serialise_asc(
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(
00040 FILE *f) {
00041 SERIALISE_LINKS.error ("ELIST_LINK::de_serialise_asc", ABORT,
00042 "Don't call this, override!");
00043 }
00044
00045
00046
00047
00048
00049
00050
00061 void
00062 ELIST::internal_clear (
00063 void (*zapper) (ELIST_LINK *)) {
00064
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;
00075 last->next = NULL;
00076 last = NULL;
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 *),
00097 const ELIST * list) {
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(
00128 ELIST_ITERATOR *start_it,
00129 ELIST_ITERATOR *end_it) {
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() {
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 (
00171 int comparator (
00172 const void *, const void *)) {
00173 ELIST_ITERATOR it(this);
00174 INT32 count;
00175 ELIST_LINK **base;
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
00185 count = length ();
00186 base = (ELIST_LINK **) malloc (count * sizeof (ELIST_LINK *));
00187
00188
00189 current = base;
00190 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) {
00191 *current = it.extract ();
00192 current++;
00193 }
00194
00195
00196 qsort ((char *) base, count, sizeof (*base), comparator);
00197
00198
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
00282 de_serialised_element->next = NULL;
00283 this_it.add_to_end (de_serialised_element);
00284 }
00285 }
00286
00287
00288
00289
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) {
00309
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(
00339 INT8 offset) {
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(
00402 ELIST_ITERATOR *other_it) {
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
00420
00421
00422 if ((list->empty ()) ||
00423 (other_it->list->empty ()) || (current == other_it->current))
00424 return;
00425
00426
00427
00428 if (!current || !other_it->current)
00429 DONT_EXCHANGE_DELETED.error ("ELIST_ITERATOR.exchange", ABORT, NULL);
00430
00431
00432
00433
00434
00435
00436
00437
00438 if ((next == other_it->current) ||
00439 (other_it->next == current)) {
00440
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 {
00447
00448
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 {
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 {
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
00473
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
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(
00503 ELIST_ITERATOR *other_it) {
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 {
00539 if (temp_it.cycled_list ())
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
00558 other_it->current->next = current;
00559 end_of_new_list = other_it->current;
00560
00561
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 }