1 /***************************************************************************/
2 /* */
3 /* TOUR MAINTANENCE ROUTINES FOR LIN-KERNIGHAN - Binary Trees (unbalanced)*/
4 /* - added dummy children */
5 /* */
6 /* TSP CODE */
7 /* */
8 /* */
9 /* Written by: Applegate, Bixby, Chvatal, and Cook */
10 /* Date: November 16, 1995 */
11 /* */
12 /* */
13 /* EXPORTED FUNCTIONS: */
14 /* int CClinkern_flipper_init (int ncount, int *cyc) */
15 /* initializes flipper1 to an initial cycle given in cyc. */
16 /* returns 0 on success, nonzero on failure. */
17 /* int CClinkern_flipper_cycle (int *p) */
18 /* places the current cycle in p. */
19 /* returns the number of segments in current representation. */
20 /* void CClinkern_flipper_finish (void) */
21 /* frees up temporary space allocated by CClinkern_flipper_init. */
22 /* every flipper_init should lead to a flipper_finish call. */
23 /* void CClinkern_flipper_free_world (void) */
24 /* frees up all remaining space (including ptrs) */
25 /* should be called when we are finished with linkern */
26 /* int CClinkern_flipper_next (int x) */
27 /* returns the successor to x in the current cycle. */
28 /* int CClinkern_flipper_prev (int x) */
29 /* returns the predecessor of x in the current cycle. */
30 /* int CClinkern_flipper_sequence (int x, int y, int z) */
31 /* returns 1 if xyz occur as an increasing subsequence of the cycle, */
32 /* returns 0 otherwise. */
33 /* */
34 /* If SAVE_NEIGHBORS is defined, the neighbors of each node are */
35 /* remembered, saving some tree traversals for next and prev. */
36 /* */
37 /***************************************************************************/
38
39 #include "machdefs.h"
40 #include "util.h"
41
42 /* #define TRACE */
43 /* #define NEIGHTRACE */
44 #define SAVE_NEIGHBORS
45 /* #define REPORT_DEPTH */
46 #define DUMMY_LEAF
47 #define NO_CLEAR_TO_ROOT
48 /* #define INLINE_CLEAR_TO_ROOT */
49 /* #define INLINE_CLEAR_TO_ROOT2 */
50 #define SKIMPY_NULLS
51 /* #define MUNCHED_SEQUENCE_CODE */
52 #define SEQUENCE_2SPLIT
53 #define UGLY_SPLIT
54
55 typedef struct btree {
56 struct btree *parent;
57 struct btree *child[2];
58 #ifdef INLINE_CLEAR_TO_ROOT
59 struct btree *next;
60 #endif
61 #ifdef SAVE_NEIGHBORS
62 struct btree *neigh[2];
63 #endif
64 int reversed;
65 int value;
66 } btree;
67
68 #ifdef CC_PROTOTYPE_ANSI
69
70 static int
71 cycle_fillin(int *x, int i, btree *p, int r);
72
73 static btree
74 *make_tree (int a, int b, int *cyc),
75 *split (btree **left, btree *i, btree **right),
76 *find_root (btree *i);
77
78 static void
79 join (btree *left, btree *i, btree *right),
80 reverse (btree *p),
81 clearrev_toroot (btree *p);
82
83 #else
84
85 static int
86 cycle_fillin();
87
88 static btree
89 *make_tree (),
90 *split (),
91 *find_root ();
92
93 static void
94 join (),
95 reverse (),
96 clearrev_toroot ();
97
98 #endif
99
100 #ifdef REPORT_DEPTH
101
102 static double probecount = 1.0;
103 static double probedepth = 1.0;
104
105 #ifdef CC_PROTOTYPE_ANSI
106 static void
107 find_depth (int x);
108 #else
109 static void
110 find_depth ();
111 #endif
112
113 #endif /* REPORT_DEPTH */
114
115 #define SWAP(a, b, t) ((t) = (a), (a) = (b), (b) = (t))
116
117 static btree *btree_space = (btree *) NULL;
118 static int btree_size;
119 static btree *root = (btree *) NULL;
120 #ifdef DUMMY_LEAF
121 static btree dummy_leaf;
122 #endif
123
124 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_reset(int ncount)125 int CClinkern_flipper_reset (int ncount)
126 #else
127 int CClinkern_flipper_reset (ncount)
128 int ncount;
129 #endif
130 {
131 return 0;
132 }
133
134 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_init(int ncount,int * cyc)135 int CClinkern_flipper_init (int ncount, int *cyc)
136 #else
137 int CClinkern_flipper_init (ncount, cyc)
138 int ncount;
139 int *cyc;
140 #endif
141 {
142 int i;
143
144 printf ("Flipper flags:");
145 #ifdef SAVE_NEIGHBORS
146 printf (" SAVE_NEIGHBORS");
147 #endif
148 #ifdef DUMMY_LEAF
149 printf (" DUMMY_LEAF");
150 #endif
151 #ifdef NO_CLEAR_TO_ROOT
152 printf (" NO_CLEAR_TO_ROOT");
153 #else
154 #ifdef INLINE_CLEAR_TO_ROOT
155 printf (" INLINE_CLEAR_TO_ROOT");
156 #else
157 #ifdef INLINE_CLEAR_TO_ROOT2
158 printf (" INLINE_CLEAR_TO_ROOT2");
159 #endif
160 #endif
161 #endif
162 #ifdef SKIMPY_NULLS
163 printf (" SKIMPY_NULLS");
164 #endif
165 #ifdef SEQUENCE_2SPLIT
166 printf (" SEQUENCE_2SPLIT");
167 #else
168 #ifdef MUNCHED_SEQUENCE_CODE
169 printf (" MUNCHED_SEQUENCE_CODE");
170 #endif
171 #endif
172 #ifdef UGLY_SPLIT
173 printf (" UGLY_SPLIT");
174 #endif
175 printf ("\n");
176 fflush (stdout);
177
178 btree_space = CC_SAFE_MALLOC (ncount, btree);
179 btree_size = ncount;
180 if (!btree_space)
181 return 1;
182
183 #ifdef TRACE
184 printf ("init:");
185 for (i=0; i<ncount; i++) {
186 printf (" %d", cyc[i]);
187 }
188 printf ("\n");
189 fflush (stdout);
190 #endif /* TRACE */
191 for (i = 0; i < ncount; i++) {
192 btree_space[i].reversed = 0;
193 btree_space[i].value = i;
194 #ifdef SAVE_NEIGHBORS
195 if (i==0) {
196 btree_space[cyc[0]].neigh[0] = &btree_space[cyc[ncount-1]];
197 btree_space[cyc[ncount-1]].neigh[1] = &btree_space[cyc[0]];
198 } else {
199 btree_space[cyc[i]].neigh[0] = &btree_space[cyc[i-1]];
200 btree_space[cyc[i-1]].neigh[1] = &btree_space[cyc[i]];
201 }
202 #endif
203 }
204
205 root = make_tree (0, ncount - 1, cyc);
206 return 0;
207 }
208
209 #ifdef CC_PROTOTYPE_ANSI
cycle_fillin(int * x,int i,btree * p,int r)210 static int cycle_fillin(int *x, int i, btree *p, int r)
211 #else
212 static int cycle_fillin(x, i, p, r)
213 int *x;
214 int i;
215 btree *p;
216 int r;
217 #endif
218 {
219 #ifdef DUMMY_LEAF
220 if (p == &dummy_leaf)
221 #else
222 if (p == (btree *) NULL)
223 #endif
224 return i;
225
226 r ^= p->reversed;
227 i = cycle_fillin (x, i, p->child[r], r);
228 x[i++] = p->value;
229 i = cycle_fillin (x, i, p->child[1 - r], r);
230
231 return i;
232 }
233
234 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_cycle(int * x)235 int CClinkern_flipper_cycle (int *x)
236 #else
237 int CClinkern_flipper_cycle (x)
238 int *x;
239 #endif
240 {
241 #ifdef REPORT_DEPTH
242 printf ("Number of Probes: %.0f Average Depth: %.2f\n",
243 probecount, probedepth / probecount);
244 fflush (stdout);
245 #endif
246 return cycle_fillin (x, 0, root, 0);
247 }
248
249 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_finish(void)250 void CClinkern_flipper_finish (void)
251 #else
252 void CClinkern_flipper_finish ()
253 #endif
254 {
255 if (btree_space)
256 CC_FREE (btree_space, btree);
257
258 root = (btree *) NULL;
259 }
260
261 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_free_world(void)262 void CClinkern_flipper_free_world (void)
263 #else
264 void CClinkern_flipper_free_world ()
265 #endif
266 {
267 return;
268 }
269
270 #ifdef REPORT_DEPTH
271 #ifdef CC_PROTOTYPE_ANSI
find_depth(int x)272 static void find_depth (int x)
273 #else
274 static void find_depth (x)
275 int x;
276 #endif
277 {
278 btree *q = btree_space + x;
279
280 probecount += 1.0;
281 while (q) {
282 probedepth += 1.0;
283 q = q->parent;
284 }
285 }
286 #endif
287
288
289 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_next(int x)290 int CClinkern_flipper_next (int x)
291 #else
292 int CClinkern_flipper_next (x)
293 int x;
294 #endif
295 {
296 btree *p = btree_space + x;
297 btree *pnext;
298 int r;
299
300 #ifdef TRACE
301 printf ("next %d", x);
302 fflush (stdout);
303 #endif /* TRACE */
304 #ifdef REPORT_DEPTH
305 find_depth (x);
306 #endif
307
308 r = 0;
309 for (pnext = p, r = 0; pnext; pnext = pnext->parent)
310 r ^= pnext->reversed;
311 #ifdef SAVE_NEIGHBORS
312 #ifdef TRACE
313 printf ("==> %d (%d)\n", p->neigh[1-r] - btree_space, p->neigh[1-r]->value);
314 fflush (stdout);
315 #endif /* TRACE */
316 return p->neigh[1-r]->value;
317 #else /* SAVE_NEIGHBORS */
318 pnext = p->child[1 - r];
319 #ifdef DUMMY_LEAF
320 if (pnext != &dummy_leaf) {
321 #else
322 if (pnext) {
323 #endif
324 p = pnext;
325 for (;;) {
326 r ^= p->reversed;
327 pnext = p->child[r];
328 #ifdef DUMMY_LEAF
329 if (pnext == &dummy_leaf) {
330 #else
331 if (!pnext) {
332 #endif
333 #ifdef TRACE
334 printf ("==> %d (%d)\n", p - btree_space, p->value);
335 fflush (stdout);
336 #endif /* TRACE */
337 return p->value;
338 }
339 p = pnext;
340 }
341 } else {
342 r ^= p->reversed;
343 pnext = p->parent;
344 while (pnext) {
345 if (pnext->child[r] == p) {
346 #ifdef TRACE
347 printf ("==> %d (%d)\n", pnext - btree_space, pnext->value);
348 fflush (stdout);
349 #endif /* TRACE */
350 return pnext->value;
351 }
352 r ^= pnext->reversed;
353 p = pnext;
354 pnext = p->parent;
355 }
356 for (;;) {
357 r ^= p->reversed;
358 pnext = p->child[r];
359 #ifdef DUMMY_LEAF
360 if (pnext == &dummy_leaf) {
361 #else
362 if (!pnext) {
363 #endif
364 #ifdef TRACE
365 printf ("==> %d (%d)\n", p - btree_space, p->value);
366 fflush (stdout);
367 #endif /* TRACE */
368 return p->value;
369 }
370 p = pnext;
371 }
372 }
373 #endif /* SAVE_NEIGHBORS */
374 }
375
376 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_prev(int x)377 int CClinkern_flipper_prev (int x) /* CClinkern_flipper_prev_nspl */
378 #else
379 int CClinkern_flipper_prev (x)
380 int x;
381 #endif
382 {
383 btree *p = btree_space + x;
384 btree *pnext;
385 int r;
386
387 #ifdef TRACE
388 printf ("prev %d", x);
389 fflush (stdout);
390 #endif /* TRACE */
391 #ifdef REPORT_DEPTH
392 find_depth (x);
393 #endif
394
395 r = 0;
396 for (pnext = p, r = 0; pnext; pnext = pnext->parent)
397 r ^= pnext->reversed;
398 #ifdef SAVE_NEIGHBORS
399 #ifdef TRACE
400 printf ("==> %d (%d)\n", p->neigh[r] - btree_space, p->neigh[r]->value);
401 fflush (stdout);
402 #endif /* TRACE */
403 return p->neigh[r]->value;
404 #else /* SAVE_NEIGHBORS */
405 pnext = p->child[r];
406 #ifdef DUMMY_LEAF
407 if (pnext != &dummy_leaf) {
408 #else
409 if (pnext) {
410 #endif
411 p = pnext;
412 for (;;) {
413 r ^= p->reversed;
414 pnext = p->child[1 - r];
415 #ifdef DUMMY_LEAF
416 if (pnext == &dummy_leaf) {
417 #else
418 if (!pnext) {
419 #endif
420 #ifdef TRACE
421 printf ("==> %d (%d)\n", p - btree_space, p->value);
422 fflush (stdout);
423 #endif /* TRACE */
424 return p->value;
425 }
426 p = pnext;
427 }
428 } else {
429 r ^= p->reversed;
430 pnext = p->parent;
431 while (pnext) {
432 if (pnext->child[1 - r] == p) {
433 #ifdef TRACE
434 printf ("==> %d (%d)\n", pnext - btree_space, pnext->value);
435 fflush (stdout);
436 #endif /* TRACE */
437 return pnext->value;
438 }
439 r ^= pnext->reversed;
440 p = pnext;
441 pnext = p->parent;
442 }
443 for (;;) {
444 r ^= p->reversed;
445 pnext = p->child[1 - r];
446 #ifdef DUMMY_LEAF
447 if (pnext == &dummy_leaf) {
448 #else
449 if (!pnext) {
450 #endif
451 #ifdef TRACE
452 printf ("==> %d (%d)\n", p - btree_space, p->value);
453 fflush (stdout);
454 #endif /* TRACE */
455 return p->value;
456 }
457 p = pnext;
458 }
459 }
460 #endif /* SAVE_NEIGHBORS */
461 }
462
463 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_flip(int xprev,int x,int y,int ynext)464 void CClinkern_flipper_flip (int xprev, int x, int y, int ynext)
465 #else
466 void CClinkern_flipper_flip (xprev, x, y, ynext)
467 int xprev, x, y, ynext;
468 #endif
469 {
470 btree *px = btree_space + x;
471 btree *py = btree_space + y;
472 #ifdef SAVE_NEIGHBORS
473 btree *temp, *temp2;
474 #endif
475 btree *a, *b, *c, *d;
476
477 #ifdef TRACE
478 printf ("flip %d-%d %d-%d\n", xprev, x, y, ynext);
479 fflush (stdout);
480 #endif /* TRACE */
481
482 #ifdef REPORT_DEPTH
483 find_depth (x);
484 find_depth (y);
485 #endif
486
487 if (x == y) return;
488 if (xprev == ynext) {
489 root->reversed ^= 1;
490 return;
491 }
492
493 split (&a, px, &b);
494 if (split (&c, py, &d) == a) { /* c y d x b ==> b^r x d y c^r */
495 if (b) b->reversed ^= 1;
496 if (c) c->reversed ^= 1;
497 join (d,py,c);
498 join (b,px,py);
499 root = px;
500 } else { /* a x c y d ==> a y c^r x d */
501 if (c) c->reversed ^= 1;
502 join (a,py,c);
503 join (py,px,d);
504 root = px;
505 }
506 #ifdef SAVE_NEIGHBORS
507 #ifdef NEIGHTRACE
508 printf ("neigh before:");
509 printf (" %d-%d-%d", px->neigh[0]-btree_space,px-btree_space,px->neigh[1]-btree_space);
510 printf (" %d-%d-%d", py->neigh[0]-btree_space,py-btree_space,py->neigh[1]-btree_space);
511 printf (" %d-%d-%d", px->neigh[0]->neigh[0]-btree_space,px->neigh[0]-btree_space,px->neigh[0]->neigh[1]-btree_space);
512 printf (" %d-%d-%d", px->neigh[1]->neigh[0]-btree_space,px->neigh[1]-btree_space,px->neigh[1]->neigh[1]-btree_space);
513 printf (" %d-%d-%d", py->neigh[0]->neigh[0]-btree_space,py->neigh[0]-btree_space,py->neigh[0]->neigh[1]-btree_space);
514 printf (" %d-%d-%d", py->neigh[1]->neigh[0]-btree_space,py->neigh[1]-btree_space,py->neigh[1]->neigh[1]-btree_space);
515 printf ("\n");
516 fflush (stdout);
517 #endif
518
519 temp = px->neigh[0];
520 temp2 = py->neigh[1];
521 px->neigh[0] = px->neigh[1];
522 py->neigh[1] = py->neigh[0];
523 py->neigh[0] = temp;
524 px->neigh[1] = temp2;
525 if (temp->neigh[0] == px) temp->neigh[0] = py;
526 else temp->neigh[1] = py;
527 if (temp2->neigh[0] == py) temp2->neigh[0] = px;
528 else temp2->neigh[1] = px;
529 #ifdef NEIGHTRACE
530 printf ("neigh after:");
531 printf (" %d-%d-%d", px->neigh[0]-btree_space,px-btree_space,px->neigh[1]-btree_space);
532 printf (" %d-%d-%d", py->neigh[0]-btree_space,py-btree_space,py->neigh[1]-btree_space);
533 printf (" %d-%d-%d", px->neigh[0]->neigh[0]-btree_space,px->neigh[0]-btree_space,px->neigh[0]->neigh[1]-btree_space);
534 printf (" %d-%d-%d", px->neigh[1]->neigh[0]-btree_space,px->neigh[1]-btree_space,px->neigh[1]->neigh[1]-btree_space);
535 printf (" %d-%d-%d", py->neigh[0]->neigh[0]-btree_space,py->neigh[0]-btree_space,py->neigh[0]->neigh[1]-btree_space);
536 printf (" %d-%d-%d", py->neigh[1]->neigh[0]-btree_space,py->neigh[1]-btree_space,py->neigh[1]->neigh[1]-btree_space);
537 printf ("\n");
538 fflush (stdout);
539 #endif
540 #endif
541 }
542
543 #if defined(MUNCHED_SEQUENCE_CODE) || defined(SEQUENCE_2SPLIT)
544
545 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_sequence(int x,int y,int z)546 int CClinkern_flipper_sequence (int x, int y, int z)
547 #else
548 int CClinkern_flipper_sequence (x, y, z)
549 int x, y, z;
550 #endif
551 {
552 btree *px = btree_space + x;
553 btree *py = btree_space + y;
554 btree *pz = btree_space + z;
555 btree *a, *b, *c, *d, *e, *f;
556 btree *r;
557
558 #ifdef TRACE
559 printf ("sequence %d %d %d", x, y, z);
560 fflush (stdout);
561 #endif /* TRACE */
562 #ifdef REPORT_DEPTH
563 find_depth (x);
564 find_depth (y);
565 find_depth (z);
566 #endif
567
568 if (y == z || x == z || x == y) {
569 #ifdef TRACE
570 printf (" ==> 1\n");
571 fflush (stdout);
572 #endif /* TRACE */
573 return 1;
574 }
575
576 split (&a, px, &b);
577 if (split (&c, pz, &d) == a) { /* c z d x b */
578 #ifdef SEQUENCE_2SPLIT
579 r = find_root (py);
580 join (c,pz,d);
581 join (pz,px,b);
582 root = px;
583 #ifdef TRACE
584 printf (" ==> %d\n", r!=d);
585 fflush (stdout);
586 #endif /* TRACE */
587 return (r!=d);
588 #else /* SEQUENCE_2SPLIT */
589 r = split (&e, py, &f);
590 if (r == c) { /* e y f z d x b */
591 join (e, py, f);
592 join (py, pz, d);
593 join (pz, px, b);
594 root = px;
595 #ifdef TRACE
596 printf (" ==> 1\n");
597 fflush (stdout);
598 #endif /* TRACE */
599 return 1;
600 } else if (r == d) { /* c z e y f x b */
601 join (c, pz, e);
602 join (pz, py, f);
603 join (py, px, b);
604 root = px;
605 #ifdef TRACE
606 printf (" ==> 0\n");
607 fflush (stdout);
608 #endif /* TRACE */
609 return 0;
610 } else { /* c z d x e y f */
611 join (c, pz, d);
612 join (e, py, f);
613 join (pz, px, py);
614 root = px;
615 #ifdef TRACE
616 printf (" ==> 1\n");
617 fflush (stdout);
618 #endif /* TRACE */
619 return 1;
620 }
621 #endif /* SEQUENCE_2SPLIT */
622 } else { /* a x c z d */
623 #ifdef SEQUENCE_2SPLIT
624 r = find_root (py);
625 join (c,pz,d);
626 join (a,px,pz);
627 root = px;
628 #ifdef TRACE
629 printf (" ==> %d\n", r==c);
630 fflush (stdout);
631 #endif /* TRACE */
632 return (r==c);
633 #else /* SEQUENCE_2SPLIT */
634 r = split (&e, py, &f);
635 if (r == a) { /* e y f x c z d */
636 join (e, py, f);
637 join (c, pz, d);
638 join (py, px, pz);
639 root = px;
640 #ifdef TRACE
641 printf (" ==> 0\n");
642 fflush (stdout);
643 #endif /* TRACE */
644 return 0;
645 } else if (r == c) { /* a x e y f z d */
646 join (e, py, f);
647 join (py, pz, d);
648 join (a, px, pz);
649 root = px;
650 #ifdef TRACE
651 printf (" ==> 1\n");
652 fflush (stdout);
653 #endif /* TRACE */
654 return 1;
655 } else { /* a x c z e y f */
656 join (e, py, f);
657 join (c, pz, py);
658 join (a, px, pz);
659 root = px;
660 #ifdef TRACE
661 printf (" ==> 0\n");
662 fflush (stdout);
663 #endif /* TRACE */
664 return 0;
665 }
666 #endif /* SEQUENCE_2SPLIT */
667 }
668 }
669
670 #else /* defined(MUNCHED_SEQUENCE_CODE) || defined(SEQUENCE_2SPLIT) */
671
672 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_sequence(int x,int y,int z)673 int CClinkern_flipper_sequence (int x, int y, int z)
674 #else
675 int CClinkern_flipper_sequence (x, y, z)
676 int x, y, z;
677 #endif
678 {
679 btree *px = btree_space + x;
680 btree *py = btree_space + y;
681 btree *pz = btree_space + z;
682 btree *a, *b, *c, *d, *e, *f;
683 btree *r;
684
685 #ifdef TRACE
686 printf ("sequence %d %d %d", x, y, z);
687 fflush (stdout);
688 #endif /* TRACE */
689 #ifdef REPORT_DEPTH
690 find_depth (x);
691 find_depth (y);
692 find_depth (z);
693 #endif
694
695 if (y == z || x == z || x == y) {
696 #ifdef TRACE
697 printf (" ==> 1\n");
698 fflush (stdout);
699 #endif /* TRACE */
700 return 1;
701 }
702
703 split (&a, px, &b);
704 if (split (&c, py, &d) == a) { /* c y d x b */
705 r = split (&e, pz, &f);
706 if (r == c) { /* e z f y d x b */
707 join (e, pz, f);
708 join (d, px, b);
709 join (pz, py, px);
710 root = py;
711 #ifdef TRACE
712 printf (" ==> 0\n");
713 fflush (stdout);
714 #endif /* TRACE */
715 return 0;
716 } else if (r == d) { /* c y e z f x b */
717 join (c, py, e);
718 join (f, px, b);
719 join (py, pz, px);
720 root = pz;
721 #ifdef TRACE
722 printf (" ==> 1\n");
723 fflush (stdout);
724 #endif /* TRACE */
725 return 1;
726 } else { /* c y d x e z f */
727 join (c, py, d);
728 join (e, pz, f);
729 join (py, px, pz);
730 root = px;
731 #ifdef TRACE
732 printf (" ==> 0\n");
733 fflush (stdout);
734 #endif /* TRACE */
735 return 0;
736 }
737 } else { /* a x c y d */
738 r = split (&e, pz, &f);
739 if (r == a) { /* e z f x c y d */
740 join (e, pz, f);
741 join (c, py, d);
742 join (pz, px, py);
743 root = px;
744 #ifdef TRACE
745 printf (" ==> 1\n");
746 fflush (stdout);
747 #endif /* TRACE */
748 return 1;
749 } else if (r == c) { /* a x e z f y d */
750 join (a, px, e);
751 join (f, py, d);
752 join (px, pz, py);
753 root = pz;
754 #ifdef TRACE
755 printf (" ==> 0\n");
756 fflush (stdout);
757 #endif /* TRACE */
758 return 0;
759 } else { /* a x c y e z f */
760 join (a, px, c);
761 join (e, pz, f);
762 join (px, py, pz);
763 root = py;
764 #ifdef TRACE
765 printf (" ==> 1\n");
766 fflush (stdout);
767 #endif /* TRACE */
768 return 1;
769 }
770 }
771 }
772
773 #endif /* defined(MUNCHED_SEQUENCE_CODE) || defined(SEQUENCE_2SPLIT) */
774
775 /***************************************************************************/
776 /* */
777 /* REVERSIBLE BINARY TREE ROUTINES (UNBALANCED) */
778 /* */
779 /* TSP CODE */
780 /* */
781 /* */
782 /* Written by: Applegate, Bixby, Chvatal, and Cook */
783 /* Date: November 16, 1995 */
784 /* */
785 /* */
786 /* btree *make_tree (int a, int b, int *cyc) */
787 /* builds a binary tree for cyc[a..b] and returns the root. */
788 /* This assumes that btree_space has been allocated and initialized. */
789 /* void join (btree *left, btree *i, btree *right) */
790 /* makes left and right the children of i. */
791 /* btree *split (btree **left, btree *i, btree **right) */
792 /* splits the tree into *left (nodes < i) and *right (nodes > i) */
793 /* returns the root of the (old) tree containing i. */
794 /* void reverse (btree *p) */
795 /* toggles the reversal bit of node p (and fixes the tree). */
796 /* void clearrev_toroot (btree *p) */
797 /* clears the reversal bits on the path from p to the root (and fixes */
798 /* the tree). */
799 /* btree *find_root (btree *i) */
800 /* returns the root of the tree containing i */
801 /* */
802 /***************************************************************************/
803
804 #ifdef TRACE
dump_tree(btree * r,int rev)805 void dump_tree (btree *r, int rev)
806 {
807 if (!r) {
808 printf ("()");
809 return;
810 }
811 rev ^= r->reversed;
812 putchar ('(');
813 if (r->child[rev]) dump_tree (r->child[rev], rev);
814 printf (" %d%s ", r-btree_space, r->reversed?"R":"");
815 if (r->child[1-rev]) dump_tree (r->child[1-rev], rev);
816 putchar (')');
817 }
818 #endif
819
820 #ifdef CC_PROTOTYPE_ANSI
make_tree(int a,int b,int * cyc)821 static btree *make_tree (int a, int b, int *cyc)
822 #else
823 static btree *make_tree (a, b, cyc)
824 int a;
825 int b;
826 int *cyc;
827 #endif
828 {
829 btree *p;
830 int center;
831
832 if (b < a)
833 #ifdef DUMMY_LEAF
834 return &dummy_leaf;
835 #else
836 return (btree *) NULL;
837 #endif
838
839 center = (a + b)/2;
840 p = btree_space + cyc[center];
841 p->child[0] = make_tree (a, center-1, cyc);
842 #ifdef DUMMY_LEAF
843 p->child[0]->parent = p;
844 #else
845 if (p->child[0]) p->child[0]->parent = p;
846 #endif
847 p->child[1] = make_tree (center+1, b, cyc);
848 #ifdef DUMMY_LEAF
849 p->child[1]->parent = p;
850 #else
851 if (p->child[1]) p->child[1]->parent = p;
852 #endif
853 return p;
854 }
855
856 #ifdef CC_PROTOTYPE_ANSI
join(btree * left,btree * i,btree * right)857 static void join (btree *left, btree *i, btree *right)
858 #else
859 static void join (left, i, right)
860 btree *left;
861 btree *i;
862 btree *right;
863 #endif
864 {
865 #ifdef TRACE
866 printf ("join ");
867 dump_tree (left, 0);
868 printf (" %d ", i - btree_space);
869 dump_tree (right, 0);
870 printf ("\n");
871 fflush (stdout);
872 #endif /* TRACE */
873 #ifdef DUMMY_LEAF
874 left->parent = i;
875 right->parent = i;
876 #else
877 if (left) left->parent = i;
878 if (right) right->parent = i;
879 #endif
880 i->child[0] = left;
881 i->child[1] = right;
882 i->reversed = 0;
883 #ifdef SKIMPY_NULLS
884 i->parent = (btree *) NULL;
885 #endif
886 #ifdef TRACE
887 printf ("==> ");
888 dump_tree (i, 0);
889 printf ("\n");
890 fflush (stdout);
891 #endif /* TRACE */
892 }
893
894 #ifdef UGLY_SPLIT
895
896 #ifdef CC_PROTOTYPE_ANSI
split(btree ** left,btree * i,btree ** right)897 static btree *split (btree **left, btree *i, btree **right)
898 #else
899 static btree *split (left, i, right)
900 btree **left;
901 btree *i;
902 btree **right;
903 #endif
904 {
905 btree *l;
906 btree *r;
907 btree *p;
908 #if defined(SAVE_NEIGHBORS) && defined(NO_CLEAR_TO_ROOT)
909 int rev = i->reversed;
910 btree *t;
911 #endif
912
913 #ifdef TRACE
914 printf ("split %d ", i - btree_space);
915 dump_tree (find_root (i), 0);
916 printf ("\n");
917 fflush (stdout);
918 #endif /* TRACE */
919
920 #ifdef NO_CLEAR_TO_ROOT
921 if (i->reversed) {
922 l = i->child[1];
923 r = i->child[0];
924 #ifdef DUMMY_LEAF
925 l->reversed ^= 1;
926 r->reversed ^= 1;
927 #else
928 if (l) l->reversed ^= 1;
929 if (r) r->reversed ^= 1;
930 #endif
931 #ifndef SKIMPY_NULLS
932 i->reversed = 0;
933 #endif
934 } else {
935 l = i->child[0];
936 r = i->child[1];
937 }
938 #else
939 clearrev_toroot (i);
940 l = i->child[0];
941 r = i->child[1];
942 #endif
943
944 #ifndef SKIMPY_NULLS
945 #ifdef DUMMY_LEAF
946 i->child[0] = &dummy_leaf;
947 i->child[1] = &dummy_leaf;
948 #else
949 i->child[0] = (btree *) NULL;
950 i->child[1] = (btree *) NULL;
951 #endif
952 #endif
953
954 p = i->parent;
955 if (!p) {p = i; goto FINISH;}
956 else if (p->child[0] == i) goto START_0;
957 else goto START_1;
958
959 I_IS_L:
960 if (p->parent == (btree *) NULL) goto FINISH;
961 p = p->parent;
962 if (p->child[1] == l) {
963 #ifdef NO_CLEAR_TO_ROOT
964 if (p->reversed) {
965 l = r;
966 r = p;
967 #ifdef DUMMY_LEAF
968 l->reversed ^= 1;
969 #else
970 if (l) l->reversed ^= 1;
971 #endif
972 #ifdef SAVE_NEIGHBORS
973 rev ^= 1;
974 #endif
975 goto I_IS_R;
976 } else {
977 l = p;
978 goto I_IS_L;
979 }
980 #else
981 l = p;
982 goto I_IS_L;
983 #endif
984 } else {
985 START_0:
986 p->child[0] = r;
987 #ifdef DUMMY_LEAF
988 r->parent = p;
989 #else
990 if (r) r->parent = p;
991 #endif
992 #ifdef NO_CLEAR_TO_ROOT
993 if (p->reversed) {
994 r = l;
995 l = p;
996 #ifdef DUMMY_LEAF
997 r->reversed ^= 1;
998 #else
999 if (r) r->reversed ^= 1;
1000 #endif
1001 #ifdef SAVE_NEIGHBORS
1002 rev ^= 1;
1003 #endif
1004 goto I_IS_L;
1005 } else {
1006 r = p;
1007 goto I_IS_R;
1008 }
1009 #else
1010 r = p;
1011 goto I_IS_R;
1012 #endif
1013 }
1014 I_IS_R:
1015 if (p->parent == (btree *) NULL) goto FINISH;
1016 p = p->parent;
1017 if (p->child[0] == r) {
1018 #ifdef NO_CLEAR_TO_ROOT
1019 if (p->reversed) {
1020 r = l;
1021 l = p;
1022 #ifdef DUMMY_LEAF
1023 r->reversed ^= 1;
1024 #else
1025 if (r) r->reversed ^= 1;
1026 #endif
1027 #ifdef SAVE_NEIGHBORS
1028 rev ^= 1;
1029 #endif
1030 goto I_IS_L;
1031 } else {
1032 r = p;
1033 goto I_IS_R;
1034 }
1035 #else
1036 r = p;
1037 goto I_IS_R;
1038 #endif
1039 } else {
1040 START_1:
1041 p->child[1] = l;
1042 #ifdef DUMMY_LEAF
1043 l->parent = p;
1044 #else
1045 if (l) l->parent = p;
1046 #endif
1047 #ifdef NO_CLEAR_TO_ROOT
1048 if (p->reversed) {
1049 l = r;
1050 r = p;
1051 #ifdef DUMMY_LEAF
1052 l->reversed ^= 1;
1053 #else
1054 if (l) l->reversed ^= 1;
1055 #endif
1056 #ifdef SAVE_NEIGHBORS
1057 rev ^= 1;
1058 #endif
1059 goto I_IS_R;
1060 } else {
1061 l = p;
1062 goto I_IS_L;
1063 }
1064 #else
1065 l = p;
1066 goto I_IS_L;
1067 #endif
1068 }
1069
1070 FINISH:
1071 #ifdef DUMMY_LEAF
1072 l->parent = (btree *) NULL;
1073 r->parent = (btree *) NULL;
1074 #else
1075 if (l) l->parent = (btree *) NULL;
1076 if (r) r->parent = (btree *) NULL;
1077 #endif
1078 *left = l;
1079 *right = r;
1080 #ifndef SKIMPY_NULLS
1081 i->parent = (btree *) NULL;
1082 #endif
1083 #if defined(SAVE_NEIGHBORS) && defined(NO_CLEAR_TO_ROOT)
1084 if (rev) SWAP (i->neigh[0], i->neigh[1], t);
1085 #endif
1086
1087 #ifdef TRACE
1088 printf ("==> ");
1089 dump_tree (l, 0);
1090 printf (" %d ", i - btree_space);
1091 dump_tree (r, 0);
1092 printf (" ret %d\n", p - btree_space);
1093 fflush (stdout);
1094 #endif /* TRACE */
1095 return p;
1096 }
1097
1098 #else /* UGLY_SPLIT */
1099
1100 #ifdef CC_PROTOTYPE_ANSI
split(btree ** left,btree * i,btree ** right)1101 static btree *split (btree **left, btree *i, btree **right)
1102 #else
1103 static btree *split (left, i, right)
1104 btree **left;
1105 btree *i;
1106 btree **right;
1107 #endif
1108 {
1109 btree *l;
1110 btree *r;
1111 btree *p;
1112 #if defined(SAVE_NEIGHBORS) || !defined(SKIMPY_NULLS)
1113 btree *isave = i;
1114 #endif
1115 #if defined(SAVE_NEIGHBORS) && defined(NO_CLEAR_TO_ROOT)
1116 int rev = i->reversed;
1117 #endif
1118
1119 #ifdef TRACE
1120 printf ("split %d ", i - btree_space);
1121 dump_tree (find_root (i), 0);
1122 printf ("\n");
1123 fflush (stdout);
1124 #endif /* TRACE */
1125
1126 #ifdef NO_CLEAR_TO_ROOT
1127 if (i->reversed) {
1128 l = i->child[1];
1129 r = i->child[0];
1130 #ifdef DUMMY_LEAF
1131 l->reversed ^= 1;
1132 r->reversed ^= 1;
1133 #else
1134 if (l) l->reversed ^= 1;
1135 if (r) r->reversed ^= 1;
1136 #endif
1137 #ifndef SKIMPY_NULLS
1138 i->reversed = 0;
1139 #endif
1140 } else {
1141 l = i->child[0];
1142 r = i->child[1];
1143 }
1144 #else
1145 clearrev_toroot (i);
1146 l = i->child[0];
1147 r = i->child[1];
1148 #endif
1149
1150 #ifndef SKIMPY_NULLS
1151 #ifdef DUMMY_LEAF
1152 i->child[0] = &dummy_leaf;
1153 i->child[1] = &dummy_leaf;
1154 #else
1155 i->child[0] = (btree *) NULL;
1156 i->child[1] = (btree *) NULL;
1157 #endif
1158 #endif
1159
1160 while ((p = i->parent) != (btree *) NULL) {
1161 if (p->child[0] == i) {
1162 p->child[0] = r;
1163 #ifdef DUMMY_LEAF
1164 r->parent = p;
1165 #else
1166 if (r) r->parent = p;
1167 #endif
1168 #ifdef NO_CLEAR_TO_ROOT
1169 if (p->reversed) {
1170 r = l;
1171 l = p;
1172 #ifdef DUMMY_LEAF
1173 r->reversed ^= 1;
1174 #else
1175 if (r) r->reversed ^= 1;
1176 #endif
1177 #ifdef SAVE_NEIGHBORS
1178 rev ^= 1;
1179 #endif
1180 } else {
1181 r = p;
1182 }
1183 #else
1184 r = p;
1185 #endif
1186 } else {
1187 p->child[1] = l;
1188 #ifdef DUMMY_LEAF
1189 l->parent = p;
1190 #else
1191 if (l) l->parent = p;
1192 #endif
1193 #ifdef NO_CLEAR_TO_ROOT
1194 if (p->reversed) {
1195 l = r;
1196 r = p;
1197 #ifdef DUMMY_LEAF
1198 l->reversed ^= 1;
1199 #else
1200 if (l) l->reversed ^= 1;
1201 #endif
1202 #ifdef SAVE_NEIGHBORS
1203 rev ^= 1;
1204 #endif
1205 } else {
1206 l = p;
1207 }
1208 #else
1209 l = p;
1210 #endif
1211 }
1212 i = p;
1213 }
1214 #ifdef DUMMY_LEAF
1215 l->parent = (btree *) NULL;
1216 r->parent = (btree *) NULL;
1217 #else
1218 if (l) l->parent = (btree *) NULL;
1219 if (r) r->parent = (btree *) NULL;
1220 #endif
1221 *left = l;
1222 *right = r;
1223 #ifndef SKIMPY_NULLS
1224 isave->parent = (btree *) NULL;
1225 #endif
1226 #if defined(SAVE_NEIGHBORS) && defined(NO_CLEAR_TO_ROOT)
1227 if (rev) SWAP (isave->neigh[0], isave->neigh[1], p);
1228 #endif
1229
1230 #ifdef TRACE
1231 printf ("==> ");
1232 dump_tree (l, 0);
1233 printf (" %d ", isave - btree_space);
1234 dump_tree (r, 0);
1235 printf (" ret %d\n", i - btree_space);
1236 fflush (stdout);
1237 #endif /* TRACE */
1238 return i;
1239 }
1240
1241 #endif /* UGLY_SPLIT */
1242
1243 #ifdef CC_PROTOTYPE_ANSI
reverse(btree * p)1244 static void reverse (btree *p)
1245 #else
1246 static void reverse (p)
1247 btree *p;
1248 #endif
1249 {
1250 btree *t;
1251
1252 SWAP(p->child[0], p->child[1], t);
1253 #ifdef DUMMY_LEAF
1254 p->child[0]->reversed ^= 1;
1255 p->child[1]->reversed ^= 1;
1256 #else
1257 if (p->child[0]) p->child[0]->reversed ^= 1;
1258 if (p->child[1]) p->child[1]->reversed ^= 1;
1259 #endif
1260 p->reversed ^= 1;
1261 #ifdef SAVE_NEIGHBORS
1262 SWAP (p->neigh[0], p->neigh[1], t);
1263 #endif
1264 }
1265
1266 #ifdef CC_PROTOTYPE_ANSI
clearrev_toroot(btree * p)1267 static void clearrev_toroot (btree *p)
1268 #else
1269 static void clearrev_toroot (p)
1270 btree *p;
1271 #endif
1272 {
1273 #ifdef INLINE_CLEAR_TO_ROOT
1274 p->next = (btree *) NULL;
1275 while (p->parent) {
1276 p->parent->next = p;
1277 p = p->parent;
1278 }
1279 while (p) {
1280 if (p->reversed) reverse (p);
1281 p = p->next;
1282 }
1283 #else
1284 #ifdef INLINE_CLEAR_TO_ROOT2
1285 int rev;
1286 btree *q;
1287
1288 for (q = p, rev = 0; q; q = q->parent) rev ^= q->reversed;
1289 if (rev) reverse(p);
1290 while (p->parent) {
1291 if (p->reversed) reverse(p->parent);
1292 p = p->parent;
1293 }
1294 #else
1295 if (p->parent) clearrev_toroot (p->parent);
1296 if (p->reversed) reverse (p);
1297 #endif
1298 #endif
1299 }
1300
1301 #ifdef CC_PROTOTYPE_ANSI
find_root(btree * i)1302 static btree *find_root (btree *i)
1303 #else
1304 static btree *find_root (i)
1305 btree *i;
1306 #endif
1307 {
1308 while (i->parent) i = i->parent;
1309 return i;
1310 }
1311