trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.27 2009-02-06 20:23:33 amb Exp $

 Super-Segment data type functions.
 ******************/ /******************
 Written by Andrew M. Bishop

 This file Copyright 2008,2009 Andrew M. Bishop
 It may be distributed under the GNU Public License, version 2, or
 any higher version.  See section COPYING of the GNU Public license
 for conditions under which this file may be redistributed.
 ***************************************/


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

#include "results.h"
#include "nodes.h"
#include "ways.h"
#include "segments.h"
#include "functions.h"


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

  NodesX *nodesx The nodes.

  SegmentsX *segmentsx The segments.

  WaysX *waysx The ways.

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

void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,int iteration)
{
 int i;
 int        segcount=0,difference=0,nnodes=0;
 node_t     node=0;
 speed_t    limit=0;
 waytype_t  type=0;
 wayallow_t allow=0;

 /* Find super-nodes */

 node=segmentsx->sdata[0]->node1;

 for(i=0;i<segmentsx->number;i++)
   {
    SegmentX *segmentx=LookupSegmentX(segmentsx,i);
    WayX *wayx=LookupWayX(waysx,segmentx->segment.way);

    if(segmentx->node1!=node)
      {
       /* Store the node if there is a difference in the ways that could affect routing.
          Store the node if it is not a dead-end and if it isn't just the middle of a way. */

       if(difference || segcount>2)
         {
          NodeX *nodex=FindNodeX(nodesx,node);

          nodex->super++;

          nnodes++;
         }

       segcount=1;
       difference=0;

       node=segmentx->node1;
       type=wayx->way.type;
       limit=wayx->way.limit;
       allow=wayx->way.allow;
      }
    else                        /* Same starting node */
      {
       if(wayx->way.type!=type)
          difference=1;

       if(wayx->way.limit!=limit)
          difference=1;

       if(wayx->way.allow!=allow)
          difference=1;

       segcount+=1;
      }

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

 printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d  \n",segmentsx->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)
{
 int i;
 SegmentsX *supersegmentsx;

 supersegmentsx=NewSegmentList();

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

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

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

       while(segmentx)
         {
          WayX *wayx=LookupWayX(waysx,(*segmentx)->segment.way);

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

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

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

                if(otherwayx->way.type ==wayx->way.type  &&
                   otherwayx->way.allow==wayx->way.allow &&
                   otherwayx->way.limit==wayx->way.limit)
                  {
                   wayx=NULL;
                   break;
                  }

                othersegmentx=FindNextSegmentX(segmentsx,othersegmentx);
               }
            }

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

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

             while(result)
               {
                NodeX *nodex=FindNodeX(nodesx,result->node);

                if(result->node!=nodesx->gdata[i]->id && nodex->super>iteration)
                  {
                   Segment *supersegment=AppendSegment(supersegmentsx,nodesx->gdata[i]->id,result->node);

                   supersegment->distance=result->shortest.distance;
                   supersegment->way=IndexWayX(waysx,wayx);

                   if(wayx->way.type&Way_OneWay)
                     {
                      supersegment->distance=ONEWAY_1TO2|result->shortest.distance;

                      supersegment=AppendSegment(supersegmentsx,result->node,nodesx->gdata[i]->id);

                      supersegment->distance=ONEWAY_2TO1|result->shortest.distance;
                      supersegment->way=IndexWayX(waysx,wayx);
                     }
                  }

                result=NextResult(results,result);
               }

             FreeResultsList(results);
            }

          segmentx=FindNextSegmentX(segmentsx,segmentx);
         }
      }

    if(!((i+1)%10000))
      {
       printf("\rCreating Super-Segments: Nodes=%d Super-Segments=%d",i+1,supersegmentsx->number);
       fflush(stdout);
      }
   }

 printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesx->number,supersegmentsx->number);
 fflush(stdout);

 /* Append the new supersegments onto the segments. */

 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)
{
 int i,j,n;

 assert(segmentsx->sorted);      /* Must be sorted */
 assert(supersegmentsx->sorted); /* Must be sorted */

 n=segmentsx->number;

 for(i=0,j=0;i<n;i++)
   {
    segmentsx->sdata[i]->segment.node1=SUPER_FLAG; /* mark as normal segment */

    segmentsx->sdata[i]->segment.next1=~0;
    segmentsx->sdata[i]->segment.next2=~0;

    while(j<supersegmentsx->number)
      {
       if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
          segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2 &&
          segmentsx->sdata[i]->segment.distance==supersegmentsx->sdata[j]->segment.distance)
         {
          segmentsx->sdata[i]->segment.node2=SUPER_FLAG; /* mark as super-segment */
          j++;
          break;
         }
       else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
               segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2)
         {
          Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);

          *supersegment=supersegmentsx->sdata[j]->segment;
          supersegment->node2=SUPER_FLAG; /* mark as super-segment */
          supersegment->next1=~0;
          supersegment->next2=~0;
         }
       else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
               segmentsx->sdata[i]->node2>supersegmentsx->sdata[j]->node2)
         {
          Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);

          *supersegment=supersegmentsx->sdata[j]->segment;
          supersegment->node2=SUPER_FLAG; /* mark as super-segment */
          supersegment->next1=~0;
          supersegment->next2=~0;
         }
       else if(segmentsx->sdata[i]->node1>supersegmentsx->sdata[j]->node1)
         {
          Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);

          *supersegment=supersegmentsx->sdata[j]->segment;
          supersegment->node2=SUPER_FLAG; /* mark as super-segment */
          supersegment->next1=~0;
          supersegment->next2=~0;
         }
       else
          break;

       j++;
      }

    if(!((i+1)%10000))
      {
       printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsx->number);
       fflush(stdout);
      }
   }

 printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsx->number,segmentsx->number);
 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.

  WayX *match The way that the route must match.

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

Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,WayX *match,int iteration)
{
 Results *results;
 index_t node1,node2;
 HalfResult shortest2;
 Result *result1,*result2;
 NodeX *nodex;
 SegmentX **segmentx;
 WayX *wayx;

 /* Insert the first node into the queue */

 results=NewResultsList(8);

 result1=InsertResult(results,start);

 result1->node=start;
 result1->shortest.prev=0;
 result1->shortest.next=0;
 result1->shortest.distance=0;

 insert_in_queue(result1);

 /* Loop across all nodes in the queue */

 while((result1=pop_from_queue()))
   {
    node1=result1->node;

    segmentx=FindFirstSegmentX(segmentsx,node1);

    while(segmentx)
      {
       if((*segmentx)->segment.distance&ONEWAY_2TO1)
          goto endloop;

       node2=(*segmentx)->node2;

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

       wayx=LookupWayX(waysx,(*segmentx)->segment.way);

       if(wayx->way.type !=match->way.type  ||
          wayx->way.allow!=match->way.allow ||
          wayx->way.limit!=match->way.limit)
          goto endloop;

       shortest2.distance=result1->shortest.distance+DISTANCE((*segmentx)->segment.distance);

       result2=FindResult(results,node2);

       if(!result2)                         /* New end node */
         {
          result2=InsertResult(results,node2);
          result2->node=node2;
          result2->shortest.prev=node1;
          result2->shortest.next=0;
          result2->shortest.distance=shortest2.distance;

          nodex=FindNodeX(nodesx,node2);

          if(nodex->super<=iteration)
             insert_in_queue(result2);
         }
       else
         {
          if(shortest2.distance<result2->shortest.distance)
            {
             result2->shortest.prev=node1;
             result2->shortest.distance=shortest2.distance;

             nodex=FindNodeX(nodesx,node2);

             if(nodex->super<=iteration)
                insert_in_queue(result2);
            }
         }

      endloop:

       segmentx=FindNextSegmentX(segmentsx,segmentx);
      }
   }

 return(results);
}
1	amb	16	/***************************************
2	amb	104	$Header: /home/amb/CVS/routino/src/supersegments.c,v 1.27 2009-02-06 20:23:33 amb Exp $
3	amb	16
4			Super-Segment data type functions.
5			****************/ /****************
6			Written by Andrew M. Bishop
7
8			This file Copyright 2008,2009 Andrew M. Bishop
9			It may be distributed under the GNU Public License, version 2, or
10			any higher version. See section COPYING of the GNU Public license
11			for conditions under which this file may be redistributed.
12			***************************************/
13
14
15			#include <assert.h>
16			#include <math.h>
17			#include <stdlib.h>
18
19	amb	104	#include "results.h"
20	amb	26	#include "nodes.h"
21			#include "ways.h"
22			#include "segments.h"
23	amb	16	#include "functions.h"
24
25	amb	89
26	amb	16	/*++++++++++++++++++++++++++++++++++++++
27			Select the super-segments from the list of segments.
28
29	amb	97	NodesX *nodesx The nodes.
30	amb	16
31	amb	97	SegmentsX *segmentsx The segments.
32	amb	16
33	amb	97	WaysX *waysx The ways.
34	amb	16
35	amb	89	int iteration The current super-node / super-segment iteration number.
36	amb	16	++++++++++++++++++++++++++++++++++++++*/
37
38	amb	97	void ChooseSuperNodes(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx,int iteration)
39	amb	16	{
40	amb	31	int i;
41	amb	89	int segcount=0,difference=0,nnodes=0;
42	amb	52	node_t node=0;
43			speed_t limit=0;
44			waytype_t type=0;
45			wayallow_t allow=0;
46	amb	16
47	amb	54	/* Find super-nodes */
48
49	amb	104	node=segmentsx->sdata[0]->node1;
50	amb	52
51	amb	97	for(i=0;i<segmentsx->number;i++)
52	amb	31	{
53	amb	97	SegmentX *segmentx=LookupSegmentX(segmentsx,i);
54			WayX *wayx=LookupWayX(waysx,segmentx->segment.way);
55	amb	31
56	amb	97	if(segmentx->node1!=node)
57	amb	31	{
58	amb	90	/* Store the node if there is a difference in the ways that could affect routing.
59			Store the node if it is not a dead-end and if it isn't just the middle of a way. */
60
61			if(difference \|\| segcount>2)
62	amb	31	{
63	amb	98	NodeX *nodex=FindNodeX(nodesx,node);
64	amb	31
65	amb	97	nodex->super++;
66	amb	31
67	amb	90	nnodes++;
68			}
69	amb	52
70	amb	90	segcount=1;
71			difference=0;
72	amb	31
73	amb	97	node=segmentx->node1;
74			type=wayx->way.type;
75			limit=wayx->way.limit;
76			allow=wayx->way.allow;
77	amb	90	}
78			else /* Same starting node */
79			{
80	amb	97	if(wayx->way.type!=type)
81	amb	90	difference=1;
82	amb	31
83	amb	97	if(wayx->way.limit!=limit)
84	amb	90	difference=1;
85	amb	31
86	amb	97	if(wayx->way.allow!=allow)
87	amb	90	difference=1;
88	amb	89
89	amb	90	segcount+=1;
90	amb	52	}
91	amb	31
92	amb	38	if(!((i+1)%10000))
93	amb	31	{
94	amb	89	printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,nnodes);
95	amb	31	fflush(stdout);
96			}
97			}
98
99	amb	97	printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d \n",segmentsx->number,nnodes);
100	amb	31	fflush(stdout);
101	amb	16	}
102	amb	31
103
104			/*++++++++++++++++++++++++++++++++++++++
105			Create the super-segments.
106
107	amb	97	SegmentsX *CreateSuperSegments Creates the super segments.
108	amb	90
109	amb	97	NodesX *nodesx The nodes.
110	amb	31
111	amb	97	SegmentsX *segmentsx The segments.
112	amb	31
113	amb	97	WaysX *waysx The ways.
114	amb	31
115	amb	89	int iteration The current super-node / super-segment iteration number.
116	amb	31	++++++++++++++++++++++++++++++++++++++*/
117
118	amb	97	SegmentsX CreateSuperSegments(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,int iteration)
119	amb	31	{
120	amb	79	int i;
121	amb	97	SegmentsX *supersegmentsx;
122	amb	31
123	amb	97	supersegmentsx=NewSegmentList();
124	amb	31
125	amb	54	/* Create super-segments for each super-node. */
126
127	amb	97	for(i=0;i<nodesx->number;i++)
128	amb	31	{
129	amb	104	if(nodesx->gdata[i]->super>iteration)
130	amb	54	{
131	amb	104	SegmentX segmentx,first;
132	amb	54
133	amb	104	segmentx=first=FindFirstSegmentX(segmentsx,nodesx->gdata[i]->id);
134	amb	54
135	amb	97	while(segmentx)
136	amb	56	{
137	amb	104	WayX wayx=LookupWayX(waysx,(segmentx)->segment.way);
138	amb	56
139	amb	89	/* Check that this type of way hasn't already been routed */
140
141	amb	97	if(segmentx!=first)
142	amb	56	{
143	amb	104	SegmentX **othersegmentx=first;
144	amb	56
145	amb	97	while(othersegmentx && othersegmentx!=segmentx)
146	amb	56	{
147	amb	104	WayX otherwayx=LookupWayX(waysx,(othersegmentx)->segment.way);
148	amb	89
149	amb	97	if(otherwayx->way.type ==wayx->way.type &&
150			otherwayx->way.allow==wayx->way.allow &&
151			otherwayx->way.limit==wayx->way.limit)
152	amb	89	{
153	amb	97	wayx=NULL;
154	amb	89	break;
155			}
156
157	amb	98	othersegmentx=FindNextSegmentX(segmentsx,othersegmentx);
158	amb	56	}
159			}
160
161	amb	89	/* Route the way and store the super-segments. */
162	amb	54
163	amb	97	if(wayx)
164	amb	89	{
165	amb	104	Results *results=FindRoutesWay(nodesx,segmentsx,waysx,nodesx->gdata[i]->id,wayx,iteration);
166	amb	89	Result *result=FirstResult(results);
167	amb	31
168	amb	89	while(result)
169	amb	54	{
170	amb	98	NodeX *nodex=FindNodeX(nodesx,result->node);
171	amb	31
172	amb	104	if(result->node!=nodesx->gdata[i]->id && nodex->super>iteration)
173	amb	62	{
174	amb	104	Segment *supersegment=AppendSegment(supersegmentsx,nodesx->gdata[i]->id,result->node);
175	amb	62
176	amb	98	supersegment->distance=result->shortest.distance;
177			supersegment->way=IndexWayX(waysx,wayx);
178	amb	89
179	amb	97	if(wayx->way.type&Way_OneWay)
180	amb	89	{
181	amb	104	supersegment->distance=ONEWAY_1TO2\|result->shortest.distance;
182	amb	89
183	amb	104	supersegment=AppendSegment(supersegmentsx,result->node,nodesx->gdata[i]->id);
184
185			supersegment->distance=ONEWAY_2TO1\|result->shortest.distance;
186	amb	98	supersegment->way=IndexWayX(waysx,wayx);
187	amb	89	}
188	amb	62	}
189	amb	89
190			result=NextResult(results,result);
191	amb	54	}
192
193	amb	89	FreeResultsList(results);
194	amb	79	}
195
196	amb	98	segmentx=FindNextSegmentX(segmentsx,segmentx);
197	amb	45	}
198	amb	54	}
199	amb	31
200	amb	90	if(!((i+1)%10000))
201	amb	31	{
202	amb	97	printf("\rCreating Super-Segments: Nodes=%d Super-Segments=%d",i+1,supersegmentsx->number);
203	amb	31	fflush(stdout);
204			}
205			}
206
207	amb	97	printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesx->number,supersegmentsx->number);
208	amb	31	fflush(stdout);
209
210	amb	89	/* Append the new supersegments onto the segments. */
211	amb	54
212	amb	97	return(supersegmentsx);
213	amb	54	}
214	amb	97
215
216			/*++++++++++++++++++++++++++++++++++++++
217	amb	104	Merge the super-segments into the segments.
218
219			SegmentsX* segmentsx The set of segments to process.
220
221			SegmentsX* supersegmentsx The set of super-segments to merge.
222			++++++++++++++++++++++++++++++++++++++*/
223
224			void MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
225			{
226			int i,j,n;
227
228			assert(segmentsx->sorted); /* Must be sorted */
229			assert(supersegmentsx->sorted); /* Must be sorted */
230
231			n=segmentsx->number;
232
233			for(i=0,j=0;i<n;i++)
234			{
235			segmentsx->sdata[i]->segment.node1=SUPER_FLAG; /* mark as normal segment */
236
237			segmentsx->sdata[i]->segment.next1=~0;
238			segmentsx->sdata[i]->segment.next2=~0;
239
240			while(j<supersegmentsx->number)
241			{
242			if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
243			segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2 &&
244			segmentsx->sdata[i]->segment.distance==supersegmentsx->sdata[j]->segment.distance)
245			{
246			segmentsx->sdata[i]->segment.node2=SUPER_FLAG; /* mark as super-segment */
247			j++;
248			break;
249			}
250			else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
251			segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2)
252			{
253			Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);
254
255			*supersegment=supersegmentsx->sdata[j]->segment;
256			supersegment->node2=SUPER_FLAG; /* mark as super-segment */
257			supersegment->next1=~0;
258			supersegment->next2=~0;
259			}
260			else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
261			segmentsx->sdata[i]->node2>supersegmentsx->sdata[j]->node2)
262			{
263			Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);
264
265			*supersegment=supersegmentsx->sdata[j]->segment;
266			supersegment->node2=SUPER_FLAG; /* mark as super-segment */
267			supersegment->next1=~0;
268			supersegment->next2=~0;
269			}
270			else if(segmentsx->sdata[i]->node1>supersegmentsx->sdata[j]->node1)
271			{
272			Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);
273
274			*supersegment=supersegmentsx->sdata[j]->segment;
275			supersegment->node2=SUPER_FLAG; /* mark as super-segment */
276			supersegment->next1=~0;
277			supersegment->next2=~0;
278			}
279			else
280			break;
281
282			j++;
283			}
284
285			if(!((i+1)%10000))
286			{
287			printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsx->number);
288			fflush(stdout);
289			}
290			}
291
292			printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsx->number,segmentsx->number);
293			fflush(stdout);
294			}
295
296
297			/*++++++++++++++++++++++++++++++++++++++
298	amb	97	Find all routes from a specified node to any node in the specified list that follows a certain type of way.
299
300			Results *FindRoutesWay Returns a set of results.
301
302			NodesX *nodesx The set of nodes to use.
303
304			SegmentsX *segmentsx The set of segments to use.
305
306			WaysX *waysx The set of ways to use.
307
308			node_t start The start node.
309
310			WayX *match The way that the route must match.
311
312			int iteration The current super-node / super-segment iteration number.
313			++++++++++++++++++++++++++++++++++++++*/
314
315			Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,WayX *match,int iteration)
316			{
317			Results *results;
318			index_t node1,node2;
319			HalfResult shortest2;
320			Result result1,result2;
321			NodeX *nodex;
322	amb	104	SegmentX **segmentx;
323	amb	97	WayX *wayx;
324
325			/* Insert the first node into the queue */
326
327			results=NewResultsList(8);
328
329			result1=InsertResult(results,start);
330
331			result1->node=start;
332			result1->shortest.prev=0;
333			result1->shortest.next=0;
334			result1->shortest.distance=0;
335
336			insert_in_queue(result1);
337
338			/* Loop across all nodes in the queue */
339
340			while((result1=pop_from_queue()))
341			{
342			node1=result1->node;
343
344	amb	98	segmentx=FindFirstSegmentX(segmentsx,node1);
345	amb	97
346			while(segmentx)
347			{
348	amb	104	if((*segmentx)->segment.distance&ONEWAY_2TO1)
349	amb	97	goto endloop;
350
351	amb	104	node2=(*segmentx)->node2;
352	amb	97
353			if(result1->shortest.prev==node2)
354			goto endloop;
355
356	amb	104	wayx=LookupWayX(waysx,(*segmentx)->segment.way);
357	amb	97
358			if(wayx->way.type !=match->way.type \|\|
359			wayx->way.allow!=match->way.allow \|\|
360			wayx->way.limit!=match->way.limit)
361			goto endloop;
362
363	amb	104	shortest2.distance=result1->shortest.distance+DISTANCE((*segmentx)->segment.distance);
364	amb	97
365			result2=FindResult(results,node2);
366
367			if(!result2) /* New end node */
368			{
369			result2=InsertResult(results,node2);
370			result2->node=node2;
371			result2->shortest.prev=node1;
372			result2->shortest.next=0;
373			result2->shortest.distance=shortest2.distance;
374
375	amb	98	nodex=FindNodeX(nodesx,node2);
376	amb	97
377			if(nodex->super<=iteration)
378			insert_in_queue(result2);
379			}
380			else
381			{
382			if(shortest2.distance<result2->shortest.distance)
383			{
384			result2->shortest.prev=node1;
385			result2->shortest.distance=shortest2.distance;
386
387	amb	98	nodex=FindNodeX(nodesx,node2);
388	amb	97
389			if(nodex->super<=iteration)
390			insert_in_queue(result2);
391			}
392			}
393
394			endloop:
395
396	amb	98	segmentx=FindNextSegmentX(segmentsx,segmentx);
397	amb	97	}
398			}
399
400			return(results);
401			}