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