trunk/src/nodesx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/nodesx.c,v 1.11 2009-06-13 12:43:02 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 */
    return(NULL);
 else if(id<nodesx->idata[start]->id) /* Check key is not before start */
    return(NULL);
 else if(id>nodesx->idata[end]->id)   /* Check key is not after end */
    return(NULL);
 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]);
   }

 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	194	$Header: /home/amb/CVS/routino/src/nodesx.c,v 1.11 2009-06-13 12:43:02 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	194	return(NULL);
196	amb	110	else if(id<nodesx->idata[start]->id) /* Check key is not before start */
197	amb	194	return(NULL);
198	amb	110	else if(id>nodesx->idata[end]->id) /* Check key is not after end */
199	amb	194	return(NULL);
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			return(NULL);
223			}
224
225
226			/*++++++++++++++++++++++++++++++++++++++
227			Append a node to a newly created node list (unsorted).
228
229			Node *AppendNode Return a pointer to the new node.
230
231			NodesX* nodesx The set of nodes to process.
232
233			node_t id The node identification.
234
235			float latitude The latitude of the node.
236
237			float longitude The longitude of the node.
238			++++++++++++++++++++++++++++++++++++++*/
239
240			Node AppendNode(NodesX nodesx,node_t id,float latitude,float longitude)
241			{
242			/* Check that the array has enough space. */
243
244			if(nodesx->xnumber==nodesx->alloced)
245			{
246			nodesx->alloced+=INCREMENT_NODES;
247
248			nodesx->xdata=(NodeX)realloc((void)nodesx->xdata,nodesx->alloced*sizeof(NodeX));
249			}
250
251			/* Insert the node */
252
253			nodesx->xdata[nodesx->xnumber].id=id;
254			nodesx->xdata[nodesx->xnumber].super=0;
255	amb	133	nodesx->xdata[nodesx->xnumber].latitude =floorf(latitude *LAT_LONG_SCALE)/LAT_LONG_SCALE;
256			nodesx->xdata[nodesx->xnumber].longitude=floorf(longitude*LAT_LONG_SCALE)/LAT_LONG_SCALE;
257	amb	110
258			memset(&nodesx->xdata[nodesx->xnumber].node,0,sizeof(Node));
259
260			nodesx->xnumber++;
261
262			nodesx->sorted=0;
263
264			return(&nodesx->xdata[nodesx->xnumber-1].node);
265			}
266
267
268			/*++++++++++++++++++++++++++++++++++++++
269			Sort the node list.
270
271			NodesX* nodesx The set of nodes to process.
272			++++++++++++++++++++++++++++++++++++++*/
273
274			void SortNodeList(NodesX* nodesx)
275			{
276			int i;
277	amb	144	int duplicate;
278	amb	110
279	amb	132	printf("Sorting Nodes"); fflush(stdout);
280
281	amb	110	/* Allocate the arrays of pointers */
282
283			if(nodesx->sorted)
284			{
285			nodesx->gdata=realloc(nodesx->gdata,nodesx->xnumbersizeof(NodeX));
286			nodesx->idata=realloc(nodesx->idata,nodesx->xnumbersizeof(NodeX));
287			}
288			else
289			{
290			nodesx->gdata=malloc(nodesx->xnumbersizeof(NodeX));
291			nodesx->idata=malloc(nodesx->xnumbersizeof(NodeX));
292			}
293
294	amb	144	sort_again:
295
296	amb	110	nodesx->number=0;
297
298			for(i=0;i<nodesx->xnumber;i++)
299	amb	176	if(nodesx->xdata[i].id!=NO_NODE)
300	amb	110	{
301			nodesx->gdata[nodesx->number]=&nodesx->xdata[i];
302			nodesx->idata[nodesx->number]=&nodesx->xdata[i];
303			nodesx->number++;
304			}
305
306	amb	144	nodesx->sorted=1;
307
308			/* Sort by id */
309
310			qsort(nodesx->idata,nodesx->number,sizeof(NodeX),(int ()(const void,const void))sort_by_id);
311
312			duplicate=0;
313
314			for(i=1;i<nodesx->number;i++)
315			{
316			if(nodesx->idata[i]->id==nodesx->idata[i-1]->id &&
317	amb	176	nodesx->idata[i]->id!=NO_NODE)
318	amb	144	{
319	amb	176	nodesx->idata[i-1]->id=NO_NODE;
320	amb	144	duplicate++;
321			}
322			}
323
324			if(duplicate)
325			{
326			printf(" - %d duplicates found; trying again.\nSorting Nodes",duplicate); fflush(stdout);
327			goto sort_again;
328			}
329
330	amb	110	/* Sort geographically */
331
332			qsort(nodesx->gdata,nodesx->number,sizeof(NodeX),(int ()(const void,const void))sort_by_lat_long);
333
334	amb	121	nodesx->lat_min=2;
335			nodesx->lat_max=-2;
336			nodesx->lon_min=4;
337			nodesx->lon_max=-4;
338	amb	110
339			for(i=0;i<nodesx->number;i++)
340			{
341	amb	118	int32_t lat=(int32_t)(nodesx->gdata[i]->latitude *LAT_LONG_SCALE);
342	amb	110	int32_t lon=(int32_t)(nodesx->gdata[i]->longitude*LAT_LONG_SCALE);
343
344			nodesx->gdata[i]->node.latoffset=lat%LAT_LONG_BIN;
345			nodesx->gdata[i]->node.lonoffset=lon%LAT_LONG_BIN;
346
347			if(nodesx->gdata[i]->latitude<nodesx->lat_min)
348			nodesx->lat_min=nodesx->gdata[i]->latitude;
349			if(nodesx->gdata[i]->latitude>nodesx->lat_max)
350			nodesx->lat_max=nodesx->gdata[i]->latitude;
351			if(nodesx->gdata[i]->longitude<nodesx->lon_min)
352			nodesx->lon_min=nodesx->gdata[i]->longitude;
353			if(nodesx->gdata[i]->longitude>nodesx->lon_max)
354			nodesx->lon_max=nodesx->gdata[i]->longitude;
355			}
356
357	amb	132	printf("\rSorted Nodes \n"); fflush(stdout);
358	amb	110	}
359
360
361			/*++++++++++++++++++++++++++++++++++++++
362			Sort the nodes into id order.
363
364			int sort_by_id Returns the comparison of the id fields.
365
366			NodeX **a The first Node.
367
368			NodeX **b The second Node.
369			++++++++++++++++++++++++++++++++++++++*/
370
371			static int sort_by_id(NodeX a,NodeX b)
372			{
373			node_t a_id=(*a)->id;
374			node_t b_id=(*b)->id;
375
376			if(a_id<b_id)
377			return(-1);
378	amb	144	else if(a_id>b_id)
379			return(1);
380	amb	110	else
381	amb	144	return(0);
382	amb	110	}
383
384
385			/*++++++++++++++++++++++++++++++++++++++
386			Sort the nodes into latitude and longitude order.
387
388			int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
389
390			NodeX **a The first Node.
391
392			NodeX **b The second Node.
393			++++++++++++++++++++++++++++++++++++++*/
394
395			static int sort_by_lat_long(NodeX a,NodeX b)
396			{
397	amb	118	int32_t a_lon=lat_long_to_bin((*a)->longitude);
398			int32_t b_lon=lat_long_to_bin((*b)->longitude);
399	amb	110
400			if(a_lon<b_lon)
401			return(-1);
402			else if(a_lon>b_lon)
403			return(1);
404			else
405			{
406	amb	118	int32_t a_lat=lat_long_to_bin((*a)->latitude);
407			int32_t b_lat=lat_long_to_bin((*b)->latitude);
408	amb	110
409			if(a_lat<b_lat)
410			return(-1);
411			else if(a_lat>b_lat)
412			return(1);
413			else
414			return(0);
415			}
416			}
417
418
419			/*++++++++++++++++++++++++++++++++++++++
420			Remove any nodes that are not part of a highway.
421
422			NodesX *nodesx The complete node list.
423
424			SegmentsX *segmentsx The list of segments.
425			++++++++++++++++++++++++++++++++++++++*/
426
427			void RemoveNonHighwayNodes(NodesX nodesx,SegmentsX segmentsx)
428			{
429			int i;
430			int highway=0,nothighway=0;
431
432			assert(!nodesx->sorted); /* Must not be sorted */
433
434			for(i=0;i<nodesx->xnumber;i++)
435			{
436			if(FindFirstSegmentX(segmentsx,nodesx->xdata[i].id))
437			highway++;
438			else
439			{
440	amb	176	nodesx->xdata[i].id=NO_NODE;
441	amb	110	nothighway++;
442			}
443
444			if(!((i+1)%10000))
445			{
446			printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
447			fflush(stdout);
448			}
449			}
450
451			printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d \n",nodesx->xnumber,highway,nothighway);
452			fflush(stdout);
453			}
454
455
456			/*++++++++++++++++++++++++++++++++++++++
457			Mark super nodes.
458
459			NodesX* nodesx The set of nodes to process.
460
461			int iteration The final super-node / super-segment iteration number.
462			++++++++++++++++++++++++++++++++++++++*/
463
464			void MarkSuperNodes(NodesX *nodesx,int iteration)
465			{
466			int i,nnodes=0;;
467
468			assert(nodesx->sorted); /* Must be sorted */
469
470			for(i=0;i<nodesx->number;i++)
471			{
472			if(nodesx->gdata[i]->super==iteration)
473			{
474	amb	176	nodesx->gdata[i]->node.firstseg=SEGMENT(NO_SEGMENT)\|SUPER_FLAG;
475	amb	110	nnodes++;
476			}
477			else
478	amb	176	nodesx->gdata[i]->node.firstseg=SEGMENT(NO_SEGMENT);
479	amb	110
480			if(!((i+1)%10000))
481			{
482			printf("\rMarking Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
483			fflush(stdout);
484			}
485			}
486
487			printf("\rMarked Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
488			fflush(stdout);
489			}
490
491
492			/*++++++++++++++++++++++++++++++++++++++
493			Assign the segment indexes to the nodes.
494
495			NodesX *nodesx The list of nodes to process.
496
497			SegmentsX* segmentsx The set of segments to use.
498			++++++++++++++++++++++++++++++++++++++*/
499
500			void IndexNodes(NodesX nodesx,SegmentsX segmentsx)
501			{
502			int i;
503
504			assert(nodesx->sorted); /* Must be sorted */
505			assert(segmentsx->sorted); /* Must be sorted */
506
507			/* Index the nodes */
508
509			for(i=0;i<segmentsx->number;i++)
510			{
511			NodeX *node1=FindNodeX(nodesx,segmentsx->sdata[i]->node1);
512			NodeX *node2=FindNodeX(nodesx,segmentsx->sdata[i]->node2);
513
514			/* Check node1 */
515
516	amb	176	if(SEGMENT(node1->node.firstseg)==SEGMENT(NO_SEGMENT))
517	amb	110	{
518	amb	176	node1->node.firstseg^=SEGMENT(NO_SEGMENT);
519	amb	110	node1->node.firstseg\|=i;
520			}
521			else
522			{
523	amb	128	SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(node1->node.firstseg));
524	amb	110
525			do
526			{
527	amb	128	if((*segmentx)->node1==segmentsx->sdata[i]->node1)
528	amb	110	{
529	amb	128	segmentx++;
530
531			if((*segmentx)->node1!=segmentsx->sdata[i]->node1 \|\| (segmentx-segmentsx->sdata)>=segmentsx->number)
532	amb	110	segmentx=NULL;
533			}
534			else
535			{
536	amb	176	if((*segmentx)->segment.next2==NO_NODE)
537	amb	110	{
538	amb	128	(*segmentx)->segment.next2=i;
539	amb	110	segmentx=NULL;
540			}
541			else
542	amb	128	segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
543	amb	110	}
544			}
545			while(segmentx);
546			}
547
548			/* Check node2 */
549
550	amb	176	if(SEGMENT(node2->node.firstseg)==SEGMENT(NO_SEGMENT))
551	amb	110	{
552	amb	176	node2->node.firstseg^=SEGMENT(NO_SEGMENT);
553	amb	110	node2->node.firstseg\|=i;
554			}
555			else
556			{
557	amb	128	SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(node2->node.firstseg));
558	amb	110
559			do
560			{
561	amb	128	if((*segmentx)->node1==segmentsx->sdata[i]->node2)
562	amb	110	{
563	amb	128	segmentx++;
564
565			if((*segmentx)->node1!=segmentsx->sdata[i]->node2 \|\| (segmentx-segmentsx->sdata)>=segmentsx->number)
566	amb	110	segmentx=NULL;
567			}
568			else
569			{
570	amb	176	if((*segmentx)->segment.next2==NO_NODE)
571	amb	110	{
572	amb	128	(*segmentx)->segment.next2=i;
573	amb	110	segmentx=NULL;
574			}
575			else
576	amb	128	segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
577	amb	110	}
578			}
579			while(segmentx);
580			}
581
582			if(!((i+1)%10000))
583			{
584			printf("\rIndexing Segments: Segments=%d",i+1);
585			fflush(stdout);
586			}
587			}
588
589			printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
590			fflush(stdout);
591			}