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