destination-access/src/relations.c

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

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2015, 2019, 2020 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 <stdlib.h>

#include "types.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;

 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=SlimMapFile(filename);

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

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

 relations->troffset=sizeof(RelationsFile);

 relations->cache=NewTurnRelationCache();
#ifndef LIBROUTINO
 log_malloc(relations->cache,sizeof(*relations->cache));
#endif

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


/*++++++++++++++++++++++++++++++++++++++
  Destroy the relation list.

  Relations *relations The relation list to destroy.
  ++++++++++++++++++++++++++++++++++++++*/

void DestroyRelationList(Relations *relations)
{
#if !SLIM

 relations->data=UnmapFile(relations->data);

#else

 relations->fd=SlimUnmapFile(relations->fd);

#ifndef LIBROUTINO
 log_free(relations->cache);
#endif
 DeleteTurnRelationCache(relations->cache);

#endif

 free(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=NO_RELATION;

 /* Binary search - search key any exact match (may be multiple) is required.
  *
  *  # <- start  |  Check mid and exit if it matches else move start or end.
  *  #           |
  *  #           |  Since an exact match is wanted we can set end=mid-1
  *  # <- mid    |  or start=mid+1 if we find that mid doesn't match.
  *  #           |
  *  #           |  Eventually either end=start or end=start+1 and one of
  *  # <- end    |  start or end matches or neither does.
  */

 while((end-start)>1)
   {
    mid=start+(end-start)/2;        /* Choose mid point (avoid overflow) */

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

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

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

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

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

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

 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=NO_RELATION;

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

 /* Binary search - search key any exact match (may be multiple) is required.
  *
  *  # <- start  |  Check mid and exit if it matches else move start or end.
  *  #           |
  *  #           |  Since an exact match is wanted we can set end=mid-1
  *  # <- mid    |  or start=mid+1 if we find that mid doesn't match.
  *  #           |
  *  #           |  Eventually either end=start or end=start+1 and one of
  *  # <- end    |  start or end matches or neither does.
  */

 while((end-start)>1)
   {
    mid=start+(end-start)/2;        /* Choose mid point (avoid overflow) */

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

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

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

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

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

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

 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	2078	This file Copyright 2008-2015, 2019, 2020 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 <stdlib.h>
24
25	amb	955	#include "types.h"
26	amb	561	#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
44			relations=(Relations*)malloc(sizeof(Relations));
45
46			#if !SLIM
47
48			relations->data=MapFile(filename);
49
50			/* Copy the RelationsFile header structure from the loaded data */
51
52			relations->file=((RelationsFile)relations->data);
53
54			/* Set the pointers in the Relations structure. */
55
56			relations->turnrelations=(TurnRelation*)(relations->data+sizeof(RelationsFile));
57
58			#else
59
60	amb	1415	relations->fd=SlimMapFile(filename);
61	amb	561
62			/* Copy the RelationsFile header structure from the loaded data */
63
64	amb	1415	SlimFetch(relations->fd,&relations->file,sizeof(RelationsFile),0);
65	amb	561
66			relations->troffset=sizeof(RelationsFile);
67
68	amb	1292	relations->cache=NewTurnRelationCache();
69	amb	1807	#ifndef LIBROUTINO
70	amb	1602	log_malloc(relations->cache,sizeof(*relations->cache));
71	amb	1807	#endif
72	amb	562
73	amb	561	#endif
74
75	amb	563	if(relations->file.trnumber>0)
76			{
77			TurnRelation *relation;
78
79			relation=LookupTurnRelation(relations,0,1);
80
81			relations->via_start =relation->via;
82
83			relation=LookupTurnRelation(relations,relations->file.trnumber-1,1);
84
85			relations->via_end =relation->via;
86			}
87
88	amb	561	return(relations);
89			}
90	amb	562
91
92			/*++++++++++++++++++++++++++++++++++++++
93	amb	1312	Destroy the relation list.
94
95			Relations *relations The relation list to destroy.
96			++++++++++++++++++++++++++++++++++++++*/
97
98			void DestroyRelationList(Relations *relations)
99			{
100			#if !SLIM
101
102			relations->data=UnmapFile(relations->data);
103
104			#else
105
106	amb	1415	relations->fd=SlimUnmapFile(relations->fd);
107	amb	1312
108	amb	1807	#ifndef LIBROUTINO
109	amb	1602	log_free(relations->cache);
110	amb	1807	#endif
111	amb	1312	DeleteTurnRelationCache(relations->cache);
112
113			#endif
114
115			free(relations);
116			}
117
118
119			/*++++++++++++++++++++++++++++++++++++++
120	amb	680	Find the first turn relation in the file whose 'via' matches a specific node.
121	amb	562
122	amb	680	index_t FindFirstTurnRelation1 Returns the index of the first turn relation matching.
123	amb	562
124	amb	681	Relations *relations The set of relations to use.
125	amb	562
126			index_t via The node that the route is going via.
127			++++++++++++++++++++++++++++++++++++++*/
128
129			index_t FindFirstTurnRelation1(Relations *relations,index_t via)
130			{
131			TurnRelation *relation;
132	amb	780	index_t start=0;
133			index_t end=relations->file.trnumber-1;
134			index_t mid;
135	amb	1303	index_t match=NO_RELATION;
136	amb	562
137	amb	2078	/* Binary search - search key any exact match (may be multiple) is required.
138	amb	562	*
139	amb	2078	* # <- start \| Check mid and exit if it matches else move start or end.
140	amb	562	* # \|
141			* # \| Since an exact match is wanted we can set end=mid-1
142	amb	2078	* # <- mid \| or start=mid+1 if we find that mid doesn't match.
143	amb	562	* # \|
144			* # \| Eventually either end=start or end=start+1 and one of
145	amb	2078	* # <- end \| start or end matches or neither does.
146	amb	562	*/
147
148	amb	2078	while((end-start)>1)
149	amb	562	{
150	amb	1969	mid=start+(end-start)/2; /* Choose mid point (avoid overflow) */
151	amb	562
152	amb	563	relation=LookupTurnRelation(relations,mid,1);
153	amb	562
154			if(relation->via<via) /* Mid point is too low for 'via' */
155			start=mid+1;
156			else if(relation->via>via) /* Mid point is too high for 'via' */
157	amb	2078	end=mid-1;
158	amb	562	else /* Mid point is correct for 'from' */
159			{
160			match=mid;
161			break;
162			}
163			}
164
165	amb	1303	if(match==NO_RELATION) /* Check if start matches */
166	amb	562	{
167	amb	563	relation=LookupTurnRelation(relations,start,1);
168	amb	562
169			if(relation->via==via)
170			match=start;
171			}
172
173	amb	1303	if(match==NO_RELATION) /* Check if end matches */
174	amb	562	{
175	amb	563	relation=LookupTurnRelation(relations,end,1);
176	amb	562
177			if(relation->via==via)
178			match=end;
179			}
180
181	amb	1303	if(match==NO_RELATION)
182			return(match);
183	amb	562
184			while(match>0) /* Search backwards for the first match */
185			{
186	amb	563	relation=LookupTurnRelation(relations,match-1,1);
187	amb	562
188			if(relation->via==via)
189			match--;
190			else
191			break;
192			}
193
194			return(match);
195			}
196
197
198			/*++++++++++++++++++++++++++++++++++++++
199	amb	680	Find the next turn relation in the file whose 'via' matches a specific node.
200	amb	562
201	amb	680	index_t FindNextTurnRelation1 Returns the index of the next turn relation matching.
202	amb	562
203	amb	681	Relations *relations The set of relations to use.
204	amb	562
205			index_t current The current index of a relation that matches.
206			++++++++++++++++++++++++++++++++++++++*/
207
208			index_t FindNextTurnRelation1(Relations *relations,index_t current)
209			{
210			TurnRelation *relation;
211			index_t via;
212
213	amb	563	relation=LookupTurnRelation(relations,current,1);
214	amb	562
215			via=relation->via;
216
217			current++;
218
219	amb	596	if(current==relations->file.trnumber)
220			return(NO_RELATION);
221
222	amb	563	relation=LookupTurnRelation(relations,current,1);
223	amb	562
224			if(relation->via==via)
225			return(current);
226			else
227			return(NO_RELATION);
228			}
229
230
231			/*++++++++++++++++++++++++++++++++++++++
232	amb	680	Find the first turn relation in the file whose 'via' and 'from' match a specific node and segment.
233	amb	562
234	amb	680	index_t FindFirstTurnRelation2 Returns the index of the first turn relation matching.
235	amb	562
236	amb	681	Relations *relations The set of relations to use.
237	amb	562
238			index_t via The node that the route is going via.
239
240	amb	599	index_t from The segment that the route is coming from.
241	amb	562	++++++++++++++++++++++++++++++++++++++*/
242
243			index_t FindFirstTurnRelation2(Relations *relations,index_t via,index_t from)
244			{
245			TurnRelation *relation;
246	amb	780	index_t start=0;
247			index_t end=relations->file.trnumber-1;
248			index_t mid;
249	amb	1303	index_t match=NO_RELATION;
250	amb	562
251	amb	608	if(IsFakeSegment(from))
252			from=IndexRealSegment(from);
253
254	amb	2078	/* Binary search - search key any exact match (may be multiple) is required.
255	amb	562	*
256	amb	2078	* # <- start \| Check mid and exit if it matches else move start or end.
257	amb	562	* # \|
258			* # \| Since an exact match is wanted we can set end=mid-1
259	amb	2078	* # <- mid \| or start=mid+1 if we find that mid doesn't match.
260	amb	562	* # \|
261			* # \| Eventually either end=start or end=start+1 and one of
262	amb	2078	* # <- end \| start or end matches or neither does.
263	amb	562	*/
264
265	amb	2078	while((end-start)>1)
266	amb	562	{
267	amb	1969	mid=start+(end-start)/2; /* Choose mid point (avoid overflow) */
268	amb	562
269	amb	563	relation=LookupTurnRelation(relations,mid,1);
270	amb	562
271	amb	563	if(relation->via<via) /* Mid point is too low for 'via' */
272	amb	562	start=mid+1;
273	amb	563	else if(relation->via>via) /* Mid point is too high for 'via' */
274	amb	2078	end=mid-1;
275	amb	563	else /* Mid point is correct for 'via' */
276	amb	562	{
277	amb	563	if(relation->from<from) /* Mid point is too low for 'from' */
278	amb	562	start=mid+1;
279	amb	563	else if(relation->from>from) /* Mid point is too high for 'from' */
280	amb	2078	end=mid-1;
281	amb	563	else /* Mid point is correct for 'from' */
282	amb	562	{
283			match=mid;
284			break;
285			}
286			}
287			}
288
289	amb	1303	if(match==NO_RELATION) /* Check if start matches */
290	amb	562	{
291	amb	563	relation=LookupTurnRelation(relations,start,1);
292	amb	562
293			if(relation->via==via && relation->from==from)
294			match=start;
295			}
296
297	amb	1303	if(match==NO_RELATION) /* Check if end matches */
298	amb	562	{
299	amb	563	relation=LookupTurnRelation(relations,end,1);
300	amb	562
301			if(relation->via==via && relation->from==from)
302			match=end;
303			}
304
305	amb	1303	if(match==NO_RELATION)
306			return(match);
307	amb	562
308	amb	563	while(match>0) /* Search backwards for the first match */
309	amb	562	{
310	amb	563	relation=LookupTurnRelation(relations,match-1,1);
311	amb	562
312			if(relation->via==via && relation->from==from)
313			match--;
314			else
315			break;
316			}
317
318			return(match);
319			}
320
321
322			/*++++++++++++++++++++++++++++++++++++++
323	amb	680	Find the next turn relation in the file whose 'via' and 'from' match a specific node and segment.
324	amb	562
325	amb	680	index_t FindNextTurnRelation2 Returns the index of the next turn relation matching.
326	amb	562
327	amb	681	Relations *relations The set of relations to use.
328	amb	562
329			index_t current The current index of a relation that matches.
330			++++++++++++++++++++++++++++++++++++++*/
331
332			index_t FindNextTurnRelation2(Relations *relations,index_t current)
333			{
334			TurnRelation *relation;
335			index_t via,from;
336
337	amb	563	relation=LookupTurnRelation(relations,current,1);
338	amb	562
339			via=relation->via;
340			from=relation->from;
341
342			current++;
343
344	amb	596	if(current==relations->file.trnumber)
345			return(NO_RELATION);
346
347	amb	563	relation=LookupTurnRelation(relations,current,1);
348	amb	562
349			if(relation->via==via && relation->from==from)
350			return(current);
351			else
352			return(NO_RELATION);
353			}
354	amb	596
355
356			/*++++++++++++++++++++++++++++++++++++++
357	amb	680	Determine if a turn is allowed between the nodes 'from', 'via' and 'to' for a particular transport type.
358	amb	596
359	amb	680	int IsTurnAllowed Return 1 if the turn is allowed or 0 if not.
360	amb	596
361	amb	681	Relations *relations The set of relations to use.
362	amb	596
363	amb	680	index_t index The index of the first turn relation containing 'via' and 'from'.
364	amb	596
365			index_t via The via node.
366
367	amb	599	index_t from The from segment.
368	amb	596
369	amb	599	index_t to The to segment.
370	amb	596
371			transports_t transport The type of transport that is being routed.
372			++++++++++++++++++++++++++++++++++++++*/
373
374			int IsTurnAllowed(Relations *relations,index_t index,index_t via,index_t from,index_t to,transports_t transport)
375			{
376	amb	608	if(IsFakeSegment(from))
377			from=IndexRealSegment(from);
378
379			if(IsFakeSegment(to))
380			to=IndexRealSegment(to);
381
382	amb	596	while(index<relations->file.trnumber)
383			{
384			TurnRelation *relation=LookupTurnRelation(relations,index,1);
385
386			if(relation->via!=via)
387			return(1);
388
389			if(relation->from!=from)
390			return(1);
391
392			if(relation->to>to)
393			return(1);
394
395			if(relation->to==to)
396			if(!(relation->except & transport))
397			return(0);
398
399			index++;
400			}
401
402			return(1);
403			}