trunk/src/nodesx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/nodesx.c,v 1.31 2009-09-03 17:51:03 amb Exp $

 Extented Node data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008,2009 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 "types.h"
#include "functions.h"
#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.h"
#include "segments.h"
#include "nodes.h"


/* Constants */

/*+ The array size increment for NodesX (UK is ~10.3M raw nodes, this is ~78 increments). +*/
#define INCREMENT_NODESX (128*1024)


/* Functions */

static int sort_by_id(NodeX **a,NodeX **b);
static int sort_by_lat_long(NodeX **a,NodeX **b);


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new node list.

  NodesX *NewNodeList Returns the node list.

  const char *dirname The name of the directory to save the temporary file into or NULL to use RAM.
  ++++++++++++++++++++++++++++++++++++++*/

NodesX *NewNodeList(const char *dirname)
{
 NodesX *nodesx;

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

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

 nodesx->row=-1;

 if(dirname)                    /* slim mode */
   {
    nodesx->filename=(char*)malloc(strlen(dirname)+24);
    if(*dirname)
       sprintf(nodesx->filename,"%s/nodes.%p.tmp",dirname,nodesx);
    else
       sprintf(nodesx->filename,"nodes.%p.tmp",nodesx);

    nodesx->fd=OpenFile(nodesx->filename);
   }

 return(nodesx);
}


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

  NodesX *nodesx The list to be freed.
  ++++++++++++++++++++++++++++++++++++++*/

void FreeNodeList(NodesX *nodesx)
{
 if(nodesx->filename)           /* slim mode */
   {
    UnmapFile(nodesx->filename,1);
    if(nodesx->xdata)
       free(nodesx->xdata);
   }
 else                           /* normal mode */
   {
    if(nodesx->xdata)
      {
       int i;
       for(i=0;i<=nodesx->row;i++)
          free(nodesx->xdata[i]);
       free(nodesx->xdata);
      }
   }

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

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

 free(nodesx);
}


/*++++++++++++++++++++++++++++++++++++++
  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;
 Nodes *nodes;
 index_t *offsets;
 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 latbins,lonbins,latlonbin;
 int super_number=0;

 assert(nodesx->gdata);         /* Must have gdata filled in => sorted geographically */
 assert(nodesx->ndata);         /* Must have ndata filled in => real nodes exist */
 assert(nodesx->idata);         /* Must have idata filled in => sorted by id */

 printf("Writing Nodes: Nodes=0");
 fflush(stdout);

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

 for(i=0;i<nodesx->number;i++)
   {
    if(nodesx->idata[i]->latitude<lat_min)
       lat_min=nodesx->idata[i]->latitude;
    if(nodesx->idata[i]->latitude>lat_max)
       lat_max=nodesx->idata[i]->latitude;
    if(nodesx->idata[i]->longitude<lon_min)
       lon_min=nodesx->idata[i]->longitude;
    if(nodesx->idata[i]->longitude>lon_max)
       lon_max=nodesx->idata[i]->longitude;

    if(nodesx->ndata[i].firstseg&NODE_SUPER)
       super_number++;
   }

 /* Work out the offsets */

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

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

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

 latlonbin=0;

 for(i=0;i<nodesx->number;i++)
   {
    ll_bin_t latbin=latlong_to_bin(nodesx->gdata[i]->latitude )-lat_min_bin;
    ll_bin_t lonbin=latlong_to_bin(nodesx->gdata[i]->longitude)-lon_min_bin;
    int llbin=lonbin*latbins+latbin;

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

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

 /* Fill in a Nodes structure with the offset of the real data in the file after
    the Node structure itself. */

 nodes=calloc(1,sizeof(Nodes));

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

 nodes->number=nodesx->number;
 nodes->snumber=super_number;

 nodes->latbins=latbins;
 nodes->lonbins=lonbins;

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

 nodes->data=NULL;

 nodes->offsets=(void*)sizeof(Nodes);
 nodes->nodes=(void*)(sizeof(Nodes)+(latbins*lonbins+1)*sizeof(index_t));

 /* Write out the Nodes structure and then the real data. */

 fd=OpenFile(filename);

 WriteFile(fd,nodes,sizeof(Nodes));

 WriteFile(fd,offsets,(latbins*lonbins+1)*sizeof(index_t));

 for(i=0;i<nodes->number;i++)
   {
    Node *node=&nodesx->ndata[IndexNodeX(nodesx,nodesx->gdata[i]->id)];

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

    if(!((i+1)%10000))
      {
       printf("\rWriting Nodes: Nodes=%d",i+1);
       fflush(stdout);
      }
   }

 printf("\rWrote Nodes: Nodes=%d  \n",nodes->number);
 fflush(stdout);

 CloseFile(fd);

 /* Free the fake Nodes */

 free(nodes);
 free(offsets);
}


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

  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;

 assert(nodesx->idata);         /* Must have idata filled in => sorted by id */

 /* 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]->id) /* Check key is not before start */
    return(NO_NODE);
 else if(id>nodesx->idata[end]->id)   /* Check key is not after end */
    return(NO_NODE);
 else
   {
    do
      {
       mid=(start+end)/2;                 /* Choose mid point */

       if(nodesx->idata[mid]->id<id)      /* Mid point is too low */
          start=mid+1;
       else if(nodesx->idata[mid]->id>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==id)      /* Start is correct */
       return(start);

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

 return(NO_NODE);
}


/*++++++++++++++++++++++++++++++++++++++
  Append a node to a newly created node list (unsorted).

  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.
  ++++++++++++++++++++++++++++++++++++++*/

void AppendNode(NodesX* nodesx,node_t id,double latitude,double longitude)
{
 assert(!nodesx->idata);        /* Must not have idata filled in => unsorted */

 if(nodesx->filename)           /* slim mode */
   {
    NodeX temp;

    temp.id=id;
    temp.latitude =radians_to_latlong(latitude);
    temp.longitude=radians_to_latlong(longitude);

    WriteFile(nodesx->fd,&temp,sizeof(temp));
   }
 else                           /* normal mode */
   {
    /* Check that the array has enough space. */

    if(nodesx->row==-1 || nodesx->col==INCREMENT_NODESX)
      {
       nodesx->row++;
       nodesx->col=0;

       if((nodesx->row%16)==0)
         {
          nodesx->xdata=(NodeX**)realloc((void*)nodesx->xdata,(nodesx->row+16)*sizeof(NodeX*));

          assert(nodesx->xdata); /* Check realloc() worked */
         }

       nodesx->xdata[nodesx->row]=(NodeX*)malloc(INCREMENT_NODESX*sizeof(NodeX));

       assert(nodesx->xdata[nodesx->row]); /* Check malloc() worked */
      }

    /* Insert the node */

    nodesx->xdata[nodesx->row][nodesx->col].id=id;
    nodesx->xdata[nodesx->row][nodesx->col].latitude =radians_to_latlong(latitude);
    nodesx->xdata[nodesx->row][nodesx->col].longitude=radians_to_latlong(longitude);

    nodesx->col++;
   }
}


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

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

void SortNodeList(NodesX* nodesx)
{
 index_t i;
 int duplicate;

 printf("Sorting Nodes");
 fflush(stdout);

 if(nodesx->filename && !nodesx->xdata) /* slim mode */
   {
    NodeX* address;
    size_t length;

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

    address=MapFile(nodesx->filename,&length);
    length/=sizeof(NodeX);

    nodesx->row=length/INCREMENT_NODESX;
    nodesx->col=length%INCREMENT_NODESX;

    nodesx->xdata=(NodeX**)malloc((nodesx->row+1)*sizeof(NodeX*));
    for(i=0;i<=nodesx->row;i++)
       nodesx->xdata[i]=&address[i*INCREMENT_NODESX];
   }

 assert(nodesx->xdata);         /* Must have xdata filled in => data exists */

 /* Allocate the array of pointers and sort them */

 if(!nodesx->idata)
   {
    nodesx->idata=(NodeX**)malloc((nodesx->row*INCREMENT_NODESX+nodesx->col)*sizeof(NodeX*));

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

    nodesx->number=0;

    for(i=0;i<(nodesx->row*INCREMENT_NODESX+nodesx->col);i++)
      {
       nodesx->idata[nodesx->number]=&nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX];
       nodesx->number++;
      }
   }

 /* Sort the nodes */

 do
   {
    qsort(nodesx->idata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_id);

    duplicate=0;

    for(i=1;i<nodesx->number;i++)
       if(nodesx->idata[i] && nodesx->idata[i]->id==nodesx->idata[i-1]->id)
         {
          nodesx->idata[i-1]=NULL;
          duplicate++;
         }

    while(!nodesx->idata[nodesx->number-1])
       nodesx->number--;

    if(duplicate)
      {
       printf(" - %d duplicates found; trying again.\nSorting Nodes",duplicate);
       fflush(stdout);
      }
   }
 while(duplicate);

 printf("\rSorted Nodes \n");
 fflush(stdout);

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

 if(!nodesx->super)
   {
    nodesx->super=(uint8_t*)malloc(nodesx->number*sizeof(uint8_t));
    memset(nodesx->super,0,nodesx->number*sizeof(uint8_t));
   }
}


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

  int sort_by_id Returns the comparison of the id fields.

  NodeX **a The first Node.

  NodeX **b The second Node.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_id(NodeX **a,NodeX **b)
{
 if(!*a)
    return(1);
 else if(!*b)
    return(-1);
 else
   {
    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);
   }
}


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

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

void SortNodeListGeographically(NodesX* nodesx)
{
 index_t i;

 assert(nodesx->idata);         /* Must have idata filled in => sorted by id */
 assert(!nodesx->gdata);        /* Must not have gdata filled in => unsorted geographically */

 printf("Sorting Nodes Geographically");
 fflush(stdout);

 /* Allocate the array of pointers and sort them */

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

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

 for(i=0;i<nodesx->number;i++)
    nodesx->gdata[i]=nodesx->idata[i];

 qsort(nodesx->gdata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_lat_long);

 printf("\rSorted Nodes Geographically \n");
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  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 Node.

  NodeX **b The second 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
       return(0);
   }
}


/*++++++++++++++++++++++++++++++++++++++
  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)
{
 index_t i;
 int highway=0,nothighway=0;

 assert(nodesx->idata);         /* Must have idata filled in => data sorted */

 printf("Checking: Nodes=0");
 fflush(stdout);

 for(i=0;i<nodesx->number;i++)
   {
    if(FindFirstSegmentX(segmentsx,nodesx->idata[i]->id))
       highway++;
    else
      {
       nodesx->idata[i]=NULL;
       nothighway++;
      }

    if(!((i+1)%10000))
      {
       printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
       fflush(stdout);
      }
   }

 printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d  \n",i,highway,nothighway);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Create the real node data.

  NodesX *nodesx The set of nodes to use.

  int iteration The final super-node iteration.
  ++++++++++++++++++++++++++++++++++++++*/

void CreateRealNodes(NodesX *nodesx,int iteration)
{
 index_t i;

 assert(nodesx->idata);         /* Must have idata filled in => sorted by id */
 assert(!nodesx->ndata);        /* Must not have ndata filled in => no real nodes */

 printf("Creating Real Nodes: Nodes=0");
 fflush(stdout);

 /* Allocate the memory */

 nodesx->ndata=(Node*)malloc(nodesx->number*sizeof(Node));

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

 /* Loop through and allocate. */

 for(i=0;i<nodesx->number;i++)
   {
    nodesx->ndata[i].latoffset=latlong_to_off(nodesx->idata[i]->latitude);
    nodesx->ndata[i].lonoffset=latlong_to_off(nodesx->idata[i]->longitude);

    nodesx->ndata[i].firstseg=SEGMENT(NO_SEGMENT);

    if(nodesx->super[i]==iteration)
       nodesx->ndata[i].firstseg|=NODE_SUPER;

    if(!((i+1)%10000))
      {
       printf("\rCreating Real Nodes: Nodes=%d",i+1);
       fflush(stdout);
      }
   }

 printf("\rCreating Real Nodes: Nodes=%d \n",nodesx->number);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Assign the segment indexes to the nodes.

  NodesX *nodesx The list of nodes to process.

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

void IndexNodes(NodesX *nodesx,SegmentsX *segmentsx)
{
 index_t i;

 assert(nodesx->idata);         /* Must have idata filled in => sorted */
 assert(nodesx->ndata);         /* Must have ndata filled in => real nodes exist */
 assert(segmentsx->n1data);     /* Must have n1data filled in => sorted */
 assert(segmentsx->sdata);      /* Must have sdata filled in => real segments exist */

 printf("Indexing Segments: Segments=0");
 fflush(stdout);

 /* Index the nodes */

 for(i=0;i<segmentsx->number;i++)
   {
    Node *node1=&nodesx->ndata[IndexNodeX(nodesx,segmentsx->n1data[i]->node1)];
    Node *node2=&nodesx->ndata[IndexNodeX(nodesx,segmentsx->n1data[i]->node2)];

    /* Check node1 */

    if(SEGMENT(node1->firstseg)==SEGMENT(NO_SEGMENT))
      {
       node1->firstseg^=SEGMENT(NO_SEGMENT);
       node1->firstseg|=i;
      }
    else
      {
       index_t index=SEGMENT(node1->firstseg);

       do
         {
          if(segmentsx->n1data[index]->node1==segmentsx->n1data[i]->node1)
            {
             index++;

             if(index>=segmentsx->number || segmentsx->n1data[index]->node1!=segmentsx->n1data[i]->node1)
                break;
            }
          else
            {
             if(segmentsx->sdata[index].next2==NO_NODE)
               {
                segmentsx->sdata[index].next2=i;
                break;
               }
             else
                index=segmentsx->sdata[index].next2;
            }
         }
       while(1);
      }

    /* Check node2 */

    if(SEGMENT(node2->firstseg)==SEGMENT(NO_SEGMENT))
      {
       node2->firstseg^=SEGMENT(NO_SEGMENT);
       node2->firstseg|=i;
      }
    else
      {
       index_t index=SEGMENT(node2->firstseg);

       do
         {
          if(segmentsx->n1data[index]->node1==segmentsx->n1data[i]->node2)
            {
             index++;

             if(index>=segmentsx->number || segmentsx->n1data[index]->node1!=segmentsx->n1data[i]->node2)
                break;
            }
          else
            {
             if(segmentsx->sdata[index].next2==NO_NODE)
               {
                segmentsx->sdata[index].next2=i;
                break;
               }
             else
                index=segmentsx->sdata[index].next2;
            }
         }
       while(1);
      }

    if(!((i+1)%10000))
      {
       printf("\rIndexing Segments: Segments=%d",i+1);
       fflush(stdout);
      }
   }

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