trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.39 2010-07-12 17:59:42 amb Exp $

 Super-Segment data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2010 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 "ways.h"

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

#include "files.h"
#include "results.h"


/* Variables */

/*+ The command line '--slim' option. +*/
extern int option_slim;

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

 /* Check the start conditions */

 assert(segmentsx->firstnode); /* Must have firstnode filled in => segments are updated */

 /* Print the start message */

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

 /* Map into memory */

 if(!option_slim)
   {
    segmentsx->xdata=MapFile(segmentsx->filename);
    waysx->xdata=MapFile(waysx->filename);
   }

 /* Find super-nodes */

 for(i=0;i<nodesx->number;i++)
   {
    int difference=0;
    index_t index1,index2;

    index1=IndexFirstSegmentX(segmentsx,i);

    while(index1!=NO_SEGMENT)
      {
       SegmentX *segmentx1=LookupSegmentX(segmentsx,index1,1);
       WayX *wayx1=LookupWayX(waysx,segmentx1->way,1);

       index1=IndexNextSegmentX(segmentsx,index1,i);
       index2=index1;

       while(index2!=NO_SEGMENT)
         {
          SegmentX *segmentx2=LookupSegmentX(segmentsx,index2,2);
          WayX *wayx2=LookupWayX(waysx,segmentx2->way,2);

          /* If the ways are different in any way and there is a type of traffic that can use both ... */

          if(WaysCompare(&wayx1->way,&wayx2->way))
             if(wayx1->way.allow & wayx2->way.allow)
               {
                difference=1;
                break;
               }

          index2=IndexNextSegmentX(segmentsx,index2,i);
         }

       if(difference)
          break;
      }

    /* Store the node if there is a difference in the connected ways that could affect routing. */

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

       nnodes++;
      }

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

 /* Unmap from memory */

 if(!option_slim)
   {
    segmentsx->xdata=UnmapFile(segmentsx->filename);
    waysx->xdata=UnmapFile(waysx->filename);
   }

 /* Print the final message */

 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;

 /* Check the start conditions */

 assert(segmentsx->firstnode); /* Must have firstnode filled in => segments are updated */

 /* Print the start message */

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

 /* Map into memory */

 if(!option_slim)
   {
    segmentsx->xdata=MapFile(segmentsx->filename);
    waysx->xdata=MapFile(waysx->filename);
   }

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

 supersegmentsx=NewSegmentList(0);

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

       index=first=IndexFirstSegmentX(segmentsx,i);

       while(index!=NO_SEGMENT)
         {
          SegmentX *segmentx=LookupSegmentX(segmentsx,index,1);
          WayX *wayx=LookupWayX(waysx,segmentx->way,1);

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

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

             while(otherindex!=NO_SEGMENT && otherindex!=index)
               {
                SegmentX *othersegmentx=LookupSegmentX(segmentsx,otherindex,2);
                WayX *otherwayx=LookupWayX(waysx,othersegmentx->way,2);

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

                otherindex=IndexNextSegmentX(segmentsx,otherindex,i);
               }
            }

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

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

             while(result)
               {
                if(result->node!=i && nodesx->super[result->node]>iteration)
                  {
                   if(wayx->way.type&Way_OneWay)
                     {
                      AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2);
                      AppendSegment(supersegmentsx,segmentx->way,result->node,i,DISTANCE((distance_t)result->score)|ONEWAY_2TO1);
                     }
                   else
                      AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));

                   ss++;
                  }

                result=NextResult(results,result);
               }

             FreeResultsList(results);
            }

          index=IndexNextSegmentX(segmentsx,index,i);
         }

       sn++;

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

 /* Unmap from memory */

 if(!option_slim)
   {
    segmentsx->xdata=UnmapFile(segmentsx->filename);
    waysx->xdata=UnmapFile(waysx->filename);
   }

 /* Print the final message */

 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;

 /* Print the start message */

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

 /* Map into memory */

 if(!option_slim)
   {
    segmentsx->xdata=MapFile(segmentsx->filename);
    supersegmentsx->xdata=MapFile(supersegmentsx->filename);
   }

 /* Loop through and create a new list of combined segments */

 mergedsegmentsx=NewSegmentList(0);

 for(i=0,j=0;i<segmentsx->number;i++)
   {
    int super=0;
    SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);

    while(j<supersegmentsx->number)
      {
       SegmentX *supersegmentx=LookupSegmentX(supersegmentsx,j,1);

       if(segmentx->node1   ==supersegmentx->node1 &&
          segmentx->node2   ==supersegmentx->node2 &&
          segmentx->distance==supersegmentx->distance)
         {
          m++;
          j++;
          /* mark as super-segment and normal segment */
          super=1;
          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
         {
          /* mark as normal segment */
          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);
      }
   }

 /* Unmap from memory */

 if(!option_slim)
   {
    segmentsx->xdata=UnmapFile(segmentsx->filename);
    supersegmentsx->xdata=UnmapFile(supersegmentsx->filename);
   }

 /* Print the final message */

 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!=NO_SEGMENT)
      {
       SegmentX *segmentx=LookupSegmentX(segmentsx,index,2); /* must use 2 here */
       distance_t cumulative_distance;

       if(segmentx->distance&ONEWAY_2TO1)
          goto endloop;

       node2=segmentx->node2;

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

       wayx=LookupWayX(waysx,segmentx->way,2);

       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[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[node2]<=iteration)
             InsertInQueue(queue,result2);
         }

      endloop:

       index=IndexNextSegmentX(segmentsx,index,node1);
      }
   }

 FreeQueueList(queue);

 return(results);
}
1	amb	110	/***************************************
2	amb	449	$Header: /home/amb/CVS/routino/src/superx.c,v 1.39 2010-07-12 17:59:42 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	326	This file Copyright 2008-2010 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	amb	449	#include "ways.h"
30
31	amb	110	#include "nodesx.h"
32			#include "segmentsx.h"
33			#include "waysx.h"
34			#include "superx.h"
35
36	amb	449	#include "files.h"
37			#include "results.h"
38	amb	110
39	amb	449
40	amb	257	/* Variables */
41
42	amb	289	/+ The command line '--slim' option. +/
43	amb	257	extern int option_slim;
44
45	amb	228	/* Local Functions */
46
47			static Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,Way *match,int iteration);
48
49
50	amb	110	/*++++++++++++++++++++++++++++++++++++++
51			Select the super-segments from the list of segments.
52
53			NodesX *nodesx The nodes.
54
55			SegmentsX *segmentsx The segments.
56
57			WaysX *waysx The ways.
58			++++++++++++++++++++++++++++++++++++++*/
59
60	amb	214	void ChooseSuperNodes(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx)
61	amb	110	{
62	amb	214	index_t i;
63	amb	229	int nnodes=0;
64	amb	110
65	amb	275	/* Check the start conditions */
66
67	amb	279	assert(segmentsx->firstnode); /* Must have firstnode filled in => segments are updated */
68	amb	213
69	amb	275	/* Print the start message */
70
71	amb	231	printf("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
72	amb	227	fflush(stdout);
73
74	amb	275	/* Map into memory */
75
76			if(!option_slim)
77			{
78	amb	257	segmentsx->xdata=MapFile(segmentsx->filename);
79	amb	275	waysx->xdata=MapFile(waysx->filename);
80			}
81	amb	257
82	amb	110	/* Find super-nodes */
83
84	amb	229	for(i=0;i<nodesx->number;i++)
85	amb	110	{
86	amb	434	int difference=0;
87			index_t index1,index2;
88	amb	110
89	amb	434	index1=IndexFirstSegmentX(segmentsx,i);
90	amb	229
91	amb	434	while(index1!=NO_SEGMENT)
92	amb	110	{
93	amb	434	SegmentX *segmentx1=LookupSegmentX(segmentsx,index1,1);
94	amb	279	WayX *wayx1=LookupWayX(waysx,segmentx1->way,1);
95	amb	110
96	amb	434	index1=IndexNextSegmentX(segmentsx,index1,i);
97			index2=index1;
98	amb	229
99	amb	434	while(index2!=NO_SEGMENT)
100	amb	110	{
101	amb	434	SegmentX *segmentx2=LookupSegmentX(segmentsx,index2,2);
102	amb	279	WayX *wayx2=LookupWayX(waysx,segmentx2->way,2);
103	amb	110
104	amb	434	/* If the ways are different in any way and there is a type of traffic that can use both ... */
105	amb	110
106	amb	434	if(WaysCompare(&wayx1->way,&wayx2->way))
107			if(wayx1->way.allow & wayx2->way.allow)
108			{
109			difference=1;
110			break;
111			}
112
113			index2=IndexNextSegmentX(segmentsx,index2,i);
114	amb	110	}
115
116	amb	434	if(difference)
117			break;
118			}
119	amb	110
120	amb	434	/* Store the node if there is a difference in the connected ways that could affect routing. */
121	amb	110
122	amb	434	if(difference)
123			{
124			nodesx->super[i]++;
125
126			nnodes++;
127	amb	110	}
128
129			if(!((i+1)%10000))
130			{
131	amb	231	printf("\rFinding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
132	amb	110	fflush(stdout);
133			}
134			}
135
136	amb	275	/* Unmap from memory */
137
138			if(!option_slim)
139			{
140			segmentsx->xdata=UnmapFile(segmentsx->filename);
141			waysx->xdata=UnmapFile(waysx->filename);
142			}
143
144			/* Print the final message */
145
146	amb	231	printf("\rFound Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
147	amb	110	fflush(stdout);
148			}
149
150
151			/*++++++++++++++++++++++++++++++++++++++
152			Create the super-segments.
153
154			SegmentsX *CreateSuperSegments Creates the super segments.
155
156			NodesX *nodesx The nodes.
157
158			SegmentsX *segmentsx The segments.
159
160			WaysX *waysx The ways.
161
162			int iteration The current super-node / super-segment iteration number.
163			++++++++++++++++++++++++++++++++++++++*/
164
165			SegmentsX CreateSuperSegments(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,int iteration)
166			{
167	amb	214	index_t i;
168	amb	110	SegmentsX *supersegmentsx;
169	amb	227	int sn=0,ss=0;
170	amb	110
171	amb	275	/* Check the start conditions */
172
173	amb	279	assert(segmentsx->firstnode); /* Must have firstnode filled in => segments are updated */
174	amb	213
175	amb	275	/* Print the start message */
176
177	amb	227	printf("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
178			fflush(stdout);
179
180	amb	275	/* Map into memory */
181
182			if(!option_slim)
183			{
184	amb	257	segmentsx->xdata=MapFile(segmentsx->filename);
185	amb	275	waysx->xdata=MapFile(waysx->filename);
186			}
187	amb	257
188	amb	275	/* Create super-segments for each super-node. */
189
190	amb	326	supersegmentsx=NewSegmentList(0);
191	amb	110
192			for(i=0;i<nodesx->number;i++)
193			{
194	amb	249	if(nodesx->super[i]>iteration)
195	amb	110	{
196	amb	275	index_t index,first;
197	amb	110
198	amb	279	index=first=IndexFirstSegmentX(segmentsx,i);
199	amb	110
200	amb	275	while(index!=NO_SEGMENT)
201	amb	110	{
202	amb	275	SegmentX *segmentx=LookupSegmentX(segmentsx,index,1);
203	amb	279	WayX *wayx=LookupWayX(waysx,segmentx->way,1);
204	amb	110
205			/* Check that this type of way hasn't already been routed */
206
207	amb	256	if(index!=first)
208	amb	110	{
209	amb	275	index_t otherindex=first;
210	amb	110
211	amb	275	while(otherindex!=NO_SEGMENT && otherindex!=index)
212	amb	110	{
213	amb	275	SegmentX *othersegmentx=LookupSegmentX(segmentsx,otherindex,2);
214	amb	279	WayX *otherwayx=LookupWayX(waysx,othersegmentx->way,2);
215	amb	110
216	amb	262	if(!WaysCompare(&otherwayx->way,&wayx->way))
217	amb	110	{
218	amb	204	wayx=NULL;
219	amb	110	break;
220			}
221
222	amb	279	otherindex=IndexNextSegmentX(segmentsx,otherindex,i);
223	amb	110	}
224			}
225
226			/* Route the way and store the super-segments. */
227
228	amb	204	if(wayx)
229	amb	110	{
230	amb	279	Results *results=FindRoutesWay(nodesx,segmentsx,waysx,i,&wayx->way,iteration);
231	amb	110	Result *result=FirstResult(results);
232
233			while(result)
234			{
235	amb	279	if(result->node!=i && nodesx->super[result->node]>iteration)
236	amb	110	{
237	amb	262	if(wayx->way.type&Way_OneWay)
238	amb	277	{
239	amb	279	AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)\|ONEWAY_1TO2);
240			AppendSegment(supersegmentsx,segmentx->way,result->node,i,DISTANCE((distance_t)result->score)\|ONEWAY_2TO1);
241	amb	277	}
242	amb	172	else
243	amb	279	AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));
244	amb	216
245	amb	229	ss++;
246	amb	110	}
247
248			result=NextResult(results,result);
249			}
250
251			FreeResultsList(results);
252			}
253
254	amb	279	index=IndexNextSegmentX(segmentsx,index,i);
255	amb	110	}
256	amb	227
257			sn++;
258	amb	110
259	amb	229	if(!(sn%10000))
260			{
261			printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
262			fflush(stdout);
263			}
264	amb	110	}
265			}
266
267	amb	275	/* Unmap from memory */
268
269			if(!option_slim)
270			{
271			segmentsx->xdata=UnmapFile(segmentsx->filename);
272			waysx->xdata=UnmapFile(waysx->filename);
273			}
274
275			/* Print the final message */
276
277	amb	227	printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",sn,ss);
278	amb	110	fflush(stdout);
279
280			return(supersegmentsx);
281			}
282
283
284			/*++++++++++++++++++++++++++++++++++++++
285	amb	256	Merge the segments and super-segments into a new segment list.
286	amb	110
287	amb	256	SegmentsX* MergeSuperSegments Returns a new set of merged segments.
288
289	amb	110	SegmentsX* segmentsx The set of segments to process.
290
291			SegmentsX* supersegmentsx The set of super-segments to merge.
292			++++++++++++++++++++++++++++++++++++++*/
293
294	amb	256	SegmentsX MergeSuperSegments(SegmentsX segmentsx,SegmentsX* supersegmentsx)
295	amb	110	{
296	amb	216	index_t i,j;
297			int m=0,a=0;
298	amb	256	SegmentsX* mergedsegmentsx;
299	amb	110
300	amb	275	/* Print the start message */
301
302	amb	227	printf("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0");
303			fflush(stdout);
304
305	amb	275	/* Map into memory */
306
307			if(!option_slim)
308			{
309			segmentsx->xdata=MapFile(segmentsx->filename);
310			supersegmentsx->xdata=MapFile(supersegmentsx->filename);
311			}
312
313			/* Loop through and create a new list of combined segments */
314
315	amb	326	mergedsegmentsx=NewSegmentList(0);
316	amb	256
317	amb	216	for(i=0,j=0;i<segmentsx->number;i++)
318	amb	110	{
319	amb	256	int super=0;
320	amb	275	SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
321	amb	256
322	amb	110	while(j<supersegmentsx->number)
323			{
324	amb	275	SegmentX *supersegmentx=LookupSegmentX(supersegmentsx,j,1);
325	amb	256
326			if(segmentx->node1 ==supersegmentx->node1 &&
327			segmentx->node2 ==supersegmentx->node2 &&
328			segmentx->distance==supersegmentx->distance)
329	amb	110	{
330	amb	257	m++;
331			j++;
332	amb	256	/* mark as super-segment and normal segment */
333			super=1;
334	amb	110	break;
335			}
336	amb	256	else if((segmentx->node1==supersegmentx->node1 &&
337			segmentx->node2==supersegmentx->node2) \|\|
338			(segmentx->node1==supersegmentx->node1 &&
339			segmentx->node2>supersegmentx->node2) \|\|
340			(segmentx->node1>supersegmentx->node1))
341	amb	110	{
342	amb	256	/* mark as super-segment */
343			AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance\|SEGMENT_SUPER);
344	amb	216	a++;
345			j++;
346	amb	110	}
347			else
348	amb	257	{
349			/* mark as normal segment */
350	amb	110	break;
351	amb	257	}
352	amb	110	}
353
354	amb	256	if(super)
355			AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance\|SEGMENT_SUPER\|SEGMENT_NORMAL);
356			else
357			AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance\|SEGMENT_NORMAL);
358	amb	208
359	amb	110	if(!((i+1)%10000))
360			{
361	amb	216	printf("\rMerging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
362	amb	110	fflush(stdout);
363			}
364			}
365
366	amb	275	/* Unmap from memory */
367
368			if(!option_slim)
369			{
370			segmentsx->xdata=UnmapFile(segmentsx->filename);
371			supersegmentsx->xdata=UnmapFile(supersegmentsx->filename);
372			}
373
374			/* Print the final message */
375
376	amb	216	printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
377	amb	110	fflush(stdout);
378	amb	256
379			return(mergedsegmentsx);
380	amb	110	}
381
382
383			/*++++++++++++++++++++++++++++++++++++++
384			Find all routes from a specified node to any node in the specified list that follows a certain type of way.
385
386			Results *FindRoutesWay Returns a set of results.
387
388			NodesX *nodesx The set of nodes to use.
389
390			SegmentsX *segmentsx The set of segments to use.
391
392			WaysX *waysx The set of ways to use.
393
394			node_t start The start node.
395
396	amb	203	Way *match The way that the route must match.
397	amb	110
398			int iteration The current super-node / super-segment iteration number.
399			++++++++++++++++++++++++++++++++++++++*/
400
401	amb	228	static Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,Way *match,int iteration)
402	amb	110	{
403			Results *results;
404	amb	236	Queue *queue;
405	amb	110	index_t node1,node2;
406			Result result1,result2;
407	amb	275	index_t index;
408	amb	204	WayX *wayx;
409	amb	110
410			/* Insert the first node into the queue */
411
412			results=NewResultsList(8);
413
414	amb	236	queue=NewQueueList();
415
416	amb	110	result1=InsertResult(results,start);
417
418	amb	166	ZeroResult(result1);
419	amb	110
420	amb	236	InsertInQueue(queue,result1);
421	amb	110
422			/* Loop across all nodes in the queue */
423
424	amb	236	while((result1=PopFromQueue(queue)))
425	amb	110	{
426			node1=result1->node;
427
428	amb	256	index=IndexFirstSegmentX(segmentsx,node1);
429	amb	110
430	amb	275	while(index!=NO_SEGMENT)
431	amb	110	{
432	amb	279	SegmentX segmentx=LookupSegmentX(segmentsx,index,2); / must use 2 here */
433	amb	113	distance_t cumulative_distance;
434
435	amb	275	if(segmentx->distance&ONEWAY_2TO1)
436			goto endloop;
437	amb	110
438	amb	275	node2=segmentx->node2;
439	amb	110
440	amb	113	if(result1->prev==node2)
441	amb	110	goto endloop;
442
443	amb	279	wayx=LookupWayX(waysx,segmentx->way,2);
444	amb	110
445	amb	262	if(WaysCompare(&wayx->way,match))
446	amb	110	goto endloop;
447
448	amb	256	cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
449	amb	110
450			result2=FindResult(results,node2);
451
452			if(!result2) /* New end node */
453			{
454			result2=InsertResult(results,node2);
455	amb	113	result2->prev=node1;
456	amb	176	result2->next=NO_NODE;
457	amb	172	result2->score=cumulative_distance;
458	amb	166	result2->sortby=cumulative_distance;
459	amb	110
460	amb	279	if(nodesx->super[node2]<=iteration)
461	amb	236	InsertInQueue(queue,result2);
462	amb	110	}
463	amb	172	else if(cumulative_distance<result2->score)
464	amb	110	{
465	amb	166	result2->prev=node1;
466	amb	172	result2->score=cumulative_distance;
467	amb	166	result2->sortby=cumulative_distance;
468	amb	110
469	amb	279	if(nodesx->super[node2]<=iteration)
470	amb	236	InsertInQueue(queue,result2);
471	amb	110	}
472
473			endloop:
474
475	amb	279	index=IndexNextSegmentX(segmentsx,index,node1);
476	amb	110	}
477			}
478
479	amb	236	FreeQueueList(queue);
480
481	amb	110	return(results);
482			}