trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.1 2009-01-06 18:32:27 amb Exp $

 Super-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 "functions.h"
#include "types.h"

#define INCREMENT 64*1024

/*+ The list of super-segments +*/
SuperSegments *OSMSuperSegments=NULL;

/*+ Is the data sorted and therefore searchable? +*/
static int sorted=0;

/*+ Is the data loaded from a file and therefore read-only? +*/
static int loaded=0;

/*+ How many entries are allocated? +*/
static size_t alloced=0;

/* Functions */

static void append_super_segment(node_t node1,node_t node2);
static int sort_by_id(SuperSegment *a,SuperSegment *b);


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

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

void LoadSuperSegmentList(const char *filename)
{
 assert(!OSMSuperSegments);          /* Must be NULL */

 OSMSuperSegments=(SuperSegments*)MapFile(filename);

 assert(OSMSuperSegments);           /* Must be non-NULL */

 sorted=1;
 loaded=1;
}


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

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

void SaveSuperSegmentList(const char *filename)
{
 int retval;

 assert(!loaded);               /* Must not be loaded */

 assert(sorted);                /* Must be sorted */

 retval=WriteFile(filename,OSMSuperSegments,sizeof(SuperSegments)-sizeof(OSMSuperSegments->segments)+OSMSuperSegments->number*sizeof(SuperSegment));

 assert(!retval);               /* Must be zero */
}


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

  SuperSegment *FindFirstSuperSegment Returns a pointer to the first super-segment with the specified id.

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

SuperSegment *FindFirstSuperSegment(node_t node)
{
 int start=0;
 int end=OSMSuperSegments->number-1;
 int mid;
 int found;

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

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

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

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

 return(NULL);

 found:

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

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


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

  SuperSegment *FindSuperSegment Returns a pointer to the first super-segment with the specified id.

  SuperSegment *supersegment The current super-segment.
  ++++++++++++++++++++++++++++++++++++++*/

SuperSegment *FindNextSuperSegment(SuperSegment *supersegment)
{
 SuperSegment *next=supersegment+1;

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

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

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Select the super-segments from the list of segments.
  ++++++++++++++++++++++++++++++++++++++*/

void ChooseSuperSegments(void)
{
 assert(!loaded);               /* Must not be loaded */


 /* Check that the whole thing is allocated. */

 if(!OSMSuperSegments)
   {
    alloced=INCREMENT;
    OSMSuperSegments=(SuperSegments*)malloc(sizeof(SuperSegments)-sizeof(OSMSuperSegments->segments)+alloced*sizeof(SuperSegment));

    OSMSuperSegments->number=0;
   }

}


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

  node_t node1 The first node in the super-segment.

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

static void append_super_segment(node_t node1,node_t node2)
{
 assert(!loaded);               /* Must not be loaded */

 /* Check that the whole thing is allocated. */

 if(!OSMSuperSegments)
   {
    alloced=INCREMENT;
    OSMSuperSegments=(SuperSegments*)malloc(sizeof(SuperSegments)-sizeof(OSMSuperSegments->segments)+alloced*sizeof(SuperSegment));

    OSMSuperSegments->number=0;
   }

 /* Check that the arrays have enough space. */

 if(OSMSuperSegments->number==alloced)
   {
    alloced+=INCREMENT;
    OSMSuperSegments=(SuperSegments*)realloc((void*)OSMSuperSegments,sizeof(SuperSegments)-sizeof(OSMSuperSegments->segments)+alloced*sizeof(SuperSegment));
   }

 /* Insert the super-segment */

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

 OSMSuperSegments->number++;

 sorted=0;
}


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

void SortSuperSegmentList(void)
{
 assert(!loaded);               /* Must not be loaded */

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

 sorted=1;
}


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

  int sort_by_id Returns the comparison of the node fields.

  SuperSegment *a The first SuperSegment.

  SuperSegment *b The second SuperSegment.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_id(SuperSegment *a,SuperSegment *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(a_id2-b_id2);
 else
    return(a_id1-b_id1);
}


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

void FixupSuperSegmentLengths(void)
{
 int i;

 assert(!loaded);               /* Must not be loaded */

 assert(sorted);                /* Must be sorted */

 for(i=0;i<OSMSuperSegments->number;i++)
   {
//    Node *node1=FindNode(OSMSuperSegments->segments[i].node1);
//    Node *node2=FindNode(OSMSuperSegments->segments[i].node2);

//    distance_t distance=Distance(node1,node2);
//    duration_t duration=hours_to_duration(distance_to_km(distance)/speed);

//    OSMSuperSegments->segments[i].distance=distance;
//    OSMSuperSegments->segments[i].duration=duration;
   }
}
1	amb	16	/***************************************
2			$Header: /home/amb/CVS/routino/src/supersegments.c,v 1.1 2009-01-06 18:32:27 amb Exp $
3
4			Super-Segment data type functions.
5			****************/ /****************
6			Written by Andrew M. Bishop
7
8			This file Copyright 2008,2009 Andrew M. Bishop
9			It may be distributed under the GNU Public License, version 2, or
10			any higher version. See section COPYING of the GNU Public license
11			for conditions under which this file may be redistributed.
12			***************************************/
13
14
15			#include <assert.h>
16			#include <math.h>
17			#include <stdlib.h>
18
19			#include "functions.h"
20			#include "types.h"
21
22			#define INCREMENT 64*1024
23
24			/+ The list of super-segments +/
25			SuperSegments *OSMSuperSegments=NULL;
26
27			/+ Is the data sorted and therefore searchable? +/
28			static int sorted=0;
29
30			/+ Is the data loaded from a file and therefore read-only? +/
31			static int loaded=0;
32
33			/+ How many entries are allocated? +/
34			static size_t alloced=0;
35
36			/* Functions */
37
38			static void append_super_segment(node_t node1,node_t node2);
39			static int sort_by_id(SuperSegment a,SuperSegment b);
40
41
42			/*++++++++++++++++++++++++++++++++++++++
43			Load in a super-segment list from a file.
44
45			const char *filename The name of the file to load.
46			++++++++++++++++++++++++++++++++++++++*/
47
48			void LoadSuperSegmentList(const char *filename)
49			{
50			assert(!OSMSuperSegments); /* Must be NULL */
51
52			OSMSuperSegments=(SuperSegments*)MapFile(filename);
53
54			assert(OSMSuperSegments); /* Must be non-NULL */
55
56			sorted=1;
57			loaded=1;
58			}
59
60
61			/*++++++++++++++++++++++++++++++++++++++
62			Save the super-segment list to a file.
63
64			const char *filename The name of the file to save.
65			++++++++++++++++++++++++++++++++++++++*/
66
67			void SaveSuperSegmentList(const char *filename)
68			{
69			int retval;
70
71			assert(!loaded); /* Must not be loaded */
72
73			assert(sorted); /* Must be sorted */
74
75			retval=WriteFile(filename,OSMSuperSegments,sizeof(SuperSegments)-sizeof(OSMSuperSegments->segments)+OSMSuperSegments->number*sizeof(SuperSegment));
76
77			assert(!retval); /* Must be zero */
78			}
79
80
81			/*++++++++++++++++++++++++++++++++++++++
82			Find the first super-segment with a particular starting node.
83
84			SuperSegment *FindFirstSuperSegment Returns a pointer to the first super-segment with the specified id.
85
86			node_t node The node to look for.
87			++++++++++++++++++++++++++++++++++++++*/
88
89			SuperSegment *FindFirstSuperSegment(node_t node)
90			{
91			int start=0;
92			int end=OSMSuperSegments->number-1;
93			int mid;
94			int found;
95
96			assert(sorted); /* Must be sorted */
97
98			/* Binary search - search key exact match only is required.
99			*
100			* # <- start \| Check mid and move start or end if it doesn't match
101			* # \|
102			* # \| Since an exact match is wanted we can set end=mid-1
103			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
104			* # \|
105			* # \| Eventually either end=start or end=start+1 and one of
106			* # <- end \| start or end is the wanted one.
107			*/
108
109			if(OSMSuperSegments->number==0) /* There are no segments */
110			return(NULL);
111			else if(node<OSMSuperSegments->segments[start].node1) /* Check key is not before start */
112			return(NULL);
113			else if(node>OSMSuperSegments->segments[end].node1) /* Check key is not after end */
114			return(NULL);
115			else
116			{
117			do
118			{
119			mid=(start+end)/2; /* Choose mid point */
120
121			if(OSMSuperSegments->segments[mid].node1<node) /* Mid point is too low */
122			start=mid;
123			else if(OSMSuperSegments->segments[mid].node1>node) /* Mid point is too high */
124			end=mid;
125			else /* Mid point is correct */
126			{found=mid; goto found;}
127			}
128			while((end-start)>1);
129
130			if(OSMSuperSegments->segments[start].node1==node) /* Start is correct */
131			{found=start; goto found;}
132
133			if(OSMSuperSegments->segments[end].node1==node) /* End is correct */
134			{found=end; goto found;}
135			}
136
137			return(NULL);
138
139			found:
140
141			while(found>0 && OSMSuperSegments->segments[found-1].node1==node)
142			found--;
143
144			return(&OSMSuperSegments->segments[found]);
145			}
146
147
148			/*++++++++++++++++++++++++++++++++++++++
149			Find the next super-segment with a particular starting node.
150
151			SuperSegment *FindSuperSegment Returns a pointer to the first super-segment with the specified id.
152
153			SuperSegment *supersegment The current super-segment.
154			++++++++++++++++++++++++++++++++++++++*/
155
156			SuperSegment FindNextSuperSegment(SuperSegment supersegment)
157			{
158			SuperSegment *next=supersegment+1;
159
160			if((next-OSMSuperSegments->segments)==OSMSuperSegments->number)
161			return(NULL);
162
163			if(next->node1==supersegment->node1)
164			return(next);
165
166			return(NULL);
167			}
168
169
170			/*++++++++++++++++++++++++++++++++++++++
171			Select the super-segments from the list of segments.
172			++++++++++++++++++++++++++++++++++++++*/
173
174			void ChooseSuperSegments(void)
175			{
176			assert(!loaded); /* Must not be loaded */
177
178
179			/* Check that the whole thing is allocated. */
180
181			if(!OSMSuperSegments)
182			{
183			alloced=INCREMENT;
184			OSMSuperSegments=(SuperSegments)malloc(sizeof(SuperSegments)-sizeof(OSMSuperSegments->segments)+allocedsizeof(SuperSegment));
185
186			OSMSuperSegments->number=0;
187			}
188
189			}
190
191
192			/*++++++++++++++++++++++++++++++++++++++
193			Append a super-segment to a newly created segment list (unsorted).
194
195			node_t node1 The first node in the super-segment.
196
197			node_t node2 The second node in the super-segment.
198			++++++++++++++++++++++++++++++++++++++*/
199
200			static void append_super_segment(node_t node1,node_t node2)
201			{
202			assert(!loaded); /* Must not be loaded */
203
204			/* Check that the whole thing is allocated. */
205
206			if(!OSMSuperSegments)
207			{
208			alloced=INCREMENT;
209			OSMSuperSegments=(SuperSegments)malloc(sizeof(SuperSegments)-sizeof(OSMSuperSegments->segments)+allocedsizeof(SuperSegment));
210
211			OSMSuperSegments->number=0;
212			}
213
214			/* Check that the arrays have enough space. */
215
216			if(OSMSuperSegments->number==alloced)
217			{
218			alloced+=INCREMENT;
219			OSMSuperSegments=(SuperSegments)realloc((void)OSMSuperSegments,sizeof(SuperSegments)-sizeof(OSMSuperSegments->segments)+alloced*sizeof(SuperSegment));
220			}
221
222			/* Insert the super-segment */
223
224			OSMSuperSegments->segments[OSMSuperSegments->number].node1=node1;
225			OSMSuperSegments->segments[OSMSuperSegments->number].node2=node2;
226			OSMSuperSegments->segments[OSMSuperSegments->number].distance=0;
227			OSMSuperSegments->segments[OSMSuperSegments->number].duration=0;
228
229			OSMSuperSegments->number++;
230
231			sorted=0;
232			}
233
234
235			/*++++++++++++++++++++++++++++++++++++++
236			Sort the super-segment list.
237			++++++++++++++++++++++++++++++++++++++*/
238
239			void SortSuperSegmentList(void)
240			{
241			assert(!loaded); /* Must not be loaded */
242
243			qsort(OSMSuperSegments->segments,OSMSuperSegments->number,sizeof(SuperSegment),(int ()(const void,const void*))sort_by_id);
244
245			sorted=1;
246			}
247
248
249			/*++++++++++++++++++++++++++++++++++++++
250			Sort the super-segments into id order.
251
252			int sort_by_id Returns the comparison of the node fields.
253
254			SuperSegment *a The first SuperSegment.
255
256			SuperSegment *b The second SuperSegment.
257			++++++++++++++++++++++++++++++++++++++*/
258
259			static int sort_by_id(SuperSegment a,SuperSegment b)
260			{
261			node_t a_id1=a->node1,a_id2=a->node2;
262			node_t b_id1=b->node1,b_id2=b->node2;
263
264			if(a_id1==b_id1)
265			return(a_id2-b_id2);
266			else
267			return(a_id1-b_id1);
268			}
269
270
271			/*++++++++++++++++++++++++++++++++++++++
272			Assign the lengths and durations to all of the super-segments.
273			++++++++++++++++++++++++++++++++++++++*/
274
275			void FixupSuperSegmentLengths(void)
276			{
277			int i;
278
279			assert(!loaded); /* Must not be loaded */
280
281			assert(sorted); /* Must be sorted */
282
283			for(i=0;i<OSMSuperSegments->number;i++)
284			{
285			// Node *node1=FindNode(OSMSuperSegments->segments[i].node1);
286			// Node *node2=FindNode(OSMSuperSegments->segments[i].node2);
287
288			// distance_t distance=Distance(node1,node2);
289			// duration_t duration=hours_to_duration(distance_to_km(distance)/speed);
290
291			// OSMSuperSegments->segments[i].distance=distance;
292			// OSMSuperSegments->segments[i].duration=duration;
293			}
294			}