trunk/src/superx.c

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

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2012 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 "logging.h"
#include "results.h"


/* Local functions */

static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match);


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

  NodesX *nodesx The set of nodes to use.

  SegmentsX *segmentsx The set of segments to use.

  WaysX *waysx The set of ways to use.
  ++++++++++++++++++++++++++++++++++++++*/

void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
{
 index_t i;
 index_t 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");

 /* Allocate and set the super-node markers */

 if(!nodesx->super)
   {
    nodesx->super=(uint8_t*)malloc((1+nodesx->number/8)*sizeof(uint8_t));

    assert(nodesx->super); /* Check calloc() worked */

    memset(nodesx->super,~0,(1+nodesx->number/8));
   }

 /* Map into memory / open the files */

#if !SLIM
 nodesx->data=MapFile(nodesx->filename);
 segmentsx->data=MapFile(segmentsx->filename);
 waysx->data=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++)
   {
    if(IsBitSet(nodesx->super,i))
      {
       int issuper=0;
       NodeX *nodex=LookupNodeX(nodesx,i,1);

       if(nodex->flags&(NODE_TURNRSTRCT|NODE_TURNRSTRCT2))
          issuper=1;
       else
         {
          int count=0,j;
          Way segmentway[MAX_SEG_PER_NODE];
          int segmentweight[MAX_SEG_PER_NODE];
          SegmentX *segmentx=FirstSegmentX(segmentsx,i,1);

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

             /* Segments that are loops count twice */

             assert(count<MAX_SEG_PER_NODE); /* Only a limited amount of information stored. */

             if(segmentx->node1==segmentx->node2)
                segmentweight[count]=2;
             else
                segmentweight[count]=1;

             segmentway[count]=wayx->way;

             /* If the node allows less traffic types than any connecting way then it is super */

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

             nsegments=segmentweight[count];

             for(j=0;j<count;j++)
                if(wayx->way.allow & segmentway[j].allow)
                  {
                   /* If two ways are different in any attribute and there is a type of traffic that can use both then it is super */

                   if(WaysCompare(&segmentway[j],&wayx->way))
                     {
                      issuper=1;
                      break;
                     }

                   /* If there are two other segments that can be used by the same types of traffic as this one then it is super */

                   nsegments+=segmentweight[j];
                   if(nsegments>2)
                     {
                      issuper=1;
                      break;
                     }
                  }

             if(issuper)
                break;

             segmentx=NextSegmentX(segmentsx,segmentx,i);

             count++;
            }
         }

       /* Mark the node as super if it is. */

       if(issuper)
          nnodes++;
       else
          ClearBit(nodesx->super,i);
      }

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

 /* Unmap from memory / close the files */

#if !SLIM
 nodesx->data=UnmapFile(nodesx->filename);
 segmentsx->data=UnmapFile(segmentsx->filename);
 waysx->data=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=%"Pindex_t" Super-Nodes=%"Pindex_t,nodesx->number,nnodes);
}


/*++++++++++++++++++++++++++++++++++++++
  Create the super-segments from the existing segments.

  SegmentsX *CreateSuperSegments Returns the new super segments.

  NodesX *nodesx The set of nodes to use.

  SegmentsX *segmentsx The set of segments to use.

  WaysX *waysx The set of ways to use.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentsX *CreateSuperSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
{
 index_t i;
 SegmentsX *supersegmentsx;
 index_t 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->data=MapFile(segmentsx->filename);
 waysx->data=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(IsBitSet(nodesx->super,i))
      {
       SegmentX *segmentx;
       int count=0,match;
       Way prevway[MAX_SEG_PER_NODE];

       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(count>0)
            {
             int j;

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

          assert(count<MAX_SEG_PER_NODE); /* Only a limited amount of history stored. */

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

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

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

             while(result)
               {
                if(IsBitSet(nodesx->super,result->node) && 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);
         }

       sn++;

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

 /* Unmap from memory / close the files */

#if !SLIM
 segmentsx->data=UnmapFile(segmentsx->filename);
 waysx->data=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=%"Pindex_t" Super-Segments=%"Pindex_t,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 use.

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

SegmentsX *MergeSuperSegments(SegmentsX *segmentsx,SegmentsX *supersegmentsx)
{
 index_t i,j;
 index_t merged=0,added=0;
 SegmentsX *mergedsegmentsx;

 mergedsegmentsx=NewSegmentList(0);

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

 /* Print the start message */

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

 /* Map into memory / open the files */

#if !SLIM
 segmentsx->data=MapFile(segmentsx->filename);
 if(supersegmentsx->number>0)
    supersegmentsx->data=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)
         {
          merged++;
          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);
          added++;
          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=%"Pindex_t" Super=%"Pindex_t" Merged=%"Pindex_t" Added=%"Pindex_t,i+1,j,merged,added);
   }

 /* Unmap from memory / close the files */

#if !SLIM
 segmentsx->data=UnmapFile(segmentsx->filename);
 if(supersegmentsx->number>0)
    supersegmentsx->data=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=%"Pindex_t" Super=%"Pindex_t" Merged=%"Pindex_t" Added=%"Pindex_t,segmentsx->number,supersegmentsx->number,merged,added);

 return(mergedsegmentsx);
}


/*++++++++++++++++++++++++++++++++++++++
  Find all routes from a specified super-node to any other super-node 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 A template for the type of way that the route must follow.
  ++++++++++++++++++++++++++++++++++++++*/

static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match)
{
 Results *results;
 Queue *queue;
 Result *result1,*result2;
 WayX *wayx;

 /* Insert the first node into the queue */

 results=NewResultsList(4);

 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;
    SegmentX *segmentx;

    node1=result1->node;

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

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

       /* must not be one-way against the direction of travel */
       if(IsOnewayTo(segmentx,node1))
          goto endloop;

       node2=OtherNode(segmentx,node1);

       seg2=IndexSegmentX(segmentsx,segmentx);

       /* must not be a u-turn */
       if(result1->segment==seg2)
          goto endloop;

       wayx=LookupWayX(waysx,segmentx->way,2); /* position 1 is already used */

       /* must be the right type of way */
       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;

          /* don't route beyond a super-node. */
          if(!IsBitSet(nodesx->super,node2))
             InsertInQueue(queue,result2);
         }
       else if(cumulative_distance<result2->score)
         {
          result2->prev=result1;
          result2->score=cumulative_distance;
          result2->sortby=cumulative_distance;

          /* don't route beyond a super-node. */
          if(!IsBitSet(nodesx->super,node2))
             InsertInQueue(queue,result2);
         }

      endloop:

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

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