trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.26 2009-08-15 14:18:23 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 */

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

 /* Find super-nodes */

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

    segmentx=FindFirstSegmentX(segmentsx,nodesx->idata[i]->id);

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

       segmentx=FindNextSegmentX(segmentsx,segmentx);

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

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

          segmentx=FindNextSegmentX(segmentsx,segmentx);
         }

       /* 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 || segmentx)
         {
          nodesx->idata[i]->super++;

          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 */

 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->idata[i]->super>iteration)
      {
       SegmentX **segmentx,**first;

       segmentx=first=FindFirstSegmentX(segmentsx,nodesx->idata[i]->id);

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

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

          if(segmentx!=first)
            {
             SegmentX **othersegmentx=first;

             while(othersegmentx && othersegmentx!=segmentx)
               {
                WayX *otherwayx=FindWayX(waysx,(*othersegmentx)->way);

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

                othersegmentx=FindNextSegmentX(segmentsx,othersegmentx);
               }
            }

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

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

             while(result)
               {
                NodeX **nodex=FindNodeX(nodesx,result->node);
                WayX   *wayx =FindWayX (waysx ,(*segmentx)->way);

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

                   ss++;
                  }

                result=NextResult(results,result);
               }

             FreeResultsList(results);
            }

          segmentx=FindNextSegmentX(segmentsx,segmentx);
         }

       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 super-segments into the segments.

  SegmentsX* segmentsx The set of segments to process.

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

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

 assert(segmentsx->sorted);      /* Must be sorted */
 assert(segmentsx->n1data);      /* Must have n1data filled in */
 assert(supersegmentsx->sorted); /* Must be sorted */
 assert(supersegmentsx->n1data); /* Must have n1data filled in */

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

 for(i=0,j=0;i<segmentsx->number;i++)
   {
    while(j<supersegmentsx->number)
      {
       if(segmentsx->n1data[i]->node1==supersegmentsx->n1data[j]->node1 &&
          segmentsx->n1data[i]->node2==supersegmentsx->n1data[j]->node2 &&
          segmentsx->n1data[i]->distance==supersegmentsx->n1data[j]->distance)
         {
          segmentsx->n1data[i]->distance|=SEGMENT_SUPER; /* mark as super-segment */
          m++;
          j++;
          break;
         }
       else if((segmentsx->n1data[i]->node1==supersegmentsx->n1data[j]->node1 &&
                segmentsx->n1data[i]->node2==supersegmentsx->n1data[j]->node2) ||
               (segmentsx->n1data[i]->node1==supersegmentsx->n1data[j]->node1 &&
                segmentsx->n1data[i]->node2>supersegmentsx->n1data[j]->node2) ||
               (segmentsx->n1data[i]->node1>supersegmentsx->n1data[j]->node1))
         {
          supersegmentsx->n1data[j]->distance|=SEGMENT_SUPER; /* mark as super-segment */
          AppendSegment(segmentsx,supersegmentsx->n1data[j]->way,supersegmentsx->n1data[j]->node1,supersegmentsx->n1data[j]->node2,supersegmentsx->n1data[j]->distance);
          a++;
          j++;
         }
       else
          break;
      }

    segmentsx->n1data[i]->distance|=SEGMENT_NORMAL; /* mark as normal segment (as well) */

    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);
}


/*++++++++++++++++++++++++++++++++++++++
  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;
 NodeX **nodex;
 SegmentX **segmentx;
 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;

    segmentx=FindFirstSegmentX(segmentsx,node1);

    while(segmentx)
      {
       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;

          nodex=FindNodeX(nodesx,node2);

          if((*nodex)->super<=iteration)
             InsertInQueue(queue,result2);
         }
       else if(cumulative_distance<result2->score)
         {
          result2->prev=node1;
          result2->score=cumulative_distance;
          result2->sortby=cumulative_distance;

          nodex=FindNodeX(nodesx,node2);

          if((*nodex)->super<=iteration)
             InsertInQueue(queue,result2);
         }

      endloop:

       segmentx=FindNextSegmentX(segmentsx,segmentx);
      }
   }

 FreeQueueList(queue);

 return(results);
}
1	amb	110	/***************************************
2	amb	236	$Header: /home/amb/CVS/routino/src/superx.c,v 1.26 2009-08-15 14:18:23 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	229	assert(nodesx->idata); /* Must have idata filled in */
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			SegmentX **segmentx;
68	amb	110
69	amb	229	segmentx=FindFirstSegmentX(segmentsx,nodesx->idata[i]->id);
70
71			if(segmentx)
72	amb	110	{
73	amb	229	WayX wayx1=FindWayX(waysx,(segmentx)->way);
74	amb	110
75	amb	229	segmentx=FindNextSegmentX(segmentsx,segmentx);
76
77			if(segmentx)
78	amb	110	{
79	amb	229	WayX wayx2=FindWayX(waysx,(segmentx)->way);
80	amb	110
81	amb	229	if(WaysCompare(wayx2->way,wayx1->way))
82			difference=1;
83	amb	110
84	amb	229	segmentx=FindNextSegmentX(segmentsx,segmentx);
85	amb	110	}
86
87	amb	229	/* Store the node if there is a difference in the first two ways that could affect routing.
88			Store the node if it has at least three segments. */
89	amb	110
90	amb	229	if(difference \|\| segmentx)
91			{
92			nodesx->idata[i]->super++;
93	amb	110
94	amb	229	nnodes++;
95			}
96	amb	110	}
97
98			if(!((i+1)%10000))
99			{
100	amb	231	printf("\rFinding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
101	amb	110	fflush(stdout);
102			}
103			}
104
105	amb	231	printf("\rFound Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
106	amb	110	fflush(stdout);
107			}
108
109
110			/*++++++++++++++++++++++++++++++++++++++
111			Create the super-segments.
112
113			SegmentsX *CreateSuperSegments Creates the super segments.
114
115			NodesX *nodesx The nodes.
116
117			SegmentsX *segmentsx The segments.
118
119			WaysX *waysx The ways.
120
121			int iteration The current super-node / super-segment iteration number.
122			++++++++++++++++++++++++++++++++++++++*/
123
124			SegmentsX CreateSuperSegments(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,int iteration)
125			{
126	amb	214	index_t i;
127	amb	110	SegmentsX *supersegmentsx;
128	amb	227	int sn=0,ss=0;
129	amb	110
130	amb	213	assert(nodesx->idata); /* Must have idata filled in */
131
132	amb	227	printf("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
133			fflush(stdout);
134
135	amb	110	supersegmentsx=NewSegmentList();
136
137			/* Create super-segments for each super-node. */
138
139			for(i=0;i<nodesx->number;i++)
140			{
141	amb	212	if(nodesx->idata[i]->super>iteration)
142	amb	110	{
143			SegmentX segmentx,first;
144
145	amb	212	segmentx=first=FindFirstSegmentX(segmentsx,nodesx->idata[i]->id);
146	amb	110
147			while(segmentx)
148			{
149	amb	204	WayX wayx=FindWayX(waysx,(segmentx)->way);
150	amb	110
151			/* Check that this type of way hasn't already been routed */
152
153			if(segmentx!=first)
154			{
155			SegmentX **othersegmentx=first;
156
157			while(othersegmentx && othersegmentx!=segmentx)
158			{
159	amb	204	WayX otherwayx=FindWayX(waysx,(othersegmentx)->way);
160	amb	110
161	amb	204	if(!WaysCompare(otherwayx->way,wayx->way))
162	amb	110	{
163	amb	204	wayx=NULL;
164	amb	110	break;
165			}
166
167			othersegmentx=FindNextSegmentX(segmentsx,othersegmentx);
168			}
169			}
170
171			/* Route the way and store the super-segments. */
172
173	amb	204	if(wayx)
174	amb	110	{
175	amb	212	Results *results=FindRoutesWay(nodesx,segmentsx,waysx,nodesx->idata[i]->id,wayx->way,iteration);
176	amb	110	Result *result=FirstResult(results);
177
178			while(result)
179			{
180	amb	212	NodeX **nodex=FindNodeX(nodesx,result->node);
181			WayX wayx =FindWayX (waysx ,(segmentx)->way);
182	amb	110
183	amb	212	if(result->node!=nodesx->idata[i]->id && (*nodex)->super>iteration)
184	amb	110	{
185	amb	203	if(wayx->way->type&Way_OneWay)
186	amb	212	AppendSegment(supersegmentsx,wayx->id,nodesx->idata[i]->id,result->node,DISTANCE((distance_t)result->score)\|ONEWAY_1TO2);
187	amb	172	else
188	amb	212	AppendSegment(supersegmentsx,wayx->id,result->node,nodesx->idata[i]->id,DISTANCE((distance_t)result->score));
189	amb	216
190	amb	229	ss++;
191	amb	110	}
192
193			result=NextResult(results,result);
194			}
195
196			FreeResultsList(results);
197			}
198
199			segmentx=FindNextSegmentX(segmentsx,segmentx);
200			}
201	amb	227
202			sn++;
203	amb	110
204	amb	229	if(!(sn%10000))
205			{
206			printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
207			fflush(stdout);
208			}
209	amb	110	}
210			}
211
212	amb	227	printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",sn,ss);
213	amb	110	fflush(stdout);
214
215			return(supersegmentsx);
216			}
217
218
219			/*++++++++++++++++++++++++++++++++++++++
220			Merge the super-segments into the segments.
221
222			SegmentsX* segmentsx The set of segments to process.
223
224			SegmentsX* supersegmentsx The set of super-segments to merge.
225			++++++++++++++++++++++++++++++++++++++*/
226
227			void MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
228			{
229	amb	216	index_t i,j;
230			int m=0,a=0;
231	amb	110
232			assert(segmentsx->sorted); /* Must be sorted */
233	amb	229	assert(segmentsx->n1data); /* Must have n1data filled in */
234	amb	110	assert(supersegmentsx->sorted); /* Must be sorted */
235	amb	229	assert(supersegmentsx->n1data); /* Must have n1data filled in */
236	amb	110
237	amb	227	printf("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0");
238			fflush(stdout);
239
240	amb	216	for(i=0,j=0;i<segmentsx->number;i++)
241	amb	110	{
242			while(j<supersegmentsx->number)
243			{
244	amb	229	if(segmentsx->n1data[i]->node1==supersegmentsx->n1data[j]->node1 &&
245			segmentsx->n1data[i]->node2==supersegmentsx->n1data[j]->node2 &&
246			segmentsx->n1data[i]->distance==supersegmentsx->n1data[j]->distance)
247	amb	110	{
248	amb	229	segmentsx->n1data[i]->distance\|=SEGMENT_SUPER; /* mark as super-segment */
249	amb	216	m++;
250	amb	110	j++;
251			break;
252			}
253	amb	229	else if((segmentsx->n1data[i]->node1==supersegmentsx->n1data[j]->node1 &&
254			segmentsx->n1data[i]->node2==supersegmentsx->n1data[j]->node2) \|\|
255			(segmentsx->n1data[i]->node1==supersegmentsx->n1data[j]->node1 &&
256			segmentsx->n1data[i]->node2>supersegmentsx->n1data[j]->node2) \|\|
257			(segmentsx->n1data[i]->node1>supersegmentsx->n1data[j]->node1))
258	amb	110	{
259	amb	229	supersegmentsx->n1data[j]->distance\|=SEGMENT_SUPER; /* mark as super-segment */
260			AppendSegment(segmentsx,supersegmentsx->n1data[j]->way,supersegmentsx->n1data[j]->node1,supersegmentsx->n1data[j]->node2,supersegmentsx->n1data[j]->distance);
261	amb	216	a++;
262			j++;
263	amb	110	}
264			else
265			break;
266			}
267
268	amb	229	segmentsx->n1data[i]->distance\|=SEGMENT_NORMAL; /* mark as normal segment (as well) */
269	amb	208
270	amb	110	if(!((i+1)%10000))
271			{
272	amb	216	printf("\rMerging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
273	amb	110	fflush(stdout);
274			}
275			}
276
277	amb	216	printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
278	amb	110	fflush(stdout);
279			}
280
281
282			/*++++++++++++++++++++++++++++++++++++++
283			Find all routes from a specified node to any node in the specified list that follows a certain type of way.
284
285			Results *FindRoutesWay Returns a set of results.
286
287			NodesX *nodesx The set of nodes to use.
288
289			SegmentsX *segmentsx The set of segments to use.
290
291			WaysX *waysx The set of ways to use.
292
293			node_t start The start node.
294
295	amb	203	Way *match The way that the route must match.
296	amb	110
297			int iteration The current super-node / super-segment iteration number.
298			++++++++++++++++++++++++++++++++++++++*/
299
300	amb	228	static Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,Way *match,int iteration)
301	amb	110	{
302			Results *results;
303	amb	236	Queue *queue;
304	amb	110	index_t node1,node2;
305			Result result1,result2;
306	amb	212	NodeX **nodex;
307	amb	110	SegmentX **segmentx;
308	amb	204	WayX *wayx;
309	amb	110
310			/* Insert the first node into the queue */
311
312			results=NewResultsList(8);
313
314	amb	236	queue=NewQueueList();
315
316	amb	110	result1=InsertResult(results,start);
317
318	amb	166	ZeroResult(result1);
319	amb	110
320	amb	236	InsertInQueue(queue,result1);
321	amb	110
322			/* Loop across all nodes in the queue */
323
324	amb	236	while((result1=PopFromQueue(queue)))
325	amb	110	{
326			node1=result1->node;
327
328			segmentx=FindFirstSegmentX(segmentsx,node1);
329
330			while(segmentx)
331			{
332	amb	113	distance_t cumulative_distance;
333
334	amb	229	if((segmentx)->node1==node1) / Correct way round */
335			{
336			if((*segmentx)->distance&ONEWAY_2TO1)
337			goto endloop;
338	amb	110
339	amb	229	node2=(*segmentx)->node2;
340			}
341			else /* Opposite way round */
342			{
343			if((*segmentx)->distance&ONEWAY_1TO2)
344			goto endloop;
345	amb	110
346	amb	229	node2=(*segmentx)->node1;
347			}
348
349	amb	113	if(result1->prev==node2)
350	amb	110	goto endloop;
351
352	amb	204	wayx=FindWayX(waysx,(*segmentx)->way);
353	amb	110
354	amb	204	if(WaysCompare(wayx->way,match))
355	amb	110	goto endloop;
356
357	amb	209	cumulative_distance=(distance_t)result1->score+DISTANCE((*segmentx)->distance);
358	amb	110
359			result2=FindResult(results,node2);
360
361			if(!result2) /* New end node */
362			{
363			result2=InsertResult(results,node2);
364	amb	113	result2->prev=node1;
365	amb	176	result2->next=NO_NODE;
366	amb	172	result2->score=cumulative_distance;
367	amb	166	result2->sortby=cumulative_distance;
368	amb	110
369			nodex=FindNodeX(nodesx,node2);
370
371	amb	212	if((*nodex)->super<=iteration)
372	amb	236	InsertInQueue(queue,result2);
373	amb	110	}
374	amb	172	else if(cumulative_distance<result2->score)
375	amb	110	{
376	amb	166	result2->prev=node1;
377	amb	172	result2->score=cumulative_distance;
378	amb	166	result2->sortby=cumulative_distance;
379	amb	110
380	amb	166	nodex=FindNodeX(nodesx,node2);
381	amb	110
382	amb	212	if((*nodex)->super<=iteration)
383	amb	236	InsertInQueue(queue,result2);
384	amb	110	}
385
386			endloop:
387
388			segmentx=FindNextSegmentX(segmentsx,segmentx);
389			}
390			}
391
392	amb	236	FreeQueueList(queue);
393
394	amb	110	return(results);
395			}