navit/navit/route.c

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