1 /***************************************************************************/
2 /* */
3 /* TOUR MAINTANENCE ROUTINES FOR LIN-KERNIGHAN - Segments with UNDO */
4 /* - No perm mucks */
5 /* */
6 /* TSP CODE */
7 /* */
8 /* */
9 /* Written by: Applegate, Bixby, Chvatal, and Cook */
10 /* Date: April 24, 1995 (but mainly from March, 1990) */
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_reset_temp (int ncount) */
18 /* reinitializes the cycle to the current cycle - use this to keep the */
19 /* number of segments small. */
20 /* int CClinkern_flipper_cycle (int *p) */
21 /* places the current cycle in p. */
22 /* returns the number of segments in current representation. */
23 /* void CClinkern_flipper_finish (void) */
24 /* frees up temporary space allocated by CClinkern_flipper_init. */
25 /* every flipper_init should lead to a flipper_finish call. */
26 /* void CClinkern_flipper_free_world (void) */
27 /* frees up all remaining space (including ptrs) */
28 /* should be called when we are finished with linkern */
29 /* int CClinkern_flipper_next (int x) */
30 /* returns the successor to x in the current cycle. */
31 /* int CClinkern_flipper_prev (int x) */
32 /* returns the predecessor of x in the current cycle. */
33 /* void CClinkern_flipper_flip (int x, int y) */
34 /* flips the portion of the cycle from x to y (inclusive). */
35 /* int CClinkern_flipper_sequence (int * x, int y, int z) */
36 /* returns 1 if xyz occur as an increasing subsequence of the cycle, */
37 /* returns 0 otherwise. */
38 /* */
39 /* NOTES: */
40 /* This version is closest to our orignal segment code. It undos the */
41 /* flips that do not lead to an improvement. */
42 /* */
43 /***************************************************************************/
44
45 #include "machdefs.h"
46 #include "util.h"
47
48 #define USE_TIMESTAMP
49
50 /***************************************************************************/
51 /* */
52 /* FULL SEGMENT FLIPPER (flipper1): */
53 /* */
54 /* 1. CClinkern_flipper_cycle and CClinkern_flipper_cycle_inverse */
55 /* return the current number of segments. */
56 /* */
57 /* 2. this version wants to keep the segment tree around until a */
58 /* Lin-Kern round is complete. If its an improving round, then */
59 /* the perm tour is updated. If its not a winner, then the segment */
60 /* tree is discarded. Sounds like it would be okay late in a run */
61 /* not many winners are found (do not use ACCEPT_TIES), but the big */
62 /* trees lead to long searches for the segment containing a node. */
63 /* */
64 /***************************************************************************/
65
66
67 typedef struct flipper1 {
68 struct {
69 struct flipper1 *parent;
70 struct flipper1 *lower;
71 struct flipper1 *higher;
72 } locate;
73 struct {
74 struct flipper1 *left;
75 struct flipper1 *right;
76 } order;
77 int low;
78 int high;
79 int reverse;
80 struct flipper1 *next;
81 } flipper1;
82
83 #ifdef USE_TIMESTAMP
84 typedef struct cacheobj {
85 struct flipper1 *segment;
86 int stamp;
87 } cacheobj;
88 #endif
89
90
91 #ifdef CC_PROTOTYPE_ANSI
92
93 static void
94 flipper1_tree_delete (flipper1 *),
95 flipper1_merge (flipper1 *),
96 flipper1_checkmerge (flipper1 *),
97 flipper1free (flipper1 *p),
98 flipper1_tree_free (flipper1 *, flipper1 *);
99
100 static flipper1
101 *flipper1_locate (int x),
102 *flipper1_split (flipper1 *, int);
103
104 #else
105
106 static void
107 flipper1_tree_delete (),
108 flipper1_merge (),
109 flipper1_checkmerge (),
110 flipper1free (),
111 flipper1_tree_free ();
112
113 static flipper1
114 *flipper1_locate (),
115 *flipper1_split ();
116
117 #endif
118
119 #define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
120
121 #define LOCATE_CHILD(p, c) (*((p) ? ((p)->locate.lower == (c) ? \
122 &(p)->locate.lower : &(p)->locate.higher) : \
123 &locate_root))
124
125 #define PARENT_HOOKUP(q, p, c) (((q)->locate.parent = (p)), \
126 (LOCATE_CHILD((p),(c)) = (q)))
127
128 #define HIGHER_HOOKUP(p, c) (((p)->locate.higher = (c)), \
129 ((c) ? (c)->locate.parent = (p) : (flipper1 *) NULL))
130
131 #define LOWER_HOOKUP(p, c) (((p)->locate.lower = (c)), \
132 ((c) ? (c)->locate.parent = (p) : (flipper1 *) NULL))
133
134 static flipper1 *locate_root = (flipper1 *) NULL;
135 static flipper1 *order_root = (flipper1 *) NULL;
136 #ifdef USE_TIMESTAMP
137 static cacheobj *locate_cache = (cacheobj *) NULL;
138 static int locate_cache_magic = 0;
139 #else
140 static flipper1 **locate_cache = (flipper1 **) NULL;
141 #endif
142
143 static int *flip1_cyc = (int *) NULL;
144 static int *flip1_inv = (int *) NULL;
145 static int reversed = 0;
146 static int short_size = 0;
147 static int cycle_size = 0;
148 static int segment_count = 1;
149
150 /*
151 static double totalsize = 1.0;
152 static double totaldepth = 1.0;
153 static int depthcalls = 1;
154 */
155
CC_PTR_ALLOC_ROUTINE(flipper1,flipper1alloc,flipper1chunklist,flipper1freelist)156 CC_PTR_ALLOC_ROUTINE (flipper1, flipper1alloc, flipper1chunklist,
157 flipper1freelist)
158 CC_PTR_FREE_WORLD_ROUTINE (flipper1, flipper1free_world, flipper1chunklist,
159 flipper1freelist)
160 CC_PTR_LEAKS_ROUTINE (flipper1, flipper1_check_leaks, flipper1chunklist,
161 flipper1freelist, reverse, int)
162
163 #ifdef CC_PROTOTYPE_ANSI
164 static void flipper1free (flipper1 *p)
165 #else
166 static void flipper1free (p)
167 flipper1 *p;
168 #endif
169 {
170 p->next = flipper1freelist;
171 flipper1freelist = p;
172 p->low = p->high = -1;
173 }
174
175 #ifdef CC_PROTOTYPE_ANSI
flipper1_tree_free(flipper1 * p,flipper1 * bigp)176 static void flipper1_tree_free (flipper1 *p, flipper1 *bigp)
177 #else
178 static void flipper1_tree_free (p, bigp)
179 flipper1 *p, *bigp;
180 #endif
181 {
182 if (p) {
183 flipper1_tree_free (p->locate.lower, bigp);
184 flipper1_tree_free (p->locate.higher, bigp);
185 if (p != bigp)
186 flipper1free (p);
187 }
188 }
189
190 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_reset_perm(int ncount)191 int CClinkern_flipper_reset_perm (int ncount)
192 #else
193 int CClinkern_flipper_reset_perm (ncount)
194 int ncount;
195 #endif
196 {
197 flipper1_tree_free (locate_root, (flipper1 *) NULL);
198 locate_root = flipper1alloc ();
199 if (!locate_root)
200 return 1;
201
202 order_root = locate_root;
203 locate_root->locate.lower = (flipper1 *) NULL;
204 locate_root->locate.higher = (flipper1 *) NULL;
205 locate_root->order.left = locate_root;
206 locate_root->order.right = locate_root;
207 locate_root->low = 0;
208 locate_root->high = cycle_size - 1;
209 locate_root->reverse = reversed;
210 segment_count = 1;
211 locate_cache_magic++;
212
213 /*
214 printf ("Locate Calls: %d Depth: %.0f Size: %.0f\n",
215 depthcalls, totaldepth/depthcalls, totalsize/depthcalls);
216 fflush (stdout);
217 */
218
219 return 0;
220 }
221
222 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_reset_temp(int ncount)223 int CClinkern_flipper_reset_temp (int ncount)
224 #else
225 int CClinkern_flipper_reset_temp (ncount)
226 int ncount;
227 #endif
228 {
229 int i, n, *cyc = (int *) NULL;
230 int nseg = 0, big = 0, bigreverse = 0;
231 flipper1 *p, *bigp = (flipper1 *) NULL;
232
233 /*
234 printf ("CClinkern_flipper_reset_temp ....\n"); fflush (stdout);
235 printf ("Locate Calls: %d Depth: %.0f Size: %.0f\n",
236 depthcalls, totaldepth/depthcalls, totalsize/depthcalls);
237 fflush (stdout);
238 */
239
240 p = order_root;
241 do {
242 if (p->high - p->low > big) {
243 big = p->high - p->low;
244 bigp = p;
245 }
246 nseg++;
247 p = p->order.right;
248 } while (p != order_root);
249
250 if (nseg == 1)
251 return 0;
252
253 cyc = CC_SAFE_MALLOC (ncount, int);
254 if (!cyc) {
255 #ifdef USE_TIMESTAMP
256 CC_FREE (locate_cache, cacheobj);
257 #else
258 CC_FREE (locate_cache, flipper1 *);
259 #endif
260 return 1;
261 }
262 if (bigp->reverse) {
263 bigreverse = 1;
264 p = bigp->order.left;
265 n = bigp->high + 1;
266 do {
267 if (!p->reverse) {
268 for (i = p->high; i >= p->low; i--) {
269 if (n == ncount)
270 n = 0;
271 cyc[n++] = flip1_cyc[i];
272 }
273 } else {
274 for (i = p->low; i <= p->high; i++) {
275 if (n == ncount)
276 n = 0;
277 cyc[n++] = flip1_cyc[i];
278 }
279 }
280 p = p->order.left;
281 } while (p != bigp);
282 } else {
283 bigreverse = 0;
284 p = bigp->order.right;
285 n = bigp->high + 1;
286 do {
287 if (p->reverse) {
288 for (i = p->high; i >= p->low; i--) {
289 if (n == ncount)
290 n = 0;
291 cyc[n++] = flip1_cyc[i];
292 }
293 } else {
294 for (i = p->low; i <= p->high; i++) {
295 if (n == ncount)
296 n = 0;
297 cyc[n++] = flip1_cyc[i];
298 }
299 }
300 p = p->order.right;
301 } while (p != bigp);
302 }
303
304 for (i = bigp->high + 1; i < ncount; i++) {
305 flip1_cyc[i] = cyc[i];
306 flip1_inv[cyc[i]] = i;
307 #ifndef USE_TIMESTAMP
308 locate_cache[i] = bigp;
309 #endif
310 }
311 for (i = 0; i < bigp->low; i++) {
312 flip1_cyc[i] = cyc[i];
313 flip1_inv[cyc[i]] = i;
314 #ifndef USE_TIMESTAMP
315 locate_cache[i] = bigp;
316 #endif
317 }
318 if (cyc)
319 CC_FREE (cyc, int);
320
321
322 #ifdef USE_TIMESTAMP
323 flipper1_tree_free (locate_root, (flipper1 *) NULL);
324 locate_root = flipper1alloc ();
325 if (!locate_root)
326 return 1;
327 #else
328 flipper1_tree_free (locate_root, bigp);
329 locate_root = bigp;
330 #endif
331
332 order_root = locate_root;
333 locate_root->locate.parent = (flipper1 *) NULL;
334 locate_root->locate.lower = (flipper1 *) NULL;
335 locate_root->locate.higher = (flipper1 *) NULL;
336 locate_root->order.left = locate_root;
337 locate_root->order.right = locate_root;
338 locate_root->low = 0;
339 locate_root->high = ncount - 1;
340 locate_root->reverse = bigreverse;
341 segment_count = 1;
342 reversed = bigreverse;
343
344 #ifdef USE_TIMESTAMP
345 locate_cache_magic++;
346 #endif
347
348 return 0;
349 }
350
351 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_init(int ncount,int * cyc)352 int CClinkern_flipper_init (int ncount, int *cyc)
353 #else
354 int CClinkern_flipper_init (ncount, cyc)
355 int ncount;
356 int *cyc;
357 #endif
358 {
359 int i;
360
361 locate_root = flipper1alloc ();
362 if (!locate_root)
363 return 1;
364 order_root = locate_root;
365
366 #ifdef USE_TIMESTAMP
367 if (!locate_cache) {
368 locate_cache = CC_SAFE_MALLOC (ncount, cacheobj);
369 if (!locate_cache) {
370 flipper1free (locate_root);
371 return 1;
372 }
373 for (i = 0; i < ncount; i++) {
374 locate_cache[i].segment = locate_root;
375 locate_cache[i].stamp = 0;
376 }
377 locate_cache_magic = 0;
378 } else {
379 locate_cache_magic++;
380 }
381 #else
382 if (!locate_cache) {
383 locate_cache = CC_SAFE_MALLOC (ncount, flipper1 *);
384 if (!locate_cache) {
385 flipper1free (locate_root);
386 return 1;
387 }
388 }
389 #endif
390
391 locate_root->locate.parent = (flipper1 *) NULL;
392 locate_root->locate.lower = (flipper1 *) NULL;
393 locate_root->locate.higher = (flipper1 *) NULL;
394 locate_root->order.left = locate_root;
395 locate_root->order.right = locate_root;
396 locate_root->low = 0;
397 locate_root->high = ncount - 1;
398 locate_root->reverse = 0;
399 segment_count = 1;
400
401 #ifndef USE_TIMESTAMP
402 for (i = 0; i < ncount; i++) {
403 locate_cache[i] = locate_root;
404 }
405 #endif
406
407 flip1_cyc = CC_SAFE_MALLOC (ncount, int);
408 if (!flip1_cyc) {
409 #ifdef USE_TIMESTAMP
410 CC_FREE (locate_cache, cacheobj);
411 #else
412 CC_FREE (locate_cache, flipper1 *);
413 #endif
414 return 1;
415 }
416 flip1_inv = CC_SAFE_MALLOC (ncount, int);
417 if (!flip1_inv) {
418 #ifdef USE_TIMESTAMP
419 CC_FREE (locate_cache, cacheobj);
420 #else
421 CC_FREE (locate_cache, flipper1 *);
422 #endif
423 CC_FREE (flip1_cyc, int);
424 return 1;
425 }
426
427 for (i = 0; i < ncount; i++) {
428 flip1_cyc[i] = cyc[i];
429 flip1_inv[cyc[i]] = i;
430 }
431 cycle_size = ncount;
432 short_size = ncount/2;
433 reversed = 0;
434
435 return 0;
436 }
437
438 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_cycle(int * x)439 int CClinkern_flipper_cycle (int *x)
440 #else
441 int CClinkern_flipper_cycle (x)
442 int *x;
443 #endif
444 {
445 flipper1 *p;
446 int i;
447 int n = 0;
448 int nseg = 0;
449
450 p = order_root;
451
452 do {
453 nseg++;
454 if (p->reverse) {
455 for (i = p->high; i >= p->low; i--)
456 x[n++] = flip1_cyc[i];
457 } else {
458 for (i = p->low; i <= p->high; i++)
459 x[n++] = flip1_cyc[i];
460 }
461 p = p->order.right;
462 } while (p != order_root);
463
464 assert (nseg == segment_count);
465 /*
466 printf ("Segment Hits: %d (Total %d) (%.2f)\n", seghit, segtotal,
467 (double) seghit / (double) segtotal);
468 fflush (stdout);
469 */
470 return nseg;
471 }
472
473 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_finish(void)474 void CClinkern_flipper_finish (void)
475 #else
476 void CClinkern_flipper_finish ()
477 #endif
478 {
479 flipper1_tree_free (locate_root, (flipper1 *) NULL);
480 locate_root = (flipper1 *) NULL;
481 order_root = (flipper1 *) NULL;
482
483 if (flip1_cyc)
484 CC_FREE (flip1_cyc, int);
485 if (flip1_inv)
486 CC_FREE (flip1_inv, int);
487 cycle_size = 0;
488 short_size = 0;
489 reversed = 0;
490 }
491
492 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_free_world(void)493 void CClinkern_flipper_free_world (void)
494 #else
495 void CClinkern_flipper_free_world ()
496 #endif
497 {
498 int total, onlist;
499
500 if (locate_cache)
501 #ifdef USE_TIMESTAMP
502 CC_FREE (locate_cache, cacheobj);
503 #else
504 CC_FREE (locate_cache, flipper1 *);
505 #endif
506
507 if (flipper1_check_leaks (&total, &onlist)) {
508 fprintf (stderr, "WARNING: %d outstanding flippers\n", total - onlist);
509 }
510 flipper1free_world ();
511 }
512
513
514 #ifdef CC_PROTOTYPE_ANSI
flipper1_locate(int x)515 static flipper1 *flipper1_locate (int x)
516 #else
517 static flipper1 *flipper1_locate (x)
518 int x;
519 #endif
520 {
521 flipper1 *p;
522
523 #ifdef USE_TIMESTAMP
524 if (locate_cache[x].stamp == locate_cache_magic) {
525 p = locate_cache[x].segment;
526 } else {
527 p = locate_root;
528 }
529 #else
530 p = locate_cache[x];
531 #endif
532
533 if (x <= p->high && x >= p->low)
534 return p;
535 else
536 p = locate_root;
537
538 if (p->high < x) {
539 if (p->high != -1) {
540 if (p->locate.higher && p->locate.higher->high >= x) {
541 p = p->locate.higher;
542 } else if (p->locate.parent && p->locate.parent->high >= x) {
543 p = p->locate.parent;
544 } else {
545 p = locate_root;
546 }
547 } else {
548 p = locate_root;
549 }
550 } else if (p->low > x) {
551 if (p->locate.lower && p->locate.lower->low <= x) {
552 p = p->locate.lower;
553 } else if (p->locate.parent && p->locate.parent->low <= x) {
554 p = p->locate.parent;
555 } else {
556 p = locate_root;
557 }
558 } else {
559 return p;
560 }
561
562 /*
563 while (p) { For some reason this is faster under linux
564 */
565 while (1) {
566 /*
567 totaldepth += 1.0;
568 */
569 if (x < p->low)
570 p = p->locate.lower;
571 else if (x > p->high)
572 p = p->locate.higher;
573 else
574 break;
575 }
576 /*
577 totalsize += segment_count;
578 depthcalls++;
579 */
580
581 #ifdef USE_TIMESTAMP
582 locate_cache[x].segment = p;
583 locate_cache[x].stamp = locate_cache_magic;
584 #else
585 locate_cache[x] = p;
586 #endif
587
588 return p;
589 }
590
591 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_next(int ix)592 int CClinkern_flipper_next (int ix)
593 #else
594 int CClinkern_flipper_next (ix)
595 int ix;
596 #endif
597 {
598 int x = flip1_inv[ix];
599 flipper1 *p;
600
601 p = flipper1_locate (x);
602
603 if (p->reverse) {
604 return x == p->low ? (p->order.right->reverse
605 ? flip1_cyc[p->order.right->high]
606 : flip1_cyc[p->order.right->low])
607 : flip1_cyc[x - 1];
608 } else {
609 return x == p->high ? (p->order.right->reverse
610 ? flip1_cyc[p->order.right->high]
611 : flip1_cyc[p->order.right->low])
612 : flip1_cyc[x + 1];
613 }
614 }
615
616 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_prev(int ix)617 int CClinkern_flipper_prev (int ix)
618 #else
619 int CClinkern_flipper_prev (ix)
620 int ix;
621 #endif
622 {
623 int x = flip1_inv[ix];
624 flipper1 *p;
625
626 p = flipper1_locate (x);
627
628 if (p->reverse) {
629 return x == p->high ? (p->order.left->reverse
630 ? flip1_cyc[p->order.left->low]
631 : flip1_cyc[p->order.left->high])
632 : flip1_cyc[x + 1];
633 } else {
634 return x == p->low ? (p->order.left->reverse
635 ? flip1_cyc[p->order.left->low]
636 : flip1_cyc[p->order.left->high])
637 : flip1_cyc[x - 1];
638 }
639 }
640
641 #ifdef CC_PROTOTYPE_ANSI
flipper1_tree_delete(flipper1 * p)642 static void flipper1_tree_delete (flipper1 *p)
643 #else
644 static void flipper1_tree_delete (p)
645 flipper1 *p;
646 #endif
647 {
648 flipper1 *q;
649
650 if (p->locate.lower == (flipper1 *) NULL) {
651 if (p->locate.higher) {
652 PARENT_HOOKUP (p->locate.higher, p->locate.parent, p);
653 } else {
654 LOCATE_CHILD (p->locate.parent, p) = (flipper1 *) NULL;
655 }
656 } else if (p->locate.higher == (flipper1 *) NULL) {
657 PARENT_HOOKUP (p->locate.lower, p->locate.parent, p);
658 } else {
659 q = p->locate.lower;
660 while (q->locate.higher)
661 q = q->locate.higher;
662 if (q->locate.parent == p) {
663 PARENT_HOOKUP (q, p->locate.parent, p);
664 HIGHER_HOOKUP (q, p->locate.higher);
665 } else {
666 HIGHER_HOOKUP (q->locate.parent, q->locate.lower);
667 PARENT_HOOKUP (q, p->locate.parent, p);
668 LOWER_HOOKUP (q, p->locate.lower);
669 HIGHER_HOOKUP (q, p->locate.higher);
670 }
671 }
672 }
673
674 /*
675 flipper1_split breaks p between x-1 and x.
676 */
677
678 #ifdef CC_PROTOTYPE_ANSI
flipper1_split(flipper1 * p,int x)679 static flipper1 *flipper1_split (flipper1 *p, int x)
680 #else
681 static flipper1 *flipper1_split (p, x)
682 flipper1 *p;
683 int x;
684 #endif
685 {
686 flipper1 *q = flipper1alloc (); /* This will not fail - initial supply */
687 static int side = 0;
688
689 segment_count++;
690 if (side) {
691 HIGHER_HOOKUP (q, p->locate.higher);
692 HIGHER_HOOKUP (p, q);
693 q->locate.lower = (flipper1 *) NULL;
694 q->low = x;
695 q->high = p->high;
696 p->high = x - 1;
697 q->reverse = p->reverse;
698 if (p->reverse) {
699 p->order.left->order.right = q;
700 q->order.left = p->order.left;
701 q->order.right = p;
702 p->order.left = q;
703 } else {
704 p->order.right->order.left = q;
705 q->order.right = p->order.right;
706 q->order.left = p;
707 p->order.right = q;
708 }
709 side = 0;
710 return q;
711 } else {
712 LOWER_HOOKUP (q, p->locate.lower);
713 LOWER_HOOKUP (p, q);
714 q->locate.higher = (flipper1 *) NULL;
715 q->low = p->low;
716 q->high = x - 1;
717 p->low = x;
718 q->reverse = p->reverse;
719 if (p->reverse) {
720 p->order.right->order.left = q;
721 q->order.right = p->order.right;
722 q->order.left = p;
723 p->order.right = q;
724 } else {
725 p->order.left->order.right = q;
726 q->order.left = p->order.left;
727 q->order.right = p;
728 p->order.left = q;
729 }
730 side = 1;
731 return p;
732 }
733 }
734
735 /* flipper1_merge merges p->right into p. */
736
737 #ifdef CC_PROTOTYPE_ANSI
flipper1_merge(flipper1 * p)738 static void flipper1_merge (flipper1 *p)
739 #else
740 static void flipper1_merge (p)
741 flipper1 *p;
742 #endif
743 {
744 flipper1 *pr = p->order.right;
745
746 if (pr->high > p->high)
747 p->high = pr->high;
748 if (pr->low < p->low)
749 p->low = pr->low;
750 p->order.right = pr->order.right;
751 p->order.right->order.left = p;
752 flipper1_tree_delete (pr);
753 if (order_root == pr)
754 order_root = p;
755 flipper1free (pr);
756 segment_count--;
757 }
758
759 #ifdef CC_PROTOTYPE_ANSI
flipper1_checkmerge(flipper1 * x)760 static void flipper1_checkmerge (flipper1 *x)
761 #else
762 static void flipper1_checkmerge (x)
763 flipper1 *x;
764 #endif
765 {
766 flipper1 *xr = x->order.right;
767
768 if (x->reverse || x->low == x->high) {
769 if ((xr->reverse || xr->low == xr->high) && xr->high + 1 == x->low) {
770 x->reverse = 1;
771 flipper1_merge (x);
772 }
773 }
774 if (!x->reverse || x->low == x->high) {
775 if ((!xr->reverse || xr->low == xr->high) && x->high + 1 == xr->low) {
776 x->reverse = 0;
777 flipper1_merge (x);
778 }
779 }
780 }
781
782 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_flip(int ix,int iy)783 void CClinkern_flipper_flip (int ix, int iy)
784 #else
785 void CClinkern_flipper_flip (ix, iy)
786 int ix, iy;
787 #endif
788 {
789 flipper1 *xp, *yp, *p, *ptemp, *rp, *lp;
790 int x, y;
791
792 x = flip1_inv[ix];
793 y = flip1_inv[iy];
794
795 xp = flipper1_locate (x);
796
797 /* split segments if necessary */
798 if (xp->reverse) {
799 if (x != xp->high) {
800 xp = flipper1_split (xp, x + 1);
801 xp = xp->order.right;
802 }
803 } else {
804 if (x != xp->low) {
805 xp = flipper1_split (xp, x);
806 }
807 }
808
809 yp = flipper1_locate (y);
810 if (yp->reverse) {
811 if (y != yp->low) {
812 yp = flipper1_split (yp, y);
813 }
814 } else {
815 if (y != yp->high) {
816 yp = flipper1_split (yp, y + 1);
817 yp = yp->order.left;
818 }
819 }
820 xp = flipper1_locate (x);
821
822 /* reverse */
823 p = xp;
824 for (;;) {
825 SWAP (p->order.right, p->order.left, ptemp);
826 p->reverse ^= 1;
827 if (p == yp)
828 break;
829 p = p->order.left;
830 }
831
832 if (xp->order.right != yp) {
833 lp = xp->order.right;
834 rp = yp->order.left;
835
836 lp->order.right = yp;
837 rp->order.left = xp;
838 xp->order.right = rp;
839 yp->order.left = lp;
840 }
841 /* merge segments if necessary */
842 rp = xp->order.right;
843 if (yp != xp->order.right) {
844 flipper1_checkmerge (xp);
845 flipper1_checkmerge (yp->order.left);
846 }
847 }
848
849 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_sequence(int ix,int iy,int iz)850 int CClinkern_flipper_sequence (int ix, int iy, int iz)
851 #else
852 int CClinkern_flipper_sequence (ix, iy, iz)
853 int ix, iy, iz;
854 #endif
855 {
856 flipper1 *xp, *yp, *zp;
857 int x, y, z;
858
859 x = flip1_inv[ix];
860 y = flip1_inv[iy];
861 z = flip1_inv[iz];
862
863 if (segment_count == 1) {
864 if (locate_root->reverse) {
865 if (x >= y)
866 return y >= z || z >= x;
867 else
868 return y >= z && z >= x;
869 } else {
870 if (x <= y)
871 return y <= z || z <= x;
872 else
873 return y <= z && z <= x;
874 }
875 }
876
877 xp = flipper1_locate (x);
878 yp = flipper1_locate (y);
879 zp = flipper1_locate (z);
880
881 if (xp == yp) {
882 if (xp == zp) {
883 if (xp->reverse) {
884 if (x >= y) {
885 return y >= z || z >= x;
886 } else {
887 return y >= z && z >= x;
888 }
889 } else {
890 if (x <= y) {
891 return y <= z || z <= x;
892 } else {
893 return y <= z && z <= x;
894 }
895 }
896 } else {
897 if (xp->reverse) {
898 return x >= y;
899 } else {
900 return x <= y;
901 }
902 }
903 } else if (xp == zp) {
904 if (xp->reverse) {
905 return z >= x;
906 } else {
907 return z <= x;
908 }
909 } else if (yp == zp) {
910 if (yp->reverse) {
911 return y >= z;
912 } else {
913 return y <= z;
914 }
915 } else {
916 while (xp != yp) {
917 if (xp == zp) {
918 return 0;
919 }
920 xp = xp->order.right;
921 }
922 return 1;
923 }
924 }
925
926 #ifdef CC_PROTOTYPE_ANSI
CClinkern_flipper_flip_perm(int x,int y)927 void CClinkern_flipper_flip_perm (int x, int y)
928 #else
929 void CClinkern_flipper_flip_perm (x, y)
930 int x,y;
931 #endif
932 {
933 int xloc = flip1_inv[x];
934 int yloc = flip1_inv[y];
935 int temp;
936 int gap;
937
938 if (reversed) {
939 SWAP (xloc, yloc, temp);
940 }
941 gap = yloc - xloc;
942 if (gap < 0) gap += cycle_size;
943 if (gap > short_size) {
944 SWAP (xloc, yloc, temp);
945 reversed ^= 1;
946 xloc++;
947 if (xloc >= cycle_size)
948 xloc = 0;
949 yloc--;
950 if (yloc < 0)
951 yloc = cycle_size - 1;
952 gap = cycle_size - gap - 2;
953 }
954 if (xloc > yloc) {
955 gap++;
956 gap /= 2;
957 for (; gap; gap--) {
958 x = flip1_cyc[xloc];
959 y = flip1_cyc[yloc];
960 flip1_cyc[xloc] = y;
961 flip1_cyc[yloc] = x;
962 flip1_inv[x] = yloc--;
963 flip1_inv[y] = xloc++;
964 if (xloc >= cycle_size)
965 xloc = 0;
966 if (yloc < 0)
967 yloc = cycle_size - 1;
968 }
969 } else {
970 gap++;
971 gap /= 2;
972 for (; gap; gap--) {
973 x = flip1_cyc[xloc];
974 y = flip1_cyc[yloc];
975 flip1_cyc[xloc] = y;
976 flip1_cyc[yloc] = x;
977 flip1_inv[x] = yloc--;
978 flip1_inv[y] = xloc++;
979 }
980 }
981 }
982
983