trunk/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);
}


/*++++++++++++++++++++++++++++++++++++++
  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=CloseFile(relations->fd);

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