git.maemo.org Git - navit-package/blob - navit/route.c

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