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