trunk/src/segmentsx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.15 2009-06-30 18:32:42 amb Exp $

 Extended Segment data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008,2009 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#include <assert.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#include "types.h"
#include "functions.h"
#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.h"


/* Constants */

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


/* Functions */

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


/*++++++++++++++++++++++++++++++++++++++
  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->xnumber=0;
 segmentsx->number=0;

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

 segmentsx->sdata=NULL;

 return(segmentsx);
}


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

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

void FreeSegmentList(SegmentsX *segmentsx)
{
 if(segmentsx->sdata)
    free(segmentsx->sdata);
 free(segmentsx->xdata);
 free(segmentsx->ndata);
 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<segments->number;i++)
   {
    WriteFile(fd,&segmentsx->sdata[i],sizeof(Segment));

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

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

 CloseFile(fd);

 /* Free the fake Segments */

 free(segments);
}


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

  SegmentX **FindFirstSegmentX Returns a pointer to 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;

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

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

       if(segmentsx->ndata[mid]->node1<node)      /* Mid point is too low */
          start=mid;
       else if(segmentsx->ndata[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->ndata[start]->node1==node)      /* Start is correct */
         {found=start; goto found;}

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

 return(NULL);

 found:

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

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


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

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

  SegmentsX* segmentsx The set of segments to process.

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

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

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

 if((*next)->node1==(*segmentx)->node1)
    return(next);

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

  SegmentsX* segmentsx The set of segments to process.

  way_t way The way that the segment belongs to.

  node_t node1 The first node in the segment.

  node_t node2 The second node in the segment.
  ++++++++++++++++++++++++++++++++++++++*/

void AppendSegment(SegmentsX* segmentsx,way_t way,node_t node1,node_t node2,distance_t distance)
{
 /* Check that the array has enough space. */

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

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

 /* Insert the segment */

 segmentsx->xdata[segmentsx->xnumber].way=way;
 segmentsx->xdata[segmentsx->xnumber].node1=node1;
 segmentsx->xdata[segmentsx->xnumber].node2=node2;
 segmentsx->xdata[segmentsx->xnumber].distance=distance;

 segmentsx->xnumber++;

 segmentsx->sorted=0;
}


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

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

void SortSegmentList(SegmentsX* segmentsx)
{
 int i;

 printf("Sorting Segments"); fflush(stdout);

 /* Allocate the arrays of pointers */

 if(segmentsx->sorted)
    segmentsx->ndata=realloc(segmentsx->ndata,segmentsx->xnumber*sizeof(SegmentX*));
 else
    segmentsx->ndata=malloc(segmentsx->xnumber*sizeof(SegmentX*));

 segmentsx->number=0;

 for(i=0;i<segmentsx->xnumber;i++)
    if(segmentsx->xdata[i].node1!=NO_NODE)
      {
       segmentsx->ndata[segmentsx->number]=&segmentsx->xdata[i];
       segmentsx->number++;
      }

 qsort(segmentsx->ndata,segmentsx->number,sizeof(SegmentX*),(int (*)(const void*,const void*))sort_by_id_and_distance);

 segmentsx->sorted=1;

 printf("\rSorted Segments \n"); fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the segments into id order and then distance order.

  int sort_by_id_and_distance Returns the comparison of the node fields.

  SegmentX **a The first Segment.

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

static int sort_by_id_and_distance(SegmentX **a,SegmentX **b)
{
 node_t a_id1=(*a)->node1;
 node_t b_id1=(*b)->node1;

 if(a_id1<b_id1)
    return(-1);
 else if(a_id1>b_id1)
    return(1);
 else /* if(a_id1==b_id1) */
   {
    node_t a_id2=(*a)->node2;
    node_t b_id2=(*b)->node2;

    if(a_id2<b_id2)
       return(-1);
    else if(a_id2>b_id2)
       return(1);
    else
      {
       distance_t a_distance=DISTANCE((*a)->distance);
       distance_t b_distance=DISTANCE((*b)->distance);

       if(a_distance<b_distance)
          return(-1);
       else if(a_distance>b_distance)
          return(1);
       else
          return(0);
      }
   }
}


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

  NodesX *nodesx The nodes to check.

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

void RemoveBadSegments(NodesX *nodesx,SegmentsX *segmentsx)
{
 int i;
 int duplicate=0,loop=0,missing=0;

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

 for(i=0;i<segmentsx->number;i++)
   {
    if(i && segmentsx->ndata[i]->node1==segmentsx->ndata[i-1]->node1 &&
            segmentsx->ndata[i]->node2==segmentsx->ndata[i-1]->node2)
      {
       duplicate++;
       segmentsx->ndata[i-1]->node1=NO_NODE;
      }
    else if(segmentsx->ndata[i]->node1==segmentsx->ndata[i]->node2)
      {
       loop++;
       segmentsx->ndata[i]->node1=NO_NODE;
      }
    else if(!FindNodeX(nodesx,segmentsx->ndata[i]->node1) ||
            !FindNodeX(nodesx,segmentsx->ndata[i]->node2))
      {
       missing++;
       segmentsx->ndata[i]->node1=NO_NODE;
      }

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

 printf("\rChecked: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d \n",segmentsx->number,duplicate,loop,missing);
 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->ndata[i]->node1);
    NodeX *node2=FindNodeX(nodesx,segmentsx->ndata[i]->node2);

    /* Set the distance but preserve the ONEWAY_* flags */

    segmentsx->ndata[i]->distance|=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);
}


/*++++++++++++++++++++++++++++++++++++++
  Make the segments all point the same way (node1<node2).

  SegmentsX* segmentsx The set of segments to process.

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

void RotateSegments(SegmentsX* segmentsx,NodesX *nodesx)
{
 int i,rotated=0;

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

 for(i=0;i<segmentsx->number;i++)
   {
    if(segmentsx->ndata[i]->node1>segmentsx->ndata[i]->node2)
      {
       segmentsx->ndata[i]->node1^=segmentsx->ndata[i]->node2;
       segmentsx->ndata[i]->node2^=segmentsx->ndata[i]->node1;
       segmentsx->ndata[i]->node1^=segmentsx->ndata[i]->node2;

       if(segmentsx->ndata[i]->distance&(ONEWAY_2TO1|ONEWAY_1TO2))
          segmentsx->ndata[i]->distance^=ONEWAY_2TO1|ONEWAY_1TO2;

       rotated++;
      }

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

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


/*++++++++++++++++++++++++++++++++++++++
  Mark the duplicate segments.

  SegmentsX* segmentsx The set of segments to process.

  NodesX *nodesx The list of nodes to use.

  WaysX *waysx The list of ways to use.
  ++++++++++++++++++++++++++++++++++++++*/

void DeduplicateSegments(SegmentsX* segmentsx,NodesX *nodesx,WaysX *waysx)
{
 int i,duplicate=0;

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

 for(i=1;i<segmentsx->number;i++)
   {
    if(segmentsx->ndata[i]->node1==segmentsx->ndata[i-1]->node1 &&
       segmentsx->ndata[i]->node2==segmentsx->ndata[i-1]->node2 &&
       segmentsx->ndata[i]->distance==segmentsx->ndata[i-1]->distance)
      {
       WayX *wayx1=FindWayX(waysx,segmentsx->ndata[i-1]->way);
       WayX *wayx2=FindWayX(waysx,segmentsx->ndata[i  ]->way);

       if(!WaysCompare(wayx1->way,wayx2->way))
         {
          segmentsx->ndata[i-1]->node1=NO_NODE;
          segmentsx->ndata[i-1]->node2=NO_NODE;

          duplicate++;
         }
      }

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

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


/*++++++++++++++++++++++++++++++++++++++
  Create the real segments data.

  SegmentsX* segmentsx The set of segments to use.

  WaysX* waysx The set of ways to use.
  ++++++++++++++++++++++++++++++++++++++*/

void CreateRealSegments(SegmentsX *segmentsx,WaysX *waysx)
{
 int i;

 /* Allocate the memory */

 segmentsx->sdata=(Segment*)malloc(segmentsx->number*sizeof(Segment));

 /* Loop through and allocate. */

 for(i=0;i<segmentsx->number;i++)
   {
    WayX *wayx=FindWayX(waysx,segmentsx->ndata[i]->way);

    segmentsx->sdata[i].node1=0;
    segmentsx->sdata[i].node2=0;
    segmentsx->sdata[i].next2=NO_NODE;
    segmentsx->sdata[i].way=wayx->way-waysx->wdata;
    segmentsx->sdata[i].distance=segmentsx->ndata[i]->distance;

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

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


/*++++++++++++++++++++++++++++++++++++++
  Assign the nodes indexes to the segments.

  SegmentsX* segmentsx The set of segments to process.

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

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

 assert(segmentsx->sorted);     /* Must be sorted */
 assert(segmentsx->sdata);      /* Must have real segments */
 assert(nodesx->sorted);        /* Must be sorted */

 /* Index the segments */

 for(i=0;i<nodesx->number;i++)
   {
    index_t index=SEGMENT(nodesx->gdata[i]->node.firstseg);

    do
      {
       if(segmentsx->ndata[index]->node1==nodesx->gdata[i]->id)
         {
          segmentsx->sdata[index].node1=i;

          index++;

          if(index>=segmentsx->number || segmentsx->ndata[index]->node1!=nodesx->gdata[i]->id)
             break;
         }
       else
         {
          segmentsx->sdata[index].node2=i;

          if(segmentsx->sdata[index].next2==NO_NODE)
             break;
          else
             index=segmentsx->sdata[index].next2;
         }
      }
    while(1);

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

 printf("\rIndexed Nodes: Nodes=%d \n",nodesx->number);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  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)
{
 float dlon = nodex1->longitude - nodex2->longitude;
 float dlat = nodex1->latitude  - nodex2->latitude;

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

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

 a1 = sinf (dlat / 2);
 a2 = sinf (dlon / 2);
 a = (a1 * a1) + cosf (nodex1->latitude) * cosf (nodex2->latitude) * a2 * a2;
 sa = sqrtf (a);
 if (sa <= 1.0)
   {c = 2 * asinf (sa);}
 else
   {c = 2 * asinf (1.0);}
 d = 6378.137 * c;

 return km_to_distance(d);
}
1	amb	110	/***************************************
2	amb	209	$Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.15 2009-06-30 18:32:42 amb Exp $
3	amb	110
4			Extended Segment data type functions.
5	amb	151
6			Part of the Routino routing software.
7	amb	110	****************/ /****************
8	amb	151	This file Copyright 2008,2009 Andrew M. Bishop
9	amb	110
10	amb	151	This program is free software: you can redistribute it and/or modify
11			it under the terms of the GNU Affero General Public License as published by
12			the Free Software Foundation, either version 3 of the License, or
13			(at your option) any later version.
14
15			This program is distributed in the hope that it will be useful,
16			but WITHOUT ANY WARRANTY; without even the implied warranty of
17			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18			GNU Affero General Public License for more details.
19
20			You should have received a copy of the GNU Affero General Public License
21			along with this program. If not, see <http://www.gnu.org/licenses/>.
22	amb	110	***************************************/
23
24
25			#include <assert.h>
26			#include <math.h>
27			#include <string.h>
28			#include <stdlib.h>
29			#include <stdio.h>
30
31			#include "types.h"
32			#include "functions.h"
33			#include "nodesx.h"
34			#include "segmentsx.h"
35			#include "waysx.h"
36
37
38			/* Constants */
39
40			/+ The array size increment for segments - expect ~8,000,000 segments. +/
41			#define INCREMENT_SEGMENTS 1024*1024
42
43
44			/* Functions */
45
46	amb	204	static int sort_by_id_and_distance(SegmentX a,SegmentX b);
47	amb	110
48
49			/*++++++++++++++++++++++++++++++++++++++
50			Allocate a new segment list.
51
52			SegmentsX *NewSegmentList Returns the segment list.
53			++++++++++++++++++++++++++++++++++++++*/
54
55			SegmentsX *NewSegmentList(void)
56			{
57			SegmentsX *segmentsx;
58
59			segmentsx=(SegmentsX*)malloc(sizeof(SegmentsX));
60
61			segmentsx->sorted=0;
62			segmentsx->alloced=INCREMENT_SEGMENTS;
63			segmentsx->xnumber=0;
64	amb	209	segmentsx->number=0;
65	amb	110
66			segmentsx->xdata=(SegmentX)malloc(segmentsx->allocedsizeof(SegmentX));
67	amb	206	segmentsx->ndata=NULL;
68	amb	110
69	amb	209	segmentsx->sdata=NULL;
70
71	amb	110	return(segmentsx);
72			}
73
74
75			/*++++++++++++++++++++++++++++++++++++++
76			Free a segment list.
77
78			SegmentsX *segmentsx The list to be freed.
79			++++++++++++++++++++++++++++++++++++++*/
80
81			void FreeSegmentList(SegmentsX *segmentsx)
82			{
83	amb	209	if(segmentsx->sdata)
84			free(segmentsx->sdata);
85	amb	110	free(segmentsx->xdata);
86	amb	206	free(segmentsx->ndata);
87	amb	110	free(segmentsx);
88			}
89
90
91			/*++++++++++++++++++++++++++++++++++++++
92			Save the segment list to a file.
93
94			SegmentsX* segmentsx The set of segments to save.
95
96			const char *filename The name of the file to save.
97			++++++++++++++++++++++++++++++++++++++*/
98
99			void SaveSegmentList(SegmentsX* segmentsx,const char *filename)
100			{
101			int i;
102			int fd;
103			Segments *segments=calloc(1,sizeof(Segments));
104
105			assert(segmentsx->sorted); /* Must be sorted */
106
107			/* Fill in a Segments structure with the offset of the real data in the file after
108			the Segment structure itself. */
109
110			segments->number=segmentsx->number;
111			segments->data=NULL;
112			segments->segments=(void*)sizeof(Segments);
113
114			/* Write out the Segments structure and then the real data. */
115
116			fd=OpenFile(filename);
117
118			WriteFile(fd,segments,sizeof(Segments));
119
120	amb	203	for(i=0;i<segments->number;i++)
121	amb	132	{
122	amb	209	WriteFile(fd,&segmentsx->sdata[i],sizeof(Segment));
123	amb	110
124	amb	132	if(!((i+1)%10000))
125			{
126			printf("\rWriting Segments: Segments=%d",i+1);
127			fflush(stdout);
128			}
129			}
130
131	amb	203	printf("\rWrote Segments: Segments=%d \n",segments->number);
132	amb	132	fflush(stdout);
133
134	amb	110	CloseFile(fd);
135
136			/* Free the fake Segments */
137
138			free(segments);
139			}
140
141
142			/*++++++++++++++++++++++++++++++++++++++
143			Find the first segment with a particular starting node.
144
145			SegmentX **FindFirstSegmentX Returns a pointer to the first extended segment with the specified id.
146
147			SegmentsX* segmentsx The set of segments to process.
148
149			node_t node The node to look for.
150			++++++++++++++++++++++++++++++++++++++*/
151
152			SegmentX *FindFirstSegmentX(SegmentsX segmentsx,node_t node)
153			{
154			int start=0;
155			int end=segmentsx->number-1;
156			int mid;
157			int found;
158
159			assert(segmentsx->sorted); /* Must be sorted */
160
161			/* Binary search - search key exact match only is required.
162			*
163			* # <- start \| Check mid and move start or end if it doesn't match
164			* # \|
165			* # \| Since an exact match is wanted we can set end=mid-1
166			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
167			* # \|
168			* # \| Eventually either end=start or end=start+1 and one of
169			* # <- end \| start or end is the wanted one.
170			*/
171
172			if(end<start) /* There are no nodes */
173			return(NULL);
174	amb	206	else if(node<segmentsx->ndata[start]->node1) /* Check key is not before start */
175	amb	110	return(NULL);
176	amb	206	else if(node>segmentsx->ndata[end]->node1) /* Check key is not after end */
177	amb	110	return(NULL);
178			else
179			{
180			do
181			{
182			mid=(start+end)/2; /* Choose mid point */
183
184	amb	206	if(segmentsx->ndata[mid]->node1<node) /* Mid point is too low */
185	amb	110	start=mid;
186	amb	206	else if(segmentsx->ndata[mid]->node1>node) /* Mid point is too high */
187	amb	110	end=mid;
188			else /* Mid point is correct */
189			{found=mid; goto found;}
190			}
191			while((end-start)>1);
192
193	amb	206	if(segmentsx->ndata[start]->node1==node) /* Start is correct */
194	amb	110	{found=start; goto found;}
195
196	amb	206	if(segmentsx->ndata[end]->node1==node) /* End is correct */
197	amb	110	{found=end; goto found;}
198			}
199
200			return(NULL);
201
202			found:
203
204	amb	206	while(found>0 && segmentsx->ndata[found-1]->node1==node)
205	amb	110	found--;
206
207	amb	206	return(&segmentsx->ndata[found]);
208	amb	110	}
209
210
211			/*++++++++++++++++++++++++++++++++++++++
212			Find the next segment with a particular starting node.
213
214			SegmentX **FindNextSegmentX Returns a pointer to the next segment with the same id.
215
216			SegmentsX* segmentsx The set of segments to process.
217
218			SegmentX **segmentx The current segment.
219			++++++++++++++++++++++++++++++++++++++*/
220
221			SegmentX *FindNextSegmentX(SegmentsX segmentsx,SegmentX **segmentx)
222			{
223			SegmentX **next=segmentx+1;
224
225	amb	206	if((next-segmentsx->ndata)==segmentsx->number)
226	amb	110	return(NULL);
227
228			if((next)->node1==(segmentx)->node1)
229			return(next);
230
231			return(NULL);
232			}
233
234
235			/*++++++++++++++++++++++++++++++++++++++
236			Append a segment to a segment list.
237
238			SegmentsX* segmentsx The set of segments to process.
239
240	amb	203	way_t way The way that the segment belongs to.
241
242	amb	110	node_t node1 The first node in the segment.
243
244			node_t node2 The second node in the segment.
245			++++++++++++++++++++++++++++++++++++++*/
246
247	amb	209	void AppendSegment(SegmentsX* segmentsx,way_t way,node_t node1,node_t node2,distance_t distance)
248	amb	110	{
249			/* Check that the array has enough space. */
250
251			if(segmentsx->xnumber==segmentsx->alloced)
252			{
253			segmentsx->alloced+=INCREMENT_SEGMENTS;
254
255			segmentsx->xdata=(SegmentX)realloc((void)segmentsx->xdata,segmentsx->alloced*sizeof(SegmentX));
256			}
257
258			/* Insert the segment */
259
260	amb	203	segmentsx->xdata[segmentsx->xnumber].way=way;
261	amb	110	segmentsx->xdata[segmentsx->xnumber].node1=node1;
262			segmentsx->xdata[segmentsx->xnumber].node2=node2;
263	amb	209	segmentsx->xdata[segmentsx->xnumber].distance=distance;
264	amb	110
265			segmentsx->xnumber++;
266
267			segmentsx->sorted=0;
268			}
269
270
271			/*++++++++++++++++++++++++++++++++++++++
272			Sort the segment list.
273
274			SegmentsX* segmentsx The set of segments to process.
275			++++++++++++++++++++++++++++++++++++++*/
276
277			void SortSegmentList(SegmentsX* segmentsx)
278			{
279			int i;
280
281	amb	132	printf("Sorting Segments"); fflush(stdout);
282
283	amb	110	/* Allocate the arrays of pointers */
284
285			if(segmentsx->sorted)
286	amb	206	segmentsx->ndata=realloc(segmentsx->ndata,segmentsx->xnumbersizeof(SegmentX));
287	amb	110	else
288	amb	206	segmentsx->ndata=malloc(segmentsx->xnumbersizeof(SegmentX));
289	amb	110
290			segmentsx->number=0;
291
292			for(i=0;i<segmentsx->xnumber;i++)
293	amb	176	if(segmentsx->xdata[i].node1!=NO_NODE)
294	amb	110	{
295	amb	206	segmentsx->ndata[segmentsx->number]=&segmentsx->xdata[i];
296	amb	110	segmentsx->number++;
297			}
298
299	amb	206	qsort(segmentsx->ndata,segmentsx->number,sizeof(SegmentX),(int ()(const void,const void))sort_by_id_and_distance);
300	amb	110
301			segmentsx->sorted=1;
302	amb	132
303			printf("\rSorted Segments \n"); fflush(stdout);
304	amb	110	}
305
306
307			/*++++++++++++++++++++++++++++++++++++++
308	amb	204	Sort the segments into id order and then distance order.
309	amb	110
310	amb	204	int sort_by_id_and_distance Returns the comparison of the node fields.
311	amb	110
312			SegmentX **a The first Segment.
313
314			SegmentX **b The second Segment.
315			++++++++++++++++++++++++++++++++++++++*/
316
317	amb	204	static int sort_by_id_and_distance(SegmentX a,SegmentX b)
318	amb	110	{
319			node_t a_id1=(*a)->node1;
320			node_t b_id1=(*b)->node1;
321
322			if(a_id1<b_id1)
323			return(-1);
324			else if(a_id1>b_id1)
325			return(1);
326			else /* if(a_id1==b_id1) */
327			{
328			node_t a_id2=(*a)->node2;
329			node_t b_id2=(*b)->node2;
330
331			if(a_id2<b_id2)
332			return(-1);
333			else if(a_id2>b_id2)
334			return(1);
335			else
336			{
337	amb	209	distance_t a_distance=DISTANCE((*a)->distance);
338			distance_t b_distance=DISTANCE((*b)->distance);
339	amb	110
340			if(a_distance<b_distance)
341			return(-1);
342			else if(a_distance>b_distance)
343			return(1);
344			else
345			return(0);
346			}
347			}
348			}
349
350
351			/*++++++++++++++++++++++++++++++++++++++
352			Remove bad segments (zero length or duplicated).
353
354	amb	195	NodesX *nodesx The nodes to check.
355
356	amb	110	SegmentsX *segmentsx The segments to modify.
357			++++++++++++++++++++++++++++++++++++++*/
358
359	amb	204	void RemoveBadSegments(NodesX nodesx,SegmentsX segmentsx)
360	amb	110	{
361			int i;
362	amb	195	int duplicate=0,loop=0,missing=0;
363	amb	110
364			assert(segmentsx->sorted); /* Must be sorted */
365
366			for(i=0;i<segmentsx->number;i++)
367			{
368	amb	206	if(i && segmentsx->ndata[i]->node1==segmentsx->ndata[i-1]->node1 &&
369			segmentsx->ndata[i]->node2==segmentsx->ndata[i-1]->node2)
370	amb	110	{
371			duplicate++;
372	amb	206	segmentsx->ndata[i-1]->node1=NO_NODE;
373	amb	110	}
374	amb	206	else if(segmentsx->ndata[i]->node1==segmentsx->ndata[i]->node2)
375	amb	110	{
376			loop++;
377	amb	206	segmentsx->ndata[i]->node1=NO_NODE;
378	amb	110	}
379	amb	206	else if(!FindNodeX(nodesx,segmentsx->ndata[i]->node1) \|\|
380			!FindNodeX(nodesx,segmentsx->ndata[i]->node2))
381	amb	195	{
382			missing++;
383	amb	206	segmentsx->ndata[i]->node1=NO_NODE;
384	amb	195	}
385	amb	110
386			if(!((i+1)%10000))
387			{
388	amb	195	printf("\rChecking: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d",i+1,duplicate,loop,missing);
389	amb	110	fflush(stdout);
390			}
391			}
392
393	amb	195	printf("\rChecked: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d \n",segmentsx->number,duplicate,loop,missing);
394	amb	110	fflush(stdout);
395			}
396
397
398			/*++++++++++++++++++++++++++++++++++++++
399			Measure the segments.
400
401			SegmentsX* segmentsx The set of segments to process.
402
403			NodesX *nodesx The list of nodes to use.
404			++++++++++++++++++++++++++++++++++++++*/
405
406			void MeasureSegments(SegmentsX* segmentsx,NodesX *nodesx)
407			{
408			int i;
409
410			assert(segmentsx->sorted); /* Must be sorted */
411
412			for(i=0;i<segmentsx->number;i++)
413			{
414	amb	206	NodeX *node1=FindNodeX(nodesx,segmentsx->ndata[i]->node1);
415			NodeX *node2=FindNodeX(nodesx,segmentsx->ndata[i]->node2);
416	amb	110
417			/* Set the distance but preserve the ONEWAY_* flags */
418
419	amb	209	segmentsx->ndata[i]->distance\|=DISTANCE(DistanceX(node1,node2));
420	amb	110
421			if(!((i+1)%10000))
422			{
423			printf("\rMeasuring Segments: Segments=%d",i+1);
424			fflush(stdout);
425			}
426			}
427
428			printf("\rMeasured Segments: Segments=%d \n",segmentsx->number);
429			fflush(stdout);
430			}
431
432
433			/*++++++++++++++++++++++++++++++++++++++
434			Make the segments all point the same way (node1<node2).
435
436			SegmentsX* segmentsx The set of segments to process.
437
438			NodesX *nodesx The list of nodes to use.
439			++++++++++++++++++++++++++++++++++++++*/
440
441			void RotateSegments(SegmentsX* segmentsx,NodesX *nodesx)
442			{
443			int i,rotated=0;
444
445			assert(segmentsx->sorted); /* Must be sorted */
446
447			for(i=0;i<segmentsx->number;i++)
448			{
449	amb	206	if(segmentsx->ndata[i]->node1>segmentsx->ndata[i]->node2)
450	amb	110	{
451	amb	206	segmentsx->ndata[i]->node1^=segmentsx->ndata[i]->node2;
452			segmentsx->ndata[i]->node2^=segmentsx->ndata[i]->node1;
453			segmentsx->ndata[i]->node1^=segmentsx->ndata[i]->node2;
454	amb	110
455	amb	209	if(segmentsx->ndata[i]->distance&(ONEWAY_2TO1\|ONEWAY_1TO2))
456			segmentsx->ndata[i]->distance^=ONEWAY_2TO1\|ONEWAY_1TO2;
457	amb	110
458			rotated++;
459			}
460
461			if(!((i+1)%10000))
462			{
463			printf("\rRotating Segments: Segments=%d Rotated=%d",i+1,rotated);
464			fflush(stdout);
465			}
466			}
467
468			printf("\rRotated Segments: Segments=%d Rotated=%d \n",segmentsx->number,rotated);
469			fflush(stdout);
470			}
471
472
473			/*++++++++++++++++++++++++++++++++++++++
474			Mark the duplicate segments.
475
476			SegmentsX* segmentsx The set of segments to process.
477
478			NodesX *nodesx The list of nodes to use.
479
480			WaysX *waysx The list of ways to use.
481			++++++++++++++++++++++++++++++++++++++*/
482
483			void DeduplicateSegments(SegmentsX* segmentsx,NodesX nodesx,WaysX waysx)
484			{
485			int i,duplicate=0;
486
487			assert(segmentsx->sorted); /* Must be sorted */
488
489			for(i=1;i<segmentsx->number;i++)
490			{
491	amb	206	if(segmentsx->ndata[i]->node1==segmentsx->ndata[i-1]->node1 &&
492			segmentsx->ndata[i]->node2==segmentsx->ndata[i-1]->node2 &&
493	amb	209	segmentsx->ndata[i]->distance==segmentsx->ndata[i-1]->distance)
494	amb	110	{
495	amb	206	WayX *wayx1=FindWayX(waysx,segmentsx->ndata[i-1]->way);
496			WayX *wayx2=FindWayX(waysx,segmentsx->ndata[i ]->way);
497	amb	110
498	amb	204	if(!WaysCompare(wayx1->way,wayx2->way))
499	amb	110	{
500	amb	206	segmentsx->ndata[i-1]->node1=NO_NODE;
501			segmentsx->ndata[i-1]->node2=NO_NODE;
502	amb	110
503			duplicate++;
504			}
505			}
506
507			if(!((i+1)%10000))
508			{
509			printf("\rDeduplicating Segments: Segments=%d Duplicate=%d",i+1,duplicate);
510			fflush(stdout);
511			}
512			}
513
514			printf("\rDeduplicated Segments: Segments=%d Duplicate=%d \n",segmentsx->number,duplicate);
515			fflush(stdout);
516			}
517
518
519			/*++++++++++++++++++++++++++++++++++++++
520	amb	209	Create the real segments data.
521
522			SegmentsX* segmentsx The set of segments to use.
523
524			WaysX* waysx The set of ways to use.
525			++++++++++++++++++++++++++++++++++++++*/
526
527			void CreateRealSegments(SegmentsX segmentsx,WaysX waysx)
528			{
529			int i;
530
531			/* Allocate the memory */
532
533			segmentsx->sdata=(Segment)malloc(segmentsx->numbersizeof(Segment));
534
535			/* Loop through and allocate. */
536
537			for(i=0;i<segmentsx->number;i++)
538			{
539			WayX *wayx=FindWayX(waysx,segmentsx->ndata[i]->way);
540
541			segmentsx->sdata[i].node1=0;
542			segmentsx->sdata[i].node2=0;
543			segmentsx->sdata[i].next2=NO_NODE;
544			segmentsx->sdata[i].way=wayx->way-waysx->wdata;
545			segmentsx->sdata[i].distance=segmentsx->ndata[i]->distance;
546
547			if(!((i+1)%10000))
548			{
549			printf("\rCreating Real Segments: Segments=%d",i+1);
550			fflush(stdout);
551			}
552			}
553
554			printf("\rCreating Real Segments: Segments=%d \n",segmentsx->number);
555			fflush(stdout);
556			}
557
558
559			/*++++++++++++++++++++++++++++++++++++++
560	amb	110	Assign the nodes indexes to the segments.
561
562			SegmentsX* segmentsx The set of segments to process.
563
564			NodesX *nodesx The list of nodes to use.
565			++++++++++++++++++++++++++++++++++++++*/
566
567			void IndexSegments(SegmentsX* segmentsx,NodesX *nodesx)
568			{
569			int i;
570
571			assert(segmentsx->sorted); /* Must be sorted */
572	amb	209	assert(segmentsx->sdata); /* Must have real segments */
573	amb	110	assert(nodesx->sorted); /* Must be sorted */
574
575			/* Index the segments */
576
577			for(i=0;i<nodesx->number;i++)
578			{
579	amb	209	index_t index=SEGMENT(nodesx->gdata[i]->node.firstseg);
580	amb	110
581			do
582			{
583	amb	209	if(segmentsx->ndata[index]->node1==nodesx->gdata[i]->id)
584	amb	110	{
585	amb	209	segmentsx->sdata[index].node1=i;
586	amb	110
587	amb	209	index++;
588	amb	128
589	amb	209	if(index>=segmentsx->number \|\| segmentsx->ndata[index]->node1!=nodesx->gdata[i]->id)
590			break;
591	amb	110	}
592			else
593			{
594	amb	209	segmentsx->sdata[index].node2=i;
595	amb	110
596	amb	209	if(segmentsx->sdata[index].next2==NO_NODE)
597			break;
598	amb	110	else
599	amb	209	index=segmentsx->sdata[index].next2;
600	amb	110	}
601			}
602	amb	209	while(1);
603	amb	110
604			if(!((i+1)%10000))
605			{
606			printf("\rIndexing Nodes: Nodes=%d",i+1);
607			fflush(stdout);
608			}
609			}
610
611			printf("\rIndexed Nodes: Nodes=%d \n",nodesx->number);
612			fflush(stdout);
613			}
614
615
616			/*++++++++++++++++++++++++++++++++++++++
617			Calculate the distance between two nodes.
618
619			distance_t DistanceX Returns the distance between the extended nodes.
620
621			NodeX *nodex1 The starting node.
622
623			NodeX *nodex2 The end node.
624			++++++++++++++++++++++++++++++++++++++*/
625
626			distance_t DistanceX(NodeX nodex1,NodeX nodex2)
627			{
628	amb	121	float dlon = nodex1->longitude - nodex2->longitude;
629			float dlat = nodex1->latitude - nodex2->latitude;
630	amb	110
631	amb	120	float a1,a2,a,sa,c,d;
632	amb	110
633			if(dlon==0 && dlat==0)
634			return 0;
635
636	amb	120	a1 = sinf (dlat / 2);
637			a2 = sinf (dlon / 2);
638	amb	121	a = (a1 * a1) + cosf (nodex1->latitude) * cosf (nodex2->latitude) * a2 * a2;
639	amb	120	sa = sqrtf (a);
640	amb	110	if (sa <= 1.0)
641	amb	120	{c = 2 * asinf (sa);}
642	amb	110	else
643	amb	120	{c = 2 * asinf (1.0);}
644	amb	110	d = 6378.137 * c;
645
646			return km_to_distance(d);
647			}