navit/navit/route.c

   1 /**
   2  * Navit, a modular navigation system.
   3  * Copyright (C) 2005-2008 Navit Team
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * version 2 as published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the
  16  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA  02110-1301, USA.
  18  */
  19
  20 /** @file
  21  * @brief Contains code related to finding a route from a position to a destination
  22  *
  23  * Routing uses segments, points and items. Items are items from the map: Streets, highways, etc.
  24  * Segments represent such items, or parts of it. Generally, a segment is a driveable path. An item
  25  * can be represented by more than one segment - in that case it is "segmented". Each segment has an
  26  * "offset" associated, that indicates at which position in a segmented item this segment is - a
  27  * segment representing a not-segmented item always has the offset 1.
  28  * A point is located at the end of segments, often connecting several segments.
  29  *
  30  * The code in this file will make navit find a route between a position and a destination.
  31  * It accomplishes this by first building a "route graph". This graph contains segments and
  32  * points.
  33  *
  34  * After building this graph in route_graph_build(), the function route_graph_flood() assigns every
  35  * point and segment a "value" which represents the "costs" of traveling from this point to the
  36  * destination. This is done by Dijkstra's algorithm.
  37  *
  38  * When the graph is built a "route path" is created, which is a path in this graph from a given
  39  * position to the destination determined at time of building the graph.
  40  */
  41
  42 #include <stdio.h>
  43 #include <stdlib.h>
  44 #include <string.h>
  45 #if 0
  46 #include <math.h>
  47 #include <assert.h>
  48 #include <unistd.h>
  49 #include <sys/time.h>
  50 #endif
  51 #include <glib.h>
  52 #include "config.h"
  53 #include "debug.h"
  54 #include "profile.h"
  55 #include "coord.h"
  56 #include "projection.h"
  57 #include "item.h"
  58 #include "map.h"
  59 #include "mapset.h"
  60 #include "route.h"
  61 #include "track.h"
  62 #include "point.h"
  63 #include "graphics.h"
  64 #include "transform.h"
  65 #include "plugin.h"
  66 #include "fib.h"
  67 #include "event.h"
  68 #include "callback.h"
  69
  70
  71 struct map_priv {
  72         struct route *route;
  73 };
  74
  75 int debug_route=0;
  76
  77 /**
  78  * @brief A point in the route graph
  79  *
  80  * This represents a point in the route graph. A point usually connects two or more segments,
  81  * but there are also points which don't do that (e.g. at the end of a dead-end).
  82  */
  83 struct route_graph_point {
  84         struct route_graph_point *next;          /**< Linked-list pointer to a list of all route_graph_points */
  85         struct route_graph_point *hash_next; /**< Pointer to a chained hashlist of all route_graph_points with this hash */
  86         struct route_graph_segment *start;       /**< Pointer to a list of segments of which this point is the start. The links
  87                                                                                   *  of this linked-list are in route_graph_segment->start_next.*/
  88         struct route_graph_segment *end;         /**< Pointer to a list of segments of which this pointer is the end. The links
  89                                                                                   *  of this linked-list are in route_graph_segment->end_next. */
  90         struct route_graph_segment *seg;         /**< Pointer to the segment one should use to reach the destination at
  91                                                                                   *  least costs */
  92         struct fibheap_el *el;                           /**< When this point is put on a Fibonacci heap, this is a pointer
  93                                                                                   *  to this point's heap-element */
  94         int value;                                                       /**< The cost at which one can reach the destination from this point on */
  95         struct coord c;                                          /**< Coordinates of this point */
  96 };
  97
  98
  99 /**
 100  * @brief A segment in the route graph or path
 101  *
 102  * This is a segment in the route graph or path. A segment represents a driveable way.
 103  */
 104
 105 struct route_segment_data {
 106         struct item item;                                                       /**< The item (e.g. street) that this segment represents. */
 107         int flags;
 108         int len;                                                                        /**< Length of this segment */
 109         /*NOTE: After a segment, various fields may follow, depending on what flags are set. Order of fields:
 110                                 1.) maxspeed                    Maximum allowed speed on this segment. Present if AF_SPEED_LIMIT is set.
 111                                 2.) offset                              If the item is segmented (i.e. represented by more than one segment), this
 112                                                                                 indicates the position of this segment in the item. Present if AF_SEGMENTED is set.
 113          */
 114 };
 115
 116 #define RSD_OFFSET(x) *((int *)route_segment_data_field_pos((x), attr_offset))
 117 #define RSD_MAXSPEED(x) *((int *)route_segment_data_field_pos((x), attr_maxspeed))
 118
 119
 120
 121 /**
 122  * @brief A segment in the route graph
 123  *
 124  * This is a segment in the route graph. A segment represents a driveable way.
 125  */
 126 struct route_graph_segment {
 127         struct route_graph_segment *next;                       /**< Linked-list pointer to a list of all route_graph_segments */
 128         struct route_graph_segment *start_next;         /**< Pointer to the next element in the list of segments that start at the
 129                                                                                                  *  same point. Start of this list is in route_graph_point->start. */
 130         struct route_graph_segment *end_next;           /**< Pointer to the next element in the list of segments that end at the
 131                                                                                                  *  same point. Start of this list is in route_graph_point->end. */
 132         struct route_graph_point *start;                        /**< Pointer to the point this segment starts at. */
 133         struct route_graph_point *end;                          /**< Pointer to the point this segment ends at. */
 134         struct route_segment_data data;                         /**< The segment data */
 135 };
 136
 137 /**
 138  * @brief A segment in the route path
 139  *
 140  * This is a segment in the route path.
 141  */
 142 struct route_path_segment {
 143         struct route_path_segment *next;        /**< Pointer to the next segment in the path */
 144         struct route_segment_data *data;        /**< The segment data */
 145         int direction;                                          /**< Order in which the coordinates are ordered. >0 means "First
 146                                                                                  *  coordinate of the segment is the first coordinate of the item", <=0
 147                                                                                  *  means reverse. */
 148         unsigned ncoords;                                       /**< How many coordinates does this segment have? */
 149         struct coord c[0];                                      /**< Pointer to the ncoords coordinates of this segment */
 150         /* WARNING: There will be coordinates following here, so do not create new fields after c! */
 151 };
 152
 153 /**
 154  * @brief Usually represents a destination or position
 155  *
 156  * This struct usually represents a destination or position
 157  */
 158 struct route_info {
 159         struct coord c;                  /**< The actual destination / position */
 160         struct coord lp;                 /**< The nearest point on a street to c */
 161         int pos;                                 /**< The position of lp within the coords of the street */
 162         int lenpos;                      /**< Distance between lp and the end of the street */
 163         int lenneg;                      /**< Distance between lp and the start of the street */
 164         int lenextra;                    /**< Distance between lp and c */
 165         int percent;                     /**< ratio of lenneg to lenght of whole street in percent */
 166         struct street_data *street; /**< The street lp is on */
 167 };
 168
 169 /**
 170  * @brief A complete route path
 171  *
 172  * This structure describes a whole routing path
 173  */
 174 struct route_path {
 175         int in_use;                                             /**< The path is in use and can not be updated */
 176         int update_required;                                    /**< The path needs to be updated after it is no longer in use */
 177         int updated;                                            /**< The path has only been updated */
 178         struct route_path_segment *path;                        /**< The first segment in the path, i.e. the segment one should
 179                                                                                                  *  drive in next */
 180         struct route_path_segment *path_last;           /**< The last segment in the path */
 181         /* XXX: path_hash is not necessery now */
 182         struct item_hash *path_hash;                            /**< A hashtable of all the items represented by this route's segements */
 183 };
 184
 185 #define RF_FASTEST      (1<<0)
 186 #define RF_SHORTEST     (1<<1)
 187 #define RF_AVOIDHW      (1<<2)
 188 #define RF_AVOIDPAID    (1<<3)
 189 #define RF_LOCKONROAD   (1<<4)
 190 #define RF_SHOWGRAPH    (1<<5)
 191
 192 /**
 193  * @brief Routing preferences
 194  *
 195  * This struct holds all information about route preferences (fastest, shortest, etc)
 196  */
 197
 198 struct route_preferences {
 199         int mode;                                               /**< 0 = Auto, 1 = On-Road, 2 = Off-Road */
 200         int flags_forward_mask;                                 /**< Flags mask for moving in positive direction */
 201         int flags_reverse_mask;                                 /**< Flags mask for moving in reverse direction */
 202         int flags;                                              /**< Required flags to move through a segment */
 203         int maxspeed_handling;                                  /**< 0 = Always, 1 = Only if lower, 2 = Never */
 204         int speedlist[route_item_last-route_item_first+1];      /**< The speedlist for this route */
 205 };
 206
 207 /**
 208  * @brief A complete route
 209  *
 210  * This struct holds all information about a route.
 211  */
 212 struct route {
 213         struct mapset *ms;                      /**< The mapset this route is built upon */
 214         unsigned flags;
 215         struct route_info *pos;         /**< Current position within this route */
 216         struct route_info *dst;         /**< Destination of the route */
 217
 218         struct route_graph *graph;      /**< Pointer to the route graph */
 219         struct route_path *path2;       /**< Pointer to the route path */
 220         struct map *map;
 221         struct map *graph_map;
 222         struct callback * route_graph_done_cb ; /**< Callback when route graph is done */
 223         struct callback * route_graph_flood_done_cb ; /**< Callback when route graph flooding is done */
 224         struct callback_list *cbl;      /**< Callback list to call when route changes */
 225         int destination_distance;       /**< Distance to the destination at which the destination is considered "reached" */
 226         struct route_preferences preferences; /**< Routing preferences */
 227 };
 228
 229 /**
 230  * @brief A complete route graph
 231  *
 232  * This structure describes a whole routing graph
 233  */
 234 struct route_graph {
 235         int busy;                                       /**< The graph is being built */
 236         struct map_selection *sel;                      /**< The rectangle selection for the graph */
 237         struct mapset_handle *h;                        /**< Handle to the mapset */
 238         struct map *m;                                  /**< Pointer to the currently active map */
 239         struct map_rect *mr;                            /**< Pointer to the currently active map rectangle */
 240         struct callback *idle_cb;                       /**< Idle callback to process the graph */
 241         struct callback *done_cb;                       /**< Callback when graph is done */
 242         struct event_idle *idle_ev;                     /**< The pointer to the idle event */
 243         struct route_graph_point *route_points;         /**< Pointer to the first route_graph_point in the linked list of  all points */
 244         struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */
 245 #define HASH_SIZE 8192
 246         struct route_graph_point *hash[HASH_SIZE];      /**< A hashtable containing all route_graph_points in this graph */
 247 };
 248
 249 #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
 250
 251 /**
 252  * @brief Iterator to iterate through all route graph segments in a route graph point
 253  *
 254  * This structure can be used to iterate through all route graph segments connected to a
 255  * route graph point. Use this with the rp_iterator_* functions.
 256  */
 257 struct route_graph_point_iterator {
 258         struct route_graph_point *p;            /**< The route graph point whose segments should be iterated */
 259         int end;                                                        /**< Indicates if we have finished iterating through the "start" segments */
 260         struct route_graph_segment *next;       /**< The next segment to be returned */
 261 };
 262
 263 static struct route_info * route_find_nearest_street(struct mapset *ms, struct pcoord *c);
 264 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
 265 static void route_graph_update(struct route *this, struct callback *cb);
 266 static void route_graph_build_done(struct route_graph *rg, int cancel);
 267 static struct route_path *route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct route_preferences *pref);
 268 static void route_process_street_graph(struct route_graph *this, struct item *item);
 269 static void route_graph_destroy(struct route_graph *this);
 270 static void route_path_update(struct route *this, int cancel);
 271
 272 /**
 273  * @brief Returns the projection used for this route
 274  *
 275  * @param route The route to return the projection for
 276  * @return The projection used for this route
 277  */
 278 static enum projection route_projection(struct route *route)
 279 {
 280         struct street_data *street;
 281         if (!route->pos && !route->dst)
 282                 return projection_none;
 283         street = route->pos ? route->pos->street : route->dst->street;
 284         if (!street || !street->item.map)
 285                 return projection_none;
 286         return map_projection(street->item.map);
 287 }
 288
 289 /**
 290  * @brief Creates a new graph point iterator
 291  *
 292  * This function creates a new route graph point iterator, that can be used to
 293  * iterate through all segments connected to the point.
 294  *
 295  * @param p The route graph point to create the iterator from
 296  * @return A new iterator.
 297  */
 298 static struct route_graph_point_iterator
 299 rp_iterator_new(struct route_graph_point *p)
 300 {
 301         struct route_graph_point_iterator it;
 302
 303         it.p = p;
 304         if (p->start) {
 305                 it.next = p->start;
 306                 it.end = 0;
 307         } else {
 308                 it.next = p->end;
 309                 it.end = 1;
 310         }
 311
 312         return it;
 313 }
 314
 315 /**
 316  * @brief Gets the next segment connected to a route graph point from an iterator
 317  *
 318  * @param it The route graph point iterator to get the segment from
 319  * @return The next segment or NULL if there are no more segments
 320  */
 321 static struct route_graph_segment
 322 *rp_iterator_next(struct route_graph_point_iterator *it)
 323 {
 324         struct route_graph_segment *ret;
 325
 326         ret = it->next;
 327         if (!ret) {
 328                 return NULL;
 329         }
 330
 331         if (!it->end) {
 332                 if (ret->start_next) {
 333                         it->next = ret->start_next;
 334                 } else {
 335                         it->next = it->p->end;
 336                         it->end = 1;
 337                 }
 338         } else {
 339                 it->next = ret->end_next;
 340         }
 341
 342         return ret;
 343 }
 344
 345 /**
 346  * @brief Checks if the last segment returned from a route_graph_point_iterator comes from the end
 347  *
 348  * @param it The route graph point iterator to be checked
 349  * @return 1 if the last segment returned comes from the end of the route graph point, 0 otherwise
 350  */
 351 static int
 352 rp_iterator_end(struct route_graph_point_iterator *it) {
 353         if (it->end && (it->next != it->p->end)) {
 354                 return 1;
 355         } else {
 356                 return 0;
 357         }
 358 }
 359
 360 /**
 361  * @brief Destroys a route_path
 362  *
 363  * @param this The route_path to be destroyed
 364  */
 365 static void
 366 route_path_destroy(struct route_path *this)
 367 {
 368         struct route_path_segment *c,*n;
 369         if (! this)
 370                 return;
 371         if (this->path_hash) {
 372                 item_hash_destroy(this->path_hash);
 373                 this->path_hash=NULL;
 374         }
 375         c=this->path;
 376         while (c) {
 377                 n=c->next;
 378                 g_free(c);
 379                 c=n;
 380         }
 381         g_free(this);
 382 }
 383
 384 /**
 385  * @brief Creates a completely new route structure
 386  *
 387  * @param attrs Not used
 388  * @return The newly created route
 389  */
 390 struct route *
 391 route_new(struct attr *parent, struct attr **attrs)
 392 {
 393         struct route *this=g_new0(struct route, 1);
 394         struct attr dest_attr;
 395
 396         if (attr_generic_get_attr(attrs, NULL, attr_destination_distance, &dest_attr, NULL)) {
 397                 this->destination_distance = dest_attr.u.num;
 398         } else {
 399                 this->destination_distance = 50; // Default value
 400         }
 401         this->cbl=callback_list_new();
 402         this->preferences.flags_forward_mask=AF_ONEWAYREV|AF_CAR;
 403         this->preferences.flags_reverse_mask=AF_ONEWAY|AF_CAR;
 404         this->preferences.flags=AF_CAR;
 405
 406         return this;
 407 }
 408
 409 /**
 410  * @brief Checks if a segment is part of a roundabout
 411  *
 412  * This function checks if a segment is part of a roundabout.
 413  *
 414  * @param seg The segment to be checked
 415  * @param level How deep to scan the route graph
 416  * @param direction Set this to 1 if we're entering the segment through its end, to 0 otherwise
 417  * @param origin Used internally, set to NULL
 418  * @return 1 If a roundabout was detected, 0 otherwise
 419  */
 420 static int
 421 route_check_roundabout(struct route_graph_segment *seg, int level, int direction, struct route_graph_segment *origin)
 422 {
 423         struct route_graph_point_iterator it,it2;
 424         struct route_graph_segment *cur;
 425         int count=0;
 426
 427         if (!level) {
 428                 return 0;
 429         }
 430         if (!direction && !(seg->data.flags & AF_ONEWAY)) {
 431                 return 0;
 432         }
 433         if (direction && !(seg->data.flags & AF_ONEWAYREV)) {
 434                 return 0;
 435         }
 436
 437         if (!origin) {
 438                 origin = seg;
 439         }
 440
 441         if (!direction) {
 442                 it = rp_iterator_new(seg->end);
 443         } else {
 444                 it = rp_iterator_new(seg->start);
 445         }
 446         it2=it;
 447
 448         while ((cur = rp_iterator_next(&it2)))
 449                 count++;
 450
 451         if (count > 3)
 452                 return 0;
 453         cur = rp_iterator_next(&it);
 454         while (cur) {
 455                 if (cur == seg) {
 456                         cur = rp_iterator_next(&it);
 457                         continue;
 458                 }
 459
 460                 if (cur->item.type != origin->item.type) {
 461                         // This street is of another type, can't be part of the roundabout
 462                         cur = rp_iterator_next(&it);
 463                         continue;
 464                 }
 465
 466                 if (cur == origin) {
 467                         seg->data.flags |= AF_ROUNDABOUT;
 468                         return 1;
 469                 }
 470
 471                 if (route_check_roundabout(cur, (level-1), rp_iterator_end(&it), origin)) {
 472                         seg->data.flags |= AF_ROUNDABOUT;
 473                         return 1;
 474                 }
 475
 476                 cur = rp_iterator_next(&it);
 477         }
 478
 479         return 0;
 480 }
 481
 482 /**
 483  * @brief Sets the mapset of the route passwd
 484  *
 485  * @param this The route to set the mapset for
 486  * @param ms The mapset to set for this route
 487  */
 488 void
 489 route_set_mapset(struct route *this, struct mapset *ms)
 490 {
 491         this->ms=ms;
 492 }
 493
 494 /**
 495  * @brief Returns the mapset of the route passed
 496  *
 497  * @param this The route to get the mapset of
 498  * @return The mapset of the route passed
 499  */
 500 struct mapset *
 501 route_get_mapset(struct route *this)
 502 {
 503         return this->ms;
 504 }
 505
 506 /**
 507  * @brief Returns the current position within the route passed
 508  *
 509  * @param this The route to get the position for
 510  * @return The position within the route passed
 511  */
 512 struct route_info *
 513 route_get_pos(struct route *this)
 514 {
 515         return this->pos;
 516 }
 517
 518 /**
 519  * @brief Returns the destination of the route passed
 520  *
 521  * @param this The route to get the destination for
 522  * @return The destination of the route passed
 523  */
 524 struct route_info *
 525 route_get_dst(struct route *this)
 526 {
 527         return this->dst;
 528 }
 529
 530 /**
 531  * @brief Returns the speedlist of the route passed
 532  *
 533  * @param this The route to get the speedlist for
 534  * @return The speedlist of the route passed
 535  */
 536 int *
 537 route_get_speedlist(struct route *this)
 538 {
 539         return this->preferences.speedlist;
 540 }
 541
 542 /**
 543  * @brief Checks if the path is calculated for the route passed
 544  *
 545  * @param this The route to check
 546  * @return True if the path is calculated, false if not
 547  */
 548 int
 549 route_get_path_set(struct route *this)
 550 {
 551         return this->path2 != NULL;
 552 }
 553
 554 /**
 555  * @brief Sets the driving speed for a certain itemtype
 556  *
 557  * @param this The route to set the speed for
 558  * @param type The itemtype to set the speed for
 559  * @param value The speed that should be set
 560  * @return True on success, false if the itemtype does not exist
 561  */
 562 int
 563 route_set_speed(struct route *this, enum item_type type, int value)
 564 {
 565         if (type < route_item_first || type > route_item_last) {
 566                 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
 567                 return 0;
 568         }
 569         this->preferences.speedlist[type-route_item_first]=value;
 570         return 1;
 571 }
 572
 573 /**
 574  * @brief Checks if the route passed contains a certain item within the route path
 575  *
 576  * This function checks if a certain items exists in the path that navit will guide
 577  * the user to his destination. It does *not* check if this item exists in the route
 578  * graph!
 579  *
 580  * @param this The route to check for this item
 581  * @param item The item to search for
 582  * @return True if the item was found, false if the item was not found or the route was not calculated
 583  */
 584 int
 585 route_contains(struct route *this, struct item *item)
 586 {
 587         if (! this->path2 || !this->path2->path_hash)
 588                 return 0;
 589         return  (int)item_hash_lookup(this->path2->path_hash, item);
 590 }
 591
 592 /**
 593  * @brief Checks if the current position in a route is a certain item
 594  *
 595  * @param this The route to check for this item
 596  * @param item The item to search for
 597  * @return True if the current position is this item, false otherwise
 598  */
 599 int
 600 route_pos_contains(struct route *this, struct item *item)
 601 {
 602         if (! this->pos || !this->pos->street)
 603                 return 0;
 604         return item_is_equal(this->pos->street->item, *item);
 605 }
 606
 607 /**
 608  * @brief Checks if a route has reached its destination
 609  *
 610  * @param this The route to be checked
 611  * @return True if the destination is "reached", false otherwise.
 612  */
 613 int
 614 route_destination_reached(struct route *this)
 615 {
 616         struct street_data *sd = NULL;
 617         enum projection pro;
 618
 619         if (!this->pos)
 620                 return 0;
 621
 622         sd = this->pos->street;
 623
 624         if (!this->path2) {
 625                 return 0;
 626         }
 627
 628         if (!item_is_equal(this->pos->street->item, this->dst->street->item)) {
 629                 return 0;
 630         }
 631
 632         if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= this->dst->lenneg)) { // We would have to drive against the one-way road
 633                 return 0;
 634         }
 635         if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= this->dst->lenpos)) {
 636                 return 0;
 637         }
 638         pro=route_projection(this);
 639         if (pro == projection_none)
 640                 return 0;
 641
 642         if (transform_distance(pro, &this->pos->c, &this->dst->lp) > this->destination_distance) {
 643                 return 0;
 644         }
 645
 646         return 1;
 647 }
 648
 649 static void
 650 route_path_update_done(struct route *this, int new_graph)
 651 {
 652         struct route_path *oldpath=this->path2;
 653         int val;
 654         if (this->path2 && this->path2->in_use) {
 655                 this->path2->update_required=1+new_graph;
 656                 return;
 657         }
 658
 659         this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, &this->preferences);
 660         route_path_destroy(oldpath);
 661         if (this->path2) {
 662                 if (new_graph)
 663                         val=4;
 664                 else
 665                         val=2+!this->path2->updated;
 666         } else
 667                 val=1;
 668         callback_list_call_attr_1(this->cbl, attr_route, (void *)val);
 669 }
 670
 671 /**
 672  * @brief Updates the route graph and the route path if something changed with the route
 673  *
 674  * This will update the route graph and the route path of the route if some of the
 675  * route's settings (destination, position) have changed.
 676  *
 677  * @attention For this to work the route graph has to be destroyed if the route's
 678  * @attention destination is changed somewhere!
 679  *
 680  * @param this The route to update
 681  */
 682 static void
 683 route_path_update(struct route *this, int cancel)
 684 {
 685         dbg(1,"enter %d\n", cancel);
 686         if (! this->pos || ! this->dst) {
 687                 dbg(1,"destroy\n");
 688                 route_path_destroy(this->path2);
 689                 this->path2 = NULL;
 690                 return;
 691         }
 692         if (cancel) {
 693                 route_graph_destroy(this->graph);
 694                 this->graph=NULL;
 695         }
 696         /* the graph is destroyed when setting the destination */
 697         if (this->graph) {
 698                 if (this->graph->busy) {
 699                         dbg(1,"busy building graph\n");
 700                         return;
 701                 }
 702                 // we can try to update
 703                 dbg(1,"try update\n");
 704                 route_path_update_done(this, 0);
 705         } else {
 706                 route_path_destroy(this->path2);
 707                 this->path2 = NULL;
 708         }
 709         if (!this->graph || !this->path2) {
 710                 dbg(1,"rebuild graph\n");
 711                 if (! this->route_graph_flood_done_cb)
 712                         this->route_graph_flood_done_cb=callback_new_2(callback_cast(route_path_update_done), this, 1);
 713                 dbg(1,"route_graph_update\n");
 714                 route_graph_update(this, this->route_graph_flood_done_cb);
 715         }
 716 }
 717
 718 /**
 719  * @brief This will calculate all the distances stored in a route_info
 720  *
 721  * @param ri The route_info to calculate the distances for
 722  * @param pro The projection used for this route
 723  */
 724 static void
 725 route_info_distances(struct route_info *ri, enum projection pro)
 726 {
 727         int npos=ri->pos+1;
 728         struct street_data *sd=ri->street;
 729         /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
 730         ri->lenextra=transform_distance(pro, &ri->lp, &ri->c);
 731         ri->lenneg=transform_polyline_length(pro, sd->c, npos)+transform_distance(pro, &sd->c[ri->pos], &ri->lp);
 732         ri->lenpos=transform_polyline_length(pro, sd->c+npos, sd->count-npos)+transform_distance(pro, &sd->c[npos], &ri->lp);
 733         if (ri->lenneg || ri->lenpos)
 734                 ri->percent=(ri->lenneg*100)/(ri->lenneg+ri->lenpos);
 735         else
 736                 ri->percent=50;
 737 }
 738
 739 /**
 740  * @brief This sets the current position of the route passed
 741  *
 742  * This will set the current position of the route passed to the street that is nearest to the
 743  * passed coordinates. It also automatically updates the route.
 744  *
 745  * @param this The route to set the position of
 746  * @param pos Coordinates to set as position
 747  */
 748 void
 749 route_set_position(struct route *this, struct pcoord *pos)
 750 {
 751         if (this->pos)
 752                 route_info_free(this->pos);
 753         this->pos=NULL;
 754         this->pos=route_find_nearest_street(this->ms, pos);
 755         dbg(1,"this->pos=%p\n", this->pos);
 756         if (! this->pos)
 757                 return;
 758         route_info_distances(this->pos, pos->pro);
 759         route_path_update(this, 0);
 760 }
 761
 762 /**
 763  * @brief Sets a route's current position based on coordinates from tracking
 764  *
 765  * @param this The route to set the current position of
 766  * @param tracking The tracking to get the coordinates from
 767  */
 768 void
 769 route_set_position_from_tracking(struct route *this, struct tracking *tracking)
 770 {
 771         struct pcoord *c;
 772         struct route_info *ret;
 773         struct street_data *sd;
 774
 775         dbg(2,"enter\n");
 776         c=tracking_get_pos(tracking);
 777         ret=g_new0(struct route_info, 1);
 778         if (!ret) {
 779                 printf("%s:Out of memory\n", __FUNCTION__);
 780                 return;
 781         }
 782         if (this->pos)
 783                 route_info_free(this->pos);
 784         this->pos=NULL;
 785         ret->c.x = c->x;
 786         ret->c.y = c->y;
 787         ret->lp.x=c->x;
 788         ret->lp.y=c->y;
 789         ret->pos=tracking_get_segment_pos(tracking);
 790         sd=tracking_get_street_data(tracking);
 791         if (sd) {
 792                 ret->street=street_data_dup(sd);
 793                 route_info_distances(ret, c->pro);
 794         }
 795         dbg(3,"c->x=0x%x, c->y=0x%x pos=%d item=(0x%x,0x%x)\n", c->x, c->y, ret->pos, ret->street->item.id_hi, ret->street->item.id_lo);
 796         dbg(3,"street 0=(0x%x,0x%x) %d=(0x%x,0x%x)\n", ret->street->c[0].x, ret->street->c[0].y, ret->street->count-1, ret->street->c[ret->street->count-1].x, ret->street->c[ret->street->count-1].y);
 797         this->pos=ret;
 798         if (this->dst)
 799                 route_path_update(this, 0);
 800         dbg(2,"ret\n");
 801 }
 802
 803 /* Used for debuging of route_rect, what routing sees */
 804 struct map_selection *route_selection;
 805
 806 /**
 807  * @brief Returns a single map selection
 808  */
 809 struct map_selection *
 810 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
 811 {
 812         int dx,dy,sx=1,sy=1,d,m;
 813         struct map_selection *sel=g_new(struct map_selection, 1);
 814         if (!sel) {
 815                 printf("%s:Out of memory\n", __FUNCTION__);
 816                 return sel;
 817         }
 818         sel->order=order;
 819         sel->range.min=route_item_first;
 820         sel->range.max=route_item_last;
 821         dbg(1,"%p %p\n", c1, c2);
 822         dx=c1->x-c2->x;
 823         dy=c1->y-c2->y;
 824         if (dx < 0) {
 825                 sx=-1;
 826                 sel->u.c_rect.lu.x=c1->x;
 827                 sel->u.c_rect.rl.x=c2->x;
 828         } else {
 829                 sel->u.c_rect.lu.x=c2->x;
 830                 sel->u.c_rect.rl.x=c1->x;
 831         }
 832         if (dy < 0) {
 833                 sy=-1;
 834                 sel->u.c_rect.lu.y=c2->y;
 835                 sel->u.c_rect.rl.y=c1->y;
 836         } else {
 837                 sel->u.c_rect.lu.y=c1->y;
 838                 sel->u.c_rect.rl.y=c2->y;
 839         }
 840         if (dx*sx > dy*sy)
 841                 d=dx*sx;
 842         else
 843                 d=dy*sy;
 844         m=d*rel/100+abs;
 845         sel->u.c_rect.lu.x-=m;
 846         sel->u.c_rect.rl.x+=m;
 847         sel->u.c_rect.lu.y+=m;
 848         sel->u.c_rect.rl.y-=m;
 849         sel->next=NULL;
 850         return sel;
 851 }
 852
 853 /**
 854  * @brief Returns a list of map selections useable to create a route graph
 855  *
 856  * Returns a list of  map selections useable to get a  map rect from which items can be
 857  * retrieved to build a route graph. The selections are a rectangle with
 858  * c1 and c2 as two corners.
 859  *
 860  * @param c1 Corner 1 of the rectangle
 861  * @param c2 Corder 2 of the rectangle
 862  */
 863 static struct map_selection *
 864 route_calc_selection(struct coord *c1, struct coord *c2)
 865 {
 866         struct map_selection *ret,*sel;
 867         sel=route_rect(4, c1, c2, 25, 0);
 868         ret=sel;
 869         sel->next=route_rect(8, c1, c1, 0, 40000);
 870         sel=sel->next;
 871         sel->next=route_rect(18, c1, c1, 0, 10000);
 872         sel=sel->next;
 873         sel->next=route_rect(8, c2, c2, 0, 40000);
 874         sel=sel->next;
 875         sel->next=route_rect(18, c2, c2, 0, 10000);
 876         /* route_selection=ret; */
 877         return ret;
 878 }
 879
 880 /**
 881  * @brief Destroys a list of map selections
 882  *
 883  * @param sel Start of the list to be destroyed
 884  */
 885 static void
 886 route_free_selection(struct map_selection *sel)
 887 {
 888         struct map_selection *next;
 889         while (sel) {
 890                 next=sel->next;
 891                 g_free(sel);
 892                 sel=next;
 893         }
 894 }
 895
 896
 897 /**
 898  * @brief Sets the destination of a route
 899  *
 900  * This sets the destination of a route to the street nearest to the coordinates passed
 901  * and updates the route.
 902  *
 903  * @param this The route to set the destination for
 904  * @param dst Coordinates to set as destination
 905  */
 906 void
 907 route_set_destination(struct route *this, struct pcoord *dst)
 908 {
 909         profile(0,NULL);
 910         if (this->dst)
 911                 route_info_free(this->dst);
 912         this->dst=NULL;
 913         if (dst) {
 914                 this->dst=route_find_nearest_street(this->ms, dst);
 915                 if(this->dst)
 916                         route_info_distances(this->dst, dst->pro);
 917         } else
 918                 callback_list_call_attr_1(this->cbl, attr_route, (void *)0);
 919         profile(1,"find_nearest_street");
 920
 921         /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
 922         route_graph_destroy(this->graph);
 923         this->graph=NULL;
 924         route_path_update(this, 1);
 925         profile(0,"end");
 926 }
 927
 928 /**
 929  * @brief Gets the route_graph_point with the specified coordinates
 930  *
 931  * @param this The route in which to search
 932  * @param c Coordinates to search for
 933  * @return The point at the specified coordinates or NULL if not found
 934  */
 935 static struct route_graph_point *
 936 route_graph_get_point(struct route_graph *this, struct coord *c)
 937 {
 938         struct route_graph_point *p;
 939         int hashval=HASHCOORD(c);
 940         p=this->hash[hashval];
 941         while (p) {
 942                 if (p->c.x == c->x && p->c.y == c->y)
 943                         return p;
 944                 p=p->hash_next;
 945         }
 946         return NULL;
 947 }
 948
 949 /**
 950  * @brief Inserts a point into the route graph at the specified coordinates
 951  *
 952  * This will insert a point into the route graph at the coordinates passed in f.
 953  * Note that the point is not yet linked to any segments.
 954  *
 955  * @param this The route to insert the point into
 956  * @param f The coordinates at which the point should be inserted
 957  * @return The point inserted or NULL on failure
 958  */
 959 static struct route_graph_point *
 960 route_graph_add_point(struct route_graph *this, struct coord *f)
 961 {
 962         int hashval;
 963         struct route_graph_point *p;
 964
 965         p=route_graph_get_point(this,f);
 966         if (!p) {
 967                 hashval=HASHCOORD(f);
 968                 if (debug_route)
 969                         printf("p (0x%x,0x%x)\n", f->x, f->y);
 970                 p=g_new(struct route_graph_point,1);
 971                 if (!p) {
 972                         printf("%s:Out of memory\n", __FUNCTION__);
 973                         return p;
 974                 }
 975                 p->hash_next=this->hash[hashval];
 976                 this->hash[hashval]=p;
 977                 p->next=this->route_points;
 978                 p->el=NULL;
 979                 p->start=NULL;
 980                 p->end=NULL;
 981                 p->seg=NULL;
 982                 p->value=INT_MAX;
 983                 p->c=*f;
 984                 this->route_points=p;
 985         }
 986         return p;
 987 }
 988
 989 /**
 990  * @brief Frees all the memory used for points in the route graph passed
 991  *
 992  * @param this The route graph to delete all points from
 993  */
 994 static void
 995 route_graph_free_points(struct route_graph *this)
 996 {
 997         struct route_graph_point *curr,*next;
 998         curr=this->route_points;
 999         while (curr) {
1000                 next=curr->next;
1001                 g_free(curr);
1002                 curr=next;
1003         }
1004         this->route_points=NULL;
1005         memset(this->hash, 0, sizeof(this->hash));
1006 }
1007
1008 /**
1009  * @brief Returns the position of a certain field appended to a route graph segment
1010  *
1011  * This function returns a pointer to a field that is appended to a route graph
1012  * segment.
1013  *
1014  * @param seg The route graph segment the field is appended to
1015  * @param type Type of the field that should be returned
1016  * @return A pointer to a field of a certain type, or NULL if no such field is present
1017  */
1018 static void *
1019 route_segment_data_field_pos(struct route_segment_data *seg, enum attr_type type)
1020 {
1021         unsigned char *ptr;
1022
1023         ptr = ((unsigned char*)seg) + sizeof(struct route_graph_segment);
1024
1025         if (seg->flags & AF_SPEED_LIMIT) {
1026                 if (type == attr_maxspeed)
1027                         return (void*)ptr;
1028                 ptr += sizeof(int);
1029         }
1030         if (seg->flags & AF_SEGMENTED) {
1031                 if (type == attr_offset)
1032                         return (void*)ptr;
1033                 ptr += sizeof(int);
1034         }
1035         return NULL;
1036 }
1037
1038 /**
1039  * @brief Calculates the size of a route_segment_data struct with given flags
1040  *
1041  * @param flags The flags of the route_segment_data
1042  */
1043
1044 static int
1045 route_segment_data_size(int flags)
1046 {
1047         int ret=sizeof(struct route_segment_data);
1048         if (flags & AF_SPEED_LIMIT)
1049                 ret+=sizeof(int);
1050         if (flags & AF_SEGMENTED)
1051                 ret+=sizeof(int);
1052         return ret;
1053 }
1054
1055
1056 /**
1057  * @brief Inserts a new segment into the route graph
1058  *
1059  * This function performs a check if a segment for the item specified already exists, and inserts
1060  * a new segment representing this item if it does not.
1061  *
1062  * @param this The route graph to insert the segment into
1063  * @param start The graph point which should be connected to the start of this segment
1064  * @param end The graph point which should be connected to the end of this segment
1065  * @param len The length of this segment
1066  * @param item The item that is represented by this segment
1067  * @param flags Flags for this segment
1068  * @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
1069  * @param maxspeed The maximum speed allowed on this segment in km/h. -1 if not known.
1070  */
1071 static void
1072 route_graph_add_segment(struct route_graph *this, struct route_graph_point *start,
1073                         struct route_graph_point *end, int len, struct item *item,
1074                         int flags, int offset, int maxspeed)
1075 {
1076         struct route_graph_segment *s;
1077         int size;
1078         s=start->start;
1079         while (s) {
1080                 if (item_is_equal(*item, s->data.item)) {
1081                         if (flags & AF_SEGMENTED) {
1082                                 if (RSD_OFFSET(&s->data) == offset) {
1083                                         return;
1084                                 }
1085                         } else
1086                                 return;
1087                 }
1088                 s=s->start_next;
1089         }
1090
1091         size = sizeof(struct route_graph_segment)-sizeof(struct route_segment_data)+route_segment_data_size(flags);
1092         s = g_malloc0(size);
1093         if (!s) {
1094                 printf("%s:Out of memory\n", __FUNCTION__);
1095                 return;
1096         }
1097         s->start=start;
1098         s->start_next=start->start;
1099         start->start=s;
1100         s->end=end;
1101         s->end_next=end->end;
1102         end->end=s;
1103         dbg_assert(len >= 0);
1104         s->data.len=len;
1105         s->data.item=*item;
1106         s->data.flags=flags;
1107
1108         if (flags & AF_SPEED_LIMIT)
1109                 RSD_MAXSPEED(&s->data)=maxspeed;
1110         if (flags & AF_SEGMENTED)
1111                 RSD_OFFSET(&s->data)=offset;
1112
1113         s->next=this->route_segments;
1114         this->route_segments=s;
1115         if (debug_route)
1116                 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
1117 }
1118
1119 /**
1120  * @brief Gets all the coordinates of an item
1121  *
1122  * This will get all the coordinates of the item i and return them in c,
1123  * up to max coordinates. Additionally it is possible to limit the coordinates
1124  * returned to all the coordinates of the item between the two coordinates
1125  * start end end.
1126  *
1127  * @important Make shure that whatever c points to has enough memory allocated
1128  * @important to hold max coordinates!
1129  *
1130  * @param i The item to get the coordinates of
1131  * @param c Pointer to memory allocated for holding the coordinates
1132  * @param max Maximum number of coordinates to return
1133  * @param start First coordinate to get
1134  * @param end Last coordinate to get
1135  * @return The number of coordinates returned
1136  */
1137 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
1138                 struct coord *start, struct coord *end)
1139 {
1140         struct map_rect *mr;
1141         struct item *item;
1142         int rc = 0, p = 0;
1143         struct coord c1;
1144         mr=map_rect_new(i->map, NULL);
1145         if (!mr)
1146                 return 0;
1147         item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
1148         if (item) {
1149                 rc = item_coord_get(item, &c1, 1);
1150                 while (rc && (c1.x != start->x || c1.y != start->y)) {
1151                         rc = item_coord_get(item, &c1, 1);
1152                 }
1153                 while (rc && p < max) {
1154                         c[p++] = c1;
1155                         if (c1.x == end->x && c1.y == end->y)
1156                                 break;
1157                         rc = item_coord_get(item, &c1, 1);
1158                 }
1159         }
1160         map_rect_destroy(mr);
1161         return p;
1162 }
1163
1164 /**
1165  * @brief Returns and removes one segment from a path
1166  *
1167  * @param path The path to take the segment from
1168  * @param item The item whose segment to remove
1169  * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
1170  * @return The segment removed
1171  */
1172 static struct route_path_segment *
1173 route_extract_segment_from_path(struct route_path *path, struct item *item,
1174                                                  int offset)
1175 {
1176         int soffset;
1177         struct route_path_segment *sp = NULL, *s;
1178         s = path->path;
1179         while (s) {
1180                 if (item_is_equal(s->data->item,*item)) {
1181                         if (s->data->flags & AF_SEGMENTED)
1182                                 soffset=RSD_OFFSET(s->data);
1183                         else
1184                                 soffset=1;
1185                         if (soffset == offset) {
1186                                 if (sp) {
1187                                         sp->next = s->next;
1188                                         break;
1189                                 } else {
1190                                         path->path = s->next;
1191                                         break;
1192                                 }
1193                         }
1194                 }
1195                 sp = s;
1196                 s = s->next;
1197         }
1198         if (s)
1199                 item_hash_remove(path->path_hash, item);
1200         return s;
1201 }
1202
1203 /**
1204  * @brief Adds a segment and the end of a path
1205  *
1206  * @param this The path to add the segment to
1207  * @param segment The segment to add
1208  */
1209 static void
1210 route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
1211 {
1212         if (!this->path)
1213                 this->path=segment;
1214         if (this->path_last)
1215                 this->path_last->next=segment;
1216         this->path_last=segment;
1217 }
1218
1219 /**
1220  * @brief Adds a two coordinate line to a path
1221  *
1222  * This adds a new line to a path, creating a new segment for it.
1223  *
1224  * @param this The path to add the item to
1225  * @param start coordinate to add to the start of the item. If none should be added, make this NULL.
1226  * @param end coordinate to add to the end of the item. If none should be added, make this NULL.
1227  * @param len The length of the item
1228  */
1229 static void
1230 route_path_add_line(struct route_path *this, struct coord *start, struct coord *end, int len)
1231 {
1232         int ccnt=2;
1233         struct route_path_segment *segment;
1234         int seg_size,seg_dat_size;
1235
1236         seg_size=sizeof(*segment) + sizeof(struct coord) * ccnt;
1237         seg_dat_size=sizeof(struct route_segment_data);
1238         segment=g_malloc0(seg_size + seg_dat_size);
1239         segment->data=(struct route_segment_data *)((char *)segment+seg_size);
1240         segment->ncoords=ccnt;
1241         segment->direction=0;
1242         segment->c[0]=*start;
1243         segment->c[1]=*end;
1244         segment->data->len=len;
1245         route_path_add_segment(this, segment);
1246 }
1247
1248 /**
1249  * @brief Inserts a new item into the path
1250  *
1251  * This function does almost the same as "route_path_add_item()", but identifies
1252  * the item to add by a segment from the route graph. Another difference is that it "copies" the
1253  * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
1254  * be added to the route path, not all segments of the item.
1255  *
1256  * The function can be sped up by passing an old path already containing this segment in oldpath -
1257  * the segment will then be extracted from this old path. Please note that in this case the direction
1258  * parameter has no effect.
1259  *
1260  * @param this The path to add the item to
1261  * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
1262  * @param rgs Segment of the route graph that should be "copied" to the route path
1263  * @param dir Order in which to add the coordinates. See route_path_add_item()
1264  * @param pos  Information about start point if this is the first segment
1265  * @param dst  Information about end point if this is the last segment
1266  */
1267
1268 static int
1269 route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath, struct route_graph_segment *rgs, int dir, struct route_info *pos, struct route_info *dst)
1270 {
1271         struct route_path_segment *segment;
1272         int i,ccnt = 0, extra=0, ret=1;
1273         struct coord *c,*cd,ca[2048];
1274         int offset=1;
1275         int seg_size,seg_dat_size;
1276         if (rgs->data.flags & AF_SEGMENTED)
1277                 offset=RSD_OFFSET(&rgs->data);
1278
1279         dbg(1,"enter (0x%x,0x%x)\n", rgs->data.item.id_hi, rgs->data.item.id_lo);
1280         if (oldpath) {
1281                 ccnt = (int)item_hash_lookup(oldpath->path_hash, &rgs->data.item);
1282                 if (ccnt) {
1283                         segment = route_extract_segment_from_path(oldpath, &rgs->data.item, offset);
1284                         if (segment)
1285                                 goto linkold;
1286                 }
1287         }
1288
1289         if (pos) {
1290                 if (dst) {
1291                         extra=2;
1292                         if (dst->lenneg >= pos->lenneg) {
1293                                 dir=1;
1294                                 ccnt=dst->pos-pos->pos;
1295                                 c=pos->street->c+pos->pos+1;
1296                         } else {
1297                                 dir=-1;
1298                                 ccnt=pos->pos-dst->pos;
1299                                 c=pos->street->c+dst->pos+1;
1300                         }
1301                 } else {
1302                         extra=1;
1303                         dbg(0,"pos dir=%d\n", dir);
1304                         dbg(0,"pos pos=%d\n", pos->pos);
1305                         dbg(0,"pos count=%d\n", pos->street->count);
1306                         if (dir > 0) {
1307                                 c=pos->street->c+pos->pos+1;
1308                                 ccnt=pos->street->count-pos->pos-1;
1309                         } else {
1310                                 c=pos->street->c;
1311                                 ccnt=pos->pos+1;
1312                         }
1313                 }
1314         } else  if (dst) {
1315                 extra=1;
1316                 dbg(0,"dst dir=%d\n", dir);
1317                 dbg(0,"dst pos=%d\n", dst->pos);
1318                 if (dir > 0) {
1319                         c=dst->street->c;
1320                         ccnt=dst->pos+1;
1321                 } else {
1322                         c=dst->street->c+dst->pos+1;
1323                         ccnt=dst->street->count-dst->pos-1;
1324                 }
1325         } else {
1326                 ccnt=get_item_seg_coords(&rgs->data.item, ca, 2047, &rgs->start->c, &rgs->end->c);
1327                 c=ca;
1328         }
1329         seg_size=sizeof(*segment) + sizeof(struct coord) * (ccnt + extra);
1330         seg_dat_size=route_segment_data_size(rgs->data.flags);
1331         segment=g_malloc0(seg_size + seg_dat_size);
1332         segment->data=(struct route_segment_data *)((char *)segment+seg_size);
1333         segment->direction=dir;
1334         cd=segment->c;
1335         if (pos && (c[0].x != pos->lp.x || c[0].y != pos->lp.y))
1336                 *cd++=pos->lp;
1337         if (dir < 0)
1338                 c+=ccnt-1;
1339         for (i = 0 ; i < ccnt ; i++) {
1340                 *cd++=*c;
1341                 c+=dir;
1342         }
1343         segment->ncoords+=ccnt;
1344         if (dst && (cd[-1].x != dst->lp.x || cd[-1].y != dst->lp.y))
1345                 *cd++=dst->lp;
1346         segment->ncoords=cd-segment->c;
1347
1348         /* We check if the route graph segment is part of a roundabout here, because this
1349          * only matters for route graph segments which form parts of the route path */
1350         if (!(rgs->data.flags & AF_ROUNDABOUT)) { // We identified this roundabout earlier
1351                 route_check_roundabout(rgs, 13, (dir < 1), NULL);
1352         }
1353
1354         ret=0;
1355         memcpy(segment->data, &rgs->data, seg_dat_size);
1356
1357 linkold:
1358         segment->data->len=rgs->data.len;
1359         segment->next=NULL;
1360         item_hash_insert(this->path_hash,  &rgs->data.item, (void *)ccnt);
1361
1362         route_path_add_segment(this, segment);
1363
1364         return ret;
1365 }
1366
1367 /**
1368  * @brief Destroys all segments of a route graph
1369  *
1370  * @param this The graph to destroy all segments from
1371  */
1372 static void
1373 route_graph_free_segments(struct route_graph *this)
1374 {
1375         struct route_graph_segment *curr,*next;
1376         curr=this->route_segments;
1377         while (curr) {
1378                 next=curr->next;
1379                 g_free(curr);
1380                 curr=next;
1381         }
1382         this->route_segments=NULL;
1383 }
1384
1385 /**
1386  * @brief Destroys a route graph
1387  *
1388  * @param this The route graph to be destroyed
1389  */
1390 static void
1391 route_graph_destroy(struct route_graph *this)
1392 {
1393         if (this) {
1394                 route_graph_build_done(this, 1);
1395                 route_graph_free_points(this);
1396                 route_graph_free_segments(this);
1397                 g_free(this);
1398         }
1399 }
1400
1401 /**
1402  * @brief Returns the time needed to drive len on item
1403  *
1404  * This function returns the time needed to drive len meters on
1405  * the item passed in item in tenth of seconds.
1406  *
1407  * @param preferences The routing preferences
1408  * @param over The segment which is passed
1409  * @return The time needed to drive len on item in thenth of senconds
1410  */
1411
1412 static int
1413 route_time_seg(struct route_preferences *preferences, struct route_segment_data *over)
1414 {
1415         int pspeed=preferences->speedlist[over->item.type-route_item_first];
1416         int speed=pspeed;
1417         if (preferences->maxspeed_handling != 2 && (over->flags & AF_SPEED_LIMIT)) {
1418                 speed=RSD_MAXSPEED(over);
1419                 if (preferences->maxspeed_handling == 1 && speed > pspeed)
1420                         speed=pspeed;
1421         } else
1422                 speed=preferences->speedlist[over->item.type-route_item_first];
1423         if (!speed)
1424                 return INT_MAX;
1425         return over->len*36/speed;
1426 }
1427
1428 /**
1429  * @brief Returns the "costs" of driving from point from over segment over in direction dir
1430  *
1431  * @param preferences The routing preferences
1432  * @param from The point where we are starting
1433  * @param over The segment we are using
1434  * @param dir The direction of segment which we are driving
1435  * @return The "costs" needed to drive len on item
1436  */
1437
1438 static int
1439 route_value_seg(struct route_preferences *preferences, struct route_graph_point *from, struct route_segment_data *over, int dir)
1440 {
1441 #if 0
1442         dbg(0,"flags 0x%x mask 0x%x flags 0x%x\n", over->flags, dir >= 0 ? preferences->flags_forward_mask : preferences->flags_reverse_mask, preferences->flags);
1443 #endif
1444         if ((over->flags & (dir >= 0 ? preferences->flags_forward_mask : preferences->flags_reverse_mask)) != preferences->flags)
1445                 return INT_MAX;
1446         return route_time_seg(preferences, over);
1447 }
1448
1449 /**
1450  * @brief Adds an item to the route graph
1451  *
1452  * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
1453  * segmented item.
1454  *
1455  * @param this The route graph to add to
1456  * @param item The item to add
1457  */
1458 static void
1459 route_process_street_graph(struct route_graph *this, struct item *item)
1460 {
1461 #ifdef AVOID_FLOAT
1462         int len=0;
1463 #else
1464         double len=0;
1465 #endif
1466         struct route_graph_point *s_pnt,*e_pnt;
1467         struct coord c,l;
1468         struct attr flags_attr, maxspeed_attr;
1469         int flags = 0;
1470         int segmented = 0;
1471         int offset = 1;
1472         int maxspeed = -1;
1473
1474         if (item_coord_get(item, &l, 1)) {
1475                 if (item_attr_get(item, attr_flags, &flags_attr)) {
1476                         flags = flags_attr.u.num;
1477                         if (flags & AF_SEGMENTED)
1478                                 segmented = 1;
1479                 } else
1480                         flags = default_flags[item->type-route_item_first];
1481
1482
1483                 if (flags & AF_SPEED_LIMIT) {
1484                         if (item_attr_get(item, attr_maxspeed, &maxspeed_attr)) {
1485                                 maxspeed = maxspeed_attr.u.num;
1486                         }
1487                 }
1488
1489                 s_pnt=route_graph_add_point(this,&l);
1490                 if (!segmented) {
1491                         while (item_coord_get(item, &c, 1)) {
1492                                 len+=transform_distance(map_projection(item->map), &l, &c);
1493                                 l=c;
1494                         }
1495                         e_pnt=route_graph_add_point(this,&l);
1496                         dbg_assert(len >= 0);
1497                         route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset, maxspeed);
1498                 } else {
1499                         int isseg,rc;
1500                         int sc = 0;
1501                         do {
1502                                 isseg = item_coord_is_node(item);
1503                                 rc = item_coord_get(item, &c, 1);
1504                                 if (rc) {
1505                                         len+=transform_distance(map_projection(item->map), &l, &c);
1506                                         l=c;
1507                                         if (isseg) {
1508                                                 e_pnt=route_graph_add_point(this,&l);
1509                                                 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset, maxspeed);
1510                                                 offset++;
1511                                                 s_pnt=route_graph_add_point(this,&l);
1512                                                 len = 0;
1513                                         }
1514                                 }
1515                         } while(rc);
1516                         e_pnt=route_graph_add_point(this,&l);
1517                         dbg_assert(len >= 0);
1518                         sc++;
1519                         route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset, maxspeed);
1520                 }
1521         }
1522 }
1523
1524 /**
1525  * @brief Compares the costs of reaching the destination from two points on
1526  *
1527  * @important Do not pass anything other than route_graph_points in v1 and v2!
1528  *
1529  * @param v1 Point1
1530  * @param v2 Point2
1531  * @return The additional costs of v1 compared to v2 (may be negative)
1532  */
1533 static int
1534 compare(void *v1, void *v2)
1535 {
1536         struct route_graph_point *p1=v1;
1537         struct route_graph_point *p2=v2;
1538 #if 0
1539         if (debug_route)
1540                 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
1541 #endif
1542         return p1->value-p2->value;
1543 }
1544
1545 static struct route_graph_segment *
1546 route_graph_get_segment(struct route_graph *graph, struct street_data *sd)
1547 {
1548         struct route_graph_point *start=route_graph_get_point(graph, &sd->c[0]);
1549         struct route_graph_segment *s;
1550         s=start->start;
1551         while (s) {
1552                 if (item_is_equal(sd->item, s->data.item))
1553                         return s;
1554                 s=s->start_next;
1555         }
1556         return NULL;
1557 }
1558
1559 /**
1560  * @brief Calculates the routing costs for each point
1561  *
1562  * This function is the heart of routing. It assigns each point in the route graph a
1563  * cost at which one can reach the destination from this point on. Additionally it assigns
1564  * each point a segment one should follow from this point on to reach the destination at the
1565  * stated costs.
1566  *
1567  * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
1568  * at this algorithm.
1569  */
1570 static void
1571 route_graph_flood(struct route_graph *this, struct route_info *dst, struct route_preferences *preferences, struct callback *cb)
1572 {
1573         struct route_graph_point *p_min;
1574         struct route_graph_segment *s;
1575         int min,new,old,val;
1576         struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
1577
1578         heap = fh_makeheap();
1579         fh_setcmp(heap, compare);
1580
1581
1582         s=route_graph_get_segment(this, dst->street);
1583         if (!s) {
1584                 dbg(0,"no segment for destination found\n");
1585                 return;
1586         }
1587         val=route_value_seg(preferences, NULL, &s->data, 1);
1588         if (val != INT_MAX) {
1589                 val=val*(100-dst->percent)/100;
1590                 s->end->seg=s;
1591                 s->end->value=val;
1592                 s->end->el=fh_insert(heap, s->end);
1593         }
1594         val=route_value_seg(preferences, NULL, &s->data, -1);
1595         if (val != INT_MAX) {
1596                 val=val*dst->percent/100;
1597                 s->start->seg=s;
1598                 s->start->value=val;
1599                 s->start->el=fh_insert(heap, s->start);
1600         }
1601         for (;;) {
1602                 p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
1603                 if (! p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
1604                         break;
1605                 min=p_min->value;
1606                 if (debug_route)
1607                         printf("extract p=%p free el=%p min=%d, 0x%x, 0x%x\n", p_min, p_min->el, min, p_min->c.x, p_min->c.y);
1608                 p_min->el=NULL; /* This point is permanently calculated now, we've taken it out of the heap */
1609                 s=p_min->start;
1610                 while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
1611                         val=route_value_seg(preferences, p_min, &s->data, -1);
1612                         if (val != INT_MAX) {
1613                                 new=min+val;
1614                                 if (debug_route)
1615                                         printf("begin %d len %d vs %d (0x%x,0x%x)\n",new,val,s->end->value, s->end->c.x, s->end->c.y);
1616                                 if (new < s->end->value) { /* We've found a less costly way to reach the end of s, update it */
1617                                         s->end->value=new;
1618                                         s->end->seg=s;
1619                                         if (! s->end->el) {
1620                                                 if (debug_route)
1621                                                         printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
1622                                                 s->end->el=fh_insert(heap, s->end);
1623                                                 if (debug_route)
1624                                                         printf("el new=%p\n", s->end->el);
1625                                         }
1626                                         else {
1627                                                 if (debug_route)
1628                                                         printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
1629                                                 fh_replacedata(heap, s->end->el, s->end);
1630                                         }
1631                                 }
1632                                 if (debug_route)
1633                                         printf("\n");
1634                         }
1635                         s=s->start_next;
1636                 }
1637                 s=p_min->end;
1638                 while (s) { /* Doing the same as above with the segments leading towards our point */
1639                         val=route_value_seg(preferences, p_min, &s->data, 1);
1640                         if (val != INT_MAX) {
1641                                 new=min+val;
1642                                 if (debug_route)
1643                                         printf("end %d len %d vs %d (0x%x,0x%x)\n",new,val,s->start->value,s->start->c.x, s->start->c.y);
1644                                 if (new < s->start->value) {
1645                                         old=s->start->value;
1646                                         s->start->value=new;
1647                                         s->start->seg=s;
1648                                         if (! s->start->el) {
1649                                                 if (debug_route)
1650                                                         printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
1651                                                 s->start->el=fh_insert(heap, s->start);
1652                                                 if (debug_route)
1653                                                         printf("el new=%p\n", s->start->el);
1654                                         }
1655                                         else {
1656                                                 if (debug_route)
1657                                                         printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
1658                                                 fh_replacedata(heap, s->start->el, s->start);
1659                                         }
1660                                 }
1661                                 if (debug_route)
1662                                         printf("\n");
1663                         }
1664                         s=s->end_next;
1665                 }
1666         }
1667         fh_deleteheap(heap);
1668         callback_call_0(cb);
1669         dbg(0,"return\n");
1670 }
1671
1672 /**
1673  * @brief Starts an "offroad" path
1674  *
1675  * This starts a path that is not located on a street. It creates a new route path
1676  * adding only one segment, that leads from pos to dest, and which is not associated with an item.
1677  *
1678  * @param this Not used
1679  * @param pos The starting position for the new path
1680  * @param dst The destination of the new path
1681  * @param dir Not used
1682  * @return The new path
1683  */
1684 static struct route_path *
1685 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst)
1686 {
1687         struct route_path *ret;
1688
1689         ret=g_new0(struct route_path, 1);
1690         ret->path_hash=item_hash_new();
1691         route_path_add_line(ret, &pos->c, &dst->c, pos->lenextra+dst->lenextra);
1692         ret->updated=1;
1693
1694         return ret;
1695 }
1696
1697 /**
1698  * @brief Returns a coordinate at a given distance
1699  *
1700  * This function returns the coordinate, where the user will be if he
1701  * follows the current route for a certain distance.
1702  *
1703  * @param this_ The route we're driving upon
1704  * @param dist The distance in meters
1705  * @return The coordinate where the user will be in that distance
1706  */
1707 struct coord
1708 route_get_coord_dist(struct route *this_, int dist)
1709 {
1710         int d,l,i,len;
1711         int dx,dy;
1712         double frac;
1713         struct route_path_segment *cur;
1714         struct coord ret;
1715         enum projection pro=route_projection(this_);
1716
1717         d = dist;
1718
1719         if (!this_->path2 || pro == projection_none) {
1720                 return this_->pos->c;
1721         }
1722
1723         ret = this_->pos->c;
1724         cur = this_->path2->path;
1725         while (cur) {
1726                 if (cur->data->len < d) {
1727                         d -= cur->data->len;
1728                 } else {
1729                         for (i=0; i < (cur->ncoords-1); i++) {
1730                                 l = d;
1731                                 len = (int)transform_polyline_length(pro, (cur->c + i), 2);
1732                                 d -= len;
1733                                 if (d <= 0) {
1734                                         // We interpolate a bit here...
1735                                         frac = (double)l / len;
1736
1737                                         dx = (cur->c + i + 1)->x - (cur->c + i)->x;
1738                                         dy = (cur->c + i + 1)->y - (cur->c + i)->y;
1739
1740                                         ret.x = (cur->c + i)->x + (frac * dx);
1741                                         ret.y = (cur->c + i)->y + (frac * dy);
1742                                         return ret;
1743                                 }
1744                         }
1745                         return cur->c[(cur->ncoords-1)];
1746                 }
1747                 cur = cur->next;
1748         }
1749
1750         return this_->dst->c;
1751 }
1752
1753 /**
1754  * @brief Creates a new route path
1755  *
1756  * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
1757  * make shure to run route_graph_flood() after changing the destination before using this function.
1758  *
1759  * @param this The route graph to create the route from
1760  * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
1761  * @param pos The starting position of the route
1762  * @param dst The destination of the route
1763  * @param preferences The routing preferences
1764  * @return The new route path
1765  */
1766 static struct route_path *
1767 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct route_preferences *preferences)
1768 {
1769         struct route_graph_segment *first,*s=NULL;
1770         struct route_graph_point *start;
1771         struct route_info *posinfo, *dstinfo;
1772         int segs=0;
1773         int val1=INT_MAX,val2=INT_MAX;
1774         int val;
1775         struct route_path *ret;
1776
1777         if (! pos->street || ! dst->street)
1778                 return NULL;
1779
1780         if (preferences->mode == 2 || (preferences->mode == 0 && pos->lenextra + dst->lenextra + pos->lenpos-dst->lenpos > transform_distance(map_projection(pos->street->item.map), &pos->c, &dst->c)))
1781                 return route_path_new_offroad(this, pos, dst);
1782
1783         s=route_graph_get_segment(this, pos->street);
1784         if (!s) {
1785                 dbg(0,"no segment for position found\n");
1786                 return NULL;
1787         }
1788         val=route_value_seg(preferences, NULL, &s->data, -1);
1789         if (val != INT_MAX) {
1790                 val=val*(100-pos->percent)/100;
1791                 val1=s->end->value+val;
1792         }
1793         val=route_value_seg(preferences, NULL, &s->data, 1);
1794         if (val != INT_MAX) {
1795                 val=val*pos->percent/100;
1796                 val2=s->start->value+val;
1797         }
1798         if (val1 == INT_MAX && val2 == INT_MAX) {
1799                 dbg(0,"no route found, pos blocked\n");
1800                 return NULL;
1801         }
1802         if (val1 == val2) {
1803                 val1=s->end->value;
1804                 val2=s->start->value;
1805         }
1806         if (val1 < val2)
1807                 start=s->start;
1808         else
1809                 start=s->end;
1810         ret=g_new0(struct route_path, 1);
1811         ret->updated=1;
1812         if (pos->lenextra)
1813                 route_path_add_line(ret, &pos->c, &pos->lp, pos->lenextra);
1814         ret->path_hash=item_hash_new();
1815         dstinfo=NULL;
1816         posinfo=pos;
1817         first=s;
1818         while (s && !dstinfo) { /* following start->seg, which indicates the least costly way to reach our destination */
1819                 segs++;
1820 #if 0
1821                 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1822 #endif
1823                 if (s->start == start) {
1824                         if (item_is_equal(s->data.item, dst->street->item) && (s->end->seg == s || !posinfo))
1825                                 dstinfo=dst;
1826                         if (!route_path_add_item_from_graph(ret, oldpath, s, 1, posinfo, dstinfo))
1827                                 ret->updated=0;
1828                         start=s->end;
1829                 } else {
1830                         if (item_is_equal(s->data.item, dst->street->item) && (s->start->seg == s || !posinfo))
1831                                 dstinfo=dst;
1832                         if (!route_path_add_item_from_graph(ret, oldpath, s, -1, posinfo, dstinfo))
1833                                 ret->updated=0;
1834                         start=s->start;
1835                 }
1836                 posinfo=NULL;
1837                 s=start->seg;
1838         }
1839         if (dst->lenextra)
1840                 route_path_add_line(ret, &dst->lp, &dst->c, dst->lenextra);
1841         dbg(1, "%d segments\n", segs);
1842         return ret;
1843 }
1844
1845 static int
1846 route_graph_build_next_map(struct route_graph *rg)
1847 {
1848         do {
1849                 rg->m=mapset_next(rg->h, 1);
1850                 if (! rg->m)
1851                         return 0;
1852                 map_rect_destroy(rg->mr);
1853                 rg->mr=map_rect_new(rg->m, rg->sel);
1854         } while (!rg->mr);
1855
1856         return 1;
1857 }
1858
1859 static void
1860 route_graph_build_done(struct route_graph *rg, int cancel)
1861 {
1862         dbg(1,"cancel=%d\n",cancel);
1863         event_remove_idle(rg->idle_ev);
1864         callback_destroy(rg->idle_cb);
1865         map_rect_destroy(rg->mr);
1866         mapset_close(rg->h);
1867         route_free_selection(rg->sel);
1868         rg->idle_ev=NULL;
1869         rg->idle_cb=NULL;
1870         rg->mr=NULL;
1871         rg->h=NULL;
1872         rg->sel=NULL;
1873         if (! cancel)
1874                 callback_call_0(rg->done_cb);
1875         rg->busy=0;
1876 }
1877
1878 static void
1879 route_graph_build_idle(struct route_graph *rg)
1880 {
1881         int count=1000;
1882         struct item *item;
1883
1884         while (count > 0) {
1885                 for (;;) {
1886                         item=map_rect_get_item(rg->mr);
1887                         if (item)
1888                                 break;
1889                         if (!route_graph_build_next_map(rg)) {
1890                                 route_graph_build_done(rg, 0);
1891                                 return;
1892                         }
1893                 }
1894                 if (item->type >= route_item_first && item->type <= route_item_last)
1895                         route_process_street_graph(rg, item);
1896                 count--;
1897         }
1898 }
1899
1900 /**
1901  * @brief Builds a new route graph from a mapset
1902  *
1903  * This function builds a new route graph from a map. Please note that this function does not
1904  * add any routing information to the route graph - this has to be done via the route_graph_flood()
1905  * function.
1906  *
1907  * The function does not create a graph covering the whole map, but only covering the rectangle
1908  * between c1 and c2.
1909  *
1910  * @param ms The mapset to build the route graph from
1911  * @param c1 Corner 1 of the rectangle to use from the map
1912  * @param c2 Corner 2 of the rectangle to use from the map
1913  * @param done_cb The callback which will be called when graph is complete
1914  * @return The new route graph.
1915  */
1916 static struct route_graph *
1917 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2, struct callback *done_cb)
1918 {
1919         struct route_graph *ret=g_new0(struct route_graph, 1);
1920
1921         dbg(1,"enter\n");
1922
1923         ret->sel=route_calc_selection(c1, c2);
1924         ret->h=mapset_open(ms);
1925         ret->done_cb=done_cb;
1926         ret->busy=1;
1927         if (route_graph_build_next_map(ret)) {
1928                 ret->idle_cb=callback_new_1(callback_cast(route_graph_build_idle), ret);
1929                 ret->idle_ev=event_add_idle(50, ret->idle_cb);
1930         } else
1931                 route_graph_build_done(ret, 0);
1932
1933         return ret;
1934 }
1935
1936 static void
1937 route_graph_update_done(struct route *this, struct callback *cb)
1938 {
1939         route_graph_flood(this->graph, this->dst, &this->preferences, cb);
1940 }
1941
1942 /**
1943  * @brief Updates the route graph
1944  *
1945  * This updates the route graph after settings in the route have changed. It also
1946  * adds routing information afterwards by calling route_graph_flood().
1947  *
1948  * @param this The route to update the graph for
1949  */
1950 static void
1951 route_graph_update(struct route *this, struct callback *cb)
1952 {
1953         route_graph_destroy(this->graph);
1954         callback_destroy(this->route_graph_done_cb);
1955         this->route_graph_done_cb=callback_new_2(callback_cast(route_graph_update_done), this, cb);
1956         callback_list_call_attr_1(this->cbl, attr_route, (void *)0);
1957         this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c, this->route_graph_done_cb);
1958 }
1959
1960 /**
1961  * @brief Gets street data for an item
1962  *
1963  * @param item The item to get the data for
1964  * @return Street data for the item
1965  */
1966 struct street_data *
1967 street_get_data (struct item *item)
1968 {
1969         int count=0;
1970         struct street_data *ret = NULL, *ret1;
1971         struct attr flags_attr, maxspeed_attr;
1972         const int step = 128;
1973         int c;
1974
1975         do {
1976                 ret1=g_realloc(ret, sizeof(struct street_data)+(count+step)*sizeof(struct coord));
1977                 if (!ret1) {
1978                         if (ret)
1979                                 g_free(ret);
1980                         return NULL;
1981                 }
1982                 ret = ret1;
1983                 c = item_coord_get(item, &ret->c[count], step);
1984                 count += c;
1985         } while (c && c == step);
1986
1987         ret1=g_realloc(ret, sizeof(struct street_data)+count*sizeof(struct coord));
1988         if (ret1)
1989                 ret = ret1;
1990         ret->item=*item;
1991         ret->count=count;
1992         if (item_attr_get(item, attr_flags, &flags_attr))
1993                 ret->flags=flags_attr.u.num;
1994         else
1995                 ret->flags=0;
1996
1997         ret->maxspeed = -1;
1998         if (ret->flags & AF_SPEED_LIMIT) {
1999                 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr)) {
2000                         ret->maxspeed = maxspeed_attr.u.num;
2001                 }
2002         }
2003
2004         return ret;
2005 }
2006
2007 /**
2008  * @brief Copies street data
2009  *
2010  * @param orig The street data to copy
2011  * @return The copied street data
2012  */
2013 struct street_data *
2014 street_data_dup(struct street_data *orig)
2015 {
2016         struct street_data *ret;
2017         int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
2018
2019         ret=g_malloc(size);
2020         memcpy(ret, orig, size);
2021
2022         return ret;
2023 }
2024
2025 /**
2026  * @brief Frees street data
2027  *
2028  * @param sd Street data to be freed
2029  */
2030 void
2031 street_data_free(struct street_data *sd)
2032 {
2033         g_free(sd);
2034 }
2035
2036 /**
2037  * @brief Finds the nearest street to a given coordinate
2038  *
2039  * @param ms The mapset to search in for the street
2040  * @param pc The coordinate to find a street nearby
2041  * @return The nearest street
2042  */
2043 static struct route_info *
2044 route_find_nearest_street(struct mapset *ms, struct pcoord *pc)
2045 {
2046         struct route_info *ret=NULL;
2047         int max_dist=1000;
2048         struct map_selection *sel;
2049         int dist,mindist=0,pos;
2050         struct mapset_handle *h;
2051         struct map *m;
2052         struct map_rect *mr;
2053         struct item *item;
2054         struct coord lp;
2055         struct street_data *sd;
2056         struct coord c;
2057         struct coord_geo g;
2058
2059         ret=g_new0(struct route_info, 1);
2060         if (!ret) {
2061                 dbg(0,"Out of memory\n");
2062                 return ret;
2063         }
2064         mindist = INT_MAX;
2065
2066         h=mapset_open(ms);
2067         while ((m=mapset_next(h,1))) {
2068                 c.x = pc->x;
2069                 c.y = pc->y;
2070                 if (map_projection(m) != pc->pro) {
2071                         transform_to_geo(pc->pro, &c, &g);
2072                         transform_from_geo(map_projection(m), &g, &c);
2073                 }
2074                 sel = route_rect(18, &c, &c, 0, max_dist);
2075                 if (!sel)
2076                         continue;
2077                 mr=map_rect_new(m, sel);
2078                 if (!mr) {
2079                         map_selection_destroy(sel);
2080                         continue;
2081                 }
2082                 while ((item=map_rect_get_item(mr))) {
2083                         if (item->type >= route_item_first && item->type <= route_item_last) {
2084                                 sd=street_get_data(item);
2085                                 if (!sd)
2086                                         continue;
2087                                 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
2088                                 if (dist < mindist) {
2089                                         mindist = dist;
2090                                         if (ret->street) {
2091                                                 street_data_free(ret->street);
2092                                         }
2093                                         ret->c=c;
2094                                         ret->lp=lp;
2095                                         ret->pos=pos;
2096                                         ret->street=sd;
2097                                         dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
2098                                 } else {
2099                                         street_data_free(sd);
2100                                 }
2101                         }
2102                 }
2103                 map_selection_destroy(sel);
2104                 map_rect_destroy(mr);
2105         }
2106         mapset_close(h);
2107
2108         if (!ret->street || mindist > max_dist*max_dist) {
2109                 if (ret->street) {
2110                         street_data_free(ret->street);
2111                         dbg(1,"Much too far %d > %d\n", mindist, max_dist);
2112                 }
2113                 g_free(ret);
2114                 ret = NULL;
2115         }
2116
2117         return ret;
2118 }
2119
2120 /**
2121  * @brief Destroys a route_info
2122  *
2123  * @param info The route info to be destroyed
2124  */
2125 void
2126 route_info_free(struct route_info *inf)
2127 {
2128         if (inf->street)
2129                 street_data_free(inf->street);
2130         g_free(inf);
2131 }
2132
2133
2134 #include "point.h"
2135
2136 /**
2137  * @brief Returns street data for a route info
2138  *
2139  * @param rinf The route info to return the street data for
2140  * @return Street data for the route info
2141  */
2142 struct street_data *
2143 route_info_street(struct route_info *rinf)
2144 {
2145         return rinf->street;
2146 }
2147
2148 #if 0
2149 struct route_crossings *
2150 route_crossings_get(struct route *this, struct coord *c)
2151 {
2152       struct route_point *pnt;
2153       struct route_segment *seg;
2154       int crossings=0;
2155       struct route_crossings *ret;
2156
2157        pnt=route_graph_get_point(this, c);
2158        seg=pnt->start;
2159        while (seg) {
2160                 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
2161                crossings++;
2162                seg=seg->start_next;
2163        }
2164        seg=pnt->end;
2165        while (seg) {
2166                 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
2167                crossings++;
2168                seg=seg->end_next;
2169        }
2170        ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
2171        ret->count=crossings;
2172        return ret;
2173 }
2174 #endif
2175
2176
2177 struct map_rect_priv {
2178         struct route_info_handle *ri;
2179         enum attr_type attr_next;
2180         int pos;
2181         struct map_priv *mpriv;
2182         struct item item;
2183         int length;
2184         unsigned int last_coord;
2185         struct route_path *path;
2186         struct route_path_segment *seg,*seg_next;
2187         struct route_graph_point *point;
2188         struct route_graph_segment *rseg;
2189         char *str;
2190         struct coord *coord_sel;        /**< Set this to a coordinate if you want to filter for just a single route graph point */
2191         struct route_graph_point_iterator it;
2192 };
2193
2194 static void
2195 rm_coord_rewind(void *priv_data)
2196 {
2197         struct map_rect_priv *mr = priv_data;
2198         mr->last_coord = 0;
2199 }
2200
2201 static void
2202 rm_attr_rewind(void *priv_data)
2203 {
2204         struct map_rect_priv *mr = priv_data;
2205         mr->attr_next = attr_street_item;
2206 }
2207
2208 static int
2209 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2210 {
2211         struct map_rect_priv *mr = priv_data;
2212         struct route_path_segment *seg=mr->seg;
2213         struct route *route=mr->mpriv->route;
2214         if (mr->item.type != type_street_route)
2215                 return 0;
2216         attr->type=attr_type;
2217         switch (attr_type) {
2218                 case attr_any:
2219                         while (mr->attr_next != attr_none) {
2220                                 if (rm_attr_get(priv_data, mr->attr_next, attr))
2221                                         return 1;
2222                         }
2223                         return 0;
2224                 case attr_maxspeed:
2225                         mr->attr_next = attr_street_item;
2226                         if (seg && seg->data->flags && AF_SPEED_LIMIT) {
2227                                 attr->u.num=RSD_MAXSPEED(seg->data);
2228
2229                         } else {
2230                                 return 0;
2231                         }
2232                         return 1;
2233                 case attr_street_item:
2234                         mr->attr_next=attr_direction;
2235                         if (seg && seg->data->item.map)
2236                                 attr->u.item=&seg->data->item;
2237                         else
2238                                 return 0;
2239                         return 1;
2240                 case attr_direction:
2241                         mr->attr_next=attr_route;
2242                         if (seg)
2243                                 attr->u.num=seg->direction;
2244                         else
2245                                 return 0;
2246                         return 1;
2247                 case attr_route:
2248                         mr->attr_next=attr_length;
2249                         attr->u.route = mr->mpriv->route;
2250                         return 1;
2251                 case attr_length:
2252                         if (seg)
2253                                 attr->u.num=seg->data->len;
2254                         else
2255                                 attr->u.num=mr->length;
2256                         mr->attr_next=attr_time;
2257                         return 1;
2258                 case attr_time:
2259                         mr->attr_next=attr_none;
2260                         if (seg) {
2261                                 attr->u.num=route_time_seg(&route->preferences, seg->data);
2262                         } else
2263                                 return 0;
2264                         return 1;
2265                 case attr_label:
2266                         mr->attr_next=attr_none;
2267                         return 0;
2268                 default:
2269                         mr->attr_next=attr_none;
2270                         attr->type=attr_none;
2271                         return 0;
2272         }
2273         return 0;
2274 }
2275
2276 static int
2277 rm_coord_get(void *priv_data, struct coord *c, int count)
2278 {
2279         struct map_rect_priv *mr = priv_data;
2280         struct route_path_segment *seg = mr->seg;
2281         int i,rc=0;
2282         struct route *r = mr->mpriv->route;
2283         enum projection pro = route_projection(r);
2284
2285         if (pro == projection_none)
2286                 return 0;
2287         if (mr->item.type == type_route_start || mr->item.type == type_route_end) {
2288                 if (! count || mr->last_coord)
2289                         return 0;
2290                 mr->last_coord=1;
2291                 if (mr->item.type == type_route_start)
2292                         c[0]=r->pos->c;
2293                 else
2294                         c[0]=r->dst->c;
2295                 return 1;
2296         }
2297         if (! seg)
2298                 return 0;
2299         for (i=0; i < count; i++) {
2300                 if (mr->last_coord >= seg->ncoords)
2301                         break;
2302                 if (i >= seg->ncoords)
2303                         break;
2304                 if (pro != projection_mg)
2305                         transform_from_to(&seg->c[mr->last_coord++], pro,
2306                                 &c[i],projection_mg);
2307                 else
2308                         c[i] = seg->c[mr->last_coord++];
2309                 rc++;
2310         }
2311         dbg(1,"return %d\n",rc);
2312         return rc;
2313 }
2314
2315 static struct item_methods methods_route_item = {
2316         rm_coord_rewind,
2317         rm_coord_get,
2318         rm_attr_rewind,
2319         rm_attr_get,
2320 };
2321
2322 static void
2323 rp_attr_rewind(void *priv_data)
2324 {
2325         struct map_rect_priv *mr = priv_data;
2326         mr->attr_next = attr_label;
2327 }
2328
2329 static int
2330 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2331 {
2332         struct map_rect_priv *mr = priv_data;
2333         struct route_graph_point *p = mr->point;
2334         struct route_graph_segment *seg = mr->rseg;
2335         switch (attr_type) {
2336         case attr_any: // works only with rg_points for now
2337                 if (mr->item.type != type_rg_point)
2338                         return 0;
2339                 while (mr->attr_next != attr_none) {
2340                         if (rp_attr_get(priv_data, mr->attr_next, attr))
2341                                 return 1;
2342                 }
2343                 return 0;
2344         case attr_maxspeed:
2345                 mr->attr_next = attr_label;
2346                 if (mr->item.type != type_rg_segment)
2347                         return 0;
2348                 if (seg && (seg->data.flags & AF_SPEED_LIMIT)) {
2349                         attr->type = attr_maxspeed;
2350                         attr->u.num=RSD_MAXSPEED(&seg->data);
2351                         return 1;
2352                 } else {
2353                         return 0;
2354                 }
2355         case attr_label:
2356                 if (mr->item.type != type_rg_point)
2357                         return 0;
2358                 attr->type = attr_label;
2359                 if (mr->str)
2360                         g_free(mr->str);
2361                 if (p->value != INT_MAX)
2362                         mr->str=g_strdup_printf("%d", p->value);
2363                 else
2364                         mr->str=g_strdup("-");
2365                 attr->u.str = mr->str;
2366                 mr->attr_next=attr_none;
2367                 return 1;
2368         case attr_street_item:
2369                 if (mr->item.type != type_rg_segment)
2370                         return 0;
2371                 mr->attr_next=attr_none;
2372                 if (seg && seg->data.item.map)
2373                         attr->u.item=&seg->data.item;
2374                 else
2375                         return 0;
2376                 return 1;
2377         case attr_flags:
2378                 if (mr->item.type != type_rg_segment)
2379                         return 0;
2380                 mr->attr_next = attr_none;
2381                 if (seg) {
2382                         attr->u.num = seg->data.flags;
2383                 } else {
2384                         return 0;
2385                 }
2386                 return 1;
2387         case attr_direction:
2388                 // This only works if the map has been opened at a single point, and in that case indicates if the
2389                 // segment returned last is connected to this point via its start (1) or its end (-1)
2390                 if (!mr->coord_sel || (mr->item.type != type_rg_segment))
2391                         return 0;
2392                 if (seg->start == mr->point) {
2393                         attr->u.num=1;
2394                 } else if (seg->end == mr->point) {
2395                         attr->u.num=-1;
2396                 } else {
2397                         return 0;
2398                 }
2399                 return 1;
2400         case attr_debug:
2401                 if (mr->item.type != type_rg_point)
2402                         return 0;
2403                 attr->type = attr_debug;
2404                 if (mr->str)
2405                         g_free(mr->str);
2406                 mr->str=g_strdup_printf("x=%d y=%d", p->c.x, p->c.y);
2407                 attr->u.str = mr->str;
2408                 mr->attr_next=attr_none;
2409                 return 1;
2410         default:
2411                 mr->attr_next=attr_none;
2412                 attr->type=attr_none;
2413                 return 0;
2414         }
2415 }
2416
2417 /**
2418  * @brief Returns the coordinates of a route graph item
2419  *
2420  * @param priv_data The route graph item's private data
2421  * @param c Pointer where to store the coordinates
2422  * @param count How many coordinates to get at a max?
2423  * @return The number of coordinates retrieved
2424  */
2425 static int
2426 rp_coord_get(void *priv_data, struct coord *c, int count)
2427 {
2428         struct map_rect_priv *mr = priv_data;
2429         struct route_graph_point *p = mr->point;
2430         struct route_graph_segment *seg = mr->rseg;
2431         int rc = 0,i,dir;
2432         struct route *r = mr->mpriv->route;
2433         enum projection pro = route_projection(r);
2434
2435         if (pro == projection_none)
2436                 return 0;
2437         for (i=0; i < count; i++) {
2438                 if (mr->item.type == type_rg_point) {
2439                         if (mr->last_coord >= 1)
2440                                 break;
2441                         if (pro != projection_mg)
2442                                 transform_from_to(&p->c, pro,
2443                                         &c[i],projection_mg);
2444                         else
2445                                 c[i] = p->c;
2446                 } else {
2447                         if (mr->last_coord >= 2)
2448                                 break;
2449                         dir=0;
2450                         if (seg->end->seg == seg)
2451                                 dir=1;
2452                         if (mr->last_coord)
2453                                 dir=1-dir;
2454                         if (dir) {
2455                                 if (pro != projection_mg)
2456                                         transform_from_to(&seg->end->c, pro,
2457                                                 &c[i],projection_mg);
2458                                 else
2459                                         c[i] = seg->end->c;
2460                         } else {
2461                                 if (pro != projection_mg)
2462                                         transform_from_to(&seg->start->c, pro,
2463                                                 &c[i],projection_mg);
2464                                 else
2465                                         c[i] = seg->start->c;
2466                         }
2467                 }
2468                 mr->last_coord++;
2469                 rc++;
2470         }
2471         return rc;
2472 }
2473
2474 static struct item_methods methods_point_item = {
2475         rm_coord_rewind,
2476         rp_coord_get,
2477         rp_attr_rewind,
2478         rp_attr_get,
2479 };
2480
2481 static void
2482 rp_destroy(struct map_priv *priv)
2483 {
2484         g_free(priv);
2485 }
2486
2487 static void
2488 rm_destroy(struct map_priv *priv)
2489 {
2490         g_free(priv);
2491 }
2492
2493 static struct map_rect_priv *
2494 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
2495 {
2496         struct map_rect_priv * mr;
2497         dbg(1,"enter\n");
2498         if (! route_get_pos(priv->route))
2499                 return NULL;
2500         if (! route_get_dst(priv->route))
2501                 return NULL;
2502 #if 0
2503         if (! priv->route->path2)
2504                 return NULL;
2505 #endif
2506         mr=g_new0(struct map_rect_priv, 1);
2507         mr->mpriv = priv;
2508         mr->item.priv_data = mr;
2509         mr->item.type = type_none;
2510         mr->item.meth = &methods_route_item;
2511         if (priv->route->path2) {
2512                 mr->path=priv->route->path2;
2513                 mr->seg_next=mr->path->path;
2514                 mr->path->in_use++;
2515         } else
2516                 mr->seg_next=NULL;
2517         return mr;
2518 }
2519
2520 /**
2521  * @brief Opens a new map rectangle on the route graph's map
2522  *
2523  * This function opens a new map rectangle on the route graph's map.
2524  * The "sel" parameter enables you to only search for a single route graph
2525  * point on this map (or exactly: open a map rectangle that only contains
2526  * this one point). To do this, pass here a single map selection, whose
2527  * c_rect has both coordinates set to the same point. Otherwise this parameter
2528  * has no effect.
2529  *
2530  * @param priv The route graph map's private data
2531  * @param sel Here it's possible to specify a point for which to search. Please read the function's description.
2532  * @return A new map rect's private data
2533  */
2534 static struct map_rect_priv *
2535 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
2536 {
2537         struct map_rect_priv * mr;
2538
2539         dbg(1,"enter\n");
2540         if (! priv->route->graph || ! priv->route->graph->route_points)
2541                 return NULL;
2542         mr=g_new0(struct map_rect_priv, 1);
2543         mr->mpriv = priv;
2544         mr->item.priv_data = mr;
2545         mr->item.type = type_rg_point;
2546         mr->item.meth = &methods_point_item;
2547         if (sel) {
2548                 if ((sel->u.c_rect.lu.x == sel->u.c_rect.rl.x) && (sel->u.c_rect.lu.y == sel->u.c_rect.rl.y)) {
2549                         mr->coord_sel = g_malloc(sizeof(struct coord));
2550                         *(mr->coord_sel) = sel->u.c_rect.lu;
2551                 }
2552         }
2553         return mr;
2554 }
2555
2556 static void
2557 rm_rect_destroy(struct map_rect_priv *mr)
2558 {
2559         if (mr->str)
2560                 g_free(mr->str);
2561         if (mr->coord_sel) {
2562                 g_free(mr->coord_sel);
2563         }
2564         if (mr->path) {
2565                 mr->path->in_use--;
2566                 if (mr->path->update_required && !mr->path->in_use)
2567                         route_path_update_done(mr->mpriv->route, mr->path->update_required-1);
2568         }
2569
2570         g_free(mr);
2571 }
2572
2573 static struct item *
2574 rp_get_item(struct map_rect_priv *mr)
2575 {
2576         struct route *r = mr->mpriv->route;
2577         struct route_graph_point *p = mr->point;
2578         struct route_graph_segment *seg = mr->rseg;
2579
2580         if (mr->item.type == type_rg_point) {
2581                 if (mr->coord_sel) {
2582                         // We are supposed to return only the point at one specified coordinate...
2583                         if (!p) {
2584                                 p = r->graph->hash[HASHCOORD(mr->coord_sel)];
2585                                 while ((p) && ((p->c.x != mr->coord_sel->x) || (p->c.y != mr->coord_sel->y))) {
2586                                         p = p->hash_next;
2587                                 }
2588                                 if ((!p) || !((p->c.x == mr->coord_sel->x) && (p->c.y == mr->coord_sel->y))) {
2589                                         mr->point = NULL; // This indicates that no point has been found
2590                                 } else {
2591                                         mr->it = rp_iterator_new(p);
2592                                 }
2593                         } else {
2594                                 p = NULL;
2595                         }
2596                 } else {
2597                         if (!p)
2598                                 p = r->graph->route_points;
2599                         else
2600                                 p = p->next;
2601                 }
2602                 if (p) {
2603                         mr->point = p;
2604                         mr->item.id_lo++;
2605                         rm_coord_rewind(mr);
2606                         rp_attr_rewind(mr);
2607                         return &mr->item;
2608                 } else
2609                         mr->item.type = type_rg_segment;
2610         }
2611
2612         if (mr->coord_sel) {
2613                 if (!mr->point) { // This means that no point has been found
2614                         return NULL;
2615                 }
2616                 seg = rp_iterator_next(&(mr->it));
2617         } else {
2618                 if (!seg)
2619                         seg=r->graph->route_segments;
2620                 else
2621                         seg=seg->next;
2622         }
2623
2624         if (seg) {
2625                 mr->rseg = seg;
2626                 mr->item.id_lo++;
2627                 rm_coord_rewind(mr);
2628                 rp_attr_rewind(mr);
2629                 return &mr->item;
2630         }
2631         return NULL;
2632
2633 }
2634
2635 static struct item *
2636 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2637 {
2638         struct item *ret=NULL;
2639         while (id_lo-- > 0)
2640                 ret=rp_get_item(mr);
2641         return ret;
2642 }
2643
2644
2645 static struct item *
2646 rm_get_item(struct map_rect_priv *mr)
2647 {
2648         dbg(1,"enter\n", mr->pos);
2649
2650         switch (mr->item.type) {
2651         case type_none:
2652                 mr->item.type=type_route_start;
2653                 if (mr->mpriv->route->pos)
2654                         break;
2655         default:
2656                 mr->item.type=type_street_route;
2657                 mr->seg=mr->seg_next;
2658                 if (mr->seg) {
2659                         mr->seg_next=mr->seg->next;
2660                         break;
2661                 }
2662                 mr->item.type=type_route_end;
2663                 if (mr->mpriv->route->dst)
2664                         break;
2665         case type_route_end:
2666                 return NULL;
2667         }
2668         mr->last_coord = 0;
2669         mr->item.id_lo++;
2670         rm_attr_rewind(mr);
2671         return &mr->item;
2672 }
2673
2674 static struct item *
2675 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2676 {
2677         struct item *ret=NULL;
2678         while (id_lo-- > 0)
2679                 ret=rm_get_item(mr);
2680         return ret;
2681 }
2682
2683 static struct map_methods route_meth = {
2684         projection_mg,
2685         "utf-8",
2686         rm_destroy,
2687         rm_rect_new,
2688         rm_rect_destroy,
2689         rm_get_item,
2690         rm_get_item_byid,
2691         NULL,
2692         NULL,
2693         NULL,
2694 };
2695
2696 static struct map_methods route_graph_meth = {
2697         projection_mg,
2698         "utf-8",
2699         rp_destroy,
2700         rp_rect_new,
2701         rm_rect_destroy,
2702         rp_get_item,
2703         rp_get_item_byid,
2704         NULL,
2705         NULL,
2706         NULL,
2707 };
2708
2709 void
2710 route_toggle_routegraph_display(struct route *route)
2711 {
2712         if (route->flags & RF_SHOWGRAPH) {
2713                 route->flags &= ~RF_SHOWGRAPH;
2714         } else {
2715                 route->flags |= RF_SHOWGRAPH;
2716         }
2717 }
2718
2719 static struct map_priv *
2720 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
2721 {
2722         struct map_priv *ret;
2723         struct attr *route_attr;
2724
2725         route_attr=attr_search(attrs, NULL, attr_route);
2726         if (! route_attr)
2727                 return NULL;
2728         ret=g_new0(struct map_priv, 1);
2729         if (graph)
2730                 *meth=route_graph_meth;
2731         else
2732                 *meth=route_meth;
2733         ret->route=route_attr->u.route;
2734
2735         return ret;
2736 }
2737
2738 static struct map_priv *
2739 route_map_new(struct map_methods *meth, struct attr **attrs)
2740 {
2741         return route_map_new_helper(meth, attrs, 0);
2742 }
2743
2744 static struct map_priv *
2745 route_graph_map_new(struct map_methods *meth, struct attr **attrs)
2746 {
2747         return route_map_new_helper(meth, attrs, 1);
2748 }
2749
2750 static struct map *
2751 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
2752 {
2753         if (! *map)
2754                 *map=map_new(NULL, (struct attr*[]){
2755                                 &(struct attr){attr_type,{type}},
2756                                 &(struct attr){attr_route,.u.route=this_},
2757                                 &(struct attr){attr_data,{""}},
2758                                 &(struct attr){attr_description,{description}},
2759                                 NULL});
2760
2761         return *map;
2762 }
2763
2764 /**
2765  * @brief Returns a new map containing the route path
2766  *
2767  * This function returns a new map containing the route path.
2768  *
2769  * @important Do not map_destroy() this!
2770  *
2771  * @param this_ The route to get the map of
2772  * @return A new map containing the route path
2773  */
2774 struct map *
2775 route_get_map(struct route *this_)
2776 {
2777         return route_get_map_helper(this_, &this_->map, "route","Route");
2778 }
2779
2780
2781 /**
2782  * @brief Returns a new map containing the route graph
2783  *
2784  * This function returns a new map containing the route graph.
2785  *
2786  * @important Do not map_destroy()  this!
2787  *
2788  * @param this_ The route to get the map of
2789  * @return A new map containing the route graph
2790  */
2791 struct map *
2792 route_get_graph_map(struct route *this_)
2793 {
2794         return route_get_map_helper(this_, &this_->graph_map, "route_graph","Route Graph");
2795 }
2796
2797 void
2798 route_set_projection(struct route *this_, enum projection pro)
2799 {
2800 }
2801
2802 void
2803 route_add_callback(struct route *this_, struct callback *cb)
2804 {
2805         callback_list_add(this_->cbl, cb);
2806 }
2807
2808 void
2809 route_remove_callback(struct route *this_, struct callback *cb)
2810 {
2811         callback_list_remove(this_->cbl, cb);
2812 }
2813
2814
2815 void
2816 route_init(void)
2817 {
2818         plugin_register_map_type("route", route_map_new);
2819         plugin_register_map_type("route_graph", route_graph_map_new);
2820 }