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