trunk/src/nodesx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/nodesx.c,v 1.10 2009-06-03 17:34:49 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 <string.h>
#include <stdio.h>
#include <math.h>

#include "types.h"
#include "functions.h"
#include "nodesx.h"
#include "segmentsx.h"


/* Constants */

/*+ The array size increment for nodes - expect ~8,000,000 nodes. +*/
#define INCREMENT_NODES 1024*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.
  ++++++++++++++++++++++++++++++++++++++*/

NodesX *NewNodeList(void)
{
 NodesX *nodesx;

 nodesx=(NodesX*)malloc(sizeof(NodesX));

 nodesx->alloced=INCREMENT_NODES;
 nodesx->xnumber=0;
 nodesx->sorted=0;

 nodesx->xdata=(NodeX*)malloc(nodesx->alloced*sizeof(NodeX));
 nodesx->gdata=NULL;
 nodesx->idata=NULL;

 return(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)
{
 int i;
 int fd;
 Nodes *nodes=calloc(1,sizeof(Nodes));
 index_t *offsets;
 int32_t lat_min,lat_max,lon_min,lon_max;
 int latbins,lonbins,latlonbin;

 assert(nodesx->sorted);        /* Must be sorted */

 /* Work out the offsets */

 lat_min=lat_long_to_bin(nodesx->lat_min);
 lon_min=lat_long_to_bin(nodesx->lon_min);
 lat_max=lat_long_to_bin(nodesx->lat_max);
 lon_max=lat_long_to_bin(nodesx->lon_max);

 latbins=(lat_max-lat_min)+1;
 lonbins=(lon_max-lon_min)+1;

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

 latlonbin=0;

 for(i=0;i<nodesx->number;i++)
   {
    int32_t latbin=lat_long_to_bin(nodesx->gdata[i]->latitude )-lat_min;
    int32_t lonbin=lat_long_to_bin(nodesx->gdata[i]->longitude)-lon_min;
    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->number=nodesx->number;

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

 nodes->latzero=lat_min;
 nodes->lonzero=lon_min;

 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<nodesx->number;i++)
   {
    WriteFile(fd,&nodesx->gdata[i]->node,sizeof(Node));

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

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

 CloseFile(fd);

 /* Free the fake Nodes */

 free(nodes);
 free(offsets);
}


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

  NodeX *FindNodeX Returns the extended node with the specified id.

  NodesX* nodesx The set of nodes to process.

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

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

 assert(nodesx->sorted);        /* Must be sorted */

 /* 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 */
    goto error;
 else if(id<nodesx->idata[start]->id) /* Check key is not before start */
    goto error;
 else if(id>nodesx->idata[end]->id)   /* Check key is not after end */
    goto error;
 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(nodesx->idata[mid]);
      }
    while((end-start)>1);

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

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

 error:

 fprintf(stderr,"Error: Node %d is referenced but does not exist in the dataset.\n",id);
 exit(1);

 return(NULL);
}


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

  Node *AppendNode Return a pointer to the new node.

  NodesX* nodesx The set of nodes to process.

  node_t id The node identification.

  float latitude The latitude of the node.

  float longitude The longitude of the node.
  ++++++++++++++++++++++++++++++++++++++*/

Node *AppendNode(NodesX* nodesx,node_t id,float latitude,float longitude)
{
 /* Check that the array has enough space. */

 if(nodesx->xnumber==nodesx->alloced)
   {
    nodesx->alloced+=INCREMENT_NODES;

    nodesx->xdata=(NodeX*)realloc((void*)nodesx->xdata,nodesx->alloced*sizeof(NodeX));
   }

 /* Insert the node */

 nodesx->xdata[nodesx->xnumber].id=id;
 nodesx->xdata[nodesx->xnumber].super=0;
 nodesx->xdata[nodesx->xnumber].latitude =floorf(latitude *LAT_LONG_SCALE)/LAT_LONG_SCALE;
 nodesx->xdata[nodesx->xnumber].longitude=floorf(longitude*LAT_LONG_SCALE)/LAT_LONG_SCALE;

 memset(&nodesx->xdata[nodesx->xnumber].node,0,sizeof(Node));

 nodesx->xnumber++;

 nodesx->sorted=0;

 return(&nodesx->xdata[nodesx->xnumber-1].node);
}


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

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

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

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

 /* Allocate the arrays of pointers */

 if(nodesx->sorted)
   {
    nodesx->gdata=realloc(nodesx->gdata,nodesx->xnumber*sizeof(NodeX*));
    nodesx->idata=realloc(nodesx->idata,nodesx->xnumber*sizeof(NodeX*));
   }
 else
   {
    nodesx->gdata=malloc(nodesx->xnumber*sizeof(NodeX*));
    nodesx->idata=malloc(nodesx->xnumber*sizeof(NodeX*));
   }

 sort_again:

 nodesx->number=0;

 for(i=0;i<nodesx->xnumber;i++)
    if(nodesx->xdata[i].id!=NO_NODE)
      {
       nodesx->gdata[nodesx->number]=&nodesx->xdata[i];
       nodesx->idata[nodesx->number]=&nodesx->xdata[i];
       nodesx->number++;
      }

 nodesx->sorted=1;

 /* Sort by id */

 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]->id==nodesx->idata[i-1]->id &&
       nodesx->idata[i]->id!=NO_NODE)
      {
       nodesx->idata[i-1]->id=NO_NODE;
       duplicate++;
      }
   }

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

 /* Sort geographically */

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

 nodesx->lat_min=2;
 nodesx->lat_max=-2;
 nodesx->lon_min=4;
 nodesx->lon_max=-4;

 for(i=0;i<nodesx->number;i++)
   {
    int32_t lat=(int32_t)(nodesx->gdata[i]->latitude *LAT_LONG_SCALE);
    int32_t lon=(int32_t)(nodesx->gdata[i]->longitude*LAT_LONG_SCALE);

    nodesx->gdata[i]->node.latoffset=lat%LAT_LONG_BIN;
    nodesx->gdata[i]->node.lonoffset=lon%LAT_LONG_BIN;

    if(nodesx->gdata[i]->latitude<nodesx->lat_min)
       nodesx->lat_min=nodesx->gdata[i]->latitude;
    if(nodesx->gdata[i]->latitude>nodesx->lat_max)
       nodesx->lat_max=nodesx->gdata[i]->latitude;
    if(nodesx->gdata[i]->longitude<nodesx->lon_min)
       nodesx->lon_min=nodesx->gdata[i]->longitude;
    if(nodesx->gdata[i]->longitude>nodesx->lon_max)
       nodesx->lon_max=nodesx->gdata[i]->longitude;
   }

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


/*++++++++++++++++++++++++++++++++++++++
  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)
{
 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 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)
{
 int32_t a_lon=lat_long_to_bin((*a)->longitude);
 int32_t b_lon=lat_long_to_bin((*b)->longitude);

 if(a_lon<b_lon)
    return(-1);
 else if(a_lon>b_lon)
    return(1);
 else
   {
    int32_t a_lat=lat_long_to_bin((*a)->latitude);
    int32_t b_lat=lat_long_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)
{
 int i;
 int highway=0,nothighway=0;

 assert(!nodesx->sorted);     /* Must not be sorted */

 for(i=0;i<nodesx->xnumber;i++)
   {
    if(FindFirstSegmentX(segmentsx,nodesx->xdata[i].id))
       highway++;
    else
      {
       nodesx->xdata[i].id=NO_NODE;
       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",nodesx->xnumber,highway,nothighway);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Mark super nodes.

  NodesX* nodesx The set of nodes to process.

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

void MarkSuperNodes(NodesX *nodesx,int iteration)
{
 int i,nnodes=0;;

 assert(nodesx->sorted);      /* Must be sorted */

 for(i=0;i<nodesx->number;i++)
   {
    if(nodesx->gdata[i]->super==iteration)
      {
       nodesx->gdata[i]->node.firstseg=SEGMENT(NO_SEGMENT)|SUPER_FLAG;
       nnodes++;
      }
    else
       nodesx->gdata[i]->node.firstseg=SEGMENT(NO_SEGMENT);

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

 printf("\rMarked Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
 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)
{
 int i;

 assert(nodesx->sorted);        /* Must be sorted */
 assert(segmentsx->sorted);     /* Must be sorted */

 /* Index the nodes */

 for(i=0;i<segmentsx->number;i++)
   {
    NodeX *node1=FindNodeX(nodesx,segmentsx->sdata[i]->node1);
    NodeX *node2=FindNodeX(nodesx,segmentsx->sdata[i]->node2);

    /* Check node1 */

    if(SEGMENT(node1->node.firstseg)==SEGMENT(NO_SEGMENT))
      {
       node1->node.firstseg^=SEGMENT(NO_SEGMENT);
       node1->node.firstseg|=i;
      }
    else
      {
       SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(node1->node.firstseg));

       do
         {
          if((*segmentx)->node1==segmentsx->sdata[i]->node1)
            {
             segmentx++;

             if((*segmentx)->node1!=segmentsx->sdata[i]->node1 || (segmentx-segmentsx->sdata)>=segmentsx->number)
                segmentx=NULL;
            }
          else
            {
             if((*segmentx)->segment.next2==NO_NODE)
               {
                (*segmentx)->segment.next2=i;
                segmentx=NULL;
               }
             else
                segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
            }
         }
       while(segmentx);
      }

    /* Check node2 */

    if(SEGMENT(node2->node.firstseg)==SEGMENT(NO_SEGMENT))
      {
       node2->node.firstseg^=SEGMENT(NO_SEGMENT);
       node2->node.firstseg|=i;
      }
    else
      {
       SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(node2->node.firstseg));

       do
         {
          if((*segmentx)->node1==segmentsx->sdata[i]->node2)
            {
             segmentx++;

             if((*segmentx)->node1!=segmentsx->sdata[i]->node2 || (segmentx-segmentsx->sdata)>=segmentsx->number)
                segmentx=NULL;
            }
          else
            {
             if((*segmentx)->segment.next2==NO_NODE)
               {
                (*segmentx)->segment.next2=i;
                segmentx=NULL;
               }
             else
                segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
            }
         }
       while(segmentx);
      }

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

 printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
 fflush(stdout);
}
1	amb	110	/***************************************
2	amb	182	$Header: /home/amb/CVS/routino/src/nodesx.c,v 1.10 2009-06-03 17:34:49 amb Exp $
3	amb	110
4			Extented Node data type functions.
5	amb	151
6			Part of the Routino routing software.
7	amb	110	****************/ /****************
8	amb	151	This file Copyright 2008,2009 Andrew M. Bishop
9	amb	110
10	amb	151	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	amb	110	***************************************/
23
24
25			#include <assert.h>
26			#include <stdlib.h>
27			#include <string.h>
28			#include <stdio.h>
29	amb	118	#include <math.h>
30	amb	110
31			#include "types.h"
32			#include "functions.h"
33			#include "nodesx.h"
34			#include "segmentsx.h"
35
36
37			/* Constants */
38
39			/+ The array size increment for nodes - expect ~8,000,000 nodes. +/
40			#define INCREMENT_NODES 1024*1024
41
42
43			/* Functions */
44
45			static int sort_by_id(NodeX a,NodeX b);
46			static int sort_by_lat_long(NodeX a,NodeX b);
47
48
49			/*++++++++++++++++++++++++++++++++++++++
50			Allocate a new node list.
51
52			NodesX *NewNodeList Returns the node list.
53			++++++++++++++++++++++++++++++++++++++*/
54
55			NodesX *NewNodeList(void)
56			{
57			NodesX *nodesx;
58
59			nodesx=(NodesX*)malloc(sizeof(NodesX));
60
61			nodesx->alloced=INCREMENT_NODES;
62			nodesx->xnumber=0;
63			nodesx->sorted=0;
64
65			nodesx->xdata=(NodeX)malloc(nodesx->allocedsizeof(NodeX));
66			nodesx->gdata=NULL;
67			nodesx->idata=NULL;
68
69			return(nodesx);
70			}
71
72
73			/*++++++++++++++++++++++++++++++++++++++
74			Save the node list to a file.
75
76			NodesX* nodesx The set of nodes to save.
77
78			const char *filename The name of the file to save.
79			++++++++++++++++++++++++++++++++++++++*/
80
81			void SaveNodeList(NodesX* nodesx,const char *filename)
82			{
83			int i;
84			int fd;
85			Nodes *nodes=calloc(1,sizeof(Nodes));
86			index_t *offsets;
87	amb	118	int32_t lat_min,lat_max,lon_min,lon_max;
88	amb	110	int latbins,lonbins,latlonbin;
89
90			assert(nodesx->sorted); /* Must be sorted */
91
92	amb	118	/* Work out the offsets */
93	amb	110
94	amb	118	lat_min=lat_long_to_bin(nodesx->lat_min);
95			lon_min=lat_long_to_bin(nodesx->lon_min);
96			lat_max=lat_long_to_bin(nodesx->lat_max);
97			lon_max=lat_long_to_bin(nodesx->lon_max);
98	amb	110
99	amb	118	latbins=(lat_max-lat_min)+1;
100			lonbins=(lon_max-lon_min)+1;
101	amb	110
102			offsets=malloc((latbinslonbins+1)sizeof(index_t));
103
104			latlonbin=0;
105
106			for(i=0;i<nodesx->number;i++)
107			{
108	amb	118	int32_t latbin=lat_long_to_bin(nodesx->gdata[i]->latitude )-lat_min;
109			int32_t lonbin=lat_long_to_bin(nodesx->gdata[i]->longitude)-lon_min;
110	amb	110	int llbin=lonbin*latbins+latbin;
111
112			for(;latlonbin<=llbin;latlonbin++)
113			offsets[latlonbin]=i;
114			}
115
116			for(;latlonbin<=(latbins*lonbins);latlonbin++)
117			offsets[latlonbin]=nodesx->number;
118
119			/* Fill in a Nodes structure with the offset of the real data in the file after
120			the Node structure itself. */
121
122			nodes->number=nodesx->number;
123
124			nodes->latbins=latbins;
125			nodes->lonbins=lonbins;
126
127			nodes->latzero=lat_min;
128			nodes->lonzero=lon_min;
129
130			nodes->data=NULL;
131			nodes->offsets=(void*)sizeof(Nodes);
132			nodes->nodes=(void)sizeof(Nodes)+(latbinslonbins+1)*sizeof(index_t);
133
134			/* Write out the Nodes structure and then the real data. */
135
136			fd=OpenFile(filename);
137
138			WriteFile(fd,nodes,sizeof(Nodes));
139
140			WriteFile(fd,offsets,(latbinslonbins+1)sizeof(index_t));
141
142			for(i=0;i<nodesx->number;i++)
143	amb	132	{
144	amb	110	WriteFile(fd,&nodesx->gdata[i]->node,sizeof(Node));
145
146	amb	132	if(!((i+1)%10000))
147			{
148			printf("\rWriting Nodes: Nodes=%d",i+1);
149			fflush(stdout);
150			}
151			}
152
153			printf("\rWrote Nodes: Nodes=%d \n",nodesx->number);
154			fflush(stdout);
155
156	amb	110	CloseFile(fd);
157
158			/* Free the fake Nodes */
159
160			free(nodes);
161			free(offsets);
162			}
163
164
165			/*++++++++++++++++++++++++++++++++++++++
166			Find a particular node.
167
168			NodeX *FindNodeX Returns the extended node with the specified id.
169
170			NodesX* nodesx The set of nodes to process.
171
172			node_t id The node id to look for.
173			++++++++++++++++++++++++++++++++++++++*/
174
175			NodeX FindNodeX(NodesX nodesx,node_t id)
176			{
177			int start=0;
178			int end=nodesx->number-1;
179			int mid;
180
181			assert(nodesx->sorted); /* Must be sorted */
182
183			/* Binary search - search key exact match only is required.
184			*
185			* # <- start \| Check mid and move start or end if it doesn't match
186			* # \|
187			* # \| Since an exact match is wanted we can set end=mid-1
188			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
189			* # \|
190			* # \| Eventually either end=start or end=start+1 and one of
191			* # <- end \| start or end is the wanted one.
192			*/
193
194			if(end<start) /* There are no nodes */
195	amb	182	goto error;
196	amb	110	else if(id<nodesx->idata[start]->id) /* Check key is not before start */
197	amb	182	goto error;
198	amb	110	else if(id>nodesx->idata[end]->id) /* Check key is not after end */
199	amb	182	goto error;
200	amb	110	else
201			{
202			do
203			{
204			mid=(start+end)/2; /* Choose mid point */
205
206			if(nodesx->idata[mid]->id<id) /* Mid point is too low */
207			start=mid+1;
208			else if(nodesx->idata[mid]->id>id) /* Mid point is too high */
209			end=mid-1;
210			else /* Mid point is correct */
211			return(nodesx->idata[mid]);
212			}
213			while((end-start)>1);
214
215			if(nodesx->idata[start]->id==id) /* Start is correct */
216			return(nodesx->idata[start]);
217
218			if(nodesx->idata[end]->id==id) /* End is correct */
219			return(nodesx->idata[end]);
220			}
221
222	amb	182	error:
223
224			fprintf(stderr,"Error: Node %d is referenced but does not exist in the dataset.\n",id);
225			exit(1);
226
227	amb	110	return(NULL);
228			}
229
230
231			/*++++++++++++++++++++++++++++++++++++++
232			Append a node to a newly created node list (unsorted).
233
234			Node *AppendNode Return a pointer to the new node.
235
236			NodesX* nodesx The set of nodes to process.
237
238			node_t id The node identification.
239
240			float latitude The latitude of the node.
241
242			float longitude The longitude of the node.
243			++++++++++++++++++++++++++++++++++++++*/
244
245			Node AppendNode(NodesX nodesx,node_t id,float latitude,float longitude)
246			{
247			/* Check that the array has enough space. */
248
249			if(nodesx->xnumber==nodesx->alloced)
250			{
251			nodesx->alloced+=INCREMENT_NODES;
252
253			nodesx->xdata=(NodeX)realloc((void)nodesx->xdata,nodesx->alloced*sizeof(NodeX));
254			}
255
256			/* Insert the node */
257
258			nodesx->xdata[nodesx->xnumber].id=id;
259			nodesx->xdata[nodesx->xnumber].super=0;
260	amb	133	nodesx->xdata[nodesx->xnumber].latitude =floorf(latitude *LAT_LONG_SCALE)/LAT_LONG_SCALE;
261			nodesx->xdata[nodesx->xnumber].longitude=floorf(longitude*LAT_LONG_SCALE)/LAT_LONG_SCALE;
262	amb	110
263			memset(&nodesx->xdata[nodesx->xnumber].node,0,sizeof(Node));
264
265			nodesx->xnumber++;
266
267			nodesx->sorted=0;
268
269			return(&nodesx->xdata[nodesx->xnumber-1].node);
270			}
271
272
273			/*++++++++++++++++++++++++++++++++++++++
274			Sort the node list.
275
276			NodesX* nodesx The set of nodes to process.
277			++++++++++++++++++++++++++++++++++++++*/
278
279			void SortNodeList(NodesX* nodesx)
280			{
281			int i;
282	amb	144	int duplicate;
283	amb	110
284	amb	132	printf("Sorting Nodes"); fflush(stdout);
285
286	amb	110	/* Allocate the arrays of pointers */
287
288			if(nodesx->sorted)
289			{
290			nodesx->gdata=realloc(nodesx->gdata,nodesx->xnumbersizeof(NodeX));
291			nodesx->idata=realloc(nodesx->idata,nodesx->xnumbersizeof(NodeX));
292			}
293			else
294			{
295			nodesx->gdata=malloc(nodesx->xnumbersizeof(NodeX));
296			nodesx->idata=malloc(nodesx->xnumbersizeof(NodeX));
297			}
298
299	amb	144	sort_again:
300
301	amb	110	nodesx->number=0;
302
303			for(i=0;i<nodesx->xnumber;i++)
304	amb	176	if(nodesx->xdata[i].id!=NO_NODE)
305	amb	110	{
306			nodesx->gdata[nodesx->number]=&nodesx->xdata[i];
307			nodesx->idata[nodesx->number]=&nodesx->xdata[i];
308			nodesx->number++;
309			}
310
311	amb	144	nodesx->sorted=1;
312
313			/* Sort by id */
314
315			qsort(nodesx->idata,nodesx->number,sizeof(NodeX),(int ()(const void,const void))sort_by_id);
316
317			duplicate=0;
318
319			for(i=1;i<nodesx->number;i++)
320			{
321			if(nodesx->idata[i]->id==nodesx->idata[i-1]->id &&
322	amb	176	nodesx->idata[i]->id!=NO_NODE)
323	amb	144	{
324	amb	176	nodesx->idata[i-1]->id=NO_NODE;
325	amb	144	duplicate++;
326			}
327			}
328
329			if(duplicate)
330			{
331			printf(" - %d duplicates found; trying again.\nSorting Nodes",duplicate); fflush(stdout);
332			goto sort_again;
333			}
334
335	amb	110	/* Sort geographically */
336
337			qsort(nodesx->gdata,nodesx->number,sizeof(NodeX),(int ()(const void,const void))sort_by_lat_long);
338
339	amb	121	nodesx->lat_min=2;
340			nodesx->lat_max=-2;
341			nodesx->lon_min=4;
342			nodesx->lon_max=-4;
343	amb	110
344			for(i=0;i<nodesx->number;i++)
345			{
346	amb	118	int32_t lat=(int32_t)(nodesx->gdata[i]->latitude *LAT_LONG_SCALE);
347	amb	110	int32_t lon=(int32_t)(nodesx->gdata[i]->longitude*LAT_LONG_SCALE);
348
349			nodesx->gdata[i]->node.latoffset=lat%LAT_LONG_BIN;
350			nodesx->gdata[i]->node.lonoffset=lon%LAT_LONG_BIN;
351
352			if(nodesx->gdata[i]->latitude<nodesx->lat_min)
353			nodesx->lat_min=nodesx->gdata[i]->latitude;
354			if(nodesx->gdata[i]->latitude>nodesx->lat_max)
355			nodesx->lat_max=nodesx->gdata[i]->latitude;
356			if(nodesx->gdata[i]->longitude<nodesx->lon_min)
357			nodesx->lon_min=nodesx->gdata[i]->longitude;
358			if(nodesx->gdata[i]->longitude>nodesx->lon_max)
359			nodesx->lon_max=nodesx->gdata[i]->longitude;
360			}
361
362	amb	132	printf("\rSorted Nodes \n"); fflush(stdout);
363	amb	110	}
364
365
366			/*++++++++++++++++++++++++++++++++++++++
367			Sort the nodes into id order.
368
369			int sort_by_id Returns the comparison of the id fields.
370
371			NodeX **a The first Node.
372
373			NodeX **b The second Node.
374			++++++++++++++++++++++++++++++++++++++*/
375
376			static int sort_by_id(NodeX a,NodeX b)
377			{
378			node_t a_id=(*a)->id;
379			node_t b_id=(*b)->id;
380
381			if(a_id<b_id)
382			return(-1);
383	amb	144	else if(a_id>b_id)
384			return(1);
385	amb	110	else
386	amb	144	return(0);
387	amb	110	}
388
389
390			/*++++++++++++++++++++++++++++++++++++++
391			Sort the nodes into latitude and longitude order.
392
393			int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
394
395			NodeX **a The first Node.
396
397			NodeX **b The second Node.
398			++++++++++++++++++++++++++++++++++++++*/
399
400			static int sort_by_lat_long(NodeX a,NodeX b)
401			{
402	amb	118	int32_t a_lon=lat_long_to_bin((*a)->longitude);
403			int32_t b_lon=lat_long_to_bin((*b)->longitude);
404	amb	110
405			if(a_lon<b_lon)
406			return(-1);
407			else if(a_lon>b_lon)
408			return(1);
409			else
410			{
411	amb	118	int32_t a_lat=lat_long_to_bin((*a)->latitude);
412			int32_t b_lat=lat_long_to_bin((*b)->latitude);
413	amb	110
414			if(a_lat<b_lat)
415			return(-1);
416			else if(a_lat>b_lat)
417			return(1);
418			else
419			return(0);
420			}
421			}
422
423
424			/*++++++++++++++++++++++++++++++++++++++
425			Remove any nodes that are not part of a highway.
426
427			NodesX *nodesx The complete node list.
428
429			SegmentsX *segmentsx The list of segments.
430			++++++++++++++++++++++++++++++++++++++*/
431
432			void RemoveNonHighwayNodes(NodesX nodesx,SegmentsX segmentsx)
433			{
434			int i;
435			int highway=0,nothighway=0;
436
437			assert(!nodesx->sorted); /* Must not be sorted */
438
439			for(i=0;i<nodesx->xnumber;i++)
440			{
441			if(FindFirstSegmentX(segmentsx,nodesx->xdata[i].id))
442			highway++;
443			else
444			{
445	amb	176	nodesx->xdata[i].id=NO_NODE;
446	amb	110	nothighway++;
447			}
448
449			if(!((i+1)%10000))
450			{
451			printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
452			fflush(stdout);
453			}
454			}
455
456			printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d \n",nodesx->xnumber,highway,nothighway);
457			fflush(stdout);
458			}
459
460
461			/*++++++++++++++++++++++++++++++++++++++
462			Mark super nodes.
463
464			NodesX* nodesx The set of nodes to process.
465
466			int iteration The final super-node / super-segment iteration number.
467			++++++++++++++++++++++++++++++++++++++*/
468
469			void MarkSuperNodes(NodesX *nodesx,int iteration)
470			{
471			int i,nnodes=0;;
472
473			assert(nodesx->sorted); /* Must be sorted */
474
475			for(i=0;i<nodesx->number;i++)
476			{
477			if(nodesx->gdata[i]->super==iteration)
478			{
479	amb	176	nodesx->gdata[i]->node.firstseg=SEGMENT(NO_SEGMENT)\|SUPER_FLAG;
480	amb	110	nnodes++;
481			}
482			else
483	amb	176	nodesx->gdata[i]->node.firstseg=SEGMENT(NO_SEGMENT);
484	amb	110
485			if(!((i+1)%10000))
486			{
487			printf("\rMarking Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
488			fflush(stdout);
489			}
490			}
491
492			printf("\rMarked Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
493			fflush(stdout);
494			}
495
496
497			/*++++++++++++++++++++++++++++++++++++++
498			Assign the segment indexes to the nodes.
499
500			NodesX *nodesx The list of nodes to process.
501
502			SegmentsX* segmentsx The set of segments to use.
503			++++++++++++++++++++++++++++++++++++++*/
504
505			void IndexNodes(NodesX nodesx,SegmentsX segmentsx)
506			{
507			int i;
508
509			assert(nodesx->sorted); /* Must be sorted */
510			assert(segmentsx->sorted); /* Must be sorted */
511
512			/* Index the nodes */
513
514			for(i=0;i<segmentsx->number;i++)
515			{
516			NodeX *node1=FindNodeX(nodesx,segmentsx->sdata[i]->node1);
517			NodeX *node2=FindNodeX(nodesx,segmentsx->sdata[i]->node2);
518
519			/* Check node1 */
520
521	amb	176	if(SEGMENT(node1->node.firstseg)==SEGMENT(NO_SEGMENT))
522	amb	110	{
523	amb	176	node1->node.firstseg^=SEGMENT(NO_SEGMENT);
524	amb	110	node1->node.firstseg\|=i;
525			}
526			else
527			{
528	amb	128	SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(node1->node.firstseg));
529	amb	110
530			do
531			{
532	amb	128	if((*segmentx)->node1==segmentsx->sdata[i]->node1)
533	amb	110	{
534	amb	128	segmentx++;
535
536			if((*segmentx)->node1!=segmentsx->sdata[i]->node1 \|\| (segmentx-segmentsx->sdata)>=segmentsx->number)
537	amb	110	segmentx=NULL;
538			}
539			else
540			{
541	amb	176	if((*segmentx)->segment.next2==NO_NODE)
542	amb	110	{
543	amb	128	(*segmentx)->segment.next2=i;
544	amb	110	segmentx=NULL;
545			}
546			else
547	amb	128	segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
548	amb	110	}
549			}
550			while(segmentx);
551			}
552
553			/* Check node2 */
554
555	amb	176	if(SEGMENT(node2->node.firstseg)==SEGMENT(NO_SEGMENT))
556	amb	110	{
557	amb	176	node2->node.firstseg^=SEGMENT(NO_SEGMENT);
558	amb	110	node2->node.firstseg\|=i;
559			}
560			else
561			{
562	amb	128	SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(node2->node.firstseg));
563	amb	110
564			do
565			{
566	amb	128	if((*segmentx)->node1==segmentsx->sdata[i]->node2)
567	amb	110	{
568	amb	128	segmentx++;
569
570			if((*segmentx)->node1!=segmentsx->sdata[i]->node2 \|\| (segmentx-segmentsx->sdata)>=segmentsx->number)
571	amb	110	segmentx=NULL;
572			}
573			else
574			{
575	amb	176	if((*segmentx)->segment.next2==NO_NODE)
576	amb	110	{
577	amb	128	(*segmentx)->segment.next2=i;
578	amb	110	segmentx=NULL;
579			}
580			else
581	amb	128	segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
582	amb	110	}
583			}
584			while(segmentx);
585			}
586
587			if(!((i+1)%10000))
588			{
589			printf("\rIndexing Segments: Segments=%d",i+1);
590			fflush(stdout);
591			}
592			}
593
594			printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
595			fflush(stdout);
596			}