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 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)
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 }