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

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