any longer.  So the pair of assignments |ca=cb,cc=cd| is safe in place of a set of full |SWAP|s.  If these assignments {\it are\/} performed, then|ca| still lies on or to the left of |cc|.  @@<Rename so that the |a-c| portion lies entirely in one segment@@>=if ( ca == cc ) return;	/* Rerversing a length-1 list is trivial */if ( ca->seq > cc->seq ) SWAP(ca,cc,tcn),SWAP(cb,cd,tcn);	/* Make $a$ come before $c$ */if ( ca->next == cb ) ca=cb,cc=cd;	/* Make $a-c$ lie entirely in this segment */@@ Now we can get down to the business of flipping the $a-c$ portion of the tour.If it is long enough, thenit makes sense to implictly rebalance:split the ends off and turnon its parent's reversal bit.Otherwise, we physically move the cities.@@<Flip: |ca| to |cc| lies entirely within one segment@@>=if ( abs(ca->seq-cc->seq) > implicit_balance_threshhold ) {	@@<Split the ends off and flip the parent's reversal bit@@>@@;} else {	@@<Reverse the list from |ca| to |cc|@@>@@;}@@ The variable |implicit_balance_threshhold| is set when we set upthe data structure.  It is given the value of $3/4\times groupsize$,as prescribed by Fredman \etal.@@<Set up the two-level data structure@@>=implicit_balance_threshhold = (3 * groupsize)/4;@@ It is local to this module.@@<Module variables@@>=static int implicit_balance_threshhold;@@ Lets do the simpler part: moving links around to flip a tour segment.First we reverse the sequence  numbers, then we reverse the list bypermuting pointers.There will be several places where we'll need to reverse a sequence ofcities.  That code is generalized by using variables |u|  and |v| todenote the first and last cities to be reversed; city |u| occurs on or tothe left of |v|.  We already assume that |ca| occurs on or to theleft of |cc|.We reverse a segment by swapping each city's |next| and |prev| pointers.This way, what was a city's predecessor is now its successor, andvice versa.  We must ensure thatpointers from outside the reversed segment get updated to point to the appropriateend cities.  The outbound sibling pointers inside the segment are fixed bythe |SWAP(u->prev,v->next)| code: remember they will be swapped appropriatelywhen all the sibling links are swapped.@@<Reverse the list from |ca| to |cc|@@>={ city_node_t *u = ca, *v = cc;@@<Reverse the city sequence numbers from |u| to |v|@@>@@;@@<Make external pointers point to the other of |u|, |v|@@>@@;SWAP(u->prev,v->next,tcn);		/* Fix outbound sibling pointers */@@<Swap links from |u| to |v|@@>@@;}@@ Now, |u| and |v| have been chosen so that |v| may be found by followingzero or more |next| pointers from |u| without leaving this segment.Also, sequence numbers increase as we follow |next| pointers.This allows usto just overwrite the sequence numbers; we don't need to do any swapping.@@<Reverse the city sequence numbers from |u| to |v|@@>={	city_node_t *i=u, *done=v->next;	int s;	for ( s=v->seq,i=u; i!=done ; i=i->next,s-- ){		i->seq=s;	}}@@ Now that we've updated sequence numbers, we can update pointers.The pointers that might need updating are |head| and |tail| pointers,and |prev| and |next| pointers.The code for updating the |prev| and |next| pointers is just a parallel assignment.  Unfortunately, parallelassignment is awkward in \CEE/; parallel bindings are easy in \ML/.@@^ML@@>We need parallel assignment because we might be in the degenerate casewhere we are flipping the entire tour except for one node.   In that case,we shouldn't change its |next| pointer from |ca|, say, to |cc|, {\it andthen back again.}  Think about it.Similarly, there might only be one node in the segment; it would beboth the head and the tail.  But then updating it twice doesn't poseany problems, for then |ca==cc|!.  So we don't need a parallel assignmentin fixing the head and tail pointers.Recall that we assume that |u| and |v| are in the same segment, and therefore have the same parent.  Furthermore, |u| comes on or before|v|. @@<Make external pointers point to the other of |u|, |v|@@>={ parent_node_t *p = u->parent;const int upn_to_v = u->prev->next == u, upp_to_v = u->prev->prev == u,vnp_to_u = v->next->prev == v, vnn_to_u = v->next->next == v;if ( upn_to_v ) u->prev->next = v;if ( upp_to_v ) u->prev->prev = v;if ( vnp_to_u ) v->next->prev = u; if ( vnn_to_u ) v->next->next = u;if ( p->head == ca ) p->head=cc;	/* Now fix |head| and |tail| */else if ( p->head== cc ) p->head=ca;if ( p->tail == ca ) p->tail=cc;else if ( p->tail== cc ) p->tail=ca;}@@ This code requires that sequence numbers increase as we follow |next| pointers.  It assumes that |u| occurs at the same point or to the left of |v|.%%I've used fresh variables |i| and |j| because I want to be as hygienic %%as possible:%%don't destroy values unnecessarily.  A good optimizing compiler will%% reuse the registers anyway.@@<Swap links from |u| to |v|@@>={	city_node_t *i=u, *done = v->next;	for ( i=u; i != done; i=i->prev ) {	/* Yes, |prev|: it's the old |next| pointer. */		SWAP(i->next,i->prev,tcn);	}}@@ Let's do the other part: implict rebalancing. This involvessplitting the ends off the $a-c$ segment, merging those endswith their neighbours, swapping the inbound sibling pointers, andthen flipping their parent's reversal bit.We've already arranged things so that that |ca|'s sequence number isno greater than |cc|'s sequence number, \ie, that we can find |cc| byfollowing zero or more |next| pointers starting at node |ca| withoutleaving the segment.@@<Split the ends off and flip the parent's reversal bit@@>=@@<Split off the end to the left of |ca|@@>@@;@@<Split off the end to the right of |cc|@@>@@;@@<Fix sibling pointers to and from |ca| and |cc|@@>@@;ca->parent->reverse ^= 1;@@<Verbose: implicit rebalance done@@>@@;@@ The part of the segment to the left of |ca| is split off and mergedwith the segment to its left (left according to the |prev| link of thehead of this segment).  We must be careful for a few reasons.First, thereare four possible combined settings for the reversal bits of thissegment and the segment to the left.  Second, we must set the city |prev| and |next| links so that theyare correct {\it after\/} the parent's reversal bit is flipped.@@<Split off the end to the left of |ca|@@>=@@<Verbose: split off the end to the left of |ca| begin@@>@@;{ 	parent_node_t *p = ca->parent;	city_node_t *lc=p->head; 		/* City at left end of split off segment. */	city_node_t *rc=ca->prev;		/* City at right end of split off segment */	city_node_t *llc=lc->prev;		/* New sibling of |lc|: ``left of |lc|'' */	parent_node_t *lp=llc->parent;	/* Parent of the segment to be merged into */	int lpr = lp->reverse, pr=p->reverse;	errorif(lp==p,"Bug");	if ( lc != ca ) {	/* There is work to do. */		@@<Split left: set the end city links@@>@@;		@@<Split left: set the per-city data in the split off segment@@>@@;	}}@@<Verbose: split off the end to the left of |ca| end@@>@@;@@ This section updates any pointers to the end cities of the split offportion of the segment.  It helps to look at the input and outputpointer ``flows'' to/from this split off portion.  This way we canhopefully avoid missing updating a pointer.The pointers coming {\it into\/} this split off portion of the segment are asfollows:there is one sibling pointer pointing to the left end of thelist, |llc->link[lpr^LINK_NEXT]|; there is one sibling pointer pointing to theright end of the list, |ca->prev|; finally there is a head pointer fromthe old parent, |p->head|, and a head/tail pointer from thenew parent, |lp->city_link[pr^lpr^CITY_LINK_TAIL]|.  Interestingly, the sibling pointers need to be changed depending on thecontext in which this code is used, so we won't change them here.The pointers coming {\it out of\/} this split off portion of the segment are asfollows:there is one sibling pointer pointing from the left end of thelist, |lc->prev|; there is one sibling pointer pointing from theright end of the list, |rc->next|; finally there are parent pointers at each node in the list.All these outgoing pointers will be handled as part of the per-city changes.@@<Split left: set the end city links@@>=p->head = ca;lp->city_link[(pr==lpr)?CITY_LINK_TAIL:CITY_LINK_HEAD] = rc;@@ Each city node in the split off segment must be updated in thefollowing ways.First, we must set the sequence numbers so they are consecutive with those in the segment to the left.    We use two variablesto set them: |seq_num| begins as the sequence number that city |lc|should be set to; |seq_inc| is the increment in sequence numbers thatshould take effect in traversing the list from |lc| through to |rc|.There are two cases to consider.  If the two segments have the same orientation, then we're appending the |lc| to |rc| list to the right end of the segmentto the left.So|lc|'s new sequence number should be |llc->seq+1| and they should increase,\ie\ |seq_inc| should be 1.Otherwise, the segments have different orientations: |llc| is thehead of its and we'll be moving the |lc| to |rc| listto the left of |llc|.  In this case, |lc|'s new sequence number shouldbe |llc->seq-1| and they should decrease, \ie\ |seq_num| should be -1.Second, if the orientations of the old and the new segments are different,then we must reverse the links of the moved portion of the linked list.I've combined these functions into one segment because thetraversal code changes according whether we change the senseof |prev| and |next|.  In particular, |link[succ_link]| traverses thelist from |u| to |v|, which is left to right in the original list.@@<Split left: set the per-city data in the split off segment@@>={ city_node_t *i, *u=lc, *v=rc;int succ_link, seq_inc, seq_num;if ( lpr==pr ) {	/* Move to right end. */	succ_link=LINK_NEXT;	seq_inc = 1;	seq_num = llc->seq + 1;} else {	/* Move to left end. */	succ_link = LINK_PREV;	seq_inc = -1;	seq_num = llc->seq - 1;	@@<Swap links from |u| to |v|@@>@@;}for ( i=lc;i!=rc;i=i->link[succ_link], seq_num+= seq_inc ) {	/* Set parent pointers andsequence numbers */	i->parent = lp;	i->seq = seq_num;}i->parent = lp;i->seq = seq_num;}@@ Splitting off the right end is analogous to splitting off the left end,but with a slight twist.First, we make the following exchanges:|next|$\leftrightarrow$|prev|;|head|$\leftrightarrow$|tail|; |l|$\leftrightarrow$|r|, in variable names;and |cc|$\leftrightarrow$|ca|.  The twist comes when setting sequence numbers;its explained below.Here's righthand version of the top-level section.  @@<Split off the end to the right of |cc|@@>=@@<Verbose: split off the end to the right of |cc| begin@@>@@;{ 	parent_node_t *p = cc->parent;	city_node_t *rc=p->tail; 		/* City at right end of split off segment */	city_node_t *lc=cc->next;		/* City at left end of split off segment */	city_node_t *rrc=rc->next;		/* New sibling of |rc|: ``right of |rc|'' */	parent_node_t *rp=rrc->parent;	/* Parent of the segment to be merged into */	int rpr = rp->reverse, pr=p->reverse;	errorif(rp==p,"Bug");	if ( rc != cc ) {	/* There is work to do. */		@@<Split right: set the end city links@@>@@;		@@<Split right: set the per-city data in the split off segment@@>@@;	}}@@<Verbose: split off the end to the right of |cc| end@@>@@;@@ Setting the end city links on the right is analogous to setting themon the left.@@<Split right: set the end city links@@>=p->tail = cc;rp->city_link[(pr==rpr)?CITY_LINK_HEAD:CITY_LINK_TAIL] = lc;@@ Setting the per-city data on the right hand side is also analogous.  As in splitting a segment to the left, |seq_num| is again the new sequence number of |lc|and |seq_inc| is the increment on sequence numbers as we travel from|lc| to |rc|.  The twist in setting the sequence numbers that I mentioned earlier is as follows.  When the orientations of the two segments are thesame, then we're moving the |lc| to |rc| list to the {\it left\/}end of the new segment, and so |lc| must start out as |rrc->seq-1|minus the length of the |lc| to |rc| segment; the increment shouldagain be 1.  When the orientations are different, we'll be addingto the right end of the new segment, with |rc| at the beginning and|lc| becoming the new tail.  In this case, |lc|'s new sequence number should be |rrc->seq| plus the lengthof the |lc| to |rc| list, and |seq_inc| should be -1.@@<Split right: set the per-city data in the split off segment@@>={ city_node_t *i, *u=lc, *v=rc;int succ_link, seq_inc, seq_num;if ( rpr==pr ) {	/* Move to left end. */	succ_link=LINK_NEXT;	seq_inc = 1;	seq_num = rrc->seq + u->seq-v->seq - 1;} else {	/* Move to right end. */	succ_link = LINK_PREV;	seq_inc = -1;	seq_num = rrc->seq + v->seq-u->seq + 1;	@@<Swap links from |u| to |v|@@>@@;}for ( i=lc;i!=rc;i=i->link[succ_link], seq_num+= seq_inc ) {		/* Set parent pointers and sequence numbers */	i->parent = rp;	i->seq = seq_num;}i->parent = rp;i->seq = seq_num;}@@ We're reversing a single segment and must therefore swap the two inboundsibling pointers and the two outbound pointers.  In more detail, there are four pointers to change.The sibling pointer that used to point to |cc| shouldnow point to |ca|, and vice versa.  The code is only tricky because wemust handle all combinations of reversal bits of the two bordering segments.Then, |ca->prev| and |cc->next| should be swapped; these are the outboundsibling pointers.This section completes the codeto handle the first case in flipping.@@<Fix sibling pointers to and from |ca| and |cc|@@>={	city_node_t *l=ca->prev, *r = cc->next;	parent_node_t *lp= l->parent, *rp = r->parent;	const int ac_rev=ca->parent->reverse;	city_node_t **inbound_l = &l->link[LINK_NEXT^lp->reverse^ac_rev],		**inbound_r = &r->link[LINK_PREV^rp->reverse^ac_rev];	errorif(*inbound_l != ca,		"Inbound left %d != ca %d", 		*inbound_l - city_node, ca-city_node);	errorif(*inbound_r != cc,		"Inbound right %d != cc %d", 		*inbound_r - city_node, cc-city_node);	SWAP(*inbound_l,*inbound_r,tcn);	SWAP(ca->prev,cc->next,tcn);}@@ Now we can move on to handling the third case for flipping:either $a$ and $b$ are in the same segment, or $c$ and $d$ are.We handle this case by reducing it to the second case.  That is,we split segments so that $a$ and $b$ are in different segments,and $d$ and $c$ are in different segments.@@ Let's tackle splitting the $a-b$ segment first.Thankfully, we can reuse much of the code we've just written for implicit