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