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=AllocBitMask(nodesx->number);

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

    SetAllBits1(nodesx->super,nodesx->number);
   }

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