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 680 -
(show annotations)
(download)
(as text)
Sun Apr 24 15:14:53 2011 UTC (13 years, 10 months ago) by amb
File MIME type: text/x-csrc
File size: 10268 byte(s)
Sun Apr 24 15:14:53 2011 UTC (13 years, 10 months ago) by amb
File MIME type: text/x-csrc
File size: 10268 byte(s)
Update comments throughout the source code.
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 | |
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=ReOpenFile(filename); |
61 | |
62 | /* Copy the RelationsFile header structure from the loaded data */ |
63 | |
64 | ReadFile(relations->fd,&relations->file,sizeof(RelationsFile)); |
65 | |
66 | relations->troffset=sizeof(RelationsFile); |
67 | |
68 | relations->incache[0]=NO_RELATION; |
69 | relations->incache[1]=NO_RELATION; |
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 process. |
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 | int start=0; |
104 | int end=relations->file.trnumber-1; |
105 | int mid; |
106 | int match=-1; |
107 | |
108 | /* Binary search - search key first 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 | if(end<start) /* There are no relations */ |
120 | return(NO_RELATION); |
121 | |
122 | if(via<relations->via_start) /* Check key is not before start */ |
123 | return(NO_RELATION); |
124 | |
125 | if(via>relations->via_end) /* Check key is not after end */ |
126 | return(NO_RELATION); |
127 | |
128 | do |
129 | { |
130 | mid=(start+end)/2; /* Choose mid point */ |
131 | |
132 | relation=LookupTurnRelation(relations,mid,1); |
133 | |
134 | if(relation->via<via) /* Mid point is too low for 'via' */ |
135 | start=mid+1; |
136 | else if(relation->via>via) /* Mid point is too high for 'via' */ |
137 | end=mid-1; |
138 | else /* Mid point is correct for 'from' */ |
139 | { |
140 | match=mid; |
141 | break; |
142 | } |
143 | } |
144 | while((end-start)>1); |
145 | |
146 | if(match==-1) /* Check if start matches */ |
147 | { |
148 | relation=LookupTurnRelation(relations,start,1); |
149 | |
150 | if(relation->via==via) |
151 | match=start; |
152 | } |
153 | |
154 | if(match==-1) /* Check if end matches */ |
155 | { |
156 | relation=LookupTurnRelation(relations,end,1); |
157 | |
158 | if(relation->via==via) |
159 | match=end; |
160 | } |
161 | |
162 | if(match==-1) |
163 | return(NO_RELATION); |
164 | |
165 | while(match>0) /* Search backwards for the first match */ |
166 | { |
167 | relation=LookupTurnRelation(relations,match-1,1); |
168 | |
169 | if(relation->via==via) |
170 | match--; |
171 | else |
172 | break; |
173 | } |
174 | |
175 | return(match); |
176 | } |
177 | |
178 | |
179 | /*++++++++++++++++++++++++++++++++++++++ |
180 | Find the next turn relation in the file whose 'via' matches a specific node. |
181 | |
182 | index_t FindNextTurnRelation1 Returns the index of the next turn relation matching. |
183 | |
184 | Relations *relations The set of relations to process. |
185 | |
186 | index_t current The current index of a relation that matches. |
187 | ++++++++++++++++++++++++++++++++++++++*/ |
188 | |
189 | index_t FindNextTurnRelation1(Relations *relations,index_t current) |
190 | { |
191 | TurnRelation *relation; |
192 | index_t via; |
193 | |
194 | relation=LookupTurnRelation(relations,current,1); |
195 | |
196 | via=relation->via; |
197 | |
198 | current++; |
199 | |
200 | if(current==relations->file.trnumber) |
201 | return(NO_RELATION); |
202 | |
203 | relation=LookupTurnRelation(relations,current,1); |
204 | |
205 | if(relation->via==via) |
206 | return(current); |
207 | else |
208 | return(NO_RELATION); |
209 | } |
210 | |
211 | |
212 | /*++++++++++++++++++++++++++++++++++++++ |
213 | Find the first turn relation in the file whose 'via' and 'from' match a specific node and segment. |
214 | |
215 | index_t FindFirstTurnRelation2 Returns the index of the first turn relation matching. |
216 | |
217 | Relations *relations The set of relations to process. |
218 | |
219 | index_t via The node that the route is going via. |
220 | |
221 | index_t from The segment that the route is coming from. |
222 | ++++++++++++++++++++++++++++++++++++++*/ |
223 | |
224 | index_t FindFirstTurnRelation2(Relations *relations,index_t via,index_t from) |
225 | { |
226 | TurnRelation *relation; |
227 | int start=0; |
228 | int end=relations->file.trnumber-1; |
229 | int mid; |
230 | int match=-1; |
231 | |
232 | if(IsFakeSegment(from)) |
233 | from=IndexRealSegment(from); |
234 | |
235 | /* Binary search - search key first match is required. |
236 | * |
237 | * # <- start | Check mid and move start or end if it doesn't match |
238 | * # | |
239 | * # | Since an exact match is wanted we can set end=mid-1 |
240 | * # <- mid | or start=mid+1 because we know that mid doesn't match. |
241 | * # | |
242 | * # | Eventually either end=start or end=start+1 and one of |
243 | * # <- end | start or end matches (but may not be the first). |
244 | */ |
245 | |
246 | if(end<start) /* There are no relations */ |
247 | return(NO_RELATION); |
248 | |
249 | if(via<relations->via_start) /* Check key is not before start */ |
250 | return(NO_RELATION); |
251 | |
252 | if(via>relations->via_end) /* Check key is not after end */ |
253 | return(NO_RELATION); |
254 | |
255 | do |
256 | { |
257 | mid=(start+end)/2; /* Choose mid point */ |
258 | |
259 | relation=LookupTurnRelation(relations,mid,1); |
260 | |
261 | if(relation->via<via) /* Mid point is too low for 'via' */ |
262 | start=mid+1; |
263 | else if(relation->via>via) /* Mid point is too high for 'via' */ |
264 | end=mid-1; |
265 | else /* Mid point is correct for 'via' */ |
266 | { |
267 | if(relation->from<from) /* Mid point is too low for 'from' */ |
268 | start=mid+1; |
269 | else if(relation->from>from) /* Mid point is too high for 'from' */ |
270 | end=mid-1; |
271 | else /* Mid point is correct for 'from' */ |
272 | { |
273 | match=mid; |
274 | break; |
275 | } |
276 | } |
277 | } |
278 | while((end-start)>1); |
279 | |
280 | if(match==-1) /* Check if start matches */ |
281 | { |
282 | relation=LookupTurnRelation(relations,start,1); |
283 | |
284 | if(relation->via==via && relation->from==from) |
285 | match=start; |
286 | } |
287 | |
288 | if(match==-1) /* Check if end matches */ |
289 | { |
290 | relation=LookupTurnRelation(relations,end,1); |
291 | |
292 | if(relation->via==via && relation->from==from) |
293 | match=end; |
294 | } |
295 | |
296 | if(match==-1) |
297 | return(NO_RELATION); |
298 | |
299 | while(match>0) /* Search backwards for the first match */ |
300 | { |
301 | relation=LookupTurnRelation(relations,match-1,1); |
302 | |
303 | if(relation->via==via && relation->from==from) |
304 | match--; |
305 | else |
306 | break; |
307 | } |
308 | |
309 | return(match); |
310 | } |
311 | |
312 | |
313 | /*++++++++++++++++++++++++++++++++++++++ |
314 | Find the next turn relation in the file whose 'via' and 'from' match a specific node and segment. |
315 | |
316 | index_t FindNextTurnRelation2 Returns the index of the next turn relation matching. |
317 | |
318 | Relations *relations The set of relations to process. |
319 | |
320 | index_t current The current index of a relation that matches. |
321 | ++++++++++++++++++++++++++++++++++++++*/ |
322 | |
323 | index_t FindNextTurnRelation2(Relations *relations,index_t current) |
324 | { |
325 | TurnRelation *relation; |
326 | index_t via,from; |
327 | |
328 | relation=LookupTurnRelation(relations,current,1); |
329 | |
330 | via=relation->via; |
331 | from=relation->from; |
332 | |
333 | current++; |
334 | |
335 | if(current==relations->file.trnumber) |
336 | return(NO_RELATION); |
337 | |
338 | relation=LookupTurnRelation(relations,current,1); |
339 | |
340 | if(relation->via==via && relation->from==from) |
341 | return(current); |
342 | else |
343 | return(NO_RELATION); |
344 | } |
345 | |
346 | |
347 | /*++++++++++++++++++++++++++++++++++++++ |
348 | Determine if a turn is allowed between the nodes 'from', 'via' and 'to' for a particular transport type. |
349 | |
350 | int IsTurnAllowed Return 1 if the turn is allowed or 0 if not. |
351 | |
352 | Relations *relations The set of relations to process. |
353 | |
354 | index_t index The index of the first turn relation containing 'via' and 'from'. |
355 | |
356 | index_t via The via node. |
357 | |
358 | index_t from The from segment. |
359 | |
360 | index_t to The to segment. |
361 | |
362 | transports_t transport The type of transport that is being routed. |
363 | ++++++++++++++++++++++++++++++++++++++*/ |
364 | |
365 | int IsTurnAllowed(Relations *relations,index_t index,index_t via,index_t from,index_t to,transports_t transport) |
366 | { |
367 | if(IsFakeSegment(from)) |
368 | from=IndexRealSegment(from); |
369 | |
370 | if(IsFakeSegment(to)) |
371 | to=IndexRealSegment(to); |
372 | |
373 | while(index<relations->file.trnumber) |
374 | { |
375 | TurnRelation *relation=LookupTurnRelation(relations,index,1); |
376 | |
377 | if(relation->via!=via) |
378 | return(1); |
379 | |
380 | if(relation->from!=from) |
381 | return(1); |
382 | |
383 | if(relation->to>to) |
384 | return(1); |
385 | |
386 | if(relation->to==to) |
387 | if(!(relation->except & transport)) |
388 | return(0); |
389 | |
390 | index++; |
391 | } |
392 | |
393 | return(1); |
394 | } |