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