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

Contents of /navit/navit/route.c

Parent Directory Parent Directory | Revision Log Revision Log


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

   
Visit the ZANavi Wiki