trunk/src/relations.c

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

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2014 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();
 log_malloc(relations->cache,sizeof(*relations->cache));

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

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