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