trunk/src/nodesx.c

/***************************************
 Extented Node data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2011 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/stat.h>

#include "types.h"
#include "nodes.h"
#include "segments.h"

#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.h"

#include "types.h"

#include "files.h"
#include "logging.h"
#include "sorting.h"


/* Variables */

/*+ The command line '--tmpdir' option or its default value. +*/
extern char *option_tmpdirname;

/*+ A temporary file-local variable for use by the sort functions. +*/
static NodesX *sortnodesx;

/* Functions */

static int sort_by_id(NodeX *a,NodeX *b);
static int index_by_id(NodeX *nodex,index_t index);

static int sort_by_lat_long(NodeX *a,NodeX *b);
static int index_by_lat_long(NodeX *nodex,index_t index);


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new node list (create a new file or open an existing one).

  NodesX *NewNodeList Returns the node list.

  int append Set to 1 if the file is to be opened for appending (now or later).
  ++++++++++++++++++++++++++++++++++++++*/

NodesX *NewNodeList(int append)
{
 NodesX *nodesx;

 nodesx=(NodesX*)calloc(1,sizeof(NodesX));

 assert(nodesx); /* Check calloc() worked */

 nodesx->filename=(char*)malloc(strlen(option_tmpdirname)+32);

 if(append)
    sprintf(nodesx->filename,"%s/nodesx.input.tmp",option_tmpdirname);
 else
    sprintf(nodesx->filename,"%s/nodesx.%p.tmp",option_tmpdirname,nodesx);

 if(append)
   {
    off_t size;

    nodesx->fd=OpenFileAppend(nodesx->filename);

    size=SizeFile(nodesx->filename);

    nodesx->number=size/sizeof(NodeX);
   }
 else
    nodesx->fd=OpenFileNew(nodesx->filename);

 return(nodesx);
}


/*++++++++++++++++++++++++++++++++++++++
  Free a node list.

  NodesX *nodesx The list to be freed.

  int keep Set to 1 if the file is to be kept.
  ++++++++++++++++++++++++++++++++++++++*/

void FreeNodeList(NodesX *nodesx,int keep)
{
 if(!keep)
    DeleteFile(nodesx->filename);

 free(nodesx->filename);

 if(nodesx->idata)
    free(nodesx->idata);

 if(nodesx->gdata)
    free(nodesx->gdata);

 if(nodesx->super)
    free(nodesx->super);

 free(nodesx);
}


/*++++++++++++++++++++++++++++++++++++++
  Append a single node to an unsorted node list.

  NodesX* nodesx The set of nodes to process.

  node_t id The node identification.

  double latitude The latitude of the node.

  double longitude The longitude of the node.

  transports_t allow The allowed traffic types through the node.

  uint16_t flags The flags to set for this node.
  ++++++++++++++++++++++++++++++++++++++*/

void AppendNode(NodesX* nodesx,node_t id,double latitude,double longitude,transports_t allow,uint16_t flags)
{
 NodeX nodex;

 nodex.id=id;
 nodex.latitude =radians_to_latlong(latitude);
 nodex.longitude=radians_to_latlong(longitude);
 nodex.allow=allow;
 nodex.flags=flags;

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

 nodesx->number++;

 assert(nodesx->number<NODE_FAKE); /* NODE_FAKE marks the high-water mark for real nodes. */
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the node list (i.e. create the sortable indexes).

  NodesX* nodesx The set of nodes to process.
  ++++++++++++++++++++++++++++++++++++++*/

void SortNodeList(NodesX* nodesx)
{
 int fd;
 index_t xnumber;

 /* Print the start message */

 printf_first("Sorting Nodes");

 /* Close the file (finished appending) */

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

 /* Re-open the file read-only and a new file writeable */

 nodesx->fd=ReOpenFile(nodesx->filename);

 DeleteFile(nodesx->filename);

 fd=OpenFileNew(nodesx->filename);

 /* Allocate the array of indexes */

 nodesx->idata=(node_t*)malloc(nodesx->number*sizeof(node_t));

 assert(nodesx->idata); /* Check malloc() worked */

 /* Sort by node indexes */

 xnumber=nodesx->number;
 nodesx->number=0;

 sortnodesx=nodesx;

 filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))index_by_id);

 /* Close the files */

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

 /* Print the final message */

 printf_last("Sorted Nodes: Nodes=%d Duplicates=%d",xnumber,xnumber-nodesx->number);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the nodes into id order.

  int sort_by_id Returns the comparison of the id fields.

  NodeX *a The first extended node.

  NodeX *b The second extended node.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_id(NodeX *a,NodeX *b)
{
 node_t a_id=a->id;
 node_t b_id=b->id;

 if(a_id<b_id)
    return(-1);
 else if(a_id>b_id)
    return(1);
 else
    return(0);
}


/*++++++++++++++++++++++++++++++++++++++
  Index the nodes after sorting.

  int index_by_id Return 1 if the value is to be kept, otherwise zero.

  NodeX *nodex The extended node.

  index_t index The index of this node in the total.
  ++++++++++++++++++++++++++++++++++++++*/

static int index_by_id(NodeX *nodex,index_t index)
{
 if(index==0 || sortnodesx->idata[index-1]!=nodex->id)
   {
    sortnodesx->idata[index]=nodex->id;

    sortnodesx->number++;

    return(1);
   }

 return(0);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the node list geographically.

  NodesX* nodesx The set of nodes to process.
  ++++++++++++++++++++++++++++++++++++++*/

void SortNodeListGeographically(NodesX* nodesx)
{
 int fd;

 /* Print the start message */

 printf_first("Sorting Nodes Geographically");

 /* Allocate the memory for the geographical index array */

 nodesx->gdata=(index_t*)malloc(nodesx->number*sizeof(index_t));

 assert(nodesx->gdata); /* Check malloc() worked */

 /* Re-open the file read-only and a new file writeable */

 nodesx->fd=ReOpenFile(nodesx->filename);

 DeleteFile(nodesx->filename);

 fd=OpenFileNew(nodesx->filename);

 /* Sort geographically */

 sortnodesx=nodesx;

 filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_lat_long,(int (*)(void*,index_t))index_by_lat_long);

 /* Close the files */

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

 /* Print the final message */

 printf_last("Sorted Nodes Geographically");
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the nodes into latitude and longitude order.

  int sort_by_lat_long Returns the comparison of the latitude and longitude fields.

  NodeX *a The first extended node.

  NodeX *b The second extended node.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_lat_long(NodeX *a,NodeX *b)
{
 ll_bin_t a_lon=latlong_to_bin(a->longitude);
 ll_bin_t b_lon=latlong_to_bin(b->longitude);

 if(a_lon<b_lon)
    return(-1);
 else if(a_lon>b_lon)
    return(1);
 else
   {
    ll_bin_t a_lat=latlong_to_bin(a->latitude);
    ll_bin_t b_lat=latlong_to_bin(b->latitude);

    if(a_lat<b_lat)
       return(-1);
    else if(a_lat>b_lat)
       return(1);
    else
      {
       if(a->longitude<b->longitude)
          return(-1);
       else if(a->longitude>b->longitude)
          return(1);
       else
         {
          if(a->latitude<b->latitude)
             return(-1);
          else if(a->latitude>b->latitude)
             return(1);
         }

       return(0);
      }
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Index the nodes after sorting.

  int index_by_lat_long Return 1 if the value is to be kept, otherwise zero.

  NodeX *nodex The extended node.

  index_t index The index of this node in the total.
  ++++++++++++++++++++++++++++++++++++++*/

static int index_by_lat_long(NodeX *nodex,index_t index)
{
 /* Create the index from the previous sort to the current one */

 sortnodesx->gdata[nodex->id]=index;

 return(1);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular node index.

  index_t IndexNodeX Returns the index of the extended node with the specified id.

  NodesX* nodesx The set of nodes to process.

  node_t id The node id to look for.
  ++++++++++++++++++++++++++++++++++++++*/

index_t IndexNodeX(NodesX* nodesx,node_t id)
{
 int start=0;
 int end=nodesx->number-1;
 int mid;

 /* Binary search - search key exact match only is required.
  *
  *  # <- start  |  Check mid and move start or end if it doesn't match
  *  #           |
  *  #           |  Since an exact match is wanted we can set end=mid-1
  *  # <- mid    |  or start=mid+1 because we know that mid doesn't match.
  *  #           |
  *  #           |  Eventually either end=start or end=start+1 and one of
  *  # <- end    |  start or end is the wanted one.
  */

 if(end<start)                        /* There are no nodes */
    return(NO_NODE);
 else if(id<nodesx->idata[start])     /* Check key is not before start */
    return(NO_NODE);
 else if(id>nodesx->idata[end])       /* Check key is not after end */
    return(NO_NODE);
 else
   {
    do
      {
       mid=(start+end)/2;             /* Choose mid point */

       if(nodesx->idata[mid]<id)      /* Mid point is too low */
          start=mid+1;
       else if(nodesx->idata[mid]>id) /* Mid point is too high */
          end=mid-1;
       else                           /* Mid point is correct */
          return(mid);
      }
    while((end-start)>1);

    if(nodesx->idata[start]==id)      /* Start is correct */
       return(start);

    if(nodesx->idata[end]==id)        /* End is correct */
       return(end);
   }

 return(NO_NODE);
}


/*++++++++++++++++++++++++++++++++++++++
  Remove any nodes that are not part of a highway.

  NodesX *nodesx The complete node list.

  SegmentsX *segmentsx The list of segments.
  ++++++++++++++++++++++++++++++++++++++*/

void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
{
 NodeX nodex;
 int total=0,highway=0,nothighway=0;
 ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
 latlong_t lat_min,lat_max,lon_min,lon_max;
 int fd;

 /* Print the start message */

 printf_first("Checking Nodes: Nodes=0");

 /* While we are here we can work out the range of data */

 lat_min=radians_to_latlong( 2);
 lat_max=radians_to_latlong(-2);
 lon_min=radians_to_latlong( 4);
 lon_max=radians_to_latlong(-4);

 /* Re-open the file read-only and a new file writeable */

 nodesx->fd=ReOpenFile(nodesx->filename);

 DeleteFile(nodesx->filename);

 fd=OpenFileNew(nodesx->filename);

 /* Modify the on-disk image */

 while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
   {
    if(!IsBitSet(segmentsx->usednode,total))
       nothighway++;
    else
      {
       nodex.id=highway;

       WriteFile(fd,&nodex,sizeof(NodeX));

       nodesx->idata[highway]=nodesx->idata[total];
       highway++;

       if(nodex.latitude<lat_min)
          lat_min=nodex.latitude;
       if(nodex.latitude>lat_max)
          lat_max=nodex.latitude;
       if(nodex.longitude<lon_min)
          lon_min=nodex.longitude;
       if(nodex.longitude>lon_max)
          lon_max=nodex.longitude;
      }

    total++;

    if(!(total%10000))
       printf_middle("Checking Nodes: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
   }

 nodesx->number=highway;

 /* Close the files */

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

 /* Work out the number of bins */

 lat_min_bin=latlong_to_bin(lat_min);
 lon_min_bin=latlong_to_bin(lon_min);
 lat_max_bin=latlong_to_bin(lat_max);
 lon_max_bin=latlong_to_bin(lon_max);

 nodesx->latzero=lat_min_bin;
 nodesx->lonzero=lon_min_bin;

 nodesx->latbins=(lat_max_bin-lat_min_bin)+1;
 nodesx->lonbins=(lon_max_bin-lon_min_bin)+1;

 /* Free the now-unneeded index */

 free(segmentsx->usednode);
 segmentsx->usednode=NULL;

 /* Allocate and set the super-node markers */

 nodesx->super=(uint8_t*)malloc((1+nodesx->number/8)*sizeof(uint8_t));

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

 memset(nodesx->super,~0,(1+nodesx->number/8));

 /* Print the final message */

 printf_last("Checked Nodes: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
}


/*++++++++++++++++++++++++++++++++++++++
  Insert the super-node flag and the first segment indexes after geographical sorting.

  NodesX *nodesx The list of nodes to update.

  SegmentsX *segmentsx The set of segments to use.
  ++++++++++++++++++++++++++++++++++++++*/

void UpdateNodes(NodesX *nodesx,SegmentsX *segmentsx)
{
 index_t i;
 int fd;

 /* Print the start message */

 printf_first("Updating Super Nodes: Nodes=0");

 /* Re-open the file read-only and a new file writeable */

 nodesx->fd=ReOpenFile(nodesx->filename);

 DeleteFile(nodesx->filename);

 fd=OpenFileNew(nodesx->filename);

 /* Modify the on-disk image */

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

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

    if(IsBitSet(nodesx->super,nodex.id))
       nodex.flags|=NODE_SUPER;

    nodex.id=segmentsx->firstnode[nodex.id];

    WriteFile(fd,&nodex,sizeof(NodeX));

    if(!((i+1)%10000))
       printf_middle("Updating Super Nodes: Nodes=%d",i+1);
   }

 /* Close the files */

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

 /* Print the final message */

 printf_last("Updated Super Nodes: Nodes=%d",nodesx->number);
}


/*++++++++++++++++++++++++++++++++++++++
  Save the node list to a file.

  NodesX* nodesx The set of nodes to save.

  const char *filename The name of the file to save.
  ++++++++++++++++++++++++++++++++++++++*/

void SaveNodeList(NodesX* nodesx,const char *filename)
{
 index_t i;
 int fd;
 NodesFile nodesfile={0};
 int super_number=0;
 index_t latlonbin=0,*offsets;

 /* Print the start message */

 printf_first("Writing Nodes: Nodes=0");

 /* Allocate the memory for the geographical offsets array */

 offsets=(index_t*)malloc((nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));

 assert(offsets); /* Check malloc() worked */

 latlonbin=0;

 /* Re-open the file */

 nodesx->fd=ReOpenFile(nodesx->filename);

 /* Write out the nodes data */

 fd=OpenFileNew(filename);

 SeekFile(fd,sizeof(NodesFile)+(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));

 for(i=0;i<nodesx->number;i++)
   {
    NodeX nodex;
    Node node;
    ll_bin_t latbin,lonbin;
    int llbin;

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

    /* Create the Node */

    node.latoffset=latlong_to_off(nodex.latitude);
    node.lonoffset=latlong_to_off(nodex.longitude);
    node.firstseg=nodex.id;
    node.allow=nodex.allow;
    node.flags=nodex.flags;

    if(node.flags&NODE_SUPER)
       super_number++;

    /* Work out the offsets */

    latbin=latlong_to_bin(nodex.latitude )-nodesx->latzero;
    lonbin=latlong_to_bin(nodex.longitude)-nodesx->lonzero;
    llbin=lonbin*nodesx->latbins+latbin;

    for(;latlonbin<=llbin;latlonbin++)
       offsets[latlonbin]=i;

    /* Write the data */

    WriteFile(fd,&node,sizeof(Node));

    if(!((i+1)%10000))
       printf_middle("Writing Nodes: Nodes=%d",i+1);
   }

 /* Close the file */

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

 /* Finish off the offset indexing and write them out */

 for(;latlonbin<=(nodesx->latbins*nodesx->lonbins);latlonbin++)
    offsets[latlonbin]=nodesx->number;

 SeekFile(fd,sizeof(NodesFile));
 WriteFile(fd,offsets,(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));

 /* Write out the header structure */

 nodesfile.number=nodesx->number;
 nodesfile.snumber=super_number;

 nodesfile.latbins=nodesx->latbins;
 nodesfile.lonbins=nodesx->lonbins;

 nodesfile.latzero=nodesx->latzero;
 nodesfile.lonzero=nodesx->lonzero;

 SeekFile(fd,0);
 WriteFile(fd,&nodesfile,sizeof(NodesFile));

 CloseFile(fd);

 /* Print the final message */

 printf_last("Wrote Nodes: Nodes=%d",nodesx->number);
}
1	amb	110	/***************************************
2			Extented Node data type functions.
3	amb	151
4			Part of the Routino routing software.
5	amb	110	****************/ /****************
6	amb	612	This file Copyright 2008-2011 Andrew M. Bishop
7	amb	110
8	amb	151	This program is free software: you can redistribute it and/or modify
9			it under the terms of the GNU Affero General Public License as published by
10			the Free Software Foundation, either version 3 of the License, or
11			(at your option) any later version.
12
13			This program is distributed in the hope that it will be useful,
14			but WITHOUT ANY WARRANTY; without even the implied warranty of
15			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16			GNU Affero General Public License for more details.
17
18			You should have received a copy of the GNU Affero General Public License
19			along with this program. If not, see <http://www.gnu.org/licenses/>.
20	amb	110	***************************************/
21
22
23			#include <assert.h>
24			#include <stdlib.h>
25			#include <stdio.h>
26	amb	249	#include <string.h>
27	amb	326	#include <sys/stat.h>
28	amb	110
29			#include "types.h"
30	amb	449	#include "nodes.h"
31			#include "segments.h"
32
33	amb	110	#include "nodesx.h"
34			#include "segmentsx.h"
35	amb	204	#include "waysx.h"
36	amb	110
37	amb	466	#include "types.h"
38
39	amb	449	#include "files.h"
40	amb	519	#include "logging.h"
41	amb	532	#include "sorting.h"
42	amb	110
43	amb	449
44	amb	252	/* Variables */
45	amb	110
46	amb	289	/+ The command line '--tmpdir' option or its default value. +/
47	amb	284	extern char *option_tmpdirname;
48	amb	110
49	amb	284	/+ A temporary file-local variable for use by the sort functions. +/
50			static NodesX *sortnodesx;
51
52	amb	110	/* Functions */
53
54	amb	271	static int sort_by_id(NodeX a,NodeX b);
55	amb	273	static int index_by_id(NodeX *nodex,index_t index);
56	amb	271
57	amb	281	static int sort_by_lat_long(NodeX a,NodeX b);
58			static int index_by_lat_long(NodeX *nodex,index_t index);
59	amb	110
60
61			/*++++++++++++++++++++++++++++++++++++++
62	amb	326	Allocate a new node list (create a new file or open an existing one).
63	amb	110
64			NodesX *NewNodeList Returns the node list.
65	amb	326
66			int append Set to 1 if the file is to be opened for appending (now or later).
67	amb	110	++++++++++++++++++++++++++++++++++++++*/
68
69	amb	326	NodesX *NewNodeList(int append)
70	amb	110	{
71			NodesX *nodesx;
72
73	amb	213	nodesx=(NodesX*)calloc(1,sizeof(NodesX));
74	amb	110
75	amb	243	assert(nodesx); /* Check calloc() worked */
76
77	amb	284	nodesx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
78	amb	216
79	amb	326	if(append)
80	amb	447	sprintf(nodesx->filename,"%s/nodesx.input.tmp",option_tmpdirname);
81	amb	326	else
82	amb	447	sprintf(nodesx->filename,"%s/nodesx.%p.tmp",option_tmpdirname,nodesx);
83	amb	249
84	amb	326	if(append)
85			{
86	amb	331	off_t size;
87	amb	326
88	amb	502	nodesx->fd=OpenFileAppend(nodesx->filename);
89	amb	326
90	amb	331	size=SizeFile(nodesx->filename);
91	amb	326
92	amb	650	nodesx->number=size/sizeof(NodeX);
93	amb	326	}
94			else
95	amb	502	nodesx->fd=OpenFileNew(nodesx->filename);
96	amb	326
97	amb	110	return(nodesx);
98			}
99
100
101			/*++++++++++++++++++++++++++++++++++++++
102	amb	226	Free a node list.
103
104			NodesX *nodesx The list to be freed.
105	amb	326
106			int keep Set to 1 if the file is to be kept.
107	amb	226	++++++++++++++++++++++++++++++++++++++*/
108
109	amb	326	void FreeNodeList(NodesX *nodesx,int keep)
110	amb	226	{
111	amb	326	if(!keep)
112			DeleteFile(nodesx->filename);
113
114	amb	283	free(nodesx->filename);
115	amb	226
116			if(nodesx->idata)
117			free(nodesx->idata);
118
119	amb	552	if(nodesx->gdata)
120			free(nodesx->gdata);
121	amb	226
122	amb	283	if(nodesx->super)
123			free(nodesx->super);
124
125	amb	226	free(nodesx);
126			}
127
128
129			/*++++++++++++++++++++++++++++++++++++++
130	amb	493	Append a single node to an unsorted node list.
131	amb	243
132	amb	252	NodesX* nodesx The set of nodes to process.
133	amb	243
134	amb	252	node_t id The node identification.
135	amb	110
136	amb	252	double latitude The latitude of the node.
137	amb	110
138	amb	252	double longitude The longitude of the node.
139	amb	469
140	amb	529	transports_t allow The allowed traffic types through the node.
141	amb	537
142	amb	538	uint16_t flags The flags to set for this node.
143	amb	252	++++++++++++++++++++++++++++++++++++++*/
144	amb	110
145	amb	538	void AppendNode(NodesX* nodesx,node_t id,double latitude,double longitude,transports_t allow,uint16_t flags)
146	amb	252	{
147			NodeX nodex;
148	amb	249
149	amb	252	nodex.id=id;
150			nodex.latitude =radians_to_latlong(latitude);
151			nodex.longitude=radians_to_latlong(longitude);
152	amb	469	nodex.allow=allow;
153	amb	538	nodex.flags=flags;
154	amb	252
155			WriteFile(nodesx->fd,&nodex,sizeof(NodeX));
156
157	amb	650	nodesx->number++;
158	amb	466
159	amb	650	assert(nodesx->number<NODE_FAKE); /* NODE_FAKE marks the high-water mark for real nodes. */
160	amb	110	}
161
162
163			/*++++++++++++++++++++++++++++++++++++++
164	amb	263	Sort the node list (i.e. create the sortable indexes).
165	amb	110
166			NodesX* nodesx The set of nodes to process.
167			++++++++++++++++++++++++++++++++++++++*/
168
169	amb	263	void SortNodeList(NodesX* nodesx)
170	amb	110	{
171	amb	263	int fd;
172	amb	650	index_t xnumber;
173	amb	110
174	amb	263	/* Print the start message */
175
176	amb	519	printf_first("Sorting Nodes");
177	amb	132
178	amb	555	/* Close the file (finished appending) */
179	amb	260
180	amb	612	nodesx->fd=CloseFile(nodesx->fd);
181	amb	555
182			/* Re-open the file read-only and a new file writeable */
183
184	amb	260	nodesx->fd=ReOpenFile(nodesx->filename);
185
186	amb	271	DeleteFile(nodesx->filename);
187
188	amb	502	fd=OpenFileNew(nodesx->filename);
189	amb	271
190	amb	252	/* Allocate the array of indexes */
191	amb	249
192	amb	650	nodesx->idata=(node_t)malloc(nodesx->numbersizeof(node_t));
193	amb	249
194	amb	252	assert(nodesx->idata); /* Check malloc() worked */
195	amb	249
196	amb	271	/* Sort by node indexes */
197	amb	249
198	amb	650	xnumber=nodesx->number;
199			nodesx->number=0;
200
201	amb	271	sortnodesx=nodesx;
202	amb	110
203	amb	311	filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int ()(const void,const void))sort_by_id,(int ()(void*,index_t))index_by_id);
204	amb	252
205	amb	555	/* Close the files */
206	amb	260
207	amb	612	nodesx->fd=CloseFile(nodesx->fd);
208	amb	257	CloseFile(fd);
209	amb	252
210	amb	263	/* Print the final message */
211
212	amb	650	printf_last("Sorted Nodes: Nodes=%d Duplicates=%d",xnumber,xnumber-nodesx->number);
213	amb	110	}
214
215
216			/*++++++++++++++++++++++++++++++++++++++
217			Sort the nodes into id order.
218
219			int sort_by_id Returns the comparison of the id fields.
220
221	amb	271	NodeX *a The first extended node.
222	amb	110
223	amb	271	NodeX *b The second extended node.
224	amb	110	++++++++++++++++++++++++++++++++++++++*/
225
226	amb	271	static int sort_by_id(NodeX a,NodeX b)
227	amb	110	{
228	amb	271	node_t a_id=a->id;
229			node_t b_id=b->id;
230	amb	252
231			if(a_id<b_id)
232			return(-1);
233			else if(a_id>b_id)
234	amb	249	return(1);
235	amb	110	else
236	amb	252	return(0);
237	amb	110	}
238
239
240	amb	271	/*++++++++++++++++++++++++++++++++++++++
241			Index the nodes after sorting.
242	amb	252
243	amb	289	int index_by_id Return 1 if the value is to be kept, otherwise zero.
244	amb	273
245	amb	271	NodeX *nodex The extended node.
246	amb	252
247	amb	271	index_t index The index of this node in the total.
248			++++++++++++++++++++++++++++++++++++++*/
249
250	amb	273	static int index_by_id(NodeX *nodex,index_t index)
251	amb	271	{
252	amb	273	if(index==0 \|\| sortnodesx->idata[index-1]!=nodex->id)
253			{
254			sortnodesx->idata[index]=nodex->id;
255	amb	271
256	amb	273	sortnodesx->number++;
257
258			return(1);
259			}
260
261			return(0);
262	amb	271	}
263
264
265	amb	110	/*++++++++++++++++++++++++++++++++++++++
266	amb	212	Sort the node list geographically.
267
268			NodesX* nodesx The set of nodes to process.
269			++++++++++++++++++++++++++++++++++++++*/
270
271			void SortNodeListGeographically(NodesX* nodesx)
272			{
273	amb	281	int fd;
274	amb	212
275	amb	263	/* Print the start message */
276
277	amb	519	printf_first("Sorting Nodes Geographically");
278	amb	212
279	amb	552	/* Allocate the memory for the geographical index array */
280
281			nodesx->gdata=(index_t)malloc(nodesx->numbersizeof(index_t));
282
283			assert(nodesx->gdata); /* Check malloc() worked */
284
285	amb	555	/* Re-open the file read-only and a new file writeable */
286	amb	212
287	amb	281	nodesx->fd=ReOpenFile(nodesx->filename);
288	amb	243
289	amb	281	DeleteFile(nodesx->filename);
290	amb	212
291	amb	502	fd=OpenFileNew(nodesx->filename);
292	amb	212
293	amb	281	/* Sort geographically */
294	amb	252
295	amb	281	sortnodesx=nodesx;
296	amb	257
297	amb	311	filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int ()(const void,const void))sort_by_lat_long,(int ()(void*,index_t))index_by_lat_long);
298	amb	257
299	amb	555	/* Close the files */
300	amb	257
301	amb	612	nodesx->fd=CloseFile(nodesx->fd);
302	amb	281	CloseFile(fd);
303	amb	257
304	amb	263	/* Print the final message */
305	amb	257
306	amb	519	printf_last("Sorted Nodes Geographically");
307	amb	212	}
308
309
310			/*++++++++++++++++++++++++++++++++++++++
311	amb	110	Sort the nodes into latitude and longitude order.
312
313			int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
314
315	amb	281	NodeX *a The first extended node.
316	amb	110
317	amb	281	NodeX *b The second extended node.
318	amb	110	++++++++++++++++++++++++++++++++++++++*/
319
320	amb	281	static int sort_by_lat_long(NodeX a,NodeX b)
321	amb	110	{
322	amb	281	ll_bin_t a_lon=latlong_to_bin(a->longitude);
323			ll_bin_t b_lon=latlong_to_bin(b->longitude);
324	amb	110
325			if(a_lon<b_lon)
326			return(-1);
327			else if(a_lon>b_lon)
328			return(1);
329			else
330			{
331	amb	281	ll_bin_t a_lat=latlong_to_bin(a->latitude);
332			ll_bin_t b_lat=latlong_to_bin(b->latitude);
333	amb	110
334			if(a_lat<b_lat)
335			return(-1);
336			else if(a_lat>b_lat)
337			return(1);
338			else
339	amb	281	{
340	amb	664	if(a->longitude<b->longitude)
341	amb	281	return(-1);
342	amb	664	else if(a->longitude>b->longitude)
343	amb	281	return(1);
344			else
345	amb	664	{
346			if(a->latitude<b->latitude)
347			return(-1);
348			else if(a->latitude>b->latitude)
349			return(1);
350			}
351
352			return(0);
353	amb	281	}
354	amb	110	}
355			}
356
357
358			/*++++++++++++++++++++++++++++++++++++++
359	amb	281	Index the nodes after sorting.
360
361	amb	289	int index_by_lat_long Return 1 if the value is to be kept, otherwise zero.
362	amb	281
363			NodeX *nodex The extended node.
364
365			index_t index The index of this node in the total.
366			++++++++++++++++++++++++++++++++++++++*/
367
368			static int index_by_lat_long(NodeX *nodex,index_t index)
369			{
370	amb	552	/* Create the index from the previous sort to the current one */
371
372			sortnodesx->gdata[nodex->id]=index;
373
374	amb	281	return(1);
375			}
376
377
378			/*++++++++++++++++++++++++++++++++++++++
379	amb	285	Find a particular node index.
380
381			index_t IndexNodeX Returns the index of the extended node with the specified id.
382
383			NodesX* nodesx The set of nodes to process.
384
385			node_t id The node id to look for.
386			++++++++++++++++++++++++++++++++++++++*/
387
388			index_t IndexNodeX(NodesX* nodesx,node_t id)
389			{
390			int start=0;
391			int end=nodesx->number-1;
392			int mid;
393
394			/* Binary search - search key exact match only is required.
395			*
396			* # <- start \| Check mid and move start or end if it doesn't match
397			* # \|
398			* # \| Since an exact match is wanted we can set end=mid-1
399			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
400			* # \|
401			* # \| Eventually either end=start or end=start+1 and one of
402			* # <- end \| start or end is the wanted one.
403			*/
404
405			if(end<start) /* There are no nodes */
406			return(NO_NODE);
407			else if(id<nodesx->idata[start]) /* Check key is not before start */
408			return(NO_NODE);
409			else if(id>nodesx->idata[end]) /* Check key is not after end */
410			return(NO_NODE);
411			else
412			{
413			do
414			{
415			mid=(start+end)/2; /* Choose mid point */
416
417			if(nodesx->idata[mid]<id) /* Mid point is too low */
418			start=mid+1;
419			else if(nodesx->idata[mid]>id) /* Mid point is too high */
420			end=mid-1;
421			else /* Mid point is correct */
422			return(mid);
423			}
424			while((end-start)>1);
425
426			if(nodesx->idata[start]==id) /* Start is correct */
427			return(start);
428
429			if(nodesx->idata[end]==id) /* End is correct */
430			return(end);
431			}
432
433			return(NO_NODE);
434			}
435
436
437			/*++++++++++++++++++++++++++++++++++++++
438	amb	110	Remove any nodes that are not part of a highway.
439
440			NodesX *nodesx The complete node list.
441
442			SegmentsX *segmentsx The list of segments.
443			++++++++++++++++++++++++++++++++++++++*/
444
445			void RemoveNonHighwayNodes(NodesX nodesx,SegmentsX segmentsx)
446			{
447	amb	263	NodeX nodex;
448	amb	273	int total=0,highway=0,nothighway=0;
449	amb	281	ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
450			latlong_t lat_min,lat_max,lon_min,lon_max;
451	amb	263	int fd;
452	amb	110
453	amb	263	/* Print the start message */
454
455	amb	627	printf_first("Checking Nodes: Nodes=0");
456	amb	227
457	amb	281	/* While we are here we can work out the range of data */
458
459			lat_min=radians_to_latlong( 2);
460			lat_max=radians_to_latlong(-2);
461			lon_min=radians_to_latlong( 4);
462			lon_max=radians_to_latlong(-4);
463
464	amb	555	/* Re-open the file read-only and a new file writeable */
465	amb	263
466	amb	555	nodesx->fd=ReOpenFile(nodesx->filename);
467
468	amb	263	DeleteFile(nodesx->filename);
469
470	amb	502	fd=OpenFileNew(nodesx->filename);
471	amb	263
472	amb	555	/* Modify the on-disk image */
473
474	amb	263	while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
475	amb	110	{
476	amb	655	if(!IsBitSet(segmentsx->usednode,total))
477	amb	271	nothighway++;
478			else
479	amb	263	{
480	amb	280	nodex.id=highway;
481
482	amb	263	WriteFile(fd,&nodex,sizeof(NodeX));
483
484			nodesx->idata[highway]=nodesx->idata[total];
485	amb	110	highway++;
486	amb	281
487			if(nodex.latitude<lat_min)
488			lat_min=nodex.latitude;
489			if(nodex.latitude>lat_max)
490			lat_max=nodex.latitude;
491			if(nodex.longitude<lon_min)
492			lon_min=nodex.longitude;
493			if(nodex.longitude>lon_max)
494			lon_max=nodex.longitude;
495	amb	263	}
496	amb	110
497	amb	263	total++;
498
499			if(!(total%10000))
500	amb	627	printf_middle("Checking Nodes: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
501	amb	110	}
502
503	amb	555	nodesx->number=highway;
504	amb	263
505	amb	555	/* Close the files */
506
507	amb	612	nodesx->fd=CloseFile(nodesx->fd);
508	amb	263	CloseFile(fd);
509
510	amb	281	/* Work out the number of bins */
511
512			lat_min_bin=latlong_to_bin(lat_min);
513			lon_min_bin=latlong_to_bin(lon_min);
514			lat_max_bin=latlong_to_bin(lat_max);
515			lon_max_bin=latlong_to_bin(lon_max);
516
517			nodesx->latzero=lat_min_bin;
518			nodesx->lonzero=lon_min_bin;
519
520			nodesx->latbins=(lat_max_bin-lat_min_bin)+1;
521			nodesx->lonbins=(lon_max_bin-lon_min_bin)+1;
522
523	amb	643	/* Free the now-unneeded index */
524
525			free(segmentsx->usednode);
526			segmentsx->usednode=NULL;
527
528	amb	653	/* Allocate and set the super-node markers */
529	amb	263
530	amb	654	nodesx->super=(uint8_t)malloc((1+nodesx->number/8)sizeof(uint8_t));
531	amb	263
532			assert(nodesx->super); /* Check calloc() worked */
533
534	amb	654	memset(nodesx->super,~0,(1+nodesx->number/8));
535	amb	653
536	amb	263	/* Print the final message */
537
538	amb	627	printf_last("Checked Nodes: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
539	amb	110	}
540
541
542			/*++++++++++++++++++++++++++++++++++++++
543	amb	643	Insert the super-node flag and the first segment indexes after geographical sorting.
544	amb	110
545	amb	643	NodesX *nodesx The list of nodes to update.
546	amb	110
547	amb	643	SegmentsX *segmentsx The set of segments to use.
548	amb	110	++++++++++++++++++++++++++++++++++++++*/
549
550	amb	653	void UpdateNodes(NodesX nodesx,SegmentsX segmentsx)
551	amb	110	{
552	amb	214	index_t i;
553	amb	643	int fd;
554	amb	110
555	amb	275	/* Print the start message */
556
557	amb	643	printf_first("Updating Super Nodes: Nodes=0");
558	amb	227
559	amb	643	/* Re-open the file read-only and a new file writeable */
560	amb	275
561	amb	643	nodesx->fd=ReOpenFile(nodesx->filename);
562	amb	554
563	amb	643	DeleteFile(nodesx->filename);
564	amb	212
565	amb	643	fd=OpenFileNew(nodesx->filename);
566
567			/* Modify the on-disk image */
568
569	amb	110	for(i=0;i<nodesx->number;i++)
570			{
571	amb	643	NodeX nodex;
572	amb	208
573	amb	643	ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
574	amb	212
575	amb	654	if(IsBitSet(nodesx->super,nodex.id))
576	amb	643	nodex.flags\|=NODE_SUPER;
577	amb	212
578	amb	643	nodex.id=segmentsx->firstnode[nodex.id];
579	amb	448
580	amb	643	WriteFile(fd,&nodex,sizeof(NodeX));
581
582	amb	110	if(!((i+1)%10000))
583	amb	643	printf_middle("Updating Super Nodes: Nodes=%d",i+1);
584	amb	110	}
585
586	amb	643	/* Close the files */
587
588			nodesx->fd=CloseFile(nodesx->fd);
589			CloseFile(fd);
590
591	amb	275	/* Print the final message */
592
593	amb	643	printf_last("Updated Super Nodes: Nodes=%d",nodesx->number);
594	amb	110	}
595
596
597			/*++++++++++++++++++++++++++++++++++++++
598	amb	285	Save the node list to a file.
599
600			NodesX* nodesx The set of nodes to save.
601
602			const char *filename The name of the file to save.
603			++++++++++++++++++++++++++++++++++++++*/
604
605			void SaveNodeList(NodesX* nodesx,const char *filename)
606			{
607			index_t i;
608			int fd;
609	amb	500	NodesFile nodesfile={0};
610	amb	285	int super_number=0;
611	amb	553	index_t latlonbin=0,*offsets;
612	amb	285
613			/* Print the start message */
614
615	amb	519	printf_first("Writing Nodes: Nodes=0");
616	amb	285
617	amb	553	/* Allocate the memory for the geographical offsets array */
618
619			offsets=(index_t)malloc((nodesx->latbinsnodesx->lonbins+1)*sizeof(index_t));
620
621			assert(offsets); /* Check malloc() worked */
622
623			latlonbin=0;
624
625	amb	556	/* Re-open the file */
626	amb	285
627	amb	555	nodesx->fd=ReOpenFile(nodesx->filename);
628	amb	285
629	amb	461	/* Write out the nodes data */
630	amb	285
631	amb	502	fd=OpenFileNew(filename);
632	amb	285
633	amb	553	SeekFile(fd,sizeof(NodesFile)+(nodesx->latbinsnodesx->lonbins+1)sizeof(index_t));
634	amb	285
635	amb	461	for(i=0;i<nodesx->number;i++)
636	amb	285	{
637	amb	556	NodeX nodex;
638	amb	552	Node node;
639	amb	553	ll_bin_t latbin,lonbin;
640			int llbin;
641	amb	285
642	amb	556	ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
643
644	amb	553	/* Create the Node */
645
646	amb	556	node.latoffset=latlong_to_off(nodex.latitude);
647			node.lonoffset=latlong_to_off(nodex.longitude);
648			node.firstseg=nodex.id;
649			node.allow=nodex.allow;
650			node.flags=nodex.flags;
651	amb	552
652			if(node.flags&NODE_SUPER)
653	amb	461	super_number++;
654
655	amb	553	/* Work out the offsets */
656
657	amb	556	latbin=latlong_to_bin(nodex.latitude )-nodesx->latzero;
658			lonbin=latlong_to_bin(nodex.longitude)-nodesx->lonzero;
659	amb	553	llbin=lonbin*nodesx->latbins+latbin;
660
661			for(;latlonbin<=llbin;latlonbin++)
662			offsets[latlonbin]=i;
663
664			/* Write the data */
665
666	amb	552	WriteFile(fd,&node,sizeof(Node));
667	amb	285
668			if(!((i+1)%10000))
669	amb	519	printf_middle("Writing Nodes: Nodes=%d",i+1);
670	amb	285	}
671
672	amb	556	/* Close the file */
673
674	amb	612	nodesx->fd=CloseFile(nodesx->fd);
675	amb	556
676	amb	553	/* Finish off the offset indexing and write them out */
677
678			for(;latlonbin<=(nodesx->latbins*nodesx->lonbins);latlonbin++)
679			offsets[latlonbin]=nodesx->number;
680
681			SeekFile(fd,sizeof(NodesFile));
682			WriteFile(fd,offsets,(nodesx->latbinsnodesx->lonbins+1)sizeof(index_t));
683
684	amb	461	/* Write out the header structure */
685
686			nodesfile.number=nodesx->number;
687			nodesfile.snumber=super_number;
688
689			nodesfile.latbins=nodesx->latbins;
690			nodesfile.lonbins=nodesx->lonbins;
691
692			nodesfile.latzero=nodesx->latzero;
693			nodesfile.lonzero=nodesx->lonzero;
694
695			SeekFile(fd,0);
696			WriteFile(fd,&nodesfile,sizeof(NodesFile));
697
698	amb	285	CloseFile(fd);
699
700			/* Print the final message */
701
702	amb	519	printf_last("Wrote Nodes: Nodes=%d",nodesx->number);
703	amb	285	}