trunk/src/segments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segments.c,v 1.8 2009-01-11 09:28:31 amb Exp $

 Segment 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 <math.h>
#include <stdlib.h>

#include "segments.h"
#include "functions.h"


/* Functions */

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


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

  SegmentsMem *NewSegmentList Returns the segment list.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentsMem *NewSegmentList(void)
{
 SegmentsMem *segments;

 segments=(SegmentsMem*)malloc(sizeof(SegmentsMem));

 segments->alloced=INCREMENT_SEGMENTS;
 segments->number=0;
 segments->sorted=0;

 segments->segments=(Segments*)malloc(sizeof(Segments)+segments->alloced*sizeof(Segment));

 return(segments);
}


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

  Segments* SaveSegmentList Returns the segment list that has just been loaded.

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

Segments *LoadSegmentList(const char *filename)
{
 return((Segments*)MapFile(filename));
}


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

  Segments* SaveSegmentList Returns the segment list that has just been saved.

  SegmentsMem* segments The set of segments to save.

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

Segments *SaveSegmentList(SegmentsMem* segments,const char *filename)
{
#ifdef NBINS_SEGMENTS
 int i,bin=0;
#endif

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

 segments->segments->number=segments->number;

#ifdef NBINS_SEGMENTS
 for(i=0;i<segments->number;i++)
    for(;bin<=(segments->segments->segments[i].node1%NBINS_SEGMENTS);bin++)
       segments->segments->offset[bin]=i;

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

 if(WriteFile(filename,(void*)segments->segments,sizeof(Segments)-sizeof(segments->segments->segments)+segments->number*sizeof(Segment)))
    assert(0);

 free(segments->segments);
 free(segments);

 return(LoadSegmentList(filename));
}


/*++++++++++++++++++++++++++++++++++++++
  Find the first segment with a particular starting node.

  Segment *FindFirstSegment Returns a pointer to the first segment with the specified id.

  Segments* segments The set of segments to process.

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

Segment *FindFirstSegment(Segments* segments,node_t node)
{
#ifdef NBINS_SEGMENTS
 int bin=node%NBINS_SEGMENTS;
 int start=segments->offset[bin];
 int end=segments->offset[bin+1]-1;
#else
 int start=0;
 int end=segments->number-1;
#endif
 int mid;
 int found;

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

       if(segments->segments[mid].node1<node)      /* Mid point is too low */
          start=mid;
       else if(segments->segments[mid].node1>node) /* Mid point is too high */
          end=mid;
       else                                        /* Mid point is correct */
         {found=mid; goto found;}
      }
    while((end-start)>1);

    if(segments->segments[start].node1==node)      /* Start is correct */
         {found=start; goto found;}

    if(segments->segments[end].node1==node)        /* End is correct */
         {found=end; goto found;}
   }

 return(NULL);

 found:

 while(found>0 && segments->segments[found-1].node1==node)
    found--;

 return(&segments->segments[found]);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the next segment with a particular starting node.

  Segment *FindNextSegment Returns a pointer to the next segment with the same id.

  Segments* segments The set of segments to process.

  Segment *segment The current segment.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *FindNextSegment(Segments* segments,Segment *segment)
{
 Segment *next=segment+1;

 if((next-segments->segments)==segments->number)
    return(NULL);

 if(next->node1==segment->node1)
    return(next);

 return(NULL);
}


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

  Segment *AppendSegment Returns the appended segment.

  SegmentsMem* segments The set of segments to process.

  node_t node1 The first node in the segment.

  node_t node2 The second node in the segment.

  way_t way The way that the pair of segments are connected by.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *AppendSegment(SegmentsMem* segments,node_t node1,node_t node2,way_t way)
{
 /* Check that the array has enough space. */

 if(segments->number==segments->alloced)
   {
    segments->alloced+=INCREMENT_SEGMENTS;

    segments->segments=(Segments*)realloc((void*)segments->segments,sizeof(Segments)+segments->alloced*sizeof(Segment));
   }

 /* Insert the segment */

 segments->segments->segments[segments->number].node1=node1;
 segments->segments->segments[segments->number].node2=node2;
 segments->segments->segments[segments->number].way=way;
 segments->segments->segments[segments->number].distance=0;
 segments->segments->segments[segments->number].duration=0;

 segments->number++;

 segments->sorted=0;

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


/*++++++++++++++++++++++++++++++++++++++
  Sort the segment list.

  SegmentsMem* segments The set of segments to process.
  ++++++++++++++++++++++++++++++++++++++*/

void SortSegmentList(SegmentsMem* segments)
{
 qsort(segments->segments->segments,segments->number,sizeof(Segment),(int (*)(const void*,const void*))sort_by_id);

 segments->sorted=1;
}


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

  int sort_by_id Returns the comparison of the node fields.

  Segment *a The first Segment.

  Segment *b The second Segment.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_id(Segment *a,Segment *b)
{
 node_t a_id1=a->node1,a_id2=a->node2;
 node_t b_id1=b->node1,b_id2=b->node2;

#ifdef NBINS_SEGMENTS
 int a_bin=a->node1%NBINS_SEGMENTS;
 int b_bin=b->node1%NBINS_SEGMENTS;

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

 if(a_id1==b_id1)
    return(a_id2-b_id2);
 else
    return(a_id1-b_id1);
}


/*++++++++++++++++++++++++++++++++++++++
  Assign the lengths and durations to all of the segments.

  SegmentsMem* segments The set of segments to process.

  Nodes *nodes The list of nodes to use.

  Ways *ways The list of ways to use.
  ++++++++++++++++++++++++++++++++++++++*/

void FixupSegmentLengths(SegmentsMem* segments,Nodes *nodes,Ways *ways)
{
 int i;

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

 for(i=0;i<segments->number;i++)
   {
    speed_t    speed;
    distance_t distance;
    duration_t duration;
    Node *node1=FindNode(nodes,segments->segments->segments[i].node1);
    Node *node2=FindNode(nodes,segments->segments->segments[i].node2);
    Way  *way=FindWay(ways,segments->segments->segments[i].way);

    if(way->limit)
       speed=way->limit;
    else
       speed=way->speed;

    if(way->type&Way_NOTROUTABLE || Way_TYPE(way->type)>Way_HighestRoutable)
      {
       distance=(distance_short_t)~0;
       duration=(duration_short_t)~0;
      }
    else
      {
       distance=Distance(node1,node2);
       duration=hours_to_duration(distance_to_km(distance)/speed);

       if(distance>(distance_short_t)~0)
         {
          fprintf(stderr,"\nSegment too long (%d->%d) = %.1f km\n",node1->id,node2->id,distance_to_km(distance));
          distance=(distance_short_t)~0;
         }

       if(duration>(duration_short_t)~0)
         {
          fprintf(stderr,"\nSegment too long (%d->%d) = %.1f mins\n",node1->id,node2->id,duration_to_minutes(duration));
          duration=(duration_short_t)~0;
         }
      }

    segments->segments->segments[i].distance=distance;
    segments->segments->segments[i].duration=duration;
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Calculate the distance between two nodes.

  distance_t Distance Returns the distance between the nodes.

  Node *node1 The starting node.

  Node *node2 The end node.
  ++++++++++++++++++++++++++++++++++++++*/

distance_t Distance(Node *node1,Node *node2)
{
 double radiant = M_PI / 180;

 double dlon = radiant * (node1->longitude - node2->longitude);
 double dlat = radiant * (node1->latitude  - node2->latitude);

 double a1,a2,a,sa,c,d;

 if(dlon==0 && dlat==0)
   return 0;

 a1 = sin (dlat / 2);
 a2 = sin (dlon / 2);
 a = (a1 * a1) + cos (node1->latitude * radiant) * cos (node2->latitude * radiant) * a2 * a2;
 sa = sqrt (a);
 if (sa <= 1.0)
   {c = 2 * asin (sa);}
 else
   {c = 2 * asin (1.0);}
 d = 6378.137 * c;

 return km_to_distance(d);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/segments.c,v 1.8 2009-01-11 09:28:31 amb Exp $
3
4	Segment 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 <math.h>
17	#include <stdlib.h>
18
19	#include "segments.h"
20	#include "functions.h"
21
22
23	/* Functions */
24
25	static int sort_by_id(Segment a,Segment b);
26
27
28	/*++++++++++++++++++++++++++++++++++++++
29	Allocate a new segment list.
30
31	SegmentsMem *NewSegmentList Returns the segment list.
32	++++++++++++++++++++++++++++++++++++++*/
33
34	SegmentsMem *NewSegmentList(void)
35	{
36	SegmentsMem *segments;
37
38	segments=(SegmentsMem*)malloc(sizeof(SegmentsMem));
39
40	segments->alloced=INCREMENT_SEGMENTS;
41	segments->number=0;
42	segments->sorted=0;
43
44	segments->segments=(Segments)malloc(sizeof(Segments)+segments->allocedsizeof(Segment));
45
46	return(segments);
47	}
48
49
50	/*++++++++++++++++++++++++++++++++++++++
51	Load in a segment list from a file.
52
53	Segments* SaveSegmentList Returns the segment list that has just been loaded.
54
55	const char *filename The name of the file to load.
56	++++++++++++++++++++++++++++++++++++++*/
57
58	Segments LoadSegmentList(const char filename)
59	{
60	return((Segments*)MapFile(filename));
61	}
62
63
64	/*++++++++++++++++++++++++++++++++++++++
65	Save the segment list to a file.
66
67	Segments* SaveSegmentList Returns the segment list that has just been saved.
68
69	SegmentsMem* segments The set of segments to save.
70
71	const char *filename The name of the file to save.
72	++++++++++++++++++++++++++++++++++++++*/
73
74	Segments SaveSegmentList(SegmentsMem segments,const char *filename)
75	{
76	#ifdef NBINS_SEGMENTS
77	int i,bin=0;
78	#endif
79
80	assert(segments->sorted); /* Must be sorted */
81
82	segments->segments->number=segments->number;
83
84	#ifdef NBINS_SEGMENTS
85	for(i=0;i<segments->number;i++)
86	for(;bin<=(segments->segments->segments[i].node1%NBINS_SEGMENTS);bin++)
87	segments->segments->offset[bin]=i;
88
89	for(;bin<=NBINS_SEGMENTS;bin++)
90	segments->segments->offset[bin]=segments->number;
91	#endif
92
93	if(WriteFile(filename,(void)segments->segments,sizeof(Segments)-sizeof(segments->segments->segments)+segments->numbersizeof(Segment)))
94	assert(0);
95
96	free(segments->segments);
97	free(segments);
98
99	return(LoadSegmentList(filename));
100	}
101
102
103	/*++++++++++++++++++++++++++++++++++++++
104	Find the first segment with a particular starting node.
105
106	Segment *FindFirstSegment Returns a pointer to the first segment with the specified id.
107
108	Segments* segments The set of segments to process.
109
110	node_t node The node to look for.
111	++++++++++++++++++++++++++++++++++++++*/
112
113	Segment FindFirstSegment(Segments segments,node_t node)
114	{
115	#ifdef NBINS_SEGMENTS
116	int bin=node%NBINS_SEGMENTS;
117	int start=segments->offset[bin];
118	int end=segments->offset[bin+1]-1;
119	#else
120	int start=0;
121	int end=segments->number-1;
122	#endif
123	int mid;
124	int found;
125
126	/* Binary search - search key exact match only is required.
127	*
128	* # <- start \| Check mid and move start or end if it doesn't match
129	* # \|
130	* # \| Since an exact match is wanted we can set end=mid-1
131	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
132	* # \|
133	* # \| Eventually either end=start or end=start+1 and one of
134	* # <- end \| start or end is the wanted one.
135	*/
136
137	if(end<start) /* There are no nodes */
138	return(NULL);
139	else if(node<segments->segments[start].node1) /* Check key is not before start */
140	return(NULL);
141	else if(node>segments->segments[end].node1) /* Check key is not after end */
142	return(NULL);
143	else
144	{
145	do
146	{
147	mid=(start+end)/2; /* Choose mid point */
148
149	if(segments->segments[mid].node1<node) /* Mid point is too low */
150	start=mid;
151	else if(segments->segments[mid].node1>node) /* Mid point is too high */
152	end=mid;
153	else /* Mid point is correct */
154	{found=mid; goto found;}
155	}
156	while((end-start)>1);
157
158	if(segments->segments[start].node1==node) /* Start is correct */
159	{found=start; goto found;}
160
161	if(segments->segments[end].node1==node) /* End is correct */
162	{found=end; goto found;}
163	}
164
165	return(NULL);
166
167	found:
168
169	while(found>0 && segments->segments[found-1].node1==node)
170	found--;
171
172	return(&segments->segments[found]);
173	}
174
175
176	/*++++++++++++++++++++++++++++++++++++++
177	Find the next segment with a particular starting node.
178
179	Segment *FindNextSegment Returns a pointer to the next segment with the same id.
180
181	Segments* segments The set of segments to process.
182
183	Segment *segment The current segment.
184	++++++++++++++++++++++++++++++++++++++*/
185
186	Segment FindNextSegment(Segments segments,Segment *segment)
187	{
188	Segment *next=segment+1;
189
190	if((next-segments->segments)==segments->number)
191	return(NULL);
192
193	if(next->node1==segment->node1)
194	return(next);
195
196	return(NULL);
197	}
198
199
200	/*++++++++++++++++++++++++++++++++++++++
201	Append a segment to a newly created segment list (unsorted).
202
203	Segment *AppendSegment Returns the appended segment.
204
205	SegmentsMem* segments The set of segments to process.
206
207	node_t node1 The first node in the segment.
208
209	node_t node2 The second node in the segment.
210
211	way_t way The way that the pair of segments are connected by.
212	++++++++++++++++++++++++++++++++++++++*/
213
214	Segment AppendSegment(SegmentsMem segments,node_t node1,node_t node2,way_t way)
215	{
216	/* Check that the array has enough space. */
217
218	if(segments->number==segments->alloced)
219	{
220	segments->alloced+=INCREMENT_SEGMENTS;
221
222	segments->segments=(Segments)realloc((void)segments->segments,sizeof(Segments)+segments->alloced*sizeof(Segment));
223	}
224
225	/* Insert the segment */
226
227	segments->segments->segments[segments->number].node1=node1;
228	segments->segments->segments[segments->number].node2=node2;
229	segments->segments->segments[segments->number].way=way;
230	segments->segments->segments[segments->number].distance=0;
231	segments->segments->segments[segments->number].duration=0;
232
233	segments->number++;
234
235	segments->sorted=0;
236
237	return(&segments->segments->segments[segments->number-1]);
238	}
239
240
241	/*++++++++++++++++++++++++++++++++++++++
242	Sort the segment list.
243
244	SegmentsMem* segments The set of segments to process.
245	++++++++++++++++++++++++++++++++++++++*/
246
247	void SortSegmentList(SegmentsMem* segments)
248	{
249	qsort(segments->segments->segments,segments->number,sizeof(Segment),(int ()(const void,const void*))sort_by_id);
250
251	segments->sorted=1;
252	}
253
254
255	/*++++++++++++++++++++++++++++++++++++++
256	Sort the segments into id order.
257
258	int sort_by_id Returns the comparison of the node fields.
259
260	Segment *a The first Segment.
261
262	Segment *b The second Segment.
263	++++++++++++++++++++++++++++++++++++++*/
264
265	static int sort_by_id(Segment a,Segment b)
266	{
267	node_t a_id1=a->node1,a_id2=a->node2;
268	node_t b_id1=b->node1,b_id2=b->node2;
269
270	#ifdef NBINS_SEGMENTS
271	int a_bin=a->node1%NBINS_SEGMENTS;
272	int b_bin=b->node1%NBINS_SEGMENTS;
273
274	if(a_bin!=b_bin)
275	return(a_bin-b_bin);
276	#endif
277
278	if(a_id1==b_id1)
279	return(a_id2-b_id2);
280	else
281	return(a_id1-b_id1);
282	}
283
284
285	/*++++++++++++++++++++++++++++++++++++++
286	Assign the lengths and durations to all of the segments.
287
288	SegmentsMem* segments The set of segments to process.
289
290	Nodes *nodes The list of nodes to use.
291
292	Ways *ways The list of ways to use.
293	++++++++++++++++++++++++++++++++++++++*/
294
295	void FixupSegmentLengths(SegmentsMem* segments,Nodes nodes,Ways ways)
296	{
297	int i;
298
299	assert(segments->sorted); /* Must be sorted */
300
301	for(i=0;i<segments->number;i++)
302	{
303	speed_t speed;
304	distance_t distance;
305	duration_t duration;
306	Node *node1=FindNode(nodes,segments->segments->segments[i].node1);
307	Node *node2=FindNode(nodes,segments->segments->segments[i].node2);
308	Way *way=FindWay(ways,segments->segments->segments[i].way);
309
310	if(way->limit)
311	speed=way->limit;
312	else
313	speed=way->speed;
314
315	if(way->type&Way_NOTROUTABLE \|\| Way_TYPE(way->type)>Way_HighestRoutable)
316	{
317	distance=(distance_short_t)~0;
318	duration=(duration_short_t)~0;
319	}
320	else
321	{
322	distance=Distance(node1,node2);
323	duration=hours_to_duration(distance_to_km(distance)/speed);
324
325	if(distance>(distance_short_t)~0)
326	{
327	fprintf(stderr,"\nSegment too long (%d->%d) = %.1f km\n",node1->id,node2->id,distance_to_km(distance));
328	distance=(distance_short_t)~0;
329	}
330
331	if(duration>(duration_short_t)~0)
332	{
333	fprintf(stderr,"\nSegment too long (%d->%d) = %.1f mins\n",node1->id,node2->id,duration_to_minutes(duration));
334	duration=(duration_short_t)~0;
335	}
336	}
337
338	segments->segments->segments[i].distance=distance;
339	segments->segments->segments[i].duration=duration;
340	}
341	}
342
343
344	/*++++++++++++++++++++++++++++++++++++++
345	Calculate the distance between two nodes.
346
347	distance_t Distance Returns the distance between the nodes.
348
349	Node *node1 The starting node.
350
351	Node *node2 The end node.
352	++++++++++++++++++++++++++++++++++++++*/
353
354	distance_t Distance(Node node1,Node node2)
355	{
356	double radiant = M_PI / 180;
357
358	double dlon = radiant * (node1->longitude - node2->longitude);
359	double dlat = radiant * (node1->latitude - node2->latitude);
360
361	double a1,a2,a,sa,c,d;
362
363	if(dlon==0 && dlat==0)
364	return 0;
365
366	a1 = sin (dlat / 2);
367	a2 = sin (dlon / 2);
368	a = (a1 * a1) + cos (node1->latitude * radiant) * cos (node2->latitude * radiant) * a2 * a2;
369	sa = sqrt (a);
370	if (sa <= 1.0)
371	{c = 2 * asin (sa);}
372	else
373	{c = 2 * asin (1.0);}
374	d = 6378.137 * c;
375
376	return km_to_distance(d);
377	}