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 "fakes.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;
#if SLIM
 int i;
#endif

 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);

 for(i=0;i<sizeof(relations->cached)/sizeof(relations->cached[0]);i++)
    relations->incache[i]=NO_RELATION;

#endif

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

    relation=LookupTurnRelation(relations,0,1);

    relations->via_start =relation->via;

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

    relations->via_end =relation->via;
   }

 return(relations);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the first turn relation in the file whose 'via' matches a specific node.

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

  Relations *relations The set of relations to use.

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

index_t FindFirstTurnRelation1(Relations *relations,index_t via)
{
 TurnRelation *relation;
 index_t start=0;
 index_t end=relations->file.trnumber-1;
 index_t mid;
 index_t 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 matches (but may not be the first).
  */

 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 turn relation in the file whose 'via' matches a specific node.

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

  Relations *relations The set of relations to use.

  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 the first turn relation in the file whose 'via' and 'from' match a specific node and segment.

  index_t FindFirstTurnRelation2 Returns the index of the first turn relation matching.

  Relations *relations The set of relations to use.

  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;
 index_t start=0;
 index_t end=relations->file.trnumber-1;
 index_t mid;
 index_t match=-1;

 if(IsFakeSegment(from))
    from=IndexRealSegment(from);

 /* 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 matches (but may not be the first).
  */

 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 '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 turn relation in the file whose 'via' and 'from' match a specific node and segment.

  index_t FindNextTurnRelation2 Returns the index of the next turn relation matching.

  Relations *relations The set of relations to use.

  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 or 0 if not.

  Relations *relations The set of relations to use.

  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)
{
 if(IsFakeSegment(from))
    from=IndexRealSegment(from);

 if(IsFakeSegment(to))
    to=IndexRealSegment(to);

 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	amb	561	/***************************************
2			Relation data type functions.
3
4			Part of the Routino routing software.
5			****************/ /****************
6	amb	596	This file Copyright 2008-2011 Andrew M. Bishop
7	amb	561
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	amb	608	#include "fakes.h"
28	amb	561
29			#include "files.h"
30
31
32			/*++++++++++++++++++++++++++++++++++++++
33			Load in a relation list from a file.
34
35	amb	681	Relations *LoadRelationList Returns the relation list.
36	amb	561
37			const char *filename The name of the file to load.
38			++++++++++++++++++++++++++++++++++++++*/
39
40			Relations LoadRelationList(const char filename)
41			{
42			Relations *relations;
43	amb	706	#if SLIM
44			int i;
45			#endif
46	amb	561
47			relations=(Relations*)malloc(sizeof(Relations));
48
49			#if !SLIM
50
51			relations->data=MapFile(filename);
52
53			/* Copy the RelationsFile header structure from the loaded data */
54
55			relations->file=((RelationsFile)relations->data);
56
57			/* Set the pointers in the Relations structure. */
58
59			relations->turnrelations=(TurnRelation*)(relations->data+sizeof(RelationsFile));
60
61			#else
62
63			relations->fd=ReOpenFile(filename);
64
65			/* Copy the RelationsFile header structure from the loaded data */
66
67			ReadFile(relations->fd,&relations->file,sizeof(RelationsFile));
68
69			relations->troffset=sizeof(RelationsFile);
70
71	amb	706	for(i=0;i<sizeof(relations->cached)/sizeof(relations->cached[0]);i++)
72			relations->incache[i]=NO_RELATION;
73	amb	562
74	amb	561	#endif
75
76	amb	563	if(relations->file.trnumber>0)
77			{
78			TurnRelation *relation;
79
80			relation=LookupTurnRelation(relations,0,1);
81
82			relations->via_start =relation->via;
83
84			relation=LookupTurnRelation(relations,relations->file.trnumber-1,1);
85
86			relations->via_end =relation->via;
87			}
88
89	amb	561	return(relations);
90			}
91	amb	562
92
93			/*++++++++++++++++++++++++++++++++++++++
94	amb	680	Find the first turn relation in the file whose 'via' matches a specific node.
95	amb	562
96	amb	680	index_t FindFirstTurnRelation1 Returns the index of the first turn relation matching.
97	amb	562
98	amb	681	Relations *relations The set of relations to use.
99	amb	562
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	amb	780	index_t start=0;
107			index_t end=relations->file.trnumber-1;
108			index_t mid;
109			index_t match=-1;
110	amb	562
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	amb	680	* # <- end \| start or end matches (but may not be the first).
120	amb	562	*/
121
122			if(end<start) /* There are no relations */
123			return(NO_RELATION);
124
125	amb	563	if(via<relations->via_start) /* Check key is not before start */
126	amb	562	return(NO_RELATION);
127
128	amb	563	if(via>relations->via_end) /* Check key is not after end */
129	amb	562	return(NO_RELATION);
130
131			do
132			{
133			mid=(start+end)/2; /* Choose mid point */
134
135	amb	563	relation=LookupTurnRelation(relations,mid,1);
136	amb	562
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	amb	563	relation=LookupTurnRelation(relations,start,1);
152	amb	562
153			if(relation->via==via)
154			match=start;
155			}
156
157			if(match==-1) /* Check if end matches */
158			{
159	amb	563	relation=LookupTurnRelation(relations,end,1);
160	amb	562
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	amb	563	relation=LookupTurnRelation(relations,match-1,1);
171	amb	562
172			if(relation->via==via)
173			match--;
174			else
175			break;
176			}
177
178			return(match);
179			}
180
181
182			/*++++++++++++++++++++++++++++++++++++++
183	amb	680	Find the next turn relation in the file whose 'via' matches a specific node.
184	amb	562
185	amb	680	index_t FindNextTurnRelation1 Returns the index of the next turn relation matching.
186	amb	562
187	amb	681	Relations *relations The set of relations to use.
188	amb	562
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	amb	563	relation=LookupTurnRelation(relations,current,1);
198	amb	562
199			via=relation->via;
200
201			current++;
202
203	amb	596	if(current==relations->file.trnumber)
204			return(NO_RELATION);
205
206	amb	563	relation=LookupTurnRelation(relations,current,1);
207	amb	562
208			if(relation->via==via)
209			return(current);
210			else
211			return(NO_RELATION);
212			}
213
214
215			/*++++++++++++++++++++++++++++++++++++++
216	amb	680	Find the first turn relation in the file whose 'via' and 'from' match a specific node and segment.
217	amb	562
218	amb	680	index_t FindFirstTurnRelation2 Returns the index of the first turn relation matching.
219	amb	562
220	amb	681	Relations *relations The set of relations to use.
221	amb	562
222			index_t via The node that the route is going via.
223
224	amb	599	index_t from The segment that the route is coming from.
225	amb	562	++++++++++++++++++++++++++++++++++++++*/
226
227			index_t FindFirstTurnRelation2(Relations *relations,index_t via,index_t from)
228			{
229			TurnRelation *relation;
230	amb	780	index_t start=0;
231			index_t end=relations->file.trnumber-1;
232			index_t mid;
233			index_t match=-1;
234	amb	562
235	amb	608	if(IsFakeSegment(from))
236			from=IndexRealSegment(from);
237
238	amb	562	/* Binary search - search key first match is required.
239			*
240			* # <- start \| Check mid and move start or end if it doesn't match
241			* # \|
242			* # \| Since an exact match is wanted we can set end=mid-1
243			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
244			* # \|
245			* # \| Eventually either end=start or end=start+1 and one of
246	amb	680	* # <- end \| start or end matches (but may not be the first).
247	amb	562	*/
248
249	amb	563	if(end<start) /* There are no relations */
250	amb	562	return(NO_RELATION);
251
252	amb	604	if(via<relations->via_start) /* Check key is not before start */
253	amb	562	return(NO_RELATION);
254
255	amb	604	if(via>relations->via_end) /* Check key is not after end */
256	amb	562	return(NO_RELATION);
257
258			do
259			{
260	amb	563	mid=(start+end)/2; /* Choose mid point */
261	amb	562
262	amb	563	relation=LookupTurnRelation(relations,mid,1);
263	amb	562
264	amb	563	if(relation->via<via) /* Mid point is too low for 'via' */
265	amb	562	start=mid+1;
266	amb	563	else if(relation->via>via) /* Mid point is too high for 'via' */
267	amb	562	end=mid-1;
268	amb	563	else /* Mid point is correct for 'via' */
269	amb	562	{
270	amb	563	if(relation->from<from) /* Mid point is too low for 'from' */
271	amb	562	start=mid+1;
272	amb	563	else if(relation->from>from) /* Mid point is too high for 'from' */
273	amb	562	end=mid-1;
274	amb	563	else /* Mid point is correct for 'from' */
275	amb	562	{
276			match=mid;
277			break;
278			}
279			}
280			}
281			while((end-start)>1);
282
283	amb	563	if(match==-1) /* Check if start matches */
284	amb	562	{
285	amb	563	relation=LookupTurnRelation(relations,start,1);
286	amb	562
287			if(relation->via==via && relation->from==from)
288			match=start;
289			}
290
291	amb	563	if(match==-1) /* Check if end matches */
292	amb	562	{
293	amb	563	relation=LookupTurnRelation(relations,end,1);
294	amb	562
295			if(relation->via==via && relation->from==from)
296			match=end;
297			}
298
299			if(match==-1)
300			return(NO_RELATION);
301
302	amb	563	while(match>0) /* Search backwards for the first match */
303	amb	562	{
304	amb	563	relation=LookupTurnRelation(relations,match-1,1);
305	amb	562
306			if(relation->via==via && relation->from==from)
307			match--;
308			else
309			break;
310			}
311
312			return(match);
313			}
314
315
316			/*++++++++++++++++++++++++++++++++++++++
317	amb	680	Find the next turn relation in the file whose 'via' and 'from' match a specific node and segment.
318	amb	562
319	amb	680	index_t FindNextTurnRelation2 Returns the index of the next turn relation matching.
320	amb	562
321	amb	681	Relations *relations The set of relations to use.
322	amb	562
323			index_t current The current index of a relation that matches.
324			++++++++++++++++++++++++++++++++++++++*/
325
326			index_t FindNextTurnRelation2(Relations *relations,index_t current)
327			{
328			TurnRelation *relation;
329			index_t via,from;
330
331	amb	563	relation=LookupTurnRelation(relations,current,1);
332	amb	562
333			via=relation->via;
334			from=relation->from;
335
336			current++;
337
338	amb	596	if(current==relations->file.trnumber)
339			return(NO_RELATION);
340
341	amb	563	relation=LookupTurnRelation(relations,current,1);
342	amb	562
343			if(relation->via==via && relation->from==from)
344			return(current);
345			else
346			return(NO_RELATION);
347			}
348	amb	596
349
350			/*++++++++++++++++++++++++++++++++++++++
351	amb	680	Determine if a turn is allowed between the nodes 'from', 'via' and 'to' for a particular transport type.
352	amb	596
353	amb	680	int IsTurnAllowed Return 1 if the turn is allowed or 0 if not.
354	amb	596
355	amb	681	Relations *relations The set of relations to use.
356	amb	596
357	amb	680	index_t index The index of the first turn relation containing 'via' and 'from'.
358	amb	596
359			index_t via The via node.
360
361	amb	599	index_t from The from segment.
362	amb	596
363	amb	599	index_t to The to segment.
364	amb	596
365			transports_t transport The type of transport that is being routed.
366			++++++++++++++++++++++++++++++++++++++*/
367
368			int IsTurnAllowed(Relations *relations,index_t index,index_t via,index_t from,index_t to,transports_t transport)
369			{
370	amb	608	if(IsFakeSegment(from))
371			from=IndexRealSegment(from);
372
373			if(IsFakeSegment(to))
374			to=IndexRealSegment(to);
375
376	amb	596	while(index<relations->file.trnumber)
377			{
378			TurnRelation *relation=LookupTurnRelation(relations,index,1);
379
380			if(relation->via!=via)
381			return(1);
382
383			if(relation->from!=from)
384			return(1);
385
386			if(relation->to>to)
387			return(1);
388
389			if(relation->to==to)
390			if(!(relation->except & transport))
391			return(0);
392
393			index++;
394			}
395
396			return(1);
397			}