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