trunk/src/nodesx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/nodesx.c,v 1.20 2009-07-02 17:49:16 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 "types.h"
#include "functions.h"
#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.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*)calloc(1,sizeof(NodesX));

 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)
{
 index_t 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 */
 assert(nodesx->gdata);         /* Must have gdata filled in */
 assert(nodesx->ndata);         /* Must have ndata filled in */

 /* 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<nodes->number;i++)
   {
    NodeX **nodex=FindNodeX(nodesx,nodesx->gdata[i]->id);
    Node   *node =&nodesx->ndata[nodex-nodesx->idata];

    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.

  NodeX **FindNodeX Returns a pointer to 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 */
 assert(nodesx->idata);         /* Must have idata filled in */

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

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

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

 nodesx->xnumber++;

 nodesx->sorted=0;
}


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

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

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

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

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

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

 nodesx->idata=(NodeX**)realloc(nodesx->idata,nodesx->xnumber*sizeof(NodeX*));

 do
   {
    nodesx->number=0;

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

    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);
   }
 while(duplicate);

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

 nodesx->sorted=1;
}


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

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

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

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

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

 /* Work out the range of data */

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

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

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

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

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

 nodesx->sorted=0;
}


/*++++++++++++++++++++++++++++++++++++++
  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->gdata);         /* Must have gdata filled in */

 /* Allocate the memory */

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

 /* Loop through and allocate. */

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

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

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

    if(nodesx->idata[i]->super==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->sorted);        /* Must be sorted */
 assert(nodesx->idata);         /* Must have idata filled in */
 assert(nodesx->ndata);         /* Must have ndata filled in */
 assert(segmentsx->sorted);     /* Must be sorted */
 assert(segmentsx->ndata);      /* Must have ndata filled in */
 assert(segmentsx->sdata);      /* Must have sdata filled in */

 /* Index the nodes */

 for(i=0;i<segmentsx->number;i++)
   {
    NodeX **nodex1=FindNodeX(nodesx,segmentsx->ndata[i]->node1);
    NodeX **nodex2=FindNodeX(nodesx,segmentsx->ndata[i]->node2);
    Node  *node1=&nodesx->ndata[nodex1-nodesx->idata];
    Node  *node2=&nodesx->ndata[nodex2-nodesx->idata];

    /* 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->ndata[index]->node1==segmentsx->ndata[i]->node1)
            {
             index++;

             if(index>=segmentsx->number || segmentsx->ndata[index]->node1!=segmentsx->ndata[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->ndata[index]->node1==segmentsx->ndata[i]->node2)
            {
             index++;

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