trunk/src/superx.c

/***************************************
 Super-Segment data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2011 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 <stdlib.h>
#include <stdio.h>

#include "ways.h"

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

#include "files.h"
#include "logging.h"
#include "results.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;

 if(nodesx->number==0 || segmentsx->number==0 || waysx->number==0)
    return;

 /* Print the start message */

 printf_first("Finding Super-Nodes: Nodes=0 Super-Nodes=0");

 /* Map into memory / open the files */

#if !SLIM
 nodesx->xdata=MapFile(nodesx->filename);
 segmentsx->xdata=MapFile(segmentsx->filename);
 waysx->xdata=MapFile(waysx->filename);
#else
 nodesx->fd=ReOpenFile(nodesx->filename);
 segmentsx->fd=ReOpenFile(segmentsx->filename);
 waysx->fd=ReOpenFile(waysx->filename);
#endif

 /* Find super-nodes */

 for(i=0;i<nodesx->number;i++)
   {
    NodeX *nodex=LookupNodeX(nodesx,i,1);
    int difference=0,nsegments=0;
    SegmentX *segmentx=NULL;
    int waycount=0;
    Way prevway[16];

    segmentx=FirstSegmentX(segmentsx,i,1);

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

       nsegments++;
       if(segmentx->node1==segmentx->node2)
          nsegments+=1;         /* The segment is stored once but goes both ways */

       /* If the node allows less traffic types than any connecting way ... */

       if((wayx->way.allow&nodex->allow)!=wayx->way.allow)
         {
          difference=1;
          break;
         }

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

       if(waycount>0)
         {
          int j;

          for(j=0;j<waycount;j++)
             if(WaysCompare(&prevway[j],&wayx->way))
                if(wayx->way.allow & prevway[j].allow)
                  {
                   difference=1;
                   break;
                  }
         }

       assert(waycount<(sizeof(prevway)/sizeof(prevway[0])));

       prevway[waycount++]=wayx->way;

       if(difference)
          break;

       segmentx=NextSegmentX(segmentsx,segmentx,i,1);
      }

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

    if(difference || nsegments>2 || nodex->flags&(NODE_TURNRSTRCT|NODE_TURNRSTRCT2))
      {
       nodesx->super[i]++;

       nnodes++;
      }

    if(!((i+1)%10000))
       printf_middle("Finding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
   }

 /* Unmap from memory / close the files */

#if !SLIM
 nodesx->xdata=UnmapFile(nodesx->filename);
 segmentsx->xdata=UnmapFile(segmentsx->filename);
 waysx->xdata=UnmapFile(waysx->filename);
#else
 nodesx->fd=CloseFile(nodesx->fd);
 segmentsx->fd=CloseFile(segmentsx->fd);
 waysx->fd=CloseFile(waysx->fd);
#endif

 /* Print the final message */

 printf_last("Found Super-Nodes: Nodes=%d Super-Nodes=%d",nodesx->number,nnodes);
}


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

 supersegmentsx=NewSegmentList(0);

 if(segmentsx->number==0 || waysx->number==0)
    return(supersegmentsx);

 /* Print the start message */

 printf_first("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");

 /* Map into memory / open the files */

#if !SLIM
 segmentsx->xdata=MapFile(segmentsx->filename);
 waysx->xdata=MapFile(waysx->filename);
#else
 segmentsx->fd=ReOpenFile(segmentsx->filename);
 waysx->fd=ReOpenFile(waysx->filename);
#endif

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

 for(i=0;i<nodesx->number;i++)
   {
    if(nodesx->super[i]>iteration)
      {
       SegmentX *segmentx;
       int waycount=0,match;
       Way prevway[16];

       segmentx=FirstSegmentX(segmentsx,i,1);

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

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

          match=0;

          if(waycount>0)
            {
             int j;

             for(j=0;j<waycount;j++)
                if(!WaysCompare(&prevway[j],&wayx->way))
                  {
                   match=1;
                   break;
                  }
            }

          assert(waycount<(sizeof(prevway)/sizeof(prevway[0])));

          prevway[waycount++]=wayx->way;

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

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

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

                   ss++;
                  }

                result=NextResult(results,result);
               }

             FreeResultsList(results);
            }

          segmentx=NextSegmentX(segmentsx,segmentx,i,1);
         }

       sn++;

       if(!(sn%10000))
          printf_middle("Creating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
      }
   }

 /* Unmap from memory / close the files */

#if !SLIM
 segmentsx->xdata=UnmapFile(segmentsx->filename);
 waysx->xdata=UnmapFile(waysx->filename);
#else
 segmentsx->fd=CloseFile(segmentsx->fd);
 waysx->fd=CloseFile(waysx->fd);
#endif

 /* Print the final message */

 printf_last("Created Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);

 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;

 mergedsegmentsx=NewSegmentList(0);

 if(segmentsx->number==0)
    return(mergedsegmentsx);

 /* Print the start message */

 printf_first("Merging Segments: Segments=0 Super-Segments=0 Merged=0 Added=0");

 /* Map into memory / open the files */

#if !SLIM
 segmentsx->xdata=MapFile(segmentsx->filename);
 if(supersegmentsx->number>0)
    supersegmentsx->xdata=MapFile(supersegmentsx->filename);
#else
 segmentsx->fd=ReOpenFile(segmentsx->filename);
 if(supersegmentsx->number>0)
    supersegmentsx->fd=ReOpenFile(supersegmentsx->filename);
#endif

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

 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_middle("Merging Segments: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
   }

 /* Unmap from memory / close the files */

#if !SLIM
 segmentsx->xdata=UnmapFile(segmentsx->filename);
 if(supersegmentsx->number>0)
    supersegmentsx->xdata=UnmapFile(supersegmentsx->filename);
#else
 segmentsx->fd=CloseFile(segmentsx->fd);
 if(supersegmentsx->number>0)
    supersegmentsx->fd=CloseFile(supersegmentsx->fd);
#endif

 /* Print the final message */

 printf_last("Merged Segments: Segments=%d Super-Segments=%d Merged=%d Added=%d",segmentsx->number,supersegmentsx->number,m,a);

 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;
 Result *result1,*result2;
 WayX *wayx;

 /* Insert the first node into the queue */

 results=NewResultsList(8);

 queue=NewQueueList();

 result1=InsertResult(results,start,NO_SEGMENT);

 InsertInQueue(queue,result1);

 /* Loop across all nodes in the queue */

 while((result1=PopFromQueue(queue)))
   {
    index_t node1,seg1;
    SegmentX *segmentx;

    node1=result1->node;
    seg1=result1->segment;

    segmentx=FirstSegmentX(segmentsx,node1,2); /* position 1 is already used */

    while(segmentx)
      {
       index_t node2,seg2;
       distance_t cumulative_distance;

       if(IsOnewayTo(segmentx,node1))
          goto endloop;

       node2=OtherNode(segmentx,node1);

       seg2=IndexSegmentX(segmentsx,segmentx);

       if(result1->prev && result1->prev->node==node2 && node1!=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,seg2);

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

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

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

      endloop:

       segmentx=NextSegmentX(segmentsx,segmentx,node1,2);
      }
   }

 FreeQueueList(queue);

 return(results);
}
1	/***************************************
2	Super-Segment data type functions.
3
4	Part of the Routino routing software.
5	****************/ /****************
6	This file Copyright 2008-2011 Andrew M. Bishop
7
8	This program is free software: you can redistribute it and/or modify
9	it under the terms of the GNU Affero General Public License as published by
10	the Free Software Foundation, either version 3 of the License, or
11	(at your option) any later version.
12
13	This program is distributed in the hope that it will be useful,
14	but WITHOUT ANY WARRANTY; without even the implied warranty of
15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16	GNU Affero General Public License for more details.
17
18	You should have received a copy of the GNU Affero General Public License
19	along with this program. If not, see <http://www.gnu.org/licenses/>.
20	***************************************/
21
22
23	#include <stdlib.h>
24	#include <stdio.h>
25
26	#include "ways.h"
27
28	#include "nodesx.h"
29	#include "segmentsx.h"
30	#include "waysx.h"
31	#include "superx.h"
32
33	#include "files.h"
34	#include "logging.h"
35	#include "results.h"
36
37
38	/* Local Functions */
39
40	static Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,Way *match,int iteration);
41
42
43	/*++++++++++++++++++++++++++++++++++++++
44	Select the super-segments from the list of segments.
45
46	NodesX *nodesx The nodes.
47
48	SegmentsX *segmentsx The segments.
49
50	WaysX *waysx The ways.
51	++++++++++++++++++++++++++++++++++++++*/
52
53	void ChooseSuperNodes(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx)
54	{
55	index_t i;
56	int nnodes=0;
57
58	if(nodesx->number==0 \|\| segmentsx->number==0 \|\| waysx->number==0)
59	return;
60
61	/* Print the start message */
62
63	printf_first("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
64
65	/* Map into memory / open the files */
66
67	#if !SLIM
68	nodesx->xdata=MapFile(nodesx->filename);
69	segmentsx->xdata=MapFile(segmentsx->filename);
70	waysx->xdata=MapFile(waysx->filename);
71	#else
72	nodesx->fd=ReOpenFile(nodesx->filename);
73	segmentsx->fd=ReOpenFile(segmentsx->filename);
74	waysx->fd=ReOpenFile(waysx->filename);
75	#endif
76
77	/* Find super-nodes */
78
79	for(i=0;i<nodesx->number;i++)
80	{
81	NodeX *nodex=LookupNodeX(nodesx,i,1);
82	int difference=0,nsegments=0;
83	SegmentX *segmentx=NULL;
84	int waycount=0;
85	Way prevway[16];
86
87	segmentx=FirstSegmentX(segmentsx,i,1);
88
89	while(segmentx)
90	{
91	WayX *wayx=LookupWayX(waysx,segmentx->way,1);
92
93	nsegments++;
94	if(segmentx->node1==segmentx->node2)
95	nsegments+=1; /* The segment is stored once but goes both ways */
96
97	/* If the node allows less traffic types than any connecting way ... */
98
99	if((wayx->way.allow&nodex->allow)!=wayx->way.allow)
100	{
101	difference=1;
102	break;
103	}
104
105	/* If the ways are different in any attribute and there is a type of traffic that can use both ... */
106
107	if(waycount>0)
108	{
109	int j;
110
111	for(j=0;j<waycount;j++)
112	if(WaysCompare(&prevway[j],&wayx->way))
113	if(wayx->way.allow & prevway[j].allow)
114	{
115	difference=1;
116	break;
117	}
118	}
119
120	assert(waycount<(sizeof(prevway)/sizeof(prevway[0])));
121
122	prevway[waycount++]=wayx->way;
123
124	if(difference)
125	break;
126
127	segmentx=NextSegmentX(segmentsx,segmentx,i,1);
128	}
129
130	/* Store the node if there is a difference in the connected ways that could affect routing. */
131
132	if(difference \|\| nsegments>2 \|\| nodex->flags&(NODE_TURNRSTRCT\|NODE_TURNRSTRCT2))
133	{
134	nodesx->super[i]++;
135
136	nnodes++;
137	}
138
139	if(!((i+1)%10000))
140	printf_middle("Finding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
141	}
142
143	/* Unmap from memory / close the files */
144
145	#if !SLIM
146	nodesx->xdata=UnmapFile(nodesx->filename);
147	segmentsx->xdata=UnmapFile(segmentsx->filename);
148	waysx->xdata=UnmapFile(waysx->filename);
149	#else
150	nodesx->fd=CloseFile(nodesx->fd);
151	segmentsx->fd=CloseFile(segmentsx->fd);
152	waysx->fd=CloseFile(waysx->fd);
153	#endif
154
155	/* Print the final message */
156
157	printf_last("Found Super-Nodes: Nodes=%d Super-Nodes=%d",nodesx->number,nnodes);
158	}
159
160
161	/*++++++++++++++++++++++++++++++++++++++
162	Create the super-segments.
163
164	SegmentsX *CreateSuperSegments Creates the super segments.
165
166	NodesX *nodesx The nodes.
167
168	SegmentsX *segmentsx The segments.
169
170	WaysX *waysx The ways.
171
172	int iteration The current super-node / super-segment iteration number.
173	++++++++++++++++++++++++++++++++++++++*/
174
175	SegmentsX CreateSuperSegments(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,int iteration)
176	{
177	index_t i;
178	SegmentsX *supersegmentsx;
179	int sn=0,ss=0;
180
181	supersegmentsx=NewSegmentList(0);
182
183	if(segmentsx->number==0 \|\| waysx->number==0)
184	return(supersegmentsx);
185
186	/* Print the start message */
187
188	printf_first("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
189
190	/* Map into memory / open the files */
191
192	#if !SLIM
193	segmentsx->xdata=MapFile(segmentsx->filename);
194	waysx->xdata=MapFile(waysx->filename);
195	#else
196	segmentsx->fd=ReOpenFile(segmentsx->filename);
197	waysx->fd=ReOpenFile(waysx->filename);
198	#endif
199
200	/* Create super-segments for each super-node. */
201
202	for(i=0;i<nodesx->number;i++)
203	{
204	if(nodesx->super[i]>iteration)
205	{
206	SegmentX *segmentx;
207	int waycount=0,match;
208	Way prevway[16];
209
210	segmentx=FirstSegmentX(segmentsx,i,1);
211
212	while(segmentx)
213	{
214	WayX *wayx=LookupWayX(waysx,segmentx->way,1);
215
216	/* Check that this type of way hasn't already been routed */
217
218	match=0;
219
220	if(waycount>0)
221	{
222	int j;
223
224	for(j=0;j<waycount;j++)
225	if(!WaysCompare(&prevway[j],&wayx->way))
226	{
227	match=1;
228	break;
229	}
230	}
231
232	assert(waycount<(sizeof(prevway)/sizeof(prevway[0])));
233
234	prevway[waycount++]=wayx->way;
235
236	/* Route the way and store the super-segments. */
237
238	if(!match)
239	{
240	Results *results=FindRoutesWay(nodesx,segmentsx,waysx,i,&wayx->way,iteration);
241	Result *result=FirstResult(results);
242
243	while(result)
244	{
245	if(nodesx->super[result->node]>iteration && result->segment!=NO_SEGMENT)
246	{
247	if(wayx->way.type&Way_OneWay && result->node!=i)
248	AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)\|ONEWAY_1TO2);
249	else
250	AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));
251
252	ss++;
253	}
254
255	result=NextResult(results,result);
256	}
257
258	FreeResultsList(results);
259	}
260
261	segmentx=NextSegmentX(segmentsx,segmentx,i,1);
262	}
263
264	sn++;
265
266	if(!(sn%10000))
267	printf_middle("Creating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
268	}
269	}
270
271	/* Unmap from memory / close the files */
272
273	#if !SLIM
274	segmentsx->xdata=UnmapFile(segmentsx->filename);
275	waysx->xdata=UnmapFile(waysx->filename);
276	#else
277	segmentsx->fd=CloseFile(segmentsx->fd);
278	waysx->fd=CloseFile(waysx->fd);
279	#endif
280
281	/* Print the final message */
282
283	printf_last("Created Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
284
285	return(supersegmentsx);
286	}
287
288
289	/*++++++++++++++++++++++++++++++++++++++
290	Merge the segments and super-segments into a new segment list.
291
292	SegmentsX* MergeSuperSegments Returns a new set of merged segments.
293
294	SegmentsX* segmentsx The set of segments to process.
295
296	SegmentsX* supersegmentsx The set of super-segments to merge.
297	++++++++++++++++++++++++++++++++++++++*/
298
299	SegmentsX MergeSuperSegments(SegmentsX segmentsx,SegmentsX* supersegmentsx)
300	{
301	index_t i,j;
302	int m=0,a=0;
303	SegmentsX* mergedsegmentsx;
304
305	mergedsegmentsx=NewSegmentList(0);
306
307	if(segmentsx->number==0)
308	return(mergedsegmentsx);
309
310	/* Print the start message */
311
312	printf_first("Merging Segments: Segments=0 Super-Segments=0 Merged=0 Added=0");
313
314	/* Map into memory / open the files */
315
316	#if !SLIM
317	segmentsx->xdata=MapFile(segmentsx->filename);
318	if(supersegmentsx->number>0)
319	supersegmentsx->xdata=MapFile(supersegmentsx->filename);
320	#else
321	segmentsx->fd=ReOpenFile(segmentsx->filename);
322	if(supersegmentsx->number>0)
323	supersegmentsx->fd=ReOpenFile(supersegmentsx->filename);
324	#endif
325
326	/* Loop through and create a new list of combined segments */
327
328	for(i=0,j=0;i<segmentsx->number;i++)
329	{
330	int super=0;
331	SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
332
333	while(j<supersegmentsx->number)
334	{
335	SegmentX *supersegmentx=LookupSegmentX(supersegmentsx,j,1);
336
337	if(segmentx->node1 ==supersegmentx->node1 &&
338	segmentx->node2 ==supersegmentx->node2 &&
339	segmentx->distance==supersegmentx->distance)
340	{
341	m++;
342	j++;
343	/* mark as super-segment and normal segment */
344	super=1;
345	break;
346	}
347	else if((segmentx->node1==supersegmentx->node1 &&
348	segmentx->node2==supersegmentx->node2) \|\|
349	(segmentx->node1==supersegmentx->node1 &&
350	segmentx->node2>supersegmentx->node2) \|\|
351	(segmentx->node1>supersegmentx->node1))
352	{
353	/* mark as super-segment */
354	AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance\|SEGMENT_SUPER);
355	a++;
356	j++;
357	}
358	else
359	{
360	/* mark as normal segment */
361	break;
362	}
363	}
364
365	if(super)
366	AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance\|SEGMENT_SUPER\|SEGMENT_NORMAL);
367	else
368	AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance\|SEGMENT_NORMAL);
369
370	if(!((i+1)%10000))
371	printf_middle("Merging Segments: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
372	}
373
374	/* Unmap from memory / close the files */
375
376	#if !SLIM
377	segmentsx->xdata=UnmapFile(segmentsx->filename);
378	if(supersegmentsx->number>0)
379	supersegmentsx->xdata=UnmapFile(supersegmentsx->filename);
380	#else
381	segmentsx->fd=CloseFile(segmentsx->fd);
382	if(supersegmentsx->number>0)
383	supersegmentsx->fd=CloseFile(supersegmentsx->fd);
384	#endif
385
386	/* Print the final message */
387
388	printf_last("Merged Segments: Segments=%d Super-Segments=%d Merged=%d Added=%d",segmentsx->number,supersegmentsx->number,m,a);
389
390	return(mergedsegmentsx);
391	}
392
393
394	/*++++++++++++++++++++++++++++++++++++++
395	Find all routes from a specified node to any node in the specified list that follows a certain type of way.
396
397	Results *FindRoutesWay Returns a set of results.
398
399	NodesX *nodesx The set of nodes to use.
400
401	SegmentsX *segmentsx The set of segments to use.
402
403	WaysX *waysx The set of ways to use.
404
405	node_t start The start node.
406
407	Way *match The way that the route must match.
408
409	int iteration The current super-node / super-segment iteration number.
410	++++++++++++++++++++++++++++++++++++++*/
411
412	static Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,Way *match,int iteration)
413	{
414	Results *results;
415	Queue *queue;
416	Result result1,result2;
417	WayX *wayx;
418
419	/* Insert the first node into the queue */
420
421	results=NewResultsList(8);
422
423	queue=NewQueueList();
424
425	result1=InsertResult(results,start,NO_SEGMENT);
426
427	InsertInQueue(queue,result1);
428
429	/* Loop across all nodes in the queue */
430
431	while((result1=PopFromQueue(queue)))
432	{
433	index_t node1,seg1;
434	SegmentX *segmentx;
435
436	node1=result1->node;
437	seg1=result1->segment;
438
439	segmentx=FirstSegmentX(segmentsx,node1,2); /* position 1 is already used */
440
441	while(segmentx)
442	{
443	index_t node2,seg2;
444	distance_t cumulative_distance;
445
446	if(IsOnewayTo(segmentx,node1))
447	goto endloop;
448
449	node2=OtherNode(segmentx,node1);
450
451	seg2=IndexSegmentX(segmentsx,segmentx);
452
453	if(result1->prev && result1->prev->node==node2 && node1!=node2)
454	goto endloop;
455
456	wayx=LookupWayX(waysx,segmentx->way,2);
457
458	if(WaysCompare(&wayx->way,match))
459	goto endloop;
460
461	cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
462
463	result2=FindResult(results,node2,seg2);
464
465	if(!result2) /* New end node */
466	{
467	result2=InsertResult(results,node2,seg2);
468	result2->prev=result1;
469	result2->score=cumulative_distance;
470	result2->sortby=cumulative_distance;
471
472	if(nodesx->super[node2]<=iteration)
473	InsertInQueue(queue,result2);
474	}
475	else if(cumulative_distance<result2->score)
476	{
477	result2->prev=result1;
478	result2->score=cumulative_distance;
479	result2->sortby=cumulative_distance;
480
481	if(nodesx->super[node2]<=iteration)
482	InsertInQueue(queue,result2);
483	}
484
485	endloop:
486
487	segmentx=NextSegmentX(segmentsx,segmentx,node1,2);
488	}
489	}
490
491	FreeQueueList(queue);
492
493	return(results);
494	}