trunk/src/nodesx.c

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

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

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

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

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


#include <assert.h>
#include <stdlib.h>
#include <string.h>

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

#include "typesx.h"
#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.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 delete_pruned_and_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,(void*)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 the nodes by ID and index them */

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

 sortnodesx=nodesx;

 nodesx->number=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=%"Pindex_t" Duplicates=%"Pindex_t,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;

    return(1);
   }
 else
   {
    logerror("Node %"Pnode_t" is duplicated\n",nodex->id);

    return(0);
   }
}


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

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

void SortNodeListGeographically(NodesX *nodesx)
{
 int fd;
 index_t kept;

 /* Print the start message */

 printf_first("Sorting Nodes Geographically (Deleting Pruned)");

 /* 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 nodes geographically and index them */

 sortnodesx=nodesx;

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

 /* Close the files */

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

 /* Print the final message */

 printf_last("Sorted Nodes Geographically: Nodes=%"Pindex_t" Deleted=%"Pindex_t,kept,nodesx->number-kept);
 nodesx->number=kept;
}


/*++++++++++++++++++++++++++++++++++++++
  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)
{
 int a_pruned=IsPrunedNodeX(a);
 int b_pruned=IsPrunedNodeX(b);

 if(a_pruned && b_pruned)
    return(0);
 else if(a_pruned)
    return(1);
 else if(b_pruned)
    return(-1);
 else
   {
    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);
         }
      }
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Delete the pruned nodes and create the index between the sorted and unsorted nodes.

  int delete_pruned_and_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 delete_pruned_and_index_by_lat_long(NodeX *nodex,index_t index)
{
 if(IsPrunedNodeX(nodex))
    return(0);

 /* 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?(mid-1):mid;
       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;
 int fd;

 /* Print the start message */

 printf_first("Checking 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 */

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

    total++;

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

 nodesx->number=highway;

 /* Close the files */

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

 /* Free the now-unneeded index */

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

 /* Print the final message */

 printf_last("Checked Nodes: Nodes=%"Pindex_t" Highway=%"Pindex_t" not-Highway=%"Pindex_t,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;
 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;

 /* Print the start message */

 printf_first("Updating 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 */

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

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

 /* Close the files */

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

 /* Free the memory */

 free(nodesx->super);
 nodesx->super=NULL;

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

 /* Print the final message */

 printf_last("Updated Nodes: Nodes=%"Pindex_t,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,maxlatlonbins;
 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={0};
    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=%"Pindex_t,i+1);
   }

 /* Close the file */

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

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

 maxlatlonbins=nodesx->latbins*nodesx->lonbins;

 for(;latlonbin<=maxlatlonbins;latlonbin++)
    offsets[latlonbin]=nodesx->number;

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

 free(offsets);

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