trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.49 2010-12-21 14:54:27 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 <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;
    index_t index1,index2;

    index1=IndexFirstSegmentX2(segmentsx,i);

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

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

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

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

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

          /* If the ways are different in any attribute 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=IndexNextSegmentX2(segmentsx,index2,i);
         }

       if(difference)
          break;
      }

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

    if(difference || nodex->flags&NODE_TURNRSTRCT)
      {
       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
 CloseFile(nodesx->fd);
 CloseFile(segmentsx->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)
      {
       index_t index,first;

       index=first=IndexFirstSegmentX2(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=IndexNextSegmentX2(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=IndexNextSegmentX2(segmentsx,index,i);
         }

       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
 CloseFile(segmentsx->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=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=%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
 CloseFile(segmentsx->fd);
 if(supersegmentsx->number>0)
    CloseFile(supersegmentsx->fd);
#endif

 /* Print the final message */

 printf_last("Merged: 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;
 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=IndexFirstSegmentX2(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=IndexNextSegmentX2(segmentsx,index,node1);
      }
   }

 FreeQueueList(queue);

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