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