trunk/src/segments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segments.c,v 1.26 2009-02-01 17:11:08 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"


/* Constants */

/*+ The array size increment for segments - expect ~8,000,000 segments. +*/
#define INCREMENT_SEGMENTS 1024*1024


/* Functions */

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


/*++++++++++++++++++++++++++++++++++++++
  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)
{
 void *data;
 Segments *segments;

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

 data=MapFile(filename);

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

 *segments=*((Segments*)data);

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

 segments->data =data;
 segments->segments=(Segment*)(data+(off_t)segments->segments);

 return(segments);
}


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

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

SegmentsX *NewSegmentList(void)
{
 SegmentsX *segmentsx;

 segmentsx=(SegmentsX*)malloc(sizeof(SegmentsX));

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

 segmentsx->xdata=(SegmentX*)malloc(segmentsx->alloced*sizeof(SegmentX));

 return(segmentsx);
}


/*++++++++++++++++++++++++++++++++++++++
  Free a segment list.

  SegmentsX *segmentsx The list to be freed.
  ++++++++++++++++++++++++++++++++++++++*/

void FreeSegmentList(SegmentsX *segmentsx)
{
 free(segmentsx->xdata);
 free(segmentsx);
}


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

  SegmentsX* segmentsx The set of segments to save.

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

void SaveSegmentList(SegmentsX* segmentsx,const char *filename)
{
 int i;
 int fd;
 Segments *segments=calloc(1,sizeof(Segments));

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

 /* Fill in a Segments structure with the offset of the real data in the file after
    the Segment structure itself. */

 segments->number=segmentsx->number;
 segments->data=NULL;
 segments->segments=(void*)sizeof(Segments);

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

 fd=OpenFile(filename);

 WriteFile(fd,segments,sizeof(Segments));

 for(i=0;i<segmentsx->number;i++)
    WriteFile(fd,&segmentsx->xdata[i].segment,sizeof(Segment));

 CloseFile(fd);

 /* Free the fake Segments */

 free(segments);
}


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

  SegmentX *FindFirstSegment Returns the first extended segment with the specified id.

  SegmentsX* segmentsx The set of segments to process.

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

SegmentX *FindFirstSegment(SegmentsX* segmentsx,node_t node)
{
 int start=0;
 int end=segmentsx->number-1;
 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<segmentsx->xdata[start].node1) /* Check key is not before start */
    return(NULL);
 else if(node>segmentsx->xdata[end].node1)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;                          /* Choose mid point */

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

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

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

 return(NULL);

 found:

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

 return(&segmentsx->xdata[found]);
}


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

  SegmentX *NextSegment Returns a pointer to the next segment with the same id.

  SegmentsX* segments The set of segments to process.

  SegmentX *segmentex The current segment.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentX *FindNextSegment(SegmentsX* segmentsx,SegmentX *segmentex)
{
 SegmentX *next=segmentex+1;

 if(IndexSegmentX(segmentsx,next)==segmentsx->number)
    return(NULL);

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

 return(NULL);
}
 
 
/*++++++++++++++++++++++++++++++++++++++
  Find the next segment with a particular starting node.

  Segment *NextSegment 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 *NextSegment(Segments* segments,Segment *segment)
{
 Segment *next=segment+1;

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

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

 return(NULL);
}
 
 
/*++++++++++++++++++++++++++++++++++++++
  Append a segment to a newly created segment list (unsorted).

  SegmentX *AppendSegment Returns the appended segment.

  SegmentsX* segmentsx The set of segments to process.

  node_t node1 The first node in the segment.

  node_t node2 The second node in the segment.

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

SegmentX *AppendSegment(SegmentsX* segmentsx,node_t node1,node_t node2,index_t way)
{
 /* Check that the array has enough space. */

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

    segmentsx->xdata=(SegmentX*)realloc((void*)segmentsx->xdata,segmentsx->alloced*sizeof(SegmentX));
   }

 /* Insert the segment */

 segmentsx->xdata[segmentsx->number].node1=node1;
 segmentsx->xdata[segmentsx->number].node2=node2;
 segmentsx->xdata[segmentsx->number].segment.way=way;
 segmentsx->xdata[segmentsx->number].segment.distance=0;

 segmentsx->number++;

 segmentsx->sorted=0;

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


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

  SegmentsX* segmentsx The set of segments to process.
  ++++++++++++++++++++++++++++++++++++++*/

void SortSegmentList(SegmentsX* segmentsx)
{
 qsort(segmentsx->xdata,segmentsx->number,sizeof(SegmentX),(int (*)(const void*,const void*))sort_by_id);

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

 segmentsx->sorted=1;
}


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

  int sort_by_id Returns the comparison of the node fields.

  SegmentX *a The first Segment.

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

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

 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
       return(1);
   }
}


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

  SegmentsX *segmentsx The segments to modify.
  ++++++++++++++++++++++++++++++++++++++*/

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

 for(i=0;i<segmentsx->number;i++)
   {
    if(segmentsx->xdata[i].node1==node1 && segmentsx->xdata[i].node2==node2)
      {
       duplicate++;
       segmentsx->xdata[i].node1=~0;
      }
    else if(segmentsx->xdata[i].node1==segmentsx->xdata[i].node2)
      {
       loop++;
       segmentsx->xdata[i].node1=~0;
      }

    node1=segmentsx->xdata[i].node1;
    node2=segmentsx->xdata[i].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",segmentsx->number,duplicate,loop);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Measure the segments.

  SegmentsX* segmentsx The set of segments to process.

  NodesX *nodesx The list of nodes to use.
  ++++++++++++++++++++++++++++++++++++++*/

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

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

 for(i=0;i<segmentsx->number;i++)
   {
    NodeX *node1=FindNode(nodesx,segmentsx->xdata[i].node1);
    NodeX *node2=FindNode(nodesx,segmentsx->xdata[i].node2);

    /* Set the distance but preserve the ONEWAY_OPPOSITE flag */

    segmentsx->xdata[i].segment.distance|=Distance(&node1->node,&node2->node);

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

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


/*++++++++++++++++++++++++++++++++++++++
  Fix the segment indexes to the nodes.

  SegmentsX* segmentsx The set of segments to process.

  NodesX *nodesx The list of nodes to use.

  SegmentsX* supersegmentsx The set of super-segments to append.
  ++++++++++++++++++++++++++++++++++++++*/

void FixupSegments(SegmentsX* segmentsx,NodesX *nodesx,SegmentsX* supersegmentsx)
{
 int i,j,n;

 assert(segmentsx->sorted);   /* Must be sorted */
 assert(supersegmentsx->sorted);   /* Must be sorted */

 for(i=0;i<segmentsx->number;i++)
   {
    NodeX *node1=FindNode(nodesx,segmentsx->xdata[i].node1);
    NodeX *node2=FindNode(nodesx,segmentsx->xdata[i].node2);

    segmentsx->xdata[i].segment.node1=IndexNodeX(nodesx,node1)|SUPER_FLAG;
    segmentsx->xdata[i].segment.node2=IndexNodeX(nodesx,node2);

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

 printf("\rFixed Segments: Segments=%d \n",segmentsx->number);
 fflush(stdout);

 for(i=0;i<supersegmentsx->number;i++)
   {
    NodeX *node1=FindNode(nodesx,supersegmentsx->xdata[i].node1);
    NodeX *node2=FindNode(nodesx,supersegmentsx->xdata[i].node2);

    supersegmentsx->xdata[i].segment.node1=IndexNodeX(nodesx,node1);
    supersegmentsx->xdata[i].segment.node2=IndexNodeX(nodesx,node2)|SUPER_FLAG;

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

 printf("\rFixed Super-Segments: Super-Segments=%d \n",supersegmentsx->number);
 fflush(stdout);

 n=segmentsx->number;

 for(i=0,j=0;i<n;i++)
   {
    while(j<supersegmentsx->number)
      {
       if(segmentsx->xdata[i].node1==supersegmentsx->xdata[j].node1 &&
          segmentsx->xdata[i].node2==supersegmentsx->xdata[j].node2)
         {
          segmentsx->xdata[i].segment.node2|=SUPER_FLAG;
          j++;
          break;
         }
       else if(segmentsx->xdata[i].node1==supersegmentsx->xdata[j].node1 &&
               segmentsx->xdata[i].node2>supersegmentsx->xdata[j].node2)
         {
          SegmentX *supersegmentex=AppendSegment(segmentsx,supersegmentsx->xdata[j].node1,supersegmentsx->xdata[j].node2,supersegmentsx->xdata[j].segment.way);

          supersegmentex->segment.node1=supersegmentsx->xdata[j].segment.node1;
          supersegmentex->segment.node2=supersegmentsx->xdata[j].segment.node2;
          supersegmentex->segment.distance=supersegmentsx->xdata[j].segment.distance;
         }
       else if(segmentsx->xdata[i].node1>supersegmentsx->xdata[j].node1)
         {
          SegmentX *supersegmentex=AppendSegment(segmentsx,supersegmentsx->xdata[j].node1,supersegmentsx->xdata[j].node2,supersegmentsx->xdata[j].segment.way);

          supersegmentex->segment.node1=supersegmentsx->xdata[j].segment.node1;
          supersegmentex->segment.node2=supersegmentsx->xdata[j].segment.node2;
          supersegmentex->segment.distance=supersegmentsx->xdata[j].segment.distance;
         }
       else
          break;

       j++;
      }

    if(!((i+1)%10000))
      {
       printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsx->number);
       fflush(stdout);
      }
   }

 printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsx->number,segmentsx->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);
}


/*++++++++++++++++++++++++++++++++++++++
  Calculate the duration of segment.

  duration_t Duration Returns the duration of travel between the nodes.

  Segment *segment The segment to traverse.

  Way *way The way that the segment belongs to.

  Profile *profile The profile of the transport being used.
  ++++++++++++++++++++++++++++++++++++++*/

duration_t Duration(Segment *segment,Way *way,Profile *profile)
{
 speed_t    speed=profile->speed[HIGHWAY(way->type)];
 distance_t distance=DISTANCE(segment->distance);

 return distance_speed_to_duration(distance,speed);
}
1	amb	2	/***************************************
2	amb	97	$Header: /home/amb/CVS/routino/src/segments.c,v 1.26 2009-02-01 17:11:08 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	96	/* Constants */
25
26			/+ The array size increment for segments - expect ~8,000,000 segments. +/
27			#define INCREMENT_SEGMENTS 1024*1024
28
29
30	amb	23	/* Functions */
31	amb	2
32	amb	97	static int sort_by_id(SegmentX a,SegmentX b);
33	amb	2
34	amb	8
35	amb	23	/*++++++++++++++++++++++++++++++++++++++
36	amb	2	Load in a segment list from a file.
37
38	amb	23	Segments* SaveSegmentList Returns the segment list that has just been loaded.
39
40	amb	2	const char *filename The name of the file to load.
41			++++++++++++++++++++++++++++++++++++++*/
42
43	amb	23	Segments LoadSegmentList(const char filename)
44	amb	2	{
45	amb	88	void *data;
46			Segments *segments;
47
48			segments=(Segments*)malloc(sizeof(Segments));
49
50			data=MapFile(filename);
51
52			/* Copy the Segments structure from the loaded data */
53
54			segments=((Segments*)data);
55
56			/* Adjust the pointers in the Segments structure. */
57
58			segments->data =data;
59			segments->segments=(Segment*)(data+(off_t)segments->segments);
60
61			return(segments);
62	amb	2	}
63
64
65			/*++++++++++++++++++++++++++++++++++++++
66	amb	97	Allocate a new segment list.
67
68			SegmentsX *NewSegmentList Returns the segment list.
69			++++++++++++++++++++++++++++++++++++++*/
70
71			SegmentsX *NewSegmentList(void)
72			{
73			SegmentsX *segmentsx;
74
75			segmentsx=(SegmentsX*)malloc(sizeof(SegmentsX));
76
77			segmentsx->sorted=0;
78			segmentsx->alloced=INCREMENT_SEGMENTS;
79			segmentsx->number=0;
80
81			segmentsx->xdata=(SegmentX)malloc(segmentsx->allocedsizeof(SegmentX));
82
83			return(segmentsx);
84			}
85
86
87			/*++++++++++++++++++++++++++++++++++++++
88			Free a segment list.
89
90			SegmentsX *segmentsx The list to be freed.
91			++++++++++++++++++++++++++++++++++++++*/
92
93			void FreeSegmentList(SegmentsX *segmentsx)
94			{
95			free(segmentsx->xdata);
96			free(segmentsx);
97			}
98
99
100			/*++++++++++++++++++++++++++++++++++++++
101	amb	2	Save the segment list to a file.
102
103	amb	97	SegmentsX* segmentsx The set of segments to save.
104	amb	23
105	amb	2	const char *filename The name of the file to save.
106			++++++++++++++++++++++++++++++++++++++*/
107
108	amb	97	void SaveSegmentList(SegmentsX* segmentsx,const char *filename)
109	amb	2	{
110	amb	88	int i;
111			int fd;
112			Segments *segments=calloc(1,sizeof(Segments));
113	amb	2
114	amb	97	assert(segmentsx->sorted); /* Must be sorted */
115	amb	23
116	amb	88	/* Fill in a Segments structure with the offset of the real data in the file after
117			the Segment structure itself. */
118
119	amb	97	segments->number=segmentsx->number;
120	amb	88	segments->data=NULL;
121			segments->segments=(void*)sizeof(Segments);
122
123			/* Write out the Segments structure and then the real data. */
124
125			fd=OpenFile(filename);
126
127	amb	97	WriteFile(fd,segments,sizeof(Segments));
128	amb	88
129	amb	97	for(i=0;i<segmentsx->number;i++)
130			WriteFile(fd,&segmentsx->xdata[i].segment,sizeof(Segment));
131	amb	88
132	amb	97	CloseFile(fd);
133	amb	88
134	amb	89	/* Free the fake Segments */
135	amb	88
136	amb	23	free(segments);
137	amb	2	}
138
139
140			/*++++++++++++++++++++++++++++++++++++++
141			Find the first segment with a particular starting node.
142
143	amb	97	SegmentX *FindFirstSegment Returns the first extended segment with the specified id.
144	amb	2
145	amb	97	SegmentsX* segmentsx The set of segments to process.
146	amb	23
147	amb	2	node_t node The node to look for.
148			++++++++++++++++++++++++++++++++++++++*/
149
150	amb	97	SegmentX FindFirstSegment(SegmentsX segmentsx,node_t node)
151	amb	2	{
152	amb	88	int start=0;
153	amb	97	int end=segmentsx->number-1;
154	amb	2	int mid;
155			int found;
156
157			/* Binary search - search key exact match only is required.
158			*
159			* # <- start \| Check mid and move start or end if it doesn't match
160			* # \|
161			* # \| Since an exact match is wanted we can set end=mid-1
162			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
163			* # \|
164			* # \| Eventually either end=start or end=start+1 and one of
165			* # <- end \| start or end is the wanted one.
166			*/
167
168	amb	23	if(end<start) /* There are no nodes */
169	amb	89	return(NULL);
170	amb	97	else if(node<segmentsx->xdata[start].node1) /* Check key is not before start */
171	amb	89	return(NULL);
172	amb	97	else if(node>segmentsx->xdata[end].node1) /* Check key is not after end */
173	amb	89	return(NULL);
174	amb	2	else
175			{
176			do
177			{
178	amb	23	mid=(start+end)/2; /* Choose mid point */
179	amb	2
180	amb	97	if(segmentsx->xdata[mid].node1<node) /* Mid point is too low */
181	amb	2	start=mid;
182	amb	97	else if(segmentsx->xdata[mid].node1>node) /* Mid point is too high */
183	amb	2	end=mid;
184	amb	23	else /* Mid point is correct */
185	amb	2	{found=mid; goto found;}
186			}
187			while((end-start)>1);
188
189	amb	97	if(segmentsx->xdata[start].node1==node) /* Start is correct */
190	amb	2	{found=start; goto found;}
191
192	amb	97	if(segmentsx->xdata[end].node1==node) /* End is correct */
193	amb	2	{found=end; goto found;}
194			}
195
196	amb	89	return(NULL);
197	amb	2
198			found:
199
200	amb	97	while(found>0 && segmentsx->xdata[found-1].node1==node)
201	amb	2	found--;
202
203	amb	97	return(&segmentsx->xdata[found]);
204	amb	2	}
205
206
207			/*++++++++++++++++++++++++++++++++++++++
208			Find the next segment with a particular starting node.
209
210	amb	97	SegmentX *NextSegment Returns a pointer to the next segment with the same id.
211	amb	89
212	amb	97	SegmentsX* segments The set of segments to process.
213	amb	89
214	amb	97	SegmentX *segmentex The current segment.
215	amb	89	++++++++++++++++++++++++++++++++++++++*/
216
217	amb	97	SegmentX FindNextSegment(SegmentsX segmentsx,SegmentX *segmentex)
218	amb	89	{
219	amb	97	SegmentX *next=segmentex+1;
220	amb	89
221	amb	97	if(IndexSegmentX(segmentsx,next)==segmentsx->number)
222	amb	89	return(NULL);
223
224			if(next->node1==segmentex->node1)
225			return(next);
226
227			return(NULL);
228			}
229
230
231			/*++++++++++++++++++++++++++++++++++++++
232			Find the next segment with a particular starting node.
233
234	amb	88	Segment *NextSegment Returns a pointer to the next segment with the same id.
235	amb	2
236	amb	23	Segments* segments The set of segments to process.
237
238	amb	2	Segment *segment The current segment.
239			++++++++++++++++++++++++++++++++++++++*/
240
241	amb	88	Segment NextSegment(Segments segments,Segment *segment)
242	amb	2	{
243			Segment *next=segment+1;
244
245	amb	89	if(IndexSegment(segments,next)==segments->number)
246	amb	23	return(NULL);
247	amb	2
248	amb	90	if(NODE(next->node1)==NODE(segment->node1))
249	amb	2	return(next);
250
251			return(NULL);
252	amb	89	}
253	amb	88
254
255	amb	2	/*++++++++++++++++++++++++++++++++++++++
256			Append a segment to a newly created segment list (unsorted).
257
258	amb	97	SegmentX *AppendSegment Returns the appended segment.
259	amb	31
260	amb	97	SegmentsX* segmentsx The set of segments to process.
261	amb	23
262	amb	2	node_t node1 The first node in the segment.
263
264			node_t node2 The second node in the segment.
265
266	amb	96	index_t way The index of the way that the pair of segments are connected by.
267	amb	2	++++++++++++++++++++++++++++++++++++++*/
268
269	amb	97	SegmentX AppendSegment(SegmentsX segmentsx,node_t node1,node_t node2,index_t way)
270	amb	2	{
271	amb	23	/* Check that the array has enough space. */
272	amb	8
273	amb	97	if(segmentsx->number==segmentsx->alloced)
274	amb	4	{
275	amb	97	segmentsx->alloced+=INCREMENT_SEGMENTS;
276	amb	4
277	amb	97	segmentsx->xdata=(SegmentX)realloc((void)segmentsx->xdata,segmentsx->alloced*sizeof(SegmentX));
278	amb	4	}
279
280			/* Insert the segment */
281
282	amb	97	segmentsx->xdata[segmentsx->number].node1=node1;
283			segmentsx->xdata[segmentsx->number].node2=node2;
284			segmentsx->xdata[segmentsx->number].segment.way=way;
285			segmentsx->xdata[segmentsx->number].segment.distance=0;
286	amb	2
287	amb	97	segmentsx->number++;
288	amb	2
289	amb	97	segmentsx->sorted=0;
290	amb	31
291	amb	97	return(&segmentsx->xdata[segmentsx->number-1]);
292	amb	2	}
293
294
295			/*++++++++++++++++++++++++++++++++++++++
296			Sort the segment list.
297	amb	23
298	amb	97	SegmentsX* segmentsx The set of segments to process.
299	amb	2	++++++++++++++++++++++++++++++++++++++*/
300
301	amb	97	void SortSegmentList(SegmentsX* segmentsx)
302	amb	2	{
303	amb	97	qsort(segmentsx->xdata,segmentsx->number,sizeof(SegmentX),(int ()(const void,const void*))sort_by_id);
304	amb	39
305	amb	97	while(segmentsx->xdata[segmentsx->number-1].node1==~0)
306			segmentsx->number--;
307	amb	8
308	amb	97	segmentsx->sorted=1;
309	amb	2	}
310
311
312			/*++++++++++++++++++++++++++++++++++++++
313			Sort the segments into id order.
314
315			int sort_by_id Returns the comparison of the node fields.
316
317	amb	97	SegmentX *a The first Segment.
318	amb	2
319	amb	97	SegmentX *b The second Segment.
320	amb	2	++++++++++++++++++++++++++++++++++++++*/
321
322	amb	97	static int sort_by_id(SegmentX a,SegmentX b)
323	amb	2	{
324			node_t a_id1=a->node1,a_id2=a->node2;
325			node_t b_id1=b->node1,b_id2=b->node2;
326
327	amb	39	if(a_id1<b_id1)
328			return(-1);
329			else if(a_id1>b_id1)
330			return(1);
331			else /* if(a_id1==b_id1) */
332			{
333			if(a_id2<b_id2)
334			return(-1);
335	amb	88	else
336	amb	39	return(1);
337			}
338	amb	2	}
339
340
341			/*++++++++++++++++++++++++++++++++++++++
342	amb	39	Remove bad segments (zero length or duplicated).
343
344	amb	97	SegmentsX *segmentsx The segments to modify.
345	amb	39	++++++++++++++++++++++++++++++++++++++*/
346
347	amb	97	void RemoveBadSegments(SegmentsX *segmentsx)
348	amb	39	{
349			int i;
350			int duplicate=0,loop=0;
351			node_t node1=~0,node2=~0;
352
353	amb	97	for(i=0;i<segmentsx->number;i++)
354	amb	39	{
355	amb	97	if(segmentsx->xdata[i].node1==node1 && segmentsx->xdata[i].node2==node2)
356	amb	39	{
357			duplicate++;
358	amb	97	segmentsx->xdata[i].node1=~0;
359	amb	39	}
360	amb	97	else if(segmentsx->xdata[i].node1==segmentsx->xdata[i].node2)
361	amb	39	{
362			loop++;
363	amb	97	segmentsx->xdata[i].node1=~0;
364	amb	39	}
365
366	amb	97	node1=segmentsx->xdata[i].node1;
367			node2=segmentsx->xdata[i].node2;
368	amb	39
369			if(!((i+1)%10000))
370			{
371			printf("\rChecking: Segments=%d Duplicate=%d Loop=%d",i+1,duplicate,loop);
372			fflush(stdout);
373			}
374			}
375
376	amb	97	printf("\rChecked: Segments=%d Duplicate=%d Loop=%d \n",segmentsx->number,duplicate,loop);
377	amb	39	fflush(stdout);
378			}
379
380
381			/*++++++++++++++++++++++++++++++++++++++
382	amb	89	Measure the segments.
383	amb	23
384	amb	97	SegmentsX* segmentsx The set of segments to process.
385	amb	23
386	amb	97	NodesX *nodesx The list of nodes to use.
387	amb	8	++++++++++++++++++++++++++++++++++++++*/
388	amb	2
389	amb	97	void MeasureSegments(SegmentsX* segmentsx,NodesX *nodesx)
390	amb	8	{
391			int i;
392	amb	2
393	amb	97	assert(segmentsx->sorted); /* Must be sorted */
394	amb	8
395	amb	97	for(i=0;i<segmentsx->number;i++)
396	amb	8	{
397	amb	97	NodeX *node1=FindNode(nodesx,segmentsx->xdata[i].node1);
398			NodeX *node2=FindNode(nodesx,segmentsx->xdata[i].node2);
399	amb	8
400	amb	82	/* Set the distance but preserve the ONEWAY_OPPOSITE flag */
401	amb	8
402	amb	97	segmentsx->xdata[i].segment.distance\|=Distance(&node1->node,&node2->node);
403	amb	69
404	amb	54	if(!((i+1)%10000))
405			{
406	amb	89	printf("\rMeasuring Segments: Segments=%d",i+1);
407			fflush(stdout);
408			}
409			}
410
411	amb	97	printf("\rMeasured Segments: Segments=%d \n",segmentsx->number);
412	amb	89	fflush(stdout);
413			}
414
415
416			/*++++++++++++++++++++++++++++++++++++++
417			Fix the segment indexes to the nodes.
418
419	amb	97	SegmentsX* segmentsx The set of segments to process.
420	amb	89
421	amb	97	NodesX *nodesx The list of nodes to use.
422	amb	90
423	amb	97	SegmentsX* supersegmentsx The set of super-segments to append.
424	amb	89	++++++++++++++++++++++++++++++++++++++*/
425
426	amb	97	void FixupSegments(SegmentsX* segmentsx,NodesX nodesx,SegmentsX supersegmentsx)
427	amb	89	{
428	amb	90	int i,j,n;
429	amb	89
430	amb	97	assert(segmentsx->sorted); /* Must be sorted */
431			assert(supersegmentsx->sorted); /* Must be sorted */
432	amb	89
433	amb	97	for(i=0;i<segmentsx->number;i++)
434	amb	89	{
435	amb	97	NodeX *node1=FindNode(nodesx,segmentsx->xdata[i].node1);
436			NodeX *node2=FindNode(nodesx,segmentsx->xdata[i].node2);
437	amb	89
438	amb	97	segmentsx->xdata[i].segment.node1=IndexNodeX(nodesx,node1)\|SUPER_FLAG;
439			segmentsx->xdata[i].segment.node2=IndexNodeX(nodesx,node2);
440	amb	89
441			if(!((i+1)%10000))
442			{
443	amb	88	printf("\rFixing Segments: Segments=%d",i+1);
444	amb	54	fflush(stdout);
445			}
446	amb	8	}
447	amb	54
448	amb	97	printf("\rFixed Segments: Segments=%d \n",segmentsx->number);
449	amb	54	fflush(stdout);
450	amb	90
451	amb	97	for(i=0;i<supersegmentsx->number;i++)
452	amb	90	{
453	amb	97	NodeX *node1=FindNode(nodesx,supersegmentsx->xdata[i].node1);
454			NodeX *node2=FindNode(nodesx,supersegmentsx->xdata[i].node2);
455	amb	90
456	amb	97	supersegmentsx->xdata[i].segment.node1=IndexNodeX(nodesx,node1);
457			supersegmentsx->xdata[i].segment.node2=IndexNodeX(nodesx,node2)\|SUPER_FLAG;
458	amb	90
459			if(!((i+1)%10000))
460			{
461			printf("\rFixing Super-Segments: Super-Segments=%d",i+1);
462			fflush(stdout);
463			}
464			}
465
466	amb	97	printf("\rFixed Super-Segments: Super-Segments=%d \n",supersegmentsx->number);
467	amb	90	fflush(stdout);
468
469	amb	97	n=segmentsx->number;
470	amb	90
471			for(i=0,j=0;i<n;i++)
472			{
473	amb	97	while(j<supersegmentsx->number)
474	amb	90	{
475	amb	97	if(segmentsx->xdata[i].node1==supersegmentsx->xdata[j].node1 &&
476			segmentsx->xdata[i].node2==supersegmentsx->xdata[j].node2)
477	amb	90	{
478	amb	97	segmentsx->xdata[i].segment.node2\|=SUPER_FLAG;
479	amb	90	j++;
480			break;
481			}
482	amb	97	else if(segmentsx->xdata[i].node1==supersegmentsx->xdata[j].node1 &&
483			segmentsx->xdata[i].node2>supersegmentsx->xdata[j].node2)
484	amb	90	{
485	amb	97	SegmentX *supersegmentex=AppendSegment(segmentsx,supersegmentsx->xdata[j].node1,supersegmentsx->xdata[j].node2,supersegmentsx->xdata[j].segment.way);
486	amb	90
487	amb	97	supersegmentex->segment.node1=supersegmentsx->xdata[j].segment.node1;
488			supersegmentex->segment.node2=supersegmentsx->xdata[j].segment.node2;
489			supersegmentex->segment.distance=supersegmentsx->xdata[j].segment.distance;
490	amb	90	}
491	amb	97	else if(segmentsx->xdata[i].node1>supersegmentsx->xdata[j].node1)
492	amb	90	{
493	amb	97	SegmentX *supersegmentex=AppendSegment(segmentsx,supersegmentsx->xdata[j].node1,supersegmentsx->xdata[j].node2,supersegmentsx->xdata[j].segment.way);
494	amb	90
495	amb	97	supersegmentex->segment.node1=supersegmentsx->xdata[j].segment.node1;
496			supersegmentex->segment.node2=supersegmentsx->xdata[j].segment.node2;
497			supersegmentex->segment.distance=supersegmentsx->xdata[j].segment.distance;
498	amb	90	}
499			else
500			break;
501
502			j++;
503			}
504
505			if(!((i+1)%10000))
506			{
507	amb	97	printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsx->number);
508	amb	90	fflush(stdout);
509			}
510			}
511
512	amb	97	printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsx->number,segmentsx->number);
513	amb	90	fflush(stdout);
514	amb	8	}
515
516
517			/*++++++++++++++++++++++++++++++++++++++
518			Calculate the distance between two nodes.
519
520			distance_t Distance Returns the distance between the nodes.
521
522	amb	2	Node *node1 The starting node.
523
524			Node *node2 The end node.
525			++++++++++++++++++++++++++++++++++++++*/
526
527	amb	8	distance_t Distance(Node node1,Node node2)
528	amb	2	{
529			double radiant = M_PI / 180;
530
531			double dlon = radiant * (node1->longitude - node2->longitude);
532			double dlat = radiant * (node1->latitude - node2->latitude);
533
534			double a1,a2,a,sa,c,d;
535
536			if(dlon==0 && dlat==0)
537			return 0;
538
539			a1 = sin (dlat / 2);
540			a2 = sin (dlon / 2);
541			a = (a1 * a1) + cos (node1->latitude * radiant) * cos (node2->latitude * radiant) * a2 * a2;
542			sa = sqrt (a);
543			if (sa <= 1.0)
544			{c = 2 * asin (sa);}
545			else
546			{c = 2 * asin (1.0);}
547	amb	5	d = 6378.137 * c;
548	amb	2
549	amb	5	return km_to_distance(d);
550	amb	2	}
551	amb	63
552
553			/*++++++++++++++++++++++++++++++++++++++
554			Calculate the duration of segment.
555
556			duration_t Duration Returns the duration of travel between the nodes.
557
558			Segment *segment The segment to traverse.
559
560			Way *way The way that the segment belongs to.
561
562	amb	82	Profile *profile The profile of the transport being used.
563	amb	63	++++++++++++++++++++++++++++++++++++++*/
564
565	amb	82	duration_t Duration(Segment segment,Way way,Profile *profile)
566	amb	63	{
567	amb	82	speed_t speed=profile->speed[HIGHWAY(way->type)];
568	amb	90	distance_t distance=DISTANCE(segment->distance);
569	amb	63
570	amb	86	return distance_speed_to_duration(distance,speed);
571	amb	63	}