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 deduplicate_and_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 a pointer to 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 set of nodes to be freed.

  int keep Set to 1 if the file is to be kept (for appending later).
  ++++++++++++++++++++++++++++++++++++++*/

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 modify.

  node_t id The node identifier from the original OSM data.

  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.

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

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))deduplicate_and_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);
}


/*++++++++++++++++++++++++++++++++++++++
  Create the index of identifiers and discard duplicate nodes.

  int deduplicate_and_index_by_id Return 1 if the value is to be kept, otherwise 0.

  NodeX *nodex The extended node.

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

static int deduplicate_and_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 modify.
  ++++++++++++++++++++++++++++++++++++++*/

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 (first by longitude bin
  number, then by latitude bin number and then by exact longitude and then by
  exact latitude).

  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);
      }
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Create the index between the sorted and unsorted nodes.

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

  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 use.

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

index_t IndexNodeX(NodesX *nodesx,node_t id)
{
 index_t start=0;
 index_t end=nodesx->number-1;
 index_t 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 set of nodes to modify.

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

void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
{
 NodeX nodex;
 index_t 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 set of nodes to modify.

  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[nodesx->gdata[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 final node list database 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};
 index_t super_number=0;
 ll_bin2_t latlonbin=0;
 index_t *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;
    ll_bin2_t 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	680	static int deduplicate_and_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	amb	680	NodesX *NewNodeList Returns a pointer to 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	amb	681	NodesX *nodesx The set of nodes to be freed.
105	amb	326
106	amb	680	int keep Set to 1 if the file is to be kept (for appending later).
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	681	NodesX *nodesx The set of nodes to modify.
133	amb	243
134	amb	680	node_t id The node identifier from the original OSM data.
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	681	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	680	Sort the node list.
165	amb	110
166	amb	681	NodesX *nodesx The set of nodes to modify.
167	amb	110	++++++++++++++++++++++++++++++++++++++*/
168
169	amb	681	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	680	filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int ()(const void,const void))sort_by_id,(int ()(void*,index_t))deduplicate_and_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	amb	680	Create the index of identifiers and discard duplicate nodes.
242	amb	252
243	amb	680	int deduplicate_and_index_by_id Return 1 if the value is to be kept, otherwise 0.
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	680	static int deduplicate_and_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	amb	681	NodesX *nodesx The set of nodes to modify.
269	amb	212	++++++++++++++++++++++++++++++++++++++*/
270
271	amb	681	void SortNodeListGeographically(NodesX *nodesx)
272	amb	212	{
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	680	Sort the nodes into latitude and longitude order (first by longitude bin
312			number, then by latitude bin number and then by exact longitude and then by
313			exact latitude).
314	amb	110
315			int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
316
317	amb	281	NodeX *a The first extended node.
318	amb	110
319	amb	281	NodeX *b The second extended node.
320	amb	110	++++++++++++++++++++++++++++++++++++++*/
321
322	amb	281	static int sort_by_lat_long(NodeX a,NodeX b)
323	amb	110	{
324	amb	281	ll_bin_t a_lon=latlong_to_bin(a->longitude);
325			ll_bin_t b_lon=latlong_to_bin(b->longitude);
326	amb	110
327			if(a_lon<b_lon)
328			return(-1);
329			else if(a_lon>b_lon)
330			return(1);
331			else
332			{
333	amb	281	ll_bin_t a_lat=latlong_to_bin(a->latitude);
334			ll_bin_t b_lat=latlong_to_bin(b->latitude);
335	amb	110
336			if(a_lat<b_lat)
337			return(-1);
338			else if(a_lat>b_lat)
339			return(1);
340			else
341	amb	281	{
342	amb	664	if(a->longitude<b->longitude)
343	amb	281	return(-1);
344	amb	664	else if(a->longitude>b->longitude)
345	amb	281	return(1);
346			else
347	amb	664	{
348			if(a->latitude<b->latitude)
349			return(-1);
350			else if(a->latitude>b->latitude)
351			return(1);
352			}
353
354			return(0);
355	amb	281	}
356	amb	110	}
357			}
358
359
360			/*++++++++++++++++++++++++++++++++++++++
361	amb	680	Create the index between the sorted and unsorted nodes.
362	amb	281
363	amb	680	int index_by_lat_long Return 1 if the value is to be kept, otherwise 0.
364	amb	281
365			NodeX *nodex The extended node.
366
367			index_t index The index of this node in the total.
368			++++++++++++++++++++++++++++++++++++++*/
369
370			static int index_by_lat_long(NodeX *nodex,index_t index)
371			{
372	amb	552	/* Create the index from the previous sort to the current one */
373
374			sortnodesx->gdata[nodex->id]=index;
375
376	amb	281	return(1);
377			}
378
379
380			/*++++++++++++++++++++++++++++++++++++++
381	amb	285	Find a particular node index.
382
383			index_t IndexNodeX Returns the index of the extended node with the specified id.
384
385	amb	681	NodesX *nodesx The set of nodes to use.
386	amb	285
387			node_t id The node id to look for.
388			++++++++++++++++++++++++++++++++++++++*/
389
390	amb	681	index_t IndexNodeX(NodesX *nodesx,node_t id)
391	amb	285	{
392	amb	780	index_t start=0;
393			index_t end=nodesx->number-1;
394			index_t mid;
395	amb	285
396			/* Binary search - search key exact match only is required.
397			*
398			* # <- start \| Check mid and move start or end if it doesn't match
399			* # \|
400			* # \| Since an exact match is wanted we can set end=mid-1
401			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
402			* # \|
403			* # \| Eventually either end=start or end=start+1 and one of
404			* # <- end \| start or end is the wanted one.
405			*/
406
407			if(end<start) /* There are no nodes */
408			return(NO_NODE);
409			else if(id<nodesx->idata[start]) /* Check key is not before start */
410			return(NO_NODE);
411			else if(id>nodesx->idata[end]) /* Check key is not after end */
412			return(NO_NODE);
413			else
414			{
415			do
416			{
417			mid=(start+end)/2; /* Choose mid point */
418
419			if(nodesx->idata[mid]<id) /* Mid point is too low */
420			start=mid+1;
421			else if(nodesx->idata[mid]>id) /* Mid point is too high */
422			end=mid-1;
423			else /* Mid point is correct */
424			return(mid);
425			}
426			while((end-start)>1);
427
428			if(nodesx->idata[start]==id) /* Start is correct */
429			return(start);
430
431			if(nodesx->idata[end]==id) /* End is correct */
432			return(end);
433			}
434
435			return(NO_NODE);
436			}
437
438
439			/*++++++++++++++++++++++++++++++++++++++
440	amb	110	Remove any nodes that are not part of a highway.
441
442	amb	681	NodesX *nodesx The set of nodes to modify.
443	amb	110
444	amb	680	SegmentsX *segmentsx The set of segments to use.
445	amb	110	++++++++++++++++++++++++++++++++++++++*/
446
447			void RemoveNonHighwayNodes(NodesX nodesx,SegmentsX segmentsx)
448			{
449	amb	263	NodeX nodex;
450	amb	780	index_t total=0,highway=0,nothighway=0;
451	amb	281	ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
452			latlong_t lat_min,lat_max,lon_min,lon_max;
453	amb	263	int fd;
454	amb	110
455	amb	263	/* Print the start message */
456
457	amb	627	printf_first("Checking Nodes: Nodes=0");
458	amb	227
459	amb	281	/* While we are here we can work out the range of data */
460
461			lat_min=radians_to_latlong( 2);
462			lat_max=radians_to_latlong(-2);
463			lon_min=radians_to_latlong( 4);
464			lon_max=radians_to_latlong(-4);
465
466	amb	555	/* Re-open the file read-only and a new file writeable */
467	amb	263
468	amb	555	nodesx->fd=ReOpenFile(nodesx->filename);
469
470	amb	263	DeleteFile(nodesx->filename);
471
472	amb	502	fd=OpenFileNew(nodesx->filename);
473	amb	263
474	amb	555	/* Modify the on-disk image */
475
476	amb	263	while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
477	amb	110	{
478	amb	655	if(!IsBitSet(segmentsx->usednode,total))
479	amb	271	nothighway++;
480			else
481	amb	263	{
482	amb	280	nodex.id=highway;
483
484	amb	263	WriteFile(fd,&nodex,sizeof(NodeX));
485
486			nodesx->idata[highway]=nodesx->idata[total];
487	amb	110	highway++;
488	amb	281
489			if(nodex.latitude<lat_min)
490			lat_min=nodex.latitude;
491			if(nodex.latitude>lat_max)
492			lat_max=nodex.latitude;
493			if(nodex.longitude<lon_min)
494			lon_min=nodex.longitude;
495			if(nodex.longitude>lon_max)
496			lon_max=nodex.longitude;
497	amb	263	}
498	amb	110
499	amb	263	total++;
500
501			if(!(total%10000))
502	amb	627	printf_middle("Checking Nodes: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
503	amb	110	}
504
505	amb	555	nodesx->number=highway;
506	amb	263
507	amb	555	/* Close the files */
508
509	amb	612	nodesx->fd=CloseFile(nodesx->fd);
510	amb	263	CloseFile(fd);
511
512	amb	281	/* Work out the number of bins */
513
514			lat_min_bin=latlong_to_bin(lat_min);
515			lon_min_bin=latlong_to_bin(lon_min);
516			lat_max_bin=latlong_to_bin(lat_max);
517			lon_max_bin=latlong_to_bin(lon_max);
518
519			nodesx->latzero=lat_min_bin;
520			nodesx->lonzero=lon_min_bin;
521
522			nodesx->latbins=(lat_max_bin-lat_min_bin)+1;
523			nodesx->lonbins=(lon_max_bin-lon_min_bin)+1;
524
525	amb	643	/* Free the now-unneeded index */
526
527			free(segmentsx->usednode);
528			segmentsx->usednode=NULL;
529
530	amb	653	/* Allocate and set the super-node markers */
531	amb	263
532	amb	654	nodesx->super=(uint8_t)malloc((1+nodesx->number/8)sizeof(uint8_t));
533	amb	263
534			assert(nodesx->super); /* Check calloc() worked */
535
536	amb	654	memset(nodesx->super,~0,(1+nodesx->number/8));
537	amb	653
538	amb	263	/* Print the final message */
539
540	amb	627	printf_last("Checked Nodes: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
541	amb	110	}
542
543
544			/*++++++++++++++++++++++++++++++++++++++
545	amb	643	Insert the super-node flag and the first segment indexes after geographical sorting.
546	amb	110
547	amb	681	NodesX *nodesx The set of nodes to modify.
548	amb	110
549	amb	643	SegmentsX *segmentsx The set of segments to use.
550	amb	110	++++++++++++++++++++++++++++++++++++++*/
551
552	amb	653	void UpdateNodes(NodesX nodesx,SegmentsX segmentsx)
553	amb	110	{
554	amb	214	index_t i;
555	amb	643	int fd;
556	amb	110
557	amb	275	/* Print the start message */
558
559	amb	643	printf_first("Updating Super Nodes: Nodes=0");
560	amb	227
561	amb	643	/* Re-open the file read-only and a new file writeable */
562	amb	275
563	amb	643	nodesx->fd=ReOpenFile(nodesx->filename);
564	amb	554
565	amb	643	DeleteFile(nodesx->filename);
566	amb	212
567	amb	643	fd=OpenFileNew(nodesx->filename);
568
569			/* Modify the on-disk image */
570
571	amb	110	for(i=0;i<nodesx->number;i++)
572			{
573	amb	643	NodeX nodex;
574	amb	208
575	amb	643	ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
576	amb	212
577	amb	654	if(IsBitSet(nodesx->super,nodex.id))
578	amb	643	nodex.flags\|=NODE_SUPER;
579	amb	212
580	amb	674	nodex.id=segmentsx->firstnode[nodesx->gdata[nodex.id]];
581	amb	448
582	amb	643	WriteFile(fd,&nodex,sizeof(NodeX));
583
584	amb	110	if(!((i+1)%10000))
585	amb	643	printf_middle("Updating Super Nodes: Nodes=%d",i+1);
586	amb	110	}
587
588	amb	643	/* Close the files */
589
590			nodesx->fd=CloseFile(nodesx->fd);
591			CloseFile(fd);
592
593	amb	275	/* Print the final message */
594
595	amb	643	printf_last("Updated Super Nodes: Nodes=%d",nodesx->number);
596	amb	110	}
597
598
599			/*++++++++++++++++++++++++++++++++++++++
600	amb	680	Save the final node list database to a file.
601	amb	285
602	amb	681	NodesX *nodesx The set of nodes to save.
603	amb	285
604			const char *filename The name of the file to save.
605			++++++++++++++++++++++++++++++++++++++*/
606
607	amb	681	void SaveNodeList(NodesX nodesx,const char filename)
608	amb	285	{
609			index_t i;
610			int fd;
611	amb	500	NodesFile nodesfile={0};
612	amb	780	index_t super_number=0;
613			ll_bin2_t latlonbin=0;
614			index_t *offsets;
615	amb	285
616			/* Print the start message */
617
618	amb	519	printf_first("Writing Nodes: Nodes=0");
619	amb	285
620	amb	553	/* Allocate the memory for the geographical offsets array */
621
622			offsets=(index_t)malloc((nodesx->latbinsnodesx->lonbins+1)*sizeof(index_t));
623
624			assert(offsets); /* Check malloc() worked */
625
626			latlonbin=0;
627
628	amb	556	/* Re-open the file */
629	amb	285
630	amb	555	nodesx->fd=ReOpenFile(nodesx->filename);
631	amb	285
632	amb	461	/* Write out the nodes data */
633	amb	285
634	amb	502	fd=OpenFileNew(filename);
635	amb	285
636	amb	553	SeekFile(fd,sizeof(NodesFile)+(nodesx->latbinsnodesx->lonbins+1)sizeof(index_t));
637	amb	285
638	amb	461	for(i=0;i<nodesx->number;i++)
639	amb	285	{
640	amb	556	NodeX nodex;
641	amb	552	Node node;
642	amb	553	ll_bin_t latbin,lonbin;
643	amb	780	ll_bin2_t llbin;
644	amb	285
645	amb	556	ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
646
647	amb	553	/* Create the Node */
648
649	amb	556	node.latoffset=latlong_to_off(nodex.latitude);
650			node.lonoffset=latlong_to_off(nodex.longitude);
651			node.firstseg=nodex.id;
652			node.allow=nodex.allow;
653			node.flags=nodex.flags;
654	amb	552
655			if(node.flags&NODE_SUPER)
656	amb	461	super_number++;
657
658	amb	553	/* Work out the offsets */
659
660	amb	556	latbin=latlong_to_bin(nodex.latitude )-nodesx->latzero;
661			lonbin=latlong_to_bin(nodex.longitude)-nodesx->lonzero;
662	amb	553	llbin=lonbin*nodesx->latbins+latbin;
663
664			for(;latlonbin<=llbin;latlonbin++)
665			offsets[latlonbin]=i;
666
667			/* Write the data */
668
669	amb	552	WriteFile(fd,&node,sizeof(Node));
670	amb	285
671			if(!((i+1)%10000))
672	amb	519	printf_middle("Writing Nodes: Nodes=%d",i+1);
673	amb	285	}
674
675	amb	556	/* Close the file */
676
677	amb	612	nodesx->fd=CloseFile(nodesx->fd);
678	amb	556
679	amb	553	/* Finish off the offset indexing and write them out */
680
681			for(;latlonbin<=(nodesx->latbins*nodesx->lonbins);latlonbin++)
682			offsets[latlonbin]=nodesx->number;
683
684			SeekFile(fd,sizeof(NodesFile));
685			WriteFile(fd,offsets,(nodesx->latbinsnodesx->lonbins+1)sizeof(index_t));
686
687	amb	461	/* Write out the header structure */
688
689			nodesfile.number=nodesx->number;
690			nodesfile.snumber=super_number;
691
692			nodesfile.latbins=nodesx->latbins;
693			nodesfile.lonbins=nodesx->lonbins;
694
695			nodesfile.latzero=nodesx->latzero;
696			nodesfile.lonzero=nodesx->lonzero;
697
698			SeekFile(fd,0);
699			WriteFile(fd,&nodesfile,sizeof(NodesFile));
700
701	amb	285	CloseFile(fd);
702
703			/* Print the final message */
704
705	amb	519	printf_last("Wrote Nodes: Nodes=%d",nodesx->number);
706	amb	285	}