trunk/src/nodesx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/nodesx.c,v 1.5 2009-02-28 17:31:41 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));

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

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

 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;

 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
    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	132	$Header: /home/amb/CVS/routino/src/nodesx.c,v 1.5 2009-02-28 17:31:41 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	amb	132	{
134	amb	110	WriteFile(fd,&nodesx->gdata[i]->node,sizeof(Node));
135
136	amb	132	if(!((i+1)%10000))
137			{
138			printf("\rWriting Nodes: Nodes=%d",i+1);
139			fflush(stdout);
140			}
141			}
142
143			printf("\rWrote Nodes: Nodes=%d \n",nodesx->number);
144			fflush(stdout);
145
146	amb	110	CloseFile(fd);
147
148			/* Free the fake Nodes */
149
150			free(nodes);
151			free(offsets);
152			}
153
154
155			/*++++++++++++++++++++++++++++++++++++++
156			Find a particular node.
157
158			NodeX *FindNodeX Returns the extended node with the specified id.
159
160			NodesX* nodesx The set of nodes to process.
161
162			node_t id The node id to look for.
163			++++++++++++++++++++++++++++++++++++++*/
164
165			NodeX FindNodeX(NodesX nodesx,node_t id)
166			{
167			int start=0;
168			int end=nodesx->number-1;
169			int mid;
170
171			assert(nodesx->sorted); /* Must be sorted */
172
173			/* Binary search - search key exact match only is required.
174			*
175			* # <- start \| Check mid and move start or end if it doesn't match
176			* # \|
177			* # \| Since an exact match is wanted we can set end=mid-1
178			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
179			* # \|
180			* # \| Eventually either end=start or end=start+1 and one of
181			* # <- end \| start or end is the wanted one.
182			*/
183
184			if(end<start) /* There are no nodes */
185			return(NULL);
186			else if(id<nodesx->idata[start]->id) /* Check key is not before start */
187			return(NULL);
188			else if(id>nodesx->idata[end]->id) /* Check key is not after end */
189			return(NULL);
190			else
191			{
192			do
193			{
194			mid=(start+end)/2; /* Choose mid point */
195
196			if(nodesx->idata[mid]->id<id) /* Mid point is too low */
197			start=mid+1;
198			else if(nodesx->idata[mid]->id>id) /* Mid point is too high */
199			end=mid-1;
200			else /* Mid point is correct */
201			return(nodesx->idata[mid]);
202			}
203			while((end-start)>1);
204
205			if(nodesx->idata[start]->id==id) /* Start is correct */
206			return(nodesx->idata[start]);
207
208			if(nodesx->idata[end]->id==id) /* End is correct */
209			return(nodesx->idata[end]);
210			}
211
212			return(NULL);
213			}
214
215
216			/*++++++++++++++++++++++++++++++++++++++
217			Append a node to a newly created node list (unsorted).
218
219			Node *AppendNode Return a pointer to the new node.
220
221			NodesX* nodesx The set of nodes to process.
222
223			node_t id The node identification.
224
225			float latitude The latitude of the node.
226
227			float longitude The longitude of the node.
228			++++++++++++++++++++++++++++++++++++++*/
229
230			Node AppendNode(NodesX nodesx,node_t id,float latitude,float longitude)
231			{
232			/* Check that the array has enough space. */
233
234			if(nodesx->xnumber==nodesx->alloced)
235			{
236			nodesx->alloced+=INCREMENT_NODES;
237
238			nodesx->xdata=(NodeX)realloc((void)nodesx->xdata,nodesx->alloced*sizeof(NodeX));
239			}
240
241			/* Insert the node */
242
243			nodesx->xdata[nodesx->xnumber].id=id;
244			nodesx->xdata[nodesx->xnumber].super=0;
245			nodesx->xdata[nodesx->xnumber].latitude=latitude;
246			nodesx->xdata[nodesx->xnumber].longitude=longitude;
247
248			memset(&nodesx->xdata[nodesx->xnumber].node,0,sizeof(Node));
249
250			nodesx->xnumber++;
251
252			nodesx->sorted=0;
253
254			return(&nodesx->xdata[nodesx->xnumber-1].node);
255			}
256
257
258			/*++++++++++++++++++++++++++++++++++++++
259			Sort the node list.
260
261			NodesX* nodesx The set of nodes to process.
262			++++++++++++++++++++++++++++++++++++++*/
263
264			void SortNodeList(NodesX* nodesx)
265			{
266			int i;
267
268	amb	132	printf("Sorting Nodes"); fflush(stdout);
269
270	amb	110	/* Allocate the arrays of pointers */
271
272			if(nodesx->sorted)
273			{
274			nodesx->gdata=realloc(nodesx->gdata,nodesx->xnumbersizeof(NodeX));
275			nodesx->idata=realloc(nodesx->idata,nodesx->xnumbersizeof(NodeX));
276			}
277			else
278			{
279			nodesx->gdata=malloc(nodesx->xnumbersizeof(NodeX));
280			nodesx->idata=malloc(nodesx->xnumbersizeof(NodeX));
281			}
282
283			nodesx->number=0;
284
285			for(i=0;i<nodesx->xnumber;i++)
286			if(nodesx->xdata[i].id!=~0)
287			{
288			nodesx->gdata[nodesx->number]=&nodesx->xdata[i];
289			nodesx->idata[nodesx->number]=&nodesx->xdata[i];
290			nodesx->number++;
291			}
292
293			/* Sort geographically */
294
295			qsort(nodesx->gdata,nodesx->number,sizeof(NodeX),(int ()(const void,const void))sort_by_lat_long);
296
297	amb	121	nodesx->lat_min=2;
298			nodesx->lat_max=-2;
299			nodesx->lon_min=4;
300			nodesx->lon_max=-4;
301	amb	110
302			for(i=0;i<nodesx->number;i++)
303			{
304	amb	118	int32_t lat=(int32_t)(nodesx->gdata[i]->latitude *LAT_LONG_SCALE);
305	amb	110	int32_t lon=(int32_t)(nodesx->gdata[i]->longitude*LAT_LONG_SCALE);
306
307			nodesx->gdata[i]->node.latoffset=lat%LAT_LONG_BIN;
308			nodesx->gdata[i]->node.lonoffset=lon%LAT_LONG_BIN;
309
310			if(nodesx->gdata[i]->latitude<nodesx->lat_min)
311			nodesx->lat_min=nodesx->gdata[i]->latitude;
312			if(nodesx->gdata[i]->latitude>nodesx->lat_max)
313			nodesx->lat_max=nodesx->gdata[i]->latitude;
314			if(nodesx->gdata[i]->longitude<nodesx->lon_min)
315			nodesx->lon_min=nodesx->gdata[i]->longitude;
316			if(nodesx->gdata[i]->longitude>nodesx->lon_max)
317			nodesx->lon_max=nodesx->gdata[i]->longitude;
318			}
319
320			/* Sort by id */
321
322			qsort(nodesx->idata,nodesx->number,sizeof(NodeX),(int ()(const void,const void))sort_by_id);
323
324			nodesx->sorted=1;
325	amb	132
326			printf("\rSorted Nodes \n"); fflush(stdout);
327	amb	110	}
328
329
330			/*++++++++++++++++++++++++++++++++++++++
331			Sort the nodes into id order.
332
333			int sort_by_id Returns the comparison of the id fields.
334
335			NodeX **a The first Node.
336
337			NodeX **b The second Node.
338			++++++++++++++++++++++++++++++++++++++*/
339
340			static int sort_by_id(NodeX a,NodeX b)
341			{
342			node_t a_id=(*a)->id;
343			node_t b_id=(*b)->id;
344
345			if(a_id<b_id)
346			return(-1);
347			else
348			return(1);
349			}
350
351
352			/*++++++++++++++++++++++++++++++++++++++
353			Sort the nodes into latitude and longitude order.
354
355			int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
356
357			NodeX **a The first Node.
358
359			NodeX **b The second Node.
360			++++++++++++++++++++++++++++++++++++++*/
361
362			static int sort_by_lat_long(NodeX a,NodeX b)
363			{
364	amb	118	int32_t a_lon=lat_long_to_bin((*a)->longitude);
365			int32_t b_lon=lat_long_to_bin((*b)->longitude);
366	amb	110
367			if(a_lon<b_lon)
368			return(-1);
369			else if(a_lon>b_lon)
370			return(1);
371			else
372			{
373	amb	118	int32_t a_lat=lat_long_to_bin((*a)->latitude);
374			int32_t b_lat=lat_long_to_bin((*b)->latitude);
375	amb	110
376			if(a_lat<b_lat)
377			return(-1);
378			else if(a_lat>b_lat)
379			return(1);
380			else
381			return(0);
382			}
383			}
384
385
386			/*++++++++++++++++++++++++++++++++++++++
387			Remove any nodes that are not part of a highway.
388
389			NodesX *nodesx The complete node list.
390
391			SegmentsX *segmentsx The list of segments.
392			++++++++++++++++++++++++++++++++++++++*/
393
394			void RemoveNonHighwayNodes(NodesX nodesx,SegmentsX segmentsx)
395			{
396			int i;
397			int highway=0,nothighway=0;
398
399			assert(!nodesx->sorted); /* Must not be sorted */
400
401			for(i=0;i<nodesx->xnumber;i++)
402			{
403			if(FindFirstSegmentX(segmentsx,nodesx->xdata[i].id))
404			highway++;
405			else
406			{
407			nodesx->xdata[i].id=~0;
408			nothighway++;
409			}
410
411			if(!((i+1)%10000))
412			{
413			printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
414			fflush(stdout);
415			}
416			}
417
418			printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d \n",nodesx->xnumber,highway,nothighway);
419			fflush(stdout);
420			}
421
422
423			/*++++++++++++++++++++++++++++++++++++++
424			Mark super nodes.
425
426			NodesX* nodesx The set of nodes to process.
427
428			int iteration The final super-node / super-segment iteration number.
429			++++++++++++++++++++++++++++++++++++++*/
430
431			void MarkSuperNodes(NodesX *nodesx,int iteration)
432			{
433			int i,nnodes=0;;
434
435			assert(nodesx->sorted); /* Must be sorted */
436
437			for(i=0;i<nodesx->number;i++)
438			{
439			if(nodesx->gdata[i]->super==iteration)
440			{
441			nodesx->gdata[i]->node.firstseg=SEGMENT(~0)\|SUPER_FLAG;
442			nnodes++;
443			}
444			else
445			nodesx->gdata[i]->node.firstseg=SEGMENT(~0);
446
447			if(!((i+1)%10000))
448			{
449			printf("\rMarking Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
450			fflush(stdout);
451			}
452			}
453
454			printf("\rMarked Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
455			fflush(stdout);
456			}
457
458
459			/*++++++++++++++++++++++++++++++++++++++
460			Assign the segment indexes to the nodes.
461
462			NodesX *nodesx The list of nodes to process.
463
464			SegmentsX* segmentsx The set of segments to use.
465			++++++++++++++++++++++++++++++++++++++*/
466
467			void IndexNodes(NodesX nodesx,SegmentsX segmentsx)
468			{
469			int i;
470
471			assert(nodesx->sorted); /* Must be sorted */
472			assert(segmentsx->sorted); /* Must be sorted */
473
474			/* Index the nodes */
475
476			for(i=0;i<segmentsx->number;i++)
477			{
478			NodeX *node1=FindNodeX(nodesx,segmentsx->sdata[i]->node1);
479			NodeX *node2=FindNodeX(nodesx,segmentsx->sdata[i]->node2);
480
481			/* Check node1 */
482
483			if(SEGMENT(node1->node.firstseg)==SEGMENT(~0))
484			{
485			node1->node.firstseg^=SEGMENT(~0);
486			node1->node.firstseg\|=i;
487			}
488			else
489			{
490	amb	128	SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(node1->node.firstseg));
491	amb	110
492			do
493			{
494	amb	128	if((*segmentx)->node1==segmentsx->sdata[i]->node1)
495	amb	110	{
496	amb	128	segmentx++;
497
498			if((*segmentx)->node1!=segmentsx->sdata[i]->node1 \|\| (segmentx-segmentsx->sdata)>=segmentsx->number)
499	amb	110	segmentx=NULL;
500			}
501			else
502			{
503	amb	128	if((*segmentx)->segment.next2==~0)
504	amb	110	{
505	amb	128	(*segmentx)->segment.next2=i;
506	amb	110	segmentx=NULL;
507			}
508			else
509	amb	128	segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
510	amb	110	}
511			}
512			while(segmentx);
513			}
514
515			/* Check node2 */
516
517			if(SEGMENT(node2->node.firstseg)==SEGMENT(~0))
518			{
519			node2->node.firstseg^=SEGMENT(~0);
520			node2->node.firstseg\|=i;
521			}
522			else
523			{
524	amb	128	SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(node2->node.firstseg));
525	amb	110
526			do
527			{
528	amb	128	if((*segmentx)->node1==segmentsx->sdata[i]->node2)
529	amb	110	{
530	amb	128	segmentx++;
531
532			if((*segmentx)->node1!=segmentsx->sdata[i]->node2 \|\| (segmentx-segmentsx->sdata)>=segmentsx->number)
533	amb	110	segmentx=NULL;
534			}
535			else
536			{
537	amb	128	if((*segmentx)->segment.next2==~0)
538	amb	110	{
539	amb	128	(*segmentx)->segment.next2=i;
540	amb	110	segmentx=NULL;
541			}
542			else
543	amb	128	segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
544	amb	110	}
545			}
546			while(segmentx);
547			}
548
549			if(!((i+1)%10000))
550			{
551			printf("\rIndexing Segments: Segments=%d",i+1);
552			fflush(stdout);
553			}
554			}
555
556			printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
557			fflush(stdout);
558			}