destination-access/src/relations.c

/***************************************
 Relation data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2011 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++;

 if(current==relations->file.trnumber)
    return(NO_RELATION);

 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 segment 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++;

 if(current==relations->file.trnumber)
    return(NO_RELATION);

 relation=LookupTurnRelation(relations,current,1);

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


/*++++++++++++++++++++++++++++++++++++++
  Determine if a turn is allowed between the nodes from, via and to for a particular transport type.

  int IsTurnAllowed Return 1 if the turn is allowed.

  Relations *relations The set of relations to process.

  index_t index The index of the first turn relation containing via and from.

  index_t via The via node.

  index_t from The from segment.

  index_t to The to segment.

  transports_t transport The type of transport that is being routed.
  ++++++++++++++++++++++++++++++++++++++*/

int IsTurnAllowed(Relations *relations,index_t index,index_t via,index_t from,index_t to,transports_t transport)
{
 while(index<relations->file.trnumber)
   {
    TurnRelation *relation=LookupTurnRelation(relations,index,1);

    if(relation->via!=via)
       return(1);

    if(relation->from!=from)
       return(1);

    if(relation->to>to)
       return(1);

    if(relation->to==to)
       if(!(relation->except & transport))
          return(0);

    index++;
   }

 return(1);
}
1	/***************************************
2	Relation data type functions.
3
4	Part of the Routino routing software.
5	****************/ /****************
6	This file Copyright 2008-2011 Andrew M. Bishop
7
8	This program is free software: you can redistribute it and/or modify
9	it under the terms of the GNU Affero General Public License as published by
10	the Free Software Foundation, either version 3 of the License, or
11	(at your option) any later version.
12
13	This program is distributed in the hope that it will be useful,
14	but WITHOUT ANY WARRANTY; without even the implied warranty of
15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16	GNU Affero General Public License for more details.
17
18	You should have received a copy of the GNU Affero General Public License
19	along with this program. If not, see <http://www.gnu.org/licenses/>.
20	***************************************/
21
22
23	#include <sys/types.h>
24	#include <stdlib.h>
25
26	#include "relations.h"
27
28	#include "files.h"
29
30
31	/*++++++++++++++++++++++++++++++++++++++
32	Load in a relation list from a file.
33
34	Relations* LoadRelationList Returns the relation list.
35
36	const char *filename The name of the file to load.
37	++++++++++++++++++++++++++++++++++++++*/
38
39	Relations LoadRelationList(const char filename)
40	{
41	Relations *relations;
42
43	relations=(Relations*)malloc(sizeof(Relations));
44
45	#if !SLIM
46
47	relations->data=MapFile(filename);
48
49	/* Copy the RelationsFile header structure from the loaded data */
50
51	relations->file=((RelationsFile)relations->data);
52
53	/* Set the pointers in the Relations structure. */
54
55	relations->turnrelations=(TurnRelation*)(relations->data+sizeof(RelationsFile));
56
57	#else
58
59	relations->fd=ReOpenFile(filename);
60
61	/* Copy the RelationsFile header structure from the loaded data */
62
63	ReadFile(relations->fd,&relations->file,sizeof(RelationsFile));
64
65	relations->troffset=sizeof(RelationsFile);
66
67	relations->incache[0]=NO_RELATION;
68	relations->incache[1]=NO_RELATION;
69
70	#endif
71
72	if(relations->file.trnumber>0)
73	{
74	TurnRelation *relation;
75
76	relation=LookupTurnRelation(relations,0,1);
77
78	relations->via_start =relation->via;
79	relations->from_start=relation->from;
80
81	relation=LookupTurnRelation(relations,relations->file.trnumber-1,1);
82
83	relations->via_end =relation->via;
84	relations->from_end=relation->from;
85	}
86
87	return(relations);
88	}
89
90
91	/*++++++++++++++++++++++++++++++++++++++
92	Find a particular turn relation in the file.
93
94	index_t FindFirstTurnRelation1 Returns the index of the first turn relation matching via.
95
96	Relations *relations The set of relations to process.
97
98	index_t via The node that the route is going via.
99	++++++++++++++++++++++++++++++++++++++*/
100
101	index_t FindFirstTurnRelation1(Relations *relations,index_t via)
102	{
103	TurnRelation *relation;
104	int start=0;
105	int end=relations->file.trnumber-1;
106	int mid;
107	int match=-1;
108
109	/* Binary search - search key first match is required.
110	*
111	* # <- start \| Check mid and move start or end if it doesn't match
112	* # \|
113	* # \| Since an exact match is wanted we can set end=mid-1
114	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
115	* # \|
116	* # \| Eventually either end=start or end=start+1 and one of
117	* # <- end \| start or end is the wanted one.
118	*/
119
120	if(end<start) /* There are no relations */
121	return(NO_RELATION);
122
123	if(via<relations->via_start) /* Check key is not before start */
124	return(NO_RELATION);
125
126	if(via>relations->via_end) /* Check key is not after end */
127	return(NO_RELATION);
128
129	do
130	{
131	mid=(start+end)/2; /* Choose mid point */
132
133	relation=LookupTurnRelation(relations,mid,1);
134
135	if(relation->via<via) /* Mid point is too low for 'via' */
136	start=mid+1;
137	else if(relation->via>via) /* Mid point is too high for 'via' */
138	end=mid-1;
139	else /* Mid point is correct for 'from' */
140	{
141	match=mid;
142	break;
143	}
144	}
145	while((end-start)>1);
146
147	if(match==-1) /* Check if start matches */
148	{
149	relation=LookupTurnRelation(relations,start,1);
150
151	if(relation->via==via)
152	match=start;
153	}
154
155	if(match==-1) /* Check if end matches */
156	{
157	relation=LookupTurnRelation(relations,end,1);
158
159	if(relation->via==via)
160	match=end;
161	}
162
163	if(match==-1)
164	return(NO_RELATION);
165
166	while(match>0) /* Search backwards for the first match */
167	{
168	relation=LookupTurnRelation(relations,match-1,1);
169
170	if(relation->via==via)
171	match--;
172	else
173	break;
174	}
175
176	return(match);
177	}
178
179
180	/*++++++++++++++++++++++++++++++++++++++
181	Find the next matching turn relation in the file.
182
183	index_t FindNextTurnRelation1 Returns the index of the next turn relation matching via.
184
185	Relations *relations The set of relations to process.
186
187	index_t current The current index of a relation that matches.
188	++++++++++++++++++++++++++++++++++++++*/
189
190	index_t FindNextTurnRelation1(Relations *relations,index_t current)
191	{
192	TurnRelation *relation;
193	index_t via;
194
195	relation=LookupTurnRelation(relations,current,1);
196
197	via=relation->via;
198
199	current++;
200
201	if(current==relations->file.trnumber)
202	return(NO_RELATION);
203
204	relation=LookupTurnRelation(relations,current,1);
205
206	if(relation->via==via)
207	return(current);
208	else
209	return(NO_RELATION);
210	}
211
212
213	/*++++++++++++++++++++++++++++++++++++++
214	Find a particular turn relation in the file.
215
216	index_t FindFirstTurnRelation2 Returns the index of the first turn relation matching via and from.
217
218	Relations *relations The set of relations to process.
219
220	index_t via The node that the route is going via.
221
222	index_t from The segment that the route is coming from.
223	++++++++++++++++++++++++++++++++++++++*/
224
225	index_t FindFirstTurnRelation2(Relations *relations,index_t via,index_t from)
226	{
227	TurnRelation *relation;
228	int start=0;
229	int end=relations->file.trnumber-1;
230	int mid;
231	int match=-1;
232
233	/* Binary search - search key first match is required.
234	*
235	* # <- start \| Check mid and move start or end if it doesn't match
236	* # \|
237	* # \| Since an exact match is wanted we can set end=mid-1
238	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
239	* # \|
240	* # \| Eventually either end=start or end=start+1 and one of
241	* # <- end \| start or end is the wanted one.
242	*/
243
244	if(end<start) /* There are no relations */
245	return(NO_RELATION);
246
247	if(via<relations->via_start \|\|
248	from<relations->from_start) /* Check key is not before start */
249	return(NO_RELATION);
250
251	if(via>relations->via_end \|\|
252	from>relations->from_end) /* Check key is not after end */
253	return(NO_RELATION);
254
255	do
256	{
257	mid=(start+end)/2; /* Choose mid point */
258
259	relation=LookupTurnRelation(relations,mid,1);
260
261	if(relation->via<via) /* Mid point is too low for 'via' */
262	start=mid+1;
263	else if(relation->via>via) /* Mid point is too high for 'via' */
264	end=mid-1;
265	else /* Mid point is correct for 'via' */
266	{
267	if(relation->from<from) /* Mid point is too low for 'from' */
268	start=mid+1;
269	else if(relation->from>from) /* Mid point is too high for 'from' */
270	end=mid-1;
271	else /* Mid point is correct for 'from' */
272	{
273	match=mid;
274	break;
275	}
276	}
277	}
278	while((end-start)>1);
279
280	if(match==-1) /* Check if start matches */
281	{
282	relation=LookupTurnRelation(relations,start,1);
283
284	if(relation->via==via && relation->from==from)
285	match=start;
286	}
287
288	if(match==-1) /* Check if end matches */
289	{
290	relation=LookupTurnRelation(relations,end,1);
291
292	if(relation->via==via && relation->from==from)
293	match=end;
294	}
295
296	if(match==-1)
297	return(NO_RELATION);
298
299	while(match>0) /* Search backwards for the first match */
300	{
301	relation=LookupTurnRelation(relations,match-1,1);
302
303	if(relation->via==via && relation->from==from)
304	match--;
305	else
306	break;
307	}
308
309	return(match);
310	}
311
312
313	/*++++++++++++++++++++++++++++++++++++++
314	Find the next matching turn relation in the file.
315
316	index_t FindNextTurnRelation2 Returns the index of the next turn relation matching via and from.
317
318	Relations *relations The set of relations to process.
319
320	index_t current The current index of a relation that matches.
321	++++++++++++++++++++++++++++++++++++++*/
322
323	index_t FindNextTurnRelation2(Relations *relations,index_t current)
324	{
325	TurnRelation *relation;
326	index_t via,from;
327
328	relation=LookupTurnRelation(relations,current,1);
329
330	via=relation->via;
331	from=relation->from;
332
333	current++;
334
335	if(current==relations->file.trnumber)
336	return(NO_RELATION);
337
338	relation=LookupTurnRelation(relations,current,1);
339
340	if(relation->via==via && relation->from==from)
341	return(current);
342	else
343	return(NO_RELATION);
344	}
345
346
347	/*++++++++++++++++++++++++++++++++++++++
348	Determine if a turn is allowed between the nodes from, via and to for a particular transport type.
349
350	int IsTurnAllowed Return 1 if the turn is allowed.
351
352	Relations *relations The set of relations to process.
353
354	index_t index The index of the first turn relation containing via and from.
355
356	index_t via The via node.
357
358	index_t from The from segment.
359
360	index_t to The to segment.
361
362	transports_t transport The type of transport that is being routed.
363	++++++++++++++++++++++++++++++++++++++*/
364
365	int IsTurnAllowed(Relations *relations,index_t index,index_t via,index_t from,index_t to,transports_t transport)
366	{
367	while(index<relations->file.trnumber)
368	{
369	TurnRelation *relation=LookupTurnRelation(relations,index,1);
370
371	if(relation->via!=via)
372	return(1);
373
374	if(relation->from!=from)
375	return(1);
376
377	if(relation->to>to)
378	return(1);
379
380	if(relation->to==to)
381	if(!(relation->except & transport))
382	return(0);
383
384	index++;
385	}
386
387	return(1);
388	}