trunk/src/ways.c

/***************************************
 $Header: /home/amb/CVS/routino/src/ways.c,v 1.5 2009-01-10 15:59:59 amb Exp $

 Way 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 "functions.h"
#include "ways.h"


/*+ A temporary variable used when sorting +*/
static char **sort_names;

/* Functions */

static int sort_by_id(Way *a,Way *b);
static int sort_by_name(Way *a,Way *b);


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

  WaysMem *NewWayList Returns the way list.
  ++++++++++++++++++++++++++++++++++++++*/

WaysMem *NewWayList(void)
{
 WaysMem *ways;

 ways=(WaysMem*)malloc(sizeof(WaysMem));

 ways->alloced=INCREMENT_WAYS;
 ways->number=0;
 ways->number_str=0;
 ways->sorted=0;

 ways->ways=(Ways*)malloc(sizeof(Ways)+ways->alloced*sizeof(Way));
 ways->names=(char**)malloc(ways->alloced*sizeof(char*));

 return(ways);
}


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

  Ways* LoadWayList Returns the way list.

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

Ways *LoadWayList(const char *filename)
{
 return((Ways*)MapFile(filename));
}


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

  Ways* SaveWayList Returns the way list that has just been saved.

  WaysMem* ways The set of ways to save.

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

Ways *SaveWayList(WaysMem* ways,const char *filename)
{
#ifdef NBINS_WAYS
 int i,bin=0;
#endif

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

 ways->ways->number=ways->number;

#ifdef NBINS_WAYS
 for(i=0;i<ways->number;i++)
    for(;bin<=(ways->ways->ways[i].id%NBINS_WAYS);bin++)
       ways->ways->offset[bin]=i;

 for(;bin<=NBINS_WAYS;bin++)
    ways->ways->offset[bin]=ways->number;
#endif

 if(WriteFile(filename,(void*)ways->ways,sizeof(Ways)-sizeof(ways->ways->ways)+(ways->number+ways->number_str)*sizeof(Way)))
    assert(0);

 free(ways->names);
 free(ways->ways);
 free(ways);

 return(LoadWayList(filename));
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular way.

  Way *FindWay Returns a pointer to the way with the specified id.

  Ways* ways The set of ways to process.

  way_t id The way id to look for.
  ++++++++++++++++++++++++++++++++++++++*/

Way *FindWay(Ways* ways,way_t id)
{
#ifdef NBINS_WAYS
 int bin=id%NBINS_WAYS;
 int start=ways->offset[bin];
 int end=ways->offset[bin+1]-1;
#else
 int start=0;
 int end=ways->number-1;
#endif
 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 ways */
    return(NULL);
 else if(id<ways->ways[start].id) /* Check key is not before start */
    return(NULL);
 else if(id>ways->ways[end].id)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;             /* Choose mid point */

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

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

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

 return(NULL);
}


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

  Way *AppendWay Returns the newly appended way.

  WaysMem* ways The set of ways to process.

  way_t id The way identification.

  const char *name The name or reference of the way.

  speed_t speed The speed on the way.
  ++++++++++++++++++++++++++++++++++++++*/

Way *AppendWay(WaysMem* ways,way_t id,const char *name)
{
 /* Check that the array has enough space. */

 if(ways->number==ways->alloced)
   {
    ways->alloced+=INCREMENT_WAYS;

    ways->ways=(Ways*)realloc((void*)ways->ways,sizeof(Ways)+ways->alloced*sizeof(Way));
    ways->names=(char**)realloc((void*)ways->names,ways->alloced*sizeof(char*));
   }

 assert(!ways->sorted);         /* Must be sorted */

 /* Insert the way */

 ways->names[ways->number]=strcpy((char*)malloc(strlen(name)+1),name);

 ways->ways->ways[ways->number].id=id;
 ways->ways->ways[ways->number].name=ways->number;

 ways->number++;

 ways->sorted=0;

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


/*++++++++++++++++++++++++++++++++++++++
  Sort the way list.

  WaysMem* ways The set of ways to process.
  ++++++++++++++++++++++++++++++++++++++*/

void SortWayList(WaysMem* ways)
{
 char *name=NULL;
 int i;

 /* Sort the ways by name */

 sort_names=ways->names;
 qsort(ways->ways->ways,ways->number,sizeof(Way),(int (*)(const void*,const void*))sort_by_name);

 /* Setup the offsets for the names in the way array */

 for(i=0;i<ways->number;i++)
   {
    if(name && !strcmp(name,ways->names[ways->ways->ways[i].name])) /* Same name */
      {
       free(ways->names[ways->ways->ways[i].name]);
       ways->ways->ways[i].name=ways->ways->ways[i-1].name;
      }
    else                                            /* Different name */
      {
       name=ways->names[ways->ways->ways[i].name];

       if((ways->number+ways->number_str+strlen(name)/sizeof(Way)+1)>=ways->alloced)
         {
          ways->alloced+=INCREMENT_WAYS;

          ways->ways=(Ways*)realloc((void*)ways->ways,sizeof(Ways)+ways->alloced*sizeof(Way));
         }

       strcpy((char*)&ways->ways->ways[ways->number+ways->number_str],name);
       free(name);

       ways->ways->ways[i].name=ways->number+ways->number_str;
       name=(char*)&ways->ways->ways[ways->ways->ways[i].name];

       ways->number_str+=strlen(name)/sizeof(Way)+1;
      }
   }

 /* Sort the ways by id */

 qsort(ways->ways->ways,ways->number,sizeof(Way),(int (*)(const void*,const void*))sort_by_id);

 ways->sorted=1;
}


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

  int sort_by_id Returns the comparison of the id fields.

  Way *a The first Way.

  Way *b The second Way.
  ++++++++++++++++++++++++++++++++++++++*/

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

#ifdef NBINS_WAYS
 int a_bin=a->id%NBINS_WAYS;
 int b_bin=b->id%NBINS_WAYS;

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

 return(a_id-b_id);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the ways into name order.

  int sort_by_name Returns the comparison of the name fields.

  Way *a The first Way.

  Way *b The second Way.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_name(Way *a,Way *b)
{
 char *a_name=sort_names[a->name];
 char *b_name=sort_names[b->name];

 return(strcmp(a_name,b_name));
}


/*++++++++++++++++++++++++++++++++++++++
  Return the name of the way.

  const char *WayName Returns the name.

  Ways* ways The set of ways to process.

  Way *way The way whose name is to be found.
  ++++++++++++++++++++++++++++++++++++++*/

const char *WayName(Ways* ways,Way *way)
{
 return((char*)&ways->ways[way->name]);
}


/*++++++++++++++++++++++++++++++++++++++
  Decide on the type of a way given the "highway" parameter.

  WayType TypeOfWay Returns the type of the way.

  const char *type The string containing the type of the way.
  ++++++++++++++++++++++++++++++++++++++*/

WayType TypeOfWay(const char *type)
{
 switch(*type)
   {
   case 'b':
    if(!strcmp(type,"byway")) return(Way_Track);
    if(!strcmp(type,"bridleway")) return(Way_Bridleway);
    return(Way_Unknown);

   case 'c':
    if(!strcmp(type,"cycleway")) return(Way_Cycleway);
    return(Way_Unknown);

   case 'f':
    if(!strcmp(type,"footway")) return(Way_Footway);
    return(Way_Unknown);

   case 'm':
    if(!strncmp(type,"motorway",8)) return(Way_Motorway);
    if(!strcmp(type,"minor")) return(Way_Unclassfied);
    return(Way_Unknown);

   case 'p':
    if(!strncmp(type,"primary",7)) return(Way_Primary);
    if(!strcmp(type,"path")) return(Way_Footway);
    if(!strcmp(type,"pedestrian")) return(Way_Footway);
    return(Way_Unknown);

   case 'r':
    if(!strcmp(type,"road")) return(Way_Unclassfied);
    if(!strcmp(type,"residential")) return(Way_Residential);
    return(Way_Unknown);

   case 's':
    if(!strncmp(type,"secondary",9)) return(Way_Secondary);
    if(!strcmp(type,"service")) return(Way_Service);
    if(!strcmp(type,"steps")) return(Way_Footway);
    return(Way_Unknown);

   case 't':
    if(!strncmp(type,"trunk",5)) return(Way_Trunk);
    if(!strcmp(type,"tertiary")) return(Way_Tertiary);
    if(!strcmp(type,"track")) return(Way_Track);
    return(Way_Unknown);

   case 'u':
    if(!strcmp(type,"unclassified")) return(Way_Unclassfied);
    if(!strcmp(type,"unsurfaced")) return(Way_Track);
    if(!strcmp(type,"unpaved")) return(Way_Track);
    return(Way_Unknown);

   case 'w':
    if(!strcmp(type,"walkway")) return(Way_Footway);
    return(Way_Unknown);

   default:
    ;
   }

 return(Way_Unknown);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/ways.c,v 1.5 2009-01-10 15:59:59 amb Exp $
3
4	Way 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
19	#include "functions.h"
20	#include "ways.h"
21
22
23	/+ A temporary variable used when sorting +/
24	static char **sort_names;
25
26	/* Functions */
27
28	static int sort_by_id(Way a,Way b);
29	static int sort_by_name(Way a,Way b);
30
31
32	/*++++++++++++++++++++++++++++++++++++++
33	Allocate a new way list.
34
35	WaysMem *NewWayList Returns the way list.
36	++++++++++++++++++++++++++++++++++++++*/
37
38	WaysMem *NewWayList(void)
39	{
40	WaysMem *ways;
41
42	ways=(WaysMem*)malloc(sizeof(WaysMem));
43
44	ways->alloced=INCREMENT_WAYS;
45	ways->number=0;
46	ways->number_str=0;
47	ways->sorted=0;
48
49	ways->ways=(Ways)malloc(sizeof(Ways)+ways->allocedsizeof(Way));
50	ways->names=(char*)malloc(ways->allocedsizeof(char*));
51
52	return(ways);
53	}
54
55
56	/*++++++++++++++++++++++++++++++++++++++
57	Load in a way list from a file.
58
59	Ways* LoadWayList Returns the way list.
60
61	const char *filename The name of the file to load.
62	++++++++++++++++++++++++++++++++++++++*/
63
64	Ways LoadWayList(const char filename)
65	{
66	return((Ways*)MapFile(filename));
67	}
68
69
70	/*++++++++++++++++++++++++++++++++++++++
71	Save the way list to a file.
72
73	Ways* SaveWayList Returns the way list that has just been saved.
74
75	WaysMem* ways The set of ways to save.
76
77	const char *filename The name of the file to save.
78	++++++++++++++++++++++++++++++++++++++*/
79
80	Ways SaveWayList(WaysMem ways,const char *filename)
81	{
82	#ifdef NBINS_WAYS
83	int i,bin=0;
84	#endif
85
86	assert(ways->sorted); /* Must be sorted */
87
88	ways->ways->number=ways->number;
89
90	#ifdef NBINS_WAYS
91	for(i=0;i<ways->number;i++)
92	for(;bin<=(ways->ways->ways[i].id%NBINS_WAYS);bin++)
93	ways->ways->offset[bin]=i;
94
95	for(;bin<=NBINS_WAYS;bin++)
96	ways->ways->offset[bin]=ways->number;
97	#endif
98
99	if(WriteFile(filename,(void)ways->ways,sizeof(Ways)-sizeof(ways->ways->ways)+(ways->number+ways->number_str)sizeof(Way)))
100	assert(0);
101
102	free(ways->names);
103	free(ways->ways);
104	free(ways);
105
106	return(LoadWayList(filename));
107	}
108
109
110	/*++++++++++++++++++++++++++++++++++++++
111	Find a particular way.
112
113	Way *FindWay Returns a pointer to the way with the specified id.
114
115	Ways* ways The set of ways to process.
116
117	way_t id The way id to look for.
118	++++++++++++++++++++++++++++++++++++++*/
119
120	Way FindWay(Ways ways,way_t id)
121	{
122	#ifdef NBINS_WAYS
123	int bin=id%NBINS_WAYS;
124	int start=ways->offset[bin];
125	int end=ways->offset[bin+1]-1;
126	#else
127	int start=0;
128	int end=ways->number-1;
129	#endif
130	int mid;
131
132	/* Binary search - search key exact match only is required.
133	*
134	* # <- start \| Check mid and move start or end if it doesn't match
135	* # \|
136	* # \| Since an exact match is wanted we can set end=mid-1
137	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
138	* # \|
139	* # \| Eventually either end=start or end=start+1 and one of
140	* # <- end \| start or end is the wanted one.
141	*/
142
143	if(end<start) /* There are no ways */
144	return(NULL);
145	else if(id<ways->ways[start].id) /* Check key is not before start */
146	return(NULL);
147	else if(id>ways->ways[end].id) /* Check key is not after end */
148	return(NULL);
149	else
150	{
151	do
152	{
153	mid=(start+end)/2; /* Choose mid point */
154
155	if(ways->ways[mid].id<id) /* Mid point is too low */
156	start=mid+1;
157	else if(ways->ways[mid].id>id) /* Mid point is too high */
158	end=mid-1;
159	else /* Mid point is correct */
160	return(&ways->ways[mid]);
161	}
162	while((end-start)>1);
163
164	if(ways->ways[start].id==id) /* Start is correct */
165	return(&ways->ways[start]);
166
167	if(ways->ways[end].id==id) /* End is correct */
168	return(&ways->ways[end]);
169	}
170
171	return(NULL);
172	}
173
174
175	/*++++++++++++++++++++++++++++++++++++++
176	Append a way to a newly created way list (unsorted).
177
178	Way *AppendWay Returns the newly appended way.
179
180	WaysMem* ways The set of ways to process.
181
182	way_t id The way identification.
183
184	const char *name The name or reference of the way.
185
186	speed_t speed The speed on the way.
187	++++++++++++++++++++++++++++++++++++++*/
188
189	Way AppendWay(WaysMem ways,way_t id,const char *name)
190	{
191	/* Check that the array has enough space. */
192
193	if(ways->number==ways->alloced)
194	{
195	ways->alloced+=INCREMENT_WAYS;
196
197	ways->ways=(Ways)realloc((void)ways->ways,sizeof(Ways)+ways->alloced*sizeof(Way));
198	ways->names=(char*)realloc((void)ways->names,ways->allocedsizeof(char));
199	}
200
201	assert(!ways->sorted); /* Must be sorted */
202
203	/* Insert the way */
204
205	ways->names[ways->number]=strcpy((char*)malloc(strlen(name)+1),name);
206
207	ways->ways->ways[ways->number].id=id;
208	ways->ways->ways[ways->number].name=ways->number;
209
210	ways->number++;
211
212	ways->sorted=0;
213
214	return(&ways->ways->ways[ways->number-1]);
215	}
216
217
218	/*++++++++++++++++++++++++++++++++++++++
219	Sort the way list.
220
221	WaysMem* ways The set of ways to process.
222	++++++++++++++++++++++++++++++++++++++*/
223
224	void SortWayList(WaysMem* ways)
225	{
226	char *name=NULL;
227	int i;
228
229	/* Sort the ways by name */
230
231	sort_names=ways->names;
232	qsort(ways->ways->ways,ways->number,sizeof(Way),(int ()(const void,const void*))sort_by_name);
233
234	/* Setup the offsets for the names in the way array */
235
236	for(i=0;i<ways->number;i++)
237	{
238	if(name && !strcmp(name,ways->names[ways->ways->ways[i].name])) /* Same name */
239	{
240	free(ways->names[ways->ways->ways[i].name]);
241	ways->ways->ways[i].name=ways->ways->ways[i-1].name;
242	}
243	else /* Different name */
244	{
245	name=ways->names[ways->ways->ways[i].name];
246
247	if((ways->number+ways->number_str+strlen(name)/sizeof(Way)+1)>=ways->alloced)
248	{
249	ways->alloced+=INCREMENT_WAYS;
250
251	ways->ways=(Ways)realloc((void)ways->ways,sizeof(Ways)+ways->alloced*sizeof(Way));
252	}
253
254	strcpy((char*)&ways->ways->ways[ways->number+ways->number_str],name);
255	free(name);
256
257	ways->ways->ways[i].name=ways->number+ways->number_str;
258	name=(char*)&ways->ways->ways[ways->ways->ways[i].name];
259
260	ways->number_str+=strlen(name)/sizeof(Way)+1;
261	}
262	}
263
264	/* Sort the ways by id */
265
266	qsort(ways->ways->ways,ways->number,sizeof(Way),(int ()(const void,const void*))sort_by_id);
267
268	ways->sorted=1;
269	}
270
271
272	/*++++++++++++++++++++++++++++++++++++++
273	Sort the ways into id order.
274
275	int sort_by_id Returns the comparison of the id fields.
276
277	Way *a The first Way.
278
279	Way *b The second Way.
280	++++++++++++++++++++++++++++++++++++++*/
281
282	static int sort_by_id(Way a,Way b)
283	{
284	way_t a_id=a->id;
285	way_t b_id=b->id;
286
287	#ifdef NBINS_WAYS
288	int a_bin=a->id%NBINS_WAYS;
289	int b_bin=b->id%NBINS_WAYS;
290
291	if(a_bin!=b_bin)
292	return(a_bin-b_bin);
293	#endif
294
295	return(a_id-b_id);
296	}
297
298
299	/*++++++++++++++++++++++++++++++++++++++
300	Sort the ways into name order.
301
302	int sort_by_name Returns the comparison of the name fields.
303
304	Way *a The first Way.
305
306	Way *b The second Way.
307	++++++++++++++++++++++++++++++++++++++*/
308
309	static int sort_by_name(Way a,Way b)
310	{
311	char *a_name=sort_names[a->name];
312	char *b_name=sort_names[b->name];
313
314	return(strcmp(a_name,b_name));
315	}
316
317
318	/*++++++++++++++++++++++++++++++++++++++
319	Return the name of the way.
320
321	const char *WayName Returns the name.
322
323	Ways* ways The set of ways to process.
324
325	Way *way The way whose name is to be found.
326	++++++++++++++++++++++++++++++++++++++*/
327
328	const char WayName(Ways ways,Way *way)
329	{
330	return((char*)&ways->ways[way->name]);
331	}
332
333
334	/*++++++++++++++++++++++++++++++++++++++
335	Decide on the type of a way given the "highway" parameter.
336
337	WayType TypeOfWay Returns the type of the way.
338
339	const char *type The string containing the type of the way.
340	++++++++++++++++++++++++++++++++++++++*/
341
342	WayType TypeOfWay(const char *type)
343	{
344	switch(*type)
345	{
346	case 'b':
347	if(!strcmp(type,"byway")) return(Way_Track);
348	if(!strcmp(type,"bridleway")) return(Way_Bridleway);
349	return(Way_Unknown);
350
351	case 'c':
352	if(!strcmp(type,"cycleway")) return(Way_Cycleway);
353	return(Way_Unknown);
354
355	case 'f':
356	if(!strcmp(type,"footway")) return(Way_Footway);
357	return(Way_Unknown);
358
359	case 'm':
360	if(!strncmp(type,"motorway",8)) return(Way_Motorway);
361	if(!strcmp(type,"minor")) return(Way_Unclassfied);
362	return(Way_Unknown);
363
364	case 'p':
365	if(!strncmp(type,"primary",7)) return(Way_Primary);
366	if(!strcmp(type,"path")) return(Way_Footway);
367	if(!strcmp(type,"pedestrian")) return(Way_Footway);
368	return(Way_Unknown);
369
370	case 'r':
371	if(!strcmp(type,"road")) return(Way_Unclassfied);
372	if(!strcmp(type,"residential")) return(Way_Residential);
373	return(Way_Unknown);
374
375	case 's':
376	if(!strncmp(type,"secondary",9)) return(Way_Secondary);
377	if(!strcmp(type,"service")) return(Way_Service);
378	if(!strcmp(type,"steps")) return(Way_Footway);
379	return(Way_Unknown);
380
381	case 't':
382	if(!strncmp(type,"trunk",5)) return(Way_Trunk);
383	if(!strcmp(type,"tertiary")) return(Way_Tertiary);
384	if(!strcmp(type,"track")) return(Way_Track);
385	return(Way_Unknown);
386
387	case 'u':
388	if(!strcmp(type,"unclassified")) return(Way_Unclassfied);
389	if(!strcmp(type,"unsurfaced")) return(Way_Track);
390	if(!strcmp(type,"unpaved")) return(Way_Track);
391	return(Way_Unknown);
392
393	case 'w':
394	if(!strcmp(type,"walkway")) return(Way_Footway);
395	return(Way_Unknown);
396
397	default:
398	;
399	}
400
401	return(Way_Unknown);
402	}