destination-access/src/relations.c

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

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2013 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 "cache.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->cache=NewTurnRelationCache();

#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 any exact 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).
  */

 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?(mid-1):mid;
    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).
  */

 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?(mid-1):mid;
    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?(mid-1):mid;
       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	/***************************************
2	Relation data type functions.
3
4	Part of the Routino routing software.
5	****************/ /****************
6	This file Copyright 2008-2013 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 <stdlib.h>
24
25	#include "types.h"
26	#include "relations.h"
27	#include "fakes.h"
28
29	#include "cache.h"
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->cache=NewTurnRelationCache();
70
71	#endif
72
73	if(relations->file.trnumber>0)
74	{
75	TurnRelation *relation;
76
77	relation=LookupTurnRelation(relations,0,1);
78
79	relations->via_start =relation->via;
80
81	relation=LookupTurnRelation(relations,relations->file.trnumber-1,1);
82
83	relations->via_end =relation->via;
84	}
85
86	return(relations);
87	}
88
89
90	/*++++++++++++++++++++++++++++++++++++++
91	Find the first turn relation in the file whose 'via' matches a specific node.
92
93	index_t FindFirstTurnRelation1 Returns the index of the first turn relation matching.
94
95	Relations *relations The set of relations to use.
96
97	index_t via The node that the route is going via.
98	++++++++++++++++++++++++++++++++++++++*/
99
100	index_t FindFirstTurnRelation1(Relations *relations,index_t via)
101	{
102	TurnRelation *relation;
103	index_t start=0;
104	index_t end=relations->file.trnumber-1;
105	index_t mid;
106	index_t match=-1;
107
108	/* Binary search - search key any exact match is required.
109	*
110	* # <- start \| Check mid and move start or end if it doesn't match
111	* # \|
112	* # \| Since an exact match is wanted we can set end=mid-1
113	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
114	* # \|
115	* # \| Eventually either end=start or end=start+1 and one of
116	* # <- end \| start or end matches (but may not be the first).
117	*/
118
119	do
120	{
121	mid=(start+end)/2; /* Choose mid point */
122
123	relation=LookupTurnRelation(relations,mid,1);
124
125	if(relation->via<via) /* Mid point is too low for 'via' */
126	start=mid+1;
127	else if(relation->via>via) /* Mid point is too high for 'via' */
128	end=mid?(mid-1):mid;
129	else /* Mid point is correct for 'from' */
130	{
131	match=mid;
132	break;
133	}
134	}
135	while((end-start)>1);
136
137	if(match==-1) /* Check if start matches */
138	{
139	relation=LookupTurnRelation(relations,start,1);
140
141	if(relation->via==via)
142	match=start;
143	}
144
145	if(match==-1) /* Check if end matches */
146	{
147	relation=LookupTurnRelation(relations,end,1);
148
149	if(relation->via==via)
150	match=end;
151	}
152
153	if(match==-1)
154	return(NO_RELATION);
155
156	while(match>0) /* Search backwards for the first match */
157	{
158	relation=LookupTurnRelation(relations,match-1,1);
159
160	if(relation->via==via)
161	match--;
162	else
163	break;
164	}
165
166	return(match);
167	}
168
169
170	/*++++++++++++++++++++++++++++++++++++++
171	Find the next turn relation in the file whose 'via' matches a specific node.
172
173	index_t FindNextTurnRelation1 Returns the index of the next turn relation matching.
174
175	Relations *relations The set of relations to use.
176
177	index_t current The current index of a relation that matches.
178	++++++++++++++++++++++++++++++++++++++*/
179
180	index_t FindNextTurnRelation1(Relations *relations,index_t current)
181	{
182	TurnRelation *relation;
183	index_t via;
184
185	relation=LookupTurnRelation(relations,current,1);
186
187	via=relation->via;
188
189	current++;
190
191	if(current==relations->file.trnumber)
192	return(NO_RELATION);
193
194	relation=LookupTurnRelation(relations,current,1);
195
196	if(relation->via==via)
197	return(current);
198	else
199	return(NO_RELATION);
200	}
201
202
203	/*++++++++++++++++++++++++++++++++++++++
204	Find the first turn relation in the file whose 'via' and 'from' match a specific node and segment.
205
206	index_t FindFirstTurnRelation2 Returns the index of the first turn relation matching.
207
208	Relations *relations The set of relations to use.
209
210	index_t via The node that the route is going via.
211
212	index_t from The segment that the route is coming from.
213	++++++++++++++++++++++++++++++++++++++*/
214
215	index_t FindFirstTurnRelation2(Relations *relations,index_t via,index_t from)
216	{
217	TurnRelation *relation;
218	index_t start=0;
219	index_t end=relations->file.trnumber-1;
220	index_t mid;
221	index_t match=-1;
222
223	if(IsFakeSegment(from))
224	from=IndexRealSegment(from);
225
226	/* Binary search - search key first match is required.
227	*
228	* # <- start \| Check mid and move start or end if it doesn't match
229	* # \|
230	* # \| Since an exact match is wanted we can set end=mid-1
231	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
232	* # \|
233	* # \| Eventually either end=start or end=start+1 and one of
234	* # <- end \| start or end matches (but may not be the first).
235	*/
236
237	do
238	{
239	mid=(start+end)/2; /* Choose mid point */
240
241	relation=LookupTurnRelation(relations,mid,1);
242
243	if(relation->via<via) /* Mid point is too low for 'via' */
244	start=mid+1;
245	else if(relation->via>via) /* Mid point is too high for 'via' */
246	end=mid?(mid-1):mid;
247	else /* Mid point is correct for 'via' */
248	{
249	if(relation->from<from) /* Mid point is too low for 'from' */
250	start=mid+1;
251	else if(relation->from>from) /* Mid point is too high for 'from' */
252	end=mid?(mid-1):mid;
253	else /* Mid point is correct for 'from' */
254	{
255	match=mid;
256	break;
257	}
258	}
259	}
260	while((end-start)>1);
261
262	if(match==-1) /* Check if start matches */
263	{
264	relation=LookupTurnRelation(relations,start,1);
265
266	if(relation->via==via && relation->from==from)
267	match=start;
268	}
269
270	if(match==-1) /* Check if end matches */
271	{
272	relation=LookupTurnRelation(relations,end,1);
273
274	if(relation->via==via && relation->from==from)
275	match=end;
276	}
277
278	if(match==-1)
279	return(NO_RELATION);
280
281	while(match>0) /* Search backwards for the first match */
282	{
283	relation=LookupTurnRelation(relations,match-1,1);
284
285	if(relation->via==via && relation->from==from)
286	match--;
287	else
288	break;
289	}
290
291	return(match);
292	}
293
294
295	/*++++++++++++++++++++++++++++++++++++++
296	Find the next turn relation in the file whose 'via' and 'from' match a specific node and segment.
297
298	index_t FindNextTurnRelation2 Returns the index of the next turn relation matching.
299
300	Relations *relations The set of relations to use.
301
302	index_t current The current index of a relation that matches.
303	++++++++++++++++++++++++++++++++++++++*/
304
305	index_t FindNextTurnRelation2(Relations *relations,index_t current)
306	{
307	TurnRelation *relation;
308	index_t via,from;
309
310	relation=LookupTurnRelation(relations,current,1);
311
312	via=relation->via;
313	from=relation->from;
314
315	current++;
316
317	if(current==relations->file.trnumber)
318	return(NO_RELATION);
319
320	relation=LookupTurnRelation(relations,current,1);
321
322	if(relation->via==via && relation->from==from)
323	return(current);
324	else
325	return(NO_RELATION);
326	}
327
328
329	/*++++++++++++++++++++++++++++++++++++++
330	Determine if a turn is allowed between the nodes 'from', 'via' and 'to' for a particular transport type.
331
332	int IsTurnAllowed Return 1 if the turn is allowed or 0 if not.
333
334	Relations *relations The set of relations to use.
335
336	index_t index The index of the first turn relation containing 'via' and 'from'.
337
338	index_t via The via node.
339
340	index_t from The from segment.
341
342	index_t to The to segment.
343
344	transports_t transport The type of transport that is being routed.
345	++++++++++++++++++++++++++++++++++++++*/
346
347	int IsTurnAllowed(Relations *relations,index_t index,index_t via,index_t from,index_t to,transports_t transport)
348	{
349	if(IsFakeSegment(from))
350	from=IndexRealSegment(from);
351
352	if(IsFakeSegment(to))
353	to=IndexRealSegment(to);
354
355	while(index<relations->file.trnumber)
356	{
357	TurnRelation *relation=LookupTurnRelation(relations,index,1);
358
359	if(relation->via!=via)
360	return(1);
361
362	if(relation->from!=from)
363	return(1);
364
365	if(relation->to>to)
366	return(1);
367
368	if(relation->to==to)
369	if(!(relation->except & transport))
370	return(0);
371
372	index++;
373	}
374
375	return(1);
376	}