Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

ViewVC logotype

Contents of /trunk/src/relations.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 706 - (show annotations) (download) (as text)
Sun May 8 16:39:44 2011 UTC (13 years, 10 months ago) by amb
File MIME type: text/x-csrc
File size: 10310 byte(s)
Ensure that the correct number of cached nodes, segments, ways or relations are
initialised.

1 /***************************************
2 Relation data type functions.
3
4 Part of the Routino routing software.
5 ******************/ /******************
6 This file Copyright 2008-2011 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 <sys/types.h>
24 #include <stdlib.h>
25
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 #if SLIM
44 int i;
45 #endif
46
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 for(i=0;i<sizeof(relations->cached)/sizeof(relations->cached[0]);i++)
72 relations->incache[i]=NO_RELATION;
73
74 #endif
75
76 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 return(relations);
90 }
91
92
93 /*++++++++++++++++++++++++++++++++++++++
94 Find the first turn relation in the file whose 'via' matches a specific node.
95
96 index_t FindFirstTurnRelation1 Returns the index of the first turn relation matching.
97
98 Relations *relations The set of relations to use.
99
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 int start=0;
107 int end=relations->file.trnumber-1;
108 int mid;
109 int match=-1;
110
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 * # <- end | start or end matches (but may not be the first).
120 */
121
122 if(end<start) /* There are no relations */
123 return(NO_RELATION);
124
125 if(via<relations->via_start) /* Check key is not before start */
126 return(NO_RELATION);
127
128 if(via>relations->via_end) /* Check key is not after end */
129 return(NO_RELATION);
130
131 do
132 {
133 mid=(start+end)/2; /* Choose mid point */
134
135 relation=LookupTurnRelation(relations,mid,1);
136
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 relation=LookupTurnRelation(relations,start,1);
152
153 if(relation->via==via)
154 match=start;
155 }
156
157 if(match==-1) /* Check if end matches */
158 {
159 relation=LookupTurnRelation(relations,end,1);
160
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 relation=LookupTurnRelation(relations,match-1,1);
171
172 if(relation->via==via)
173 match--;
174 else
175 break;
176 }
177
178 return(match);
179 }
180
181
182 /*++++++++++++++++++++++++++++++++++++++
183 Find the next turn relation in the file whose 'via' matches a specific node.
184
185 index_t FindNextTurnRelation1 Returns the index of the next turn relation matching.
186
187 Relations *relations The set of relations to use.
188
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 relation=LookupTurnRelation(relations,current,1);
198
199 via=relation->via;
200
201 current++;
202
203 if(current==relations->file.trnumber)
204 return(NO_RELATION);
205
206 relation=LookupTurnRelation(relations,current,1);
207
208 if(relation->via==via)
209 return(current);
210 else
211 return(NO_RELATION);
212 }
213
214
215 /*++++++++++++++++++++++++++++++++++++++
216 Find the first turn relation in the file whose 'via' and 'from' match a specific node and segment.
217
218 index_t FindFirstTurnRelation2 Returns the index of the first turn relation matching.
219
220 Relations *relations The set of relations to use.
221
222 index_t via The node that the route is going via.
223
224 index_t from The segment that the route is coming from.
225 ++++++++++++++++++++++++++++++++++++++*/
226
227 index_t FindFirstTurnRelation2(Relations *relations,index_t via,index_t from)
228 {
229 TurnRelation *relation;
230 int start=0;
231 int end=relations->file.trnumber-1;
232 int mid;
233 int match=-1;
234
235 if(IsFakeSegment(from))
236 from=IndexRealSegment(from);
237
238 /* 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 * # <- end | start or end matches (but may not be the first).
247 */
248
249 if(end<start) /* There are no relations */
250 return(NO_RELATION);
251
252 if(via<relations->via_start) /* Check key is not before start */
253 return(NO_RELATION);
254
255 if(via>relations->via_end) /* Check key is not after end */
256 return(NO_RELATION);
257
258 do
259 {
260 mid=(start+end)/2; /* Choose mid point */
261
262 relation=LookupTurnRelation(relations,mid,1);
263
264 if(relation->via<via) /* Mid point is too low for 'via' */
265 start=mid+1;
266 else if(relation->via>via) /* Mid point is too high for 'via' */
267 end=mid-1;
268 else /* Mid point is correct for 'via' */
269 {
270 if(relation->from<from) /* Mid point is too low for 'from' */
271 start=mid+1;
272 else if(relation->from>from) /* Mid point is too high for 'from' */
273 end=mid-1;
274 else /* Mid point is correct for 'from' */
275 {
276 match=mid;
277 break;
278 }
279 }
280 }
281 while((end-start)>1);
282
283 if(match==-1) /* Check if start matches */
284 {
285 relation=LookupTurnRelation(relations,start,1);
286
287 if(relation->via==via && relation->from==from)
288 match=start;
289 }
290
291 if(match==-1) /* Check if end matches */
292 {
293 relation=LookupTurnRelation(relations,end,1);
294
295 if(relation->via==via && relation->from==from)
296 match=end;
297 }
298
299 if(match==-1)
300 return(NO_RELATION);
301
302 while(match>0) /* Search backwards for the first match */
303 {
304 relation=LookupTurnRelation(relations,match-1,1);
305
306 if(relation->via==via && relation->from==from)
307 match--;
308 else
309 break;
310 }
311
312 return(match);
313 }
314
315
316 /*++++++++++++++++++++++++++++++++++++++
317 Find the next turn relation in the file whose 'via' and 'from' match a specific node and segment.
318
319 index_t FindNextTurnRelation2 Returns the index of the next turn relation matching.
320
321 Relations *relations The set of relations to use.
322
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 relation=LookupTurnRelation(relations,current,1);
332
333 via=relation->via;
334 from=relation->from;
335
336 current++;
337
338 if(current==relations->file.trnumber)
339 return(NO_RELATION);
340
341 relation=LookupTurnRelation(relations,current,1);
342
343 if(relation->via==via && relation->from==from)
344 return(current);
345 else
346 return(NO_RELATION);
347 }
348
349
350 /*++++++++++++++++++++++++++++++++++++++
351 Determine if a turn is allowed between the nodes 'from', 'via' and 'to' for a particular transport type.
352
353 int IsTurnAllowed Return 1 if the turn is allowed or 0 if not.
354
355 Relations *relations The set of relations to use.
356
357 index_t index The index of the first turn relation containing 'via' and 'from'.
358
359 index_t via The via node.
360
361 index_t from The from segment.
362
363 index_t to The to segment.
364
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 if(IsFakeSegment(from))
371 from=IndexRealSegment(from);
372
373 if(IsFakeSegment(to))
374 to=IndexRealSegment(to);
375
376 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 }