trunk/src/nodes.c

/***************************************
 $Header: /home/amb/CVS/routino/src/nodes.c,v 1.16 2009-02-02 18:53:12 amb Exp $

 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 "functions.h"
#include "nodes.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);


/*++++++++++++++++++++++++++++++++++++++
  Load in a node list from a file.

  Nodes* LoadNodeList Returns the node list.

  const char *filename The name of the file to load.
  ++++++++++++++++++++++++++++++++++++++*/

Nodes *LoadNodeList(const char *filename)
{
 void *data;
 Nodes *nodes;

 nodes=(Nodes*)malloc(sizeof(Nodes));

 data=MapFile(filename);

 /* Copy the Nodes structure from the loaded data */

 *nodes=*((Nodes*)data);

 /* Adjust the pointers in the Nodes structure. */

 nodes->data =data;
 nodes->nodes=(Node*)(data+(off_t)nodes->nodes);

 return(nodes);
}


/*++++++++++++++++++++++++++++++++++++++
  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->number=0;
 nodesx->sorted=0;

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

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

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

 /* 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->data=NULL;
 nodes->nodes=(void*)sizeof(Nodes);

 /* Write out the Nodes structure and then the real data. */

 fd=OpenFile(filename);

 WriteFile(fd,nodes,sizeof(Nodes));

 for(i=0;i<nodesx->number;i++)
   {
    if(nodesx->xdata[i].id==10319449)
       printf("\n10319449 -> %d\n",i);

    if(nodesx->xdata[i].id==30810456)
       printf("\n30810456 -> %d\n",i);

    if(nodesx->xdata[i].id==21734658)
       printf("\n21734658 -> %d\n",i);

    if(nodesx->xdata[i].id==206231001)
       printf("\n206231001 -> %d\n",i);

    WriteFile(fd,&nodesx->xdata[i].node,sizeof(Node));
   }

 CloseFile(fd);

 /* Free the fake Nodes */

 free(nodes);
}


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

 /* 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->xdata[start].id) /* Check key is not before start */
    return(NULL);
 else if(id>nodesx->xdata[end].id)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;                /* Choose mid point */

       if(nodesx->xdata[mid].id<id)      /* Mid point is too low */
          start=mid+1;
       else if(nodesx->xdata[mid].id>id) /* Mid point is too high */
          end=mid-1;
       else                              /* Mid point is correct */
          return(LookupNodeX(nodesx,mid));
      }
    while((end-start)>1);

    if(nodesx->xdata[start].id==id)      /* Start is correct */
       return(LookupNodeX(nodesx,start));

    if(nodesx->xdata[end].id==id)        /* End is correct */
       return(LookupNodeX(nodesx,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->number==nodesx->alloced)
   {
    nodesx->alloced+=INCREMENT_NODES;

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

 /* Insert the node */

 nodesx->xdata[nodesx->number].id=id;
 nodesx->xdata[nodesx->number].super=0;
 nodesx->xdata[nodesx->number].node.latitude=latitude;
 nodesx->xdata[nodesx->number].node.longitude=longitude;

 nodesx->number++;

 nodesx->sorted=0;

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


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

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

void SortNodeList(NodesX* nodesx)
{
 qsort(nodesx->xdata,nodesx->number,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_id);

 while(nodesx->xdata[nodesx->number-1].id==~0)
    nodesx->number--;

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


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

 for(i=0;i<nodesx->number;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->number,highway,nothighway);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Fix the node indexes to the segments.

  NodesX* nodesx The set of nodes to process.

  SegmentsX *segmentsx The list of segments to use.

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

void FixupNodes(NodesX *nodesx,SegmentsX* segmentsx,int iteration)
{
 int i;

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

 for(i=0;i<nodesx->number;i++)
   {
    SegmentX *firstseg=FindFirstSegmentX(segmentsx,nodesx->xdata[i].id);

    nodesx->xdata[i].node.firstseg=IndexSegmentX(segmentsx,firstseg);

    if(nodesx->xdata[i].super==iteration)
       nodesx->xdata[i].node.firstseg|=SUPER_FLAG;

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

 printf("\rFixed Nodes: Nodes=%d \n",nodesx->number);
 fflush(stdout);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/nodes.c,v 1.16 2009-02-02 18:53:12 amb Exp $
3
4	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
18	#include "functions.h"
19	#include "nodes.h"
20
21
22	/* Constants */
23
24	/+ The array size increment for nodes - expect ~8,000,000 nodes. +/
25	#define INCREMENT_NODES 1024*1024
26
27
28	/* Functions */
29
30	static int sort_by_id(NodeX a,NodeX b);
31
32
33	/*++++++++++++++++++++++++++++++++++++++
34	Load in a node list from a file.
35
36	Nodes* LoadNodeList Returns the node list.
37
38	const char *filename The name of the file to load.
39	++++++++++++++++++++++++++++++++++++++*/
40
41	Nodes LoadNodeList(const char filename)
42	{
43	void *data;
44	Nodes *nodes;
45
46	nodes=(Nodes*)malloc(sizeof(Nodes));
47
48	data=MapFile(filename);
49
50	/* Copy the Nodes structure from the loaded data */
51
52	nodes=((Nodes*)data);
53
54	/* Adjust the pointers in the Nodes structure. */
55
56	nodes->data =data;
57	nodes->nodes=(Node*)(data+(off_t)nodes->nodes);
58
59	return(nodes);
60	}
61
62
63	/*++++++++++++++++++++++++++++++++++++++
64	Allocate a new node list.
65
66	NodesX *NewNodeList Returns the node list.
67	++++++++++++++++++++++++++++++++++++++*/
68
69	NodesX *NewNodeList(void)
70	{
71	NodesX *nodesx;
72
73	nodesx=(NodesX*)malloc(sizeof(NodesX));
74
75	nodesx->alloced=INCREMENT_NODES;
76	nodesx->number=0;
77	nodesx->sorted=0;
78
79	nodesx->xdata=(NodeX)malloc(nodesx->allocedsizeof(NodeX));
80
81	return(nodesx);
82	}
83
84
85	/*++++++++++++++++++++++++++++++++++++++
86	Save the node list to a file.
87
88	NodesX* nodesx The set of nodes to save.
89
90	const char *filename The name of the file to save.
91	++++++++++++++++++++++++++++++++++++++*/
92
93	void SaveNodeList(NodesX* nodesx,const char *filename)
94	{
95	int i;
96	int fd;
97	Nodes *nodes=calloc(1,sizeof(Nodes));
98
99	assert(nodesx->sorted); /* Must be sorted */
100
101	/* Fill in a Nodes structure with the offset of the real data in the file after
102	the Node structure itself. */
103
104	nodes->number=nodesx->number;
105	nodes->data=NULL;
106	nodes->nodes=(void*)sizeof(Nodes);
107
108	/* Write out the Nodes structure and then the real data. */
109
110	fd=OpenFile(filename);
111
112	WriteFile(fd,nodes,sizeof(Nodes));
113
114	for(i=0;i<nodesx->number;i++)
115	{
116	if(nodesx->xdata[i].id==10319449)
117	printf("\n10319449 -> %d\n",i);
118
119	if(nodesx->xdata[i].id==30810456)
120	printf("\n30810456 -> %d\n",i);
121
122	if(nodesx->xdata[i].id==21734658)
123	printf("\n21734658 -> %d\n",i);
124
125	if(nodesx->xdata[i].id==206231001)
126	printf("\n206231001 -> %d\n",i);
127
128	WriteFile(fd,&nodesx->xdata[i].node,sizeof(Node));
129	}
130
131	CloseFile(fd);
132
133	/* Free the fake Nodes */
134
135	free(nodes);
136	}
137
138
139	/*++++++++++++++++++++++++++++++++++++++
140	Find a particular node.
141
142	NodeX *FindNodeX Returns the extended node with the specified id.
143
144	NodesX* nodesx The set of nodes to process.
145
146	node_t id The node id to look for.
147	++++++++++++++++++++++++++++++++++++++*/
148
149	NodeX FindNodeX(NodesX nodesx,node_t id)
150	{
151	int start=0;
152	int end=nodesx->number-1;
153	int mid;
154
155	/* Binary search - search key exact match only is required.
156	*
157	* # <- start \| Check mid and move start or end if it doesn't match
158	* # \|
159	* # \| Since an exact match is wanted we can set end=mid-1
160	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
161	* # \|
162	* # \| Eventually either end=start or end=start+1 and one of
163	* # <- end \| start or end is the wanted one.
164	*/
165
166	if(end<start) /* There are no nodes */
167	return(NULL);
168	else if(id<nodesx->xdata[start].id) /* Check key is not before start */
169	return(NULL);
170	else if(id>nodesx->xdata[end].id) /* Check key is not after end */
171	return(NULL);
172	else
173	{
174	do
175	{
176	mid=(start+end)/2; /* Choose mid point */
177
178	if(nodesx->xdata[mid].id<id) /* Mid point is too low */
179	start=mid+1;
180	else if(nodesx->xdata[mid].id>id) /* Mid point is too high */
181	end=mid-1;
182	else /* Mid point is correct */
183	return(LookupNodeX(nodesx,mid));
184	}
185	while((end-start)>1);
186
187	if(nodesx->xdata[start].id==id) /* Start is correct */
188	return(LookupNodeX(nodesx,start));
189
190	if(nodesx->xdata[end].id==id) /* End is correct */
191	return(LookupNodeX(nodesx,end));
192	}
193
194	return(NULL);
195	}
196
197
198	/*++++++++++++++++++++++++++++++++++++++
199	Append a node to a newly created node list (unsorted).
200
201	Node *AppendNode Return a pointer to the new node.
202
203	NodesX* nodesx The set of nodes to process.
204
205	node_t id The node identification.
206
207	float latitude The latitude of the node.
208
209	float longitude The longitude of the node.
210	++++++++++++++++++++++++++++++++++++++*/
211
212	Node AppendNode(NodesX nodesx,node_t id,float latitude,float longitude)
213	{
214	/* Check that the array has enough space. */
215
216	if(nodesx->number==nodesx->alloced)
217	{
218	nodesx->alloced+=INCREMENT_NODES;
219
220	nodesx->xdata=(NodeX)realloc((void)nodesx->xdata,nodesx->alloced*sizeof(NodeX));
221	}
222
223	/* Insert the node */
224
225	nodesx->xdata[nodesx->number].id=id;
226	nodesx->xdata[nodesx->number].super=0;
227	nodesx->xdata[nodesx->number].node.latitude=latitude;
228	nodesx->xdata[nodesx->number].node.longitude=longitude;
229
230	nodesx->number++;
231
232	nodesx->sorted=0;
233
234	return(&nodesx->xdata[nodesx->number-1].node);
235	}
236
237
238	/*++++++++++++++++++++++++++++++++++++++
239	Sort the node list.
240
241	NodesX* nodesx The set of nodes to process.
242	++++++++++++++++++++++++++++++++++++++*/
243
244	void SortNodeList(NodesX* nodesx)
245	{
246	qsort(nodesx->xdata,nodesx->number,sizeof(NodeX),(int ()(const void,const void*))sort_by_id);
247
248	while(nodesx->xdata[nodesx->number-1].id==~0)
249	nodesx->number--;
250
251	nodesx->sorted=1;
252	}
253
254
255	/*++++++++++++++++++++++++++++++++++++++
256	Sort the nodes into id order.
257
258	int sort_by_id Returns the comparison of the id fields.
259
260	NodeX *a The first Node.
261
262	NodeX *b The second Node.
263	++++++++++++++++++++++++++++++++++++++*/
264
265	static int sort_by_id(NodeX a,NodeX b)
266	{
267	node_t a_id=a->id;
268	node_t b_id=b->id;
269
270	if(a_id<b_id)
271	return(-1);
272	else
273	return(1);
274	}
275
276
277	/*++++++++++++++++++++++++++++++++++++++
278	Remove any nodes that are not part of a highway.
279
280	NodesX *nodesx The complete node list.
281
282	SegmentsX *segmentsx The list of segments.
283	++++++++++++++++++++++++++++++++++++++*/
284
285	void RemoveNonHighwayNodes(NodesX nodesx,SegmentsX segmentsx)
286	{
287	int i;
288	int highway=0,nothighway=0;
289
290	for(i=0;i<nodesx->number;i++)
291	{
292	if(FindFirstSegmentX(segmentsx,nodesx->xdata[i].id))
293	highway++;
294	else
295	{
296	nodesx->xdata[i].id=~0;
297	nothighway++;
298	}
299
300	if(!((i+1)%10000))
301	{
302	printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
303	fflush(stdout);
304	}
305	}
306
307	printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d \n",nodesx->number,highway,nothighway);
308	fflush(stdout);
309	}
310
311
312	/*++++++++++++++++++++++++++++++++++++++
313	Fix the node indexes to the segments.
314
315	NodesX* nodesx The set of nodes to process.
316
317	SegmentsX *segmentsx The list of segments to use.
318
319	int iteration The current super-node / super-segment iteration number.
320	++++++++++++++++++++++++++++++++++++++*/
321
322	void FixupNodes(NodesX nodesx,SegmentsX segmentsx,int iteration)
323	{
324	int i;
325
326	assert(nodesx->sorted); /* Must be sorted */
327
328	for(i=0;i<nodesx->number;i++)
329	{
330	SegmentX *firstseg=FindFirstSegmentX(segmentsx,nodesx->xdata[i].id);
331
332	nodesx->xdata[i].node.firstseg=IndexSegmentX(segmentsx,firstseg);
333
334	if(nodesx->xdata[i].super==iteration)
335	nodesx->xdata[i].node.firstseg\|=SUPER_FLAG;
336
337	if(!((i+1)%10000))
338	{
339	printf("\rFixing Nodes: Nodes=%d",i+1);
340	fflush(stdout);
341	}
342	}
343
344	printf("\rFixed Nodes: Nodes=%d \n",nodesx->number);
345	fflush(stdout);
346	}