Routino SVN Repository Browser

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

/[routino]/trunk/src/optimiser.c
ViewVC logotype

Annotation of /trunk/src/optimiser.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 64 - (hide annotations) (download) (as text)
Wed Jan 21 20:11:41 2009 UTC (16 years, 2 months ago) by amb
File MIME type: text/x-csrc
File size: 39184 byte(s) 
Various small speed-ups including not-reversing direction.
1 amb 2 /***************************************
2 amb 64 $Header: /home/amb/CVS/routino/src/optimiser.c,v 1.24 2009-01-21 20:11:41 amb Exp $
3 amb 2
4     Routing optimiser.
5     ******************/ /******************
6     Written by Andrew M. Bishop
7    
8 amb 3 This file Copyright 2008,2009 Andrew M. Bishop
9 amb 2 It may be distributed under the GNU Public License, version 2, or
10     any higher version. See section COPYING of the GNU Public license
11     for conditions under which this file may be redistributed.
12     ***************************************/
13    
14    
15 amb 11 #include <assert.h>
16 amb 2 #include <string.h>
17     #include <stdlib.h>
18    
19 amb 26 #include "nodes.h"
20     #include "ways.h"
21     #include "segments.h"
22 amb 28 #include "results.h"
23 amb 2 #include "functions.h"
24    
25 amb 26
26 amb 11 #define INCREMENT 1024
27 amb 2
28 amb 10
29 amb 2 /*+ A queue results. +*/
30     typedef struct _Queue
31     {
32 amb 45 uint32_t alloced; /*+ The amount of space allocated for results in the array. +*/
33     uint32_t number; /*+ The number of occupied results in the array. +*/
34     uint32_t *queue; /*+ An array of offsets into the results array. +*/
35 amb 2 }
36     Queue;
37    
38    
39     /*+ The queue of nodes. +*/
40 amb 45 Queue OSMQueue={0,0,NULL};
41 amb 2
42 amb 31 /*+ Print the progress? +*/
43     int print_progress=1;
44 amb 2
45 amb 31
46 amb 2 /* Functions */
47    
48 amb 45 static void insert_in_queue(Results *results,Result *result);
49 amb 2
50    
51     /*++++++++++++++++++++++++++++++++++++++
52     Find the optimum route between two nodes.
53    
54 amb 26 Results *FindRoute Returns a set of results.
55    
56     Nodes *nodes The set of nodes to use.
57    
58     Segments *segments The set of segments to use.
59    
60 amb 54 Ways *ways The set of ways to use.
61    
62 amb 2 node_t start The start node.
63    
64     node_t finish The finish node.
65 amb 54
66     wayallow_t transport The mode of transport.
67 amb 2 ++++++++++++++++++++++++++++++++++++++*/
68    
69 amb 54 Results *FindRoute(Nodes *nodes,Segments *segments,Ways *ways,node_t start,node_t finish,wayallow_t transport)
70 amb 2 {
71 amb 31 Results *results;
72 amb 43 node_t node1,node2;
73 amb 10 HalfResult shortest1,quickest1;
74     HalfResult shortest2,quickest2;
75     HalfResult shortestfinish,quickestfinish;
76 amb 2 Result *result1,*result2;
77     Segment *segment;
78 amb 54 Way *way;
79 amb 2
80 amb 10 /* Set up the finish conditions */
81    
82 amb 36 shortestfinish.distance=INVALID_DISTANCE;
83     shortestfinish.duration=INVALID_DURATION;
84     quickestfinish.distance=INVALID_DISTANCE;
85     quickestfinish.duration=INVALID_DURATION;
86 amb 10
87 amb 2 /* Insert the first node into the queue */
88    
89 amb 31 results=NewResultsList();
90 amb 2
91 amb 31 result1=InsertResult(results,start);
92 amb 28
93 amb 2 result1->node=start;
94 amb 43 result1->shortest.prev=0;
95     result1->shortest.next=0;
96 amb 10 result1->shortest.distance=0;
97     result1->shortest.duration=0;
98 amb 43 result1->quickest.prev=0;
99     result1->quickest.next=0;
100 amb 10 result1->quickest.distance=0;
101     result1->quickest.duration=0;
102 amb 2
103 amb 45 insert_in_queue(results,result1);
104 amb 2
105     /* Loop across all nodes in the queue */
106    
107 amb 45 while(OSMQueue.number>0)
108 amb 2 {
109 amb 45 result1=LookupResult(results,OSMQueue.queue[--OSMQueue.number]);
110 amb 43 node1=result1->node;
111 amb 64 shortest1=result1->shortest;
112     quickest1=result1->quickest;
113 amb 2
114 amb 43 segment=FindFirstSegment(segments,node1);
115 amb 2
116     while(segment)
117     {
118 amb 59 duration_t segment_duration;
119    
120 amb 64 if(segment->distance==INVALID_DISTANCE)
121     goto endloop;
122    
123 amb 2 node2=segment->node2;
124    
125 amb 64 if(shortest1.prev==node2 && quickest1.prev==node2)
126     goto endloop;
127    
128 amb 54 way=FindWay(ways,segment->way);
129    
130     if((way->allow&transport)!=transport)
131     goto endloop;
132    
133 amb 63 segment_duration=Duration(segment,way,transport);
134 amb 59
135 amb 10 shortest2.distance=shortest1.distance+segment->distance;
136 amb 59 shortest2.duration=shortest1.duration+segment_duration;
137 amb 10 quickest2.distance=quickest1.distance+segment->distance;
138 amb 59 quickest2.duration=quickest1.duration+segment_duration;
139 amb 2
140 amb 10 if(shortest2.distance>shortestfinish.distance && quickest2.duration>quickestfinish.duration)
141 amb 2 goto endloop;
142    
143 amb 42 result2=FindResult(results,node2);
144    
145 amb 2 if(!result2) /* New end node */
146     {
147 amb 31 result2=InsertResult(results,node2);
148 amb 2 result2->node=node2;
149 amb 43 result2->shortest.prev=node1;
150     result2->shortest.next=0;
151 amb 10 result2->shortest.distance=shortest2.distance;
152     result2->shortest.duration=shortest2.duration;
153 amb 43 result2->quickest.prev=node1;
154     result2->quickest.next=0;
155 amb 10 result2->quickest.distance=quickest2.distance;
156     result2->quickest.duration=quickest2.duration;
157 amb 2
158     if(node2==finish)
159     {
160 amb 10 shortestfinish.distance=shortest2.distance;
161     shortestfinish.duration=shortest2.duration;
162     quickestfinish.distance=quickest2.distance;
163     quickestfinish.duration=quickest2.duration;
164 amb 2 }
165     else
166 amb 45 insert_in_queue(results,result2);
167 amb 2 }
168     else
169     {
170 amb 10 if(shortest2.distance<result2->shortest.distance ||
171     (shortest2.distance==result2->shortest.distance &&
172     shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
173 amb 2 {
174 amb 43 result2->shortest.prev=node1;
175 amb 10 result2->shortest.distance=shortest2.distance;
176     result2->shortest.duration=shortest2.duration;
177 amb 2
178     if(node2==finish)
179     {
180 amb 10 shortestfinish.distance=shortest2.distance;
181     shortestfinish.duration=shortest2.duration;
182 amb 2 }
183     else
184 amb 45 insert_in_queue(results,result2);
185 amb 2 }
186    
187 amb 10 if(quickest2.duration<result2->quickest.duration ||
188     (quickest2.duration==result2->quickest.duration &&
189     quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
190 amb 2 {
191 amb 43 result2->quickest.prev=node1;
192 amb 10 result2->quickest.distance=quickest2.distance;
193     result2->quickest.duration=quickest2.duration;
194 amb 2
195     if(node2==finish)
196     {
197 amb 10 quickestfinish.distance=quickest2.distance;
198     quickestfinish.duration=quickest2.duration;
199 amb 2 }
200     else
201 amb 45 insert_in_queue(results,result2);
202 amb 2 }
203     }
204    
205     endloop:
206    
207 amb 26 segment=FindNextSegment(segments,segment);
208 amb 2 }
209    
210 amb 64 if(print_progress && !(results->number%10000))
211 amb 2 {
212 amb 64 printf("\rRouting: End Nodes=%d Queue=%d Journey=%.1fkm,%.0fmin ",results->number,OSMQueue.number,
213 amb 10 distance_to_km(shortest2.distance),duration_to_minutes(quickest2.duration));
214 amb 2 fflush(stdout);
215     }
216     }
217    
218 amb 31 if(print_progress)
219     {
220 amb 64 printf("\rRouted: End Nodes=%d Shortest=%.1fkm,%.0fmin Quickest=%.1fkm,%.0fmin\n",results->number,
221 amb 31 distance_to_km(shortestfinish.distance),duration_to_minutes(shortestfinish.duration),
222     distance_to_km(quickestfinish.distance),duration_to_minutes(quickestfinish.duration));
223     fflush(stdout);
224     }
225    
226     /* Reverse the results */
227    
228     result2=FindResult(results,finish);
229    
230     do
231     {
232 amb 43 if(result2->shortest.prev)
233 amb 31 {
234 amb 43 node_t node1=result2->shortest.prev;
235 amb 31
236     result1=FindResult(results,node1);
237    
238 amb 43 result1->shortest.next=result2->node;
239 amb 31
240     result2=result1;
241     }
242     else
243     result2=NULL;
244     }
245     while(result2);
246    
247     result2=FindResult(results,finish);
248    
249     do
250     {
251 amb 43 if(result2->quickest.prev)
252 amb 31 {
253 amb 43 node_t node1=result2->quickest.prev;
254 amb 31
255     result1=FindResult(results,node1);
256    
257 amb 43 result1->quickest.next=result2->node;
258 amb 31
259     result2=result1;
260     }
261     else
262     result2=NULL;
263     }
264     while(result2);
265    
266     return(results);
267 amb 2 }
268    
269    
270     /*++++++++++++++++++++++++++++++++++++++
271 amb 34 Find the optimum route between two nodes.
272    
273     Results *FindRoute3 Returns a set of results.
274    
275 amb 58 Nodes *supernodes The set of supernodes to use.
276 amb 34
277 amb 58 Segments *supersegments The set of supersegments to use.
278 amb 34
279 amb 58 Ways *superways The set of superways to use.
280 amb 54
281 amb 34 node_t start The start node.
282    
283     node_t finish The finish node.
284    
285     Results *begin The initial portion of the route.
286    
287     Results *end The final portion of the route.
288 amb 54
289     wayallow_t transport The mode of transport.
290 amb 34 ++++++++++++++++++++++++++++++++++++++*/
291    
292 amb 58 Results *FindRoute3(Nodes *supernodes,Segments *supersegments,Ways *superways,node_t start,node_t finish,Results *begin,Results *end,wayallow_t transport)
293 amb 34 {
294     Results *results;
295 amb 43 node_t node1,node2;
296 amb 34 HalfResult shortest1,quickest1;
297     HalfResult shortest2,quickest2;
298     HalfResult shortestfinish,quickestfinish;
299     Result *result1,*result2,*result3;
300     Segment *segment;
301 amb 54 Way *way;
302 amb 45 int j;
303 amb 34
304     /* Set up the finish conditions */
305    
306 amb 36 shortestfinish.distance=INVALID_DISTANCE;
307     shortestfinish.duration=INVALID_DURATION;
308     quickestfinish.distance=INVALID_DISTANCE;
309     quickestfinish.duration=INVALID_DURATION;
310 amb 34
311 amb 58 /* Insert the start node */
312 amb 34
313     results=NewResultsList();
314    
315     result1=InsertResult(results,start);
316     result2=FindResult(begin,start);
317    
318     *result1=*result2;
319    
320     /* Insert the finish points of the beginning part of the path into the queue */
321    
322 amb 45 for(j=0;j<begin->number;j++)
323 amb 58 if(FindNode(supernodes,begin->results[j].node))
324 amb 45 {
325     if(!(result1=FindResult(results,begin->results[j].node)))
326 amb 34 {
327 amb 45 result1=InsertResult(results,begin->results[j].node);
328 amb 34
329 amb 45 *result1=begin->results[j];
330 amb 34
331 amb 45 result1->shortest.prev=start;
332     result1->quickest.prev=start;
333 amb 47 }
334 amb 34
335 amb 47 insert_in_queue(results,result1);
336 amb 45 }
337 amb 34
338 amb 58 /* Loop across all supernodes in the queue */
339 amb 34
340 amb 45 while(OSMQueue.number>0)
341 amb 34 {
342 amb 45 result1=LookupResult(results,OSMQueue.queue[--OSMQueue.number]);
343 amb 43 node1=result1->node;
344 amb 64 shortest1=result1->shortest;
345     quickest1=result1->quickest;
346 amb 34
347 amb 58 segment=FindFirstSegment(supersegments,node1);
348 amb 34
349     while(segment)
350     {
351 amb 59 duration_t segment_duration;
352    
353 amb 64 if(segment->distance==INVALID_DISTANCE)
354     goto endloop;
355    
356 amb 34 node2=segment->node2;
357    
358 amb 64 if(shortest1.prev==node2 && quickest1.prev==node2)
359     goto endloop;
360    
361 amb 58 way=FindWay(superways,segment->way);
362 amb 54
363     if((way->allow&transport)!=transport)
364     goto endloop;
365    
366 amb 63 segment_duration=Duration(segment,way,transport);
367 amb 34
368 amb 59 shortest2.distance=shortest1.distance+segment->distance;
369     shortest2.duration=shortest1.duration+segment_duration;
370     quickest2.distance=quickest1.distance+segment->distance;
371     quickest2.duration=quickest1.duration+segment_duration;
372    
373 amb 34 if(shortest2.distance>shortestfinish.distance && quickest2.duration>quickestfinish.duration)
374     goto endloop;
375    
376 amb 42 result2=FindResult(results,node2);
377 amb 64 result3=NULL;
378 amb 42
379 amb 34 if(!result2) /* New end node */
380     {
381     result2=InsertResult(results,node2);
382     result2->node=node2;
383 amb 43 result2->shortest.prev=node1;
384     result2->shortest.next=0;
385 amb 34 result2->shortest.distance=shortest2.distance;
386     result2->shortest.duration=shortest2.duration;
387 amb 43 result2->quickest.prev=node1;
388     result2->quickest.next=0;
389 amb 34 result2->quickest.distance=quickest2.distance;
390     result2->quickest.duration=quickest2.duration;
391    
392 amb 64 if(!(result3=FindResult(end,node2)))
393 amb 45 insert_in_queue(results,result2);
394 amb 34 }
395     else
396     {
397     if(shortest2.distance<result2->shortest.distance ||
398     (shortest2.distance==result2->shortest.distance &&
399     shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
400     {
401 amb 43 result2->shortest.prev=node1;
402 amb 34 result2->shortest.distance=shortest2.distance;
403     result2->shortest.duration=shortest2.duration;
404    
405 amb 64 if(!(result3=FindResult(end,node2)))
406 amb 45 insert_in_queue(results,result2);
407 amb 34 }
408    
409     if(quickest2.duration<result2->quickest.duration ||
410     (quickest2.duration==result2->quickest.duration &&
411     quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
412     {
413 amb 43 result2->quickest.prev=node1;
414 amb 34 result2->quickest.distance=quickest2.distance;
415     result2->quickest.duration=quickest2.duration;
416    
417 amb 64 if(!(result3=FindResult(end,node2)))
418 amb 45 insert_in_queue(results,result2);
419 amb 34 }
420     }
421    
422 amb 64 if(result3)
423     {
424     if((shortest2.distance+result3->shortest.distance)<shortestfinish.distance ||
425     ((shortest2.distance+result3->shortest.distance)==shortestfinish.distance &&
426     (shortest2.duration+result3->shortest.duration)<shortestfinish.duration))
427     {
428     shortestfinish.distance=shortest2.distance+result3->shortest.distance;
429     shortestfinish.duration=shortest2.duration+result3->shortest.duration;
430     }
431     if((quickest2.duration+result3->quickest.duration)<quickestfinish.duration ||
432     ((quickest2.duration+result3->quickest.duration)==quickestfinish.duration &&
433     (quickest2.distance+result3->quickest.distance)<quickestfinish.distance))
434     {
435     quickestfinish.distance=quickest2.distance+result3->quickest.distance;
436     quickestfinish.duration=quickest2.duration+result3->quickest.duration;
437     }
438     }
439    
440 amb 34 endloop:
441    
442 amb 58 segment=FindNextSegment(supersegments,segment);
443 amb 34 }
444    
445 amb 64 if(print_progress && !(results->number%10000))
446 amb 34 {
447 amb 64 printf("\rRouting: End Super-Nodes=%d Queue=%d Journey=%.1fkm,%.0fmin ",results->number,OSMQueue.number,
448 amb 34 distance_to_km(shortest2.distance),duration_to_minutes(quickest2.duration));
449     fflush(stdout);
450     }
451     }
452    
453     if(print_progress)
454     {
455 amb 64 printf("\rRouted: End Super-Nodes=%d Shortest=%.1fkm,%.0fmin Quickest=%.1fkm,%.0fmin\n",results->number,
456 amb 34 distance_to_km(shortestfinish.distance),duration_to_minutes(shortestfinish.duration),
457     distance_to_km(quickestfinish.distance),duration_to_minutes(quickestfinish.duration));
458     fflush(stdout);
459     }
460    
461     /* Finish off the end part of the route. */
462    
463 amb 54 if(!FindResult(results,finish))
464 amb 47 {
465 amb 54 result2=InsertResult(results,finish);
466     result1=FindResult(end,finish);
467 amb 34
468 amb 54 *result2=*result1;
469 amb 47
470 amb 54 result2->shortest.distance=INVALID_DISTANCE;
471     result2->shortest.duration=INVALID_DURATION;
472     result2->quickest.distance=INVALID_DISTANCE;
473     result2->quickest.duration=INVALID_DURATION;
474    
475 amb 47 for(j=0;j<end->number;j++)
476 amb 58 if(FindNode(supernodes,end->results[j].node))
477 amb 47 if((result1=FindResult(results,end->results[j].node)))
478 amb 34 {
479 amb 47 if((result1->shortest.distance+end->results[j].shortest.distance)<result2->shortest.distance ||
480     ((result1->shortest.distance+end->results[j].shortest.distance)==result2->shortest.distance &&
481     (result1->shortest.duration+end->results[j].shortest.duration)<result2->shortest.duration))
482     {
483     result2->shortest.distance=result1->shortest.distance+end->results[j].shortest.distance;
484     result2->shortest.duration=result1->shortest.duration+end->results[j].shortest.duration;
485     result2->shortest.prev=result1->node;
486     }
487     if((result1->quickest.duration+end->results[j].quickest.duration)<result2->quickest.duration ||
488     ((result1->quickest.duration+end->results[j].quickest.duration)==result2->quickest.duration &&
489     (result1->quickest.distance+end->results[j].quickest.distance)<result2->quickest.distance))
490     {
491     result2->quickest.distance=result1->quickest.distance+end->results[j].quickest.distance;
492     result2->quickest.duration=result1->quickest.duration+end->results[j].quickest.duration;
493     result2->quickest.prev=result1->node;
494     }
495 amb 34 }
496 amb 47 }
497 amb 34
498     /* Reverse the results */
499    
500     result2=FindResult(results,finish);
501    
502     do
503     {
504 amb 43 if(result2->shortest.prev)
505 amb 34 {
506 amb 43 node_t node1=result2->shortest.prev;
507 amb 34
508     result1=FindResult(results,node1);
509    
510 amb 43 result1->shortest.next=result2->node;
511 amb 34
512     result2=result1;
513     }
514     else
515     result2=NULL;
516     }
517     while(result2);
518    
519     result2=FindResult(results,finish);
520    
521     do
522     {
523 amb 43 if(result2->quickest.prev)
524 amb 34 {
525 amb 43 node_t node1=result2->quickest.prev;
526 amb 34
527     result1=FindResult(results,node1);
528    
529 amb 43 result1->quickest.next=result2->node;
530 amb 34
531     result2=result1;
532     }
533     else
534     result2=NULL;
535     }
536     while(result2);
537    
538     return(results);
539     }
540    
541    
542     /*++++++++++++++++++++++++++++++++++++++
543 amb 2 Print the optimum route between two nodes.
544    
545 amb 31 Results *Results The set of results to print.
546    
547     Nodes *nodes The list of nodes.
548    
549 amb 26 Segments *segments The set of segments to use.
550    
551     Ways *ways The list of ways.
552    
553 amb 55 Nodes *supernodes The list of super-nodes.
554    
555 amb 2 node_t start The start node.
556    
557     node_t finish The finish node.
558 amb 63
559     wayallow_t transport The mode of transport.
560 amb 2 ++++++++++++++++++++++++++++++++++++++*/
561    
562 amb 63 void PrintRoute(Results *results,Nodes *nodes,Segments *segments,Ways *ways,Nodes *supernodes,node_t start,node_t finish,wayallow_t transport)
563 amb 2 {
564 amb 55 FILE *textfile,*gpxfile;
565 amb 2 Result *result;
566    
567     /* Print the result for the shortest route */
568    
569 amb 55 textfile=fopen("shortest.txt","w");
570     gpxfile=fopen("shortest.gpx","w");
571 amb 2
572 amb 55 fprintf(gpxfile,"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
573     fprintf(gpxfile,"<gpx version=\"1.0\" creator=\"Router\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xmlns=\"http://www.topografix.com/GPX/1/0\" xsi:schemaLocation=\"http://www.topografix.com/GPX/1/0 http://www.topografix.com/GPX/1/0/gpx.xsd\">\n");
574     fprintf(gpxfile,"<trk>\n");
575     fprintf(gpxfile,"<trkseg>\n");
576    
577 amb 31 result=FindResult(results,start);
578 amb 2
579     do
580     {
581 amb 43 Node *node=FindNode(nodes,result->node);
582    
583 amb 55 fprintf(gpxfile,"<trkpt lat=\"%.6f\" lon=\"%.6f\"></trkpt>\n",node->latitude,node->longitude);
584    
585 amb 43 if(result->shortest.prev)
586 amb 2 {
587 amb 6 Segment *segment;
588     Way *way;
589 amb 2
590 amb 43 segment=FindFirstSegment(segments,result->shortest.prev);
591 amb 34 while(segment->node2!=result->node)
592 amb 26 segment=FindNextSegment(segments,segment);
593 amb 2
594 amb 26 way=FindWay(ways,segment->way);
595 amb 6
596 amb 55 fprintf(textfile,"%8.4f %9.4f %10d%c %5.3f %5.2f %7.2f %5.1f %3d %s\n",node->latitude,node->longitude,
597     node->id,supernodes?(FindNode(supernodes,node->id)?'*':' '):' ',
598 amb 63 distance_to_km(segment->distance),duration_to_minutes(Duration(segment,way,transport)),
599 amb 34 distance_to_km(result->shortest.distance),duration_to_minutes(result->shortest.duration),
600 amb 63 WaySpeed(way),WayName(ways,way));
601 amb 34 }
602     else
603 amb 55 fprintf(textfile,"%8.4f %9.4f %10d%c %5.3f %5.2f %7.2f %5.1f\n",node->latitude,node->longitude,
604     node->id,supernodes?(FindNode(supernodes,node->id)?'*':' '):' ',
605 amb 34 0.0,0.0,0.0,0.0);
606 amb 2
607 amb 43 if(result->shortest.next)
608     result=FindResult(results,result->shortest.next);
609 amb 2 else
610     result=NULL;
611     }
612     while(result);
613    
614 amb 55 fprintf(gpxfile,"</trkseg>\n");
615     fprintf(gpxfile,"</trk>\n");
616     fprintf(gpxfile,"</gpx>\n");
617 amb 2
618 amb 55 fclose(textfile);
619     fclose(gpxfile);
620    
621 amb 2 /* Print the result for the quickest route */
622    
623 amb 55 textfile=fopen("quickest.txt","w");
624     gpxfile=fopen("quickest.gpx","w");
625 amb 2
626 amb 55 fprintf(gpxfile,"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
627     fprintf(gpxfile,"<gpx version=\"1.0\" creator=\"Router\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xmlns=\"http://www.topografix.com/GPX/1/0\" xsi:schemaLocation=\"http://www.topografix.com/GPX/1/0 http://www.topografix.com/GPX/1/0/gpx.xsd\">\n");
628     fprintf(gpxfile,"<trk>\n");
629     fprintf(gpxfile,"<trkseg>\n");
630    
631 amb 31 result=FindResult(results,start);
632 amb 2
633     do
634     {
635 amb 43 Node *node=FindNode(nodes,result->node);
636    
637 amb 55 fprintf(gpxfile,"<trkpt lat=\"%.6f\" lon=\"%.6f\"></trkpt>\n",node->latitude,node->longitude);
638    
639 amb 43 if(result->quickest.prev)
640 amb 2 {
641 amb 6 Segment *segment;
642     Way *way;
643 amb 2
644 amb 43 segment=FindFirstSegment(segments,result->quickest.prev);
645 amb 34 while(segment->node2!=result->node)
646 amb 26 segment=FindNextSegment(segments,segment);
647 amb 2
648 amb 26 way=FindWay(ways,segment->way);
649 amb 6
650 amb 55 fprintf(textfile,"%8.4f %9.4f %10d%c %5.3f %5.2f %7.2f %5.1f %3d %s\n",node->latitude,node->longitude,
651     node->id,supernodes?(FindNode(supernodes,node->id)?'*':' '):' ',
652 amb 63 distance_to_km(segment->distance),duration_to_minutes(Duration(segment,way,transport)),
653 amb 34 distance_to_km(result->quickest.distance),duration_to_minutes(result->quickest.duration),
654 amb 63 WaySpeed(way),WayName(ways,way));
655 amb 34 }
656     else
657 amb 55 fprintf(textfile,"%8.4f %9.4f %10d%c %5.3f %5.2f %7.2f %5.1f\n",node->latitude,node->longitude,
658     node->id,supernodes?(FindNode(supernodes,node->id)?'*':' '):' ',
659 amb 34 0.0,0.0,0.0,0.0);
660 amb 2
661 amb 43 if(result->quickest.next)
662     result=FindResult(results,result->quickest.next);
663 amb 2 else
664     result=NULL;
665     }
666     while(result);
667    
668 amb 55 fprintf(gpxfile,"</trkseg>\n");
669     fprintf(gpxfile,"</trk>\n");
670     fprintf(gpxfile,"</gpx>\n");
671    
672     fclose(textfile);
673     fclose(gpxfile);
674 amb 31 }
675 amb 3
676    
677 amb 31 /*++++++++++++++++++++++++++++++++++++++
678     Find all routes from a specified node to any node in the specified list.
679 amb 3
680 amb 54 Results *FindRoutes Returns a set of results.
681 amb 31
682     Nodes *nodes The set of nodes to use.
683    
684     Segments *segments The set of segments to use.
685    
686 amb 54 Ways *ways The set of ways to use.
687    
688 amb 31 node_t start The start node.
689    
690     Nodes *finish The finishing nodes.
691 amb 54
692     wayallow_t transport The mode of transport.
693 amb 31 ++++++++++++++++++++++++++++++++++++++*/
694    
695 amb 54 Results *FindRoutes(Nodes *nodes,Segments *segments,Ways *ways,node_t start,Nodes *finish,wayallow_t transport)
696 amb 31 {
697     Results *results;
698 amb 43 node_t node1,node2;
699 amb 31 HalfResult shortest1,quickest1;
700     HalfResult shortest2,quickest2;
701     Result *result1,*result2;
702     Segment *segment;
703 amb 54 Way *way;
704 amb 31
705     /* Insert the first node into the queue */
706    
707     results=NewResultsList();
708    
709     result1=InsertResult(results,start);
710    
711     result1->node=start;
712 amb 43 result1->shortest.prev=0;
713     result1->shortest.next=0;
714 amb 31 result1->shortest.distance=0;
715     result1->shortest.duration=0;
716 amb 43 result1->quickest.prev=0;
717     result1->quickest.next=0;
718 amb 31 result1->quickest.distance=0;
719     result1->quickest.duration=0;
720    
721 amb 45 insert_in_queue(results,result1);
722 amb 31
723     /* Loop across all nodes in the queue */
724    
725 amb 45 while(OSMQueue.number>0)
726 amb 31 {
727 amb 45 result1=LookupResult(results,OSMQueue.queue[--OSMQueue.number]);
728 amb 43 node1=result1->node;
729 amb 64 shortest1=result1->shortest;
730     quickest1=result1->quickest;
731 amb 31
732 amb 43 segment=FindFirstSegment(segments,node1);
733 amb 31
734     while(segment)
735     {
736 amb 59 duration_t segment_duration;
737    
738 amb 64 if(segment->distance==INVALID_DISTANCE)
739     goto endloop;
740    
741 amb 31 node2=segment->node2;
742    
743 amb 64 if(shortest1.prev==node2 && quickest1.prev==node2)
744     goto endloop;
745    
746 amb 54 way=FindWay(ways,segment->way);
747    
748     if((way->allow&transport)!=transport)
749     goto endloop;
750    
751 amb 63 segment_duration=Duration(segment,way,transport);
752 amb 59
753 amb 31 shortest2.distance=shortest1.distance+segment->distance;
754 amb 59 shortest2.duration=shortest1.duration+segment_duration;
755 amb 31 quickest2.distance=quickest1.distance+segment->distance;
756 amb 59 quickest2.duration=quickest1.duration+segment_duration;
757 amb 31
758     result2=FindResult(results,node2);
759    
760     if(!result2) /* New end node */
761     {
762     result2=InsertResult(results,node2);
763     result2->node=node2;
764 amb 43 result2->shortest.prev=node1;
765     result2->shortest.next=0;
766 amb 31 result2->shortest.distance=shortest2.distance;
767     result2->shortest.duration=shortest2.duration;
768 amb 43 result2->quickest.prev=node1;
769     result2->quickest.next=0;
770 amb 31 result2->quickest.distance=quickest2.distance;
771     result2->quickest.duration=quickest2.duration;
772    
773     if(!FindNode(finish,node2))
774 amb 45 insert_in_queue(results,result2);
775 amb 31 }
776     else
777     {
778     if(shortest2.distance<result2->shortest.distance ||
779     (shortest2.distance==result2->shortest.distance &&
780     shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
781     {
782 amb 43 result2->shortest.prev=node1;
783 amb 31 result2->shortest.distance=shortest2.distance;
784     result2->shortest.duration=shortest2.duration;
785    
786     if(!FindNode(finish,node2))
787 amb 45 insert_in_queue(results,result2);
788 amb 31 }
789    
790     if(quickest2.duration<result2->quickest.duration ||
791     (quickest2.duration==result2->quickest.duration &&
792     quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
793     {
794 amb 43 result2->quickest.prev=node1;
795 amb 31 result2->quickest.distance=quickest2.distance;
796     result2->quickest.duration=quickest2.duration;
797    
798     if(!FindNode(finish,node2))
799 amb 45 insert_in_queue(results,result2);
800 amb 31 }
801     }
802    
803     endloop:
804    
805     segment=FindNextSegment(segments,segment);
806     }
807     }
808    
809     return(results);
810 amb 2 }
811    
812    
813     /*++++++++++++++++++++++++++++++++++++++
814 amb 47 Find all routes from any node in the specified list to a specific node.
815 amb 34
816 amb 47 Results *FindReverseRoute Returns a set of results.
817 amb 34
818     Nodes *nodes The set of nodes to use.
819    
820     Segments *segments The set of segments to use.
821    
822 amb 54 Ways *ways The set of ways to use.
823    
824 amb 34 Nodes *start The starting nodes.
825    
826     node_t finish The finishing node.
827 amb 54
828     wayallow_t transport The mode of transport.
829 amb 34 ++++++++++++++++++++++++++++++++++++++*/
830    
831 amb 54 Results *FindReverseRoutes(Nodes *nodes,Segments *segments,Ways *ways,Nodes *start,node_t finish,wayallow_t transport)
832 amb 34 {
833     Results *results;
834 amb 43 node_t node1,node2;
835 amb 34 HalfResult shortest1,quickest1;
836     HalfResult shortest2,quickest2;
837     Result *result1,*result2;
838     Segment *segment;
839 amb 54 Way *way;
840 amb 34
841     /* Insert the first node into the queue */
842    
843     results=NewResultsList();
844    
845     result1=InsertResult(results,finish);
846    
847     result1->node=finish;
848 amb 43 result1->shortest.prev=0;
849     result1->shortest.next=0;
850 amb 34 result1->shortest.distance=0;
851     result1->shortest.duration=0;
852 amb 43 result1->quickest.prev=0;
853     result1->quickest.next=0;
854 amb 34 result1->quickest.distance=0;
855     result1->quickest.duration=0;
856    
857 amb 45 insert_in_queue(results,result1);
858 amb 34
859     /* Loop across all nodes in the queue */
860    
861 amb 45 while(OSMQueue.number>0)
862 amb 34 {
863 amb 45 result1=LookupResult(results,OSMQueue.queue[--OSMQueue.number]);
864 amb 43 node1=result1->node;
865 amb 64 shortest1=result1->shortest;
866     quickest1=result1->quickest;
867 amb 34
868 amb 43 segment=FindFirstSegment(segments,node1);
869 amb 34
870     while(segment)
871     {
872 amb 59 duration_t reversesegment_duration;
873    
874 amb 34 /* Reverse the segment and check it exists */
875    
876     node_t reversenode;
877     Segment *reversesegment;
878    
879     reversenode=segment->node2;
880     reversesegment=FindFirstSegment(segments,reversenode);
881    
882 amb 43 while(reversesegment && reversesegment->node2!=node1)
883 amb 34 reversesegment=FindNextSegment(segments,reversesegment);
884    
885     if(!reversesegment)
886     goto endloop;
887    
888 amb 64 if(reversesegment->distance==INVALID_DISTANCE)
889     goto endloop;
890    
891 amb 34 node2=reversesegment->node1;
892    
893 amb 64 if(shortest1.prev==node2 && quickest1.prev==node2)
894     goto endloop;
895    
896 amb 54 way=FindWay(ways,reversesegment->way);
897    
898     if((way->allow&transport)!=transport)
899     goto endloop;
900    
901 amb 63 reversesegment_duration=Duration(reversesegment,way,transport);
902 amb 59
903 amb 34 shortest2.distance=shortest1.distance+reversesegment->distance;
904 amb 59 shortest2.duration=shortest1.duration+reversesegment_duration;
905 amb 34 quickest2.distance=quickest1.distance+reversesegment->distance;
906 amb 59 quickest2.duration=quickest1.duration+reversesegment_duration;
907 amb 34
908     result2=FindResult(results,node2);
909    
910     if(!result2) /* New end node */
911     {
912     result2=InsertResult(results,node2);
913     result2->node=node2;
914 amb 43 result2->shortest.prev=0;
915     result2->shortest.next=node1;
916 amb 34 result2->shortest.distance=shortest2.distance;
917     result2->shortest.duration=shortest2.duration;
918 amb 43 result2->quickest.prev=0;
919     result2->quickest.next=node1;
920 amb 34 result2->quickest.distance=quickest2.distance;
921     result2->quickest.duration=quickest2.duration;
922    
923     if(!FindNode(start,node2))
924 amb 45 insert_in_queue(results,result2);
925 amb 34 }
926     else
927     {
928     if(shortest2.distance<result2->shortest.distance ||
929     (shortest2.distance==result2->shortest.distance &&
930     shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
931     {
932 amb 43 result2->shortest.next=node1;
933 amb 34 result2->shortest.distance=shortest2.distance;
934     result2->shortest.duration=shortest2.duration;
935    
936     if(!FindNode(start,node2))
937 amb 45 insert_in_queue(results,result2);
938 amb 34 }
939    
940     if(quickest2.duration<result2->quickest.duration ||
941     (quickest2.duration==result2->quickest.duration &&
942     quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
943     {
944 amb 43 result2->quickest.next=node1;
945 amb 34 result2->quickest.distance=quickest2.distance;
946     result2->quickest.duration=quickest2.duration;
947    
948     if(!FindNode(start,node2))
949 amb 45 insert_in_queue(results,result2);
950 amb 34 }
951     }
952    
953     endloop:
954    
955     segment=FindNextSegment(segments,segment);
956     }
957     }
958    
959     return(results);
960     }
961    
962    
963     /*++++++++++++++++++++++++++++++++++++++
964 amb 31 Print the optimum route between two nodes.
965    
966 amb 58 Results *CombineRoutes Returns the results from joining the super-nodes.
967 amb 55
968 amb 58 Results *results The set of results from the super-nodes.
969 amb 31
970     Nodes *nodes The list of nodes.
971    
972     Segments *segments The set of segments to use.
973    
974     Ways *ways The list of ways.
975    
976     node_t start The start node.
977    
978     node_t finish The finish node.
979 amb 54
980     wayallow_t transport The mode of transport.
981 amb 31 ++++++++++++++++++++++++++++++++++++++*/
982    
983 amb 55 Results *CombineRoutes(Results *results,Nodes *nodes,Segments *segments,Ways *ways,node_t start,node_t finish,wayallow_t transport)
984 amb 31 {
985     Result *result1,*result2,*result3,*result4;
986     Results *combined;
987    
988     combined=NewResultsList();
989    
990     print_progress=0;
991    
992     /* Sort out the shortest */
993    
994     result1=FindResult(results,start);
995    
996 amb 58 result3=InsertResult(combined,start);
997 amb 31
998 amb 58 result3->node=result1->node;
999 amb 36
1000 amb 58 result3->shortest.distance=0;
1001     result3->shortest.duration=0;
1002     result3->shortest.next=0;
1003     result3->shortest.prev=0;
1004 amb 31
1005 amb 58 do
1006     {
1007 amb 43 if(result1->shortest.next)
1008 amb 31 {
1009 amb 54 Results *results2=FindRoute(nodes,segments,ways,result1->node,result1->shortest.next,transport);
1010 amb 31
1011     result2=FindResult(results2,result1->node);
1012    
1013 amb 43 result3->shortest.next=result2->shortest.next;
1014 amb 36
1015 amb 43 result2=FindResult(results2,result2->shortest.next);
1016 amb 36
1017 amb 31 do
1018     {
1019 amb 58 result4=InsertResult(combined,result2->node);
1020 amb 31
1021 amb 58 result4->node=result2->node;
1022 amb 36
1023 amb 58 result4->shortest=result2->shortest;
1024     result4->shortest.distance+=result3->shortest.distance;
1025     result4->shortest.duration+=result3->shortest.duration;
1026 amb 31
1027 amb 43 if(result2->shortest.next)
1028     result2=FindResult(results2,result2->shortest.next);
1029 amb 31 else
1030     result2=NULL;
1031     }
1032     while(result2);
1033    
1034     FreeResultsList(results2);
1035    
1036 amb 43 result1=FindResult(results,result1->shortest.next);
1037 amb 58
1038     result3=result4;
1039 amb 31 }
1040     else
1041     result1=NULL;
1042     }
1043     while(result1);
1044    
1045     /* Sort out the quickest */
1046    
1047     result1=FindResult(results,start);
1048    
1049 amb 58 result3=FindResult(combined,start);
1050    
1051     result3->quickest.distance=0;
1052     result3->quickest.duration=0;
1053     result3->quickest.next=0;
1054     result3->quickest.prev=0;
1055    
1056 amb 31 do
1057     {
1058 amb 43 if(result1->quickest.next)
1059 amb 31 {
1060 amb 54 Results *results2=FindRoute(nodes,segments,ways,result1->node,result1->quickest.next,transport);
1061 amb 31
1062     result2=FindResult(results2,result1->node);
1063    
1064 amb 43 result3->quickest.next=result2->quickest.next;
1065 amb 36
1066 amb 43 result2=FindResult(results2,result2->quickest.next);
1067 amb 36
1068 amb 31 do
1069     {
1070 amb 58 result4=FindResult(combined,result2->node);
1071    
1072     if(!result4)
1073 amb 31 {
1074 amb 58 result4=InsertResult(combined,result2->node);
1075 amb 31
1076 amb 58 result4->node=result2->node;
1077     }
1078 amb 31
1079 amb 58 result4->quickest=result2->quickest;
1080     result4->quickest.distance+=result3->quickest.distance;
1081     result4->quickest.duration+=result3->quickest.duration;
1082 amb 36
1083 amb 43 if(result2->quickest.next)
1084     result2=FindResult(results2,result2->quickest.next);
1085 amb 31 else
1086     result2=NULL;
1087     }
1088     while(result2);
1089    
1090     FreeResultsList(results2);
1091    
1092 amb 43 result1=FindResult(results,result1->quickest.next);
1093 amb 58
1094     result3=result4;
1095 amb 31 }
1096     else
1097     result1=NULL;
1098     }
1099     while(result1);
1100    
1101     /* Now print out the result normally */
1102    
1103     print_progress=1;
1104    
1105 amb 55 return(combined);
1106 amb 31 }
1107    
1108    
1109     /*++++++++++++++++++++++++++++++++++++++
1110 amb 54 Find all routes from a specified node to any node in the specified list that follows a certain type of way.
1111    
1112     Results *FindRoutesWay Returns a set of results.
1113    
1114     Nodes *nodes The set of nodes to use.
1115    
1116     Segments *segments The set of segments to use.
1117    
1118     Ways *ways The set of ways to use.
1119    
1120     node_t start The start node.
1121    
1122     Nodes *finish The finishing nodes.
1123    
1124     Way *match The way that the route must match.
1125 amb 58
1126     int iteration The iteration number in Super-Segment generation.
1127 amb 54 ++++++++++++++++++++++++++++++++++++++*/
1128    
1129 amb 58 Results *FindRoutesWay(Nodes *nodes,Segments *segments,Ways *ways,node_t start,Nodes *finish,Way *match,int iteration)
1130 amb 54 {
1131     Results *results;
1132     node_t node1,node2;
1133     HalfResult shortest1,quickest1;
1134     HalfResult shortest2,quickest2;
1135     Result *result1,*result2;
1136     Segment *segment;
1137     Way *way;
1138    
1139     /* Insert the first node into the queue */
1140    
1141     results=NewResultsList();
1142    
1143     result1=InsertResult(results,start);
1144    
1145     result1->node=start;
1146     result1->shortest.prev=0;
1147     result1->shortest.next=0;
1148     result1->shortest.distance=0;
1149     result1->shortest.duration=0;
1150     result1->quickest.prev=0;
1151     result1->quickest.next=0;
1152     result1->quickest.distance=0;
1153     result1->quickest.duration=0;
1154    
1155     insert_in_queue(results,result1);
1156    
1157     /* Loop across all nodes in the queue */
1158    
1159     while(OSMQueue.number>0)
1160     {
1161     result1=LookupResult(results,OSMQueue.queue[--OSMQueue.number]);
1162     node1=result1->node;
1163 amb 64 shortest1=result1->shortest;
1164     quickest1=result1->quickest;
1165 amb 54
1166     segment=FindFirstSegment(segments,node1);
1167    
1168     while(segment)
1169     {
1170 amb 59 duration_t segment_duration;
1171    
1172 amb 64 if(segment->distance==INVALID_DISTANCE)
1173     goto endloop;
1174    
1175 amb 54 node2=segment->node2;
1176    
1177 amb 64 if(shortest1.prev==node2 && quickest1.prev==node2)
1178     goto endloop;
1179    
1180 amb 54 way=FindWay(ways,segment->way);
1181    
1182 amb 56 if(Way_TYPE(way->type)!=Way_TYPE(match->type) ||
1183     way->allow!=match->allow ||
1184 amb 54 way->limit!=match->limit)
1185     goto endloop;
1186    
1187 amb 63 segment_duration=0;
1188 amb 54
1189 amb 59 shortest2.distance=shortest1.distance+segment->distance;
1190     shortest2.duration=shortest1.duration+segment_duration;
1191     quickest2.distance=quickest1.distance+segment->distance;
1192     quickest2.duration=quickest1.duration+segment_duration;
1193    
1194 amb 54 result2=FindResult(results,node2);
1195    
1196     if(!result2) /* New end node */
1197     {
1198     result2=InsertResult(results,node2);
1199     result2->node=node2;
1200     result2->shortest.prev=node1;
1201     result2->shortest.next=0;
1202     result2->shortest.distance=shortest2.distance;
1203     result2->shortest.duration=shortest2.duration;
1204     result2->quickest.prev=node1;
1205     result2->quickest.next=0;
1206     result2->quickest.distance=quickest2.distance;
1207     result2->quickest.duration=quickest2.duration;
1208    
1209     if(!FindNode(finish,node2))
1210     insert_in_queue(results,result2);
1211     }
1212     else
1213     {
1214     if(shortest2.distance<result2->shortest.distance ||
1215     (shortest2.distance==result2->shortest.distance &&
1216     shortest2.duration<result2->shortest.duration)) /* New end node is shorter */
1217     {
1218     result2->shortest.prev=node1;
1219     result2->shortest.distance=shortest2.distance;
1220     result2->shortest.duration=shortest2.duration;
1221    
1222     if(!FindNode(finish,node2))
1223     insert_in_queue(results,result2);
1224     }
1225    
1226     if(quickest2.duration<result2->quickest.duration ||
1227     (quickest2.duration==result2->quickest.duration &&
1228     quickest2.distance<result2->quickest.distance)) /* New end node is quicker */
1229     {
1230     result2->quickest.prev=node1;
1231     result2->quickest.distance=quickest2.distance;
1232     result2->quickest.duration=quickest2.duration;
1233    
1234     if(!FindNode(finish,node2))
1235     insert_in_queue(results,result2);
1236     }
1237     }
1238    
1239     endloop:
1240    
1241     segment=FindNextSegment(segments,segment);
1242     }
1243     }
1244    
1245     return(results);
1246     }
1247    
1248    
1249     /*++++++++++++++++++++++++++++++++++++++
1250 amb 2 Insert an item into the queue in the right order.
1251    
1252 amb 45 Results *results The set of results.
1253    
1254 amb 2 Result *result The result to insert into the queue.
1255     ++++++++++++++++++++++++++++++++++++++*/
1256    
1257 amb 45 static void insert_in_queue(Results *results,Result *result)
1258 amb 2 {
1259 amb 45 int start=0;
1260     int end=OSMQueue.number-1;
1261 amb 2 int mid;
1262     int insert=-1;
1263    
1264     /* Check that the whole thing is allocated. */
1265    
1266 amb 45 if(!OSMQueue.queue)
1267 amb 2 {
1268 amb 45 OSMQueue.alloced=INCREMENT;
1269     OSMQueue.number=0;
1270     OSMQueue.queue=(uint32_t*)malloc(OSMQueue.alloced*sizeof(uint32_t));
1271 amb 2 }
1272    
1273     /* Check that the arrays have enough space. */
1274    
1275 amb 45 if(OSMQueue.number==OSMQueue.alloced)
1276 amb 2 {
1277 amb 45 OSMQueue.alloced+=INCREMENT;
1278     OSMQueue.queue=(uint32_t*)realloc((void*)OSMQueue.queue,OSMQueue.alloced*sizeof(uint32_t));
1279 amb 2 }
1280    
1281     /* Binary search - search key may not match, new insertion point required
1282     *
1283     * # <- start | Check mid and move start or end if it doesn't match
1284     * # |
1285     * # | Since there may not be an exact match we must set end=mid
1286     * # <- mid | or start=mid because we know that mid doesn't match.
1287     * # |
1288     * # | Eventually end=start+1 and the insertion point is before
1289     * # <- end | end (since it cannot be before the initial start or end).
1290     */
1291    
1292 amb 45 if(OSMQueue.number==0) /* There is nothing in the queue */
1293     insert=0;
1294     else if(result->shortest.distance>results->results[OSMQueue.queue[start]].shortest.distance) /* Check key is not before start */
1295 amb 2 insert=start;
1296 amb 45 else if(result->shortest.distance<results->results[OSMQueue.queue[end]].shortest.distance) /* Check key is not after end */
1297 amb 2 insert=end+1;
1298     else
1299     {
1300     do
1301     {
1302 amb 45 mid=(start+end)/2; /* Choose mid point */
1303 amb 2
1304 amb 45 if(results->results[OSMQueue.queue[mid]].shortest.distance>result->shortest.distance) /* Mid point is too low */
1305 amb 2 start=mid;
1306 amb 45 else if(results->results[OSMQueue.queue[mid]].shortest.distance<result->shortest.distance) /* Mid point is too high */
1307 amb 2 end=mid;
1308 amb 45 else /* Mid point is correct */
1309 amb 2 {
1310 amb 45 if(&results->results[OSMQueue.queue[mid]]==result)
1311 amb 2 return;
1312    
1313     insert=mid;
1314     break;
1315     }
1316     }
1317     while((end-start)>1);
1318    
1319     if(insert==-1)
1320     insert=end;
1321     }
1322    
1323     /* Shuffle the array up */
1324    
1325 amb 45 if(insert!=OSMQueue.number)
1326     memmove(&OSMQueue.queue[insert+1],&OSMQueue.queue[insert],(OSMQueue.number-insert)*sizeof(uint32_t));
1327 amb 2
1328     /* Insert the new entry */
1329    
1330 amb 45 OSMQueue.queue[insert]=result-results->results;
1331 amb 2
1332 amb 45 OSMQueue.number++;
1333 amb 2 }

Properties

Name Value
cvs:description Route optimiser.
Index: This Site Routino Software Download Source Code Documentation XML Files Links
Index: View SVN Development Recent changes Development (destination-access branch) Version 3.4.2 (destination-access branch) Version 3.4.2 Version 3.4.1 (destination-access branch) Version 3.4.1 Version 3.4 (destination-access branch) Version 3.4 Version 3.3.3 (destination-access branch) Version 3.3.3 Version 3.3.2 (destination-access branch) Version 3.3.2 Version 3.3.1 (destination-access branch) Version 3.3.1 Version 3.3 (destination-access branch) Version 3.3 Version 3.2 Version 3.1.1 Version 3.1 Version 3.0 Version 2.7.3 Version 2.7.2 Version 2.7.1 Version 2.7 Version 2.6 Version 2.5.1 Version 2.5 Version 2.4.1 Version 2.4 Version 2.3.2 Version 2.3.1 Version 2.3 Version 2.2 Version 2.1.2 Version 2.1.1 Version 2.1 Version 2.0.3 Version 2.0.2 Version 2.0.1 Version 2.0 Version 1.5.1 Version 1.5 Version 1.4.1 Version 1.4 Version 1.3 Version 1.2 Version 1.1 Version 1.0
Powered by ViewVC 1.3.0-dev ViewVC Help
© Andrew M. Bishop = < amb @ ... >
Root