trunk/src/segments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segments.c,v 1.29 2009-02-04 18:26:29 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);

 if(!data)
    return(NULL);

 /* 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 *FindFirstSegmentX 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 *FindFirstSegmentX(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 *FindNextSegmentX Returns a pointer to the next segment with the same id.

  SegmentsX* segmentss The set of segments to process.

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

SegmentX *FindNextSegmentX(SegmentsX* segmentsx,SegmentX *segmentx)
{
 SegmentX *next=segmentx+1;

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

 if(next->node1==segmentx->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 segment list.

  Segment *AppendSegmentX 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.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *AppendSegment(SegmentsX* segmentsx,node_t node1,node_t node2)
{
 /* 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.distance=0;

 segmentsx->number++;

 segmentsx->sorted=0;

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


/*++++++++++++++++++++++++++++++++++++++
  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=FindNodeX(nodesx,segmentsx->xdata[i].node1);
    NodeX *node2=FindNodeX(nodesx,segmentsx->xdata[i].node2);

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

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

    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=FindNodeX(nodesx,segmentsx->xdata[i].node1);
    NodeX *node2=FindNodeX(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=FindNodeX(nodesx,supersegmentsx->xdata[i].node1);
    NodeX *node2=FindNodeX(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)
         {
          Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->xdata[j].node1,supersegmentsx->xdata[j].node2);

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

          *supersegment=supersegmentsx->xdata[j].segment;
         }
       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 locations.

  float Distance Returns the distance between the locations.

  float lat1 The latitude of the first location.

  float lon1 The longitude of the first location.

  float lat2 The latitude of the second location.

  float lon2 The longitude of the second location.
  ++++++++++++++++++++++++++++++++++++++*/

float Distance(float lat1,float lon1,float lat2,float lon2)
{
 double radiant = M_PI / 180;

 double dlon = radiant * (lon1 - lon2);
 double dlat = radiant * (lat1 - lat2);

 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 (lat1 * radiant) * cos (lat2 * 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 d;
}


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

  distance_t DistanceX Returns the distance between the extended nodes.

  NodeX *nodex1 The starting node.

  NodeX *nodex2 The end node.
  ++++++++++++++++++++++++++++++++++++++*/

distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
{
 double radiant = M_PI / 180;

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