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
      {
#ifdef REGRESSION_TESTING
       // Need this for regression testing because filesort_heapsort() is not order
       // preserving like qsort() is (or was when tested).

       index_t a_id=a->id;
       index_t b_id=b->id;

       if(a_id<b_id)
          return(-1);
       else if(a_id>b_id)
          return(1);
       else
#endif
          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(!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);

 /* Free the unneeded memory */

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

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

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