trunk/src/nodes.c

/***************************************
 $Header: /home/amb/CVS/routino/src/nodes.c,v 1.9 2009-01-22 18:57:16 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"


/* Functions */

static int sort_by_id(Node *a,Node *b);


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new node list.

  NodesMem *NewNodeList Returns the node list.
  ++++++++++++++++++++++++++++++++++++++*/

NodesMem *NewNodeList(void)
{
 NodesMem *nodes;

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

 nodes->alloced=INCREMENT_NODES;
 nodes->number=0;
 nodes->sorted=0;

 nodes->nodes=(Nodes*)malloc(sizeof(Nodes)+nodes->alloced*sizeof(Node));

 return(nodes);
}


/*++++++++++++++++++++++++++++++++++++++
  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)
{
 return((Nodes*)MapFile(filename));
}


/*++++++++++++++++++++++++++++++++++++++
  Save the node list to a file.

  Nodes* SaveNodeList Returns the node list that has just been saved.

  NodesMem* nodes The set of nodes to save.

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

Nodes *SaveNodeList(NodesMem* nodes,const char *filename)
{
 assert(nodes->sorted);        /* Must be sorted */

 if(WriteFile(filename,(void*)nodes->nodes,sizeof(Nodes)-sizeof(nodes->nodes->nodes)+nodes->number*sizeof(Node)))
    assert(0);

 free(nodes->nodes);
 free(nodes);

 return(LoadNodeList(filename));
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular node.

  Node *FindNode Returns a pointer to the node with the specified id.

  Nodes* nodes The set of nodes to process.

  node_t id The node id to look for.
  ++++++++++++++++++++++++++++++++++++++*/

Node *FindNode(Nodes* nodes,node_t id)
{
 int bin=id%NBINS_NODES;
 int start=nodes->offset[bin];
 int end=nodes->offset[bin+1]-1; /* &offset[NBINS+1] == &number */
 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<nodes->nodes[start].id) /* Check key is not before start */
    return(NULL);
 else if(id>nodes->nodes[end].id)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;               /* Choose mid point */

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

    if(nodes->nodes[start].id==id)      /* Start is correct */
       return(&nodes->nodes[start]);

    if(nodes->nodes[end].id==id)        /* End is correct */
       return(&nodes->nodes[end]);
   }

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Append a node to a newly created node list (unsorted).

  Node *AppendNode Return a pointer to the new node.

  NodesMem* nodes The set of nodes to process.

  node_t id The node identification.

  latlong_t latitude The latitude of the node.

  latlong_t longitude The longitude of the node.
  ++++++++++++++++++++++++++++++++++++++*/

Node *AppendNode(NodesMem* nodes,node_t id,latlong_t latitude,latlong_t longitude)
{
 /* Check that the array has enough space. */

 if(nodes->number==nodes->alloced)
   {
    nodes->alloced+=INCREMENT_NODES;

    nodes->nodes=(Nodes*)realloc((void*)nodes->nodes,sizeof(Nodes)+nodes->alloced*sizeof(Node));
   }

 /* Insert the node */

 nodes->nodes->nodes[nodes->number].id=id;
 nodes->nodes->nodes[nodes->number].latitude=latitude;
 nodes->nodes->nodes[nodes->number].longitude=longitude;

 nodes->number++;

 nodes->sorted=0;

 return(&nodes->nodes->nodes[nodes->number-1]);
}


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

  NodesMem* nodes The set of nodes to process.
  ++++++++++++++++++++++++++++++++++++++*/

void SortNodeList(NodesMem* nodes)
{
 int i,bin=0;

 qsort(nodes->nodes->nodes,nodes->number,sizeof(Node),(int (*)(const void*,const void*))sort_by_id);

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

 nodes->sorted=1;

 /* Make it searchable */

 nodes->nodes->number=nodes->number;

 for(i=0;i<nodes->number;i++)
    for(;bin<=(nodes->nodes->nodes[i].id%NBINS_NODES);bin++)
       nodes->nodes->offset[bin]=i;

 for(;bin<NBINS_NODES;bin++)
    nodes->nodes->offset[bin]=nodes->number;
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the nodes into id order.

  int sort_by_id Returns the comparison of the id fields.

  Node *a The first Node.

  Node *b The second Node.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_id(Node *a,Node *b)
{
 node_t a_id=a->id;
 node_t b_id=b->id;

 int a_bin=a->id%NBINS_NODES;
 int b_bin=b->id%NBINS_NODES;

 if(a_bin!=b_bin)
    return(a_bin-b_bin);

 if(a_id<b_id)
    return(-1);
 else if(a_id>b_id)
    return(1);
 else /* if(a_id==b_id) */
    return(0);
}


/*++++++++++++++++++++++++++++++++++++++
  Remove any nodes that are not part of a way.

  NodesMem *nodesmem The node list to create.

  Nodes *nodes The complete node list.

  Segments *segments The list of segments.
  ++++++++++++++++++++++++++++++++++++++*/

void RemoveNonWayNodes(NodesMem *nodesmem,Nodes *nodes,Segments *segments)
{
 int i;
 int inway=0,notinway=0;

 for(i=0;i<nodes->number;i++)
   {
    Node *node=LookupNode(nodes,i);

    if(FindFirstSegment(segments,node->id))
      {
       inway++;
       AppendNode(nodesmem,node->id,node->latitude,node->longitude);
      }
    else
       notinway++;

    if(!((i+1)%10000))
      {
       printf("\rChecking: Nodes=%d in-Way=%d not-in-Way=%d",i+1,inway,notinway);
       fflush(stdout);
      }
   }

 printf("\rChecked: Nodes=%d in-Way=%d not-in-Way=%d  \n",i,inway,notinway);
 fflush(stdout);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/nodes.c,v 1.9 2009-01-22 18:57:16 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	/* Functions */
23
24	static int sort_by_id(Node a,Node b);
25
26
27	/*++++++++++++++++++++++++++++++++++++++
28	Allocate a new node list.
29
30	NodesMem *NewNodeList Returns the node list.
31	++++++++++++++++++++++++++++++++++++++*/
32
33	NodesMem *NewNodeList(void)
34	{
35	NodesMem *nodes;
36
37	nodes=(NodesMem*)malloc(sizeof(NodesMem));
38
39	nodes->alloced=INCREMENT_NODES;
40	nodes->number=0;
41	nodes->sorted=0;
42
43	nodes->nodes=(Nodes)malloc(sizeof(Nodes)+nodes->allocedsizeof(Node));
44
45	return(nodes);
46	}
47
48
49	/*++++++++++++++++++++++++++++++++++++++
50	Load in a node list from a file.
51
52	Nodes* LoadNodeList Returns the node list.
53
54	const char *filename The name of the file to load.
55	++++++++++++++++++++++++++++++++++++++*/
56
57	Nodes LoadNodeList(const char filename)
58	{
59	return((Nodes*)MapFile(filename));
60	}
61
62
63	/*++++++++++++++++++++++++++++++++++++++
64	Save the node list to a file.
65
66	Nodes* SaveNodeList Returns the node list that has just been saved.
67
68	NodesMem* nodes The set of nodes to save.
69
70	const char *filename The name of the file to save.
71	++++++++++++++++++++++++++++++++++++++*/
72
73	Nodes SaveNodeList(NodesMem nodes,const char *filename)
74	{
75	assert(nodes->sorted); /* Must be sorted */
76
77	if(WriteFile(filename,(void)nodes->nodes,sizeof(Nodes)-sizeof(nodes->nodes->nodes)+nodes->numbersizeof(Node)))
78	assert(0);
79
80	free(nodes->nodes);
81	free(nodes);
82
83	return(LoadNodeList(filename));
84	}
85
86
87	/*++++++++++++++++++++++++++++++++++++++
88	Find a particular node.
89
90	Node *FindNode Returns a pointer to the node with the specified id.
91
92	Nodes* nodes The set of nodes to process.
93
94	node_t id The node id to look for.
95	++++++++++++++++++++++++++++++++++++++*/
96
97	Node FindNode(Nodes nodes,node_t id)
98	{
99	int bin=id%NBINS_NODES;
100	int start=nodes->offset[bin];
101	int end=nodes->offset[bin+1]-1; /* &offset[NBINS+1] == &number */
102	int mid;
103
104	/* Binary search - search key exact match only is required.
105	*
106	* # <- start \| Check mid and move start or end if it doesn't match
107	* # \|
108	* # \| Since an exact match is wanted we can set end=mid-1
109	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
110	* # \|
111	* # \| Eventually either end=start or end=start+1 and one of
112	* # <- end \| start or end is the wanted one.
113	*/
114
115	if(end<start) /* There are no nodes */
116	return(NULL);
117	else if(id<nodes->nodes[start].id) /* Check key is not before start */
118	return(NULL);
119	else if(id>nodes->nodes[end].id) /* Check key is not after end */
120	return(NULL);
121	else
122	{
123	do
124	{
125	mid=(start+end)/2; /* Choose mid point */
126
127	if(nodes->nodes[mid].id<id) /* Mid point is too low */
128	start=mid+1;
129	else if(nodes->nodes[mid].id>id) /* Mid point is too high */
130	end=mid-1;
131	else /* Mid point is correct */
132	return(&nodes->nodes[mid]);
133	}
134	while((end-start)>1);
135
136	if(nodes->nodes[start].id==id) /* Start is correct */
137	return(&nodes->nodes[start]);
138
139	if(nodes->nodes[end].id==id) /* End is correct */
140	return(&nodes->nodes[end]);
141	}
142
143	return(NULL);
144	}
145
146
147	/*++++++++++++++++++++++++++++++++++++++
148	Append a node to a newly created node list (unsorted).
149
150	Node *AppendNode Return a pointer to the new node.
151
152	NodesMem* nodes The set of nodes to process.
153
154	node_t id The node identification.
155
156	latlong_t latitude The latitude of the node.
157
158	latlong_t longitude The longitude of the node.
159	++++++++++++++++++++++++++++++++++++++*/
160
161	Node AppendNode(NodesMem nodes,node_t id,latlong_t latitude,latlong_t longitude)
162	{
163	/* Check that the array has enough space. */
164
165	if(nodes->number==nodes->alloced)
166	{
167	nodes->alloced+=INCREMENT_NODES;
168
169	nodes->nodes=(Nodes)realloc((void)nodes->nodes,sizeof(Nodes)+nodes->alloced*sizeof(Node));
170	}
171
172	/* Insert the node */
173
174	nodes->nodes->nodes[nodes->number].id=id;
175	nodes->nodes->nodes[nodes->number].latitude=latitude;
176	nodes->nodes->nodes[nodes->number].longitude=longitude;
177
178	nodes->number++;
179
180	nodes->sorted=0;
181
182	return(&nodes->nodes->nodes[nodes->number-1]);
183	}
184
185
186	/*++++++++++++++++++++++++++++++++++++++
187	Sort the node list.
188
189	NodesMem* nodes The set of nodes to process.
190	++++++++++++++++++++++++++++++++++++++*/
191
192	void SortNodeList(NodesMem* nodes)
193	{
194	int i,bin=0;
195
196	qsort(nodes->nodes->nodes,nodes->number,sizeof(Node),(int ()(const void,const void*))sort_by_id);
197
198	while(nodes->nodes->nodes[nodes->number-1].id==~0)
199	nodes->number--;
200
201	nodes->sorted=1;
202
203	/* Make it searchable */
204
205	nodes->nodes->number=nodes->number;
206
207	for(i=0;i<nodes->number;i++)
208	for(;bin<=(nodes->nodes->nodes[i].id%NBINS_NODES);bin++)
209	nodes->nodes->offset[bin]=i;
210
211	for(;bin<NBINS_NODES;bin++)
212	nodes->nodes->offset[bin]=nodes->number;
213	}
214
215
216	/*++++++++++++++++++++++++++++++++++++++
217	Sort the nodes into id order.
218
219	int sort_by_id Returns the comparison of the id fields.
220
221	Node *a The first Node.
222
223	Node *b The second Node.
224	++++++++++++++++++++++++++++++++++++++*/
225
226	static int sort_by_id(Node a,Node b)
227	{
228	node_t a_id=a->id;
229	node_t b_id=b->id;
230
231	int a_bin=a->id%NBINS_NODES;
232	int b_bin=b->id%NBINS_NODES;
233
234	if(a_bin!=b_bin)
235	return(a_bin-b_bin);
236
237	if(a_id<b_id)
238	return(-1);
239	else if(a_id>b_id)
240	return(1);
241	else /* if(a_id==b_id) */
242	return(0);
243	}
244
245
246	/*++++++++++++++++++++++++++++++++++++++
247	Remove any nodes that are not part of a way.
248
249	NodesMem *nodesmem The node list to create.
250
251	Nodes *nodes The complete node list.
252
253	Segments *segments The list of segments.
254	++++++++++++++++++++++++++++++++++++++*/
255
256	void RemoveNonWayNodes(NodesMem nodesmem,Nodes nodes,Segments *segments)
257	{
258	int i;
259	int inway=0,notinway=0;
260
261	for(i=0;i<nodes->number;i++)
262	{
263	Node *node=LookupNode(nodes,i);
264
265	if(FindFirstSegment(segments,node->id))
266	{
267	inway++;
268	AppendNode(nodesmem,node->id,node->latitude,node->longitude);
269	}
270	else
271	notinway++;
272
273	if(!((i+1)%10000))
274	{
275	printf("\rChecking: Nodes=%d in-Way=%d not-in-Way=%d",i+1,inway,notinway);
276	fflush(stdout);
277	}
278	}
279
280	printf("\rChecked: Nodes=%d in-Way=%d not-in-Way=%d \n",i,inway,notinway);
281	fflush(stdout);
282	}