Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/relations.c
Parent Directory
|
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)
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 | } |