/[zanavi_public1]/navit/navit/route.c
ZANavi

Contents of /navit/navit/route.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 27 - (hide annotations) (download)
Mon Apr 9 21:27:36 2012 UTC (10 years, 9 months ago) by zoff99
File MIME type: text/plain
File size: 104560 byte(s)
lots of new stuff, tranlsations, bug fixes ...
1 zoff99 2 /**
2     * Navit, a modular navigation system.
3     * Copyright (C) 2005-2008 Navit Team
4     *
5     * This program is free software; you can redistribute it and/or
6     * modify it under the terms of the GNU General Public License
7     * version 2 as published by the Free Software Foundation.
8     *
9     * This program is distributed in the hope that it will be useful,
10     * but WITHOUT ANY WARRANTY; without even the implied warranty of
11     * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12     * GNU General Public License for more details.
13     *
14     * You should have received a copy of the GNU General Public License
15     * along with this program; if not, write to the
16     * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17     * Boston, MA 02110-1301, USA.
18     */
19    
20     /** @file
21     * @brief Contains code related to finding a route from a position to a destination
22     *
23     * Routing uses segments, points and items. Items are items from the map: Streets, highways, etc.
24     * Segments represent such items, or parts of it. Generally, a segment is a driveable path. An item
25     * can be represented by more than one segment - in that case it is "segmented". Each segment has an
26     * "offset" associated, that indicates at which position in a segmented item this segment is - a
27     * segment representing a not-segmented item always has the offset 1.
28     * A point is located at the end of segments, often connecting several segments.
29     *
30     * The code in this file will make navit find a route between a position and a destination.
31     * It accomplishes this by first building a "route graph". This graph contains segments and
32     * points.
33     *
34     * After building this graph in route_graph_build(), the function route_graph_flood() assigns every
35     * point and segment a "value" which represents the "costs" of traveling from this point to the
36     * destination. This is done by Dijkstra's algorithm.
37     *
38     * When the graph is built a "route path" is created, which is a path in this graph from a given
39     * position to the destination determined at time of building the graph.
40     */
41    
42     #include <stdio.h>
43     #include <stdlib.h>
44     #include <string.h>
45     #if 0
46     #include <math.h>
47     #include <assert.h>
48     #include <unistd.h>
49     #include <sys/time.h>
50     #endif
51     #include "glib_slice.h"
52     #include "config.h"
53     #include "point.h"
54     #include "graphics.h"
55     #include "profile.h"
56     #include "coord.h"
57     #include "projection.h"
58     #include "item.h"
59     #include "map.h"
60     #include "mapset.h"
61     #include "route.h"
62     #include "track.h"
63     #include "transform.h"
64     #include "plugin.h"
65     #include "fib.h"
66     #include "event.h"
67     #include "callback.h"
68     #include "vehicle.h"
69     #include "vehicleprofile.h"
70     #include "roadprofile.h"
71     #include "debug.h"
72    
73     #include "navit.h"
74    
75 zoff99 27 struct map_priv
76     {
77 zoff99 2 struct route *route;
78     };
79    
80 zoff99 27 int debug_route = 0;
81 zoff99 2
82     /**
83     * @brief A point in the route graph
84     *
85     * This represents a point in the route graph. A point usually connects two or more segments,
86     * but there are also points which don't do that (e.g. at the end of a dead-end).
87     */
88 zoff99 27 struct route_graph_point
89     {
90 zoff99 2 struct route_graph_point *hash_next; /**< Pointer to a chained hashlist of all route_graph_points with this hash */
91 zoff99 27 struct route_graph_segment *start; /**< Pointer to a list of segments of which this point is the start. The links
92     * of this linked-list are in route_graph_segment->start_next.*/
93     struct route_graph_segment *end; /**< Pointer to a list of segments of which this pointer is the end. The links
94     * of this linked-list are in route_graph_segment->end_next. */
95     struct route_graph_segment *seg; /**< Pointer to the segment one should use to reach the destination at
96     * least costs */
97     struct fibheap_el *el; /**< When this point is put on a Fibonacci heap, this is a pointer
98     * to this point's heap-element */
99     int value; /**< The cost at which one can reach the destination from this point on */
100     struct coord c; /**< Coordinates of this point */
101     int flags; /**< Flags for this point (eg traffic distortion) */
102 zoff99 2 };
103    
104     #define RP_TRAFFIC_DISTORTION 1
105     #define RP_TURN_RESTRICTION 2
106     #define RP_TURN_RESTRICTION_RESOLVED 4
107    
108     /**
109     * @brief A segment in the route graph or path
110     *
111     * This is a segment in the route graph or path. A segment represents a driveable way.
112     */
113    
114 zoff99 27 struct route_segment_data
115     {
116     struct item item; /**< The item (e.g. street) that this segment represents. */
117 zoff99 2 int flags;
118 zoff99 27 int len; /**< Length of this segment */
119     /*NOTE: After a segment, various fields may follow, depending on what flags are set. Order of fields:
120     1.) maxspeed Maximum allowed speed on this segment. Present if AF_SPEED_LIMIT is set.
121     2.) offset If the item is segmented (i.e. represented by more than one segment), this
122     indicates the position of this segment in the item. Present if AF_SEGMENTED is set.
123     */
124 zoff99 2 };
125    
126 zoff99 27 struct size_weight_limit
127     {
128 zoff99 2 int width;
129     int length;
130     int height;
131     int weight;
132     int axle_weight;
133     };
134    
135     #define RSD_OFFSET(x) *((int *)route_segment_data_field_pos((x), attr_offset))
136     #define RSD_MAXSPEED(x) *((int *)route_segment_data_field_pos((x), attr_maxspeed))
137     #define RSD_SIZE_WEIGHT(x) *((struct size_weight_limit *)route_segment_data_field_pos((x), attr_vehicle_width))
138     #define RSD_DANGEROUS_GOODS(x) *((int *)route_segment_data_field_pos((x), attr_vehicle_dangerous_goods))
139    
140 zoff99 27 struct route_graph_segment_data
141     {
142 zoff99 2 struct item *item;
143     int offset;
144     int flags;
145     int len;
146     int maxspeed;
147     struct size_weight_limit size_weight;
148     int dangerous_goods;
149     };
150    
151     /**
152     * @brief A segment in the route graph
153     *
154     * This is a segment in the route graph. A segment represents a driveable way.
155     */
156 zoff99 27 struct route_graph_segment
157     {
158     struct route_graph_segment *next; /**< Linked-list pointer to a list of all route_graph_segments */
159     struct route_graph_segment *start_next; /**< Pointer to the next element in the list of segments that start at the
160     * same point. Start of this list is in route_graph_point->start. */
161     struct route_graph_segment *end_next; /**< Pointer to the next element in the list of segments that end at the
162     * same point. Start of this list is in route_graph_point->end. */
163     struct route_graph_point *start; /**< Pointer to the point this segment starts at. */
164     struct route_graph_point *end; /**< Pointer to the point this segment ends at. */
165     struct route_segment_data data; /**< The segment data */
166 zoff99 2 };
167    
168     /**
169     * @brief A traffic distortion
170     *
171     * This is distortion in the traffic where you can't drive as fast as usual or have to wait for some time
172     */
173 zoff99 27 struct route_traffic_distortion
174     {
175     int maxspeed; /**< Maximum speed possible in km/h */
176     int delay; /**< Delay in tenths of seconds */
177 zoff99 2 };
178    
179     /**
180     * @brief A segment in the route path
181     *
182     * This is a segment in the route path.
183     */
184 zoff99 27 struct route_path_segment
185     {
186     struct route_path_segment *next; /**< Pointer to the next segment in the path */
187     struct route_segment_data *data; /**< The segment data */
188     int direction; /**< Order in which the coordinates are ordered. >0 means "First
189     * coordinate of the segment is the first coordinate of the item", <=0
190     * means reverse. */
191     unsigned ncoords; /**< How many coordinates does this segment have? */
192     struct coord c[0]; /**< Pointer to the ncoords coordinates of this segment */
193     /* WARNING: There will be coordinates following here, so do not create new fields after c! */
194 zoff99 2 };
195    
196    
197     /**
198     * @brief A complete route path
199     *
200     * This structure describes a whole routing path
201     */
202 zoff99 27 struct route_path
203     {
204     int in_use; /**< The path is in use and can not be updated */
205     int update_required; /**< The path needs to be updated after it is no longer in use */
206     int updated; /**< The path has only been updated */
207     int path_time; /**< Time to pass the path */
208     int path_len; /**< Length of the path */
209     struct route_path_segment *path; /**< The first segment in the path, i.e. the segment one should
210     * drive in next */
211     struct route_path_segment *path_last; /**< The last segment in the path */
212 zoff99 2 /* XXX: path_hash is not necessery now */
213 zoff99 27 struct item_hash *path_hash; /**< A hashtable of all the items represented by this route's segements */
214     struct route_path *next; /**< Next route path in case of intermediate destinations */
215 zoff99 2 };
216    
217     /**
218     * @brief A complete route
219     *
220     * This struct holds all information about a route.
221     */
222    
223     /**
224     * @brief A complete route graph
225     *
226     * This structure describes a whole routing graph
227     */
228 zoff99 27 struct route_graph
229     {
230     int busy; /**< The graph is being built */
231     struct map_selection *sel; /**< The rectangle selection for the graph */
232     struct mapset_handle *h; /**< Handle to the mapset */
233     struct map *m; /**< Pointer to the currently active map */
234     struct map_rect *mr; /**< Pointer to the currently active map rectangle */
235     struct vehicleprofile *vehicleprofile; /**< The vehicle profile */
236     struct callback *idle_cb; /**< Idle callback to process the graph */
237     struct callback *done_cb; /**< Callback when graph is done */
238     struct event_idle *idle_ev; /**< The pointer to the idle event */
239     struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */
240 zoff99 2 #define HASH_SIZE 8192
241 zoff99 27 struct route_graph_point *hash[HASH_SIZE]; /**< A hashtable containing all route_graph_points in this graph */
242 zoff99 2 };
243    
244     #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
245    
246     /**
247     * @brief Iterator to iterate through all route graph segments in a route graph point
248     *
249     * This structure can be used to iterate through all route graph segments connected to a
250     * route graph point. Use this with the rp_iterator_* functions.
251     */
252 zoff99 27 struct route_graph_point_iterator
253     {
254     struct route_graph_point *p; /**< The route graph point whose segments should be iterated */
255     int end; /**< Indicates if we have finished iterating through the "start" segments */
256     struct route_graph_segment *next; /**< The next segment to be returned */
257 zoff99 2 };
258    
259 zoff99 27 struct attr_iter
260     {
261     union
262     {
263 zoff99 2 GList *list;
264     } u;
265     };
266    
267 zoff99 27 static struct route_info * route_find_nearest_street(
268     struct vehicleprofile *vehicleprofile, struct mapset *ms,
269     struct pcoord *c);
270     static struct route_graph_point *route_graph_get_point(
271     struct route_graph *this, struct coord *c);
272     static void route_graph_update(struct route *this, struct callback *cb,
273     int async);
274 zoff99 2 static void route_graph_build_done(struct route_graph *rg, int cancel);
275 zoff99 27 static struct route_path *route_path_new(struct route_graph *this,
276     struct route_path *oldpath, struct route_info *pos,
277     struct route_info *dst, struct vehicleprofile *profile);
278     static void route_process_street_graph(struct route_graph *this,
279     struct item *item, struct vehicleprofile *profile);
280     //static void route_graph_destroy(struct route_graph *this);
281 zoff99 2 static void route_path_update(struct route *this, int cancel, int async);
282 zoff99 27 static int route_time_seg(struct vehicleprofile *profile,
283     struct route_segment_data *over, struct route_traffic_distortion *dist);
284     static void route_graph_flood(struct route_graph *this, struct route_info *dst,
285     struct vehicleprofile *profile, struct callback *cb);
286 zoff99 2 static void route_graph_reset(struct route_graph *this);
287    
288     /**
289     * @brief Returns the projection used for this route
290     *
291     * @param route The route to return the projection for
292     * @return The projection used for this route
293     */
294     static enum projection route_projection(struct route *route)
295     {
296     struct street_data *street;
297 zoff99 27 struct route_info *dst = route_get_dst(route);
298 zoff99 2 if (!route->pos && !dst)
299     return projection_none;
300     street = route->pos ? route->pos->street : dst->street;
301     if (!street || !street->item.map)
302     return projection_none;
303     return map_projection(street->item.map);
304     }
305    
306     /**
307     * @brief Creates a new graph point iterator
308     *
309     * This function creates a new route graph point iterator, that can be used to
310     * iterate through all segments connected to the point.
311     *
312     * @param p The route graph point to create the iterator from
313     * @return A new iterator.
314     */
315 zoff99 27 static struct route_graph_point_iterator rp_iterator_new(
316     struct route_graph_point *p)
317 zoff99 2 {
318     struct route_graph_point_iterator it;
319    
320     it.p = p;
321 zoff99 27 if (p->start)
322     {
323 zoff99 2 it.next = p->start;
324     it.end = 0;
325 zoff99 27 }
326     else
327     {
328 zoff99 2 it.next = p->end;
329     it.end = 1;
330     }
331    
332     return it;
333     }
334    
335     /**
336     * @brief Gets the next segment connected to a route graph point from an iterator
337     *
338     * @param it The route graph point iterator to get the segment from
339     * @return The next segment or NULL if there are no more segments
340     */
341 zoff99 27 static struct route_graph_segment *rp_iterator_next(
342     struct route_graph_point_iterator *it)
343 zoff99 2 {
344     struct route_graph_segment *ret;
345    
346     ret = it->next;
347 zoff99 27 if (!ret)
348     {
349 zoff99 2 return NULL;
350     }
351    
352 zoff99 27 if (!it->end)
353     {
354     if (ret->start_next)
355     {
356 zoff99 2 it->next = ret->start_next;
357 zoff99 27 }
358     else
359     {
360 zoff99 2 it->next = it->p->end;
361     it->end = 1;
362     }
363 zoff99 27 }
364     else
365     {
366 zoff99 2 it->next = ret->end_next;
367     }
368    
369     return ret;
370     }
371    
372     /**
373     * @brief Checks if the last segment returned from a route_graph_point_iterator comes from the end
374     *
375     * @param it The route graph point iterator to be checked
376     * @return 1 if the last segment returned comes from the end of the route graph point, 0 otherwise
377     */
378 zoff99 27 static int rp_iterator_end(struct route_graph_point_iterator *it)
379     {
380     if (it->end && (it->next != it->p->end))
381     {
382 zoff99 2 return 1;
383 zoff99 27 }
384     else
385     {
386 zoff99 2 return 0;
387     }
388     }
389    
390     /**
391     * @brief Destroys a route_path
392     *
393     * @param this The route_path to be destroyed
394     */
395 zoff99 27 void route_path_destroy(struct route_path *this, int recurse)
396 zoff99 2 {
397 zoff99 27 struct route_path_segment *c, *n;
398 zoff99 2 struct route_path *next;
399 zoff99 27 while (this)
400     {
401     next = this->next;
402     if (this->path_hash)
403     {
404 zoff99 2 item_hash_destroy(this->path_hash);
405 zoff99 27 this->path_hash = NULL;
406 zoff99 2 }
407 zoff99 27 c = this->path;
408     while (c)
409     {
410     n = c->next;
411 zoff99 2 g_free(c);
412 zoff99 27 c = n;
413 zoff99 2 }
414     this->in_use--;
415     if (!this->in_use)
416     g_free(this);
417     if (!recurse)
418     break;
419 zoff99 27 this = next;
420 zoff99 2 }
421     }
422    
423     /**
424     * @brief Creates a completely new route structure
425     *
426     * @param attrs Not used
427     * @return The newly created route
428     */
429     struct route *
430     route_new(struct attr *parent, struct attr **attrs)
431     {
432     struct route *this=g_new0(struct route, 1);
433     struct attr dest_attr;
434    
435 zoff99 27 if (attr_generic_get_attr(attrs, NULL, attr_destination_distance,
436     &dest_attr, NULL))
437     {
438 zoff99 2 this->destination_distance = dest_attr.u.num;
439 zoff99 27 }
440     else
441     {
442 zoff99 2 this->destination_distance = 50; // Default value
443     }
444 zoff99 27 this->cbl2 = callback_list_new();
445 zoff99 2
446     return this;
447     }
448    
449     /**
450     * @brief Checks if a segment is part of a roundabout
451     *
452     * This function checks if a segment is part of a roundabout.
453     *
454     * @param seg The segment to be checked
455     * @param level How deep to scan the route graph
456     * @param direction Set this to 1 if we're entering the segment through its end, to 0 otherwise
457     * @param origin Used internally, set to NULL
458     * @return 1 If a roundabout was detected, 0 otherwise
459     */
460 zoff99 27 static int route_check_roundabout(struct route_graph_segment *seg, int level,
461     int direction, struct route_graph_segment *origin)
462 zoff99 2 {
463 zoff99 27 struct route_graph_point_iterator it, it2;
464 zoff99 2 struct route_graph_segment *cur;
465 zoff99 27 int count = 0;
466 zoff99 2
467 zoff99 27 if (!level)
468     {
469 zoff99 2 return 0;
470     }
471 zoff99 27 if (!direction && !(seg->data.flags & AF_ONEWAY))
472     {
473 zoff99 2 return 0;
474     }
475 zoff99 27 if (direction && !(seg->data.flags & AF_ONEWAYREV))
476     {
477 zoff99 2 return 0;
478     }
479     if (seg->data.flags & AF_ROUNDABOUT_VALID)
480     return 0;
481 zoff99 27
482     if (!origin)
483     {
484 zoff99 2 origin = seg;
485     }
486    
487 zoff99 27 if (!direction)
488     {
489 zoff99 2 it = rp_iterator_new(seg->end);
490 zoff99 27 }
491     else
492     {
493 zoff99 2 it = rp_iterator_new(seg->start);
494     }
495 zoff99 27 it2 = it;
496    
497 zoff99 2 while ((cur = rp_iterator_next(&it2)))
498     count++;
499    
500     if (count > 3)
501     return 0;
502     cur = rp_iterator_next(&it);
503 zoff99 27 while (cur)
504     {
505     if (cur == seg)
506     {
507 zoff99 2 cur = rp_iterator_next(&it);
508     continue;
509     }
510    
511 zoff99 27 if (cur->data.item.type != origin->data.item.type)
512     {
513 zoff99 2 // This street is of another type, can't be part of the roundabout
514     cur = rp_iterator_next(&it);
515     continue;
516     }
517    
518 zoff99 27 if (cur == origin)
519     {
520 zoff99 2 seg->data.flags |= AF_ROUNDABOUT;
521     return 1;
522     }
523    
524 zoff99 27 if (route_check_roundabout(cur, (level - 1), rp_iterator_end(&it),
525     origin))
526     {
527 zoff99 2 seg->data.flags |= AF_ROUNDABOUT;
528     return 1;
529     }
530    
531     cur = rp_iterator_next(&it);
532     }
533    
534     return 0;
535     }
536    
537     /**
538     * @brief Sets the mapset of the route passwd
539     *
540     * @param this The route to set the mapset for
541     * @param ms The mapset to set for this route
542     */
543 zoff99 27 void route_set_mapset(struct route *this, struct mapset *ms)
544 zoff99 2 {
545 zoff99 27 this->ms = ms;
546 zoff99 2 }
547    
548     /**
549     * @brief Sets the vehicle profile of a route
550     *
551     * @param this The route to set the profile for
552     * @param prof The vehicle profile
553     */
554    
555 zoff99 27 void route_set_profile(struct route *this, struct vehicleprofile *prof)
556 zoff99 2 {
557 zoff99 27 if (this->vehicleprofile != prof)
558     {
559     this->vehicleprofile = prof;
560 zoff99 2 route_path_update(this, 1, 1);
561     }
562     }
563    
564     /**
565     * @brief Returns the mapset of the route passed
566     *
567     * @param this The route to get the mapset of
568     * @return The mapset of the route passed
569     */
570     struct mapset *
571     route_get_mapset(struct route *this)
572     {
573     return this->ms;
574     }
575    
576     /**
577     * @brief Returns the current position within the route passed
578     *
579     * @param this The route to get the position for
580     * @return The position within the route passed
581     */
582     struct route_info *
583     route_get_pos(struct route *this)
584     {
585     return this->pos;
586     }
587    
588     /**
589     * @brief Returns the destination of the route passed
590     *
591     * @param this The route to get the destination for
592     * @return The destination of the route passed
593     */
594     struct route_info *
595     route_get_dst(struct route *this)
596     {
597 zoff99 27 struct route_info *dst = NULL;
598 zoff99 2
599     if (this->destinations)
600 zoff99 27 dst = g_list_last(this->destinations)->data;
601 zoff99 2 return dst;
602     }
603    
604     /**
605     * @brief Checks if the path is calculated for the route passed
606     *
607     * @param this The route to check
608     * @return True if the path is calculated, false if not
609     */
610 zoff99 27 int route_get_path_set(struct route *this)
611 zoff99 2 {
612     return this->path2 != NULL;
613     }
614    
615     /**
616     * @brief Checks if the route passed contains a certain item within the route path
617     *
618     * This function checks if a certain items exists in the path that navit will guide
619     * the user to his destination. It does *not* check if this item exists in the route
620     * graph!
621     *
622     * @param this The route to check for this item
623     * @param item The item to search for
624     * @return True if the item was found, false if the item was not found or the route was not calculated
625     */
626 zoff99 27 int route_contains(struct route *this, struct item *item)
627 zoff99 2 {
628 zoff99 27 if (!this->path2 || !this->path2->path_hash)
629 zoff99 2 return 0;
630     if (item_hash_lookup(this->path2->path_hash, item))
631     return 1;
632 zoff99 27 if (!this->pos || !this->pos->street)
633 zoff99 2 return 0;
634     return item_is_equal(this->pos->street->item, *item);
635    
636     }
637    
638     static struct route_info *
639     route_next_destination(struct route *this)
640     {
641     if (!this->destinations)
642     return NULL;
643     return this->destinations->data;
644     }
645    
646     /**
647     * @brief Checks if a route has reached its destination
648     *
649     * @param this The route to be checked
650     * @return True if the destination is "reached", false otherwise.
651     */
652 zoff99 27 int route_destination_reached(struct route *this)
653 zoff99 2 {
654     struct street_data *sd = NULL;
655     enum projection pro;
656 zoff99 27 struct route_info *dst = route_next_destination(this);
657 zoff99 2
658     if (!this->pos)
659     return 0;
660     if (!dst)
661     return 0;
662 zoff99 27
663 zoff99 2 sd = this->pos->street;
664    
665 zoff99 27 if (!this->path2)
666     {
667 zoff99 2 return 0;
668     }
669    
670 zoff99 27 if (!item_is_equal(this->pos->street->item, dst->street->item))
671     {
672 zoff99 2 return 0;
673     }
674    
675 zoff99 27 if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= dst->lenneg))
676     { // We would have to drive against the one-way road
677 zoff99 2 return 0;
678     }
679 zoff99 27 if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= dst->lenpos))
680     {
681 zoff99 2 return 0;
682     }
683 zoff99 27 pro = route_projection(this);
684 zoff99 2 if (pro == projection_none)
685     return 0;
686 zoff99 27
687     if (transform_distance(pro, &this->pos->c, &dst->lp)
688     > this->destination_distance)
689     {
690 zoff99 2 return 0;
691     }
692    
693 zoff99 27 if (g_list_next(this->destinations))
694 zoff99 2 return 1;
695     else
696     return 2;
697     }
698    
699     static struct route_info *
700     route_previous_destination(struct route *this)
701     {
702 zoff99 27 GList *l = g_list_find(this->destinations, this->current_dst);
703 zoff99 2 if (!l)
704     return this->pos;
705 zoff99 27 l = g_list_previous(l);
706 zoff99 2 if (!l)
707     return this->pos;
708     return l->data;
709     }
710    
711 zoff99 27 static void route_path_update_done(struct route *this, int new_graph)
712 zoff99 2 {
713 zoff99 27 struct route_path *oldpath = this->path2;
714 zoff99 2 struct attr route_status;
715     struct route_info *prev_dst;
716 zoff99 27 route_status.type = attr_route_status;
717     if (this->path2 && (this->path2->in_use > 1))
718     {
719     this->path2->update_required = 1 + new_graph;
720 zoff99 2 return;
721     }
722 zoff99 27 route_status.u.num = route_status_building_path;
723 zoff99 2 route_set_attr(this, &route_status);
724 zoff99 27 prev_dst = route_previous_destination(this);
725     if (this->link_path)
726     {
727     this->path2 = route_path_new(this->graph, NULL, prev_dst,
728     this->current_dst, this->vehicleprofile);
729 zoff99 2 if (this->path2)
730 zoff99 27 this->path2->next = oldpath;
731     }
732     else
733     {
734     this->path2 = route_path_new(this->graph, oldpath, prev_dst,
735     this->current_dst, this->vehicleprofile);
736     if (oldpath && this->path2)
737     {
738     this->path2->next = oldpath->next;
739     route_path_destroy(oldpath, 0);
740 zoff99 2 }
741     }
742 zoff99 27 if (this->path2)
743     {
744     struct route_path_segment *seg = this->path2->path;
745     int path_time = 0, path_len = 0;
746     while (seg)
747     {
748 zoff99 2 /* FIXME */
749 zoff99 27 int seg_time =
750     route_time_seg(this->vehicleprofile, seg->data, NULL);
751     if (seg_time == INT_MAX)
752     {
753     dbg(1, "error\n");
754     }
755     else
756     path_time += seg_time;
757     path_len += seg->data->len;
758     seg = seg->next;
759 zoff99 2 }
760 zoff99 27 this->path2->path_time = path_time;
761     this->path2->path_len = path_len;
762     if (prev_dst != this->pos)
763     {
764     this->link_path = 1;
765     this->current_dst = prev_dst;
766 zoff99 2 route_graph_reset(this->graph);
767 zoff99 27 route_graph_flood(this->graph, this->current_dst,
768     this->vehicleprofile, this->route_graph_flood_done_cb);
769 zoff99 2 return;
770     }
771     if (!new_graph && this->path2->updated)
772     {
773 zoff99 27 route_status.u.num = route_status_path_done_incremental;
774 zoff99 2 }
775     else
776     {
777 zoff99 27 route_status.u.num = route_status_path_done_new;
778 zoff99 2 }
779 zoff99 27 }
780 zoff99 2 else
781 zoff99 27 {
782     route_status.u.num = route_status_not_found;
783     dbg(0, "try harder\n");
784     // Try to rebuild the graph with smaller roads
785     if (this->try_harder == 0)
786     {
787     this->try_harder = 1;
788     route_graph_destroy(this->graph);
789     this->graph = NULL;
790     route_path_update(this, 1, 1);
791     }
792 zoff99 2 }
793 zoff99 27 this->link_path = 0;
794 zoff99 2 route_set_attr(this, &route_status);
795     }
796    
797     /**
798     * @brief Updates the route graph and the route path if something changed with the route
799     *
800     * This will update the route graph and the route path of the route if some of the
801     * route's settings (destination, position) have changed.
802     *
803     * @attention For this to work the route graph has to be destroyed if the route's
804     * @attention destination is changed somewhere!
805     *
806     * @param this The route to update
807     */
808 zoff99 27 static void route_path_update(struct route *this, int cancel, int async)
809 zoff99 2 {
810 zoff99 27 //dbg(1, "enter %d\n", cancel);
811     if (!this->pos || !this->destinations)
812     {
813     //dbg(1, "destroy\n");
814     route_path_destroy(this->path2, 1);
815 zoff99 2 this->path2 = NULL;
816     return;
817     }
818 zoff99 27 if (cancel)
819     {
820 zoff99 2 route_graph_destroy(this->graph);
821 zoff99 27 this->graph = NULL;
822 zoff99 2 }
823     /* the graph is destroyed when setting the destination */
824 zoff99 27 if (this->graph)
825     {
826     if (this->graph->busy)
827     {
828     //dbg(1, "busy building graph\n");
829 zoff99 2 return;
830     }
831     // we can try to update
832 zoff99 27 //dbg(1, "try update\n");
833 zoff99 2 route_path_update_done(this, 0);
834 zoff99 27 }
835     else
836     {
837     route_path_destroy(this->path2, 1);
838 zoff99 2 this->path2 = NULL;
839     }
840 zoff99 27 if (!this->graph || !this->path2)
841     {
842     //dbg(1, "rebuild graph\n");
843     if (!this->route_graph_flood_done_cb)
844     {
845     this->route_graph_flood_done_cb = callback_new_2(
846     callback_cast(route_path_update_done), this, (long) 1);
847     }
848     //dbg(1, "route_graph_update\n");
849 zoff99 2 route_graph_update(this, this->route_graph_flood_done_cb, async);
850     }
851     }
852    
853     /**
854     * @brief This will calculate all the distances stored in a route_info
855     *
856     * @param ri The route_info to calculate the distances for
857     * @param pro The projection used for this route
858     */
859 zoff99 27 static void route_info_distances(struct route_info *ri, enum projection pro)
860 zoff99 2 {
861 zoff99 27 int npos = ri->pos + 1;
862     struct street_data *sd = ri->street;
863 zoff99 2 /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
864 zoff99 27 ri->lenextra = transform_distance(pro, &ri->lp, &ri->c);
865     ri->lenneg = transform_polyline_length(pro, sd->c, npos)
866     + transform_distance(pro, &sd->c[ri->pos], &ri->lp);
867     ri->lenpos = transform_polyline_length(pro, sd->c + npos, sd->count - npos)
868     + transform_distance(pro, &sd->c[npos], &ri->lp);
869 zoff99 2 if (ri->lenneg || ri->lenpos)
870 zoff99 27 ri->percent = (ri->lenneg * 100) / (ri->lenneg + ri->lenpos);
871 zoff99 2 else
872 zoff99 27 ri->percent = 50;
873 zoff99 2 }
874    
875     /**
876     * @brief This sets the current position of the route passed
877     *
878     * This will set the current position of the route passed to the street that is nearest to the
879     * passed coordinates. It also automatically updates the route.
880     *
881     * @param this The route to set the position of
882     * @param pos Coordinates to set as position
883     */
884 zoff99 27 void route_set_position(struct route *this, struct pcoord *pos)
885 zoff99 2 {
886     if (this->pos)
887     route_info_free(this->pos);
888 zoff99 27 this->pos = NULL;
889     this->pos = route_find_nearest_street(this->vehicleprofile, this->ms, pos);
890 zoff99 2
891     // If there is no nearest street, bail out.
892 zoff99 27 if (!this->pos)
893     return;
894 zoff99 2
895 zoff99 27 this->pos->street_direction = 0;
896     //dbg(1, "this->pos=%p\n", this->pos);
897 zoff99 2 route_info_distances(this->pos, pos->pro);
898     route_path_update(this, 0, 1);
899     }
900    
901     /**
902     * @brief Sets a route's current position based on coordinates from tracking
903     *
904     * @param this The route to set the current position of
905     * @param tracking The tracking to get the coordinates from
906     */
907 zoff99 27 void route_set_position_from_tracking(struct route *this,
908     struct tracking *tracking, enum projection pro)
909 zoff99 2 {
910     struct coord *c;
911     struct route_info *ret;
912     struct street_data *sd;
913    
914 zoff99 27 //dbg(2, "enter\n");
915     c = tracking_get_pos(tracking);
916 zoff99 2 ret=g_new0(struct route_info, 1);
917 zoff99 27 if (!ret)
918     {
919 zoff99 2 printf("%s:Out of memory\n", __FUNCTION__);
920     return;
921     }
922     if (this->pos)
923     route_info_free(this->pos);
924 zoff99 27 this->pos = NULL;
925     ret->c = *c;
926     ret->lp = *c;
927     ret->pos = tracking_get_segment_pos(tracking);
928     ret->street_direction = tracking_get_street_direction(tracking);
929     sd = tracking_get_street_data(tracking);
930     if (sd)
931     {
932     ret->street = street_data_dup(sd);
933 zoff99 2 route_info_distances(ret, pro);
934     }
935 zoff99 27 //dbg(
936     // 3,
937     // "position 0x%x,0x%x item 0x%x,0x%x direction %d pos %d lenpos %d lenneg %d\n",
938     // c->x, c->y, sd ? sd->item.id_hi : 0, sd ? sd->item.id_lo : 0,
939     // ret->street_direction, ret->pos, ret->lenpos, ret->lenneg);
940     //dbg(3, "c->x=0x%x, c->y=0x%x pos=%d item=(0x%x,0x%x)\n", c->x, c->y,
941     // ret->pos, ret->street ? ret->street->item.id_hi : 0,
942     // ret->street ? ret->street->item.id_lo : 0);
943     //dbg(3, "street 0=(0x%x,0x%x) %d=(0x%x,0x%x)\n",
944     // ret->street ? ret->street->c[0].x : 0,
945     // ret->street ? ret->street->c[0].y : 0,
946     // ret->street ? ret->street->count - 1 : 0,
947     // ret->street ? ret->street->c[ret->street->count - 1].x : 0,
948     // ret->street ? ret->street->c[ret->street->count - 1].y : 0);
949     this->pos = ret;
950     if (this->destinations)
951 zoff99 2 route_path_update(this, 0, 1);
952 zoff99 27 //dbg(2, "ret\n");
953 zoff99 2 }
954    
955     /* Used for debuging of route_rect, what routing sees */
956     struct map_selection *route_selection;
957    
958     /**
959     * @brief Returns a single map selection
960     */
961     struct map_selection *
962     route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
963     {
964 zoff99 27 int dx, dy, sx = 1, sy = 1, d, m;
965 zoff99 2 struct map_selection *sel=g_new(struct map_selection, 1);
966 zoff99 27 if (!sel)
967     {
968 zoff99 2 printf("%s:Out of memory\n", __FUNCTION__);
969     return sel;
970     }
971 zoff99 27 sel->order = order;
972     sel->range.min = route_item_first;
973     sel->range.max = route_item_last;
974     dbg(1, "%p %p\n", c1, c2);
975     dx = c1->x - c2->x;
976     dy = c1->y - c2->y;
977     if (dx < 0)
978     {
979     sx = -1;
980     sel->u.c_rect.lu.x = c1->x;
981     sel->u.c_rect.rl.x = c2->x;
982 zoff99 2 }
983 zoff99 27 else
984     {
985     sel->u.c_rect.lu.x = c2->x;
986     sel->u.c_rect.rl.x = c1->x;
987 zoff99 2 }
988 zoff99 27 if (dy < 0)
989     {
990     sy = -1;
991     sel->u.c_rect.lu.y = c2->y;
992     sel->u.c_rect.rl.y = c1->y;
993     }
994 zoff99 2 else
995 zoff99 27 {
996     sel->u.c_rect.lu.y = c1->y;
997     sel->u.c_rect.rl.y = c2->y;
998     }
999     if (dx * sx > dy * sy)
1000     d = dx * sx;
1001     else
1002     d = dy * sy;
1003     m = d * rel / 100 + abs;
1004     sel->u.c_rect.lu.x -= m;
1005     sel->u.c_rect.rl.x += m;
1006     sel->u.c_rect.lu.y += m;
1007     sel->u.c_rect.rl.y -= m;
1008     sel->next = NULL;
1009 zoff99 2 return sel;
1010     }
1011    
1012     /**
1013     * @brief Returns a list of map selections useable to create a route graph
1014     *
1015     * Returns a list of map selections useable to get a map rect from which items can be
1016     * retrieved to build a route graph. The selections are a rectangle with
1017     * c1 and c2 as two corners.
1018     *
1019     * @param c1 Corner 1 of the rectangle
1020     * @param c2 Corder 2 of the rectangle
1021     */
1022     static struct map_selection *
1023 zoff99 27 route_calc_selection(struct coord *c, int count, int try_harder)
1024 zoff99 2 {
1025 zoff99 27 struct map_selection *ret, *sel;
1026 zoff99 2 int i;
1027     struct coord_rect r;
1028    
1029     if (!count)
1030     return NULL;
1031 zoff99 27 r.lu = c[0];
1032     r.rl = c[0];
1033     for (i = 1; i < count; i++)
1034 zoff99 2 {
1035     coord_rect_extend(&r, &c[i]);
1036     }
1037    
1038     if (routing_mode == 0)
1039     {
1040     // normal highway routing
1041     // sel=route_rect(4, &r.lu, &r.rl, 25, 0);
1042 zoff99 27 sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0);
1043 zoff99 2 }
1044     else if (routing_mode == 1)
1045     {
1046     // normal roads routing (should take longer and use more roads)
1047     // sel=route_rect(6, &r.lu, &r.rl, 25, 0);
1048 zoff99 27 sel = route_rect(try_harder ? 7 : 6, &r.lu, &r.rl, 25, 0);
1049 zoff99 2 }
1050     else
1051     {
1052     // DEFAULT setting
1053     // normal highway routing
1054     // sel=route_rect(4, &r.lu, &r.rl, 25, 0);
1055 zoff99 27 sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0);
1056 zoff99 2 }
1057    
1058 zoff99 27 ret = sel;
1059     for (i = 0; i < count; i++)
1060     {
1061     sel->next = route_rect(8, &c[i], &c[i], 0, 40000);
1062     sel = sel->next;
1063     sel->next = route_rect(18, &c[i], &c[i], 0, 10000);
1064     sel = sel->next;
1065 zoff99 2 }
1066     /* route_selection=ret; */
1067     return ret;
1068     }
1069    
1070     /**
1071     * @brief Destroys a list of map selections
1072     *
1073     * @param sel Start of the list to be destroyed
1074     */
1075 zoff99 27 static void route_free_selection(struct map_selection *sel)
1076 zoff99 2 {
1077     struct map_selection *next;
1078 zoff99 27 while (sel)
1079     {
1080     next = sel->next;
1081 zoff99 2 g_free(sel);
1082 zoff99 27 sel = next;
1083 zoff99 2 }
1084     }
1085    
1086 zoff99 27 static void route_clear_destinations(struct route *this_)
1087 zoff99 2 {
1088 zoff99 27 g_list_foreach(this_->destinations, (GFunc) route_info_free, NULL);
1089 zoff99 2 g_list_free(this_->destinations);
1090 zoff99 27 this_->destinations = NULL;
1091 zoff99 2 }
1092    
1093     /**
1094     * @brief Sets the destination of a route
1095     *
1096     * This sets the destination of a route to the street nearest to the coordinates passed
1097     * and updates the route.
1098     *
1099     * @param this The route to set the destination for
1100     * @param dst Coordinates to set as destination
1101     * @param count: Number of destinations (last one is final)
1102     * @param async: If set, do routing asynchronously
1103     */
1104    
1105 zoff99 27 void route_set_destinations(struct route *this, struct pcoord *dst, int count, int async)
1106 zoff99 2 {
1107     struct attr route_status;
1108     struct route_info *dsti;
1109     int i;
1110 zoff99 27 route_status.type = attr_route_status;
1111 zoff99 2
1112 zoff99 27 //profile(0,NULL);
1113 zoff99 2 route_clear_destinations(this);
1114 zoff99 27
1115     if (dst && count)
1116     {
1117     for (i = 0; i < count; i++)
1118     {
1119     dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[i]);
1120     if (dsti)
1121     {
1122     //dbg(0, "1: x y: %i %i\n", dst[i].x, dst[i].y);
1123     //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y);
1124 zoff99 2 route_info_distances(dsti, dst->pro);
1125 zoff99 27 this->destinations = g_list_append(this->destinations, dsti);
1126 zoff99 2 }
1127     }
1128 zoff99 27 route_status.u.num = route_status_destination_set;
1129     }
1130     else
1131     {
1132     route_status.u.num = route_status_no_destination;
1133     }
1134 zoff99 2 callback_list_call_attr_1(this->cbl2, attr_destination, this);
1135     route_set_attr(this, &route_status);
1136 zoff99 27 //profile(1,"find_nearest_street");
1137 zoff99 2
1138     /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
1139     route_graph_destroy(this->graph);
1140 zoff99 27 this->graph = NULL;
1141     this->current_dst = route_get_dst(this);
1142     this->try_harder = 0;
1143 zoff99 2 route_path_update(this, 1, async);
1144 zoff99 27 //profile(0,"end");
1145 zoff99 2 }
1146    
1147 zoff99 27 void route_add_destination(struct route *this, struct pcoord *dst, int async)
1148 zoff99 2 {
1149 zoff99 27 struct attr route_status;
1150     struct route_info *dsti;
1151     route_status.type = attr_route_status;
1152    
1153     dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[0]);
1154     if (dsti)
1155     {
1156     //dbg(0, "1: x y: %i %i\n", dst[0].x, dst[0].y);
1157     //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y);
1158    
1159     route_info_distances(dsti, dst->pro);
1160     this->destinations = g_list_append(this->destinations, dsti);
1161    
1162     route_status.u.num = route_status_destination_set;
1163     }
1164    
1165     callback_list_call_attr_1(this->cbl2, attr_destination, this);
1166     route_set_attr(this, &route_status);
1167    
1168     /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
1169     route_graph_destroy(this->graph);
1170     this->graph = NULL;
1171     this->current_dst = route_get_dst(this);
1172     this->try_harder = 0;
1173     route_path_update(this, 1, async);
1174     }
1175    
1176     int route_get_destinations(struct route *this, struct pcoord *pc, int count)
1177     {
1178     int ret = 0;
1179     GList *l = this->destinations;
1180     while (l && ret < count)
1181     {
1182     struct route_info *dst = l->data;
1183     pc->x = dst->c.x;
1184     pc->y = dst->c.y;
1185     pc->pro = projection_mg; /* FIXME */
1186 zoff99 2 pc++;
1187     ret++;
1188 zoff99 27 l = g_list_next(l);
1189 zoff99 2 }
1190     return ret;
1191     }
1192 zoff99 27
1193     void route_set_destination(struct route *this, struct pcoord *dst, int async)
1194 zoff99 2 {
1195 zoff99 27 route_set_destinations(this, dst, dst ? 1 : 0, async);
1196 zoff99 2 }
1197    
1198 zoff99 27 void route_remove_waypoint(struct route *this)
1199 zoff99 2 {
1200 zoff99 27 struct route_path *path = this->path2;
1201     this->destinations = g_list_remove(this->destinations,
1202     this->destinations->data);
1203     this->path2 = this->path2->next;
1204     route_path_destroy(path, 0);
1205 zoff99 2 if (!this->destinations)
1206     return;
1207     route_graph_reset(this->graph);
1208 zoff99 27 this->current_dst = this->destinations->data;
1209     route_graph_flood(this->graph, this->current_dst, this->vehicleprofile,
1210     this->route_graph_flood_done_cb);
1211    
1212 zoff99 2 }
1213    
1214     /**
1215     * @brief Gets the route_graph_point with the specified coordinates
1216     *
1217     * @param this The route in which to search
1218     * @param c Coordinates to search for
1219     * @param last The last route graph point returned to iterate over multiple points with the same coordinates
1220     * @return The point at the specified coordinates or NULL if not found
1221     */
1222     static struct route_graph_point *
1223 zoff99 27 route_graph_get_point_next(struct route_graph *this, struct coord *c,
1224     struct route_graph_point *last)
1225 zoff99 2 {
1226     struct route_graph_point *p;
1227 zoff99 27 int seen = 0, hashval = HASHCOORD(c);
1228     p = this->hash[hashval];
1229     while (p)
1230     {
1231     if (p->c.x == c->x && p->c.y == c->y)
1232     {
1233 zoff99 2 if (!last || seen)
1234     return p;
1235     if (p == last)
1236 zoff99 27 seen = 1;
1237 zoff99 2 }
1238 zoff99 27 p = p->hash_next;
1239 zoff99 2 }
1240     return NULL;
1241     }
1242    
1243     static struct route_graph_point *
1244     route_graph_get_point(struct route_graph *this, struct coord *c)
1245     {
1246     return route_graph_get_point_next(this, c, NULL);
1247     }
1248    
1249     /**
1250     * @brief Gets the last route_graph_point with the specified coordinates
1251     *
1252     * @param this The route in which to search
1253     * @param c Coordinates to search for
1254     * @return The point at the specified coordinates or NULL if not found
1255     */
1256     static struct route_graph_point *
1257     route_graph_get_point_last(struct route_graph *this, struct coord *c)
1258     {
1259 zoff99 27 struct route_graph_point *p, *ret = NULL;
1260     int hashval = HASHCOORD(c);
1261     p = this->hash[hashval];
1262     while (p)
1263     {
1264 zoff99 2 if (p->c.x == c->x && p->c.y == c->y)
1265 zoff99 27 ret = p;
1266     p = p->hash_next;
1267 zoff99 2 }
1268     return ret;
1269     }
1270    
1271     /**
1272     * @brief Create a new point for the route graph with the specified coordinates
1273     *
1274     * @param this The route to insert the point into
1275     * @param f The coordinates at which the point should be created
1276     * @return The point created
1277     */
1278    
1279     static struct route_graph_point *
1280     route_graph_point_new(struct route_graph *this, struct coord *f)
1281     {
1282     int hashval;
1283     struct route_graph_point *p;
1284    
1285 zoff99 27 hashval = HASHCOORD(f);
1286 zoff99 2 if (debug_route)
1287     printf("p (0x%x,0x%x)\n", f->x, f->y);
1288     p=g_slice_new0(struct route_graph_point);
1289 zoff99 27 p->hash_next = this->hash[hashval];
1290     this->hash[hashval] = p;
1291     p->value = INT_MAX;
1292     p->c = *f;
1293 zoff99 2 return p;
1294     }
1295    
1296     /**
1297     * @brief Inserts a point into the route graph at the specified coordinates
1298     *
1299     * This will insert a point into the route graph at the coordinates passed in f.
1300     * Note that the point is not yet linked to any segments.
1301     *
1302     * @param this The route to insert the point into
1303     * @param f The coordinates at which the point should be inserted
1304     * @return The point inserted or NULL on failure
1305     */
1306     static struct route_graph_point *
1307     route_graph_add_point(struct route_graph *this, struct coord *f)
1308     {
1309     struct route_graph_point *p;
1310    
1311 zoff99 27 p = route_graph_get_point(this, f);
1312 zoff99 2 if (!p)
1313 zoff99 27 p = route_graph_point_new(this, f);
1314 zoff99 2 return p;
1315     }
1316    
1317     /**
1318     * @brief Frees all the memory used for points in the route graph passed
1319     *
1320     * @param this The route graph to delete all points from
1321     */
1322 zoff99 27 static void route_graph_free_points(struct route_graph *this)
1323 zoff99 2 {
1324 zoff99 27 struct route_graph_point *curr, *next;
1325 zoff99 2 int i;
1326 zoff99 27 for (i = 0; i < HASH_SIZE; i++)
1327     {
1328     curr = this->hash[i];
1329     while (curr)
1330     {
1331     next = curr->hash_next;
1332 zoff99 2 g_slice_free(struct route_graph_point, curr);
1333 zoff99 27 curr = next;
1334 zoff99 2 }
1335 zoff99 27 this->hash[i] = NULL;
1336 zoff99 2 }
1337     }
1338    
1339     /**
1340     * @brief Resets all nodes
1341     *
1342     * @param this The route graph to reset
1343     */
1344 zoff99 27 static void route_graph_reset(struct route_graph *this)
1345 zoff99 2 {
1346     struct route_graph_point *curr;
1347     int i;
1348 zoff99 27 for (i = 0; i < HASH_SIZE; i++)
1349     {
1350     curr = this->hash[i];
1351     while (curr)
1352     {
1353     curr->value = INT_MAX;
1354     curr->seg = NULL;
1355     curr->el = NULL;
1356     curr = curr->hash_next;
1357 zoff99 2 }
1358     }
1359     }
1360    
1361     /**
1362     * @brief Returns the position of a certain field appended to a route graph segment
1363     *
1364     * This function returns a pointer to a field that is appended to a route graph
1365     * segment.
1366     *
1367     * @param seg The route graph segment the field is appended to
1368     * @param type Type of the field that should be returned
1369     * @return A pointer to a field of a certain type, or NULL if no such field is present
1370     */
1371     static void *
1372 zoff99 27 route_segment_data_field_pos(struct route_segment_data *seg,
1373     enum attr_type type)
1374 zoff99 2 {
1375     unsigned char *ptr;
1376    
1377 zoff99 27 ptr = ((unsigned char*) seg) + sizeof(struct route_segment_data);
1378    
1379     if (seg->flags & AF_SPEED_LIMIT)
1380     {
1381     if (type == attr_maxspeed)
1382     return (void*) ptr;
1383 zoff99 2 ptr += sizeof(int);
1384     }
1385 zoff99 27 if (seg->flags & AF_SEGMENTED)
1386     {
1387     if (type == attr_offset)
1388     return (void*) ptr;
1389 zoff99 2 ptr += sizeof(int);
1390     }
1391 zoff99 27 if (seg->flags & AF_SIZE_OR_WEIGHT_LIMIT)
1392     {
1393 zoff99 2 if (type == attr_vehicle_width)
1394 zoff99 27 return (void*) ptr;
1395 zoff99 2 ptr += sizeof(struct size_weight_limit);
1396     }
1397 zoff99 27 if (seg->flags & AF_DANGEROUS_GOODS)
1398     {
1399 zoff99 2 if (type == attr_vehicle_dangerous_goods)
1400 zoff99 27 return (void*) ptr;
1401 zoff99 2 ptr += sizeof(int);
1402     }
1403     return NULL;
1404     }
1405    
1406     /**
1407     * @brief Calculates the size of a route_segment_data struct with given flags
1408     *
1409     * @param flags The flags of the route_segment_data
1410     */
1411    
1412 zoff99 27 static int route_segment_data_size(int flags)
1413 zoff99 2 {
1414 zoff99 27 int ret = sizeof(struct route_segment_data);
1415 zoff99 2 if (flags & AF_SPEED_LIMIT)
1416 zoff99 27 ret += sizeof(int);
1417 zoff99 2 if (flags & AF_SEGMENTED)
1418 zoff99 27 ret += sizeof(int);
1419 zoff99 2 if (flags & AF_SIZE_OR_WEIGHT_LIMIT)
1420 zoff99 27 ret += sizeof(struct size_weight_limit);
1421 zoff99 2 if (flags & AF_DANGEROUS_GOODS)
1422 zoff99 27 ret += sizeof(int);
1423 zoff99 2 return ret;
1424     }
1425    
1426 zoff99 27 static int route_graph_segment_is_duplicate(struct route_graph_point *start,
1427     struct route_graph_segment_data *data)
1428 zoff99 2 {
1429     struct route_graph_segment *s;
1430 zoff99 27 s = start->start;
1431     while (s)
1432     {
1433     if (item_is_equal(*data->item, s->data.item))
1434     {
1435     if (data->flags & AF_SEGMENTED)
1436     {
1437     if (RSD_OFFSET(&s->data) == data->offset)
1438     {
1439 zoff99 2 return 1;
1440     }
1441 zoff99 27 }
1442     else
1443 zoff99 2 return 1;
1444     }
1445 zoff99 27 s = s->start_next;
1446     }
1447 zoff99 2 return 0;
1448     }
1449    
1450     /**
1451     * @brief Inserts a new segment into the route graph
1452     *
1453     * This function performs a check if a segment for the item specified already exists, and inserts
1454     * a new segment representing this item if it does not.
1455     *
1456     * @param this The route graph to insert the segment into
1457     * @param start The graph point which should be connected to the start of this segment
1458     * @param end The graph point which should be connected to the end of this segment
1459     * @param len The length of this segment
1460     * @param item The item that is represented by this segment
1461     * @param flags Flags for this segment
1462     * @param offset If the item passed in "item" is segmented (i.e. divided into several segments), this indicates the position of this segment within the item
1463     * @param maxspeed The maximum speed allowed on this segment in km/h. -1 if not known.
1464     */
1465 zoff99 27 static void route_graph_add_segment(struct route_graph *this,
1466     struct route_graph_point *start, struct route_graph_point *end,
1467     struct route_graph_segment_data *data)
1468 zoff99 2 {
1469     struct route_graph_segment *s;
1470     int size;
1471    
1472 zoff99 27 size = sizeof(struct route_graph_segment)
1473     - sizeof(struct route_segment_data) + route_segment_data_size(
1474     data->flags);
1475 zoff99 2 s = g_slice_alloc0(size);
1476 zoff99 27 if (!s)
1477     {
1478 zoff99 2 printf("%s:Out of memory\n", __FUNCTION__);
1479     return;
1480     }
1481 zoff99 27 s->start = start;
1482     s->start_next = start->start;
1483     start->start = s;
1484     s->end = end;
1485     s->end_next = end->end;
1486     end->end = s;
1487 zoff99 2 dbg_assert(data->len >= 0);
1488 zoff99 27 s->data.len = data->len;
1489     s->data.item = *data->item;
1490     s->data.flags = data->flags;
1491 zoff99 2
1492 zoff99 27 if (data->flags & AF_SPEED_LIMIT)
1493     RSD_MAXSPEED(&s->data) = data->maxspeed;
1494     if (data->flags & AF_SEGMENTED)
1495     RSD_OFFSET(&s->data) = data->offset;
1496     if (data->flags & AF_SIZE_OR_WEIGHT_LIMIT)
1497     RSD_SIZE_WEIGHT(&s->data) = data->size_weight;
1498     if (data->flags & AF_DANGEROUS_GOODS)
1499     RSD_DANGEROUS_GOODS(&s->data) = data->dangerous_goods;
1500 zoff99 2
1501 zoff99 27 s->next = this->route_segments;
1502     this->route_segments = s;
1503 zoff99 2 if (debug_route)
1504 zoff99 27 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x,
1505     end->c.y);
1506 zoff99 2 }
1507    
1508     /**
1509     * @brief Gets all the coordinates of an item
1510     *
1511     * This will get all the coordinates of the item i and return them in c,
1512     * up to max coordinates. Additionally it is possible to limit the coordinates
1513     * returned to all the coordinates of the item between the two coordinates
1514     * start end end.
1515     *
1516     * @important Make sure that whatever c points to has enough memory allocated
1517     * @important to hold max coordinates!
1518     *
1519     * @param i The item to get the coordinates of
1520     * @param c Pointer to memory allocated for holding the coordinates
1521     * @param max Maximum number of coordinates to return
1522     * @param start First coordinate to get
1523     * @param end Last coordinate to get
1524     * @return The number of coordinates returned
1525     */
1526     static int get_item_seg_coords(struct item *i, struct coord *c, int max,
1527     struct coord *start, struct coord *end)
1528     {
1529     struct map_rect *mr;
1530     struct item *item;
1531     int rc = 0, p = 0;
1532     struct coord c1;
1533 zoff99 27 mr = map_rect_new(i->map, NULL);
1534 zoff99 2 if (!mr)
1535     return 0;
1536     item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
1537 zoff99 27 if (item)
1538     {
1539 zoff99 2 rc = item_coord_get(item, &c1, 1);
1540 zoff99 27 while (rc && (c1.x != start->x || c1.y != start->y))
1541     {
1542 zoff99 2 rc = item_coord_get(item, &c1, 1);
1543     }
1544 zoff99 27 while (rc && p < max)
1545     {
1546 zoff99 2 c[p++] = c1;
1547     if (c1.x == end->x && c1.y == end->y)
1548     break;
1549     rc = item_coord_get(item, &c1, 1);
1550     }
1551     }
1552     map_rect_destroy(mr);
1553     return p;
1554     }
1555    
1556     /**
1557     * @brief Returns and removes one segment from a path
1558     *
1559     * @param path The path to take the segment from
1560     * @param item The item whose segment to remove
1561     * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
1562     * @return The segment removed
1563     */
1564     static struct route_path_segment *
1565     route_extract_segment_from_path(struct route_path *path, struct item *item,
1566 zoff99 27 int offset)
1567 zoff99 2 {
1568     int soffset;
1569     struct route_path_segment *sp = NULL, *s;
1570     s = path->path;
1571 zoff99 27 while (s)
1572     {
1573     if (item_is_equal(s->data->item, *item))
1574     {
1575 zoff99 2 if (s->data->flags & AF_SEGMENTED)
1576 zoff99 27 soffset = RSD_OFFSET(s->data);
1577 zoff99 2 else
1578 zoff99 27 soffset = 1;
1579     if (soffset == offset)
1580     {
1581     if (sp)
1582     {
1583 zoff99 2 sp->next = s->next;
1584     break;
1585 zoff99 27 }
1586     else
1587     {
1588 zoff99 2 path->path = s->next;
1589     break;
1590     }
1591     }
1592     }
1593     sp = s;
1594     s = s->next;
1595     }
1596     if (s)
1597     item_hash_remove(path->path_hash, item);
1598     return s;
1599     }
1600    
1601     /**
1602     * @brief Adds a segment and the end of a path
1603     *
1604     * @param this The path to add the segment to
1605     * @param segment The segment to add
1606     */
1607 zoff99 27 static void route_path_add_segment(struct route_path *this,
1608     struct route_path_segment *segment)
1609 zoff99 2 {
1610     if (!this->path)
1611 zoff99 27 this->path = segment;
1612 zoff99 2 if (this->path_last)
1613 zoff99 27 this->path_last->next = segment;
1614     this->path_last = segment;
1615 zoff99 2 }
1616    
1617     /**
1618     * @brief Adds a two coordinate line to a path
1619     *
1620     * This adds a new line to a path, creating a new segment for it.
1621     *
1622     * @param this The path to add the item to
1623     * @param start coordinate to add to the start of the item. If none should be added, make this NULL.
1624     * @param end coordinate to add to the end of the item. If none should be added, make this NULL.
1625     * @param len The length of the item
1626     */
1627 zoff99 27 static void route_path_add_line(struct route_path *this, struct coord *start,
1628     struct coord *end, int len)
1629 zoff99 2 {
1630 zoff99 27 int ccnt = 2;
1631 zoff99 2 struct route_path_segment *segment;
1632 zoff99 27 int seg_size, seg_dat_size;
1633 zoff99 2
1634 zoff99 27 //dbg(1, "line from 0x%x,0x%x-0x%x,0x%x\n", start->x, start->y, end->x,
1635     // end->y);
1636     seg_size = sizeof(*segment) + sizeof(struct coord) * ccnt;
1637     seg_dat_size = sizeof(struct route_segment_data);
1638     segment = g_malloc0(seg_size + seg_dat_size);
1639     segment->data = (struct route_segment_data *) ((char *) segment + seg_size);
1640     segment->ncoords = ccnt;
1641     segment->direction = 0;
1642     segment->c[0] = *start;
1643     segment->c[1] = *end;
1644     segment->data->len = len;
1645 zoff99 2 route_path_add_segment(this, segment);
1646     }
1647    
1648     /**
1649     * @brief Inserts a new item into the path
1650     *
1651     * This function does almost the same as "route_path_add_item()", but identifies
1652     * the item to add by a segment from the route graph. Another difference is that it "copies" the
1653     * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
1654     * be added to the route path, not all segments of the item.
1655     *
1656     * The function can be sped up by passing an old path already containing this segment in oldpath -
1657     * the segment will then be extracted from this old path. Please note that in this case the direction
1658     * parameter has no effect.
1659     *
1660     * @param this The path to add the item to
1661     * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
1662     * @param rgs Segment of the route graph that should be "copied" to the route path
1663     * @param dir Order in which to add the coordinates. See route_path_add_item()
1664     * @param pos Information about start point if this is the first segment
1665     * @param dst Information about end point if this is the last segment
1666     */
1667    
1668 zoff99 27 static int route_path_add_item_from_graph(struct route_path *this,
1669     struct route_path *oldpath, struct route_graph_segment *rgs, int dir,
1670     struct route_info *pos, struct route_info *dst)
1671 zoff99 2 {
1672     struct route_path_segment *segment;
1673 zoff99 27 int i, ccnt, extra = 0, ret = 0;
1674     struct coord *c, *cd, ca[2048];
1675     int offset = 1;
1676     int seg_size, seg_dat_size;
1677     int len = rgs->data.len;
1678     if (rgs->data.flags & AF_SEGMENTED)
1679     {
1680     offset = RSD_OFFSET(&rgs->data);
1681     }
1682 zoff99 2
1683 zoff99 27 //dbg(1, "enter (0x%x,0x%x) dir=%d pos=%p dst=%p\n", rgs->data.item.id_hi,
1684     // rgs->data.item.id_lo, dir, pos, dst);
1685     if (oldpath)
1686     {
1687     segment = item_hash_lookup(oldpath->path_hash, &rgs->data.item);
1688     if (segment && segment->direction == dir)
1689     {
1690     segment = route_extract_segment_from_path(oldpath, &rgs->data.item,
1691     offset);
1692     if (segment)
1693     {
1694     ret = 1;
1695 zoff99 2 if (!pos)
1696     goto linkold;
1697     }
1698     }
1699     }
1700    
1701 zoff99 27 if (pos)
1702     {
1703     if (dst)
1704     {
1705     extra = 2;
1706     if (dst->lenneg >= pos->lenneg)
1707     {
1708     dir = 1;
1709     ccnt = dst->pos - pos->pos;
1710     c = pos->street->c + pos->pos + 1;
1711     len = dst->lenneg - pos->lenneg;
1712 zoff99 2 }
1713 zoff99 27 else
1714     {
1715     dir = -1;
1716     ccnt = pos->pos - dst->pos;
1717     c = pos->street->c + dst->pos + 1;
1718     len = pos->lenneg - dst->lenneg;
1719 zoff99 2 }
1720     }
1721 zoff99 27 else
1722     {
1723     extra = 1;
1724     //dbg(1, "pos dir=%d\n", dir);
1725     //dbg(1, "pos pos=%d\n", pos->pos);
1726     //dbg(1, "pos count=%d\n", pos->street->count);
1727     if (dir > 0)
1728     {
1729     c = pos->street->c + pos->pos + 1;
1730     ccnt = pos->street->count - pos->pos - 1;
1731     len = pos->lenpos;
1732     }
1733     else
1734     {
1735     c = pos->street->c;
1736     ccnt = pos->pos + 1;
1737     len = pos->lenneg;
1738     }
1739 zoff99 2 }
1740 zoff99 27 pos->dir = dir;
1741 zoff99 2 }
1742 zoff99 27 else if (dst)
1743     {
1744     extra = 1;
1745     //dbg(1, "dst dir=%d\n", dir);
1746     //dbg(1, "dst pos=%d\n", dst->pos);
1747     if (dir > 0)
1748     {
1749     c = dst->street->c;
1750     ccnt = dst->pos + 1;
1751     len = dst->lenpos;
1752     }
1753     else
1754     {
1755     c = dst->street->c + dst->pos + 1;
1756     ccnt = dst->street->count - dst->pos - 1;
1757     len = dst->lenneg;
1758     }
1759     }
1760     else
1761     {
1762     ccnt = get_item_seg_coords(&rgs->data.item, ca, 2047, &rgs->start->c,
1763     &rgs->end->c);
1764     c = ca;
1765     }
1766     seg_size = sizeof(*segment) + sizeof(struct coord) * (ccnt + extra);
1767     seg_dat_size = route_segment_data_size(rgs->data.flags);
1768     segment = g_malloc0(seg_size + seg_dat_size);
1769     segment->data = (struct route_segment_data *) ((char *) segment + seg_size);
1770     segment->direction = dir;
1771     cd = segment->c;
1772 zoff99 2 if (pos && (c[0].x != pos->lp.x || c[0].y != pos->lp.y))
1773 zoff99 27 *cd++ = pos->lp;
1774 zoff99 2 if (dir < 0)
1775 zoff99 27 c += ccnt - 1;
1776     for (i = 0; i < ccnt; i++)
1777     {
1778     *cd++ = *c;
1779     c += dir;
1780 zoff99 2 }
1781 zoff99 27 segment->ncoords += ccnt;
1782     if (dst && (cd[-1].x != dst->lp.x || cd[-1].y != dst->lp.y))
1783     *cd++ = dst->lp;
1784     segment->ncoords = cd - segment->c;
1785     if (segment->ncoords <= 1)
1786     {
1787 zoff99 2 g_free(segment);
1788     return 1;
1789     }
1790    
1791     /* We check if the route graph segment is part of a roundabout here, because this
1792     * only matters for route graph segments which form parts of the route path */
1793 zoff99 27 if (!(rgs->data.flags & AF_ROUNDABOUT))
1794     { // We identified this roundabout earlier
1795 zoff99 2 route_check_roundabout(rgs, 13, (dir < 1), NULL);
1796     }
1797    
1798     memcpy(segment->data, &rgs->data, seg_dat_size);
1799 zoff99 27 linkold: segment->data->len = len;
1800     segment->next = NULL;
1801     item_hash_insert(this->path_hash, &rgs->data.item, segment);
1802 zoff99 2
1803     route_path_add_segment(this, segment);
1804    
1805     return ret;
1806     }
1807    
1808     /**
1809     * @brief Destroys all segments of a route graph
1810     *
1811     * @param this The graph to destroy all segments from
1812     */
1813 zoff99 27 static void route_graph_free_segments(struct route_graph *this)
1814 zoff99 2 {
1815 zoff99 27 struct route_graph_segment *curr, *next;
1816 zoff99 2 int size;
1817 zoff99 27 curr = this->route_segments;
1818     while (curr)
1819     {
1820     next = curr->next;
1821     size = sizeof(struct route_graph_segment)
1822     - sizeof(struct route_segment_data) + route_segment_data_size(
1823     curr->data.flags);
1824 zoff99 2 g_slice_free1(size, curr);
1825 zoff99 27 curr = next;
1826 zoff99 2 }
1827 zoff99 27 this->route_segments = NULL;
1828 zoff99 2 }
1829    
1830     /**
1831     * @brief Destroys a route graph
1832     *
1833     * @param this The route graph to be destroyed
1834     */
1835 zoff99 27 void route_graph_destroy(struct route_graph *this)
1836 zoff99 2 {
1837 zoff99 27 if (this)
1838     {
1839 zoff99 2 route_graph_build_done(this, 1);
1840     route_graph_free_points(this);
1841     route_graph_free_segments(this);
1842     g_free(this);
1843     }
1844     }
1845    
1846     /**
1847     * @brief Returns the estimated speed on a segment
1848     *
1849     * This function returns the estimated speed to be driven on a segment, 0=not passable
1850     *
1851     * @param profile The routing preferences
1852     * @param over The segment which is passed
1853     * @param dist A traffic distortion if applicable
1854     * @return The estimated speed
1855     */
1856 zoff99 27 static int route_seg_speed(struct vehicleprofile *profile,
1857     struct route_segment_data *over, struct route_traffic_distortion *dist)
1858 zoff99 2 {
1859 zoff99 27 struct roadprofile *roadprofile = vehicleprofile_get_roadprofile(profile,
1860     over->item.type);
1861     int speed, maxspeed;
1862 zoff99 2 if (!roadprofile || !roadprofile->route_weight)
1863     return 0;
1864     /* maxspeed_handling: 0=always, 1 only if maxspeed restricts the speed, 2 never */
1865 zoff99 27 speed = roadprofile->route_weight;
1866     if (profile->maxspeed_handling != 2)
1867     {
1868     if (over->flags & AF_SPEED_LIMIT)
1869     {
1870     maxspeed = RSD_MAXSPEED(over);
1871 zoff99 2 if (!profile->maxspeed_handling)
1872 zoff99 27 speed = maxspeed;
1873     }
1874     else
1875     maxspeed = INT_MAX;
1876 zoff99 2 if (dist && maxspeed > dist->maxspeed)
1877 zoff99 27 maxspeed = dist->maxspeed;
1878     if (maxspeed != INT_MAX && (profile->maxspeed_handling != 1 || maxspeed
1879     < speed))
1880     speed = maxspeed;
1881 zoff99 2 }
1882 zoff99 27 if (over->flags & AF_DANGEROUS_GOODS)
1883     {
1884 zoff99 2 if (profile->dangerous_goods & RSD_DANGEROUS_GOODS(over))
1885     return 0;
1886     }
1887 zoff99 27 if (over->flags & AF_SIZE_OR_WEIGHT_LIMIT)
1888     {
1889     struct size_weight_limit *size_weight = &RSD_SIZE_WEIGHT(over);
1890     if (size_weight->width != -1 && profile->width != -1 && profile->width
1891     > size_weight->width)
1892 zoff99 2 return 0;
1893 zoff99 27 if (size_weight->height != -1 && profile->height != -1
1894     && profile->height > size_weight->height)
1895 zoff99 2 return 0;
1896 zoff99 27 if (size_weight->length != -1 && profile->length != -1
1897     && profile->length > size_weight->length)
1898 zoff99 2 return 0;
1899 zoff99 27 if (size_weight->weight != -1 && profile->weight != -1
1900     && profile->weight > size_weight->weight)
1901 zoff99 2 return 0;
1902 zoff99 27 if (size_weight->axle_weight != -1 && profile->axle_weight != -1
1903     && profile->axle_weight > size_weight->axle_weight)
1904 zoff99 2 return 0;
1905     }
1906     return speed;
1907     }
1908    
1909     /**
1910     * @brief Returns the time needed to drive len on item
1911     *
1912     * This function returns the time needed to drive len meters on
1913     * the item passed in item in tenth of seconds.
1914     *
1915     * @param profile The routing preferences
1916     * @param over The segment which is passed
1917     * @param dist A traffic distortion if applicable
1918     * @return The time needed to drive len on item in thenth of senconds
1919     */
1920    
1921 zoff99 27 static int route_time_seg(struct vehicleprofile *profile,
1922     struct route_segment_data *over, struct route_traffic_distortion *dist)
1923 zoff99 2 {
1924 zoff99 27 int speed = route_seg_speed(profile, over, dist);
1925 zoff99 2 if (!speed)
1926     return INT_MAX;
1927 zoff99 27 return over->len * 36 / speed + (dist ? dist->delay : 0);
1928 zoff99 2 }
1929    
1930 zoff99 27 static int route_get_traffic_distortion(struct route_graph_segment *seg,
1931     struct route_traffic_distortion *ret)
1932 zoff99 2 {
1933 zoff99 27 struct route_graph_point *start = seg->start;
1934     struct route_graph_point *end = seg->end;
1935     struct route_graph_segment *tmp, *found = NULL;
1936     tmp = start->start;
1937     while (tmp && !found)
1938     {
1939     if (tmp->data.item.type == type_traffic_distortion && tmp->start
1940     == start && tmp->end == end)
1941     found = tmp;
1942     tmp = tmp->start_next;
1943 zoff99 2 }
1944 zoff99 27 tmp = start->end;
1945     while (tmp && !found)
1946     {
1947     if (tmp->data.item.type == type_traffic_distortion && tmp->end == start
1948     && tmp->start == end)
1949     found = tmp;
1950     tmp = tmp->end_next;
1951 zoff99 2 }
1952 zoff99 27 if (found)
1953     {
1954     ret->delay = found->data.len;
1955 zoff99 2 if (found->data.flags & AF_SPEED_LIMIT)
1956 zoff99 27 ret->maxspeed = RSD_MAXSPEED(&found->data);
1957 zoff99 2 else
1958 zoff99 27 ret->maxspeed = INT_MAX;
1959 zoff99 2 return 1;
1960     }
1961     return 0;
1962     }
1963    
1964 zoff99 27 static int route_through_traffic_allowed(struct vehicleprofile *profile,
1965     struct route_graph_segment *seg)
1966 zoff99 2 {
1967     return (seg->data.flags & AF_THROUGH_TRAFFIC_LIMIT) == 0;
1968     }
1969    
1970     /**
1971     * @brief Returns the "costs" of driving from point from over segment over in direction dir
1972     *
1973     * @param profile The routing preferences
1974     * @param from The point where we are starting
1975     * @param over The segment we are using
1976     * @param dir The direction of segment which we are driving
1977     * @return The "costs" needed to drive len on item
1978 zoff99 27 */
1979 zoff99 2
1980 zoff99 27 static int route_value_seg(struct vehicleprofile *profile,
1981     struct route_graph_point *from, struct route_graph_segment *over,
1982     int dir)
1983 zoff99 2 {
1984     int ret;
1985 zoff99 27 struct route_traffic_distortion dist, *distp = NULL;
1986 zoff99 2 #if 0
1987     dbg(0,"flags 0x%x mask 0x%x flags 0x%x\n", over->flags, dir >= 0 ? profile->flags_forward_mask : profile->flags_reverse_mask, profile->flags);
1988     #endif
1989 zoff99 27 if ((over->data.flags & (dir >= 0 ? profile->flags_forward_mask
1990     : profile->flags_reverse_mask)) != profile->flags)
1991 zoff99 2 return INT_MAX;
1992     if (dir > 0 && (over->start->flags & RP_TURN_RESTRICTION))
1993     return INT_MAX;
1994     if (dir < 0 && (over->end->flags & RP_TURN_RESTRICTION))
1995     return INT_MAX;
1996     if (from && from->seg == over)
1997     return INT_MAX;
1998 zoff99 27 if ((over->start->flags & RP_TRAFFIC_DISTORTION) && (over->end->flags
1999     & RP_TRAFFIC_DISTORTION) && route_get_traffic_distortion(over,
2000     &dist))
2001     {
2002     distp = &dist;
2003 zoff99 2 }
2004 zoff99 27 ret = route_time_seg(profile, &over->data, distp);
2005 zoff99 2 if (ret == INT_MAX)
2006     return ret;
2007 zoff99 27 if (!route_through_traffic_allowed(profile, over) && from
2008     && route_through_traffic_allowed(profile, from->seg))
2009     ret += profile->through_traffic_penalty;
2010 zoff99 2 return ret;
2011     }
2012    
2013     /**
2014     * @brief Adds a route distortion item to the route graph
2015     *
2016     * @param this The route graph to add to
2017     * @param item The item to add
2018     */
2019 zoff99 27 static void route_process_traffic_distortion(struct route_graph *this,
2020     struct item *item)
2021 zoff99 2 {
2022 zoff99 27 struct route_graph_point *s_pnt, *e_pnt;
2023     struct coord c, l;
2024 zoff99 2 struct attr delay_attr, maxspeed_attr;
2025     struct route_graph_segment_data data;
2026    
2027 zoff99 27 data.item = item;
2028     data.len = 0;
2029     data.flags = 0;
2030     data.offset = 1;
2031 zoff99 2 data.maxspeed = INT_MAX;
2032    
2033 zoff99 27 if (item_coord_get(item, &l, 1))
2034     {
2035     s_pnt = route_graph_add_point(this, &l);
2036     while (item_coord_get(item, &c, 1))
2037     {
2038     l = c;
2039 zoff99 2 }
2040 zoff99 27 e_pnt = route_graph_add_point(this, &l);
2041 zoff99 2 s_pnt->flags |= RP_TRAFFIC_DISTORTION;
2042     e_pnt->flags |= RP_TRAFFIC_DISTORTION;
2043 zoff99 27 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr))
2044     {
2045 zoff99 2 data.flags |= AF_SPEED_LIMIT;
2046 zoff99 27 data.maxspeed = maxspeed_attr.u.num;
2047 zoff99 2 }
2048     if (item_attr_get(item, attr_delay, &delay_attr))
2049 zoff99 27 data.len = delay_attr.u.num;
2050 zoff99 2 route_graph_add_segment(this, s_pnt, e_pnt, &data);
2051     }
2052     }
2053    
2054     /**
2055     * @brief Adds a route distortion item to the route graph
2056     *
2057     * @param this The route graph to add to
2058     * @param item The item to add
2059     */
2060 zoff99 27 static void route_process_turn_restriction(struct route_graph *this,
2061     struct item *item)
2062 zoff99 2 {
2063     struct route_graph_point *pnt[4];
2064     struct coord c[5];
2065 zoff99 27 int i, count;
2066 zoff99 2 struct route_graph_segment_data data;
2067    
2068 zoff99 27 count = item_coord_get(item, c, 5);
2069     if (count != 3 && count != 4)
2070     {
2071     dbg(0, "wrong count %d\n", count);
2072 zoff99 2 return;
2073     }
2074     if (count == 4)
2075 zoff99 27 {
2076 zoff99 2 return;
2077 zoff99 27 }
2078     for (i = 0; i < count; i++)
2079     {
2080     pnt[i] = route_graph_add_point(this, &c[i]);
2081     }
2082     //dbg(1, "%s: (0x%x,0x%x)-(0x%x,0x%x)-(0x%x,0x%x) %p-%p-%p\n",
2083     // item_to_name(item->type), c[0].x, c[0].y, c[1].x, c[1].y, c[2].x,
2084     // c[2].y, pnt[0], pnt[1], pnt[2]);
2085     data.item = item;
2086     data.flags = 0;
2087     data.len = 0;
2088 zoff99 2 route_graph_add_segment(this, pnt[0], pnt[1], &data);
2089     route_graph_add_segment(this, pnt[1], pnt[2], &data);
2090     #if 1
2091 zoff99 27 if (count == 4)
2092     {
2093 zoff99 2 pnt[1]->flags |= RP_TURN_RESTRICTION;
2094     pnt[2]->flags |= RP_TURN_RESTRICTION;
2095     route_graph_add_segment(this, pnt[2], pnt[3], &data);
2096 zoff99 27 }
2097     else
2098     {
2099 zoff99 2 pnt[1]->flags |= RP_TURN_RESTRICTION;
2100 zoff99 27 }
2101 zoff99 2 #endif
2102     }
2103    
2104     /**
2105     * @brief Adds an item to the route graph
2106     *
2107     * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
2108     * segmented item.
2109     *
2110     * @param this The route graph to add to
2111     * @param item The item to add
2112     * @param profile The vehicle profile currently in use
2113     */
2114 zoff99 27 static void route_process_street_graph(struct route_graph *this,
2115     struct item *item, struct vehicleprofile *profile)
2116 zoff99 2 {
2117     #ifdef AVOID_FLOAT
2118     int len=0;
2119     #else
2120 zoff99 27 double len = 0;
2121 zoff99 2 #endif
2122     int segmented = 0;
2123     struct roadprofile *roadp;
2124 zoff99 27 struct route_graph_point *s_pnt, *e_pnt;
2125     struct coord c, l;
2126 zoff99 2 struct attr attr;
2127     struct route_graph_segment_data data;
2128 zoff99 27 data.flags = 0;
2129     data.offset = 1;
2130     data.maxspeed = -1;
2131     data.item = item;
2132 zoff99 2
2133     roadp = vehicleprofile_get_roadprofile(profile, item->type);
2134 zoff99 27 if (!roadp)
2135     {
2136 zoff99 2 // Don't include any roads that don't have a road profile in our vehicle profile
2137     return;
2138     }
2139    
2140 zoff99 27 if (item_coord_get(item, &l, 1))
2141     {
2142     int *default_flags = item_get_default_flags(item->type);
2143     if (!default_flags)
2144 zoff99 2 return;
2145 zoff99 27 if (item_attr_get(item, attr_flags, &attr))
2146     {
2147 zoff99 2 data.flags = attr.u.num;
2148     if (data.flags & AF_SEGMENTED)
2149     segmented = 1;
2150 zoff99 27 }
2151     else
2152 zoff99 2 data.flags = *default_flags;
2153    
2154 zoff99 27 if (data.flags & AF_SPEED_LIMIT)
2155     {
2156     if (item_attr_get(item, attr_maxspeed, &attr))
2157 zoff99 2 data.maxspeed = attr.u.num;
2158     }
2159 zoff99 27 if (data.flags & AF_DANGEROUS_GOODS)
2160     {
2161     if (item_attr_get(item, attr_vehicle_dangerous_goods, &attr))
2162 zoff99 2 data.dangerous_goods = attr.u.num;
2163 zoff99 27 else
2164 zoff99 2 data.flags &= ~AF_DANGEROUS_GOODS;
2165     }
2166 zoff99 27 if (data.flags & AF_SIZE_OR_WEIGHT_LIMIT)
2167     {
2168 zoff99 2 if (item_attr_get(item, attr_vehicle_width, &attr))
2169 zoff99 27 data.size_weight.width = attr.u.num;
2170 zoff99 2 else
2171 zoff99 27 data.size_weight.width = -1;
2172 zoff99 2 if (item_attr_get(item, attr_vehicle_height, &attr))
2173 zoff99 27 data.size_weight.height = attr.u.num;
2174 zoff99 2 else
2175 zoff99 27 data.size_weight.height = -1;
2176 zoff99 2 if (item_attr_get(item, attr_vehicle_length, &attr))
2177 zoff99 27 data.size_weight.length = attr.u.num;
2178 zoff99 2 else
2179 zoff99 27 data.size_weight.length = -1;
2180 zoff99 2 if (item_attr_get(item, attr_vehicle_weight, &attr))
2181 zoff99 27 data.size_weight.weight = attr.u.num;
2182 zoff99 2 else
2183 zoff99 27 data.size_weight.weight = -1;
2184 zoff99 2 if (item_attr_get(item, attr_vehicle_axle_weight, &attr))
2185 zoff99 27 data.size_weight.axle_weight = attr.u.num;
2186 zoff99 2 else
2187 zoff99 27 data.size_weight.axle_weight = -1;
2188 zoff99 2 }
2189    
2190 zoff99 27 s_pnt = route_graph_add_point(this, &l);
2191     if (!segmented)
2192     {
2193     while (item_coord_get(item, &c, 1))
2194     {
2195     len += transform_distance(map_projection(item->map), &l, &c);
2196     l = c;
2197 zoff99 2 }
2198 zoff99 27 e_pnt = route_graph_add_point(this, &l);
2199 zoff99 2 dbg_assert(len >= 0);
2200 zoff99 27 data.len = len;
2201 zoff99 2 if (!route_graph_segment_is_duplicate(s_pnt, &data))
2202     route_graph_add_segment(this, s_pnt, e_pnt, &data);
2203 zoff99 27 }
2204     else
2205     {
2206     int isseg, rc;
2207 zoff99 2 int sc = 0;
2208 zoff99 27 do
2209     {
2210 zoff99 2 isseg = item_coord_is_node(item);
2211     rc = item_coord_get(item, &c, 1);
2212 zoff99 27 if (rc)
2213     {
2214     len
2215     += transform_distance(map_projection(item->map),
2216     &l, &c);
2217     l = c;
2218     if (isseg)
2219     {
2220     e_pnt = route_graph_add_point(this, &l);
2221     data.len = len;
2222 zoff99 2 if (!route_graph_segment_is_duplicate(s_pnt, &data))
2223     route_graph_add_segment(this, s_pnt, e_pnt, &data);
2224     data.offset++;
2225 zoff99 27 s_pnt = route_graph_add_point(this, &l);
2226 zoff99 2 len = 0;
2227     }
2228     }
2229 zoff99 27 }
2230     while (rc);
2231     e_pnt = route_graph_add_point(this, &l);
2232 zoff99 2 dbg_assert(len >= 0);
2233     sc++;
2234 zoff99 27 data.len = len;
2235 zoff99 2 if (!route_graph_segment_is_duplicate(s_pnt, &data))
2236     route_graph_add_segment(this, s_pnt, e_pnt, &data);
2237     }
2238     }
2239     }
2240    
2241     static struct route_graph_segment *
2242 zoff99 27 route_graph_get_segment(struct route_graph *graph, struct street_data *sd,
2243     struct route_graph_segment *last)
2244 zoff99 2 {
2245 zoff99 27 struct route_graph_point *start = NULL;
2246 zoff99 2 struct route_graph_segment *s;
2247 zoff99 27 int seen = 0;
2248 zoff99 2
2249 zoff99 27 while ((start = route_graph_get_point_next(graph, &sd->c[0], start)))
2250     {
2251     s = start->start;
2252     while (s)
2253     {
2254     if (item_is_equal(sd->item, s->data.item))
2255     {
2256 zoff99 2 if (!last || seen)
2257     return s;
2258     if (last == s)
2259 zoff99 27 seen = 1;
2260 zoff99 2 }
2261 zoff99 27 s = s->start_next;
2262 zoff99 2 }
2263     }
2264     return NULL;
2265     }
2266    
2267     /**
2268     * @brief Calculates the routing costs for each point
2269     *
2270     * This function is the heart of routing. It assigns each point in the route graph a
2271     * cost at which one can reach the destination from this point on. Additionally it assigns
2272     * each point a segment one should follow from this point on to reach the destination at the
2273     * stated costs.
2274     *
2275     * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
2276     * at this algorithm.
2277     */
2278 zoff99 27 static void route_graph_flood(struct route_graph *this, struct route_info *dst,
2279     struct vehicleprofile *profile, struct callback *cb)
2280 zoff99 2 {
2281     struct route_graph_point *p_min;
2282 zoff99 27 struct route_graph_segment *s = NULL;
2283     int min, new, old, val;
2284 zoff99 2 struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
2285    
2286 zoff99 27 heap = fh_makekeyheap();
2287 zoff99 2
2288 zoff99 27 while ((s = route_graph_get_segment(this, dst->street, s)))
2289     {
2290     val = route_value_seg(profile, NULL, s, -1);
2291     if (val != INT_MAX)
2292     {
2293     val = val * (100 - dst->percent) / 100;
2294     s->end->seg = s;
2295     s->end->value = val;
2296     s->end->el = fh_insertkey(heap, s->end->value, s->end);
2297 zoff99 2 }
2298 zoff99 27 val = route_value_seg(profile, NULL, s, 1);
2299     if (val != INT_MAX)
2300     {
2301     val = val * dst->percent / 100;
2302     s->start->seg = s;
2303     s->start->value = val;
2304     s->start->el = fh_insertkey(heap, s->start->value, s->start);
2305 zoff99 2 }
2306     }
2307 zoff99 27 for (;;)
2308     {
2309     p_min = fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
2310     if (!p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
2311 zoff99 2 break;
2312 zoff99 27 min = p_min->value;
2313 zoff99 2 if (debug_route)
2314 zoff99 27 printf("extract p=%p free el=%p min=%d, 0x%x, 0x%x\n", p_min,
2315     p_min->el, min, p_min->c.x, p_min->c.y);
2316     p_min->el = NULL; /* This point is permanently calculated now, we've taken it out of the heap */
2317     s = p_min->start;
2318     while (s)
2319     { /* Iterating all the segments leading away from our point to update the points at their ends */
2320     val = route_value_seg(profile, p_min, s, -1);
2321     if (val != INT_MAX && !item_is_equal(s->data.item,
2322     p_min->seg->data.item))
2323     {
2324     new = min + val;
2325 zoff99 2 if (debug_route)
2326 zoff99 27 printf("begin %d len %d vs %d (0x%x,0x%x)\n", new, val,
2327     s->end->value, s->end->c.x, s->end->c.y);
2328     if (new < s->end->value)
2329     { /* We've found a less costly way to reach the end of s, update it */
2330     s->end->value = new;
2331     s->end->seg = s;
2332     if (!s->end->el)
2333     {
2334 zoff99 2 if (debug_route)
2335 zoff99 27 printf("insert_end p=%p el=%p val=%d ", s->end,
2336     s->end->el, s->end->value);
2337     s->end->el = fh_insertkey(heap, new, s->end);
2338 zoff99 2 if (debug_route)
2339     printf("el new=%p\n", s->end->el);
2340     }
2341 zoff99 27 else
2342     {
2343 zoff99 2 if (debug_route)
2344 zoff99 27 printf("replace_end p=%p el=%p val=%d\n", s->end,
2345     s->end->el, s->end->value);
2346 zoff99 2 fh_replacekey(heap, s->end->el, new);
2347     }
2348     }
2349     if (debug_route)
2350     printf("\n");
2351     }
2352 zoff99 27 s = s->start_next;
2353 zoff99 2 }
2354 zoff99 27 s = p_min->end;
2355     while (s)
2356     { /* Doing the same as above with the segments leading towards our point */
2357     val = route_value_seg(profile, p_min, s, 1);
2358     if (val != INT_MAX && !item_is_equal(s->data.item,
2359     p_min->seg->data.item))
2360     {
2361     new = min + val;
2362 zoff99 2 if (debug_route)
2363 zoff99 27 printf("end %d len %d vs %d (0x%x,0x%x)\n", new, val,
2364     s->start->value, s->start->c.x, s->start->c.y);
2365     if (new < s->start->value)
2366     {
2367     old = s->start->value;
2368     s->start->value = new;
2369     s->start->seg = s;
2370     if (!s->start->el)
2371     {
2372 zoff99 2 if (debug_route)
2373 zoff99 27 printf("insert_start p=%p el=%p val=%d ", s->start,
2374     s->start->el, s->start->value);
2375     s->start->el = fh_insertkey(heap, new, s->start);
2376 zoff99 2 if (debug_route)
2377     printf("el new=%p\n", s->start->el);
2378     }
2379 zoff99 27 else
2380     {
2381 zoff99 2 if (debug_route)
2382 zoff99 27 printf("replace_start p=%p el=%p val=%d\n",
2383     s->start, s->start->el, s->start->value);
2384 zoff99 2 fh_replacekey(heap, s->start->el, new);
2385     }
2386     }
2387     if (debug_route)
2388     printf("\n");
2389     }
2390 zoff99 27 s = s->end_next;
2391 zoff99 2 }
2392     }
2393     fh_deleteheap(heap);
2394     callback_call_0(cb);
2395 zoff99 27 //dbg(1, "return\n");
2396 zoff99 2 }
2397    
2398     /**
2399     * @brief Starts an "offroad" path
2400     *
2401     * This starts a path that is not located on a street. It creates a new route path
2402     * adding only one segment, that leads from pos to dest, and which is not associated with an item.
2403     *
2404     * @param this Not used
2405     * @param pos The starting position for the new path
2406     * @param dst The destination of the new path
2407     * @param dir Not used
2408     * @return The new path
2409     */
2410     static struct route_path *
2411 zoff99 27 route_path_new_offroad(struct route_graph *this, struct route_info *pos,
2412     struct route_info *dst)
2413 zoff99 2 {
2414     struct route_path *ret;
2415    
2416     ret=g_new0(struct route_path, 1);
2417 zoff99 27 ret->in_use = 1;
2418     ret->path_hash = item_hash_new();
2419     route_path_add_line(ret, &pos->c, &dst->c, pos->lenextra + dst->lenextra);
2420     ret->updated = 1;
2421 zoff99 2
2422     return ret;
2423     }
2424    
2425     /**
2426     * @brief Returns a coordinate at a given distance
2427     *
2428     * This function returns the coordinate, where the user will be if he
2429     * follows the current route for a certain distance.
2430     *
2431     * @param this_ The route we're driving upon
2432     * @param dist The distance in meters
2433     * @return The coordinate where the user will be in that distance
2434     */
2435 zoff99 27 struct coord route_get_coord_dist(struct route *this_, int dist)
2436 zoff99 2 {
2437 zoff99 27 int d, l, i, len;
2438     int dx, dy;
2439 zoff99 2 double frac;
2440     struct route_path_segment *cur;
2441     struct coord ret;
2442 zoff99 27 enum projection pro = route_projection(this_);
2443     struct route_info *dst = route_get_dst(this_);
2444 zoff99 2
2445     d = dist;
2446    
2447 zoff99 27 if (!this_->path2 || pro == projection_none)
2448     {
2449 zoff99 2 return this_->pos->c;
2450     }
2451 zoff99 27
2452 zoff99 2 ret = this_->pos->c;
2453     cur = this_->path2->path;
2454 zoff99 27 while (cur)
2455     {
2456     if (cur->data->len < d)
2457     {
2458 zoff99 2 d -= cur->data->len;
2459 zoff99 27 }
2460     else
2461     {
2462     for (i = 0; i < (cur->ncoords - 1); i++)
2463     {
2464 zoff99 2 l = d;
2465 zoff99 27 len = (int) transform_polyline_length(pro, (cur->c + i), 2);
2466 zoff99 2 d -= len;
2467 zoff99 27 if (d <= 0)
2468     {
2469 zoff99 2 // We interpolate a bit here...
2470 zoff99 27 frac = (double) l / len;
2471    
2472 zoff99 2 dx = (cur->c + i + 1)->x - (cur->c + i)->x;
2473     dy = (cur->c + i + 1)->y - (cur->c + i)->y;
2474 zoff99 27
2475 zoff99 2 ret.x = (cur->c + i)->x + (frac * dx);
2476     ret.y = (cur->c + i)->y + (frac * dy);
2477     return ret;
2478     }
2479     }
2480 zoff99 27 return cur->c[(cur->ncoords - 1)];
2481 zoff99 2 }
2482     cur = cur->next;
2483     }
2484    
2485     return dst->c;
2486     }
2487    
2488     /**
2489     * @brief Creates a new route path
2490     *
2491     * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
2492     * make sure to run route_graph_flood() after changing the destination before using this function.
2493     *
2494     * @param this The route graph to create the route from
2495     * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
2496     * @param pos The starting position of the route
2497     * @param dst The destination of the route
2498     * @param preferences The routing preferences
2499     * @return The new route path
2500     */
2501     static struct route_path *
2502 zoff99 27 route_path_new(struct route_graph *this, struct route_path *oldpath,
2503     struct route_info *pos, struct route_info *dst,
2504     struct vehicleprofile *profile)
2505 zoff99 2 {
2506 zoff99 27 struct route_graph_segment *first, *s = NULL, *s1 = NULL, *s2 = NULL;
2507 zoff99 2 struct route_graph_point *start;
2508     struct route_info *posinfo, *dstinfo;
2509 zoff99 27 int segs = 0;
2510     int val1 = INT_MAX, val2 = INT_MAX;
2511     int val, val1_new, val2_new;
2512 zoff99 2 struct route_path *ret;
2513    
2514 zoff99 27 if (!pos->street || !dst->street)
2515     {
2516     dbg(0, "pos or dest not set\n");
2517 zoff99 2 return NULL;
2518     }
2519    
2520 zoff99 27 if (profile->mode == 2 || (profile->mode == 0 && pos->lenextra
2521     + dst->lenextra > transform_distance(
2522     map_projection(pos->street->item.map), &pos->c, &dst->c)))
2523 zoff99 2 return route_path_new_offroad(this, pos, dst);
2524 zoff99 27 while ((s = route_graph_get_segment(this, pos->street, s)))
2525     {
2526     val = route_value_seg(profile, NULL, s, 1);
2527     if (val != INT_MAX && s->end->value != INT_MAX)
2528     {
2529     val = val * (100 - pos->percent) / 100;
2530     val1_new = s->end->value + val;
2531     if (val1_new < val1)
2532     {
2533     val1 = val1_new;
2534     s1 = s;
2535 zoff99 2 }
2536     }
2537 zoff99 27 val = route_value_seg(profile, NULL, s, -1);
2538     if (val != INT_MAX && s->start->value != INT_MAX)
2539     {
2540     val = val * pos->percent / 100;
2541     val2_new = s->start->value + val;
2542     if (val2_new < val2)
2543     {
2544     val2 = val2_new;
2545     s2 = s;
2546 zoff99 2 }
2547     }
2548     }
2549 zoff99 27 if (val1 == INT_MAX && val2 == INT_MAX)
2550     {
2551     dbg(0, "no route found, pos blocked\n");
2552 zoff99 2 return NULL;
2553     }
2554 zoff99 27 if (val1 == val2)
2555     {
2556     val1 = s1->end->value;
2557     val2 = s2->start->value;
2558 zoff99 2 }
2559 zoff99 27 if (val1 < val2)
2560     {
2561     start = s1->start;
2562     s = s1;
2563 zoff99 2 }
2564 zoff99 27 else
2565     {
2566     start = s2->end;
2567     s = s2;
2568     }ret=g_new0(struct route_path, 1);
2569     ret->in_use = 1;
2570     ret->updated = 1;
2571     if (pos->lenextra)
2572 zoff99 2 route_path_add_line(ret, &pos->c, &pos->lp, pos->lenextra);
2573 zoff99 27 ret->path_hash = item_hash_new();
2574     dstinfo = NULL;
2575     posinfo = pos;
2576     first = s;
2577     while (s && !dstinfo)
2578     { /* following start->seg, which indicates the least costly way to reach our destination */
2579 zoff99 2 segs++;
2580     #if 0
2581     printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
2582     #endif
2583 zoff99 27 if (s->start == start)
2584     {
2585     if (item_is_equal(s->data.item, dst->street->item) && (s->end->seg
2586     == s || !posinfo))
2587     dstinfo = dst;
2588     if (!route_path_add_item_from_graph(ret, oldpath, s, 1, posinfo,
2589     dstinfo))
2590     ret->updated = 0;
2591     start = s->end;
2592 zoff99 2 }
2593 zoff99 27 else
2594     {
2595     if (item_is_equal(s->data.item, dst->street->item)
2596     && (s->start->seg == s || !posinfo))
2597     dstinfo = dst;
2598     if (!route_path_add_item_from_graph(ret, oldpath, s, -1, posinfo,
2599     dstinfo))
2600     ret->updated = 0;
2601     start = s->start;
2602     }
2603     posinfo = NULL;
2604     s = start->seg;
2605 zoff99 2 }
2606 zoff99 27 if (dst->lenextra)
2607 zoff99 2 route_path_add_line(ret, &dst->lp, &dst->c, dst->lenextra);
2608 zoff99 27 //dbg(1, "%d segments\n", segs);
2609 zoff99 2 return ret;
2610     }
2611    
2612 zoff99 27 static int route_graph_build_next_map(struct route_graph *rg)
2613 zoff99 2 {
2614 zoff99 27 do
2615     {
2616     rg->m = mapset_next(rg->h, 2);
2617     if (!rg->m)
2618 zoff99 2 return 0;
2619     map_rect_destroy(rg->mr);
2620 zoff99 27 rg->mr = map_rect_new(rg->m, rg->sel);
2621     }
2622     while (!rg->mr);
2623    
2624 zoff99 2 return 1;
2625     }
2626    
2627 zoff99 27 static int is_turn_allowed(struct route_graph_point *p,
2628     struct route_graph_segment *from, struct route_graph_segment *to)
2629 zoff99 2 {
2630 zoff99 27 struct route_graph_point *prev, *next;
2631     struct route_graph_segment *tmp1, *tmp2;
2632 zoff99 2 if (item_is_equal(from->data.item, to->data.item))
2633     return 0;
2634     if (from->start == p)
2635 zoff99 27 prev = from->end;
2636 zoff99 2 else
2637 zoff99 27 prev = from->start;
2638 zoff99 2 if (to->start == p)
2639 zoff99 27 next = to->end;
2640 zoff99 2 else
2641 zoff99 27 next = to->start;
2642     tmp1 = p->end;
2643     while (tmp1)
2644     {
2645     if (tmp1->start->c.x == prev->c.x && tmp1->start->c.y == prev->c.y
2646     && (tmp1->data.item.type == type_street_turn_restriction_no
2647     || tmp1->data.item.type
2648     == type_street_turn_restriction_only))
2649     {
2650     tmp2 = p->start;
2651     //dbg(1, "found %s (0x%x,0x%x) (0x%x,0x%x)-(0x%x,0x%x) %p-%p\n",
2652     // item_to_name(tmp1->data.item.type), tmp1->data.item.id_hi,
2653     // tmp1->data.item.id_lo, tmp1->start->c.x, tmp1->start->c.y,
2654     // tmp1->end->c.x, tmp1->end->c.y, tmp1->start, tmp1->end);
2655     while (tmp2)
2656     {
2657     //dbg(
2658     // 1,
2659     // "compare %s (0x%x,0x%x) (0x%x,0x%x)-(0x%x,0x%x) %p-%p\n",
2660     // item_to_name(tmp2->data.item.type),
2661     // tmp2->data.item.id_hi, tmp2->data.item.id_lo,
2662     // tmp2->start->c.x, tmp2->start->c.y, tmp2->end->c.x,
2663     // tmp2->end->c.y, tmp2->start, tmp2->end);
2664     if (item_is_equal(tmp1->data.item, tmp2->data.item))
2665 zoff99 2 break;
2666 zoff99 27 tmp2 = tmp2->start_next;
2667 zoff99 2 }
2668 zoff99 27 //dbg(1, "tmp2=%p\n", tmp2);
2669     if (tmp2)
2670     {
2671     //dbg(1, "%s tmp2->end=%p next=%p\n",
2672     // item_to_name(tmp1->data.item.type), tmp2->end, next);
2673 zoff99 2 }
2674 zoff99 27 if (tmp1->data.item.type == type_street_turn_restriction_no && tmp2
2675     && tmp2->end->c.x == next->c.x && tmp2->end->c.y
2676     == next->c.y)
2677     {
2678     //dbg(
2679     // 1,
2680     // "from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x not allowed (no)\n",
2681     // prev->c.x, prev->c.y, p->c.x, p->c.y, next->c.x,
2682     // next->c.y);
2683 zoff99 2 return 0;
2684     }
2685 zoff99 27 if (tmp1->data.item.type == type_street_turn_restriction_only
2686     && tmp2 && (tmp2->end->c.x != next->c.x || tmp2->end->c.y
2687     != next->c.y))
2688     {
2689     //dbg(
2690     // 1,
2691     // "from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x not allowed (only)\n",
2692     // prev->c.x, prev->c.y, p->c.x, p->c.y, next->c.x,
2693     // next->c.y);
2694 zoff99 2 return 0;
2695     }
2696     }
2697 zoff99 27 tmp1 = tmp1->end_next;
2698 zoff99 2 }
2699 zoff99 27 //dbg(1, "from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x allowed\n", prev->c.x,
2700     // prev->c.y, p->c.x, p->c.y, next->c.x, next->c.y);
2701 zoff99 2 return 1;
2702     }
2703    
2704 zoff99 27 static void route_graph_clone_segment(struct route_graph *this,
2705     struct route_graph_segment *s, struct route_graph_point *start,
2706     struct route_graph_point *end, int flags)
2707 zoff99 2 {
2708     struct route_graph_segment_data data;
2709 zoff99 27 data.flags = s->data.flags | flags;
2710     data.offset = 1;
2711     data.maxspeed = -1;
2712     data.item = &s->data.item;
2713     data.len = s->data.len + 1;
2714 zoff99 2 if (s->data.flags & AF_SPEED_LIMIT)
2715 zoff99 27 data.maxspeed = RSD_MAXSPEED(&s->data);
2716     if (s->data.flags & AF_SEGMENTED)
2717     data.offset = RSD_OFFSET(&s->data);
2718     //dbg(1, "cloning segment from %p (0x%x,0x%x) to %p (0x%x,0x%x)\n", start,
2719     // start->c.x, start->c.y, end, end->c.x, end->c.y);
2720 zoff99 2 route_graph_add_segment(this, start, end, &data);
2721     }
2722    
2723 zoff99 27 static void route_graph_process_restriction_segment(struct route_graph *this,
2724     struct route_graph_point *p, struct route_graph_segment *s, int dir)
2725 zoff99 2 {
2726     struct route_graph_segment *tmp;
2727     struct route_graph_point *pn;
2728 zoff99 27 struct coord c = p->c;
2729     int dx = 0;
2730     int dy = 0;
2731     c.x += dx;
2732     c.y += dy;
2733     //dbg(1, "From %s %d,%d\n", item_to_name(s->data.item.type), dx, dy);
2734     pn = route_graph_point_new(this, &c);
2735     if (dir > 0)
2736     { /* going away */
2737     //dbg(1, "other 0x%x,0x%x\n", s->end->c.x, s->end->c.y);
2738     if (s->data.flags & AF_ONEWAY)
2739     {
2740     //dbg(1, "Not possible\n");
2741 zoff99 2 return;
2742     }
2743     route_graph_clone_segment(this, s, pn, s->end, AF_ONEWAYREV);
2744 zoff99 27 }
2745     else
2746     { /* coming in */
2747     //dbg(1, "other 0x%x,0x%x\n", s->start->c.x, s->start->c.y);
2748     if (s->data.flags & AF_ONEWAYREV)
2749     {
2750     //dbg(1, "Not possible\n");
2751 zoff99 2 return;
2752     }
2753     route_graph_clone_segment(this, s, s->start, pn, AF_ONEWAY);
2754     }
2755 zoff99 27 tmp = p->start;
2756     while (tmp)
2757     {
2758     if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no
2759     && tmp->data.item.type != type_street_turn_restriction_only
2760     && !(tmp->data.flags & AF_ONEWAYREV) && is_turn_allowed(p, s,
2761     tmp))
2762     {
2763 zoff99 2 route_graph_clone_segment(this, tmp, pn, tmp->end, AF_ONEWAY);
2764 zoff99 27 //dbg(1, "To start %s\n", item_to_name(tmp->data.item.type));
2765 zoff99 2 }
2766 zoff99 27 tmp = tmp->start_next;
2767 zoff99 2 }
2768 zoff99 27 tmp = p->end;
2769     while (tmp)
2770     {
2771     if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no
2772     && tmp->data.item.type != type_street_turn_restriction_only
2773     && !(tmp->data.flags & AF_ONEWAY) && is_turn_allowed(p, s, tmp))
2774     {
2775 zoff99 2 route_graph_clone_segment(this, tmp, tmp->start, pn, AF_ONEWAYREV);
2776 zoff99 27 //dbg(1, "To end %s\n", item_to_name(tmp->data.item.type));
2777 zoff99 2 }
2778 zoff99 27 tmp = tmp->end_next;
2779 zoff99 2 }
2780     }
2781    
2782 zoff99 27 static void route_graph_process_restriction_point(struct route_graph *this,
2783     struct route_graph_point *p)
2784 zoff99 2 {
2785     struct route_graph_segment *tmp;
2786 zoff99 27 tmp = p->start;
2787     //dbg(1, "node 0x%x,0x%x\n", p->c.x, p->c.y);
2788     while (tmp)
2789     {
2790     if (tmp->data.item.type != type_street_turn_restriction_no
2791     && tmp->data.item.type != type_street_turn_restriction_only)
2792 zoff99 2 route_graph_process_restriction_segment(this, p, tmp, 1);
2793 zoff99 27 tmp = tmp->start_next;
2794 zoff99 2 }
2795 zoff99 27 tmp = p->end;
2796     while (tmp)
2797     {
2798     if (tmp->data.item.type != type_street_turn_restriction_no
2799     && tmp->data.item.type != type_street_turn_restriction_only)
2800 zoff99 2 route_graph_process_restriction_segment(this, p, tmp, -1);
2801 zoff99 27 tmp = tmp->end_next;
2802 zoff99 2 }
2803     p->flags |= RP_TURN_RESTRICTION_RESOLVED;
2804     }
2805    
2806 zoff99 27 static void route_graph_process_restrictions(struct route_graph *this)
2807 zoff99 2 {
2808     struct route_graph_point *curr;
2809     int i;
2810 zoff99 27 //dbg(1, "enter\n");
2811     for (i = 0; i < HASH_SIZE; i++)
2812     {
2813     curr = this->hash[i];
2814     while (curr)
2815     {
2816     if (curr->flags & RP_TURN_RESTRICTION)
2817 zoff99 2 route_graph_process_restriction_point(this, curr);
2818 zoff99 27 curr = curr->hash_next;
2819 zoff99 2 }
2820     }
2821     }
2822    
2823 zoff99 27 static void route_graph_build_done(struct route_graph *rg, int cancel)
2824 zoff99 2 {
2825 zoff99 27 //dbg(1, "cancel=%d\n", cancel);
2826 zoff99 2 if (rg->idle_ev)
2827     event_remove_idle(rg->idle_ev);
2828     if (rg->idle_cb)
2829     callback_destroy(rg->idle_cb);
2830     map_rect_destroy(rg->mr);
2831 zoff99 27 mapset_close(rg->h);
2832 zoff99 2 route_free_selection(rg->sel);
2833 zoff99 27 rg->idle_ev = NULL;
2834     rg->idle_cb = NULL;
2835     rg->mr = NULL;
2836     rg->h = NULL;
2837     rg->sel = NULL;
2838     if (!cancel)
2839     {
2840 zoff99 2 route_graph_process_restrictions(rg);
2841     callback_call_0(rg->done_cb);
2842     }
2843 zoff99 27 rg->busy = 0;
2844 zoff99 2 }
2845    
2846 zoff99 27 static void route_graph_build_idle(struct route_graph *rg,
2847     struct vehicleprofile *profile)
2848 zoff99 2 {
2849 zoff99 27 int count = 1000;
2850 zoff99 2 struct item *item;
2851    
2852 zoff99 27 while (count > 0)
2853     {
2854     for (;;)
2855     {
2856     item = map_rect_get_item(rg->mr);
2857 zoff99 2 if (item)
2858     break;
2859 zoff99 27 if (!route_graph_build_next_map(rg))
2860     {
2861 zoff99 2 route_graph_build_done(rg, 0);
2862     return;
2863     }
2864     }
2865     if (item->type == type_traffic_distortion)
2866     route_process_traffic_distortion(rg, item);
2867 zoff99 27 else if (item->type == type_street_turn_restriction_no || item->type
2868     == type_street_turn_restriction_only)
2869 zoff99 2 route_process_turn_restriction(rg, item);
2870     else
2871     route_process_street_graph(rg, item, profile);
2872     count--;
2873     }
2874     }
2875    
2876     /**
2877     * @brief Builds a new route graph from a mapset
2878     *
2879     * This function builds a new route graph from a map. Please note that this function does not
2880     * add any routing information to the route graph - this has to be done via the route_graph_flood()
2881     * function.
2882     *
2883     * The function does not create a graph covering the whole map, but only covering the rectangle
2884     * between c1 and c2.
2885     *
2886     * @param ms The mapset to build the route graph from
2887     * @param c1 Corner 1 of the rectangle to use from the map
2888     * @param c2 Corner 2 of the rectangle to use from the map
2889     * @param done_cb The callback which will be called when graph is complete
2890     * @return The new route graph.
2891     */
2892     static struct route_graph *
2893 zoff99 27 route_graph_build(struct mapset *ms, struct coord *c, int count,
2894     struct callback *done_cb, int async, struct vehicleprofile *profile,
2895     int try_harder)
2896 zoff99 2 {
2897     struct route_graph *ret=g_new0(struct route_graph, 1);
2898    
2899 zoff99 27 //dbg(1, "enter\n");
2900 zoff99 2
2901 zoff99 27 ret->sel = route_calc_selection(c, count, try_harder);
2902     ret->h = mapset_open(ms);
2903     ret->done_cb = done_cb;
2904     ret->busy = 1;
2905     if (route_graph_build_next_map(ret))
2906     {
2907     if (async)
2908     {
2909     ret->idle_cb = callback_new_2(
2910     callback_cast(route_graph_build_idle), ret, profile);
2911     ret->idle_ev = event_add_idle(50, ret->idle_cb);
2912 zoff99 2 }
2913 zoff99 27 }
2914     else
2915 zoff99 2 route_graph_build_done(ret, 0);
2916    
2917     return ret;
2918     }
2919    
2920 zoff99 27 static void route_graph_update_done(struct route *this, struct callback *cb)
2921 zoff99 2 {
2922     route_graph_flood(this->graph, this->current_dst, this->vehicleprofile, cb);
2923     }
2924    
2925     /**
2926     * @brief Updates the route graph
2927     *
2928     * This updates the route graph after settings in the route have changed. It also
2929     * adds routing information afterwards by calling route_graph_flood().
2930     *
2931     * @param this The route to update the graph for
2932     */
2933 zoff99 27 static void route_graph_update(struct route *this, struct callback *cb,
2934     int async)
2935 zoff99 2 {
2936     struct attr route_status;
2937 zoff99 27 struct coord *c = g_alloca(
2938     sizeof(struct coord) * (1 + g_list_length(this->destinations)));
2939     int i = 0;
2940 zoff99 2 GList *tmp;
2941    
2942 zoff99 27 route_status.type = attr_route_status;
2943 zoff99 2 route_graph_destroy(this->graph);
2944 zoff99 27 this->graph = NULL;
2945 zoff99 2 callback_destroy(this->route_graph_done_cb);
2946 zoff99 27 this->route_graph_done_cb = callback_new_2(
2947     callback_cast(route_graph_update_done), this, cb);
2948     route_status.u.num = route_status_building_graph;
2949 zoff99 2 route_set_attr(this, &route_status);
2950 zoff99 27 c[i++] = this->pos->c;
2951     tmp = this->destinations;
2952     while (tmp)
2953     {
2954     struct route_info *dst = tmp->data;
2955     c[i++] = dst->c;
2956     tmp = g_list_next(tmp);
2957 zoff99 2 }
2958 zoff99 27 this->graph = route_graph_build(this->ms, c, i, this->route_graph_done_cb,
2959     async, this->vehicleprofile, this->try_harder);
2960     if (!async)
2961     {
2962     while (this->graph->busy)
2963 zoff99 2 route_graph_build_idle(this->graph, this->vehicleprofile);
2964     }
2965     }
2966    
2967     /**
2968     * @brief Gets street data for an item
2969     *
2970     * @param item The item to get the data for
2971     * @return Street data for the item
2972     */
2973     struct street_data *
2974 zoff99 27 street_get_data(struct item *item)
2975 zoff99 2 {
2976 zoff99 27 int count = 0, *flags;
2977 zoff99 2 struct street_data *ret = NULL, *ret1;
2978     struct attr flags_attr, maxspeed_attr;
2979     const int step = 128;
2980     int c;
2981    
2982 zoff99 27 do
2983     {
2984     ret1 = g_realloc(
2985     ret,
2986     sizeof(struct street_data) + (count + step)
2987     * sizeof(struct coord));
2988     if (!ret1)
2989     {
2990 zoff99 2 if (ret)
2991     g_free(ret);
2992     return NULL;
2993     }
2994     ret = ret1;
2995     c = item_coord_get(item, &ret->c[count], step);
2996     count += c;
2997 zoff99 27 }
2998     while (c && c == step);
2999 zoff99 2
3000 zoff99 27 ret1 = g_realloc(ret,
3001     sizeof(struct street_data) + count * sizeof(struct coord));
3002 zoff99 2 if (ret1)
3003     ret = ret1;
3004 zoff99 27 ret->item = *item;
3005     ret->count = count;
3006     if (item_attr_get(item, attr_flags, &flags_attr))
3007     ret->flags = flags_attr.u.num;
3008     else
3009     {
3010     flags = item_get_default_flags(item->type);
3011 zoff99 2 if (flags)
3012 zoff99 27 ret->flags = *flags;
3013 zoff99 2 else
3014 zoff99 27 ret->flags = 0;
3015 zoff99 2 }
3016    
3017     ret->maxspeed = -1;
3018 zoff99 27 if (ret->flags & AF_SPEED_LIMIT)
3019     {
3020     if (item_attr_get(item, attr_maxspeed, &maxspeed_attr))
3021     {
3022 zoff99 2 ret->maxspeed = maxspeed_attr.u.num;
3023     }
3024     }
3025    
3026     return ret;
3027     }
3028    
3029     /**
3030     * @brief Copies street data
3031     *
3032     * @param orig The street data to copy
3033     * @return The copied street data
3034 zoff99 27 */
3035 zoff99 2 struct street_data *
3036     street_data_dup(struct street_data *orig)
3037     {
3038     struct street_data *ret;
3039 zoff99 27 int size = sizeof(struct street_data) + orig->count * sizeof(struct coord);
3040 zoff99 2
3041 zoff99 27 ret = g_malloc(size);
3042 zoff99 2 memcpy(ret, orig, size);
3043    
3044     return ret;
3045     }
3046    
3047     /**
3048     * @brief Frees street data
3049     *
3050     * @param sd Street data to be freed
3051     */
3052 zoff99 27 void street_data_free(struct street_data *sd)
3053 zoff99 2 {
3054     g_free(sd);
3055     }
3056    
3057     /**
3058     * @brief Finds the nearest street to a given coordinate
3059     *
3060     * @param ms The mapset to search in for the street
3061     * @param pc The coordinate to find a street nearby
3062     * @return The nearest street
3063     */
3064     static struct route_info *
3065 zoff99 27 route_find_nearest_street(struct vehicleprofile *vehicleprofile,
3066     struct mapset *ms, struct pcoord *pc)
3067 zoff99 2 {
3068 zoff99 27 struct route_info *ret = NULL;
3069     int max_dist = 1000;
3070 zoff99 2 struct map_selection *sel;
3071 zoff99 27 int dist, mindist = 0, pos;
3072 zoff99 2 struct mapset_handle *h;
3073     struct map *m;
3074     struct map_rect *mr;
3075     struct item *item;
3076     struct coord lp;
3077     struct street_data *sd;
3078     struct coord c;
3079     struct coord_geo g;
3080    
3081     ret=g_new0(struct route_info, 1);
3082     mindist = INT_MAX;
3083    
3084 zoff99 27 h = mapset_open(ms);
3085     while ((m = mapset_next(h, 2)))
3086     {
3087 zoff99 2 c.x = pc->x;
3088     c.y = pc->y;
3089 zoff99 27 if (map_projection(m) != pc->pro)
3090     {
3091 zoff99 2 transform_to_geo(pc->pro, &c, &g);
3092     transform_from_geo(map_projection(m), &g, &c);
3093     }
3094     sel = route_rect(18, &c, &c, 0, max_dist);
3095     if (!sel)
3096     continue;
3097 zoff99 27 mr = map_rect_new(m, sel);
3098     if (!mr)
3099     {
3100 zoff99 2 map_selection_destroy(sel);
3101     continue;
3102     }
3103 zoff99 27 while ((item = map_rect_get_item(mr)))
3104     {
3105     if (item_get_default_flags(item->type))
3106     {
3107     sd = street_get_data(item);
3108 zoff99 2 if (!sd)
3109     continue;
3110 zoff99 27 dist = transform_distance_polyline_sq(sd->c, sd->count, &c,
3111     &lp, &pos);
3112     if (dist < mindist && ((sd->flags
3113     & vehicleprofile->flags_forward_mask)
3114     == vehicleprofile->flags || (sd->flags
3115     & vehicleprofile->flags_reverse_mask)
3116     == vehicleprofile->flags))
3117     {
3118 zoff99 2 mindist = dist;
3119 zoff99 27 if (ret->street)
3120     {
3121 zoff99 2 street_data_free(ret->street);
3122     }
3123 zoff99 27 ret->c = c;
3124     ret->lp = lp;
3125     ret->pos = pos;
3126     ret->street = sd;
3127     //dbg(1, "dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi,
3128     // item->id_lo, pos);
3129     }
3130     else
3131     {
3132 zoff99 2 street_data_free(sd);
3133     }
3134     }
3135     }
3136     map_selection_destroy(sel);
3137     map_rect_destroy(mr);
3138     }
3139     mapset_close(h);
3140    
3141 zoff99 27 if (!ret->street || mindist > max_dist * max_dist)
3142     {
3143     if (ret->street)
3144     {
3145 zoff99 2 street_data_free(ret->street);
3146 zoff99 27 //dbg(1, "Much too far %d > %d\n", mindist, max_dist);
3147 zoff99 2 }
3148     g_free(ret);
3149     ret = NULL;
3150     }
3151    
3152     return ret;
3153     }
3154    
3155     /**
3156     * @brief Destroys a route_info
3157     *
3158     * @param info The route info to be destroyed
3159     */
3160 zoff99 27 void route_info_free(struct route_info *inf)
3161 zoff99 2 {
3162     if (!inf)
3163     return;
3164     if (inf->street)
3165     street_data_free(inf->street);
3166     g_free(inf);
3167     }
3168    
3169     #include "point.h"
3170    
3171     /**
3172     * @brief Returns street data for a route info
3173     *
3174     * @param rinf The route info to return the street data for
3175     * @return Street data for the route info
3176     */
3177     struct street_data *
3178     route_info_street(struct route_info *rinf)
3179     {
3180     return rinf->street;
3181     }
3182    
3183     #if 0
3184     struct route_crossings *
3185     route_crossings_get(struct route *this, struct coord *c)
3186     {
3187 zoff99 27 struct route_point *pnt;
3188     struct route_segment *seg;
3189     int crossings=0;
3190     struct route_crossings *ret;
3191 zoff99 2
3192 zoff99 27 pnt=route_graph_get_point(this, c);
3193     seg=pnt->start;
3194     while (seg)
3195     {
3196 zoff99 2 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
3197 zoff99 27 crossings++;
3198     seg=seg->start_next;
3199     }
3200     seg=pnt->end;
3201     while (seg)
3202     {
3203 zoff99 2 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
3204 zoff99 27 crossings++;
3205     seg=seg->end_next;
3206     }
3207     ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
3208     ret->count=crossings;
3209     return ret;
3210 zoff99 2 }
3211     #endif
3212    
3213 zoff99 27 struct map_rect_priv
3214     {
3215 zoff99 2 struct route_info_handle *ri;
3216     enum attr_type attr_next;
3217     int pos;
3218     struct map_priv *mpriv;
3219     struct item item;
3220     unsigned int last_coord;
3221     struct route_path *path;
3222 zoff99 27 struct route_path_segment *seg, *seg_next;
3223 zoff99 2 struct route_graph_point *point;
3224     struct route_graph_segment *rseg;
3225     char *str;
3226     int hash_bucket;
3227 zoff99 27 struct coord *coord_sel; /**< Set this to a coordinate if you want to filter for just a single route graph point */
3228 zoff99 2 struct route_graph_point_iterator it;
3229     };
3230    
3231 zoff99 27 static void rm_coord_rewind(void *priv_data)
3232 zoff99 2 {
3233     struct map_rect_priv *mr = priv_data;
3234     mr->last_coord = 0;
3235     }
3236    
3237 zoff99 27 static void rm_attr_rewind(void *priv_data)
3238 zoff99 2 {
3239     struct map_rect_priv *mr = priv_data;
3240     mr->attr_next = attr_street_item;
3241     }
3242    
3243 zoff99 27 static int rm_attr_get(void *priv_data, enum attr_type attr_type,
3244     struct attr *attr)
3245 zoff99 2 {
3246     struct map_rect_priv *mr = priv_data;
3247 zoff99 27 struct route_path_segment *seg = mr->seg;
3248     struct route *route = mr->mpriv->route;
3249 zoff99 2 if (mr->item.type != type_street_route)
3250     return 0;
3251 zoff99 27 attr->type = attr_type;
3252     switch (attr_type)
3253     {
3254 zoff99 2 case attr_any:
3255 zoff99 27 while (mr->attr_next != attr_none)
3256     {
3257 zoff99 2 if (rm_attr_get(priv_data, mr->attr_next, attr))
3258     return 1;
3259     }
3260     return 0;
3261     case attr_maxspeed:
3262     mr->attr_next = attr_street_item;
3263 zoff99 27 if (seg && seg->data->flags & AF_SPEED_LIMIT)
3264     {
3265     attr->u.num = RSD_MAXSPEED(seg->data);
3266 zoff99 2
3267 zoff99 27 }
3268     else
3269     {
3270 zoff99 2 return 0;
3271     }
3272     return 1;
3273     case attr_street_item:
3274 zoff99 27 mr->attr_next = attr_direction;
3275 zoff99 2 if (seg && seg->data->item.map)
3276 zoff99 27 attr->u.item = &seg->data->item;
3277 zoff99 2 else
3278     return 0;
3279     return 1;
3280     case attr_direction:
3281 zoff99 27 mr->attr_next = attr_route;
3282     if (seg)
3283     attr->u.num = seg->direction;
3284 zoff99 2 else
3285     return 0;
3286     return 1;
3287     case attr_route:
3288 zoff99 27 mr->attr_next = attr_length;
3289 zoff99 2 attr->u.route = mr->mpriv->route;
3290     return 1;
3291     case attr_length:
3292 zoff99 27 mr->attr_next = attr_time;
3293 zoff99 2 if (seg)
3294 zoff99 27 attr->u.num = seg->data->len;
3295 zoff99 2 else
3296     return 0;
3297     return 1;
3298     case attr_time:
3299 zoff99 27 mr->attr_next = attr_speed;
3300 zoff99 2 if (seg)
3301 zoff99 27 attr->u.num = route_time_seg(route->vehicleprofile, seg->data,
3302     NULL);
3303 zoff99 2 else
3304     return 0;
3305     return 1;
3306     case attr_speed:
3307 zoff99 27 mr->attr_next = attr_none;
3308 zoff99 2 if (seg)
3309 zoff99 27 attr->u.num = route_seg_speed(route->vehicleprofile, seg->data,
3310     NULL);
3311 zoff99 2 else
3312     return 0;
3313     return 1;
3314     case attr_label:
3315 zoff99 27 mr->attr_next = attr_none;
3316 zoff99 2 return 0;
3317     default:
3318 zoff99 27 mr->attr_next = attr_none;
3319     attr->type = attr_none;
3320 zoff99 2 return 0;
3321     }
3322     return 0;
3323     }
3324    
3325 zoff99 27 static int rm_coord_get(void *priv_data, struct coord *c, int count)
3326 zoff99 2 {
3327     struct map_rect_priv *mr = priv_data;
3328     struct route_path_segment *seg = mr->seg;
3329 zoff99 27 int i, rc = 0;
3330 zoff99 2 struct route *r = mr->mpriv->route;
3331     enum projection pro = route_projection(r);
3332    
3333     if (pro == projection_none)
3334     return 0;
3335 zoff99 27 if (mr->item.type == type_route_start || mr->item.type
3336     == type_route_start_reverse || mr->item.type == type_route_end)
3337     {
3338     if (!count || mr->last_coord)
3339 zoff99 2 return 0;
3340 zoff99 27 mr->last_coord = 1;
3341     if (mr->item.type == type_route_start || mr->item.type
3342     == type_route_start_reverse)
3343     c[0] = r->pos->c;
3344     else
3345     {
3346     c[0] = route_get_dst(r)->c;
3347     }
3348 zoff99 2 return 1;
3349     }
3350 zoff99 27 if (!seg)
3351 zoff99 2 return 0;
3352 zoff99 27 for (i = 0; i < count; i++)
3353     {
3354 zoff99 2 if (mr->last_coord >= seg->ncoords)
3355     break;
3356     if (i >= seg->ncoords)
3357     break;
3358     if (pro != projection_mg)
3359 zoff99 27 transform_from_to(&seg->c[mr->last_coord++], pro, &c[i],
3360     projection_mg);
3361 zoff99 2 else
3362     c[i] = seg->c[mr->last_coord++];
3363     rc++;
3364     }
3365 zoff99 27 //dbg(1, "return %d\n", rc);
3366 zoff99 2 return rc;
3367     }
3368    
3369 zoff99 27 static struct item_methods methods_route_item =
3370     { rm_coord_rewind, rm_coord_get, rm_attr_rewind, rm_attr_get, };
3371 zoff99 2
3372 zoff99 27 static void rp_attr_rewind(void *priv_data)
3373 zoff99 2 {
3374     struct map_rect_priv *mr = priv_data;
3375     mr->attr_next = attr_label;
3376     }
3377    
3378 zoff99 27 static int rp_attr_get(void *priv_data, enum attr_type attr_type,
3379     struct attr *attr)
3380 zoff99 2 {
3381     struct map_rect_priv *mr = priv_data;
3382     struct route_graph_point *p = mr->point;
3383     struct route_graph_segment *seg = mr->rseg;
3384 zoff99 27 struct route *route = mr->mpriv->route;
3385 zoff99 2
3386 zoff99 27 attr->type = attr_type;
3387     switch (attr_type)
3388     {
3389     case attr_any: // works only with rg_points for now
3390     while (mr->attr_next != attr_none)
3391     {
3392     //dbg(0, "querying %s\n", attr_to_name(mr->attr_next));
3393     if (rp_attr_get(priv_data, mr->attr_next, attr))
3394     return 1;
3395     }
3396     return 0;
3397     case attr_maxspeed:
3398     mr->attr_next = attr_label;
3399     if (mr->item.type != type_rg_segment)
3400     return 0;
3401     if (seg && (seg->data.flags & AF_SPEED_LIMIT))
3402     {
3403     attr->type = attr_maxspeed;
3404     attr->u.num = RSD_MAXSPEED(&seg->data);
3405 zoff99 2 return 1;
3406     }
3407 zoff99 27 else
3408     {
3409     return 0;
3410 zoff99 2 }
3411 zoff99 27 case attr_label:
3412     mr->attr_next = attr_street_item;
3413     if (mr->item.type != type_rg_point)
3414     return 0;
3415     attr->type = attr_label;
3416     if (mr->str)
3417     g_free(mr->str);
3418     if (p->value != INT_MAX)
3419     mr->str = g_strdup_printf("%d", p->value);
3420     else
3421     mr->str = g_strdup("-");
3422 zoff99 2 attr->u.str = mr->str;
3423     return 1;
3424 zoff99 27 case attr_street_item:
3425     mr->attr_next = attr_flags;
3426     if (mr->item.type != type_rg_segment)
3427 zoff99 2 return 0;
3428 zoff99 27 if (seg && seg->data.item.map)
3429     attr->u.item = &seg->data.item;
3430     else
3431     return 0;
3432 zoff99 2 return 1;
3433 zoff99 27 case attr_flags:
3434     mr->attr_next = attr_direction;
3435     if (mr->item.type != type_rg_segment)
3436     return 0;
3437     if (seg)
3438     {
3439     attr->u.num = seg->data.flags;
3440     }
3441     else
3442     {
3443     return 0;
3444     }
3445     return 1;
3446     case attr_direction:
3447     mr->attr_next = attr_debug;
3448     // This only works if the map has been opened at a single point, and in that case indicates if the
3449     // segment returned last is connected to this point via its start (1) or its end (-1)
3450     if (!mr->coord_sel || (mr->item.type != type_rg_segment))
3451     return 0;
3452     if (seg->start == mr->point)
3453     {
3454     attr->u.num = 1;
3455     }
3456     else if (seg->end == mr->point)
3457     {
3458     attr->u.num = -1;
3459     }
3460     else
3461     {
3462     return 0;
3463     }
3464     return 1;
3465     case attr_debug:
3466     mr->attr_next = attr_none;
3467     if (mr->str)
3468     g_free(mr->str);
3469     switch (mr->item.type)
3470     {
3471     case type_rg_point:
3472     {
3473     struct route_graph_segment *tmp;
3474     int start = 0;
3475     int end = 0;
3476     tmp = p->start;
3477     while (tmp)
3478     {
3479     start++;
3480     tmp = tmp->start_next;
3481     }
3482     tmp = p->end;
3483     while (tmp)
3484     {
3485     end++;
3486     tmp = tmp->end_next;
3487     }
3488     mr->str = g_strdup_printf("%d %d %p (0x%x,0x%x)", start,
3489     end, p, p->c.x, p->c.y);
3490     attr->u.str = mr->str;
3491     }
3492     return 1;
3493     case type_rg_segment:
3494     if (!seg)
3495     return 0;
3496     mr->str = g_strdup_printf(
3497     "len %d time %d start %p end %p",
3498     seg->data.len,
3499     route_time_seg(route->vehicleprofile, &seg->data,
3500     NULL), seg->start, seg->end);
3501     attr->u.str = mr->str;
3502     return 1;
3503     default:
3504     return 0;
3505     }
3506 zoff99 2 default:
3507 zoff99 27 mr->attr_next = attr_none;
3508     attr->type = attr_none;
3509 zoff99 2 return 0;
3510     }
3511     }
3512    
3513     /**
3514     * @brief Returns the coordinates of a route graph item
3515     *
3516     * @param priv_data The route graph item's private data
3517     * @param c Pointer where to store the coordinates
3518     * @param count How many coordinates to get at a max?
3519     * @return The number of coordinates retrieved
3520     */
3521 zoff99 27 static int rp_coord_get(void *priv_data, struct coord *c, int count)
3522 zoff99 2 {
3523     struct map_rect_priv *mr = priv_data;
3524     struct route_graph_point *p = mr->point;
3525     struct route_graph_segment *seg = mr->rseg;
3526 zoff99 27 int rc = 0, i, dir;
3527 zoff99 2 struct route *r = mr->mpriv->route;
3528     enum projection pro = route_projection(r);
3529    
3530     if (pro == projection_none)
3531     return 0;
3532 zoff99 27 for (i = 0; i < count; i++)
3533     {
3534     if (mr->item.type == type_rg_point)
3535     {
3536 zoff99 2 if (mr->last_coord >= 1)
3537     break;
3538     if (pro != projection_mg)
3539 zoff99 27 transform_from_to(&p->c, pro, &c[i], projection_mg);
3540 zoff99 2 else
3541     c[i] = p->c;
3542 zoff99 27 }
3543     else
3544     {
3545 zoff99 2 if (mr->last_coord >= 2)
3546     break;
3547 zoff99 27 dir = 0;
3548 zoff99 2 if (seg->end->seg == seg)
3549 zoff99 27 dir = 1;
3550 zoff99 2 if (mr->last_coord)
3551 zoff99 27 dir = 1 - dir;
3552     if (dir)
3553     {
3554 zoff99 2 if (pro != projection_mg)
3555 zoff99 27 transform_from_to(&seg->end->c, pro, &c[i], projection_mg);
3556 zoff99 2 else
3557     c[i] = seg->end->c;
3558 zoff99 27 }
3559     else
3560     {
3561 zoff99 2 if (pro != projection_mg)
3562 zoff99 27 transform_from_to(&seg->start->c, pro, &c[i], projection_mg);
3563 zoff99 2 else
3564     c[i] = seg->start->c;
3565     }
3566     }
3567     mr->last_coord++;
3568     rc++;
3569     }
3570     return rc;
3571     }
3572    
3573 zoff99 27 static struct item_methods methods_point_item =
3574     { rm_coord_rewind, rp_coord_get, rp_attr_rewind, rp_attr_get, };
3575 zoff99 2
3576 zoff99 27 static void rp_destroy(struct map_priv *priv)
3577 zoff99 2 {
3578     g_free(priv);
3579     }
3580    
3581 zoff99 27 static void rm_destroy(struct map_priv *priv)
3582 zoff99 2 {
3583     g_free(priv);
3584     }
3585    
3586 zoff99 27 static struct map_rect_priv *
3587 zoff99 2 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
3588     {
3589     struct map_rect_priv * mr;
3590 zoff99 27 //dbg(1, "enter\n");
3591    
3592 zoff99 2 #if 0
3593     if (! route_get_pos(priv->route))
3594 zoff99 27 return NULL;
3595 zoff99 2 if (! route_get_dst(priv->route))
3596 zoff99 27 return NULL;
3597 zoff99 2 #endif
3598 zoff99 27
3599 zoff99 2 #if 0
3600     if (! priv->route->path2)
3601 zoff99 27 return NULL;
3602 zoff99 2 #endif
3603 zoff99 27
3604 zoff99 2 mr=g_new0(struct map_rect_priv, 1);
3605     mr->mpriv = priv;
3606     mr->item.priv_data = mr;
3607     mr->item.type = type_none;
3608     mr->item.meth = &methods_route_item;
3609 zoff99 27 if (priv->route->path2)
3610     {
3611     mr->path = priv->route->path2;
3612     mr->seg_next = mr->path->path;
3613 zoff99 2 mr->path->in_use++;
3614 zoff99 27 }
3615     else
3616     mr->seg_next = NULL;
3617 zoff99 2 return mr;
3618     }
3619    
3620     /**
3621     * @brief Opens a new map rectangle on the route graph's map
3622     *
3623     * This function opens a new map rectangle on the route graph's map.
3624     * The "sel" parameter enables you to only search for a single route graph
3625     * point on this map (or exactly: open a map rectangle that only contains
3626     * this one point). To do this, pass here a single map selection, whose
3627     * c_rect has both coordinates set to the same point. Otherwise this parameter
3628     * has no effect.
3629     *
3630     * @param priv The route graph map's private data
3631     * @param sel Here it's possible to specify a point for which to search. Please read the function's description.
3632     * @return A new map rect's private data
3633     */
3634 zoff99 27 static struct map_rect_priv *
3635 zoff99 2 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
3636     {
3637     struct map_rect_priv * mr;
3638    
3639 zoff99 27 //dbg(1, "enter\n");
3640     if (!priv->route->graph)
3641     return NULL;mr=g_new0(struct map_rect_priv, 1);
3642 zoff99 2 mr->mpriv = priv;
3643     mr->item.priv_data = mr;
3644     mr->item.type = type_rg_point;
3645     mr->item.meth = &methods_point_item;
3646 zoff99 27 if (sel)
3647     {
3648     if ((sel->u.c_rect.lu.x == sel->u.c_rect.rl.x) && (sel->u.c_rect.lu.y
3649     == sel->u.c_rect.rl.y))
3650     {
3651 zoff99 2 mr->coord_sel = g_malloc(sizeof(struct coord));
3652     *(mr->coord_sel) = sel->u.c_rect.lu;
3653     }
3654     }
3655     return mr;
3656     }
3657    
3658 zoff99 27 static void rm_rect_destroy(struct map_rect_priv *mr)
3659 zoff99 2 {
3660     if (mr->str)
3661     g_free(mr->str);
3662 zoff99 27 if (mr->coord_sel)
3663     {
3664 zoff99 2 g_free(mr->coord_sel);
3665     }
3666 zoff99 27 if (mr->path)
3667     {
3668 zoff99 2 mr->path->in_use--;
3669 zoff99 27 if (mr->path->update_required && (mr->path->in_use == 1))
3670     route_path_update_done(mr->mpriv->route,
3671     mr->path->update_required - 1);
3672 zoff99 2 else if (!mr->path->in_use)
3673     g_free(mr->path);
3674     }
3675    
3676     g_free(mr);
3677     }
3678    
3679     static struct item *
3680     rp_get_item(struct map_rect_priv *mr)
3681     {
3682     struct route *r = mr->mpriv->route;
3683     struct route_graph_point *p = mr->point;
3684     struct route_graph_segment *seg = mr->rseg;
3685    
3686 zoff99 27 if (mr->item.type == type_rg_point)
3687     {
3688     if (mr->coord_sel)
3689     {
3690 zoff99 2 // We are supposed to return only the point at one specified coordinate...
3691 zoff99 27 if (!p)
3692     {
3693 zoff99 2 p = route_graph_get_point_last(r->graph, mr->coord_sel);
3694 zoff99 27 if (!p)
3695     {
3696 zoff99 2 mr->point = NULL; // This indicates that no point has been found
3697 zoff99 27 }
3698     else
3699     {
3700 zoff99 2 mr->it = rp_iterator_new(p);
3701     }
3702 zoff99 27 }
3703     else
3704     {
3705 zoff99 2 p = NULL;
3706     }
3707 zoff99 27 }
3708     else
3709     {
3710     if (!p)
3711     {
3712     mr->hash_bucket = 0;
3713 zoff99 2 p = r->graph->hash[0];
3714 zoff99 27 }
3715     else
3716     p = p->hash_next;
3717     while (!p)
3718     {
3719 zoff99 2 mr->hash_bucket++;
3720     if (mr->hash_bucket >= HASH_SIZE)
3721     break;
3722     p = r->graph->hash[mr->hash_bucket];
3723     }
3724     }
3725 zoff99 27 if (p)
3726     {
3727 zoff99 2 mr->point = p;
3728     mr->item.id_lo++;
3729     rm_coord_rewind(mr);
3730     rp_attr_rewind(mr);
3731     return &mr->item;
3732 zoff99 27 }
3733     else
3734 zoff99 2 mr->item.type = type_rg_segment;
3735     }
3736 zoff99 27
3737     if (mr->coord_sel)
3738     {
3739     if (!mr->point)
3740     { // This means that no point has been found
3741 zoff99 2 return NULL;
3742     }
3743     seg = rp_iterator_next(&(mr->it));
3744 zoff99 27 }
3745     else
3746     {
3747 zoff99 2 if (!seg)
3748 zoff99 27 seg = r->graph->route_segments;
3749 zoff99 2 else
3750 zoff99 27 seg = seg->next;
3751 zoff99 2 }
3752 zoff99 27
3753     if (seg)
3754     {
3755 zoff99 2 mr->rseg = seg;
3756     mr->item.id_lo++;
3757     rm_coord_rewind(mr);
3758     rp_attr_rewind(mr);
3759     return &mr->item;
3760     }
3761     return NULL;
3762 zoff99 27
3763 zoff99 2 }
3764    
3765     static struct item *
3766     rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
3767     {
3768 zoff99 27 struct item *ret = NULL;
3769     while (id_lo-- > 0)
3770     ret = rp_get_item(mr);
3771 zoff99 2 return ret;
3772     }
3773    
3774     static struct item *
3775     rm_get_item(struct map_rect_priv *mr)
3776     {
3777 zoff99 27 struct route *route = mr->mpriv->route;
3778     //dbg(1, "enter\n", mr->pos);
3779 zoff99 2
3780 zoff99 27 switch (mr->item.type)
3781     {
3782     case type_none:
3783     if (route->pos && route->pos->street_direction
3784     && route->pos->street_direction != route->pos->dir)
3785     mr->item.type = type_route_start_reverse;
3786     else
3787     mr->item.type = type_route_start;
3788     if (route->pos)
3789     break;
3790     default:
3791     mr->item.type = type_street_route;
3792     mr->seg = mr->seg_next;
3793     if (!mr->seg && mr->path && mr->path->next)
3794     {
3795     struct route_path *p = NULL;
3796     mr->path->in_use--;
3797     if (!mr->path->in_use)
3798     p = mr->path;
3799     mr->path = mr->path->next;
3800     mr->path->in_use++;
3801     mr->seg = mr->path->path;
3802     if (p)
3803     g_free(p);
3804     }
3805     if (mr->seg)
3806     {
3807     mr->seg_next = mr->seg->next;
3808     break;
3809     }
3810     mr->item.type = type_route_end;
3811     // dbg(0,"* set route_end *\n");
3812     if (mr->mpriv->route->destinations)
3813     break;
3814     case type_route_end:
3815     return NULL;
3816 zoff99 2 }
3817     mr->last_coord = 0;
3818     mr->item.id_lo++;
3819     rm_attr_rewind(mr);
3820     return &mr->item;
3821     }
3822    
3823     static struct item *
3824     rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
3825     {
3826 zoff99 27 struct item *ret = NULL;
3827     while (id_lo-- > 0)
3828     ret = rm_get_item(mr);
3829 zoff99 2 return ret;
3830     }
3831    
3832 zoff99 27 static struct map_methods route_meth =
3833     { projection_mg, "utf-8", rm_destroy, rm_rect_new, rm_rect_destroy,
3834     rm_get_item, rm_get_item_byid, NULL, NULL, NULL, };
3835 zoff99 2
3836 zoff99 27 static struct map_methods route_graph_meth =
3837     { projection_mg, "utf-8", rp_destroy, rp_rect_new, rm_rect_destroy,
3838     rp_get_item, rp_get_item_byid, NULL, NULL, NULL, };
3839 zoff99 2
3840     static struct map_priv *
3841     route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
3842     {
3843     struct map_priv *ret;
3844     struct attr *route_attr;
3845    
3846 zoff99 27 route_attr = attr_search(attrs, NULL, attr_route);
3847     if (!route_attr)
3848     return NULL;ret=g_new0(struct map_priv, 1);
3849 zoff99 2 if (graph)
3850 zoff99 27 *meth = route_graph_meth;
3851 zoff99 2 else
3852 zoff99 27 *meth = route_meth;
3853     ret->route = route_attr->u.route;
3854 zoff99 2
3855     return ret;
3856     }
3857    
3858     static struct map_priv *
3859 zoff99 27 route_map_new(struct map_methods *meth, struct attr **attrs,
3860     struct callback_list *cbl)
3861 zoff99 2 {
3862     return route_map_new_helper(meth, attrs, 0);
3863     }
3864    
3865     static struct map_priv *
3866 zoff99 27 route_graph_map_new(struct map_methods *meth, struct attr **attrs,
3867     struct callback_list *cbl)
3868 zoff99 2 {
3869     return route_map_new_helper(meth, attrs, 1);
3870     }
3871    
3872     static struct map *
3873 zoff99 27 route_get_map_helper(struct route *this_, struct map **map, char *type,
3874     char *description)
3875 zoff99 2 {
3876     struct attr *attrs[5];
3877 zoff99 27 struct attr a_type, navigation, data, a_description;
3878     a_type.type = attr_type;
3879     a_type.u.str = type;
3880     navigation.type = attr_route;
3881     navigation.u.route = this_;
3882     data.type = attr_data;
3883     data.u.str = "";
3884     a_description.type = attr_description;
3885     a_description.u.str = description;
3886 zoff99 2
3887 zoff99 27 attrs[0] = &a_type;
3888     attrs[1] = &navigation;
3889     attrs[2] = &data;
3890     attrs[3] = &a_description;
3891     attrs[4] = NULL;
3892 zoff99 2
3893 zoff99 27 if (!*map)
3894     {
3895     *map = map_new(NULL, attrs);
3896 zoff99 2 map_ref(*map);
3897     }
3898 zoff99 27
3899 zoff99 2 return *map;
3900     }
3901    
3902     /**
3903     * @brief Returns a new map containing the route path
3904     *
3905     * This function returns a new map containing the route path.
3906     *
3907     * @important Do not map_destroy() this!
3908     *
3909     * @param this_ The route to get the map of
3910     * @return A new map containing the route path
3911     */
3912     struct map *
3913     route_get_map(struct route *this_)
3914     {
3915 zoff99 27 return route_get_map_helper(this_, &this_->map, "route", "Route");
3916 zoff99 2 }
3917    
3918     /**
3919     * @brief Returns a new map containing the route graph
3920     *
3921     * This function returns a new map containing the route graph.
3922     *
3923     * @important Do not map_destroy() this!
3924     *
3925     * @param this_ The route to get the map of
3926     * @return A new map containing the route graph
3927     */
3928     struct map *
3929     route_get_graph_map(struct route *this_)
3930     {
3931 zoff99 27 return route_get_map_helper(this_, &this_->graph_map, "route_graph",
3932     "Route Graph");
3933 zoff99 2 }
3934    
3935 zoff99 27 void route_set_projection(struct route *this_, enum projection pro)
3936 zoff99 2 {
3937     }
3938    
3939 zoff99 27 int route_set_attr(struct route *this_, struct attr *attr)
3940 zoff99 2 {
3941 zoff99 27 int attr_updated = 0;
3942     switch (attr->type)
3943     {
3944     case attr_route_status:
3945     attr_updated = (this_->route_status != attr->u.num);
3946     this_->route_status = attr->u.num;
3947     // update global route_status notifier
3948     this_->route_status_was_updated = 1;
3949     break;
3950     case attr_destination:
3951     route_set_destination(this_, attr->u.pcoord, 1);
3952     return 1;
3953     case attr_vehicle:
3954     attr_updated = (this_->v != attr->u.vehicle);
3955     this_->v = attr->u.vehicle;
3956     if (attr_updated)
3957     {
3958     struct attr g;
3959     struct pcoord pc;
3960     struct coord c;
3961     if (vehicle_get_attr(this_->v, attr_position_coord_geo, &g,
3962     NULL))
3963     {
3964     pc.pro = projection_mg;
3965     transform_from_geo(projection_mg, g.u.coord_geo, &c);
3966     pc.x = c.x;
3967     pc.y = c.y;
3968     route_set_position(this_, &pc);
3969     }
3970 zoff99 2 }
3971 zoff99 27 break;
3972     default:
3973     dbg(0, "unsupported attribute: %s\n", attr_to_name(attr->type));
3974     return 0;
3975 zoff99 2 }
3976     if (attr_updated)
3977     callback_list_call_attr_2(this_->cbl2, attr->type, this_, attr);
3978     return 1;
3979     }
3980    
3981 zoff99 27 int route_add_attr(struct route *this_, struct attr *attr)
3982