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 "types.h"
#include "segments.h"
#include "ways.h"

#include "typesx.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 */

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

 /* Map into memory / open the files */

#if !SLIM
 nodesx->data=MapFile(nodesx->filename_tmp);
 segmentsx->data=MapFile(segmentsx->filename_tmp);
 waysx->data=MapFile(waysx->filename_tmp);
#else
 nodesx->fd=ReOpenFile(nodesx->filename_tmp);
 segmentsx->fd=ReOpenFile(segmentsx->filename_tmp);
 waysx->fd=ReOpenFile(waysx->filename_tmp);
#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 it allows anything */

             if((wayx->way.allow&nodex->allow)!=wayx->way.allow && nodex->allow!=Transports_None)
               {
                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->data);
 segmentsx->data=UnmapFile(segmentsx->data);
 waysx->data=UnmapFile(waysx->data);
#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,0);

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

    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
 nodesx->data=MapFile(nodesx->filename_tmp);
 segmentsx->data=MapFile(segmentsx->filename_tmp);
 waysx->data=MapFile(waysx->filename_tmp);
#else
 nodesx->fd=ReOpenFile(nodesx->filename_tmp);
 segmentsx->fd=ReOpenFile(segmentsx->filename_tmp);
 waysx->fd=ReOpenFile(waysx->filename_tmp);
#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
 nodesx->data=UnmapFile(nodesx->data);
 segmentsx->data=UnmapFile(segmentsx->data);
 waysx->data=UnmapFile(waysx->data);
#else
 nodesx->fd=CloseFile(nodesx->fd);
 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);

 FinishSegmentList(supersegmentsx);

 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,0);

 if(segmentsx->number==0)
   {
    FinishSegmentList(mergedsegmentsx);

    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_tmp);
 if(supersegmentsx->number>0)
    supersegmentsx->data=MapFile(supersegmentsx->filename_tmp);
#else
 segmentsx->fd=ReOpenFile(segmentsx->filename_tmp);
 if(supersegmentsx->number>0)
    supersegmentsx->fd=ReOpenFile(supersegmentsx->filename_tmp);
#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->data);
 if(supersegmentsx->number>0)
    supersegmentsx->data=UnmapFile(supersegmentsx->data);
#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);

 FinishSegmentList(mergedsegmentsx);

 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(64);

 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)
      {
       NodeX  *node2x;
       index_t node2,seg2;
       distance_t cumulative_distance;

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

       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;

       node2=OtherNode(segmentx,node1);

       node2x=LookupNodeX(nodesx,node2,2); /* position 1 is already used */

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