00001
00020 #include "mfcpch.h"
00021 #include <stdlib.h>
00022 #include "host.h"
00023 #include "elst2.h"
00024
00025
00026
00027
00028
00029
00042 void
00043 ELIST2::internal_clear (
00044 void (*zapper) (ELIST2_LINK *)) {
00045
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;
00056 last->next = NULL;
00057 last = NULL;
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 *),
00077 const ELIST2 * list) {
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(
00107 ELIST2_ITERATOR *start_it,
00108 ELIST2_ITERATOR *end_it) {
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() {
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 (
00150 int comparator (
00151 const void *, const void *)) {
00152 ELIST2_ITERATOR it(this);
00153 INT32 count;
00154 ELIST2_LINK **base;
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
00164 count = length ();
00165 base = (ELIST2_LINK **) malloc (count * sizeof (ELIST2_LINK *));
00166
00167
00168 current = base;
00169 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) {
00170 *current = it.extract ();
00171 current++;
00172 }
00173
00174
00175 qsort ((char *) base, count, sizeof (*base), comparator);
00176
00177
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
00261 de_serialised_element->next = NULL;
00262
00263 de_serialised_element->prev = NULL;
00264 this_it.add_to_end (de_serialised_element);
00265 }
00266 }
00267
00268
00269
00270
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) {
00290
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) {
00329
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(
00358 INT8 offset) {
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(
00394 ELIST2_ITERATOR *other_it) {
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
00412
00413
00414 if ((list->empty ()) ||
00415 (other_it->list->empty ()) || (current == other_it->current))
00416 return;
00417
00418
00419
00420 if (!current || !other_it->current)
00421 DONT_EXCHANGE_DELETED.error ("ELIST2_ITERATOR.exchange", ABORT, NULL);
00422
00423
00424
00425
00426
00427
00428
00429
00430 if ((next == other_it->current) ||
00431 (other_it->next == current)) {
00432
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 {
00439
00440
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 {
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 {
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
00477
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
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(
00506 ELIST2_ITERATOR *other_it) {
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 {
00542 if (temp_it.cycled_list ())
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
00559 while (temp_it.prev != other_it->current);
00560
00561
00562 other_it->current->next = current;
00563
00564 current->prev = other_it->current;
00565 end_of_new_list = other_it->current;
00566
00567
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 }