destination-access/src/superx.c

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

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2015 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 "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 *FindSuperRoutes(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);
    log_malloc(nodesx->super,LengthBitMask(nodesx->number)*sizeof(BitMask));

    logassert(nodesx->super,"Failed to allocate memory (try using slim mode?)"); /* Check AllocBitMask() worked */

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

 /* Map into memory / open the files */

 nodesx->fd=ReOpenFileBuffered(nodesx->filename_tmp);

#if !SLIM
 segmentsx->data=MapFile(segmentsx->filename_tmp);
 waysx->data=MapFile(waysx->filename_tmp);
#else
 segmentsx->fd=SlimMapFile(segmentsx->filename_tmp);
 waysx->fd=SlimMapFile(waysx->filename_tmp);

 InvalidateSegmentXCache(segmentsx->cache);
 InvalidateWayXCache(waysx->cache);
#endif

 /* Find super-nodes */

 for(i=0;i<nodesx->number;i++)
   {
    NodeX nodex;

    ReadFileBuffered(nodesx->fd,&nodex,sizeof(NodeX));

    if(IsBitSet(nodesx->super,i))
      {
       int issuper=0;

       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 */

             logassert(count<MAX_SEG_PER_NODE,"Too many segments for one node (increase 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
 segmentsx->data=UnmapFile(segmentsx->data);
 waysx->data=UnmapFile(waysx->data);
#else
 segmentsx->fd=SlimUnmapFile(segmentsx->fd);
 waysx->fd=SlimUnmapFile(waysx->fd);
#endif

 nodesx->fd=CloseFileBuffered(nodesx->fd);

 /* 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();

 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=SlimMapFile(nodesx->filename_tmp);
 segmentsx->fd=SlimMapFile(segmentsx->filename_tmp);
 waysx->fd=SlimMapFile(waysx->filename_tmp);

 InvalidateNodeXCache(nodesx->cache);
 InvalidateSegmentXCache(segmentsx->cache);
 InvalidateWayXCache(waysx->cache);
#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;
                  }
            }

          logassert(count<MAX_SEG_PER_NODE,"Too many segments for one node (increase 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=FindSuperRoutes(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&Highway_OneWay && result->node!=i)
                      AppendSegmentList(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2);
                   else
                      AppendSegmentList(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));

                   ss++;
                  }

                result=NextResult(results,result);
               }
            }

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

       sn++;

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

 FinishSegmentList(supersegmentsx);

 /* 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=SlimUnmapFile(nodesx->fd);
 segmentsx->fd=SlimUnmapFile(segmentsx->fd);
 waysx->fd=SlimUnmapFile(waysx->fd);
#endif

 /* Free the no-longer required memory */

 if(segmentsx->firstnode)
   {
    log_free(segmentsx->firstnode);
    free(segmentsx->firstnode);
    segmentsx->firstnode=NULL;
   }

 /* 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,lastj;
 index_t merged=0,added=0;
 SegmentsX *mergedsegmentsx;
 SegmentX supersegmentx;

 mergedsegmentsx=NewSegmentList();

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

    return(mergedsegmentsx);
   }

 /* Print the start message */

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

 /* Open the files */

 segmentsx->fd=ReOpenFileBuffered(segmentsx->filename_tmp);
 if(supersegmentsx->number>0)
    supersegmentsx->fd=ReOpenFileBuffered(supersegmentsx->filename_tmp);

 /* Loop through and create a new list of combined segments */

 lastj=-1;
 j=0;

 for(i=0;i<segmentsx->number;i++)
   {
    int super=0;
    SegmentX segmentx;

    ReadFileBuffered(segmentsx->fd,&segmentx,sizeof(SegmentX));

    while(j<supersegmentsx->number)
      {
       if(j!=lastj)
         {
          ReadFileBuffered(supersegmentsx->fd,&supersegmentx,sizeof(SegmentX));
          lastj=j;
         }

       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 */
          AppendSegmentList(mergedsegmentsx,supersegmentx.way,supersegmentx.node1,supersegmentx.node2,supersegmentx.distance|SEGMENT_SUPER);
          added++;
          j++;
         }
       else
         {
          /* mark as normal segment */
          break;
         }
      }

    if(super)
       AppendSegmentList(mergedsegmentsx,segmentx.way,segmentx.node1,segmentx.node2,segmentx.distance|SEGMENT_SUPER|SEGMENT_NORMAL);
    else
       AppendSegmentList(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);
   }

 if(j<supersegmentsx->number)
   {
    if(j==lastj)
      {
       AppendSegmentList(mergedsegmentsx,supersegmentx.way,supersegmentx.node1,supersegmentx.node2,supersegmentx.distance|SEGMENT_SUPER);

       j++;
      }

    while(j<supersegmentsx->number)
      {
       ReadFileBuffered(supersegmentsx->fd,&supersegmentx,sizeof(SegmentX));

       AppendSegmentList(mergedsegmentsx,supersegmentx.way,supersegmentx.node1,supersegmentx.node2,supersegmentx.distance|SEGMENT_SUPER);

       added++;
       j++;
      }
   }

 FinishSegmentList(mergedsegmentsx);

 /* Close the files */

 segmentsx->fd=CloseFileBuffered(segmentsx->fd);
 if(supersegmentsx->number>0)
    supersegmentsx->fd=CloseFileBuffered(supersegmentsx->fd);

 /* 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 *FindSuperRoutes 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 *FindSuperRoutes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match)
{
 static Results *results=NULL; /* static allocation of return value (reset each call) */
 static Queue *queue=NULL;     /* static allocation of internal value (reset each call) */
 Result *result1,*result2;
 WayX *wayx;

 /* Insert the first node into the queue */

 if(!results)
    results=NewResultsList(8);
 else
    ResetResultsList(results);

 if(!queue)
    queue=NewQueueList(8);
 else
    ResetQueueList(queue);

 result1=InsertResult(results,start,NO_SEGMENT);

 InsertInQueue(queue,result1,0);

 /* 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;

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

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

      endloop:

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

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