trunk/src/segments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segments.c,v 1.12 2009-01-20 17:37:20 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 "nodes.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)
{
 assert(segments->sorted);      /* Must be sorted */

 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->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)
{
#ifdef NBINS_SEGMENTS
 int i,bin=0;
#endif

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

 while(segments->segments->segments[segments->number-1].node1==~0)
    segments->number--;

 segments->sorted=1;

 /* Make it searchable */

 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
}


/*++++++++++++++++++++++++++++++++++++++
  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(-1);
 else if(a_id1>b_id1)
    return(1);
 else /* if(a_id1==b_id1) */
   {
    if(a_id2<b_id2)
       return(-1);
    else if(a_id2>b_id2)
       return(1);
    else
       return(0);
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Remove bad segments (zero length or duplicated).

  SegmentsMem *segments The segments to modify.
  ++++++++++++++++++++++++++++++++++++++*/

void RemoveBadSegments(SegmentsMem *segments)
{
 int i;
 int duplicate=0,loop=0;
 node_t node1=~0,node2=~0;

 for(i=0;i<segments->number;i++)
   {
    Segment *segment=&segments->segments->segments[i];

    if(segment->node1==node1 && segment->node2==node2)
      {
       duplicate++;
       segment->node1=~0;
      }
    else if(segment->node1==segment->node2)
      {
       loop++;
       segment->node1=~0;
      }

    node1=segment->node1;
    node2=segment->node2;

    if(!((i+1)%10000))
      {
       printf("\rChecking: Segments=%d Duplicate=%d Loop=%d",i+1,duplicate,loop);
       fflush(stdout);
      }
   }

 printf("\rChecked: Segments=%d Duplicate=%d Loop=%d  \n",segments->number,duplicate,loop);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  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++)
   {
    Node *node1=FindNode(nodes,segments->segments->segments[i].node1);
    Node *node2=FindNode(nodes,segments->segments->segments[i].node2);

    if(segments->segments->segments[i].distance!=INVALID_DISTANCE)
       segments->segments->segments[i].distance=Distance(node1,node2);

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

 printf("\rMeasured Segments: Segments=%d \n",segments->number);
 fflush(stdout);
}


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