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

Contents of /navit/navit/route.c

Parent Directory Parent Directory | Revision Log Revision Log


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

   
Visit the ZANavi Wiki