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