trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.30 2009-09-06 15:51:09 amb Exp $

 Super-Segment data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008,2009 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

#include "results.h"
#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.h"
#include "superx.h"
#include "ways.h"


/* Local Functions */

static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration);


/*++++++++++++++++++++++++++++++++++++++
  Select the super-segments from the list of segments.

  NodesX *nodesx The nodes.

  SegmentsX *segmentsx The segments.

  WaysX *waysx The ways.
  ++++++++++++++++++++++++++++++++++++++*/

void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
{
 index_t i;
 int nnodes=0;

 assert(nodesx->idata);         /* Must have idata filled in => sorted by id */

 printf("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
 fflush(stdout);

 /* Find super-nodes */

 for(i=0;i<nodesx->number;i++)
   {
    int      difference=0;
    index_t *index;

    index=IndexFirstSegmentX(segmentsx,nodesx->idata[i]);

    if(index)
      {
       SegmentX *segmentx=FindSegmentX(segmentsx,*index);
       WayX *wayx1=FindWayX(waysx,segmentx->way);

       index=IndexNextSegmentX(segmentsx,index);

       if(index)
         {
          segmentx=FindSegmentX(segmentsx,*index);
          WayX *wayx2=FindWayX(waysx,segmentx->way);

          if(WaysCompare(wayx2->way,wayx1->way))
             difference=1;

          index=IndexNextSegmentX(segmentsx,index);
         }

       /* Store the node if there is a difference in the first two ways that could affect routing.
          Store the node if it has at least three segments. */

       if(difference || index)
         {
          nodesx->super[i]++;

          nnodes++;
         }
      }

    if(!((i+1)%10000))
      {
       printf("\rFinding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
       fflush(stdout);
      }
   }

 printf("\rFound Super-Nodes: Nodes=%d Super-Nodes=%d  \n",nodesx->number,nnodes);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Create the super-segments.

  SegmentsX *CreateSuperSegments Creates the super segments.

  NodesX *nodesx The nodes.

  SegmentsX *segmentsx The segments.

  WaysX *waysx The ways.

  int iteration The current super-node / super-segment iteration number.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentsX *CreateSuperSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,int iteration)
{
 index_t i;
 SegmentsX *supersegmentsx;
 int sn=0,ss=0;

 assert(nodesx->idata);         /* Must have idata filled in => sorted by id */

 printf("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
 fflush(stdout);

 supersegmentsx=NewSegmentList();

 /* Create super-segments for each super-node. */

 for(i=0;i<nodesx->number;i++)
   {
    if(nodesx->super[i]>iteration)
      {
       index_t *index,*first;

       index=first=IndexFirstSegmentX(segmentsx,nodesx->idata[i]);

       while(index)
         {
          SegmentX *segmentx=FindSegmentX(segmentsx,*index);
          WayX *wayx=FindWayX(waysx,segmentx->way);

          /* Check that this type of way hasn't already been routed */

          if(index!=first)
            {
             index_t *otherindex=first;

             while(otherindex && otherindex!=index)
               {
                SegmentX *othersegmentx=FindSegmentX(segmentsx,*otherindex);
                WayX *otherwayx=FindWayX(waysx,othersegmentx->way);

                if(!WaysCompare(otherwayx->way,wayx->way))
                  {
                   wayx=NULL;
                   break;
                  }

                otherindex=IndexNextSegmentX(segmentsx,otherindex);
               }
            }

          /* Route the way and store the super-segments. */

          if(wayx)
            {
             Results *results=FindRoutesWay(nodesx,segmentsx,waysx,nodesx->idata[i],wayx->way,iteration);
             Result *result=FirstResult(results);

             while(result)
               {
                index_t nindex=IndexNodeX(nodesx,result->node);

                if(result->node!=nodesx->idata[i] && nodesx->super[nindex]>iteration)
                  {
                   if(wayx->way->type&Way_OneWay)
                      AppendSegment(supersegmentsx,wayx->id,nodesx->idata[i],result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2);
                   else
                      AppendSegment(supersegmentsx,wayx->id,nodesx->idata[i],result->node,DISTANCE((distance_t)result->score));

                   ss++;
                  }

                result=NextResult(results,result);
               }

             FreeResultsList(results);
            }

          index=IndexNextSegmentX(segmentsx,index);
         }

       sn++;

       if(!(sn%10000))
         {
          printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
          fflush(stdout);
         }
      }
   }

 printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",sn,ss);
 fflush(stdout);

 return(supersegmentsx);
}


/*++++++++++++++++++++++++++++++++++++++
  Merge the segments and super-segments into a new segment list.

  SegmentsX* MergeSuperSegments Returns a new set of merged segments.

  SegmentsX* segmentsx The set of segments to process.

  SegmentsX* supersegmentsx The set of super-segments to merge.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentsX *MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
{
 index_t i,j;
 int m=0,a=0;
 SegmentsX* mergedsegmentsx;

 assert(segmentsx->n1data);      /* Must have n1data filled in => sorted by node 1 */
 assert(supersegmentsx->n1data); /* Must have n1data filled in => sorted by node 1 */

 printf("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0");
 fflush(stdout);

 mergedsegmentsx=NewSegmentList();

 for(i=0,j=0;i<segmentsx->number;i++)
   {
    int super=0;
    SegmentX *segmentx=FindSegmentX(segmentsx,segmentsx->n1data[i]);

    while(j<supersegmentsx->number)
      {
       SegmentX *supersegmentx=FindSegmentX(supersegmentsx,supersegmentsx->n1data[j]);

       if(segmentx->node1   ==supersegmentx->node1 &&
          segmentx->node2   ==supersegmentx->node2 &&
          segmentx->distance==supersegmentx->distance)
         {
          /* mark as super-segment and normal segment */
          super=1;
          m++;
          j++;
          break;
         }
       else if((segmentx->node1==supersegmentx->node1 &&
                segmentx->node2==supersegmentx->node2) ||
               (segmentx->node1==supersegmentx->node1 &&
                segmentx->node2>supersegmentx->node2) ||
               (segmentx->node1>supersegmentx->node1))
         {
          /* mark as super-segment */
          AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance|SEGMENT_SUPER);
          a++;
          j++;
         }
       else
          break;
      }

    if(super)
       AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_SUPER|SEGMENT_NORMAL);
    else
       AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_NORMAL);

    if(!((i+1)%10000))
      {
       printf("\rMerging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
       fflush(stdout);
      }
   }

 printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
 fflush(stdout);

 return(mergedsegmentsx);
}


/*++++++++++++++++++++++++++++++++++++++
  Find all routes from a specified node to any node in the specified list that follows a certain type of way.

  Results *FindRoutesWay Returns a set of results.

  NodesX *nodesx The set of nodes to use.

  SegmentsX *segmentsx The set of segments to use.

  WaysX *waysx The set of ways to use.

  node_t start The start node.

  Way *match The way that the route must match.

  int iteration The current super-node / super-segment iteration number.
  ++++++++++++++++++++++++++++++++++++++*/

static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration)
{
 Results *results;
 Queue *queue;
 index_t node1,node2;
 Result *result1,*result2;
 index_t *index;
 WayX *wayx;

 /* Insert the first node into the queue */

 results=NewResultsList(8);

 queue=NewQueueList();

 result1=InsertResult(results,start);

 ZeroResult(result1);

 InsertInQueue(queue,result1);

 /* Loop across all nodes in the queue */

 while((result1=PopFromQueue(queue)))
   {
    node1=result1->node;

    index=IndexFirstSegmentX(segmentsx,node1);

    while(index)
      {
       SegmentX *segmentx=FindSegmentX(segmentsx,*index);
       distance_t cumulative_distance;

       if(segmentx->node1==node1) /* Correct way round */
         {
          if(segmentx->distance&ONEWAY_2TO1)
             goto endloop;

          node2=segmentx->node2;
         }
       else                          /* Opposite way round */
         {
          if(segmentx->distance&ONEWAY_1TO2)
             goto endloop;

          node2=segmentx->node1;
         }

       if(result1->prev==node2)
          goto endloop;

       wayx=FindWayX(waysx,segmentx->way);

       if(WaysCompare(wayx->way,match))
          goto endloop;

       cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);

       result2=FindResult(results,node2);

       if(!result2)                         /* New end node */
         {
          result2=InsertResult(results,node2);
          result2->prev=node1;
          result2->next=NO_NODE;
          result2->score=cumulative_distance;
          result2->sortby=cumulative_distance;

          if(nodesx->super[IndexNodeX(nodesx,node2)]<=iteration)
             InsertInQueue(queue,result2);
         }
       else if(cumulative_distance<result2->score)
         {
          result2->prev=node1;
          result2->score=cumulative_distance;
          result2->sortby=cumulative_distance;

          if(nodesx->super[IndexNodeX(nodesx,node2)]<=iteration)
             InsertInQueue(queue,result2);
         }

      endloop:

       index=IndexNextSegmentX(segmentsx,index);
      }
   }

 FreeQueueList(queue);

 return(results);
}
1	amb	110	/***************************************
2	amb	256	$Header: /home/amb/CVS/routino/src/superx.c,v 1.30 2009-09-06 15:51:09 amb Exp $
3	amb	110
4			Super-Segment data type functions.
5	amb	151
6			Part of the Routino routing software.
7	amb	110	****************/ /****************
8	amb	151	This file Copyright 2008,2009 Andrew M. Bishop
9	amb	110
10	amb	151	This program is free software: you can redistribute it and/or modify
11			it under the terms of the GNU Affero General Public License as published by
12			the Free Software Foundation, either version 3 of the License, or
13			(at your option) any later version.
14
15			This program is distributed in the hope that it will be useful,
16			but WITHOUT ANY WARRANTY; without even the implied warranty of
17			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18			GNU Affero General Public License for more details.
19
20			You should have received a copy of the GNU Affero General Public License
21			along with this program. If not, see <http://www.gnu.org/licenses/>.
22	amb	110	***************************************/
23
24
25			#include <assert.h>
26			#include <stdlib.h>
27			#include <stdio.h>
28
29			#include "results.h"
30			#include "nodesx.h"
31			#include "segmentsx.h"
32			#include "waysx.h"
33			#include "superx.h"
34	amb	228	#include "ways.h"
35	amb	110
36
37	amb	228	/* Local Functions */
38
39			static Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,Way *match,int iteration);
40
41
42	amb	110	/*++++++++++++++++++++++++++++++++++++++
43			Select the super-segments from the list of segments.
44
45			NodesX *nodesx The nodes.
46
47			SegmentsX *segmentsx The segments.
48
49			WaysX *waysx The ways.
50			++++++++++++++++++++++++++++++++++++++*/
51
52	amb	214	void ChooseSuperNodes(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx)
53	amb	110	{
54	amb	214	index_t i;
55	amb	229	int nnodes=0;
56	amb	110
57	amb	243	assert(nodesx->idata); /* Must have idata filled in => sorted by id */
58	amb	213
59	amb	231	printf("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
60	amb	227	fflush(stdout);
61
62	amb	110	/* Find super-nodes */
63
64	amb	229	for(i=0;i<nodesx->number;i++)
65	amb	110	{
66	amb	229	int difference=0;
67	amb	256	index_t *index;
68	amb	110
69	amb	256	index=IndexFirstSegmentX(segmentsx,nodesx->idata[i]);
70	amb	229
71	amb	256	if(index)
72	amb	110	{
73	amb	256	SegmentX segmentx=FindSegmentX(segmentsx,index);
74			WayX *wayx1=FindWayX(waysx,segmentx->way);
75	amb	110
76	amb	256	index=IndexNextSegmentX(segmentsx,index);
77	amb	229
78	amb	256	if(index)
79	amb	110	{
80	amb	256	segmentx=FindSegmentX(segmentsx,*index);
81			WayX *wayx2=FindWayX(waysx,segmentx->way);
82	amb	110
83	amb	229	if(WaysCompare(wayx2->way,wayx1->way))
84			difference=1;
85	amb	110
86	amb	256	index=IndexNextSegmentX(segmentsx,index);
87	amb	110	}
88
89	amb	229	/* Store the node if there is a difference in the first two ways that could affect routing.
90			Store the node if it has at least three segments. */
91	amb	110
92	amb	256	if(difference \|\| index)
93	amb	229	{
94	amb	249	nodesx->super[i]++;
95	amb	110
96	amb	229	nnodes++;
97			}
98	amb	110	}
99
100			if(!((i+1)%10000))
101			{
102	amb	231	printf("\rFinding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
103	amb	110	fflush(stdout);
104			}
105			}
106
107	amb	231	printf("\rFound Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
108	amb	110	fflush(stdout);
109			}
110
111
112			/*++++++++++++++++++++++++++++++++++++++
113			Create the super-segments.
114
115			SegmentsX *CreateSuperSegments Creates the super segments.
116
117			NodesX *nodesx The nodes.
118
119			SegmentsX *segmentsx The segments.
120
121			WaysX *waysx The ways.
122
123			int iteration The current super-node / super-segment iteration number.
124			++++++++++++++++++++++++++++++++++++++*/
125
126			SegmentsX CreateSuperSegments(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,int iteration)
127			{
128	amb	214	index_t i;
129	amb	110	SegmentsX *supersegmentsx;
130	amb	227	int sn=0,ss=0;
131	amb	110
132	amb	243	assert(nodesx->idata); /* Must have idata filled in => sorted by id */
133	amb	213
134	amb	227	printf("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
135			fflush(stdout);
136
137	amb	110	supersegmentsx=NewSegmentList();
138
139			/* Create super-segments for each super-node. */
140
141			for(i=0;i<nodesx->number;i++)
142			{
143	amb	249	if(nodesx->super[i]>iteration)
144	amb	110	{
145	amb	256	index_t index,first;
146	amb	110
147	amb	256	index=first=IndexFirstSegmentX(segmentsx,nodesx->idata[i]);
148	amb	110
149	amb	256	while(index)
150	amb	110	{
151	amb	256	SegmentX segmentx=FindSegmentX(segmentsx,index);
152			WayX *wayx=FindWayX(waysx,segmentx->way);
153	amb	110
154			/* Check that this type of way hasn't already been routed */
155
156	amb	256	if(index!=first)
157	amb	110	{
158	amb	256	index_t *otherindex=first;
159	amb	110
160	amb	256	while(otherindex && otherindex!=index)
161	amb	110	{
162	amb	256	SegmentX othersegmentx=FindSegmentX(segmentsx,otherindex);
163			WayX *otherwayx=FindWayX(waysx,othersegmentx->way);
164	amb	110
165	amb	204	if(!WaysCompare(otherwayx->way,wayx->way))
166	amb	110	{
167	amb	204	wayx=NULL;
168	amb	110	break;
169			}
170
171	amb	256	otherindex=IndexNextSegmentX(segmentsx,otherindex);
172	amb	110	}
173			}
174
175			/* Route the way and store the super-segments. */
176
177	amb	204	if(wayx)
178	amb	110	{
179	amb	252	Results *results=FindRoutesWay(nodesx,segmentsx,waysx,nodesx->idata[i],wayx->way,iteration);
180	amb	110	Result *result=FirstResult(results);
181
182			while(result)
183			{
184	amb	256	index_t nindex=IndexNodeX(nodesx,result->node);
185	amb	110
186	amb	256	if(result->node!=nodesx->idata[i] && nodesx->super[nindex]>iteration)
187	amb	110	{
188	amb	203	if(wayx->way->type&Way_OneWay)
189	amb	252	AppendSegment(supersegmentsx,wayx->id,nodesx->idata[i],result->node,DISTANCE((distance_t)result->score)\|ONEWAY_1TO2);
190	amb	172	else
191	amb	252	AppendSegment(supersegmentsx,wayx->id,nodesx->idata[i],result->node,DISTANCE((distance_t)result->score));
192	amb	216
193	amb	229	ss++;
194	amb	110	}
195
196			result=NextResult(results,result);
197			}
198
199			FreeResultsList(results);
200			}
201
202	amb	256	index=IndexNextSegmentX(segmentsx,index);
203	amb	110	}
204	amb	227
205			sn++;
206	amb	110
207	amb	229	if(!(sn%10000))
208			{
209			printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
210			fflush(stdout);
211			}
212	amb	110	}
213			}
214
215	amb	227	printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",sn,ss);
216	amb	110	fflush(stdout);
217
218			return(supersegmentsx);
219			}
220
221
222			/*++++++++++++++++++++++++++++++++++++++
223	amb	256	Merge the segments and super-segments into a new segment list.
224	amb	110
225	amb	256	SegmentsX* MergeSuperSegments Returns a new set of merged segments.
226
227	amb	110	SegmentsX* segmentsx The set of segments to process.
228
229			SegmentsX* supersegmentsx The set of super-segments to merge.
230			++++++++++++++++++++++++++++++++++++++*/
231
232	amb	256	SegmentsX MergeSuperSegments(SegmentsX segmentsx,SegmentsX* supersegmentsx)
233	amb	110	{
234	amb	216	index_t i,j;
235			int m=0,a=0;
236	amb	256	SegmentsX* mergedsegmentsx;
237	amb	110
238	amb	243	assert(segmentsx->n1data); /* Must have n1data filled in => sorted by node 1 */
239			assert(supersegmentsx->n1data); /* Must have n1data filled in => sorted by node 1 */
240	amb	110
241	amb	227	printf("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0");
242			fflush(stdout);
243
244	amb	256	mergedsegmentsx=NewSegmentList();
245
246	amb	216	for(i=0,j=0;i<segmentsx->number;i++)
247	amb	110	{
248	amb	256	int super=0;
249			SegmentX *segmentx=FindSegmentX(segmentsx,segmentsx->n1data[i]);
250
251	amb	110	while(j<supersegmentsx->number)
252			{
253	amb	256	SegmentX *supersegmentx=FindSegmentX(supersegmentsx,supersegmentsx->n1data[j]);
254
255			if(segmentx->node1 ==supersegmentx->node1 &&
256			segmentx->node2 ==supersegmentx->node2 &&
257			segmentx->distance==supersegmentx->distance)
258	amb	110	{
259	amb	256	/* mark as super-segment and normal segment */
260			super=1;
261	amb	216	m++;
262	amb	110	j++;
263			break;
264			}
265	amb	256	else if((segmentx->node1==supersegmentx->node1 &&
266			segmentx->node2==supersegmentx->node2) \|\|
267			(segmentx->node1==supersegmentx->node1 &&
268			segmentx->node2>supersegmentx->node2) \|\|
269			(segmentx->node1>supersegmentx->node1))
270	amb	110	{
271	amb	256	/* mark as super-segment */
272			AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance\|SEGMENT_SUPER);
273	amb	216	a++;
274			j++;
275	amb	110	}
276			else
277			break;
278			}
279
280	amb	256	if(super)
281			AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance\|SEGMENT_SUPER\|SEGMENT_NORMAL);
282			else
283			AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance\|SEGMENT_NORMAL);
284	amb	208
285	amb	110	if(!((i+1)%10000))
286			{
287	amb	216	printf("\rMerging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
288	amb	110	fflush(stdout);
289			}
290			}
291
292	amb	216	printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
293	amb	110	fflush(stdout);
294	amb	256
295			return(mergedsegmentsx);
296	amb	110	}
297
298
299			/*++++++++++++++++++++++++++++++++++++++
300			Find all routes from a specified node to any node in the specified list that follows a certain type of way.
301
302			Results *FindRoutesWay Returns a set of results.
303
304			NodesX *nodesx The set of nodes to use.
305
306			SegmentsX *segmentsx The set of segments to use.
307
308			WaysX *waysx The set of ways to use.
309
310			node_t start The start node.
311
312	amb	203	Way *match The way that the route must match.
313	amb	110
314			int iteration The current super-node / super-segment iteration number.
315			++++++++++++++++++++++++++++++++++++++*/
316
317	amb	228	static Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,Way *match,int iteration)
318	amb	110	{
319			Results *results;
320	amb	236	Queue *queue;
321	amb	110	index_t node1,node2;
322			Result result1,result2;
323	amb	256	index_t *index;
324	amb	204	WayX *wayx;
325	amb	110
326			/* Insert the first node into the queue */
327
328			results=NewResultsList(8);
329
330	amb	236	queue=NewQueueList();
331
332	amb	110	result1=InsertResult(results,start);
333
334	amb	166	ZeroResult(result1);
335	amb	110
336	amb	236	InsertInQueue(queue,result1);
337	amb	110
338			/* Loop across all nodes in the queue */
339
340	amb	236	while((result1=PopFromQueue(queue)))
341	amb	110	{
342			node1=result1->node;
343
344	amb	256	index=IndexFirstSegmentX(segmentsx,node1);
345	amb	110
346	amb	256	while(index)
347	amb	110	{
348	amb	256	SegmentX segmentx=FindSegmentX(segmentsx,index);
349	amb	113	distance_t cumulative_distance;
350
351	amb	256	if(segmentx->node1==node1) /* Correct way round */
352	amb	229	{
353	amb	256	if(segmentx->distance&ONEWAY_2TO1)
354	amb	229	goto endloop;
355	amb	110
356	amb	256	node2=segmentx->node2;
357	amb	229	}
358			else /* Opposite way round */
359			{
360	amb	256	if(segmentx->distance&ONEWAY_1TO2)
361	amb	229	goto endloop;
362	amb	110
363	amb	256	node2=segmentx->node1;
364	amb	229	}
365
366	amb	113	if(result1->prev==node2)
367	amb	110	goto endloop;
368
369	amb	256	wayx=FindWayX(waysx,segmentx->way);
370	amb	110
371	amb	204	if(WaysCompare(wayx->way,match))
372	amb	110	goto endloop;
373
374	amb	256	cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
375	amb	110
376			result2=FindResult(results,node2);
377
378			if(!result2) /* New end node */
379			{
380			result2=InsertResult(results,node2);
381	amb	113	result2->prev=node1;
382	amb	176	result2->next=NO_NODE;
383	amb	172	result2->score=cumulative_distance;
384	amb	166	result2->sortby=cumulative_distance;
385	amb	110
386	amb	249	if(nodesx->super[IndexNodeX(nodesx,node2)]<=iteration)
387	amb	236	InsertInQueue(queue,result2);
388	amb	110	}
389	amb	172	else if(cumulative_distance<result2->score)
390	amb	110	{
391	amb	166	result2->prev=node1;
392	amb	172	result2->score=cumulative_distance;
393	amb	166	result2->sortby=cumulative_distance;
394	amb	110
395	amb	249	if(nodesx->super[IndexNodeX(nodesx,node2)]<=iteration)
396	amb	236	InsertInQueue(queue,result2);
397	amb	110	}
398
399			endloop:
400
401	amb	256	index=IndexNextSegmentX(segmentsx,index);
402	amb	110	}
403			}
404
405	amb	236	FreeQueueList(queue);
406
407	amb	110	return(results);
408			}