trunk/src/nodesx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/nodesx.c,v 1.4 2009-02-24 19:59:36 amb Exp $

 Extented Node data type functions.
 ******************/ /******************
 Written by Andrew M. Bishop

 This file Copyright 2008,2009 Andrew M. Bishop
 It may be distributed under the GNU Public License, version 2, or
 any higher version.  See section COPYING of the GNU Public license
 for conditions under which this file may be redistributed.
 ***************************************/


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

 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=latitude;
 nodesx->xdata[nodesx->xnumber].longitude=longitude;

 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;

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

 nodesx->number=0;

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

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

 /* Sort by id */

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

 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
    return(1);
}


/*++++++++++++++++++++++++++++++++++++++
  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=~0;
       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(~0)|SUPER_FLAG;
       nnodes++;
      }
    else
       nodesx->gdata[i]->node.firstseg=SEGMENT(~0);

    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(~0))
      {
       node1->node.firstseg^=SEGMENT(~0);
       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==~0)
               {
                (*segmentx)->segment.next2=i;
                segmentx=NULL;
               }
             else
                segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
            }
         }
       while(segmentx);
      }

    /* Check node2 */

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