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