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