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