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  * @return The number of coordinates returned
 842  */
 843 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
 844                 struct coord *start, struct coord *end)
 845 {
 846         struct map_rect *mr;
 847         struct item *item;
 848         int rc = 0, p = 0;
 849         struct coord c1;
 850         mr=map_rect_new(i->map, NULL);
 851         if (!mr)
 852                 return 0;
 853         item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
 854         if (item) {
 855                 rc = item_coord_get(item, &c1, 1);
 856                 while (rc && (c1.x != start->x || c1.y != start->y)) {
 857                         rc = item_coord_get(item, &c1, 1);
 858                 }
 859                 while (rc && p < max) {
 860                         c[p++] = c1;
 861                         if (c1.x == end->x && c1.y == end->y)
 862                                 break;
 863                         rc = item_coord_get(item, &c1, 1);
 864                 }
 865         }
 866         map_rect_destroy(mr);
 867         return p;
 868 }
 869
 870 /**
 871  * @brief Returns and removes one segment from a path
 872  *
 873  * @param path The path to take the segment from
 874  * @param item The item whose segment to remove
 875  * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
 876  * @return The segment removed
 877  */
 878 static struct route_path_segment *
 879 route_extract_segment_from_path(struct route_path *path, struct item *item,
 880                                                  int offset)
 881 {
 882         struct route_path_segment *sp = NULL, *s;
 883         s = path->path;
 884         while (s) {
 885                 if (s->offset == offset && item_is_equal(s->item,*item)) {
 886                         if (sp) {
 887                                 sp->next = s->next;
 888                                 break;
 889                         } else {
 890                                 path->path = s->next;
 891                                 break;
 892                         }
 893                 }
 894                 sp = s;
 895                 s = s->next;
 896         }
 897         if (s)
 898                 item_hash_remove(path->path_hash, item);
 899         return s;
 900 }
 901
 902 /**
 903  * @brief Adds a segment and the end of a path
 904  *
 905  * @param this The path to add the segment to
 906  * @param segment The segment to add
 907  */
 908 static void
 909 route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
 910 {
 911         if (!this->path)
 912                 this->path=segment;
 913         if (this->path_last)
 914                 this->path_last->next=segment;
 915         this->path_last=segment;
 916 }
 917
 918 /**
 919  * @brief Adds a new item to a path
 920  *
 921  * This adds a new item to a path, creating a new segment for it. Please note that this function does not check
 922  * if the item passed is segmented - it will create exactly one segment.
 923  *
 924  * @param this The path to add the item to
 925  * @param item The item to add
 926  * @param len The length of the item
 927  * @param first (Optional) coordinate to add to the start of the item. If none should be added, make this NULL.
 928  * @param c Pointer to count coordinates of the item.
 929  * @param cound Number of coordinates in c
 930  * @param last (Optional) coordinate to add to the end of the item. If none should be added, make this NULL.
 931  * @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"
 932  */
 933 static void
 934 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)
 935 {
 936         int i,idx=0,ccount=count + (first ? 1:0) + (last ? 1:0);
 937         struct route_path_segment *segment;
 938
 939         segment=g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccount);
 940         segment->ncoords=ccount;
 941         segment->direction=dir;
 942         if (first)
 943                 segment->c[idx++]=*first;
 944         if (dir > 0) {
 945                 for (i = 0 ; i < count ; i++)
 946                         segment->c[idx++]=c[i];
 947         } else {
 948                 for (i = 0 ; i < count ; i++)
 949                         segment->c[idx++]=c[count-i-1];
 950         }
 951         if (last)
 952                 segment->c[idx++]=*last;
 953         segment->length=len;
 954         if (item)
 955                 segment->item=*item;
 956         route_path_add_segment(this, segment);
 957 }
 958
 959 /**
 960  * @brief Inserts a new item into the path
 961  *
 962  * This function does almost the same as "route_apth_add_item()", but identifies
 963  * the item to add by a segment from the route graph. Another difference is that it "copies" the
 964  * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
 965  * be added to the route path, not all segments of the item.
 966  *
 967  * The function can be sped up by passing an old path already containing this segment in oldpath -
 968  * the segment will then be extracted from this old path. Please note that in this case the direction
 969  * parameter has no effect.
 970  *
 971  * @param this The path to add the item to
 972  * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
 973  * @param rgs Segment of the route graph that should be "copied" to the route path
 974  * @param len Length of the item to be added
 975  * @param offset Offset of rgs within the item it represents
 976  * @param dir Order in which to add the coordinates. See route_path_add_item()
 977  * @param straight Indicates if this segment is being entered "straight". See route_check_straight().
 978  */
 979 static void
 980 route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath,
 981                                    struct route_graph_segment *rgs, int len, int offset, int dir, int straight)
 982 {
 983         struct route_path_segment *segment;
 984         int i,ccnt = 0;
 985         struct coord ca[2048];
 986 #ifndef DISABLE_STRAIGHT
 987         struct attr straight_attr;
 988 #endif
 989
 990         if (oldpath) {
 991                 ccnt = (int)item_hash_lookup(oldpath->path_hash, &rgs->item);
 992                 if (ccnt) {
 993                         segment = route_extract_segment_from_path(oldpath,
 994                                                          &rgs->item, offset);
 995
 996                         if (segment)
 997                                 goto linkold;
 998                 }
 999         }
1000
1001         ccnt = get_item_seg_coords(&rgs->item, ca, 2047, &rgs->start->c, &rgs->end->c);
1002         segment= g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccnt);
1003         if (!segment) {
1004                 printf("%s:Out of memory\n", __FUNCTION__);
1005                 return;
1006         }
1007         segment->direction=dir;
1008         if (dir > 0) {
1009                 for (i = 0 ; i < ccnt ; i++)
1010                         segment->c[i]=ca[i];
1011         } else {
1012                 for (i = 0 ; i < ccnt ; i++)
1013                         segment->c[i]=ca[ccnt-i-1];
1014         }
1015         segment->ncoords = ccnt;
1016         segment->item=rgs->item;
1017         segment->offset = offset;
1018 linkold:
1019         segment->length=len;
1020         segment->next=NULL;
1021         item_hash_insert(this->path_hash,  &rgs->item, (void *)ccnt);
1022
1023 #ifndef DISABLE_STRAIGHT
1024         straight_attr.type = attr_route_follow_straight;
1025         straight_attr.u.num = straight;
1026
1027         segment->attrs = attr_generic_set_attr(segment->attrs, &straight_attr);
1028 #endif
1029
1030         route_path_add_segment(this, segment);
1031 }
1032
1033 /**
1034  * @brief Destroys all segments of a route graph
1035  *
1036  * @param this The graph to destroy all segments from
1037  */
1038 static void
1039 route_graph_free_segments(struct route_graph *this)
1040 {
1041         struct route_graph_segment *curr,*next;
1042         curr=this->route_segments;
1043         while (curr) {
1044                 next=curr->next;
1045                 g_free(curr);
1046                 curr=next;
1047         }
1048         this->route_segments=NULL;
1049 }
1050
1051 /**
1052  * @brief Destroys a route graph
1053  *
1054  * @param this The route graph to be destroyed
1055  */
1056 static void
1057 route_graph_destroy(struct route_graph *this)
1058 {
1059         if (this) {
1060                 route_graph_free_points(this);
1061                 route_graph_free_segments(this);
1062                 g_free(this);
1063         }
1064 }
1065
1066 /**
1067  * @brief Returns the time needed to drive len on item
1068  *
1069  * @param speedlist The speedlist that should be used
1070  * @param item The item to be driven on
1071  * @param len The length to drive
1072  * @return The time needed to drive len on item
1073  */
1074 int
1075 route_time(int *speedlist, struct item *item, int len)
1076 {
1077         if (item->type < route_item_first || item->type > route_item_last) {
1078                 dbg(0,"street type %d out of range [%d,%d]\n", item->type, route_item_first, route_item_last);
1079                 return len*36;
1080         }
1081         if (!speedlist[item->type-route_item_first]) {
1082                 dbg(0,"street type %d speed is zero\n", item->type);
1083                 return len*36;
1084         }
1085         return len*36/speedlist[item->type-route_item_first];
1086 }
1087
1088 /**
1089  * @brief Returns the "costs" of driving len on item
1090  *
1091  * @param speedlist The speedlist that should be used
1092  * @param item The item to be driven on
1093  * @param len The length to drive
1094  * @return The "costs" needed to drive len on item
1095  */
1096 static int
1097 route_value(int *speedlist, struct item *item, int len)
1098 {
1099         int ret;
1100         if (len < 0) {
1101                 printf("len=%d\n", len);
1102         }
1103         dbg_assert(len >= 0);
1104         ret=route_time(speedlist, item, len);
1105         dbg(1, "route_value(0x%x, %d)=%d\n", item->type, len, ret);
1106         return ret;
1107 }
1108
1109 /**
1110  * @brief Adds an item to the route graph
1111  *
1112  * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
1113  * segmented item.
1114  *
1115  * @param this The route graph to add to
1116  * @param item The item to add
1117  */
1118 static void
1119 route_process_street_graph(struct route_graph *this, struct item *item)
1120 {
1121 #ifdef AVOID_FLOAT
1122         int len=0;
1123 #else
1124         double len=0;
1125 #endif
1126         struct route_graph_point *s_pnt,*e_pnt;
1127         struct coord c,l;
1128         struct attr attr;
1129         int flags = 0;
1130         int segmented = 0;
1131         int offset = 1;
1132
1133         if (item_coord_get(item, &l, 1)) {
1134                 if (item_attr_get(item, attr_flags, &attr)) {
1135                         flags = attr.u.num;
1136                         if (flags & AF_SEGMENTED)
1137                                 segmented = 1;
1138                 }
1139                 s_pnt=route_graph_add_point(this,&l);
1140                 if (!segmented) {
1141                         while (item_coord_get(item, &c, 1)) {
1142                                 len+=transform_distance(map_projection(item->map), &l, &c);
1143                                 l=c;
1144                         }
1145                         e_pnt=route_graph_add_point(this,&l);
1146                         dbg_assert(len >= 0);
1147                         route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1148                 } else {
1149                         int isseg,rc;
1150                         int sc = 0;
1151                         do {
1152                                 isseg = item_coord_is_node(item);
1153                                 rc = item_coord_get(item, &c, 1);
1154                                 if (rc) {
1155                                         len+=transform_distance(map_projection(item->map), &l, &c);
1156                                         l=c;
1157                                         if (isseg) {
1158                                                 e_pnt=route_graph_add_point(this,&l);
1159                                                 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1160                                                 offset++;
1161                                                 s_pnt=route_graph_add_point(this,&l);
1162                                                 len = 0;
1163                                         }
1164                                 }
1165                         } while(rc);
1166                         e_pnt=route_graph_add_point(this,&l);
1167                         dbg_assert(len >= 0);
1168                         sc++;
1169                         route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1170                 }
1171         }
1172 }
1173
1174 /**
1175  * @brief Compares the costs of reaching the destination from two points on
1176  *
1177  * @important Do not pass anything other than route_graph_points in v1 and v2!
1178  *
1179  * @param v1 Point1
1180  * @param v2 Point2
1181  * @return The additional costs of v1 compared to v2 (may be negative)
1182  */
1183 static int
1184 compare(void *v1, void *v2)
1185 {
1186         struct route_graph_point *p1=v1;
1187         struct route_graph_point *p2=v2;
1188 #if 0
1189         if (debug_route)
1190                 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
1191 #endif
1192         return p1->value-p2->value;
1193 }
1194
1195 /**
1196  * @brief Calculates the routing costs for each point
1197  *
1198  * This function is the heart of routing. It assigns each point in the route graph a
1199  * cost at which one can reach the destination from this point on. Additionally it assigns
1200  * each point a segment one should follow from this point on to reach the destination at the
1201  * stated costs.
1202  *
1203  * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
1204  * at this algorithm.
1205  */
1206 static void
1207 route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist)
1208 {
1209         struct route_graph_point *p_min,*end=NULL;
1210         struct route_graph_segment *s;
1211         int min,new,old,val;
1212         struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
1213         struct street_data *sd=dst->street;
1214
1215         heap = fh_makeheap();
1216         fh_setcmp(heap, compare);
1217
1218         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 */
1219                 end=route_graph_get_point(this, &sd->c[0]);
1220                 dbg_assert(end != 0);
1221                 end->value=route_value(speedlist, &sd->item, dst->lenneg);
1222                 end->el=fh_insert(heap, end);
1223         }
1224
1225         if (! (sd->flags & AF_ONEWAY)) { /* If we may drive against the direction of the coordinates, the last coordinate is another starting point */
1226                 end=route_graph_get_point(this, &sd->c[sd->count-1]);
1227                 dbg_assert(end != 0);
1228                 end->value=route_value(speedlist, &sd->item, dst->lenpos);
1229                 end->el=fh_insert(heap, end);
1230         }
1231
1232         dbg(1,"0x%x,0x%x\n", end->c.x, end->c.y);
1233         for (;;) {
1234                 p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
1235                 if (! p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
1236                         break;
1237                 min=p_min->value;
1238                 if (debug_route)
1239                         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);
1240                 p_min->el=NULL; /* This point is permanently calculated now, we've taken it out of the heap */
1241                 s=p_min->start;
1242                 while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
1243                         val=route_value(speedlist, &s->item, s->len);
1244 #if 0
1245                         val+=val*2*street_route_contained(s->str->segid);
1246 #endif
1247                         new=min+val;
1248                         if (debug_route)
1249                                 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);
1250                         if (new < s->end->value && !(s->flags & AF_ONEWAY)) { /* We've found a less costly way to reach the end of s, update it */
1251                                 s->end->value=new;
1252                                 s->end->seg=s;
1253                                 if (! s->end->el) {
1254                                         if (debug_route)
1255                                                 printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
1256                                         s->end->el=fh_insert(heap, s->end);
1257                                         if (debug_route)
1258                                                 printf("el new=%p\n", s->end->el);
1259                                 }
1260                                 else {
1261                                         if (debug_route)
1262                                                 printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
1263                                         fh_replacedata(heap, s->end->el, s->end);
1264                                 }
1265                         }
1266                         if (debug_route)
1267                                 printf("\n");
1268                         s=s->start_next;
1269                 }
1270                 s=p_min->end;
1271                 while (s) { /* Doing the same as above with the segments leading towards our point */
1272                         val=route_value(speedlist, &s->item, s->len);
1273                         new=min+val;
1274                         if (debug_route)
1275                                 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);
1276                         if (new < s->start->value && !(s->flags & AF_ONEWAYREV)) {
1277                                 old=s->start->value;
1278                                 s->start->value=new;
1279                                 s->start->seg=s;
1280                                 if (! s->start->el) {
1281                                         if (debug_route)
1282                                                 printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
1283                                         s->start->el=fh_insert(heap, s->start);
1284                                         if (debug_route)
1285                                                 printf("el new=%p\n", s->start->el);
1286                                 }
1287                                 else {
1288                                         if (debug_route)
1289                                                 printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
1290                                         fh_replacedata(heap, s->start->el, s->start);
1291                                 }
1292                         }
1293                         if (debug_route)
1294                                 printf("\n");
1295                         s=s->end_next;
1296                 }
1297         }
1298         fh_deleteheap(heap);
1299 }
1300
1301 /**
1302  * @brief Starts an "offroad" path
1303  *
1304  * This starts a path that is not located on a street. It creates a new route path
1305  * adding only one segment, that leads from pos to dest, and which is not associated with an item.
1306  *
1307  * @param this Not used
1308  * @param pos The starting position for the new path
1309  * @param dst The destination of the new path
1310  * @param dir Not used
1311  * @return The new path
1312  */
1313 static struct route_path *
1314 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1315 {
1316         struct route_path *ret;
1317
1318         ret=g_new0(struct route_path, 1);
1319         ret->path_hash=item_hash_new();
1320         route_path_add_item(ret, NULL, pos->lenextra+dst->lenextra, &pos->c, NULL, 0, &dst->c, 1);
1321
1322         return ret;
1323 }
1324
1325 /**
1326  * @brief Creates a new "trivial" route
1327  *
1328  * This function creates a new "trivial" route. A trivial route is a route that starts and ends on the same street,
1329  * so there is no routing needed. Depending on pos and dst it can optionally add some "offroad" part to the route.
1330  *
1331  * @param this The route graph to place the route on
1332  * @param pos The starting position for the new path
1333  * @param dst The destination of the new path
1334  * @param dir Direction of the coordinates to be added
1335  * @return The new path
1336  */
1337 static struct route_path *
1338 route_path_new_trivial(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1339 {
1340         struct street_data *sd=pos->street;
1341         struct route_path *ret;
1342
1343         if (dir > 0) {
1344                 if (pos->lenextra + dst->lenextra + pos->lenneg-dst->lenneg > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1345                         return route_path_new_offroad(this, pos, dst, dir);
1346         } else {
1347                 if (pos->lenextra + dst->lenextra + pos->lenpos-dst->lenpos > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1348                         return route_path_new_offroad(this, pos, dst, dir);
1349         }
1350         ret=g_new0(struct route_path, 1);
1351         ret->path_hash=item_hash_new();
1352         if (pos->lenextra)
1353                 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1354         if (dir > 0)
1355                 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);
1356         else
1357                 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);
1358         if (dst->lenextra)
1359                 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1360         return ret;
1361 }
1362
1363 #ifndef DISABLE_STRAIGHT
1364 /**
1365  * @brief Calculates of two coordinates' connection
1366  *
1367  * This function calculates the angle between coordinates, with north = 0
1368  * and east = 90.
1369  *
1370  * %FIXME This is a duplicate of road_angle() in navigation.c - combine them?
1371  *
1372  * @param c1 Coordinate 1
1373  * @param c2 Coordinate 2
1374  * @param dir Set to true if c1 is the prior, and c2 the later coordinate.
1375  * @return The angle of the coordinate's connection
1376  */
1377 static int
1378 route_road_angle(struct coord *c1, struct coord *c2, int dir)
1379 {
1380         int ret=transform_get_angle_delta(c1, c2, dir);
1381         dbg(1, "road_angle(0x%x,0x%x - 0x%x,0x%x)=%d\n", c1->x, c1->y, c2->x, c2->y, ret);
1382         return ret;
1383 }
1384
1385 /**
1386  * @brief Checks if entering one segment from another is a "straight" road
1387  *
1388  * This checks if one can enter seg_to from seg_from by driving "straight" - i.e.
1389  * if seg_to is the segment you can drive to from seg_from by steering less than
1390  * all to all other segments.
1391  *
1392  * This function returns true on failure, so we don't create maneuvers on every error.
1393  *
1394  * @param seg_from Segment we are driving from
1395  * @param seg_to Segment we are driving to
1396  * @return True if driving from seg_from to seg_to is "straight", false otherwise
1397  */
1398 static int
1399 route_check_straight(struct route_graph_segment *seg_from, struct route_graph_segment *seg_to)
1400 {
1401         struct route_graph_segment *curr;
1402         struct route_graph_point *conn;
1403         int from_angle, to_angle, curr_angle, angle_diff;
1404         int ccnt;
1405         struct coord ca[2048];
1406
1407         if ((seg_from->end == seg_to->start) || (seg_from->end == seg_to->end)) {
1408                 ccnt = get_item_seg_coords(&seg_from->item, ca, 2047, &seg_from->start->c, &seg_from->end->c);
1409                 from_angle = route_road_angle(&ca[ccnt-2], &ca[ccnt-1],1);
1410
1411                 conn = seg_from->end;
1412         } else if ((seg_from->start == seg_to->start) || (seg_from->start == seg_to->end)) {
1413                 ccnt = get_item_seg_coords(&seg_from->item, ca, 2, &seg_from->start->c, &seg_from->end->c);
1414                 from_angle = route_road_angle(&ca[1], &ca[0],1);
1415
1416                 conn = seg_from->start;
1417         } else {
1418                 // Not connected!
1419                 return 1;
1420         }
1421
1422
1423         if (seg_to->end == conn) {
1424                 ccnt = get_item_seg_coords(&seg_to->item, ca, 2047, &seg_to->start->c, &seg_to->end->c);
1425                 to_angle = route_road_angle(&ca[ccnt-1], &ca[ccnt-2],1);
1426         } else {
1427                 ccnt = get_item_seg_coords(&seg_to->item, ca, 2, &seg_to->start->c, &seg_to->end->c);
1428                 to_angle = route_road_angle(&ca[0], &ca[1],1);
1429         }
1430
1431
1432         angle_diff = from_angle - to_angle;
1433         if (angle_diff < 0) {
1434                 angle_diff *= -1;
1435         }
1436
1437
1438         curr = conn->start;
1439         while (curr != NULL) {
1440                 if (curr==seg_to) {
1441                         curr = curr->start_next;
1442                         continue;
1443                 }
1444
1445                 ccnt = get_item_seg_coords(&curr->item, ca, 2, &curr->start->c, &curr->end->c);
1446                 curr_angle = route_road_angle(&ca[0], &ca[1], 1);
1447
1448                 curr_angle = from_angle - curr_angle;
1449
1450                 if (curr_angle < 0) {
1451                         curr_angle *= -1;
1452                 }
1453
1454
1455                 if (curr_angle < angle_diff) {
1456                         return 0;
1457                 }
1458
1459                 curr = curr->start_next;
1460         }
1461
1462         curr = conn->end;
1463         while (curr != NULL) {
1464                 if (curr==seg_to) {
1465                         curr = curr->end_next;
1466                         continue;
1467                 }
1468
1469                 ccnt = get_item_seg_coords(&curr->item, ca, 2047, &curr->start->c, &curr->end->c);
1470                 curr_angle = route_road_angle(&ca[ccnt-1], &ca[ccnt-2], 1);
1471
1472                 curr_angle = from_angle - curr_angle;
1473
1474                 if (curr_angle < 0) {
1475                         curr_angle *= -1;
1476                 }
1477
1478                 if (curr_angle < angle_diff) {
1479                         return 0;
1480                 }
1481
1482                 curr = curr->end_next;
1483         }
1484
1485         return 1;
1486 }
1487 #endif
1488
1489 /**
1490  * @brief Creates a new route path
1491  *
1492  * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
1493  * make shure to run route_graph_flood() after changing the destination before using this function.
1494  *
1495  * @param this The route graph to create the route from
1496  * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
1497  * @param pos The starting position of the route
1498  * @param dst The destination of the route
1499  * @param speedlist The speedlist to use
1500  * @return The new route path
1501  */
1502 static struct route_path *
1503 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist)
1504 {
1505         struct route_graph_point *start1=NULL,*start2=NULL,*start;
1506         struct route_graph_segment *s=NULL;
1507         struct route_graph_segment *lastseg = NULL;
1508         int is_straight=0;
1509         int len=0,segs=0;
1510         int seg_len;
1511 #if 0
1512         int time=0,hr,min,sec
1513 #endif
1514         unsigned int val1=0xffffffff,val2=0xffffffff;
1515         struct street_data *sd=pos->street;
1516         struct route_path *ret;
1517
1518         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 */
1519                 if (!(sd->flags & AF_ONEWAY) && pos->lenneg >= dst->lenneg) {
1520                         return route_path_new_trivial(this, pos, dst, -1);
1521                 }
1522                 if (!(sd->flags & AF_ONEWAYREV) && pos->lenpos >= dst->lenpos) {
1523                         return route_path_new_trivial(this, pos, dst, 1);
1524                 }
1525         }
1526         if (! (sd->flags & AF_ONEWAY)) { /* Using the start of the current segment as one starting point */
1527                 start1=route_graph_get_point(this, &sd->c[0]);
1528                 if (! start1)
1529                         return NULL;
1530                 val1=start1->value+route_value(speedlist, &sd->item, pos->lenneg);
1531                 dbg(1,"start1: %d(route)+%d=%d\n", start1->value, val1-start1->value, val1);
1532         }
1533         if (! (sd->flags & AF_ONEWAYREV)) { /* Using the start of the current segment as an alternative starting point */
1534                 start2=route_graph_get_point(this, &sd->c[sd->count-1]);
1535                 if (! start2)
1536                         return NULL;
1537                 val2=start2->value+route_value(speedlist, &sd->item, pos->lenpos);
1538                 dbg(1,"start2: %d(route)+%d=%d\n", start2->value, val2-start2->value, val2);
1539         }
1540         dbg(1,"val1=%d val2=%d\n", val1, val2);
1541         if (val1 == val2) {
1542                 val1=start1->start->start->value;
1543                 val2=start2->end->end->value;
1544         }
1545         ret=g_new0(struct route_path, 1);
1546         if (pos->lenextra)
1547                 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1548         if (start1 && (val1 < val2)) {
1549                 start=start1;
1550                 route_path_add_item(ret, &sd->item, pos->lenneg, &pos->lp, sd->c, pos->pos+1, NULL, -1);
1551         } else {
1552                 if (start2) {
1553                         start=start2;
1554                         route_path_add_item(ret, &sd->item, pos->lenpos, &pos->lp, sd->c+pos->pos+1, sd->count-pos->pos-1, NULL, 1);
1555                 } else {
1556                         printf("no route found, pos blocked\n");
1557                         return NULL;
1558                 }
1559         }
1560         ret->path_hash=item_hash_new();
1561         while ((s=start->seg)) { /* following start->seg, which indicates the least costly way to reach our destination */
1562                 segs++;
1563 #if 0
1564                 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1565 #endif
1566                 seg_len=s->len;
1567                 len+=seg_len;
1568
1569 #ifndef DISABLE_STRAIGHT
1570                 if (lastseg) {
1571                         is_straight = route_check_straight(lastseg,s);
1572                 } else {
1573                         is_straight = 0;
1574                 }
1575 #endif
1576
1577                 if (s->start == start) {
1578                         route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, 1, is_straight);
1579                         start=s->end;
1580                 } else {
1581                         route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, -1, is_straight);
1582                         start=s->start;
1583                 }
1584
1585                 lastseg = s;
1586         }
1587         sd=dst->street;
1588         dbg(1,"start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1589         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);
1590         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 */
1591                 route_path_add_item(ret, &sd->item, dst->lenneg, NULL, sd->c, dst->pos+1, &dst->lp, 1);
1592         } else if (start->c.x == sd->c[sd->count-1].x && start->c.y == sd->c[sd->count-1].y) {
1593                 route_path_add_item(ret, &sd->item, dst->lenpos, NULL, sd->c+dst->pos+1, sd->count-dst->pos-1, &dst->lp, -1);
1594         } else {
1595                 printf("no route found\n");
1596                 route_path_destroy(ret);
1597                 return NULL;
1598         }
1599         if (dst->lenextra)
1600                 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1601         dbg(1, "%d segments\n", segs);
1602         return ret;
1603 }
1604
1605 /**
1606  * @brief Builds a new route graph from a mapset
1607  *
1608  * This function builds a new route graph from a map. Please note that this function does not
1609  * add any routing information to the route graph - this has to be done via the route_graph_flood()
1610  * function.
1611  *
1612  * The function does not create a graph covering the whole map, but only covering the rectangle
1613  * between c1 and c2.
1614  *
1615  * @param ms The mapset to build the route graph from
1616  * @param c1 Corner 1 of the rectangle to use from the map
1617  * @param c2 Corner 2 of the rectangle to use from the map
1618  * @return The new route graph.
1619  */
1620 static struct route_graph *
1621 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2)
1622 {
1623         struct route_graph *ret=g_new0(struct route_graph, 1);
1624         struct map_selection *sel;
1625         struct mapset_handle *h;
1626         struct map_rect *mr;
1627         struct map *m;
1628         struct item *item;
1629
1630         if (!ret) {
1631                 printf("%s:Out of memory\n", __FUNCTION__);
1632                 return ret;
1633         }
1634         sel=route_calc_selection(c1, c2);
1635         h=mapset_open(ms);
1636         while ((m=mapset_next(h,1))) {
1637                 mr=map_rect_new(m, sel);
1638                 if (! mr)
1639                         continue;
1640                 while ((item=map_rect_get_item(mr))) {
1641                         if (item->type >= type_street_0 && item->type <= type_ferry) {
1642                                 route_process_street_graph(ret, item);
1643                         }
1644                 }
1645                 map_rect_destroy(mr);
1646         }
1647         mapset_close(h);
1648         route_free_selection(sel);
1649
1650         return ret;
1651 }
1652
1653 /**
1654  * @brief Updates the route graph
1655  *
1656  * This updates the route graph after settings in the route have changed. It also
1657  * adds routing information afterwards by calling route_graph_flood().
1658  *
1659  * @param this The route to update the graph for
1660  */
1661 static void
1662 route_graph_update(struct route *this)
1663 {
1664         route_graph_destroy(this->graph);
1665         profile(1,"graph_free");
1666         this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c);
1667         profile(1,"route_graph_build");
1668         route_graph_flood(this->graph, this->dst, this->speedlist);
1669         profile(1,"route_graph_flood");
1670         this->version++;
1671 }
1672
1673 /**
1674  * @brief Gets street data for an item
1675  *
1676  * @param item The item to get the data for
1677  * @return Street data for the item
1678  */
1679 struct street_data *
1680 street_get_data (struct item *item)
1681 {
1682         int count=0;
1683         struct street_data *ret = NULL, *ret1;
1684         struct attr attr;
1685         const int step = 128;
1686         int c;
1687
1688         do {
1689                 ret1=g_realloc(ret, sizeof(struct street_data)+(count+step)*sizeof(struct coord));
1690                 if (!ret1) {
1691                         if (ret)
1692                                 g_free(ret);
1693                         return NULL;
1694                 }
1695                 ret = ret1;
1696                 c = item_coord_get(item, &ret->c[count], step);
1697                 count += c;
1698         } while (c && c == step);
1699
1700         ret1=g_realloc(ret, sizeof(struct street_data)+count*sizeof(struct coord));
1701         if (ret1)
1702                 ret = ret1;
1703         ret->item=*item;
1704         ret->count=count;
1705         if (item_attr_get(item, attr_flags, &attr))
1706                 ret->flags=attr.u.num;
1707         else
1708                 ret->flags=0;
1709
1710         return ret;
1711 }
1712
1713 /**
1714  * @brief Copies street data
1715  *
1716  * @param orig The street data to copy
1717  * @return The copied street data
1718  */
1719 struct street_data *
1720 street_data_dup(struct street_data *orig)
1721 {
1722         struct street_data *ret;
1723         int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
1724
1725         ret=g_malloc(size);
1726         memcpy(ret, orig, size);
1727
1728         return ret;
1729 }
1730
1731 /**
1732  * @brief Frees street data
1733  *
1734  * @param sd Street data to be freed
1735  */
1736 void
1737 street_data_free(struct street_data *sd)
1738 {
1739         g_free(sd);
1740 }
1741
1742 /**
1743  * @brief Finds the nearest street to a given coordinate
1744  *
1745  * @param ms The mapset to search in for the street
1746  * @param pc The coordinate to find a street nearby
1747  * @return The nearest street
1748  */
1749 static struct route_info *
1750 route_find_nearest_street(struct mapset *ms, struct pcoord *pc)
1751 {
1752         struct route_info *ret=NULL;
1753         int max_dist=1000;
1754         struct map_selection *sel;
1755         int dist,mindist=0,pos;
1756         struct mapset_handle *h;
1757         struct map *m;
1758         struct map_rect *mr;
1759         struct item *item;
1760         struct coord lp;
1761         struct street_data *sd;
1762         struct coord c;
1763         struct coord_geo g;
1764
1765         ret=g_new0(struct route_info, 1);
1766         if (!ret) {
1767                 dbg(0,"Out of memory\n");
1768                 return ret;
1769         }
1770         mindist = INT_MAX;
1771
1772         h=mapset_open(ms);
1773         while ((m=mapset_next(h,1))) {
1774                 c.x = pc->x;
1775                 c.y = pc->y;
1776                 if (map_projection(m) != pc->pro) {
1777                         transform_to_geo(pc->pro, &c, &g);
1778                         transform_from_geo(map_projection(m), &g, &c);
1779                 }
1780                 sel = route_rect(18, &c, &c, 0, max_dist);
1781                 if (!sel)
1782                         continue;
1783                 mr=map_rect_new(m, sel);
1784                 if (!mr) {
1785                         map_selection_destroy(sel);
1786                         continue;
1787                 }
1788                 while ((item=map_rect_get_item(mr))) {
1789                         if (item->type >= type_street_0 && item->type <= type_ferry) {
1790                                 sd=street_get_data(item);
1791                                 if (!sd)
1792                                         continue;
1793                                 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
1794                                 if (dist < mindist) {
1795                                         mindist = dist;
1796                                         if (ret->street) {
1797                                                 street_data_free(ret->street);
1798                                         }
1799                                         ret->c=c;
1800                                         ret->lp=lp;
1801                                         ret->pos=pos;
1802                                         ret->street=sd;
1803                                         dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
1804                                 } else {
1805                                         street_data_free(sd);
1806                                 }
1807                         }
1808                 }
1809                 map_selection_destroy(sel);
1810                 map_rect_destroy(mr);
1811         }
1812         mapset_close(h);
1813
1814         if (!ret->street || mindist > max_dist*max_dist) {
1815                 if (ret->street) {
1816                         street_data_free(ret->street);
1817                         dbg(1,"Much too far %d > %d\n", mindist, max_dist);
1818                 }
1819                 g_free(ret);
1820                 ret = NULL;
1821         }
1822
1823         return ret;
1824 }
1825
1826 /**
1827  * @brief Destroys a route_info
1828  *
1829  * @param info The route info to be destroyed
1830  */
1831 void
1832 route_info_free(struct route_info *inf)
1833 {
1834         if (inf->street)
1835                 street_data_free(inf->street);
1836         g_free(inf);
1837 }
1838
1839
1840 #include "point.h"
1841
1842 /**
1843  * @brief Returns street data for a route info
1844  *
1845  * @param rinf The route info to return the street data for
1846  * @return Street data for the route info
1847  */
1848 struct street_data *
1849 route_info_street(struct route_info *rinf)
1850 {
1851         return rinf->street;
1852 }
1853
1854 #if 0
1855 struct route_crossings *
1856 route_crossings_get(struct route *this, struct coord *c)
1857 {
1858       struct route_point *pnt;
1859       struct route_segment *seg;
1860       int crossings=0;
1861       struct route_crossings *ret;
1862
1863        pnt=route_graph_get_point(this, c);
1864        seg=pnt->start;
1865        while (seg) {
1866                 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1867                crossings++;
1868                seg=seg->start_next;
1869        }
1870        seg=pnt->end;
1871        while (seg) {
1872                 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1873                crossings++;
1874                seg=seg->end_next;
1875        }
1876        ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
1877        ret->count=crossings;
1878        return ret;
1879 }
1880 #endif
1881
1882
1883 struct map_rect_priv {
1884         struct route_info_handle *ri;
1885         enum attr_type attr_next;
1886         int pos;
1887         struct map_priv *mpriv;
1888         struct item item;
1889         int length;
1890         unsigned int last_coord;
1891         struct route_path_segment *seg,*seg_next;
1892         struct route_graph_point *point;
1893         struct route_graph_segment *rseg;
1894         char *str;
1895 };
1896
1897 static void
1898 rm_coord_rewind(void *priv_data)
1899 {
1900         struct map_rect_priv *mr = priv_data;
1901         mr->last_coord = 0;
1902 }
1903
1904 static void
1905 rm_attr_rewind(void *priv_data)
1906 {
1907         struct map_rect_priv *mr = priv_data;
1908         mr->attr_next = attr_street_item;
1909 }
1910
1911 static int
1912 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1913 {
1914         struct map_rect_priv *mr = priv_data;
1915         struct route_path_segment *seg=mr->seg;
1916         struct route *route=mr->mpriv->route;
1917         attr->type=attr_type;
1918         switch (attr_type) {
1919                 case attr_any:
1920                         while (mr->attr_next != attr_none) {
1921                                 if (rm_attr_get(priv_data, mr->attr_next, attr))
1922                                         return 1;
1923                         }
1924                         return 0;
1925                 case attr_street_item:
1926 #ifndef DISABLE_STRAIGHT
1927                         mr->attr_next=attr_route_follow_straight;
1928 #else
1929                         mr->attr_next=attr_direction;
1930 #endif
1931                         if (seg && seg->item.map)
1932                                 attr->u.item=&seg->item;
1933                         else
1934                                 return 0;
1935                         return 1;
1936 #ifndef DISABLE_STRAIGHT
1937                 case attr_route_follow_straight:
1938                         mr->attr_next=attr_direction;
1939                         if (seg) {
1940                                 return attr_generic_get_attr(seg->attrs,NULL,attr_route_follow_straight,attr,NULL);
1941                         }
1942                         return 0;
1943 #endif
1944                 case attr_direction:
1945                         mr->attr_next=attr_length;
1946                         if (seg)
1947                                 attr->u.num=seg->direction;
1948                         else
1949                                 return 0;
1950                         return 1;
1951                 case attr_length:
1952                         if (seg)
1953                                 attr->u.num=seg->length;
1954                         else
1955                                 attr->u.num=mr->length;
1956                         mr->attr_next=attr_time;
1957                         return 1;
1958                 case attr_time:
1959                         mr->attr_next=attr_none;
1960                         if (seg)
1961                                 attr->u.num=route_time(route->speedlist, &seg->item, seg->length);
1962                         else
1963                                 return 0;
1964                         return 1;
1965                 case attr_label:
1966                         mr->attr_next=attr_none;
1967                         return 0;
1968                 default:
1969                         mr->attr_next=attr_none;
1970                         attr->type=attr_none;
1971                         return 0;
1972         }
1973         return 0;
1974 }
1975
1976 static int
1977 rm_coord_get(void *priv_data, struct coord *c, int count)
1978 {
1979         struct map_rect_priv *mr = priv_data;
1980         struct route_path_segment *seg = mr->seg;
1981         int i,rc=0;
1982         struct route *r = mr->mpriv->route;
1983         enum projection pro = route_projection(r);
1984
1985         if (! seg)
1986                 return 0;
1987         for (i=0; i < count; i++) {
1988                 if (mr->last_coord >= seg->ncoords)
1989                         break;
1990                 if (i >= seg->ncoords)
1991                         break;
1992                 if (pro != projection_mg)
1993                         transform_from_to(&seg->c[mr->last_coord++], pro,
1994                                 &c[i],projection_mg);
1995                 else
1996                         c[i] = seg->c[mr->last_coord++];
1997                 rc++;
1998         }
1999         dbg(1,"return %d\n",rc);
2000         return rc;
2001 }
2002
2003 static struct item_methods methods_route_item = {
2004         rm_coord_rewind,
2005         rm_coord_get,
2006         rm_attr_rewind,
2007         rm_attr_get,
2008 };
2009
2010 static void
2011 rp_attr_rewind(void *priv_data)
2012 {
2013         struct map_rect_priv *mr = priv_data;
2014         mr->attr_next = attr_label;
2015 }
2016
2017 static int
2018 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2019 {
2020         struct map_rect_priv *mr = priv_data;
2021         struct route_graph_point *p = mr->point;
2022         if (mr->item.type != type_rg_point)
2023                 return 0;
2024         switch (attr_type) {
2025         case attr_any:
2026                 while (mr->attr_next != attr_none) {
2027                         if (rp_attr_get(priv_data, mr->attr_next, attr))
2028                                 return 1;
2029                 }
2030                 return 0;
2031         case attr_label:
2032                 attr->type = attr_label;
2033                 if (mr->str)
2034                         g_free(mr->str);
2035                 if (p->value != INT_MAX)
2036                         mr->str=g_strdup_printf("%d", p->value);
2037                 else
2038                         mr->str=g_strdup("-");
2039                 attr->u.str = mr->str;
2040                 mr->attr_next=attr_none;
2041                 return 1;
2042         case attr_debug:
2043                 attr->type = attr_debug;
2044                 if (mr->str)
2045                         g_free(mr->str);
2046                 mr->str=g_strdup_printf("x=%d y=%d", p->c.x, p->c.y);
2047                 attr->u.str = mr->str;
2048                 mr->attr_next=attr_none;
2049                 return 1;
2050         default:
2051                 mr->attr_next=attr_none;
2052                 attr->type=attr_none;
2053                 return 0;
2054         }
2055 }
2056
2057 static int
2058 rp_coord_get(void *priv_data, struct coord *c, int count)
2059 {
2060         struct map_rect_priv *mr = priv_data;
2061         struct route_graph_point *p = mr->point;
2062         struct route_graph_segment *seg = mr->rseg;
2063         int rc = 0,i,dir;
2064         struct route *r = mr->mpriv->route;
2065         enum projection pro = route_projection(r);
2066
2067         for (i=0; i < count; i++) {
2068                 if (mr->item.type == type_rg_point) {
2069                         if (mr->last_coord >= 1)
2070                                 break;
2071                         if (pro != projection_mg)
2072                                 transform_from_to(&p->c, pro,
2073                                         &c[i],projection_mg);
2074                         else
2075                                 c[i] = p->c;
2076                 } else {
2077                         if (mr->last_coord >= 2)
2078                                 break;
2079                         dir=0;
2080                         if (seg->end->seg == seg)
2081                                 dir=1;
2082                         if (mr->last_coord)
2083                                 dir=1-dir;
2084                         if (dir) {
2085                                 if (pro != projection_mg)
2086                                         transform_from_to(&seg->end->c, pro,
2087                                                 &c[i],projection_mg);
2088                                 else
2089                                         c[i] = seg->end->c;
2090                         } else {
2091                                 if (pro != projection_mg)
2092                                         transform_from_to(&seg->start->c, pro,
2093                                                 &c[i],projection_mg);
2094                                 else
2095                                         c[i] = seg->start->c;
2096                         }
2097                 }
2098                 mr->last_coord++;
2099                 rc++;
2100         }
2101         return rc;
2102 }
2103
2104 static struct item_methods methods_point_item = {
2105         rm_coord_rewind,
2106         rp_coord_get,
2107         rp_attr_rewind,
2108         rp_attr_get,
2109 };
2110
2111 static void
2112 rm_destroy(struct map_priv *priv)
2113 {
2114         g_free(priv);
2115 }
2116
2117 static struct map_rect_priv *
2118 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
2119 {
2120         struct map_rect_priv * mr;
2121         dbg(1,"enter\n");
2122         if (! route_get_pos(priv->route))
2123                 return NULL;
2124         if (! route_get_dst(priv->route))
2125                 return NULL;
2126         if (! priv->route->path2)
2127                 return NULL;
2128         mr=g_new0(struct map_rect_priv, 1);
2129         mr->mpriv = priv;
2130         mr->item.priv_data = mr;
2131         mr->item.type = type_street_route;
2132         mr->item.meth = &methods_route_item;
2133         mr->seg_next=priv->route->path2->path;
2134         return mr;
2135 }
2136
2137 static struct map_rect_priv *
2138 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
2139 {
2140         struct map_rect_priv * mr;
2141         dbg(1,"enter\n");
2142         if (! priv->route->graph || ! priv->route->graph->route_points)
2143                 return NULL;
2144         mr=g_new0(struct map_rect_priv, 1);
2145         mr->mpriv = priv;
2146         mr->item.priv_data = mr;
2147         mr->item.type = type_rg_point;
2148         mr->item.meth = &methods_point_item;
2149         return mr;
2150 }
2151
2152 static void
2153 rm_rect_destroy(struct map_rect_priv *mr)
2154 {
2155         if (mr->str)
2156                 g_free(mr->str);
2157         g_free(mr);
2158 }
2159
2160 static struct item *
2161 rp_get_item(struct map_rect_priv *mr)
2162 {
2163         struct route *r = mr->mpriv->route;
2164         struct route_graph_point *p = mr->point;
2165         struct route_graph_segment *seg = mr->rseg;
2166
2167         if (mr->item.type == type_rg_point) {
2168                 if (!p)
2169                         p = r->graph->route_points;
2170                 else
2171                         p = p->next;
2172                 if (p) {
2173                         mr->point = p;
2174                         mr->item.id_lo++;
2175                         rm_coord_rewind(mr);
2176                         rp_attr_rewind(mr);
2177                         return &mr->item;
2178                 } else
2179                         mr->item.type = type_rg_segment;
2180         }
2181         if (!seg)
2182                 seg=r->graph->route_segments;
2183         else
2184                 seg=seg->next;
2185         if (seg) {
2186                 mr->rseg = seg;
2187                 mr->item.id_lo++;
2188                 rm_coord_rewind(mr);
2189                 rp_attr_rewind(mr);
2190                 return &mr->item;
2191         }
2192         return NULL;
2193
2194 }
2195
2196 static struct item *
2197 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2198 {
2199         struct item *ret=NULL;
2200         while (id_lo-- > 0)
2201                 ret=rp_get_item(mr);
2202         return ret;
2203 }
2204
2205
2206 static struct item *
2207 rm_get_item(struct map_rect_priv *mr)
2208 {
2209         dbg(1,"enter\n", mr->pos);
2210
2211         mr->seg=mr->seg_next;
2212         if (! mr->seg)
2213                 return NULL;
2214         mr->seg_next=mr->seg->next;
2215         mr->last_coord = 0;
2216         mr->item.id_lo++;
2217         rm_attr_rewind(mr);
2218         return &mr->item;
2219 }
2220
2221 static struct item *
2222 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2223 {
2224         struct item *ret=NULL;
2225         while (id_lo-- > 0)
2226                 ret=rm_get_item(mr);
2227         return ret;
2228 }
2229
2230 static struct map_methods route_meth = {
2231         projection_mg,
2232         "utf-8",
2233         rm_destroy,
2234         rm_rect_new,
2235         rm_rect_destroy,
2236         rm_get_item,
2237         rm_get_item_byid,
2238         NULL,
2239         NULL,
2240         NULL,
2241 };
2242
2243 static struct map_methods route_graph_meth = {
2244         projection_mg,
2245         "utf-8",
2246         rm_destroy,
2247         rp_rect_new,
2248         rm_rect_destroy,
2249         rp_get_item,
2250         rp_get_item_byid,
2251         NULL,
2252         NULL,
2253         NULL,
2254 };
2255
2256 void
2257 route_toggle_routegraph_display(struct route *route)
2258 {
2259         if (route->flags & RF_SHOWGRAPH) {
2260                 route->flags &= ~RF_SHOWGRAPH;
2261         } else {
2262                 route->flags |= RF_SHOWGRAPH;
2263         }
2264 }
2265
2266 static struct map_priv *
2267 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
2268 {
2269         struct map_priv *ret;
2270         struct attr *route_attr;
2271
2272         route_attr=attr_search(attrs, NULL, attr_route);
2273         if (! route_attr)
2274                 return NULL;
2275         ret=g_new0(struct map_priv, 1);
2276         if (graph)
2277                 *meth=route_graph_meth;
2278         else
2279                 *meth=route_meth;
2280         ret->route=route_attr->u.route;
2281
2282         return ret;
2283 }
2284
2285 static struct map_priv *
2286 route_map_new(struct map_methods *meth, struct attr **attrs)
2287 {
2288         return route_map_new_helper(meth, attrs, 0);
2289 }
2290
2291 static struct map_priv *
2292 route_graph_map_new(struct map_methods *meth, struct attr **attrs)
2293 {
2294         return route_map_new_helper(meth, attrs, 1);
2295 }
2296
2297 static struct map *
2298 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
2299 {
2300         if (! *map)
2301                 *map=map_new(NULL, (struct attr*[]){
2302                                 &(struct attr){attr_type,{type}},
2303                                 &(struct attr){attr_route,.u.route=this_},
2304                                 &(struct attr){attr_data,{""}},
2305                                 &(struct attr){attr_description,{description}},
2306                                 NULL});
2307         return *map;
2308 }
2309
2310 struct map *
2311 route_get_map(struct route *this_)
2312 {
2313         return route_get_map_helper(this_, &this_->map, "route","Route");
2314 }
2315
2316
2317 struct map *
2318 route_get_graph_map(struct route *this_)
2319 {
2320         return route_get_map_helper(this_, &this_->graph_map, "route_graph","Route Graph");
2321 }
2322
2323 void
2324 route_set_projection(struct route *this_, enum projection pro)
2325 {
2326 }
2327
2328 void
2329 route_init(void)
2330 {
2331         plugin_register_map_type("route", route_map_new);
2332         plugin_register_map_type("route_graph", route_graph_map_new);
2333 }