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	/***************************************
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	}