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_slice.h"
  52 #include "config.h"
  53 #include "point.h"
  54 #include "graphics.h"
  55 #include "profile.h"
  56 #include "coord.h"
  57 #include "projection.h"
  58 #include "item.h"
  59 #include "map.h"
  60 #include "mapset.h"
  61 #include "route.h"
  62 #include "track.h"
  63 #include "transform.h"
  64 #include "plugin.h"
  65 #include "fib.h"
  66 #include "event.h"
  67 #include "callback.h"
  68 #include "vehicle.h"
  69 #include "vehicleprofile.h"
  70 #include "roadprofile.h"
  71 #include "debug.h"
  72
  73 struct map_priv {
  74         struct route *route;
  75 };
  76
  77 int debug_route=0;
  78
  79 /**
  80  * @brief A point in the route graph
  81  *
  82  * This represents a point in the route graph. A point usually connects two or more segments,
  83  * but there are also points which don't do that (e.g. at the end of a dead-end).
  84  */
  85 struct route_graph_point {
  86         struct route_graph_point *hash_next; /**< Pointer to a chained hashlist of all route_graph_points with this hash */
  87         struct route_graph_segment *start;       /**< Pointer to a list of segments of which this point is the start. The links
  88                                                                                   *  of this linked-list are in route_graph_segment->start_next.*/
  89         struct route_graph_segment *end;         /**< Pointer to a list of segments of which this pointer is the end. The links
  90                                                                                   *  of this linked-list are in route_graph_segment->end_next. */
  91         struct route_graph_segment *seg;         /**< Pointer to the segment one should use to reach the destination at
  92                                                                                   *  least costs */
  93         struct fibheap_el *el;                           /**< When this point is put on a Fibonacci heap, this is a pointer
  94                                                                                   *  to this point's heap-element */
  95         int value;                                                       /**< The cost at which one can reach the destination from this point on */
  96         struct coord c;                                          /**< Coordinates of this point */
  97         int flags;                                              /**< Flags for this point (eg traffic distortion) */
  98 };
  99
 100 #define RP_TRAFFIC_DISTORTION 1
 101 #define RP_TURN_RESTRICTION 2
 102 #define RP_TURN_RESTRICTION_RESOLVED 4
 103
 104 /**
 105  * @brief A segment in the route graph or path
 106  *
 107  * This is a segment in the route graph or path. A segment represents a driveable way.
 108  */
 109
 110 struct route_segment_data {
 111         struct item item;                                                       /**< The item (e.g. street) that this segment represents. */
 112         int flags;
 113         int len;                                                                        /**< Length of this segment */
 114         /*NOTE: After a segment, various fields may follow, depending on what flags are set. Order of fields:
 115                                 1.) maxspeed                    Maximum allowed speed on this segment. Present if AF_SPEED_LIMIT is set.
 116                                 2.) offset                              If the item is segmented (i.e. represented by more than one segment), this
 117                                                                                 indicates the position of this segment in the item. Present if AF_SEGMENTED is set.
 118          */
 119 };
 120
 121
 122 struct size_weight_limit {
 123         int width;
 124         int length;
 125         int height;
 126         int weight;
 127         int axle_weight;
 128 };
 129
 130 #define RSD_OFFSET(x) *((int *)route_segment_data_field_pos((x), attr_offset))
 131 #define RSD_MAXSPEED(x) *((int *)route_segment_data_field_pos((x), attr_maxspeed))
 132 #define RSD_SIZE_WEIGHT(x) *((struct size_weight_limit *)route_segment_data_field_pos((x), attr_vehicle_width))
 133 #define RSD_DANGEROUS_GOODS(x) *((int *)route_segment_data_field_pos((x), attr_vehicle_dangerous_goods))
 134
 135
 136 struct route_graph_segment_data {
 137         struct item *item;
 138         int offset;
 139         int flags;
 140         int len;
 141         int maxspeed;
 142         struct size_weight_limit size_weight;
 143         int dangerous_goods;
 144 };
 145
 146 /**
 147  * @brief A segment in the route graph
 148  *
 149  * This is a segment in the route graph. A segment represents a driveable way.
 150  */
 151 struct route_graph_segment {
 152         struct route_graph_segment *next;                       /**< Linked-list pointer to a list of all route_graph_segments */
 153         struct route_graph_segment *start_next;         /**< Pointer to the next element in the list of segments that start at the
 154                                                                                                  *  same point. Start of this list is in route_graph_point->start. */
 155         struct route_graph_segment *end_next;           /**< Pointer to the next element in the list of segments that end at the
 156                                                                                                  *  same point. Start of this list is in route_graph_point->end. */
 157         struct route_graph_point *start;                        /**< Pointer to the point this segment starts at. */
 158         struct route_graph_point *end;                          /**< Pointer to the point this segment ends at. */
 159         struct route_segment_data data;                         /**< The segment data */
 160 };
 161
 162 /**
 163  * @brief A traffic distortion
 164  *
 165  * This is distortion in the traffic where you can't drive as fast as usual or have to wait for some time
 166  */
 167 struct route_traffic_distortion {
 168         int maxspeed;                                   /**< Maximum speed possible in km/h */
 169         int delay;                                      /**< Delay in tenths of seconds */
 170 };
 171
 172 /**
 173  * @brief A segment in the route path
 174  *
 175  * This is a segment in the route path.
 176  */
 177 struct route_path_segment {
 178         struct route_path_segment *next;        /**< Pointer to the next segment in the path */
 179         struct route_segment_data *data;        /**< The segment data */
 180         int direction;                                          /**< Order in which the coordinates are ordered. >0 means "First
 181                                                                                  *  coordinate of the segment is the first coordinate of the item", <=0
 182                                                                                  *  means reverse. */
 183         unsigned ncoords;                                       /**< How many coordinates does this segment have? */
 184         struct coord c[0];                                      /**< Pointer to the ncoords coordinates of this segment */
 185         /* WARNING: There will be coordinates following here, so do not create new fields after c! */
 186 };
 187
 188 /**
 189  * @brief Usually represents a destination or position
 190  *
 191  * This struct usually represents a destination or position
 192  */
 193 struct route_info {
 194         struct coord c;                  /**< The actual destination / position */
 195         struct coord lp;                 /**< The nearest point on a street to c */
 196         int pos;                                 /**< The position of lp within the coords of the street */
 197         int lenpos;                      /**< Distance between lp and the end of the street */
 198         int lenneg;                      /**< Distance between lp and the start of the street */
 199         int lenextra;                    /**< Distance between lp and c */
 200         int percent;                     /**< ratio of lenneg to lenght of whole street in percent */
 201         struct street_data *street; /**< The street lp is on */
 202         int street_direction;   /**< Direction of vehicle on street -1 = Negative direction, 1 = Positive direction, 0 = Unknown */
 203         int dir;                /**< Direction to take when following the route -1 = Negative direction, 1 = Positive direction */
 204 };
 205
 206 /**
 207  * @brief A complete route path
 208  *
 209  * This structure describes a whole routing path
 210  */
 211 struct route_path {
 212         int in_use;                                             /**< The path is in use and can not be updated */
 213         int update_required;                                    /**< The path needs to be updated after it is no longer in use */
 214         int updated;                                            /**< The path has only been updated */
 215         int path_time;                                          /**< Time to pass the path */
 216         int path_len;                                           /**< Length of the path */
 217         struct route_path_segment *path;                        /**< The first segment in the path, i.e. the segment one should
 218                                                                                                  *  drive in next */
 219         struct route_path_segment *path_last;           /**< The last segment in the path */
 220         /* XXX: path_hash is not necessery now */
 221         struct item_hash *path_hash;                            /**< A hashtable of all the items represented by this route's segements */
 222         struct route_path *next;                                /**< Next route path in case of intermediate destinations */
 223 };
 224
 225 /**
 226  * @brief A complete route
 227  *
 228  * This struct holds all information about a route.
 229  */
 230 struct route {
 231         struct mapset *ms;                      /**< The mapset this route is built upon */
 232         unsigned flags;
 233         struct route_info *pos;         /**< Current position within this route */
 234         GList *destinations;            /**< Destinations of the route */
 235         struct route_info *current_dst; /**< Current destination */
 236
 237         struct route_graph *graph;      /**< Pointer to the route graph */
 238         struct route_path *path2;       /**< Pointer to the route path */
 239         struct map *map;
 240         struct map *graph_map;
 241         struct callback * route_graph_done_cb ; /**< Callback when route graph is done */
 242         struct callback * route_graph_flood_done_cb ; /**< Callback when route graph flooding is done */
 243         struct callback_list *cbl2;     /**< Callback list to call when route changes */
 244         int destination_distance;       /**< Distance to the destination at which the destination is considered "reached" */
 245         struct vehicleprofile *vehicleprofile; /**< Routing preferences */
 246         int route_status;               /**< Route Status */
 247         int link_path;                  /**< Link paths over multiple waypoints together */
 248         struct pcoord pc;
 249         struct vehicle *v;
 250 };
 251
 252 /**
 253  * @brief A complete route graph
 254  *
 255  * This structure describes a whole routing graph
 256  */
 257 struct route_graph {
 258         int busy;                                       /**< The graph is being built */
 259         struct map_selection *sel;                      /**< The rectangle selection for the graph */
 260         struct mapset_handle *h;                        /**< Handle to the mapset */
 261         struct map *m;                                  /**< Pointer to the currently active map */
 262         struct map_rect *mr;                            /**< Pointer to the currently active map rectangle */
 263         struct vehicleprofile *vehicleprofile;          /**< The vehicle profile */
 264         struct callback *idle_cb;                       /**< Idle callback to process the graph */
 265         struct callback *done_cb;                       /**< Callback when graph is done */
 266         struct event_idle *idle_ev;                     /**< The pointer to the idle event */
 267         struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */
 268 #define HASH_SIZE 8192
 269         struct route_graph_point *hash[HASH_SIZE];      /**< A hashtable containing all route_graph_points in this graph */
 270 };
 271
 272 #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
 273
 274 /**
 275  * @brief Iterator to iterate through all route graph segments in a route graph point
 276  *
 277  * This structure can be used to iterate through all route graph segments connected to a
 278  * route graph point. Use this with the rp_iterator_* functions.
 279  */
 280 struct route_graph_point_iterator {
 281         struct route_graph_point *p;            /**< The route graph point whose segments should be iterated */
 282         int end;                                                        /**< Indicates if we have finished iterating through the "start" segments */
 283         struct route_graph_segment *next;       /**< The next segment to be returned */
 284 };
 285
 286 struct attr_iter {
 287         union {
 288                 GList *list;
 289         } u;
 290 };
 291
 292 static struct route_info * route_find_nearest_street(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *c);
 293 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
 294 static void route_graph_update(struct route *this, struct callback *cb, int async);
 295 static void route_graph_build_done(struct route_graph *rg, int cancel);
 296 static struct route_path *route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct vehicleprofile *profile);
 297 static void route_process_street_graph(struct route_graph *this, struct item *item, struct vehicleprofile *profile);
 298 static void route_graph_destroy(struct route_graph *this);
 299 static void route_path_update(struct route *this, int cancel, int async);
 300 static int route_time_seg(struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist);
 301 static void route_graph_flood(struct route_graph *this, struct route_info *dst, struct vehicleprofile *profile, struct callback *cb);
 302 static void route_graph_reset(struct route_graph *this);
 303
 304
 305 /**
 306  * @brief Returns the projection used for this route
 307  *
 308  * @param route The route to return the projection for
 309  * @return The projection used for this route
 310  */
 311 static enum projection route_projection(struct route *route)
 312 {
 313         struct street_data *street;
 314         struct route_info *dst=route_get_dst(route);
 315         if (!route->pos && !dst)
 316                 return projection_none;
 317         street = route->pos ? route->pos->street : dst->street;
 318         if (!street || !street->item.map)
 319                 return projection_none;
 320         return map_projection(street->item.map);
 321 }
 322
 323 /**
 324  * @brief Creates a new graph point iterator
 325  *
 326  * This function creates a new route graph point iterator, that can be used to
 327  * iterate through all segments connected to the point.
 328  *
 329  * @param p The route graph point to create the iterator from
 330  * @return A new iterator.
 331  */
 332 static struct route_graph_point_iterator
 333 rp_iterator_new(struct route_graph_point *p)
 334 {
 335         struct route_graph_point_iterator it;
 336
 337         it.p = p;
 338         if (p->start) {
 339                 it.next = p->start;
 340                 it.end = 0;
 341         } else {
 342                 it.next = p->end;
 343                 it.end = 1;
 344         }
 345
 346         return it;
 347 }
 348
 349 /**
 350  * @brief Gets the next segment connected to a route graph point from an iterator
 351  *
 352  * @param it The route graph point iterator to get the segment from
 353  * @return The next segment or NULL if there are no more segments
 354  */
 355 static struct route_graph_segment
 356 *rp_iterator_next(struct route_graph_point_iterator *it)
 357 {
 358         struct route_graph_segment *ret;
 359
 360         ret = it->next;
 361         if (!ret) {
 362                 return NULL;
 363         }
 364
 365         if (!it->end) {
 366                 if (ret->start_next) {
 367                         it->next = ret->start_next;
 368                 } else {
 369                         it->next = it->p->end;
 370                         it->end = 1;
 371                 }
 372         } else {
 373                 it->next = ret->end_next;
 374         }
 375
 376         return ret;
 377 }
 378
 379 /**
 380  * @brief Checks if the last segment returned from a route_graph_point_iterator comes from the end
 381  *
 382  * @param it The route graph point iterator to be checked
 383  * @return 1 if the last segment returned comes from the end of the route graph point, 0 otherwise
 384  */
 385 static int
 386 rp_iterator_end(struct route_graph_point_iterator *it) {
 387         if (it->end && (it->next != it->p->end)) {
 388                 return 1;
 389         } else {
 390                 return 0;
 391         }
 392 }
 393
 394 /**
 395  * @brief Destroys a route_path
 396  *
 397  * @param this The route_path to be destroyed
 398  */
 399 static void
 400 route_path_destroy(struct route_path *this, int recurse)
 401 {
 402         struct route_path_segment *c,*n;
 403         struct route_path *next;
 404         while (this) {
 405                 next=this->next;
 406                 if (this->path_hash) {
 407                         item_hash_destroy(this->path_hash);
 408                         this->path_hash=NULL;
 409                 }
 410                 c=this->path;
 411                 while (c) {
 412                         n=c->next;
 413                         g_free(c);
 414                         c=n;
 415                 }
 416                 this->in_use--;
 417                 if (!this->in_use)
 418                         g_free(this);
 419                 if (!recurse)
 420                         break;
 421                 this=next;
 422         }
 423 }
 424
 425 /**
 426  * @brief Creates a completely new route structure
 427  *
 428  * @param attrs Not used
 429  * @return The newly created route
 430  */
 431 struct route *
 432 route_new(struct attr *parent, struct attr **attrs)
 433 {
 434         struct route *this=g_new0(struct route, 1);
 435         struct attr dest_attr;
 436
 437         if (attr_generic_get_attr(attrs, NULL, attr_destination_distance, &dest_attr, NULL)) {
 438                 this->destination_distance = dest_attr.u.num;
 439         } else {
 440                 this->destination_distance = 50; // Default value
 441         }
 442         this->cbl2=callback_list_new();
 443
 444         return this;
 445 }
 446
 447 /**
 448  * @brief Checks if a segment is part of a roundabout
 449  *
 450  * This function checks if a segment is part of a roundabout.
 451  *
 452  * @param seg The segment to be checked
 453  * @param level How deep to scan the route graph
 454  * @param direction Set this to 1 if we're entering the segment through its end, to 0 otherwise
 455  * @param origin Used internally, set to NULL
 456  * @return 1 If a roundabout was detected, 0 otherwise
 457  */
 458 static int
 459 route_check_roundabout(struct route_graph_segment *seg, int level, int direction, struct route_graph_segment *origin)
 460 {
 461         struct route_graph_point_iterator it,it2;
 462         struct route_graph_segment *cur;
 463         int count=0;
 464
 465         if (!level) {
 466                 return 0;
 467         }
 468         if (!direction && !(seg->data.flags & AF_ONEWAY)) {
 469                 return 0;
 470         }
 471         if (direction && !(seg->data.flags & AF_ONEWAYREV)) {
 472                 return 0;
 473         }
 474         if (seg->data.flags & AF_ROUNDABOUT_VALID)
 475                 return 0;
 476
 477         if (!origin) {
 478                 origin = seg;
 479         }
 480
 481         if (!direction) {
 482                 it = rp_iterator_new(seg->end);
 483         } else {
 484                 it = rp_iterator_new(seg->start);
 485         }
 486         it2=it;
 487
 488         while ((cur = rp_iterator_next(&it2)))
 489                 count++;
 490
 491         if (count > 3)
 492                 return 0;
 493         cur = rp_iterator_next(&it);
 494         while (cur) {
 495                 if (cur == seg) {
 496                         cur = rp_iterator_next(&it);
 497                         continue;
 498                 }
 499
 500                 if (cur->data.item.type != origin->data.item.type) {
 501                         // This street is of another type, can't be part of the roundabout
 502                         cur = rp_iterator_next(&it);
 503                         continue;
 504                 }
 505
 506                 if (cur == origin) {
 507                         seg->data.flags |= AF_ROUNDABOUT;
 508                         return 1;
 509                 }
 510
 511                 if (route_check_roundabout(cur, (level-1), rp_iterator_end(&it), origin)) {
 512                         seg->data.flags |= AF_ROUNDABOUT;
 513                         return 1;
 514                 }
 515
 516                 cur = rp_iterator_next(&it);
 517         }
 518
 519         return 0;
 520 }
 521
 522 /**
 523  * @brief Sets the mapset of the route passwd
 524  *
 525  * @param this The route to set the mapset for
 526  * @param ms The mapset to set for this route
 527  */
 528 void
 529 route_set_mapset(struct route *this, struct mapset *ms)
 530 {
 531         this->ms=ms;
 532 }
 533
 534 /**
 535  * @brief Sets the vehicle profile of a route
 536  *
 537  * @param this The route to set the profile for
 538  * @param prof The vehicle profile
 539  */
 540
 541 void
 542 route_set_profile(struct route *this, struct vehicleprofile *prof)
 543 {
 544         if (this->vehicleprofile != prof) {
 545                 this->vehicleprofile=prof;
 546                 route_path_update(this, 1, 1);
 547         }
 548 }
 549
 550 /**
 551  * @brief Returns the mapset of the route passed
 552  *
 553  * @param this The route to get the mapset of
 554  * @return The mapset of the route passed
 555  */
 556 struct mapset *
 557 route_get_mapset(struct route *this)
 558 {
 559         return this->ms;
 560 }
 561
 562 /**
 563  * @brief Returns the current position within the route passed
 564  *
 565  * @param this The route to get the position for
 566  * @return The position within the route passed
 567  */
 568 struct route_info *
 569 route_get_pos(struct route *this)
 570 {
 571         return this->pos;
 572 }
 573
 574 /**
 575  * @brief Returns the destination of the route passed
 576  *
 577  * @param this The route to get the destination for
 578  * @return The destination of the route passed
 579  */
 580 struct route_info *
 581 route_get_dst(struct route *this)
 582 {
 583         struct route_info *dst=NULL;
 584
 585         if (this->destinations)
 586                 dst=g_list_last(this->destinations)->data;
 587         return dst;
 588 }
 589
 590 /**
 591  * @brief Checks if the path is calculated for the route passed
 592  *
 593  * @param this The route to check
 594  * @return True if the path is calculated, false if not
 595  */
 596 int
 597 route_get_path_set(struct route *this)
 598 {
 599         return this->path2 != NULL;
 600 }
 601
 602 /**
 603  * @brief Checks if the route passed contains a certain item within the route path
 604  *
 605  * This function checks if a certain items exists in the path that navit will guide
 606  * the user to his destination. It does *not* check if this item exists in the route
 607  * graph!
 608  *
 609  * @param this The route to check for this item
 610  * @param item The item to search for
 611  * @return True if the item was found, false if the item was not found or the route was not calculated
 612  */
 613 int
 614 route_contains(struct route *this, struct item *item)
 615 {
 616         if (! this->path2 || !this->path2->path_hash)
 617                 return 0;
 618         if (item_hash_lookup(this->path2->path_hash, item))
 619                 return 1;
 620         if (! this->pos || !this->pos->street)
 621                 return 0;
 622         return item_is_equal(this->pos->street->item, *item);
 623
 624 }
 625
 626 static struct route_info *
 627 route_next_destination(struct route *this)
 628 {
 629         if (!this->destinations)
 630                 return NULL;
 631         return this->destinations->data;
 632 }
 633
 634 /**
 635  * @brief Checks if a route has reached its destination
 636  *
 637  * @param this The route to be checked
 638  * @return True if the destination is "reached", false otherwise.
 639  */
 640 int
 641 route_destination_reached(struct route *this)
 642 {
 643         struct street_data *sd = NULL;
 644         enum projection pro;
 645         struct route_info *dst=route_next_destination(this);
 646
 647         if (!this->pos)
 648                 return 0;
 649         if (!dst)
 650                 return 0;
 651
 652         sd = this->pos->street;
 653
 654         if (!this->path2) {
 655                 return 0;
 656         }
 657
 658         if (!item_is_equal(this->pos->street->item, dst->street->item)) {
 659                 return 0;
 660         }
 661
 662         if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= dst->lenneg)) { // We would have to drive against the one-way road
 663                 return 0;
 664         }
 665         if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= dst->lenpos)) {
 666                 return 0;
 667         }
 668         pro=route_projection(this);
 669         if (pro == projection_none)
 670                 return 0;
 671
 672         if (transform_distance(pro, &this->pos->c, &dst->lp) > this->destination_distance) {
 673                 return 0;
 674         }
 675
 676         if (g_list_next(this->destinations))
 677                 return 1;
 678         else
 679                 return 2;
 680 }
 681
 682 static struct route_info *
 683 route_previous_destination(struct route *this)
 684 {
 685         GList *l=g_list_find(this->destinations, this->current_dst);
 686         if (!l)
 687                 return this->pos;
 688         l=g_list_previous(l);
 689         if (!l)
 690                 return this->pos;
 691         return l->data;
 692 }
 693
 694 static void
 695 route_path_update_done(struct route *this, int new_graph)
 696 {
 697         struct route_path *oldpath=this->path2;
 698         struct attr route_status;
 699         struct route_info *prev_dst;
 700         route_status.type=attr_route_status;
 701         if (this->path2 && (this->path2->in_use>1)) {
 702                 this->path2->update_required=1+new_graph;
 703                 return;
 704         }
 705         route_status.u.num=route_status_building_path;
 706         route_set_attr(this, &route_status);
 707         prev_dst=route_previous_destination(this);
 708         if (this->link_path) {
 709                 this->path2=route_path_new(this->graph, NULL, prev_dst, this->current_dst, this->vehicleprofile);
 710                 if (this->path2)
 711                     this->path2->next=oldpath;
 712         } else {
 713                 this->path2=route_path_new(this->graph, oldpath, prev_dst, this->current_dst, this->vehicleprofile);
 714                 if (oldpath && this->path2) {
 715                         this->path2->next=oldpath->next;
 716                         route_path_destroy(oldpath,0);
 717                 }
 718         }
 719         if (this->path2) {
 720                 struct route_path_segment *seg=this->path2->path;
 721                 int path_time=0,path_len=0;
 722                 while (seg) {
 723                         /* FIXME */
 724                         int seg_time=route_time_seg(this->vehicleprofile, seg->data, NULL);
 725                         if (seg_time == INT_MAX) {
 726                                 dbg(1,"error\n");
 727                         } else
 728                                 path_time+=seg_time;
 729                         path_len+=seg->data->len;
 730                         seg=seg->next;
 731                 }
 732                 this->path2->path_time=path_time;
 733                 this->path2->path_len=path_len;
 734                 if (prev_dst != this->pos) {
 735                         this->link_path=1;
 736                         this->current_dst=prev_dst;
 737                         route_graph_reset(this->graph);
 738                         route_graph_flood(this->graph, this->current_dst, this->vehicleprofile, this->route_graph_flood_done_cb);
 739                         return;
 740                 }
 741                 if (!new_graph && this->path2->updated)
 742                         route_status.u.num=route_status_path_done_incremental;
 743                 else
 744                         route_status.u.num=route_status_path_done_new;
 745         } else
 746                 route_status.u.num=route_status_not_found;
 747         this->link_path=0;
 748         route_set_attr(this, &route_status);
 749 }
 750
 751 /**
 752  * @brief Updates the route graph and the route path if something changed with the route
 753  *
 754  * This will update the route graph and the route path of the route if some of the
 755  * route's settings (destination, position) have changed.
 756  *
 757  * @attention For this to work the route graph has to be destroyed if the route's
 758  * @attention destination is changed somewhere!
 759  *
 760  * @param this The route to update
 761  */
 762 static void
 763 route_path_update(struct route *this, int cancel, int async)
 764 {
 765         dbg(1,"enter %d\n", cancel);
 766         if (! this->pos || ! this->destinations) {
 767                 dbg(1,"destroy\n");
 768                 route_path_destroy(this->path2,1);
 769                 this->path2 = NULL;
 770                 return;
 771         }
 772         if (cancel) {
 773                 route_graph_destroy(this->graph);
 774                 this->graph=NULL;
 775         }
 776         /* the graph is destroyed when setting the destination */
 777         if (this->graph) {
 778                 if (this->graph->busy) {
 779                         dbg(1,"busy building graph\n");
 780                         return;
 781                 }
 782                 // we can try to update
 783                 dbg(1,"try update\n");
 784                 route_path_update_done(this, 0);
 785         } else {
 786                 route_path_destroy(this->path2,1);
 787                 this->path2 = NULL;
 788         }
 789         if (!this->graph || !this->path2) {
 790                 dbg(1,"rebuild graph\n");
 791                 if (! this->route_graph_flood_done_cb)
 792                         this->route_graph_flood_done_cb=callback_new_2(callback_cast(route_path_update_done), this, (long)1);
 793                 dbg(1,"route_graph_update\n");
 794                 route_graph_update(this, this->route_graph_flood_done_cb, async);
 795         }
 796 }
 797
 798 /**
 799  * @brief This will calculate all the distances stored in a route_info
 800  *
 801  * @param ri The route_info to calculate the distances for
 802  * @param pro The projection used for this route
 803  */
 804 static void
 805 route_info_distances(struct route_info *ri, enum projection pro)
 806 {
 807         int npos=ri->pos+1;
 808         struct street_data *sd=ri->street;
 809         /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
 810         ri->lenextra=transform_distance(pro, &ri->lp, &ri->c);
 811         ri->lenneg=transform_polyline_length(pro, sd->c, npos)+transform_distance(pro, &sd->c[ri->pos], &ri->lp);
 812         ri->lenpos=transform_polyline_length(pro, sd->c+npos, sd->count-npos)+transform_distance(pro, &sd->c[npos], &ri->lp);
 813         if (ri->lenneg || ri->lenpos)
 814                 ri->percent=(ri->lenneg*100)/(ri->lenneg+ri->lenpos);
 815         else
 816                 ri->percent=50;
 817 }
 818
 819 /**
 820  * @brief This sets the current position of the route passed
 821  *
 822  * This will set the current position of the route passed to the street that is nearest to the
 823  * passed coordinates. It also automatically updates the route.
 824  *
 825  * @param this The route to set the position of
 826  * @param pos Coordinates to set as position
 827  */
 828 void
 829 route_set_position(struct route *this, struct pcoord *pos)
 830 {
 831         if (this->pos)
 832                 route_info_free(this->pos);
 833         this->pos=NULL;
 834         this->pos=route_find_nearest_street(this->vehicleprofile, this->ms, pos);
 835
 836         // If there is no nearest street, bail out.
 837         if (!this->pos) return;
 838
 839         this->pos->street_direction=0;
 840         dbg(1,"this->pos=%p\n", this->pos);
 841         route_info_distances(this->pos, pos->pro);
 842         route_path_update(this, 0, 1);
 843 }
 844
 845 /**
 846  * @brief Sets a route's current position based on coordinates from tracking
 847  *
 848  * @param this The route to set the current position of
 849  * @param tracking The tracking to get the coordinates from
 850  */
 851 void
 852 route_set_position_from_tracking(struct route *this, struct tracking *tracking, enum projection pro)
 853 {
 854         struct coord *c;
 855         struct route_info *ret;
 856         struct street_data *sd;
 857
 858         dbg(2,"enter\n");
 859         c=tracking_get_pos(tracking);
 860         ret=g_new0(struct route_info, 1);
 861         if (!ret) {
 862                 printf("%s:Out of memory\n", __FUNCTION__);
 863                 return;
 864         }
 865         if (this->pos)
 866                 route_info_free(this->pos);
 867         this->pos=NULL;
 868         ret->c=*c;
 869         ret->lp=*c;
 870         ret->pos=tracking_get_segment_pos(tracking);
 871         ret->street_direction=tracking_get_street_direction(tracking);
 872         sd=tracking_get_street_data(tracking);
 873         if (sd) {
 874                 ret->street=street_data_dup(sd);
 875                 route_info_distances(ret, pro);
 876         }
 877         dbg(3,"position 0x%x,0x%x item 0x%x,0x%x direction %d pos %d lenpos %d lenneg %d\n",c->x,c->y,sd?sd->item.id_hi:0,sd?sd->item.id_lo:0,ret->street_direction,ret->pos,ret->lenpos,ret->lenneg);
 878         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?ret->street->item.id_hi:0, ret->street?ret->street->item.id_lo:0);
 879         dbg(3,"street 0=(0x%x,0x%x) %d=(0x%x,0x%x)\n", ret->street?ret->street->c[0].x:0, ret->street?ret->street->c[0].y:0, ret->street?ret->street->count-1:0, ret->street?ret->street->c[ret->street->count-1].x:0, ret->street?ret->street->c[ret->street->count-1].y:0);
 880         this->pos=ret;
 881         if (this->destinations)
 882                 route_path_update(this, 0, 1);
 883         dbg(2,"ret\n");
 884 }
 885
 886 /* Used for debuging of route_rect, what routing sees */
 887 struct map_selection *route_selection;
 888
 889 /**
 890  * @brief Returns a single map selection
 891  */
 892 struct map_selection *
 893 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
 894 {
 895         int dx,dy,sx=1,sy=1,d,m;
 896         struct map_selection *sel=g_new(struct map_selection, 1);
 897         if (!sel) {
 898                 printf("%s:Out of memory\n", __FUNCTION__);
 899                 return sel;
 900         }
 901         sel->order=order;
 902         sel->range.min=route_item_first;
 903         sel->range.max=route_item_last;
 904         dbg(1,"%p %p\n", c1, c2);
 905         dx=c1->x-c2->x;
 906         dy=c1->y-c2->y;
 907         if (dx < 0) {
 908                 sx=-1;
 909                 sel->u.c_rect.lu.x=c1->x;
 910                 sel->u.c_rect.rl.x=c2->x;
 911         } else {
 912                 sel->u.c_rect.lu.x=c2->x;
 913                 sel->u.c_rect.rl.x=c1->x;
 914         }
 915         if (dy < 0) {
 916                 sy=-1;
 917                 sel->u.c_rect.lu.y=c2->y;
 918                 sel->u.c_rect.rl.y=c1->y;
 919         } else {
 920                 sel->u.c_rect.lu.y=c1->y;
 921                 sel->u.c_rect.rl.y=c2->y;
 922         }
 923         if (dx*sx > dy*sy)
 924                 d=dx*sx;
 925         else
 926                 d=dy*sy;
 927         m=d*rel/100+abs;
 928         sel->u.c_rect.lu.x-=m;
 929         sel->u.c_rect.rl.x+=m;
 930         sel->u.c_rect.lu.y+=m;
 931         sel->u.c_rect.rl.y-=m;
 932         sel->next=NULL;
 933         return sel;
 934 }
 935
 936 /**
 937  * @brief Returns a list of map selections useable to create a route graph
 938  *
 939  * Returns a list of  map selections useable to get a  map rect from which items can be
 940  * retrieved to build a route graph. The selections are a rectangle with
 941  * c1 and c2 as two corners.
 942  *
 943  * @param c1 Corner 1 of the rectangle
 944  * @param c2 Corder 2 of the rectangle
 945  */
 946 static struct map_selection *
 947 route_calc_selection(struct coord *c, int count)
 948 {
 949         struct map_selection *ret,*sel;
 950         int i;
 951         struct coord_rect r;
 952
 953         if (!count)
 954                 return NULL;
 955         r.lu=c[0];
 956         r.rl=c[0];
 957         for (i = 1 ; i < count ; i++)
 958                 coord_rect_extend(&r, &c[i]);
 959         sel=route_rect(4, &r.lu, &r.rl, 25, 0);
 960         ret=sel;
 961         for (i = 0 ; i < count ; i++) {
 962                 sel->next=route_rect(8, &c[i], &c[i], 0, 40000);
 963                 sel=sel->next;
 964                 sel->next=route_rect(18, &c[i], &c[i], 0, 10000);
 965                 sel=sel->next;
 966         }
 967         /* route_selection=ret; */
 968         return ret;
 969 }
 970
 971 /**
 972  * @brief Destroys a list of map selections
 973  *
 974  * @param sel Start of the list to be destroyed
 975  */
 976 static void
 977 route_free_selection(struct map_selection *sel)
 978 {
 979         struct map_selection *next;
 980         while (sel) {
 981                 next=sel->next;
 982                 g_free(sel);
 983                 sel=next;
 984         }
 985 }
 986
 987
 988 static void
 989 route_clear_destinations(struct route *this_)
 990 {
 991         g_list_foreach(this_->destinations, (GFunc)route_info_free, NULL);
 992         g_list_free(this_->destinations);
 993         this_->destinations=NULL;
 994 }
 995
 996 /**
 997  * @brief Sets the destination of a route
 998  *
 999  * This sets the destination of a route to the street nearest to the coordinates passed
1000  * and updates the route.
1001  *
1002  * @param this The route to set the destination for
1003  * @param dst Coordinates to set as destination
1004  * @param count: Number of destinations (last one is final)
1005  * @param async: If set, do routing asynchronously
1006  */
1007
1008 void
1009 route_set_destinations(struct route *this, struct pcoord *dst, int count, int async)
1010 {
1011         struct attr route_status;
1012         struct route_info *dsti;
1013         int i;
1014         route_status.type=attr_route_status;
1015
1016         profile(0,NULL);
1017         route_clear_destinations(this);
1018         if (dst && count) {
1019                 for (i = 0 ; i < count ; i++) {
1020                         dsti=route_find_nearest_street(this->vehicleprofile, this->ms, &dst[i]);
1021                         if(dsti) {
1022                                 route_info_distances(dsti, dst->pro);
1023                                 this->destinations=g_list_append(this->destinations, dsti);
1024                         }
1025                 }
1026                 route_status.u.num=route_status_destination_set;
1027         } else
1028                 route_status.u.num=route_status_no_destination;
1029         callback_list_call_attr_1(this->cbl2, attr_destination, this);
1030         route_set_attr(this, &route_status);
1031         profile(1,"find_nearest_street");
1032
1033         /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
1034         route_graph_destroy(this->graph);
1035         this->graph=NULL;
1036         this->current_dst=route_get_dst(this);
1037         route_path_update(this, 1, async);
1038         profile(0,"end");
1039 }
1040
1041 int
1042 route_get_destinations(struct route *this, struct pcoord *pc, int count)
1043 {
1044         int ret=0;
1045         GList *l=this->destinations;
1046         while (l && ret < count) {
1047                 struct route_info *dst=l->data;
1048                 pc->x=dst->c.x;
1049                 pc->y=dst->c.y;
1050                 pc->pro=projection_mg; /* FIXME */
1051                 pc++;
1052                 ret++;
1053                 l=g_list_next(l);
1054         }
1055         return ret;
1056 }
1057
1058 void
1059 route_set_destination(struct route *this, struct pcoord *dst, int async)
1060 {
1061         route_set_destinations(this, dst, dst?1:0, async);
1062 }
1063
1064 void
1065 route_remove_waypoint(struct route *this)
1066 {
1067         struct route_path *path=this->path2;
1068         this->destinations=g_list_remove(this->destinations,this->destinations->data);
1069         this->path2=this->path2->next;
1070         route_path_destroy(path,0);
1071         if (!this->destinations)
1072                 return;
1073         route_graph_reset(this->graph);
1074         this->current_dst=this->destinations->data;
1075         route_graph_flood(this->graph, this->current_dst, this->vehicleprofile, this->route_graph_flood_done_cb);
1076
1077 }
1078
1079 /**
1080  * @brief Gets the route_graph_point with the specified coordinates
1081  *
1082  * @param this The route in which to search
1083  * @param c Coordinates to search for
1084  * @param last The last route graph point returned to iterate over multiple points with the same coordinates
1085  * @return The point at the specified coordinates or NULL if not found
1086  */
1087 static struct route_graph_point *
1088 route_graph_get_point_next(struct route_graph *this, struct coord *c, struct route_graph_point *last)
1089 {
1090         struct route_graph_point *p;
1091         int seen=0,hashval=HASHCOORD(c);
1092         p=this->hash[hashval];
1093         while (p) {
1094                 if (p->c.x == c->x && p->c.y == c->y) {
1095                         if (!last || seen)
1096                                 return p;
1097                         if (p == last)
1098                                 seen=1;
1099                 }
1100                 p=p->hash_next;
1101         }
1102         return NULL;
1103 }
1104
1105 static struct route_graph_point *
1106 route_graph_get_point(struct route_graph *this, struct coord *c)
1107 {
1108         return route_graph_get_point_next(this, c, NULL);
1109 }
1110
1111 /**
1112  * @brief Gets the last route_graph_point with the specified coordinates
1113  *
1114  * @param this The route in which to search
1115  * @param c Coordinates to search for
1116  * @return The point at the specified coordinates or NULL if not found
1117  */
1118 static struct route_graph_point *
1119 route_graph_get_point_last(struct route_graph *this, struct coord *c)
1120 {
1121         struct route_graph_point *p,*ret=NULL;
1122         int hashval=HASHCOORD(c);
1123         p=this->hash[hashval];
1124         while (p) {
1125                 if (p->c.x == c->x && p->c.y == c->y)
1126                         ret=p;
1127                 p=p->hash_next;
1128         }
1129         return ret;
1130 }
1131
1132
1133
1134 /**
1135  * @brief Create a new point for the route graph with the specified coordinates
1136  *
1137  * @param this The route to insert the point into
1138  * @param f The coordinates at which the point should be created
1139  * @return The point created
1140  */
1141
1142 static struct route_graph_point *
1143 route_graph_point_new(struct route_graph *this, struct coord *f)
1144 {
1145         int hashval;
1146         struct route_graph_point *p;
1147
1148         hashval=HASHCOORD(f);
1149         if (debug_route)
1150                 printf("p (0x%x,0x%x)\n", f->x, f->y);
1151         p=g_slice_new0(struct route_graph_point);
1152         p->hash_next=this->hash[hashval];
1153         this->hash[hashval]=p;
1154         p->value=INT_MAX;
1155         p->c=*f;
1156         return p;
1157 }
1158
1159 /**
1160  * @brief Inserts a point into the route graph at the specified coordinates
1161  *
1162  * This will insert a point into the route graph at the coordinates passed in f.
1163  * Note that the point is not yet linked to any segments.
1164  *
1165  * @param this The route to insert the point into
1166  * @param f The coordinates at which the point should be inserted
1167  * @return The point inserted or NULL on failure
1168  */
1169 static struct route_graph_point *
1170 route_graph_add_point(struct route_graph *this, struct coord *f)
1171 {
1172         struct route_graph_point *p;
1173
1174         p=route_graph_get_point(this,f);
1175         if (!p)
1176                 p=route_graph_point_new(this,f);
1177         return p;
1178 }
1179
1180 /**
1181  * @brief Frees all the memory used for points in the route graph passed
1182  *
1183  * @param this The route graph to delete all points from
1184  */
1185 static void
1186 route_graph_free_points(struct route_graph *this)
1187 {
1188         struct route_graph_point *curr,*next;
1189         int i;
1190         for (i = 0 ; i < HASH_SIZE ; i++) {
1191                 curr=this->hash[i];
1192                 while (curr) {
1193                         next=curr->hash_next;
1194                         g_slice_free(struct route_graph_point, curr);
1195                         curr=next;
1196                 }
1197                 this->hash[i]=NULL;
1198         }
1199 }
1200
1201 /**
1202  * @brief Resets all nodes
1203  *
1204  * @param this The route graph to reset
1205  */
1206 static void
1207 route_graph_reset(struct route_graph *this)
1208 {
1209         struct route_graph_point *curr;
1210         int i;
1211         for (i = 0 ; i < HASH_SIZE ; i++) {
1212                 curr=this->hash[i];
1213                 while (curr) {
1214                         curr->value=INT_MAX;
1215                         curr->seg=NULL;
1216                         curr->el=NULL;
1217                         curr=curr->hash_next;
1218                 }
1219         }
1220 }
1221
1222 /**
1223  * @brief Returns the position of a certain field appended to a route graph segment
1224  *
1225  * This function returns a pointer to a field that is appended to a route graph
1226  * segment.
1227  *
1228  * @param seg The route graph segment the field is appended to
1229  * @param type Type of the field that should be returned
1230  * @return A pointer to a field of a certain type, or NULL if no such field is present
1231  */
1232 static void *
1233 route_segment_data_field_pos(struct route_segment_data *seg, enum attr_type type)
1234 {
1235         unsigned char *ptr;
1236
1237         ptr = ((unsigned char*)seg) + sizeof(struct route_segment_data);
1238
1239         if (seg->flags & AF_SPEED_LIMIT) {
1240                 if (type == attr_maxspeed)
1241                         return (void*)ptr;
1242                 ptr += sizeof(int);
1243         }
1244         if (seg->flags & AF_SEGMENTED) {
1245                 if (type == attr_offset)
1246                         return (void*)ptr;
1247                 ptr += sizeof(int);
1248         }
1249         if (seg->flags & AF_SIZE_OR_WEIGHT_LIMIT) {
1250                 if (type == attr_vehicle_width)
1251                         return (void*)ptr;
1252                 ptr += sizeof(struct size_weight_limit);
1253         }
1254         if (seg->flags & AF_DANGEROUS_GOODS) {
1255                 if (type == attr_vehicle_dangerous_goods)
1256                         return (void*)ptr;
1257                 ptr += sizeof(int);
1258         }
1259         return NULL;
1260 }
1261
1262 /**
1263  * @brief Calculates the size of a route_segment_data struct with given flags
1264  *
1265  * @param flags The flags of the route_segment_data
1266  */
1267
1268 static int
1269 route_segment_data_size(int flags)
1270 {
1271         int ret=sizeof(struct route_segment_data);
1272         if (flags & AF_SPEED_LIMIT)
1273                 ret+=sizeof(int);
1274         if (flags & AF_SEGMENTED)
1275                 ret+=sizeof(int);
1276         if (flags & AF_SIZE_OR_WEIGHT_LIMIT)
1277                 ret+=sizeof(struct size_weight_limit);
1278         if (flags & AF_DANGEROUS_GOODS)
1279                 ret+=sizeof(int);
1280         return ret;
1281 }
1282
1283
1284 static int
1285 route_graph_segment_is_duplicate(struct route_graph_point *start, struct route_graph_segment_data *data)
1286 {
1287         struct route_graph_segment *s;
1288         s=start->start;
1289         while (s) {
1290                 if (item_is_equal(*data->item, s->data.item)) {
1291                         if (data->flags & AF_SEGMENTED) {
1292                                 if (RSD_OFFSET(&s->data) == data->offset) {
1293                                         return 1;
1294                                 }
1295                         } else
1296                                 return 1;
1297                 }
1298                 s=s->start_next;
1299         }
1300         return 0;
1301 }
1302
1303 /**
1304  * @brief Inserts a new segment into the route graph
1305  *
1306  * This function performs a check if a segment for the item specified already exists, and inserts
1307  * a new segment representing this item if it does not.
1308  *
1309  * @param this The route graph to insert the segment into
1310  * @param start The graph point which should be connected to the start of this segment
1311  * @param end The graph point which should be connected to the end of this segment
1312  * @param len The length of this segment
1313  * @param item The item that is represented by this segment
1314  * @param flags Flags for this segment
1315  * @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
1316  * @param maxspeed The maximum speed allowed on this segment in km/h. -1 if not known.
1317  */
1318 static void
1319 route_graph_add_segment(struct route_graph *this, struct route_graph_point *start,
1320                         struct route_graph_point *end, struct route_graph_segment_data *data)
1321 {
1322         struct route_graph_segment *s;
1323         int size;
1324
1325         size = sizeof(struct route_graph_segment)-sizeof(struct route_segment_data)+route_segment_data_size(data->flags);
1326         s = g_slice_alloc0(size);
1327         if (!s) {
1328                 printf("%s:Out of memory\n", __FUNCTION__);
1329                 return;
1330         }
1331         s->start=start;
1332         s->start_next=start->start;
1333         start->start=s;
1334         s->end=end;
1335         s->end_next=end->end;
1336         end->end=s;
1337         dbg_assert(data->len >= 0);
1338         s->data.len=data->len;
1339         s->data.item=*data->item;
1340         s->data.flags=data->flags;
1341
1342         if (data->flags & AF_SPEED_LIMIT)
1343                 RSD_MAXSPEED(&s->data)=data->maxspeed;
1344         if (data->flags & AF_SEGMENTED)
1345                 RSD_OFFSET(&s->data)=data->offset;
1346         if (data->flags & AF_SIZE_OR_WEIGHT_LIMIT)
1347                 RSD_SIZE_WEIGHT(&s->data)=data->size_weight;
1348         if (data->flags & AF_DANGEROUS_GOODS)
1349                 RSD_DANGEROUS_GOODS(&s->data)=data->dangerous_goods;
1350
1351         s->next=this->route_segments;
1352         this->route_segments=s;
1353         if (debug_route)
1354                 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
1355 }
1356
1357 /**
1358  * @brief Gets all the coordinates of an item
1359  *
1360  * This will get all the coordinates of the item i and return them in c,
1361  * up to max coordinates. Additionally it is possible to limit the coordinates
1362  * returned to all the coordinates of the item between the two coordinates
1363  * start end end.
1364  *
1365  * @important Make sure that whatever c points to has enough memory allocated
1366  * @important to hold max coordinates!
1367  *
1368  * @param i The item to get the coordinates of
1369  * @param c Pointer to memory allocated for holding the coordinates
1370  * @param max Maximum number of coordinates to return
1371  * @param start First coordinate to get
1372  * @param end Last coordinate to get
1373  * @return The number of coordinates returned
1374  */
1375 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
1376                 struct coord *start, struct coord *end)
1377 {
1378         struct map_rect *mr;
1379         struct item *item;
1380         int rc = 0, p = 0;
1381         struct coord c1;
1382         mr=map_rect_new(i->map, NULL);
1383         if (!mr)
1384                 return 0;
1385         item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
1386         if (item) {
1387                 rc = item_coord_get(item, &c1, 1);
1388                 while (rc && (c1.x != start->x || c1.y != start->y)) {
1389                         rc = item_coord_get(item, &c1, 1);
1390                 }
1391                 while (rc && p < max) {
1392                         c[p++] = c1;
1393                         if (c1.x == end->x && c1.y == end->y)
1394                                 break;
1395                         rc = item_coord_get(item, &c1, 1);
1396                 }
1397         }
1398         map_rect_destroy(mr);
1399         return p;
1400 }
1401
1402 /**
1403  * @brief Returns and removes one segment from a path
1404  *
1405  * @param path The path to take the segment from
1406  * @param item The item whose segment to remove
1407  * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
1408  * @return The segment removed
1409  */
1410 static struct route_path_segment *
1411 route_extract_segment_from_path(struct route_path *path, struct item *item,
1412                                                  int offset)
1413 {
1414         int soffset;
1415         struct route_path_segment *sp = NULL, *s;
1416         s = path->path;
1417         while (s) {
1418                 if (item_is_equal(s->data->item,*item)) {
1419                         if (s->data->flags & AF_SEGMENTED)
1420                                 soffset=RSD_OFFSET(s->data);
1421                         else
1422                                 soffset=1;
1423                         if (soffset == offset) {
1424                                 if (sp) {
1425                                         sp->next = s->next;
1426                                         break;
1427                                 } else {
1428                                         path->path = s->next;
1429                                         break;
1430                                 }
1431                         }
1432                 }
1433                 sp = s;
1434                 s = s->next;
1435         }
1436         if (s)
1437                 item_hash_remove(path->path_hash, item);
1438         return s;
1439 }
1440
1441 /**
1442  * @brief Adds a segment and the end of a path
1443  *
1444  * @param this The path to add the segment to
1445  * @param segment The segment to add
1446  */
1447 static void
1448 route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
1449 {
1450         if (!this->path)
1451                 this->path=segment;
1452         if (this->path_last)
1453                 this->path_last->next=segment;
1454         this->path_last=segment;
1455 }
1456
1457 /**
1458  * @brief Adds a two coordinate line to a path
1459  *
1460  * This adds a new line to a path, creating a new segment for it.
1461  *
1462  * @param this The path to add the item to
1463  * @param start coordinate to add to the start of the item. If none should be added, make this NULL.
1464  * @param end coordinate to add to the end of the item. If none should be added, make this NULL.
1465  * @param len The length of the item
1466  */
1467 static void
1468 route_path_add_line(struct route_path *this, struct coord *start, struct coord *end, int len)
1469 {
1470         int ccnt=2;
1471         struct route_path_segment *segment;
1472         int seg_size,seg_dat_size;
1473
1474         dbg(1,"line from 0x%x,0x%x-0x%x,0x%x\n", start->x, start->y, end->x, end->y);
1475         seg_size=sizeof(*segment) + sizeof(struct coord) * ccnt;
1476         seg_dat_size=sizeof(struct route_segment_data);
1477         segment=g_malloc0(seg_size + seg_dat_size);
1478         segment->data=(struct route_segment_data *)((char *)segment+seg_size);
1479         segment->ncoords=ccnt;
1480         segment->direction=0;
1481         segment->c[0]=*start;
1482         segment->c[1]=*end;
1483         segment->data->len=len;
1484         route_path_add_segment(this, segment);
1485 }
1486
1487 /**
1488  * @brief Inserts a new item into the path
1489  *
1490  * This function does almost the same as "route_path_add_item()", but identifies
1491  * the item to add by a segment from the route graph. Another difference is that it "copies" the
1492  * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
1493  * be added to the route path, not all segments of the item.
1494  *
1495  * The function can be sped up by passing an old path already containing this segment in oldpath -
1496  * the segment will then be extracted from this old path. Please note that in this case the direction
1497  * parameter has no effect.
1498  *
1499  * @param this The path to add the item to
1500  * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
1501  * @param rgs Segment of the route graph that should be "copied" to the route path
1502  * @param dir Order in which to add the coordinates. See route_path_add_item()
1503  * @param pos  Information about start point if this is the first segment
1504  * @param dst  Information about end point if this is the last segment
1505  */
1506
1507 static int
1508 route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath, struct route_graph_segment *rgs, int dir, struct route_info *pos, struct route_info *dst)
1509 {
1510         struct route_path_segment *segment;
1511         int i, ccnt, extra=0, ret=0;
1512         struct coord *c,*cd,ca[2048];
1513         int offset=1;
1514         int seg_size,seg_dat_size;
1515         int len=rgs->data.len;
1516         if (rgs->data.flags & AF_SEGMENTED)
1517                 offset=RSD_OFFSET(&rgs->data);
1518
1519         dbg(1,"enter (0x%x,0x%x) dir=%d pos=%p dst=%p\n", rgs->data.item.id_hi, rgs->data.item.id_lo, dir, pos, dst);
1520         if (oldpath) {
1521                 segment=item_hash_lookup(oldpath->path_hash, &rgs->data.item);
1522                 if (segment && segment->direction == dir) {
1523                         segment = route_extract_segment_from_path(oldpath, &rgs->data.item, offset);
1524                         if (segment) {
1525                                 ret=1;
1526                                 if (!pos)
1527                                         goto linkold;
1528                         }
1529                 }
1530         }
1531
1532         if (pos) {
1533                 if (dst) {
1534                         extra=2;
1535                         if (dst->lenneg >= pos->lenneg) {
1536                                 dir=1;
1537                                 ccnt=dst->pos-pos->pos;
1538                                 c=pos->street->c+pos->pos+1;
1539                                 len=dst->lenneg-pos->lenneg;
1540                         } else {
1541                                 dir=-1;
1542                                 ccnt=pos->pos-dst->pos;
1543                                 c=pos->street->c+dst->pos+1;
1544                                 len=pos->lenneg-dst->lenneg;
1545                         }
1546                 } else {
1547                         extra=1;
1548                         dbg(1,"pos dir=%d\n", dir);
1549                         dbg(1,"pos pos=%d\n", pos->pos);
1550                         dbg(1,"pos count=%d\n", pos->street->count);
1551                         if (dir > 0) {
1552                                 c=pos->street->c+pos->pos+1;
1553                                 ccnt=pos->street->count-pos->pos-1;
1554                                 len=pos->lenpos;
1555                         } else {
1556                                 c=pos->street->c;
1557                                 ccnt=pos->pos+1;
1558                                 len=pos->lenneg;
1559                         }
1560                 }
1561                 pos->dir=dir;
1562         } else  if (dst) {
1563                 extra=1;
1564                 dbg(1,"dst dir=%d\n", dir);
1565                 dbg(1,"dst pos=%d\n", dst->pos);
1566                 if (dir > 0) {
1567                         c=dst->street->c;
1568                         ccnt=dst->pos+1;
1569                         len=dst->lenpos;
1570                 } else {
1571                         c=dst->street->c+dst->pos+1;
1572                         ccnt=dst->street->count-dst->pos-1;
1573                         len=dst->lenneg;
1574                 }
1575         } else {
1576                 ccnt=get_item_seg_coords(&rgs->data.item, ca, 2047, &rgs->start->c, &rgs->end->c);
1577                 c=ca;
1578         }
1579         seg_size=sizeof(*segment) + sizeof(struct coord) * (ccnt + extra);
1580         seg_dat_size=route_segment_data_size(rgs->data.flags);
1581         segment=g_malloc0(seg_size + seg_dat_size);
1582         segment->data=(struct route_segment_data *)((char *)segment+seg_size);
1583         segment->direction=dir;
1584         cd=segment->c;
1585         if (pos && (c[0].x != pos->lp.x || c[0].y != pos->lp.y))
1586                 *cd++=pos->lp;
1587         if (dir < 0)
1588                 c+=ccnt-1;
1589         for (i = 0 ; i < ccnt ; i++) {
1590                 *cd++=*c;
1591                 c+=dir;
1592         }
1593         segment->ncoords+=ccnt;
1594         if (dst && (cd[-1].x != dst->lp.x || cd[-1].y != dst->lp.y))
1595                 *cd++=dst->lp;
1596         segment->ncoords=cd-segment->c;
1597         if (segment->ncoords <= 1) {
1598                 g_free(segment);
1599                 return 1;
1600         }
1601
1602         /* We check if the route graph segment is part of a roundabout here, because this
1603          * only matters for route graph segments which form parts of the route path */
1604         if (!(rgs->data.flags & AF_ROUNDABOUT)) { // We identified this roundabout earlier
1605                 route_check_roundabout(rgs, 13, (dir < 1), NULL);
1606         }
1607
1608         memcpy(segment->data, &rgs->data, seg_dat_size);
1609 linkold:
1610         segment->data->len=len;
1611         segment->next=NULL;
1612         item_hash_insert(this->path_hash,  &rgs->data.item, segment);
1613
1614         route_path_add_segment(this, segment);
1615
1616         return ret;
1617 }
1618
1619 /**
1620  * @brief Destroys all segments of a route graph
1621  *
1622  * @param this The graph to destroy all segments from
1623  */
1624 static void
1625 route_graph_free_segments(struct route_graph *this)
1626 {
1627         struct route_graph_segment *curr,*next;
1628         int size;
1629         curr=this->route_segments;
1630         while (curr) {
1631                 next=curr->next;
1632                 size = sizeof(struct route_graph_segment)-sizeof(struct route_segment_data)+route_segment_data_size(curr->data.flags);
1633                 g_slice_free1(size, curr);
1634                 curr=next;
1635         }
1636         this->route_segments=NULL;
1637 }
1638
1639 /**
1640  * @brief Destroys a route graph
1641  *
1642  * @param this The route graph to be destroyed
1643  */
1644 static void
1645 route_graph_destroy(struct route_graph *this)
1646 {
1647         if (this) {
1648                 route_graph_build_done(this, 1);
1649                 route_graph_free_points(this);
1650                 route_graph_free_segments(this);
1651                 g_free(this);
1652         }
1653 }
1654
1655 /**
1656  * @brief Returns the estimated speed on a segment
1657  *
1658  * This function returns the estimated speed to be driven on a segment, 0=not passable
1659  *
1660  * @param profile The routing preferences
1661  * @param over The segment which is passed
1662  * @param dist A traffic distortion if applicable
1663  * @return The estimated speed
1664  */
1665 static int
1666 route_seg_speed(struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist)
1667 {
1668         struct roadprofile *roadprofile=vehicleprofile_get_roadprofile(profile, over->item.type);
1669         int speed,maxspeed;
1670         if (!roadprofile || !roadprofile->route_weight)
1671                 return 0;
1672         /* maxspeed_handling: 0=always, 1 only if maxspeed restricts the speed, 2 never */
1673         speed=roadprofile->route_weight;
1674         if (profile->maxspeed_handling != 2) {
1675                 if (over->flags & AF_SPEED_LIMIT) {
1676                         maxspeed=RSD_MAXSPEED(over);
1677                         if (!profile->maxspeed_handling)
1678                                 speed=maxspeed;
1679                 } else
1680                         maxspeed=INT_MAX;
1681                 if (dist && maxspeed > dist->maxspeed)
1682                         maxspeed=dist->maxspeed;
1683                 if (maxspeed != INT_MAX && (profile->maxspeed_handling != 1 || maxspeed < speed))
1684                         speed=maxspeed;
1685         }
1686         if (over->flags & AF_DANGEROUS_GOODS) {
1687                 if (profile->dangerous_goods & RSD_DANGEROUS_GOODS(over))
1688                         return 0;
1689         }
1690         if (over->flags & AF_SIZE_OR_WEIGHT_LIMIT) {
1691                 struct size_weight_limit *size_weight=&RSD_SIZE_WEIGHT(over);
1692                 if (size_weight->width != -1 && profile->width != -1 && profile->width > size_weight->width)
1693                         return 0;
1694                 if (size_weight->height != -1 && profile->height != -1 && profile->height > size_weight->height)
1695                         return 0;
1696                 if (size_weight->length != -1 && profile->length != -1 && profile->length > size_weight->length)
1697                         return 0;
1698                 if (size_weight->weight != -1 && profile->weight != -1 && profile->weight > size_weight->weight)
1699                         return 0;
1700                 if (size_weight->axle_weight != -1 && profile->axle_weight != -1 && profile->axle_weight > size_weight->axle_weight)
1701                         return 0;
1702         }
1703         return speed;
1704 }
1705
1706 /**
1707  * @brief Returns the time needed to drive len on item
1708  *
1709  * This function returns the time needed to drive len meters on
1710  * the item passed in item in tenth of seconds.
1711  *
1712  * @param profile The routing preferences
1713  * @param over The segment which is passed
1714  * @param dist A traffic distortion if applicable
1715  * @return The time needed to drive len on item in thenth of senconds
1716  */
1717
1718 static int
1719 route_time_seg(struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist)
1720 {
1721         int speed=route_seg_speed(profile, over, dist);
1722         if (!speed)
1723                 return INT_MAX;
1724         return over->len*36/speed+(dist ? dist->delay : 0);
1725 }
1726
1727 static int
1728 route_get_traffic_distortion(struct route_graph_segment *seg, struct route_traffic_distortion *ret)
1729 {
1730         struct route_graph_point *start=seg->start;
1731         struct route_graph_point *end=seg->end;
1732         struct route_graph_segment *tmp,*found=NULL;
1733         tmp=start->start;
1734         while (tmp && !found) {
1735                 if (tmp->data.item.type == type_traffic_distortion && tmp->start == start && tmp->end == end)
1736                         found=tmp;
1737                 tmp=tmp->start_next;
1738         }
1739         tmp=start->end;
1740         while (tmp && !found) {
1741                 if (tmp->data.item.type == type_traffic_distortion && tmp->end == start && tmp->start == end)
1742                         found=tmp;
1743                 tmp=tmp->end_next;
1744         }
1745         if (found) {
1746                 ret->delay=found->data.len;
1747                 if (found->data.flags & AF_SPEED_LIMIT)
1748                         ret->maxspeed=RSD_MAXSPEED(&found->data);
1749                 else
1750                         ret->maxspeed=INT_MAX;
1751                 return 1;
1752         }
1753         return 0;
1754 }
1755
1756 static int
1757 route_through_traffic_allowed(struct vehicleprofile *profile, struct route_graph_segment *seg)
1758 {
1759         return (seg->data.flags & AF_THROUGH_TRAFFIC_LIMIT) == 0;
1760 }
1761
1762 /**
1763  * @brief Returns the "costs" of driving from point from over segment over in direction dir
1764  *
1765  * @param profile The routing preferences
1766  * @param from The point where we are starting
1767  * @param over The segment we are using
1768  * @param dir The direction of segment which we are driving
1769  * @return The "costs" needed to drive len on item
1770  */
1771
1772 static int
1773 route_value_seg(struct vehicleprofile *profile, struct route_graph_point *from, struct route_graph_segment *over, int dir)
1774 {
1775         int ret;
1776         struct route_traffic_distortion dist,*distp=NULL;
1777 #if 0
1778         dbg(0,"flags 0x%x mask 0x%x flags 0x%x\n", over->flags, dir >= 0 ? profile->flags_forward_mask : profile->flags_reverse_mask, profile->flags);
1779 #endif
1780         if ((over->data.flags & (dir >= 0 ? profile->flags_forward_mask : profile->flags_reverse_mask)) != profile->flags)
1781                 return INT_MAX;
1782         if (dir > 0 && (over->start->flags & RP_TURN_RESTRICTION))
1783                 return INT_MAX;
1784         if (dir < 0 && (over->end->flags & RP_TURN_RESTRICTION))
1785                 return INT_MAX;
1786         if (from && from->seg == over)
1787                 return INT_MAX;
1788         if ((over->start->flags & RP_TRAFFIC_DISTORTION) && (over->end->flags & RP_TRAFFIC_DISTORTION) &&
1789                 route_get_traffic_distortion(over, &dist)) {
1790                         distp=&dist;
1791         }
1792         ret=route_time_seg(profile, &over->data, distp);
1793         if (ret == INT_MAX)
1794                 return ret;
1795         if (!route_through_traffic_allowed(profile, over) && from && route_through_traffic_allowed(profile, from->seg))
1796                 ret+=profile->through_traffic_penalty;
1797         return ret;
1798 }
1799
1800 /**
1801  * @brief Adds a route distortion item to the route graph
1802  *
1803  * @param this The route graph to add to
1804  * @param item The item to add
1805  */
1806 static void
1807 route_process_traffic_distortion(struct route_graph *this, struct item *item)
1808 {
1809         struct route_graph_point *s_pnt,*e_pnt;
1810         struct coord c,l;
1811         struct attr delay_attr, maxspeed_attr;
1812         struct route_graph_segment_data data;
1813
1814         data.item=item;
1815         data.len=0;
1816         data.flags=0;
1817         data.offset=1;
1818         data.maxspeed = INT_MAX;
1819
1820         if (item_coord_get(item, &l, 1)) {
1821                 s_pnt=route_graph_add_point(this,&l);
1822                 while (item_coord_get(item, &c, 1)) {
1823                         l=c;
1824                 }
1825                 e_pnt=route_graph_add_point(this,&l);
1826                 s_pnt->flags |= RP_TRAFFIC_DISTORTION;
1827                 e_pnt->flags |= RP_TRAFFIC_DISTORTION;
1828                 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr)) {
1829                         data.flags |= AF_SPEED_LIMIT;
1830                         data.maxspeed=maxspeed_attr.u.num;
1831                 }
1832                 if (item_attr_get(item, attr_delay, &delay_attr))
1833                         data.len=delay_attr.u.num;
1834                 route_graph_add_segment(this, s_pnt, e_pnt, &data);
1835         }
1836 }
1837
1838 /**
1839  * @brief Adds a route distortion item to the route graph
1840  *
1841  * @param this The route graph to add to
1842  * @param item The item to add
1843  */
1844 static void
1845 route_process_turn_restriction(struct route_graph *this, struct item *item)
1846 {
1847         struct route_graph_point *pnt[4];
1848         struct coord c[5];
1849         int i,count;
1850         struct route_graph_segment_data data;
1851
1852         count=item_coord_get(item, c, 5);
1853         if (count != 3 && count != 4) {
1854                 dbg(0,"wrong count %d\n",count);
1855                 return;
1856         }
1857         if (count == 4)
1858                 return;
1859         for (i = 0 ; i < count ; i++)
1860                 pnt[i]=route_graph_add_point(this,&c[i]);
1861         dbg(1,"%s: (0x%x,0x%x)-(0x%x,0x%x)-(0x%x,0x%x) %p-%p-%p\n",item_to_name(item->type),c[0].x,c[0].y,c[1].x,c[1].y,c[2].x,c[2].y,pnt[0],pnt[1],pnt[2]);
1862         data.item=item;
1863         data.flags=0;
1864         data.len=0;
1865         route_graph_add_segment(this, pnt[0], pnt[1], &data);
1866         route_graph_add_segment(this, pnt[1], pnt[2], &data);
1867 #if 1
1868         if (count == 4) {
1869                 pnt[1]->flags |= RP_TURN_RESTRICTION;
1870                 pnt[2]->flags |= RP_TURN_RESTRICTION;
1871                 route_graph_add_segment(this, pnt[2], pnt[3], &data);
1872         } else
1873                 pnt[1]->flags |= RP_TURN_RESTRICTION;
1874 #endif
1875 }
1876
1877 /**
1878  * @brief Adds an item to the route graph
1879  *
1880  * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
1881  * segmented item.
1882  *
1883  * @param this The route graph to add to
1884  * @param item The item to add
1885  * @param profile               The vehicle profile currently in use
1886  */
1887 static void
1888 route_process_street_graph(struct route_graph *this, struct item *item, struct vehicleprofile *profile)
1889 {
1890 #ifdef AVOID_FLOAT
1891         int len=0;
1892 #else
1893         double len=0;
1894 #endif
1895         int segmented = 0;
1896         struct roadprofile *roadp;
1897         struct route_graph_point *s_pnt,*e_pnt;
1898         struct coord c,l;
1899         struct attr attr;
1900         struct route_graph_segment_data data;
1901         data.flags=0;
1902         data.offset=1;
1903         data.maxspeed=-1;
1904         data.item=item;
1905
1906         roadp = vehicleprofile_get_roadprofile(profile, item->type);
1907         if (!roadp) {
1908                 // Don't include any roads that don't have a road profile in our vehicle profile
1909                 return;
1910         }
1911
1912         if (item_coord_get(item, &l, 1)) {
1913                 int *default_flags=item_get_default_flags(item->type);
1914                 if (! default_flags)
1915                         return;
1916                 if (item_attr_get(item, attr_flags, &attr)) {
1917                         data.flags = attr.u.num;
1918                         if (data.flags & AF_SEGMENTED)
1919                                 segmented = 1;
1920                 } else
1921                         data.flags = *default_flags;
1922
1923
1924                 if (data.flags & AF_SPEED_LIMIT) {
1925                         if (item_attr_get(item, attr_maxspeed, &attr))
1926                                 data.maxspeed = attr.u.num;
1927                 }
1928                 if (data.flags & AF_DANGEROUS_GOODS) {
1929                         if (item_attr_get(item, attr_vehicle_dangerous_goods, &attr))
1930                                 data.dangerous_goods = attr.u.num;
1931                         else
1932                                 data.flags &= ~AF_DANGEROUS_GOODS;
1933                 }
1934                 if (data.flags & AF_SIZE_OR_WEIGHT_LIMIT) {
1935                         if (item_attr_get(item, attr_vehicle_width, &attr))
1936                                 data.size_weight.width=attr.u.num;
1937                         else
1938                                 data.size_weight.width=-1;
1939                         if (item_attr_get(item, attr_vehicle_height, &attr))
1940                                 data.size_weight.height=attr.u.num;
1941                         else
1942                                 data.size_weight.height=-1;
1943                         if (item_attr_get(item, attr_vehicle_length, &attr))
1944                                 data.size_weight.length=attr.u.num;
1945                         else
1946                                 data.size_weight.length=-1;
1947                         if (item_attr_get(item, attr_vehicle_weight, &attr))
1948                                 data.size_weight.weight=attr.u.num;
1949                         else
1950                                 data.size_weight.weight=-1;
1951                         if (item_attr_get(item, attr_vehicle_axle_weight, &attr))
1952                                 data.size_weight.axle_weight=attr.u.num;
1953                         else
1954                                 data.size_weight.axle_weight=-1;
1955                 }
1956
1957                 s_pnt=route_graph_add_point(this,&l);
1958                 if (!segmented) {
1959                         while (item_coord_get(item, &c, 1)) {
1960                                 len+=transform_distance(map_projection(item->map), &l, &c);
1961                                 l=c;
1962                         }
1963                         e_pnt=route_graph_add_point(this,&l);
1964                         dbg_assert(len >= 0);
1965                         data.len=len;
1966                         if (!route_graph_segment_is_duplicate(s_pnt, &data))
1967                                 route_graph_add_segment(this, s_pnt, e_pnt, &data);
1968                 } else {
1969                         int isseg,rc;
1970                         int sc = 0;
1971                         do {
1972                                 isseg = item_coord_is_node(item);
1973                                 rc = item_coord_get(item, &c, 1);
1974                                 if (rc) {
1975                                         len+=transform_distance(map_projection(item->map), &l, &c);
1976                                         l=c;
1977                                         if (isseg) {
1978                                                 e_pnt=route_graph_add_point(this,&l);
1979                                                 data.len=len;
1980                                                 if (!route_graph_segment_is_duplicate(s_pnt, &data))
1981                                                         route_graph_add_segment(this, s_pnt, e_pnt, &data);
1982                                                 data.offset++;
1983                                                 s_pnt=route_graph_add_point(this,&l);
1984                                                 len = 0;
1985                                         }
1986                                 }
1987                         } while(rc);
1988                         e_pnt=route_graph_add_point(this,&l);
1989                         dbg_assert(len >= 0);
1990                         sc++;
1991                         data.len=len;
1992                         if (!route_graph_segment_is_duplicate(s_pnt, &data))
1993                                 route_graph_add_segment(this, s_pnt, e_pnt, &data);
1994                 }
1995         }
1996 }
1997
1998 static struct route_graph_segment *
1999 route_graph_get_segment(struct route_graph *graph, struct street_data *sd, struct route_graph_segment *last)
2000 {
2001         struct route_graph_point *start=NULL;
2002         struct route_graph_segment *s;
2003         int seen=0;
2004
2005         while ((start=route_graph_get_point_next(graph, &sd->c[0], start))) {
2006                 s=start->start;
2007                 while (s) {
2008                         if (item_is_equal(sd->item, s->data.item)) {
2009                                 if (!last || seen)
2010                                         return s;
2011                                 if (last == s)
2012                                         seen=1;
2013                         }
2014                         s=s->start_next;
2015                 }
2016         }
2017         return NULL;
2018 }
2019
2020 /**
2021  * @brief Calculates the routing costs for each point
2022  *
2023  * This function is the heart of routing. It assigns each point in the route graph a
2024  * cost at which one can reach the destination from this point on. Additionally it assigns
2025  * each point a segment one should follow from this point on to reach the destination at the
2026  * stated costs.
2027  *
2028  * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
2029  * at this algorithm.
2030  */
2031 static void
2032 route_graph_flood(struct route_graph *this, struct route_info *dst, struct vehicleprofile *profile, struct callback *cb)
2033 {
2034         struct route_graph_point *p_min;
2035         struct route_graph_segment *s=NULL;
2036         int min,new,val;
2037         struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
2038
2039         heap = fh_makekeyheap();
2040
2041         while ((s=route_graph_get_segment(this, dst->street, s))) {
2042                 val=route_value_seg(profile, NULL, s, -1);
2043                 if (val != INT_MAX) {
2044                         val=val*(100-dst->percent)/100;
2045                         s->end->seg=s;
2046                         s->end->value=val;
2047                         s->end->el=fh_insertkey(heap, s->end->value, s->end);
2048                 }
2049                 val=route_value_seg(profile, NULL, s, 1);
2050                 if (val != INT_MAX) {
2051                         val=val*dst->percent/100;
2052                         s->start->seg=s;
2053                         s->start->value=val;
2054                         s->start->el=fh_insertkey(heap, s->start->value, s->start);
2055                 }
2056         }
2057         for (;;) {
2058                 p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
2059                 if (! p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
2060                         break;
2061                 min=p_min->value;
2062                 if (debug_route)
2063                         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);
2064                 p_min->el=NULL; /* This point is permanently calculated now, we've taken it out of the heap */
2065                 s=p_min->start;
2066                 while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
2067                         val=route_value_seg(profile, p_min, s, -1);
2068                         if (val != INT_MAX && !item_is_equal(s->data.item,p_min->seg->data.item)) {
2069                                 new=min+val;
2070                                 if (debug_route)
2071                                         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);
2072                                 if (new < s->end->value) { /* We've found a less costly way to reach the end of s, update it */
2073                                         s->end->value=new;
2074                                         s->end->seg=s;
2075                                         if (! s->end->el) {
2076                                                 if (debug_route)
2077                                                         printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
2078                                                 s->end->el=fh_insertkey(heap, new, s->end);
2079                                                 if (debug_route)
2080                                                         printf("el new=%p\n", s->end->el);
2081                                         }
2082                                         else {
2083                                                 if (debug_route)
2084                                                         printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
2085                                                 fh_replacekey(heap, s->end->el, new);
2086                                         }
2087                                 }
2088                                 if (debug_route)
2089                                         printf("\n");
2090                         }
2091                         s=s->start_next;
2092                 }
2093                 s=p_min->end;
2094                 while (s) { /* Doing the same as above with the segments leading towards our point */
2095                         val=route_value_seg(profile, p_min, s, 1);
2096                         if (val != INT_MAX && !item_is_equal(s->data.item,p_min->seg->data.item)) {
2097                                 new=min+val;
2098                                 if (debug_route)
2099                                         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);
2100                                 if (new < s->start->value) {
2101                                         s->start->value=new;
2102                                         s->start->seg=s;
2103                                         if (! s->start->el) {
2104                                                 if (debug_route)
2105                                                         printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
2106                                                 s->start->el=fh_insertkey(heap, new, s->start);
2107                                                 if (debug_route)
2108                                                         printf("el new=%p\n", s->start->el);
2109                                         }
2110                                         else {
2111                                                 if (debug_route)
2112                                                         printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
2113                                                 fh_replacekey(heap, s->start->el, new);
2114                                         }
2115                                 }
2116                                 if (debug_route)
2117                                         printf("\n");
2118                         }
2119                         s=s->end_next;
2120                 }
2121         }
2122         fh_deleteheap(heap);
2123         callback_call_0(cb);
2124         dbg(1,"return\n");
2125 }
2126
2127 /**
2128  * @brief Starts an "offroad" path
2129  *
2130  * This starts a path that is not located on a street. It creates a new route path
2131  * adding only one segment, that leads from pos to dest, and which is not associated with an item.
2132  *
2133  * @param this Not used
2134  * @param pos The starting position for the new path
2135  * @param dst The destination of the new path
2136  * @param dir Not used
2137  * @return The new path
2138  */
2139 static struct route_path *
2140 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst)
2141 {
2142         struct route_path *ret;
2143
2144         ret=g_new0(struct route_path, 1);
2145         ret->in_use=1;
2146         ret->path_hash=item_hash_new();
2147         route_path_add_line(ret, &pos->c, &dst->c, pos->lenextra+dst->lenextra);
2148         ret->updated=1;
2149
2150         return ret;
2151 }
2152
2153 /**
2154  * @brief Returns a coordinate at a given distance
2155  *
2156  * This function returns the coordinate, where the user will be if he
2157  * follows the current route for a certain distance.
2158  *
2159  * @param this_ The route we're driving upon
2160  * @param dist The distance in meters
2161  * @return The coordinate where the user will be in that distance
2162  */
2163 struct coord
2164 route_get_coord_dist(struct route *this_, int dist)
2165 {
2166         int d,l,i,len;
2167         int dx,dy;
2168         double frac;
2169         struct route_path_segment *cur;
2170         struct coord ret;
2171         enum projection pro=route_projection(this_);
2172         struct route_info *dst=route_get_dst(this_);
2173
2174         d = dist;
2175
2176         if (!this_->path2 || pro == projection_none) {
2177                 return this_->pos->c;
2178         }
2179
2180         ret = this_->pos->c;
2181         cur = this_->path2->path;
2182         while (cur) {
2183                 if (cur->data->len < d) {
2184                         d -= cur->data->len;
2185                 } else {
2186                         for (i=0; i < (cur->ncoords-1); i++) {
2187                                 l = d;
2188                                 len = (int)transform_polyline_length(pro, (cur->c + i), 2);
2189                                 d -= len;
2190                                 if (d <= 0) {
2191                                         // We interpolate a bit here...
2192                                         frac = (double)l / len;
2193
2194                                         dx = (cur->c + i + 1)->x - (cur->c + i)->x;
2195                                         dy = (cur->c + i + 1)->y - (cur->c + i)->y;
2196
2197                                         ret.x = (cur->c + i)->x + (frac * dx);
2198                                         ret.y = (cur->c + i)->y + (frac * dy);
2199                                         return ret;
2200                                 }
2201                         }
2202                         return cur->c[(cur->ncoords-1)];
2203                 }
2204                 cur = cur->next;
2205         }
2206
2207         return dst->c;
2208 }
2209
2210 /**
2211  * @brief Creates a new route path
2212  *
2213  * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
2214  * make sure to run route_graph_flood() after changing the destination before using this function.
2215  *
2216  * @param this The route graph to create the route from
2217  * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
2218  * @param pos The starting position of the route
2219  * @param dst The destination of the route
2220  * @param preferences The routing preferences
2221  * @return The new route path
2222  */
2223 static struct route_path *
2224 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct vehicleprofile *profile)
2225 {
2226         struct route_graph_segment *s=NULL,*s1=NULL,*s2=NULL;
2227         struct route_graph_point *start;
2228         struct route_info *posinfo, *dstinfo;
2229         int segs=0;
2230         int val1=INT_MAX,val2=INT_MAX;
2231         int val,val1_new,val2_new;
2232         struct route_path *ret;
2233
2234         if (! pos->street || ! dst->street) {
2235                 dbg(0,"pos or dest not set\n");
2236                 return NULL;
2237         }
2238
2239         if (profile->mode == 2 || (profile->mode == 0 && pos->lenextra + dst->lenextra > transform_distance(map_projection(pos->street->item.map), &pos->c, &dst->c)))
2240                 return route_path_new_offroad(this, pos, dst);
2241         while ((s=route_graph_get_segment(this, pos->street, s))) {
2242                 val=route_value_seg(profile, NULL, s, 1);
2243                 if (val != INT_MAX && s->end->value != INT_MAX) {
2244                         val=val*(100-pos->percent)/100;
2245                         val1_new=s->end->value+val;
2246                         if (val1_new < val1) {
2247                                 val1=val1_new;
2248                                 s1=s;
2249                         }
2250                 }
2251                 val=route_value_seg(profile, NULL, s, -1);
2252                 if (val != INT_MAX && s->start->value != INT_MAX) {
2253                         val=val*pos->percent/100;
2254                         val2_new=s->start->value+val;
2255                         if (val2_new < val2) {
2256                                 val2=val2_new;
2257                                 s2=s;
2258                         }
2259                 }
2260         }
2261         if (val1 == INT_MAX && val2 == INT_MAX) {
2262                 dbg(0,"no route found, pos blocked\n");
2263                 return NULL;
2264         }
2265         if (val1 == val2) {
2266                 val1=s1->end->value;
2267                 val2=s2->start->value;
2268         }
2269         if (val1 < val2) {
2270                 start=s1->start;
2271                 s=s1;
2272         } else {
2273                 start=s2->end;
2274                 s=s2;
2275         }
2276         ret=g_new0(struct route_path, 1);
2277         ret->in_use=1;
2278         ret->updated=1;
2279         if (pos->lenextra)
2280                 route_path_add_line(ret, &pos->c, &pos->lp, pos->lenextra);
2281         ret->path_hash=item_hash_new();
2282         dstinfo=NULL;
2283         posinfo=pos;
2284         while (s && !dstinfo) { /* following start->seg, which indicates the least costly way to reach our destination */
2285                 segs++;
2286 #if 0
2287                 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
2288 #endif
2289                 if (s->start == start) {
2290                         if (item_is_equal(s->data.item, dst->street->item) && (s->end->seg == s || !posinfo))
2291                                 dstinfo=dst;
2292                         if (!route_path_add_item_from_graph(ret, oldpath, s, 1, posinfo, dstinfo))
2293                                 ret->updated=0;
2294                         start=s->end;
2295                 } else {
2296                         if (item_is_equal(s->data.item, dst->street->item) && (s->start->seg == s || !posinfo))
2297                                 dstinfo=dst;
2298                         if (!route_path_add_item_from_graph(ret, oldpath, s, -1, posinfo, dstinfo))
2299                                 ret->updated=0;
2300                         start=s->start;
2301                 }
2302                 posinfo=NULL;
2303                 s=start->seg;
2304         }
2305         if (dst->lenextra)
2306                 route_path_add_line(ret, &dst->lp, &dst->c, dst->lenextra);
2307         dbg(1, "%d segments\n", segs);
2308         return ret;
2309 }
2310
2311 static int
2312 route_graph_build_next_map(struct route_graph *rg)
2313 {
2314         do {
2315                 rg->m=mapset_next(rg->h, 2);
2316                 if (! rg->m)
2317                         return 0;
2318                 map_rect_destroy(rg->mr);
2319                 rg->mr=map_rect_new(rg->m, rg->sel);
2320         } while (!rg->mr);
2321
2322         return 1;
2323 }
2324
2325
2326 static int
2327 is_turn_allowed(struct route_graph_point *p, struct route_graph_segment *from, struct route_graph_segment *to)
2328 {
2329         struct route_graph_point *prev,*next;
2330         struct route_graph_segment *tmp1,*tmp2;
2331         if (item_is_equal(from->data.item, to->data.item))
2332                 return 0;
2333         if (from->start == p)
2334                 prev=from->end;
2335         else
2336                 prev=from->start;
2337         if (to->start == p)
2338                 next=to->end;
2339         else
2340                 next=to->start;
2341         tmp1=p->end;
2342         while (tmp1) {
2343                 if (tmp1->start->c.x == prev->c.x && tmp1->start->c.y == prev->c.y &&
2344                         (tmp1->data.item.type == type_street_turn_restriction_no ||
2345                         tmp1->data.item.type == type_street_turn_restriction_only)) {
2346                         tmp2=p->start;
2347                         dbg(1,"found %s (0x%x,0x%x) (0x%x,0x%x)-(0x%x,0x%x) %p-%p\n",item_to_name(tmp1->data.item.type),tmp1->data.item.id_hi,tmp1->data.item.id_lo,tmp1->start->c.x,tmp1->start->c.y,tmp1->end->c.x,tmp1->end->c.y,tmp1->start,tmp1->end);
2348                         while (tmp2) {
2349                                 dbg(1,"compare %s (0x%x,0x%x) (0x%x,0x%x)-(0x%x,0x%x) %p-%p\n",item_to_name(tmp2->data.item.type),tmp2->data.item.id_hi,tmp2->data.item.id_lo,tmp2->start->c.x,tmp2->start->c.y,tmp2->end->c.x,tmp2->end->c.y,tmp2->start,tmp2->end);
2350                                 if (item_is_equal(tmp1->data.item, tmp2->data.item))
2351                                         break;
2352                                 tmp2=tmp2->start_next;
2353                         }
2354                         dbg(1,"tmp2=%p\n",tmp2);
2355                         if (tmp2) {
2356                                 dbg(1,"%s tmp2->end=%p next=%p\n",item_to_name(tmp1->data.item.type),tmp2->end,next);
2357                         }
2358                         if (tmp1->data.item.type == type_street_turn_restriction_no && tmp2 && tmp2->end->c.x == next->c.x && tmp2->end->c.y == next->c.y) {
2359                                 dbg(1,"from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x not allowed (no)\n",prev->c.x,prev->c.y,p->c.x,p->c.y,next->c.x,next->c.y);
2360                                 return 0;
2361                         }
2362                         if (tmp1->data.item.type == type_street_turn_restriction_only && tmp2 && (tmp2->end->c.x != next->c.x || tmp2->end->c.y != next->c.y)) {
2363                                 dbg(1,"from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x not allowed (only)\n",prev->c.x,prev->c.y,p->c.x,p->c.y,next->c.x,next->c.y);
2364                                 return 0;
2365                         }
2366                 }
2367                 tmp1=tmp1->end_next;
2368         }
2369         dbg(1,"from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x allowed\n",prev->c.x,prev->c.y,p->c.x,p->c.y,next->c.x,next->c.y);
2370         return 1;
2371 }
2372
2373 static void
2374 route_graph_clone_segment(struct route_graph *this, struct route_graph_segment *s, struct route_graph_point *start, struct route_graph_point *end, int flags)
2375 {
2376         struct route_graph_segment_data data;
2377         data.flags=s->data.flags|flags;
2378         data.offset=1;
2379         data.maxspeed=-1;
2380         data.item=&s->data.item;
2381         data.len=s->data.len+1;
2382         if (s->data.flags & AF_SPEED_LIMIT)
2383                 data.maxspeed=RSD_MAXSPEED(&s->data);
2384         if (s->data.flags & AF_SEGMENTED)
2385                 data.offset=RSD_OFFSET(&s->data);
2386         dbg(1,"cloning segment from %p (0x%x,0x%x) to %p (0x%x,0x%x)\n",start,start->c.x,start->c.y, end, end->c.x, end->c.y);
2387         route_graph_add_segment(this, start, end, &data);
2388 }
2389
2390 static void
2391 route_graph_process_restriction_segment(struct route_graph *this, struct route_graph_point *p, struct route_graph_segment *s, int dir)
2392 {
2393         struct route_graph_segment *tmp;
2394         struct route_graph_point *pn;
2395         struct coord c=p->c;
2396         int dx=0;
2397         int dy=0;
2398         c.x+=dx;
2399         c.y+=dy;
2400         dbg(1,"From %s %d,%d\n",item_to_name(s->data.item.type),dx,dy);
2401         pn=route_graph_point_new(this, &c);
2402         if (dir > 0) { /* going away */
2403                 dbg(1,"other 0x%x,0x%x\n",s->end->c.x,s->end->c.y);
2404                 if (s->data.flags & AF_ONEWAY) {
2405                         dbg(1,"Not possible\n");
2406                         return;
2407                 }
2408                 route_graph_clone_segment(this, s, pn, s->end, AF_ONEWAYREV);
2409         } else { /* coming in */
2410                 dbg(1,"other 0x%x,0x%x\n",s->start->c.x,s->start->c.y);
2411                 if (s->data.flags & AF_ONEWAYREV) {
2412                         dbg(1,"Not possible\n");
2413                         return;
2414                 }
2415                 route_graph_clone_segment(this, s, s->start, pn, AF_ONEWAY);
2416         }
2417         tmp=p->start;
2418         while (tmp) {
2419                 if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no &&
2420                         tmp->data.item.type != type_street_turn_restriction_only &&
2421                         !(tmp->data.flags & AF_ONEWAYREV) && is_turn_allowed(p, s, tmp)) {
2422                         route_graph_clone_segment(this, tmp, pn, tmp->end, AF_ONEWAY);
2423                         dbg(1,"To start %s\n",item_to_name(tmp->data.item.type));
2424                 }
2425                 tmp=tmp->start_next;
2426         }
2427         tmp=p->end;
2428         while (tmp) {
2429                 if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no &&
2430                         tmp->data.item.type != type_street_turn_restriction_only &&
2431                         !(tmp->data.flags & AF_ONEWAY) && is_turn_allowed(p, s, tmp)) {
2432                         route_graph_clone_segment(this, tmp, tmp->start, pn, AF_ONEWAYREV);
2433                         dbg(1,"To end %s\n",item_to_name(tmp->data.item.type));
2434                 }
2435                 tmp=tmp->end_next;
2436         }
2437 }
2438
2439 static void
2440 route_graph_process_restriction_point(struct route_graph *this, struct route_graph_point *p)
2441 {
2442         struct route_graph_segment *tmp;
2443         tmp=p->start;
2444         dbg(1,"node 0x%x,0x%x\n",p->c.x,p->c.y);
2445         while (tmp) {
2446                 if (tmp->data.item.type != type_street_turn_restriction_no &&
2447                         tmp->data.item.type != type_street_turn_restriction_only)
2448                         route_graph_process_restriction_segment(this, p, tmp, 1);
2449                 tmp=tmp->start_next;
2450         }
2451         tmp=p->end;
2452         while (tmp) {
2453                 if (tmp->data.item.type != type_street_turn_restriction_no &&
2454                         tmp->data.item.type != type_street_turn_restriction_only)
2455                         route_graph_process_restriction_segment(this, p, tmp, -1);
2456                 tmp=tmp->end_next;
2457         }
2458         p->flags |= RP_TURN_RESTRICTION_RESOLVED;
2459 }
2460
2461 static void
2462 route_graph_process_restrictions(struct route_graph *this)
2463 {
2464         struct route_graph_point *curr;
2465         int i;
2466         dbg(1,"enter\n");
2467         for (i = 0 ; i < HASH_SIZE ; i++) {
2468                 curr=this->hash[i];
2469                 while (curr) {
2470                         if (curr->flags & RP_TURN_RESTRICTION)
2471                                 route_graph_process_restriction_point(this, curr);
2472                         curr=curr->hash_next;
2473                 }
2474         }
2475 }
2476
2477 static void
2478 route_graph_build_done(struct route_graph *rg, int cancel)
2479 {
2480         dbg(1,"cancel=%d\n",cancel);
2481         if (rg->idle_ev)
2482                 event_remove_idle(rg->idle_ev);
2483         if (rg->idle_cb)
2484                 callback_destroy(rg->idle_cb);
2485         map_rect_destroy(rg->mr);
2486         mapset_close(rg->h);
2487         route_free_selection(rg->sel);
2488         rg->idle_ev=NULL;
2489         rg->idle_cb=NULL;
2490         rg->mr=NULL;
2491         rg->h=NULL;
2492         rg->sel=NULL;
2493         if (! cancel) {
2494                 route_graph_process_restrictions(rg);
2495                 callback_call_0(rg->done_cb);
2496         }
2497         rg->busy=0;
2498 }
2499
2500 static void
2501 route_graph_build_idle(struct route_graph *rg, struct vehicleprofile *profile)
2502 {
2503         int count=1000;
2504         struct item *item;
2505
2506         while (count > 0) {
2507                 for (;;) {
2508                         item=map_rect_get_item(rg->mr);
2509                         if (item)
2510                                 break;
2511                         if (!route_graph_build_next_map(rg)) {
2512                                 route_graph_build_done(rg, 0);
2513                                 return;
2514                         }
2515                 }
2516                 if (item->type == type_traffic_distortion)
2517                         route_process_traffic_distortion(rg, item);
2518                 else if (item->type == type_street_turn_restriction_no || item->type == type_street_turn_restriction_only)
2519                         route_process_turn_restriction(rg, item);
2520                 else
2521                         route_process_street_graph(rg, item, profile);
2522                 count--;
2523         }
2524 }
2525
2526 /**
2527  * @brief Builds a new route graph from a mapset
2528  *
2529  * This function builds a new route graph from a map. Please note that this function does not
2530  * add any routing information to the route graph - this has to be done via the route_graph_flood()
2531  * function.
2532  *
2533  * The function does not create a graph covering the whole map, but only covering the rectangle
2534  * between c1 and c2.
2535  *
2536  * @param ms The mapset to build the route graph from
2537  * @param c1 Corner 1 of the rectangle to use from the map
2538  * @param c2 Corner 2 of the rectangle to use from the map
2539  * @param done_cb The callback which will be called when graph is complete
2540  * @return The new route graph.
2541  */
2542 static struct route_graph *
2543 route_graph_build(struct mapset *ms, struct coord *c, int count, struct callback *done_cb, int async, struct vehicleprofile *profile)
2544 {
2545         struct route_graph *ret=g_new0(struct route_graph, 1);
2546
2547         dbg(1,"enter\n");
2548
2549         ret->sel=route_calc_selection(c, count);
2550         ret->h=mapset_open(ms);
2551         ret->done_cb=done_cb;
2552         ret->busy=1;
2553         if (route_graph_build_next_map(ret)) {
2554                 if (async) {
2555                         ret->idle_cb=callback_new_2(callback_cast(route_graph_build_idle), ret, profile);
2556                         ret->idle_ev=event_add_idle(50, ret->idle_cb);
2557                 }
2558         } else
2559                 route_graph_build_done(ret, 0);
2560
2561         return ret;
2562 }
2563
2564 static void
2565 route_graph_update_done(struct route *this, struct callback *cb)
2566 {
2567         route_graph_flood(this->graph, this->current_dst, this->vehicleprofile, cb);
2568 }
2569
2570 /**
2571  * @brief Updates the route graph
2572  *
2573  * This updates the route graph after settings in the route have changed. It also
2574  * adds routing information afterwards by calling route_graph_flood().
2575  *
2576  * @param this The route to update the graph for
2577  */
2578 static void
2579 route_graph_update(struct route *this, struct callback *cb, int async)
2580 {
2581         struct attr route_status;
2582         struct coord *c=g_alloca(sizeof(struct coord)*(1+g_list_length(this->destinations)));
2583         int i=0;
2584         GList *tmp;
2585
2586         route_status.type=attr_route_status;
2587         route_graph_destroy(this->graph);
2588         this->graph=NULL;
2589         callback_destroy(this->route_graph_done_cb);
2590         this->route_graph_done_cb=callback_new_2(callback_cast(route_graph_update_done), this, cb);
2591         route_status.u.num=route_status_building_graph;
2592         route_set_attr(this, &route_status);
2593         c[i++]=this->pos->c;
2594         tmp=this->destinations;
2595         while (tmp) {
2596                 struct route_info *dst=tmp->data;
2597                 c[i++]=dst->c;
2598                 tmp=g_list_next(tmp);
2599         }
2600         this->graph=route_graph_build(this->ms, c, i, this->route_graph_done_cb, async, this->vehicleprofile);
2601         if (! async) {
2602                 while (this->graph->busy)
2603                         route_graph_build_idle(this->graph, this->vehicleprofile);
2604         }
2605 }
2606
2607 /**
2608  * @brief Gets street data for an item
2609  *
2610  * @param item The item to get the data for
2611  * @return Street data for the item
2612  */
2613 struct street_data *
2614 street_get_data (struct item *item)
2615 {
2616         int count=0,*flags;
2617         struct street_data *ret = NULL, *ret1;
2618         struct attr flags_attr, maxspeed_attr;
2619         const int step = 128;
2620         int c;
2621
2622         do {
2623                 ret1=g_realloc(ret, sizeof(struct street_data)+(count+step)*sizeof(struct coord));
2624                 if (!ret1) {
2625                         if (ret)
2626                                 g_free(ret);
2627                         return NULL;
2628                 }
2629                 ret = ret1;
2630                 c = item_coord_get(item, &ret->c[count], step);
2631                 count += c;
2632         } while (c && c == step);
2633
2634         ret1=g_realloc(ret, sizeof(struct street_data)+count*sizeof(struct coord));
2635         if (ret1)
2636                 ret = ret1;
2637         ret->item=*item;
2638         ret->count=count;
2639         if (item_attr_get(item, attr_flags, &flags_attr))
2640                 ret->flags=flags_attr.u.num;
2641         else {
2642                 flags=item_get_default_flags(item->type);
2643                 if (flags)
2644                         ret->flags=*flags;
2645                 else
2646                         ret->flags=0;
2647         }
2648
2649         ret->maxspeed = -1;
2650         if (ret->flags & AF_SPEED_LIMIT) {
2651                 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr)) {
2652                         ret->maxspeed = maxspeed_attr.u.num;
2653                 }
2654         }
2655
2656         return ret;
2657 }
2658
2659 /**
2660  * @brief Copies street data
2661  *
2662  * @param orig The street data to copy
2663  * @return The copied street data
2664  */
2665 struct street_data *
2666 street_data_dup(struct street_data *orig)
2667 {
2668         struct street_data *ret;
2669         int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
2670
2671         ret=g_malloc(size);
2672         memcpy(ret, orig, size);
2673
2674         return ret;
2675 }
2676
2677 /**
2678  * @brief Frees street data
2679  *
2680  * @param sd Street data to be freed
2681  */
2682 void
2683 street_data_free(struct street_data *sd)
2684 {
2685         g_free(sd);
2686 }
2687
2688 /**
2689  * @brief Finds the nearest street to a given coordinate
2690  *
2691  * @param ms The mapset to search in for the street
2692  * @param pc The coordinate to find a street nearby
2693  * @return The nearest street
2694  */
2695 static struct route_info *
2696 route_find_nearest_street(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc)
2697 {
2698         struct route_info *ret=NULL;
2699         int max_dist=1000;
2700         struct map_selection *sel;
2701         int dist,mindist=0,pos;
2702         struct mapset_handle *h;
2703         struct map *m;
2704         struct map_rect *mr;
2705         struct item *item;
2706         struct coord lp;
2707         struct street_data *sd;
2708         struct coord c;
2709         struct coord_geo g;
2710
2711         ret=g_new0(struct route_info, 1);
2712         mindist = INT_MAX;
2713
2714         h=mapset_open(ms);
2715         while ((m=mapset_next(h,2))) {
2716                 c.x = pc->x;
2717                 c.y = pc->y;
2718                 if (map_projection(m) != pc->pro) {
2719                         transform_to_geo(pc->pro, &c, &g);
2720                         transform_from_geo(map_projection(m), &g, &c);
2721                 }
2722                 sel = route_rect(18, &c, &c, 0, max_dist);
2723                 if (!sel)
2724                         continue;
2725                 mr=map_rect_new(m, sel);
2726                 if (!mr) {
2727                         map_selection_destroy(sel);
2728                         continue;
2729                 }
2730                 while ((item=map_rect_get_item(mr))) {
2731                         if (item_get_default_flags(item->type)) {
2732                                 sd=street_get_data(item);
2733                                 if (!sd)
2734                                         continue;
2735                                 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
2736                                 if (dist < mindist && (
2737                                         (sd->flags & vehicleprofile->flags_forward_mask) == vehicleprofile->flags ||
2738                                         (sd->flags & vehicleprofile->flags_reverse_mask) == vehicleprofile->flags)) {
2739                                         mindist = dist;
2740                                         if (ret->street) {
2741                                                 street_data_free(ret->street);
2742                                         }
2743                                         ret->c=c;
2744                                         ret->lp=lp;
2745                                         ret->pos=pos;
2746                                         ret->street=sd;
2747                                         dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
2748                                 } else {
2749                                         street_data_free(sd);
2750                                 }
2751                         }
2752                 }
2753                 map_selection_destroy(sel);
2754                 map_rect_destroy(mr);
2755         }
2756         mapset_close(h);
2757
2758         if (!ret->street || mindist > max_dist*max_dist) {
2759                 if (ret->street) {
2760                         street_data_free(ret->street);
2761                         dbg(1,"Much too far %d > %d\n", mindist, max_dist);
2762                 }
2763                 g_free(ret);
2764                 ret = NULL;
2765         }
2766
2767         return ret;
2768 }
2769
2770 /**
2771  * @brief Destroys a route_info
2772  *
2773  * @param info The route info to be destroyed
2774  */
2775 void
2776 route_info_free(struct route_info *inf)
2777 {
2778         if (!inf)
2779                 return;
2780         if (inf->street)
2781                 street_data_free(inf->street);
2782         g_free(inf);
2783 }
2784
2785
2786 #include "point.h"
2787
2788 /**
2789  * @brief Returns street data for a route info
2790  *
2791  * @param rinf The route info to return the street data for
2792  * @return Street data for the route info
2793  */
2794 struct street_data *
2795 route_info_street(struct route_info *rinf)
2796 {
2797         return rinf->street;
2798 }
2799
2800 #if 0
2801 struct route_crossings *
2802 route_crossings_get(struct route *this, struct coord *c)
2803 {
2804       struct route_point *pnt;
2805       struct route_segment *seg;
2806       int crossings=0;
2807       struct route_crossings *ret;
2808
2809        pnt=route_graph_get_point(this, c);
2810        seg=pnt->start;
2811        while (seg) {
2812                 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
2813                crossings++;
2814                seg=seg->start_next;
2815        }
2816        seg=pnt->end;
2817        while (seg) {
2818                 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
2819                crossings++;
2820                seg=seg->end_next;
2821        }
2822        ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
2823        ret->count=crossings;
2824        return ret;
2825 }
2826 #endif
2827
2828
2829 struct map_rect_priv {
2830         struct route_info_handle *ri;
2831         enum attr_type attr_next;
2832         int pos;
2833         struct map_priv *mpriv;
2834         struct item item;
2835         unsigned int last_coord;
2836         struct route_path *path;
2837         struct route_path_segment *seg,*seg_next;
2838         struct route_graph_point *point;
2839         struct route_graph_segment *rseg;
2840         char *str;
2841         int hash_bucket;
2842         struct coord *coord_sel;        /**< Set this to a coordinate if you want to filter for just a single route graph point */
2843         struct route_graph_point_iterator it;
2844 };
2845
2846 static void
2847 rm_coord_rewind(void *priv_data)
2848 {
2849         struct map_rect_priv *mr = priv_data;
2850         mr->last_coord = 0;
2851 }
2852
2853 static void
2854 rm_attr_rewind(void *priv_data)
2855 {
2856         struct map_rect_priv *mr = priv_data;
2857         mr->attr_next = attr_street_item;
2858 }
2859
2860 static int
2861 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2862 {
2863         struct map_rect_priv *mr = priv_data;
2864         struct route_path_segment *seg=mr->seg;
2865         struct route *route=mr->mpriv->route;
2866         if (mr->item.type != type_street_route)
2867                 return 0;
2868         attr->type=attr_type;
2869         switch (attr_type) {
2870                 case attr_any:
2871                         while (mr->attr_next != attr_none) {
2872                                 if (rm_attr_get(priv_data, mr->attr_next, attr))
2873                                         return 1;
2874                         }
2875                         return 0;
2876                 case attr_maxspeed:
2877                         mr->attr_next = attr_street_item;
2878                         if (seg && seg->data->flags & AF_SPEED_LIMIT) {
2879                                 attr->u.num=RSD_MAXSPEED(seg->data);
2880
2881                         } else {
2882                                 return 0;
2883                         }
2884                         return 1;
2885                 case attr_street_item:
2886                         mr->attr_next=attr_direction;
2887                         if (seg && seg->data->item.map)
2888                                 attr->u.item=&seg->data->item;
2889                         else
2890                                 return 0;
2891                         return 1;
2892                 case attr_direction:
2893                         mr->attr_next=attr_route;
2894                         if (seg)
2895                                 attr->u.num=seg->direction;
2896                         else
2897                                 return 0;
2898                         return 1;
2899                 case attr_route:
2900                         mr->attr_next=attr_length;
2901                         attr->u.route = mr->mpriv->route;
2902                         return 1;
2903                 case attr_length:
2904                         mr->attr_next=attr_time;
2905                         if (seg)
2906                                 attr->u.num=seg->data->len;
2907                         else
2908                                 return 0;
2909                         return 1;
2910                 case attr_time:
2911                         mr->attr_next=attr_speed;
2912                         if (seg)
2913                                 attr->u.num=route_time_seg(route->vehicleprofile, seg->data, NULL);
2914                         else
2915                                 return 0;
2916                         return 1;
2917                 case attr_speed:
2918                         mr->attr_next=attr_none;
2919                         if (seg)
2920                                 attr->u.num=route_seg_speed(route->vehicleprofile, seg->data, NULL);
2921                         else
2922                                 return 0;
2923                         return 1;
2924                 case attr_label:
2925                         mr->attr_next=attr_none;
2926                         return 0;
2927                 default:
2928                         mr->attr_next=attr_none;
2929                         attr->type=attr_none;
2930                         return 0;
2931         }
2932         return 0;
2933 }
2934
2935 static int
2936 rm_coord_get(void *priv_data, struct coord *c, int count)
2937 {
2938         struct map_rect_priv *mr = priv_data;
2939         struct route_path_segment *seg = mr->seg;
2940         int i,rc=0;
2941         struct route *r = mr->mpriv->route;
2942         enum projection pro = route_projection(r);
2943
2944         if (pro == projection_none)
2945                 return 0;
2946         if (mr->item.type == type_route_start || mr->item.type == type_route_start_reverse || mr->item.type == type_route_end) {
2947                 if (! count || mr->last_coord)
2948                         return 0;
2949                 mr->last_coord=1;
2950                 if (mr->item.type == type_route_start || mr->item.type == type_route_start_reverse)
2951                         c[0]=r->pos->c;
2952                 else {
2953                         c[0]=route_get_dst(r)->c;
2954                 }
2955                 return 1;
2956         }
2957         if (! seg)
2958                 return 0;
2959         for (i=0; i < count; i++) {
2960                 if (mr->last_coord >= seg->ncoords)
2961                         break;
2962                 if (i >= seg->ncoords)
2963                         break;
2964                 if (pro != projection_mg)
2965                         transform_from_to(&seg->c[mr->last_coord++], pro,
2966                                 &c[i],projection_mg);
2967                 else
2968                         c[i] = seg->c[mr->last_coord++];
2969                 rc++;
2970         }
2971         dbg(1,"return %d\n",rc);
2972         return rc;
2973 }
2974
2975 static struct item_methods methods_route_item = {
2976         rm_coord_rewind,
2977         rm_coord_get,
2978         rm_attr_rewind,
2979         rm_attr_get,
2980 };
2981
2982 static void
2983 rp_attr_rewind(void *priv_data)
2984 {
2985         struct map_rect_priv *mr = priv_data;
2986         mr->attr_next = attr_label;
2987 }
2988
2989 static int
2990 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2991 {
2992         struct map_rect_priv *mr = priv_data;
2993         struct route_graph_point *p = mr->point;
2994         struct route_graph_segment *seg = mr->rseg;
2995         struct route *route=mr->mpriv->route;
2996
2997         attr->type=attr_type;
2998         switch (attr_type) {
2999         case attr_any: // works only with rg_points for now
3000                 while (mr->attr_next != attr_none) {
3001                         dbg(0,"querying %s\n", attr_to_name(mr->attr_next));
3002                         if (rp_attr_get(priv_data, mr->attr_next, attr))
3003                                 return 1;
3004                 }
3005                 return 0;
3006         case attr_maxspeed:
3007                 mr->attr_next = attr_label;
3008                 if (mr->item.type != type_rg_segment)
3009                         return 0;
3010                 if (seg && (seg->data.flags & AF_SPEED_LIMIT)) {
3011                         attr->type = attr_maxspeed;
3012                         attr->u.num=RSD_MAXSPEED(&seg->data);
3013                         return 1;
3014                 } else {
3015                         return 0;
3016                 }
3017         case attr_label:
3018                 mr->attr_next=attr_street_item;
3019                 if (mr->item.type != type_rg_point)
3020                         return 0;
3021                 attr->type = attr_label;
3022                 if (mr->str)
3023                         g_free(mr->str);
3024                 if (p->value != INT_MAX)
3025                         mr->str=g_strdup_printf("%d", p->value);
3026                 else
3027                         mr->str=g_strdup("-");
3028                 attr->u.str = mr->str;
3029                 return 1;
3030         case attr_street_item:
3031                 mr->attr_next=attr_flags;
3032                 if (mr->item.type != type_rg_segment)
3033                         return 0;
3034                 if (seg && seg->data.item.map)
3035                         attr->u.item=&seg->data.item;
3036                 else
3037                         return 0;
3038                 return 1;
3039         case attr_flags:
3040                 mr->attr_next = attr_direction;
3041                 if (mr->item.type != type_rg_segment)
3042                         return 0;
3043                 if (seg) {
3044                         attr->u.num = seg->data.flags;
3045                 } else {
3046                         return 0;
3047                 }
3048                 return 1;
3049         case attr_direction:
3050                 mr->attr_next = attr_debug;
3051                 // This only works if the map has been opened at a single point, and in that case indicates if the
3052                 // segment returned last is connected to this point via its start (1) or its end (-1)
3053                 if (!mr->coord_sel || (mr->item.type != type_rg_segment))
3054                         return 0;
3055                 if (seg->start == mr->point) {
3056                         attr->u.num=1;
3057                 } else if (seg->end == mr->point) {
3058                         attr->u.num=-1;
3059                 } else {
3060                         return 0;
3061                 }
3062                 return 1;
3063         case attr_debug:
3064                 mr->attr_next=attr_none;
3065                 if (mr->str)
3066                         g_free(mr->str);
3067                 switch (mr->item.type) {
3068                 case type_rg_point:
3069                 {
3070                         struct route_graph_segment *tmp;
3071                         int start=0;
3072                         int end=0;
3073                         tmp=p->start;
3074                         while (tmp) {
3075                                 start++;
3076                                 tmp=tmp->start_next;
3077                         }
3078                         tmp=p->end;
3079                         while (tmp) {
3080                                 end++;
3081                                 tmp=tmp->end_next;
3082                         }
3083                         mr->str=g_strdup_printf("%d %d %p (0x%x,0x%x)", start, end, p, p->c.x, p->c.y);
3084                         attr->u.str = mr->str;
3085                 }
3086                         return 1;
3087                 case type_rg_segment:
3088                         if (! seg)
3089                                 return 0;
3090                         mr->str=g_strdup_printf("len %d time %d start %p end %p",seg->data.len, route_time_seg(route->vehicleprofile, &seg->data, NULL), seg->start, seg->end);
3091                         attr->u.str = mr->str;
3092                         return 1;
3093                 default:
3094                         return 0;
3095                 }
3096         default:
3097                 mr->attr_next=attr_none;
3098                 attr->type=attr_none;
3099                 return 0;
3100         }
3101 }
3102
3103 /**
3104  * @brief Returns the coordinates of a route graph item
3105  *
3106  * @param priv_data The route graph item's private data
3107  * @param c Pointer where to store the coordinates
3108  * @param count How many coordinates to get at a max?
3109  * @return The number of coordinates retrieved
3110  */
3111 static int
3112 rp_coord_get(void *priv_data, struct coord *c, int count)
3113 {
3114         struct map_rect_priv *mr = priv_data;
3115         struct route_graph_point *p = mr->point;
3116         struct route_graph_segment *seg = mr->rseg;
3117         int rc = 0,i,dir;
3118         struct route *r = mr->mpriv->route;
3119         enum projection pro = route_projection(r);
3120
3121         if (pro == projection_none)
3122                 return 0;
3123         for (i=0; i < count; i++) {
3124                 if (mr->item.type == type_rg_point) {
3125                         if (mr->last_coord >= 1)
3126                                 break;
3127                         if (pro != projection_mg)
3128                                 transform_from_to(&p->c, pro,
3129                                         &c[i],projection_mg);
3130                         else
3131                                 c[i] = p->c;
3132                 } else {
3133                         if (mr->last_coord >= 2)
3134                                 break;
3135                         dir=0;
3136                         if (seg->end->seg == seg)
3137                                 dir=1;
3138                         if (mr->last_coord)
3139                                 dir=1-dir;
3140                         if (dir) {
3141                                 if (pro != projection_mg)
3142                                         transform_from_to(&seg->end->c, pro,
3143                                                 &c[i],projection_mg);
3144                                 else
3145                                         c[i] = seg->end->c;
3146                         } else {
3147                                 if (pro != projection_mg)
3148                                         transform_from_to(&seg->start->c, pro,
3149                                                 &c[i],projection_mg);
3150                                 else
3151                                         c[i] = seg->start->c;
3152                         }
3153                 }
3154                 mr->last_coord++;
3155                 rc++;
3156         }
3157         return rc;
3158 }
3159
3160 static struct item_methods methods_point_item = {
3161         rm_coord_rewind,
3162         rp_coord_get,
3163         rp_attr_rewind,
3164         rp_attr_get,
3165 };
3166
3167 static void
3168 rp_destroy(struct map_priv *priv)
3169 {
3170         g_free(priv);
3171 }
3172
3173 static void
3174 rm_destroy(struct map_priv *priv)
3175 {
3176         g_free(priv);
3177 }
3178
3179 static struct map_rect_priv *
3180 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
3181 {
3182         struct map_rect_priv * mr;
3183         dbg(1,"enter\n");
3184 #if 0
3185         if (! route_get_pos(priv->route))
3186                 return NULL;
3187         if (! route_get_dst(priv->route))
3188                 return NULL;
3189 #endif
3190 #if 0
3191         if (! priv->route->path2)
3192                 return NULL;
3193 #endif
3194         mr=g_new0(struct map_rect_priv, 1);
3195         mr->mpriv = priv;
3196         mr->item.priv_data = mr;
3197         mr->item.type = type_none;
3198         mr->item.meth = &methods_route_item;
3199         if (priv->route->path2) {
3200                 mr->path=priv->route->path2;
3201                 mr->seg_next=mr->path->path;
3202                 mr->path->in_use++;
3203         } else
3204                 mr->seg_next=NULL;
3205         return mr;
3206 }
3207
3208 /**
3209  * @brief Opens a new map rectangle on the route graph's map
3210  *
3211  * This function opens a new map rectangle on the route graph's map.
3212  * The "sel" parameter enables you to only search for a single route graph
3213  * point on this map (or exactly: open a map rectangle that only contains
3214  * this one point). To do this, pass here a single map selection, whose
3215  * c_rect has both coordinates set to the same point. Otherwise this parameter
3216  * has no effect.
3217  *
3218  * @param priv The route graph map's private data
3219  * @param sel Here it's possible to specify a point for which to search. Please read the function's description.
3220  * @return A new map rect's private data
3221  */
3222 static struct map_rect_priv *
3223 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
3224 {
3225         struct map_rect_priv * mr;
3226
3227         dbg(1,"enter\n");
3228         if (! priv->route->graph)
3229                 return NULL;
3230         mr=g_new0(struct map_rect_priv, 1);
3231         mr->mpriv = priv;
3232         mr->item.priv_data = mr;
3233         mr->item.type = type_rg_point;
3234         mr->item.meth = &methods_point_item;
3235         if (sel) {
3236                 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)) {
3237                         mr->coord_sel = g_malloc(sizeof(struct coord));
3238                         *(mr->coord_sel) = sel->u.c_rect.lu;
3239                 }
3240         }
3241         return mr;
3242 }
3243
3244 static void
3245 rm_rect_destroy(struct map_rect_priv *mr)
3246 {
3247         if (mr->str)
3248                 g_free(mr->str);
3249         if (mr->coord_sel) {
3250                 g_free(mr->coord_sel);
3251         }
3252         if (mr->path) {
3253                 mr->path->in_use--;
3254                 if (mr->path->update_required && (mr->path->in_use==1))
3255                         route_path_update_done(mr->mpriv->route, mr->path->update_required-1);
3256                 else if (!mr->path->in_use)
3257                         g_free(mr->path);
3258         }
3259
3260         g_free(mr);
3261 }
3262
3263 static struct item *
3264 rp_get_item(struct map_rect_priv *mr)
3265 {
3266         struct route *r = mr->mpriv->route;
3267         struct route_graph_point *p = mr->point;
3268         struct route_graph_segment *seg = mr->rseg;
3269
3270         if (mr->item.type == type_rg_point) {
3271                 if (mr->coord_sel) {
3272                         // We are supposed to return only the point at one specified coordinate...
3273                         if (!p) {
3274                                 p = route_graph_get_point_last(r->graph, mr->coord_sel);
3275                                 if (!p) {
3276                                         mr->point = NULL; // This indicates that no point has been found
3277                                 } else {
3278                                         mr->it = rp_iterator_new(p);
3279                                 }
3280                         } else {
3281                                 p = NULL;
3282                         }
3283                 } else {
3284                         if (!p) {
3285                                 mr->hash_bucket=0;
3286                                 p = r->graph->hash[0];
3287                         } else
3288                                 p=p->hash_next;
3289                         while (!p) {
3290                                 mr->hash_bucket++;
3291                                 if (mr->hash_bucket >= HASH_SIZE)
3292                                         break;
3293                                 p = r->graph->hash[mr->hash_bucket];
3294                         }
3295                 }
3296                 if (p) {
3297                         mr->point = p;
3298                         mr->item.id_lo++;
3299                         rm_coord_rewind(mr);
3300                         rp_attr_rewind(mr);
3301                         return &mr->item;
3302                 } else
3303                         mr->item.type = type_rg_segment;
3304         }
3305
3306         if (mr->coord_sel) {
3307                 if (!mr->point) { // This means that no point has been found
3308                         return NULL;
3309                 }
3310                 seg = rp_iterator_next(&(mr->it));
3311         } else {
3312                 if (!seg)
3313                         seg=r->graph->route_segments;
3314                 else
3315                         seg=seg->next;
3316         }
3317
3318         if (seg) {
3319                 mr->rseg = seg;
3320                 mr->item.id_lo++;
3321                 rm_coord_rewind(mr);
3322                 rp_attr_rewind(mr);
3323                 return &mr->item;
3324         }
3325         return NULL;
3326
3327 }
3328
3329 static struct item *
3330 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
3331 {
3332         struct item *ret=NULL;
3333         while (id_lo-- > 0)
3334                 ret=rp_get_item(mr);
3335         return ret;
3336 }
3337
3338
3339 static struct item *
3340 rm_get_item(struct map_rect_priv *mr)
3341 {
3342         struct route *route=mr->mpriv->route;
3343         dbg(1,"enter\n", mr->pos);
3344
3345         switch (mr->item.type) {
3346         case type_none:
3347                 if (route->pos && route->pos->street_direction && route->pos->street_direction != route->pos->dir)
3348                         mr->item.type=type_route_start_reverse;
3349                 else
3350                         mr->item.type=type_route_start;
3351                 if (route->pos)
3352                         break;
3353         default:
3354                 mr->item.type=type_street_route;
3355                 mr->seg=mr->seg_next;
3356                 if (!mr->seg && mr->path && mr->path->next) {
3357                         struct route_path *p=NULL;
3358                         mr->path->in_use--;
3359                         if (!mr->path->in_use)
3360                                 p=mr->path;
3361                         mr->path=mr->path->next;
3362                         mr->path->in_use++;
3363                         mr->seg=mr->path->path;
3364                         if (p)
3365                                 g_free(p);
3366                 }
3367                 if (mr->seg) {
3368                         mr->seg_next=mr->seg->next;
3369                         break;
3370                 }
3371                 mr->item.type=type_route_end;
3372                 if (mr->mpriv->route->destinations)
3373                         break;
3374         case type_route_end:
3375                 return NULL;
3376         }
3377         mr->last_coord = 0;
3378         mr->item.id_lo++;
3379         rm_attr_rewind(mr);
3380         return &mr->item;
3381 }
3382
3383 static struct item *
3384 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
3385 {
3386         struct item *ret=NULL;
3387         while (id_lo-- > 0)
3388                 ret=rm_get_item(mr);
3389         return ret;
3390 }
3391
3392 static struct map_methods route_meth = {
3393         projection_mg,
3394         "utf-8",
3395         rm_destroy,
3396         rm_rect_new,
3397         rm_rect_destroy,
3398         rm_get_item,
3399         rm_get_item_byid,
3400         NULL,
3401         NULL,
3402         NULL,
3403 };
3404
3405 static struct map_methods route_graph_meth = {
3406         projection_mg,
3407         "utf-8",
3408         rp_destroy,
3409         rp_rect_new,
3410         rm_rect_destroy,
3411         rp_get_item,
3412         rp_get_item_byid,
3413         NULL,
3414         NULL,
3415         NULL,
3416 };
3417
3418 static struct map_priv *
3419 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
3420 {
3421         struct map_priv *ret;
3422         struct attr *route_attr;
3423
3424         route_attr=attr_search(attrs, NULL, attr_route);
3425         if (! route_attr)
3426                 return NULL;
3427         ret=g_new0(struct map_priv, 1);
3428         if (graph)
3429                 *meth=route_graph_meth;
3430         else
3431                 *meth=route_meth;
3432         ret->route=route_attr->u.route;
3433
3434         return ret;
3435 }
3436
3437 static struct map_priv *
3438 route_map_new(struct map_methods *meth, struct attr **attrs, struct callback_list *cbl)
3439 {
3440         return route_map_new_helper(meth, attrs, 0);
3441 }
3442
3443 static struct map_priv *
3444 route_graph_map_new(struct map_methods *meth, struct attr **attrs, struct callback_list *cbl)
3445 {
3446         return route_map_new_helper(meth, attrs, 1);
3447 }
3448
3449 static struct map *
3450 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
3451 {
3452         struct attr *attrs[5];
3453         struct attr a_type,navigation,data,a_description;
3454         a_type.type=attr_type;
3455         a_type.u.str=type;
3456         navigation.type=attr_route;
3457         navigation.u.route=this_;
3458         data.type=attr_data;
3459         data.u.str="";
3460         a_description.type=attr_description;
3461         a_description.u.str=description;
3462
3463         attrs[0]=&a_type;
3464         attrs[1]=&navigation;
3465         attrs[2]=&data;
3466         attrs[3]=&a_description;
3467         attrs[4]=NULL;
3468
3469         if (! *map) {
3470                 *map=map_new(NULL, attrs);
3471                 map_ref(*map);
3472         }
3473
3474         return *map;
3475 }
3476
3477 /**
3478  * @brief Returns a new map containing the route path
3479  *
3480  * This function returns a new map containing the route path.
3481  *
3482  * @important Do not map_destroy() this!
3483  *
3484  * @param this_ The route to get the map of
3485  * @return A new map containing the route path
3486  */
3487 struct map *
3488 route_get_map(struct route *this_)
3489 {
3490         return route_get_map_helper(this_, &this_->map, "route","Route");
3491 }
3492
3493
3494 /**
3495  * @brief Returns a new map containing the route graph
3496  *
3497  * This function returns a new map containing the route graph.
3498  *
3499  * @important Do not map_destroy()  this!
3500  *
3501  * @param this_ The route to get the map of
3502  * @return A new map containing the route graph
3503  */
3504 struct map *
3505 route_get_graph_map(struct route *this_)
3506 {
3507         return route_get_map_helper(this_, &this_->graph_map, "route_graph","Route Graph");
3508 }
3509
3510 void
3511 route_set_projection(struct route *this_, enum projection pro)
3512 {
3513 }
3514
3515 int
3516 route_set_attr(struct route *this_, struct attr *attr)
3517 {
3518         int attr_updated=0;
3519         switch (attr->type) {
3520         case attr_route_status:
3521                 attr_updated = (this_->route_status != attr->u.num);
3522                 this_->route_status = attr->u.num;
3523                 break;
3524         case attr_destination:
3525                 route_set_destination(this_, attr->u.pcoord, 1);
3526                 return 1;
3527         case attr_vehicle:
3528                 attr_updated = (this_->v != attr->u.vehicle);
3529                 this_->v=attr->u.vehicle;
3530                 if (attr_updated) {
3531                         struct attr g;
3532                         struct pcoord pc;
3533                         struct coord c;
3534                         if (vehicle_get_attr(this_->v, attr_position_coord_geo, &g, NULL)) {
3535                                 pc.pro=projection_mg;
3536                                 transform_from_geo(projection_mg, g.u.coord_geo, &c);
3537                                 pc.x=c.x;
3538                                 pc.y=c.y;
3539                                 route_set_position(this_, &pc);
3540                         }
3541                 }
3542                 break;
3543         default:
3544                 dbg(0,"unsupported attribute: %s\n",attr_to_name(attr->type));
3545                 return 0;
3546         }
3547         if (attr_updated)
3548                 callback_list_call_attr_2(this_->cbl2, attr->type, this_, attr);
3549         return 1;
3550 }
3551
3552 int
3553 route_add_attr(struct route *this_, struct attr *attr)
3554 {
3555         switch (attr->type) {
3556         case attr_callback:
3557                 callback_list_add(this_->cbl2, attr->u.callback);
3558                 return 1;
3559         default:
3560                 return 0;
3561         }
3562 }
3563
3564 int
3565 route_remove_attr(struct route *this_, struct attr *attr)
3566 {
3567         dbg(0,"enter\n");
3568         switch (attr->type) {
3569         case attr_callback:
3570                 callback_list_remove(this_->cbl2, attr->u.callback);
3571                 return 1;
3572         case attr_vehicle:
3573                 this_->v=NULL;
3574                 return 1;
3575         default:
3576                 return 0;
3577         }
3578 }
3579
3580 int
3581 route_get_attr(struct route *this_, enum attr_type type, struct attr *attr, struct attr_iter *iter)
3582 {
3583         int ret=1;
3584         switch (type) {
3585         case attr_map:
3586                 attr->u.map=route_get_map(this_);
3587                 ret=(attr->u.map != NULL);
3588                 break;
3589         case attr_destination:
3590                 if (this_->destinations) {
3591                         struct route_info *dst;
3592                         if (iter) {
3593                                 if (iter->u.list) {
3594                                         iter->u.list=g_list_next(iter->u.list);
3595                                 } else {
3596                                         iter->u.list=this_->destinations;
3597                                 }
3598                                 if (!iter->u.list) {
3599                                         return 0;
3600                                 }
3601                                 dst = (struct route_info*)iter->u.list->data;
3602                         } else { //No iter handling
3603                                 dst=route_get_dst(this_);
3604                         }
3605                         attr->u.pcoord=&this_->pc;
3606                         this_->pc.pro=projection_mg; /* fixme */
3607                         this_->pc.x=dst->c.x;
3608                         this_->pc.y=dst->c.y;
3609                 } else
3610                         ret=0;
3611                 break;
3612         case attr_vehicle:
3613                 attr->u.vehicle=this_->v;
3614                 ret=(this_->v != NULL);
3615                 dbg(0,"get vehicle %p\n",this_->v);
3616                 break;
3617         case attr_vehicleprofile:
3618                 attr->u.vehicleprofile=this_->vehicleprofile;
3619                 ret=(this_->vehicleprofile != NULL);
3620                 break;
3621         case attr_route_status:
3622                 attr->u.num=this_->route_status;
3623                 break;
3624         case attr_destination_time:
3625                 if (this_->path2 && (this_->route_status == route_status_path_done_new || this_->route_status == route_status_path_done_incremental)) {
3626
3627                         attr->u.num=this_->path2->path_time;
3628                         dbg(1,"path_time %d\n",attr->u.num);
3629                 }
3630                 else
3631                         ret=0;
3632                 break;
3633         case attr_destination_length:
3634                 if (this_->path2 && (this_->route_status == route_status_path_done_new || this_->route_status == route_status_path_done_incremental))
3635                         attr->u.num=this_->path2->path_len;
3636                 else
3637                         ret=0;
3638                 break;
3639         default:
3640                 return 0;
3641         }
3642         attr->type=type;
3643         return ret;
3644 }
3645
3646 struct attr_iter *
3647 route_attr_iter_new(void)
3648 {
3649         return g_new0(struct attr_iter, 1);
3650 }
3651
3652 void
3653 route_attr_iter_destroy(struct attr_iter *iter)
3654 {
3655         g_free(iter);
3656 }
3657
3658 void
3659 route_init(void)
3660 {
3661         plugin_register_map_type("route", route_map_new);
3662         plugin_register_map_type("route_graph", route_graph_map_new);
3663 }
3664
3665 void
3666 route_destroy(struct route *this_)
3667 {
3668         route_path_destroy(this_->path2,1);
3669         route_graph_destroy(this_->graph);
3670         route_clear_destinations(this_);
3671         route_info_free(this_->pos);
3672         map_destroy(this_->map);
3673         map_destroy(this_->graph_map);
3674         g_free(this_);
3675 }