trunk/src/relations.c

/***************************************
 $Header: /home/amb/CVS/routino/src/relations.c,v 1.3 2010-12-21 17:17:57 amb Exp $

 Relation data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2010 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 <sys/types.h>
#include <stdlib.h>

#include "relations.h"

#include "files.h"


/*++++++++++++++++++++++++++++++++++++++
  Load in a relation list from a file.

  Relations* LoadRelationList Returns the relation list.

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

Relations *LoadRelationList(const char *filename)
{
 Relations *relations;

 relations=(Relations*)malloc(sizeof(Relations));

#if !SLIM

 relations->data=MapFile(filename);

 /* Copy the RelationsFile header structure from the loaded data */

 relations->file=*((RelationsFile*)relations->data);

 /* Set the pointers in the Relations structure. */

 relations->turnrelations=(TurnRelation*)(relations->data+sizeof(RelationsFile));

#else

 relations->fd=ReOpenFile(filename);

 /* Copy the RelationsFile header structure from the loaded data */

 ReadFile(relations->fd,&relations->file,sizeof(RelationsFile));

 relations->troffset=sizeof(RelationsFile);

 relations->incache[0]=NO_RELATION;
 relations->incache[1]=NO_RELATION;

#endif

 if(relations->file.trnumber>0)
   {
    TurnRelation *relation;

    relation=LookupTurnRelation(relations,0,1);

    relations->via_start =relation->via;
    relations->from_start=relation->from;

    relation=LookupTurnRelation(relations,relations->file.trnumber-1,1);

    relations->via_end =relation->via;
    relations->from_end=relation->from;
   }

 return(relations);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular turn relation in the file.

  index_t FindFirstTurnRelation1 Returns the index of the first turn relation matching via.

  Relations *relations The set of relations to process.

  index_t via The node that the route is going via.
  ++++++++++++++++++++++++++++++++++++++*/

index_t FindFirstTurnRelation1(Relations *relations,index_t via)
{
 TurnRelation *relation;
 int start=0;
 int end=relations->file.trnumber-1;
 int mid;
 int match=-1;

 /* Binary search - search key first match 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 relations */
    return(NO_RELATION);

 if(via<relations->via_start)       /* Check key is not before start */
    return(NO_RELATION);

 if(via>relations->via_end)         /* Check key is not after end */
    return(NO_RELATION);

 do
   {
    mid=(start+end)/2;              /* Choose mid point */

    relation=LookupTurnRelation(relations,mid,1);

    if(relation->via<via)           /* Mid point is too low for 'via' */
       start=mid+1;
    else if(relation->via>via)      /* Mid point is too high for 'via' */
       end=mid-1;
    else                            /* Mid point is correct for 'from' */
      {
       match=mid;
       break;
      }
   }
 while((end-start)>1);

 if(match==-1)                      /* Check if start matches */
   {
    relation=LookupTurnRelation(relations,start,1);

    if(relation->via==via)
       match=start;
   }

 if(match==-1)                      /* Check if end matches */
   {
    relation=LookupTurnRelation(relations,end,1);

    if(relation->via==via)
       match=end;
   }

 if(match==-1)
    return(NO_RELATION);

 while(match>0)                     /* Search backwards for the first match */
   {
    relation=LookupTurnRelation(relations,match-1,1);

    if(relation->via==via)
       match--;
    else
       break;
   }

 return(match);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the next matching turn relation in the file.

  index_t FindNextTurnRelation1 Returns the index of the next turn relation matching via.

  Relations *relations The set of relations to process.

  index_t current The current index of a relation that matches.
  ++++++++++++++++++++++++++++++++++++++*/

index_t FindNextTurnRelation1(Relations *relations,index_t current)
{
 TurnRelation *relation;
 index_t via;

 relation=LookupTurnRelation(relations,current,1);

 via=relation->via;

 current++;

 relation=LookupTurnRelation(relations,current,1);

 if(relation->via==via)
    return(current);
 else
    return(NO_RELATION);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular turn relation in the file.

  index_t FindFirstTurnRelation2 Returns the index of the first turn relation matching via and from.

  Relations *relations The set of relations to process.

  index_t via The node that the route is going via.

  index_t from The node that the route is coming from.
  ++++++++++++++++++++++++++++++++++++++*/

index_t FindFirstTurnRelation2(Relations *relations,index_t via,index_t from)
{
 TurnRelation *relation;
 int start=0;
 int end=relations->file.trnumber-1;
 int mid;
 int match=-1;

 /* Binary search - search key first match 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 relations */
    return(NO_RELATION);

 if(via<relations->via_start ||
    from<relations->from_start)     /* Check key is not before start */
    return(NO_RELATION);

 if(via>relations->via_end ||
    from>relations->from_end)       /* Check key is not after end */
    return(NO_RELATION);

 do
   {
    mid=(start+end)/2;              /* Choose mid point */

    relation=LookupTurnRelation(relations,mid,1);

    if(relation->via<via)           /* Mid point is too low for 'via' */
       start=mid+1;
    else if(relation->via>via)      /* Mid point is too high for 'via' */
       end=mid-1;
    else                            /* Mid point is correct for 'via' */
      {
       if(relation->from<from)      /* Mid point is too low for 'from' */
          start=mid+1;
       else if(relation->from>from) /* Mid point is too high for 'from' */
          end=mid-1;
       else                         /* Mid point is correct for 'from' */
         {
          match=mid;
          break;
         }
      }
   }
 while((end-start)>1);

 if(match==-1)                      /* Check if start matches */
   {
    relation=LookupTurnRelation(relations,start,1);

    if(relation->via==via && relation->from==from)
       match=start;
   }

 if(match==-1)                      /* Check if end matches */
   {
    relation=LookupTurnRelation(relations,end,1);

    if(relation->via==via && relation->from==from)
       match=end;
   }

 if(match==-1)
    return(NO_RELATION);

 while(match>0)                     /* Search backwards for the first match */
   {
    relation=LookupTurnRelation(relations,match-1,1);

    if(relation->via==via && relation->from==from)
       match--;
    else
       break;
   }

 return(match);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the next matching turn relation in the file.

  index_t FindNextTurnRelation2 Returns the index of the next turn relation matching via and from.

  Relations *relations The set of relations to process.

  index_t current The current index of a relation that matches.
  ++++++++++++++++++++++++++++++++++++++*/

index_t FindNextTurnRelation2(Relations *relations,index_t current)
{
 TurnRelation *relation;
 index_t via,from;

 relation=LookupTurnRelation(relations,current,1);

 via=relation->via;
 from=relation->from;

 current++;

 relation=LookupTurnRelation(relations,current,1);

 if(relation->via==via && relation->from==from)
    return(current);
 else
    return(NO_RELATION);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/relations.c,v 1.3 2010-12-21 17:17:57 amb Exp $
3
4	Relation data type functions.
5
6	Part of the Routino routing software.
7	****************/ /****************
8	This file Copyright 2008-2010 Andrew M. Bishop
9
10	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	***************************************/
23
24
25	#include <sys/types.h>
26	#include <stdlib.h>
27
28	#include "relations.h"
29
30	#include "files.h"
31
32
33	/*++++++++++++++++++++++++++++++++++++++
34	Load in a relation list from a file.
35
36	Relations* LoadRelationList Returns the relation list.
37
38	const char *filename The name of the file to load.
39	++++++++++++++++++++++++++++++++++++++*/
40
41	Relations LoadRelationList(const char filename)
42	{
43	Relations *relations;
44
45	relations=(Relations*)malloc(sizeof(Relations));
46
47	#if !SLIM
48
49	relations->data=MapFile(filename);
50
51	/* Copy the RelationsFile header structure from the loaded data */
52
53	relations->file=((RelationsFile)relations->data);
54
55	/* Set the pointers in the Relations structure. */
56
57	relations->turnrelations=(TurnRelation*)(relations->data+sizeof(RelationsFile));
58
59	#else
60
61	relations->fd=ReOpenFile(filename);
62
63	/* Copy the RelationsFile header structure from the loaded data */
64
65	ReadFile(relations->fd,&relations->file,sizeof(RelationsFile));
66
67	relations->troffset=sizeof(RelationsFile);
68
69	relations->incache[0]=NO_RELATION;
70	relations->incache[1]=NO_RELATION;
71
72	#endif
73
74	if(relations->file.trnumber>0)
75	{
76	TurnRelation *relation;
77
78	relation=LookupTurnRelation(relations,0,1);
79
80	relations->via_start =relation->via;
81	relations->from_start=relation->from;
82
83	relation=LookupTurnRelation(relations,relations->file.trnumber-1,1);
84
85	relations->via_end =relation->via;
86	relations->from_end=relation->from;
87	}
88
89	return(relations);
90	}
91
92
93	/*++++++++++++++++++++++++++++++++++++++
94	Find a particular turn relation in the file.
95
96	index_t FindFirstTurnRelation1 Returns the index of the first turn relation matching via.
97
98	Relations *relations The set of relations to process.
99
100	index_t via The node that the route is going via.
101	++++++++++++++++++++++++++++++++++++++*/
102
103	index_t FindFirstTurnRelation1(Relations *relations,index_t via)
104	{
105	TurnRelation *relation;
106	int start=0;
107	int end=relations->file.trnumber-1;
108	int mid;
109	int match=-1;
110
111	/* Binary search - search key first match is required.
112	*
113	* # <- start \| Check mid and move start or end if it doesn't match
114	* # \|
115	* # \| Since an exact match is wanted we can set end=mid-1
116	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
117	* # \|
118	* # \| Eventually either end=start or end=start+1 and one of
119	* # <- end \| start or end is the wanted one.
120	*/
121
122	if(end<start) /* There are no relations */
123	return(NO_RELATION);
124
125	if(via<relations->via_start) /* Check key is not before start */
126	return(NO_RELATION);
127
128	if(via>relations->via_end) /* Check key is not after end */
129	return(NO_RELATION);
130
131	do
132	{
133	mid=(start+end)/2; /* Choose mid point */
134
135	relation=LookupTurnRelation(relations,mid,1);
136
137	if(relation->via<via) /* Mid point is too low for 'via' */
138	start=mid+1;
139	else if(relation->via>via) /* Mid point is too high for 'via' */
140	end=mid-1;
141	else /* Mid point is correct for 'from' */
142	{
143	match=mid;
144	break;
145	}
146	}
147	while((end-start)>1);
148
149	if(match==-1) /* Check if start matches */
150	{
151	relation=LookupTurnRelation(relations,start,1);
152
153	if(relation->via==via)
154	match=start;
155	}
156
157	if(match==-1) /* Check if end matches */
158	{
159	relation=LookupTurnRelation(relations,end,1);
160
161	if(relation->via==via)
162	match=end;
163	}
164
165	if(match==-1)
166	return(NO_RELATION);
167
168	while(match>0) /* Search backwards for the first match */
169	{
170	relation=LookupTurnRelation(relations,match-1,1);
171
172	if(relation->via==via)
173	match--;
174	else
175	break;
176	}
177
178	return(match);
179	}
180
181
182	/*++++++++++++++++++++++++++++++++++++++
183	Find the next matching turn relation in the file.
184
185	index_t FindNextTurnRelation1 Returns the index of the next turn relation matching via.
186
187	Relations *relations The set of relations to process.
188
189	index_t current The current index of a relation that matches.
190	++++++++++++++++++++++++++++++++++++++*/
191
192	index_t FindNextTurnRelation1(Relations *relations,index_t current)
193	{
194	TurnRelation *relation;
195	index_t via;
196
197	relation=LookupTurnRelation(relations,current,1);
198
199	via=relation->via;
200
201	current++;
202
203	relation=LookupTurnRelation(relations,current,1);
204
205	if(relation->via==via)
206	return(current);
207	else
208	return(NO_RELATION);
209	}
210
211
212	/*++++++++++++++++++++++++++++++++++++++
213	Find a particular turn relation in the file.
214
215	index_t FindFirstTurnRelation2 Returns the index of the first turn relation matching via and from.
216
217	Relations *relations The set of relations to process.
218
219	index_t via The node that the route is going via.
220
221	index_t from The node that the route is coming from.
222	++++++++++++++++++++++++++++++++++++++*/
223
224	index_t FindFirstTurnRelation2(Relations *relations,index_t via,index_t from)
225	{
226	TurnRelation *relation;
227	int start=0;
228	int end=relations->file.trnumber-1;
229	int mid;
230	int match=-1;
231
232	/* Binary search - search key first match is required.
233	*
234	* # <- start \| Check mid and move start or end if it doesn't match
235	* # \|
236	* # \| Since an exact match is wanted we can set end=mid-1
237	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
238	* # \|
239	* # \| Eventually either end=start or end=start+1 and one of
240	* # <- end \| start or end is the wanted one.
241	*/
242
243	if(end<start) /* There are no relations */
244	return(NO_RELATION);
245
246	if(via<relations->via_start \|\|
247	from<relations->from_start) /* Check key is not before start */
248	return(NO_RELATION);
249
250	if(via>relations->via_end \|\|
251	from>relations->from_end) /* Check key is not after end */
252	return(NO_RELATION);
253
254	do
255	{
256	mid=(start+end)/2; /* Choose mid point */
257
258	relation=LookupTurnRelation(relations,mid,1);
259
260	if(relation->via<via) /* Mid point is too low for 'via' */
261	start=mid+1;
262	else if(relation->via>via) /* Mid point is too high for 'via' */
263	end=mid-1;
264	else /* Mid point is correct for 'via' */
265	{
266	if(relation->from<from) /* Mid point is too low for 'from' */
267	start=mid+1;
268	else if(relation->from>from) /* Mid point is too high for 'from' */
269	end=mid-1;
270	else /* Mid point is correct for 'from' */
271	{
272	match=mid;
273	break;
274	}
275	}
276	}
277	while((end-start)>1);
278
279	if(match==-1) /* Check if start matches */
280	{
281	relation=LookupTurnRelation(relations,start,1);
282
283	if(relation->via==via && relation->from==from)
284	match=start;
285	}
286
287	if(match==-1) /* Check if end matches */
288	{
289	relation=LookupTurnRelation(relations,end,1);
290
291	if(relation->via==via && relation->from==from)
292	match=end;
293	}
294
295	if(match==-1)
296	return(NO_RELATION);
297
298	while(match>0) /* Search backwards for the first match */
299	{
300	relation=LookupTurnRelation(relations,match-1,1);
301
302	if(relation->via==via && relation->from==from)
303	match--;
304	else
305	break;
306	}
307
308	return(match);
309	}
310
311
312	/*++++++++++++++++++++++++++++++++++++++
313	Find the next matching turn relation in the file.
314
315	index_t FindNextTurnRelation2 Returns the index of the next turn relation matching via and from.
316
317	Relations *relations The set of relations to process.
318
319	index_t current The current index of a relation that matches.
320	++++++++++++++++++++++++++++++++++++++*/
321
322	index_t FindNextTurnRelation2(Relations *relations,index_t current)
323	{
324	TurnRelation *relation;
325	index_t via,from;
326
327	relation=LookupTurnRelation(relations,current,1);
328
329	via=relation->via;
330	from=relation->from;
331
332	current++;
333
334	relation=LookupTurnRelation(relations,current,1);
335
336	if(relation->via==via && relation->from==from)
337	return(current);
338	else
339	return(NO_RELATION);
340	}