navit/navit/route.c

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