trunk/src/superx.c

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

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2015, 2022 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,SizeBitMask(nodesx->number));

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