navit/navit/route.c

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