git.maemo.org Git - navit-package/blob - navit/navigation.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 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <math.h>
  24 #include <glib.h>
  25 #include "debug.h"
  26 #include "profile.h"
  27 #include "navigation.h"
  28 #include "coord.h"
  29 #include "item.h"
  30 #include "route.h"
  31 #include "transform.h"
  32 #include "mapset.h"
  33 #include "projection.h"
  34 #include "map.h"
  35 #include "navit.h"
  36 #include "callback.h"
  37 #include "plugin.h"
  38 #include "navit_nls.h"
  39
  40 /* #define DEBUG */
  41
  42 struct suffix {
  43         char *fullname;
  44         char *abbrev;
  45         int sex;
  46 } suffixes[]= {
  47         {"weg",NULL,1},
  48         {"platz","pl.",1},
  49         {"ring",NULL,1},
  50         {"allee",NULL,2},
  51         {"gasse",NULL,2},
  52         {"straße","str.",2},
  53         {"strasse",NULL,2},
  54 };
  55
  56 struct navigation {
  57         struct map *map;
  58         struct item_hash *hash;
  59         struct navigation_itm *first;
  60         struct navigation_itm *last;
  61         struct navigation_command *cmd_first;
  62         struct navigation_command *cmd_last;
  63         struct callback_list *callback_speech;
  64         struct callback_list *callback;
  65         int level_last;
  66         struct item item_last;
  67         int turn_around;
  68         int turn_around_limit;
  69         int distance_turn;
  70         int distance_last;
  71         int announce[route_item_last-route_item_first+1][3];
  72 };
  73
  74
  75 struct navigation_command {
  76         struct navigation_itm *itm;
  77         struct navigation_command *next;
  78         int delta;
  79         int roundabout_delta;
  80         int length;
  81 };
  82
  83 /**
  84  * @brief Calculates the delta between two angles
  85  * @param angle1 The first angle
  86  * @param angle2 The second angle
  87  * @return The difference between the angles: -179..-1=angle2 is left of angle1,0=same,1..179=angle2 is right of angle1,180=angle1 is opposite of angle2
  88  */
  89
  90 static int
  91 angle_delta(int angle1, int angle2)
  92 {
  93         int delta=angle2-angle1;
  94         if (delta <= -180)
  95                 delta+=360;
  96         if (delta > 180)
  97                 delta-=360;
  98         return delta;
  99 }
 100
 101 struct navigation *
 102 navigation_new(struct attr **attrs)
 103 {
 104         int i,j;
 105         struct navigation *ret=g_new0(struct navigation, 1);
 106         ret->hash=item_hash_new();
 107         ret->callback=callback_list_new();
 108         ret->callback_speech=callback_list_new();
 109         ret->level_last=-2;
 110         ret->distance_last=-2;
 111         ret->distance_turn=50;
 112         ret->turn_around_limit=3;
 113
 114         for (j = 0 ; j <= route_item_last-route_item_first ; j++) {
 115                 for (i = 0 ; i < 3 ; i++) {
 116                         ret->announce[j][i]=-1;
 117                 }
 118         }
 119
 120         return ret;
 121 }
 122
 123 int
 124 navigation_set_announce(struct navigation *this_, enum item_type type, int *level)
 125 {
 126         int i;
 127         if (type < route_item_first || type > route_item_last) {
 128                 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
 129                 return 0;
 130         }
 131         for (i = 0 ; i < 3 ; i++)
 132                 this_->announce[type-route_item_first][i]=level[i];
 133         return 1;
 134 }
 135
 136 static int
 137 navigation_get_announce_level(struct navigation *this_, enum item_type type, int dist)
 138 {
 139         int i;
 140
 141         if (type < route_item_first || type > route_item_last)
 142                 return -1;
 143         for (i = 0 ; i < 3 ; i++) {
 144                 if (dist <= this_->announce[type-route_item_first][i])
 145                         return i;
 146         }
 147         return i;
 148 }
 149
 150 /**
 151  * @brief Holds a way that one could possibly drive from a navigation item
 152  */
 153 struct navigation_way {
 154         struct navigation_way *next;            /**< Pointer to a linked-list of all navigation_ways from this navigation item */
 155         short dir;                      /**< The direction -1 or 1 of the way */
 156         short angle2;                   /**< The angle one has to steer to drive from the old item to this street */
 157         int flags;                      /**< The flags of the way */
 158         struct item item;               /**< The item of the way */
 159         char *name1;
 160         char *name2;
 161 };
 162
 163 struct navigation_itm {
 164         char *name1;
 165         char *name2;
 166         struct item item;
 167         int direction;
 168         int angle_start;
 169         int angle_end;
 170         struct coord start,end;
 171         int time;
 172         int length;
 173         int dest_time;
 174         int dest_length;
 175         int told;
 176         int dest_count;
 177         int flags;
 178         struct navigation_itm *next;
 179         struct navigation_itm *prev;
 180         struct navigation_way *ways;            /**< Pointer to all ways one could drive from here */
 181 };
 182
 183 /* 0=N,90=E */
 184 static int
 185 road_angle(struct coord *c1, struct coord *c2, int dir)
 186 {
 187         int ret=transform_get_angle_delta(c1, c2, dir);
 188         dbg(1, "road_angle(0x%x,0x%x - 0x%x,0x%x)=%d\n", c1->x, c1->y, c2->x, c2->y, ret);
 189         return ret;
 190 }
 191
 192 static char
 193 *get_count_str(int n)
 194 {
 195         switch (n) {
 196         case 0:
 197                 return _("zeroth"); // Not shure if this exists, neither if it will ever be needed
 198         case 1:
 199                 return _("first");
 200         case 2:
 201                 return _("second");
 202         case 3:
 203                 return _("third");
 204         case 4:
 205                 return _("fourth");
 206         case 5:
 207                 return _("fifth");
 208         case 6:
 209                 return _("sixth");
 210         default:
 211                 return NULL;
 212         }
 213 }
 214
 215 static int
 216 round_distance(int dist)
 217 {
 218         if (dist < 100) {
 219                 dist=(dist+5)/10;
 220                 return dist*10;
 221         }
 222         if (dist < 250) {
 223                 dist=(dist+13)/25;
 224                 return dist*25;
 225         }
 226         if (dist < 500) {
 227                 dist=(dist+25)/50;
 228                 return dist*50;
 229         }
 230         if (dist < 1000) {
 231                 dist=(dist+50)/100;
 232                 return dist*100;
 233         }
 234         if (dist < 5000) {
 235                 dist=(dist+50)/100;
 236                 return dist*100;
 237         }
 238         if (dist < 100000) {
 239                 dist=(dist+500)/1000;
 240                 return dist*1000;
 241         }
 242         dist=(dist+5000)/10000;
 243         return dist*10000;
 244 }
 245
 246 static char *
 247 get_distance(int dist, enum attr_type type, int is_length)
 248 {
 249         if (type == attr_navigation_long) {
 250                 if (is_length)
 251                         return g_strdup_printf(_("%d m"), dist);
 252                 else
 253                         return g_strdup_printf(_("in %d m"), dist);
 254         }
 255         if (dist < 1000) {
 256                 if (is_length)
 257                         return g_strdup_printf(_("%d meters"), dist);
 258                 else
 259                         return g_strdup_printf(_("in %d meters"), dist);
 260         }
 261         if (dist < 5000) {
 262                 int rem=(dist/100)%10;
 263                 if (rem) {
 264                         if (is_length)
 265                                 return g_strdup_printf(_("%d.%d kilometer"), dist/1000, rem);
 266                         else
 267                                 return g_strdup_printf(_("in %d.%d kilometers"), dist/1000, rem);
 268                 }
 269         }
 270         if (is_length)
 271                 return g_strdup_printf(ngettext("one kilometer","%d kilometers", dist/1000), dist/1000);
 272         else
 273                 return g_strdup_printf(ngettext("in one kilometer","in %d kilometers", dist/1000), dist/1000);
 274 }
 275
 276
 277 /**
 278  * @brief This calculates the angle with which an item starts or ends
 279  *
 280  * This function can be used to get the angle an item (from a route graph map)
 281  * starts or ends with. Note that the angle will point towards the inner of
 282  * the item.
 283  *
 284  * This is meant to be used with items from a route graph map
 285  * With other items this will probably not be optimal...
 286  *
 287  * @param w The way which should be calculated
 288  */
 289 static void
 290 calculate_angle(struct navigation_way *w)
 291 {
 292         struct coord cbuf[2];
 293         struct item *ritem; // the "real" item
 294         struct coord c;
 295         struct map_rect *mr;
 296         struct attr attr;
 297
 298         w->angle2=361;
 299         mr = map_rect_new(w->item.map, NULL);
 300         if (!mr)
 301                 return;
 302
 303         ritem = map_rect_get_item_byid(mr, w->item.id_hi, w->item.id_lo);
 304         if (!ritem) {
 305                 dbg(1,"Item from segment not found on map!\n");
 306                 map_rect_destroy(mr);
 307                 return;
 308         }
 309
 310         if (ritem->type < type_line || ritem->type >= type_area) {
 311                 map_rect_destroy(mr);
 312                 return;
 313         }
 314         if (item_attr_get(ritem, attr_flags, &attr))
 315                 w->flags=attr.u.num;
 316         else
 317                 w->flags=0;
 318         if (item_attr_get(ritem, attr_street_name, &attr))
 319                 w->name1=map_convert_string(ritem->map,attr.u.str);
 320         else
 321                 w->name1=NULL;
 322         if (item_attr_get(ritem, attr_street_name_systematic, &attr))
 323                 w->name2=map_convert_string(ritem->map,attr.u.str);
 324         else
 325                 w->name2=NULL;
 326
 327         if (w->dir < 0) {
 328                 if (item_coord_get(ritem, cbuf, 2) != 2) {
 329                         dbg(1,"Using calculate_angle() with a less-than-two-coords-item?\n");
 330                         map_rect_destroy(mr);
 331                         return;
 332                 }
 333
 334                 while (item_coord_get(ritem, &c, 1)) {
 335                         cbuf[0] = cbuf[1];
 336                         cbuf[1] = c;
 337                 }
 338
 339         } else {
 340                 if (item_coord_get(ritem, cbuf, 2) != 2) {
 341                         dbg(1,"Using calculate_angle() with a less-than-two-coords-item?\n");
 342                         map_rect_destroy(mr);
 343                         return;
 344                 }
 345                 c = cbuf[0];
 346                 cbuf[0] = cbuf[1];
 347                 cbuf[1] = c;
 348         }
 349
 350         map_rect_destroy(mr);
 351
 352         w->angle2=road_angle(&cbuf[1],&cbuf[0],0);
 353 }
 354
 355 /**
 356  * @brief Clears the ways one can drive from itm
 357  *
 358  * @param itm The item that should have its ways cleared
 359  */
 360 static void
 361 navigation_itm_ways_clear(struct navigation_itm *itm)
 362 {
 363         struct navigation_way *c,*n;
 364
 365         c = itm->ways;
 366         while (c) {
 367                 n = c->next;
 368                 map_convert_free(c->name1);
 369                 map_convert_free(c->name2);
 370                 g_free(c);
 371                 c = n;
 372         }
 373
 374         itm->ways = NULL;
 375 }
 376
 377 /**
 378  * @brief Updates the ways one can drive from itm
 379  *
 380  * This updates the list of possible ways to drive to from itm. The item "itm" is on
 381  * and the next navigation item are excluded.
 382  *
 383  * @param itm The item that should be updated
 384  * @param graph_map The route graph's map that these items are on
 385  */
 386 static void
 387 navigation_itm_ways_update(struct navigation_itm *itm, struct map *graph_map)
 388 {
 389         struct map_selection coord_sel;
 390         struct map_rect *g_rect; // Contains a map rectangle from the route graph's map
 391         struct item *i,*sitem;
 392         struct attr sitem_attr,direction_attr;
 393         struct navigation_way *w,*l;
 394
 395         navigation_itm_ways_clear(itm);
 396
 397         // These values cause the code in route.c to get us only the route graph point and connected segments
 398         coord_sel.next = NULL;
 399         coord_sel.u.c_rect.lu = itm->start;
 400         coord_sel.u.c_rect.rl = itm->start;
 401         // the selection's order is ignored
 402
 403         g_rect = map_rect_new(graph_map, &coord_sel);
 404
 405         i = map_rect_get_item(g_rect);
 406         if (!i || i->type != type_rg_point) { // probably offroad?
 407                 return ;
 408         }
 409
 410         w = NULL;
 411
 412         while (1) {
 413                 i = map_rect_get_item(g_rect);
 414
 415                 if (!i) {
 416                         break;
 417                 }
 418
 419                 if (i->type != type_rg_segment) {
 420                         continue;
 421                 }
 422
 423                 if (!item_attr_get(i,attr_street_item,&sitem_attr)) {
 424                         dbg(1, "Got no street item for route graph item in entering_straight()\n");
 425                         continue;
 426                 }
 427
 428                 if (!item_attr_get(i,attr_direction,&direction_attr)) {
 429                         continue;
 430                 }
 431
 432                 sitem = sitem_attr.u.item;
 433                 if (item_is_equal(itm->item,*sitem) || ((itm->prev) && item_is_equal(itm->prev->item,*sitem))) {
 434                         continue;
 435                 }
 436
 437                 l = w;
 438                 w = g_new(struct navigation_way, 1);
 439                 w->dir = direction_attr.u.num;
 440                 w->item = *sitem;
 441                 w->next = l;
 442                 calculate_angle(w);
 443         }
 444
 445         map_rect_destroy(g_rect);
 446
 447         itm->ways = w;
 448 }
 449
 450 static void
 451 navigation_destroy_itms_cmds(struct navigation *this_, struct navigation_itm *end)
 452 {
 453         struct navigation_itm *itm;
 454         struct navigation_command *cmd;
 455         dbg(2,"enter this_=%p this_->first=%p this_->cmd_first=%p end=%p\n", this_, this_->first, this_->cmd_first, end);
 456         if (this_->cmd_first)
 457                 dbg(2,"this_->cmd_first->itm=%p\n", this_->cmd_first->itm);
 458         while (this_->first && this_->first != end) {
 459                 itm=this_->first;
 460                 dbg(3,"destroying %p\n", itm);
 461                 item_hash_remove(this_->hash, &itm->item);
 462                 this_->first=itm->next;
 463                 if (this_->first)
 464                         this_->first->prev=NULL;
 465                 if (this_->cmd_first && this_->cmd_first->itm == itm->next) {
 466                         cmd=this_->cmd_first;
 467                         this_->cmd_first=cmd->next;
 468                         g_free(cmd);
 469                 }
 470                 map_convert_free(itm->name1);
 471                 map_convert_free(itm->name2);
 472                 navigation_itm_ways_clear(itm);
 473                 g_free(itm);
 474         }
 475         if (! this_->first)
 476                 this_->last=NULL;
 477         if (! this_->first && end)
 478                 dbg(0,"end wrong\n");
 479         dbg(2,"ret this_->first=%p this_->cmd_first=%p\n",this_->first, this_->cmd_first);
 480 }
 481
 482 static void
 483 navigation_itm_update(struct navigation_itm *itm, struct item *ritem)
 484 {
 485         struct attr length, time;
 486         if (! item_attr_get(ritem, attr_length, &length)) {
 487                 dbg(0,"no length\n");
 488                 return;
 489         }
 490         if (! item_attr_get(ritem, attr_time, &time)) {
 491                 dbg(0,"no time\n");
 492                 return;
 493         }
 494
 495         dbg(1,"length=%d time=%d\n", length.u.num, time.u.num);
 496         itm->length=length.u.num;
 497         itm->time=time.u.num;
 498 }
 499
 500 /**
 501  * @brief This check if an item is part of a roundabout
 502  *
 503  * @param itm The item to be checked
 504  * @return True if the item is part of a roundabout
 505  */
 506 static int
 507 check_roundabout(struct navigation_itm *itm, struct map *graph_map)
 508 {
 509         struct map_selection coord_sel;
 510         struct map_rect *g_rect; // Contains a map rectangle from the route graph's map
 511         struct item *i,*sitem;
 512         struct attr sitem_attr,flags_attr;
 513
 514         // These values cause the code in route.c to get us only the route graph point and connected segments
 515         coord_sel.next = NULL;
 516         coord_sel.u.c_rect.lu = itm->start;
 517         coord_sel.u.c_rect.rl = itm->start;
 518         // the selection's order is ignored
 519
 520         g_rect = map_rect_new(graph_map, &coord_sel);
 521
 522         i = map_rect_get_item(g_rect);
 523         if (!i || i->type != type_rg_point) { // probably offroad?
 524                 return 0;
 525         }
 526
 527         while (1) {
 528                 i = map_rect_get_item(g_rect);
 529
 530                 if (!i) {
 531                         break;
 532                 }
 533
 534                 if (i->type != type_rg_segment) {
 535                         continue;
 536                 }
 537
 538                 if (!item_attr_get(i,attr_street_item,&sitem_attr)) {
 539                         continue;
 540                 }
 541
 542                 sitem = sitem_attr.u.item;
 543                 if (item_is_equal(itm->item,*sitem)) {
 544                         if (item_attr_get(i,attr_flags,&flags_attr) && (flags_attr.u.num & AF_ROUNDABOUT)) {
 545                                 map_rect_destroy(g_rect);
 546                                 return 1;
 547                         }
 548                 }
 549         }
 550
 551         map_rect_destroy(g_rect);
 552         return 0;
 553 }
 554
 555 static struct navigation_itm *
 556 navigation_itm_new(struct navigation *this_, struct item *ritem)
 557 {
 558         struct navigation_itm *ret=g_new0(struct navigation_itm, 1);
 559         int i=0;
 560         struct item *sitem;
 561         struct map *graph_map = NULL;
 562         struct attr street_item,direction,route_attr;
 563         struct map_rect *mr;
 564         struct attr attr;
 565         struct coord c[5];
 566
 567         if (ritem) {
 568                 ret->told=0;
 569                 if (! item_attr_get(ritem, attr_street_item, &street_item)) {
 570                         dbg(0,"no street item\n");
 571                         return NULL;
 572                 }
 573                 if (item_attr_get(ritem, attr_direction, &direction))
 574                         ret->direction=direction.u.num;
 575                 else
 576                         ret->direction=0;
 577
 578                 sitem=street_item.u.item;
 579                 ret->item=*sitem;
 580                 item_hash_insert(this_->hash, sitem, ret);
 581                 mr=map_rect_new(sitem->map, NULL);
 582                 sitem=map_rect_get_item_byid(mr, sitem->id_hi, sitem->id_lo);
 583                 if (item_attr_get(sitem, attr_street_name, &attr))
 584                         ret->name1=map_convert_string(sitem->map,attr.u.str);
 585                 if (item_attr_get(sitem, attr_street_name_systematic, &attr))
 586                         ret->name2=map_convert_string(sitem->map,attr.u.str);
 587                 navigation_itm_update(ret, ritem);
 588
 589                 while (item_coord_get(ritem, &c[i], 1)) {
 590                         dbg(1, "coord %d 0x%x 0x%x\n", i, c[i].x ,c[i].y);
 591
 592                         if (i < 4)
 593                                 i++;
 594                         else {
 595                                 c[2]=c[3];
 596                                 c[3]=c[4];
 597                         }
 598                 }
 599                 dbg(1,"count=%d\n", i);
 600                 i--;
 601
 602                 ret->angle_start=road_angle(&c[0], &c[1], 0);
 603                 ret->angle_end=road_angle(&c[i-1], &c[i], 0);
 604
 605                 ret->start=c[0];
 606                 ret->end=c[i];
 607
 608                 item_attr_get(ritem, attr_route, &route_attr);
 609                 graph_map = route_get_graph_map(route_attr.u.route);
 610                 if (check_roundabout(ret, graph_map)) {
 611                         ret->flags |= AF_ROUNDABOUT;
 612                 }
 613
 614                 dbg(1,"i=%d start %d end %d '%s' '%s'\n", i, ret->angle_start, ret->angle_end, ret->name1, ret->name2);
 615                 map_rect_destroy(mr);
 616         } else {
 617                 if (this_->last)
 618                         ret->start=ret->end=this_->last->end;
 619         }
 620         if (! this_->first)
 621                 this_->first=ret;
 622         if (this_->last) {
 623                 this_->last->next=ret;
 624                 ret->prev=this_->last;
 625                 if (graph_map) {
 626                         navigation_itm_ways_update(ret,graph_map);
 627                 }
 628         }
 629         dbg(1,"ret=%p\n", ret);
 630         this_->last=ret;
 631         return ret;
 632 }
 633
 634 /**
 635  * @brief Counts how many times a driver could turn right/left
 636  *
 637  * This function counts how many times the driver theoretically could
 638  * turn right/left between two navigation items, not counting the final
 639  * turn itself.
 640  *
 641  * @param from The navigation item which should form the start
 642  * @param to The navigation item which should form the end
 643  * @param direction Set to < 0 to count turns to the left >= 0 for turns to the right
 644  * @return The number of possibilities to turn or -1 on error
 645  */
 646 static int
 647 count_possible_turns(struct navigation_itm *from, struct navigation_itm *to, int direction)
 648 {
 649         int count;
 650         struct navigation_itm *curr;
 651         struct navigation_way *w;
 652
 653         count = 0;
 654         curr = from->next;
 655         while (curr && (curr != to)) {
 656                 w = curr->ways;
 657
 658                 while (w) {
 659                         if (direction < 0) {
 660                                 if (angle_delta(curr->prev->angle_end, w->angle2) < 0) {
 661                                         count++;
 662                                         break;
 663                                 }
 664                         } else {
 665                                 if (angle_delta(curr->prev->angle_end, w->angle2) > 0) {
 666                                         count++;
 667                                         break;
 668                                 }
 669                         }
 670                         w = w->next;
 671                 }
 672                 curr = curr->next;
 673         }
 674
 675         if (!curr) { // from does not lead to to?
 676                 return -1;
 677         }
 678
 679         return count;
 680 }
 681
 682 /**
 683  * @brief Calculates distance and time to the destination
 684  *
 685  * This function calculates the distance and the time to the destination of a
 686  * navigation. If incr is set, this is only calculated for the first navigation
 687  * item, which is a lot faster than re-calculation the whole destination, but works
 688  * only if the rest of the navigation already has been calculated.
 689  *
 690  * @param this_ The navigation whose destination / time should be calculated
 691  * @param incr Set this to true to only calculate the first item. See description.
 692  */
 693 static void
 694 calculate_dest_distance(struct navigation *this_, int incr)
 695 {
 696         int len=0, time=0, count=0;
 697         struct navigation_itm *next,*itm=this_->last;
 698         dbg(1, "enter this_=%p, incr=%d\n", this_, incr);
 699         if (incr) {
 700                 if (itm)
 701                         dbg(2, "old values: (%p) time=%d lenght=%d\n", itm, itm->dest_length, itm->dest_time);
 702                 else
 703                         dbg(2, "old values: itm is null\n");
 704                 itm=this_->first;
 705                 next=itm->next;
 706                 dbg(2, "itm values: time=%d lenght=%d\n", itm->length, itm->time);
 707                 dbg(2, "next values: (%p) time=%d lenght=%d\n", next, next->dest_length, next->dest_time);
 708                 itm->dest_length=next->dest_length+itm->length;
 709                 itm->dest_count=next->dest_count+1;
 710                 itm->dest_time=next->dest_time+itm->time;
 711                 dbg(2, "new values: time=%d lenght=%d\n", itm->dest_length, itm->dest_time);
 712                 return;
 713         }
 714         while (itm) {
 715                 len+=itm->length;
 716                 time+=itm->time;
 717                 itm->dest_length=len;
 718                 itm->dest_time=time;
 719                 itm->dest_count=count++;
 720                 itm=itm->prev;
 721         }
 722         dbg(1,"len %d time %d\n", len, time);
 723 }
 724
 725 /**
 726  * @brief Checks if two navigation items are on the same street
 727  *
 728  * This function checks if two navigation items are on the same street. It returns
 729  * true if either their name or their "systematic name" (e.g. "A6" or "B256") are the
 730  * same.
 731  *
 732  * @param old The first item to be checked
 733  * @param new The second item to be checked
 734  * @return True if both old and new are on the same street
 735  */
 736 static int
 737 is_same_street2(char *old_name1, char *old_name2, char *new_name1, char *new_name2)
 738 {
 739         if (old_name1 && new_name1 && !strcmp(old_name1, new_name1)) {
 740                 dbg(1,"is_same_street: '%s' '%s' vs '%s' '%s' yes (1.)\n", old_name2, new_name2, old_name1, new_name1);
 741                 return 1;
 742         }
 743         if (old_name2 && new_name2 && !strcmp(old_name2, new_name2)) {
 744                 dbg(1,"is_same_street: '%s' '%s' vs '%s' '%s' yes (2.)\n", old_name2, new_name2, old_name1, new_name1);
 745                 return 1;
 746         }
 747         dbg(1,"is_same_street: '%s' '%s' vs '%s' '%s' no\n", old_name2, new_name2, old_name1, new_name1);
 748         return 0;
 749 }
 750
 751 #if 0
 752 /**
 753  * @brief Checks if two navigation items are on the same street
 754  *
 755  * This function checks if two navigation items are on the same street. It returns
 756  * true if the first part of their "systematic name" is equal. If the "systematic name" is
 757  * for example "A352/E3" (a german highway which at the same time is part of the international
 758  * E-road network), it would only search for "A352" in the second item's systematic name.
 759  *
 760  * @param old The first item to be checked
 761  * @param new The second item to be checked
 762  * @return True if the "systematic name" of both items matches. See description.
 763  */
 764 static int
 765 is_same_street_systematic(struct navigation_itm *old, struct navigation_itm *new)
 766 {
 767         int slashold,slashnew;
 768         if (!old->name2 || !new->name2)
 769                 return 1;
 770         slashold=strcspn(old->name2, "/");
 771         slashnew=strcspn(new->name2, "/");
 772         if (slashold != slashnew || strncmp(old->name2, new->name2, slashold))
 773                 return 0;
 774         return 1;
 775 }
 776
 777
 778 /**
 779  * @brief Check if there are multiple possibilities to drive from old
 780  *
 781  * This function checks, if there are multiple streets connected to the exit of "old".
 782  * Sometimes it happens that an item on a map is just segmented, without any other streets
 783  * being connected there, and it is not useful if navit creates a maneuver there.
 784  *
 785  * @param new The navigation item we're driving to
 786  * @return True if there are multiple streets
 787  */
 788 static int
 789 maneuver_multiple_streets(struct navigation_itm *new)
 790 {
 791         if (new->ways) {
 792                 return 1;
 793         } else {
 794                 return 0;
 795         }
 796 }
 797
 798
 799 /**
 800  * @brief Check if the new item is entered "straight"
 801  *
 802  * This function checks if the new item is entered "straight" from the old item, i.e. if there
 803  * is no other street one could take from the old item on with less steering.
 804  *
 805  * @param new The navigation item we're driving to
 806  * @param diff The absolute angle one needs to steer to drive to this item
 807  * @return True if the new item is entered "straight"
 808  */
 809 static int
 810 maneuver_straight(struct navigation_itm *new, int diff)
 811 {
 812         int curr_diff;
 813         struct navigation_way *w;
 814
 815         w = new->ways;
 816         dbg(1,"diff=%d\n", diff);
 817         while (w) {
 818                 curr_diff=abs(angle_delta(new->prev->angle_end, w->angle2));
 819                 dbg(1,"curr_diff=%d\n", curr_diff);
 820                 if (curr_diff < diff) {
 821                         return 0;
 822                 }
 823                 w = w->next;
 824         }
 825         return 1;
 826 }
 827 #endif
 828
 829 static int maneuver_category(enum item_type type)
 830 {
 831         switch (type) {
 832         case type_street_0:
 833                 return 1;
 834         case type_street_1_city:
 835                 return 2;
 836         case type_street_2_city:
 837                 return 3;
 838         case type_street_3_city:
 839                 return 4;
 840         case type_street_4_city:
 841                 return 5;
 842         case type_highway_city:
 843                 return 7;
 844         case type_street_1_land:
 845                 return 2;
 846         case type_street_2_land:
 847                 return 3;
 848         case type_street_3_land:
 849                 return 4;
 850         case type_street_4_land:
 851                 return 5;
 852         case type_street_n_lanes:
 853                 return 6;
 854         case type_highway_land:
 855                 return 7;
 856         case type_ramp:
 857                 return 0;
 858         case type_roundabout:
 859                 return 0;
 860         case type_ferry:
 861                 return 0;
 862         default:
 863                 return 0;
 864         }
 865
 866
 867 }
 868
 869 static int
 870 is_way_allowed(struct navigation_way *way)
 871 {
 872         if (way->dir > 0) {
 873                 if (way->flags & AF_ONEWAYREV)
 874                         return 0;
 875         } else {
 876                 if (way->flags & AF_ONEWAY)
 877                         return 0;
 878         }
 879         return 1;
 880 }
 881
 882 /**
 883  * @brief Checks if navit has to create a maneuver to drive from old to new
 884  *
 885  * This function checks if it has to create a "maneuver" - i.e. guide the user - to drive
 886  * from "old" to "new".
 887  *
 888  * @param old The old navigation item, where we're coming from
 889  * @param new The new navigation item, where we're going to
 890  * @param delta The angle the user has to steer to navigate from old to new
 891  * @param reason A text string explaining how the return value resulted
 892  * @return True if navit should guide the user, false otherwise
 893  */
 894 static int
 895 maneuver_required2(struct navigation_itm *old, struct navigation_itm *new, int *delta, char **reason)
 896 {
 897         int ret=0,d,dw,dlim;
 898         char *r=NULL;
 899         struct navigation_way *w;
 900         int cat,ncat,wcat,maxcat,left=-180,right=180,is_unambigous=0,is_same_street;
 901
 902         dbg(1,"enter %p %p %p\n",old, new, delta);
 903         d=angle_delta(old->angle_end, new->angle_start);
 904         if (!new->ways) {
 905                 /* No announcement necessary */
 906                 r="no: Only one possibility";
 907         } else if (!new->ways->next && new->ways->item.type == type_ramp) {
 908                 /* If the other way is only a ramp and it is one-way in the wrong direction, no announcement necessary */
 909                 /* TODO: check for one way in wrong direction */
 910                 r="no: Only ramp";
 911         }
 912         if (! r) {
 913                 if ((old->flags & AF_ROUNDABOUT) && ! (new->flags & AF_ROUNDABOUT)) {
 914                         r="yes: leaving roundabout";
 915                         ret=1;
 916                 } else  if (!(old->flags & AF_ROUNDABOUT) && (new->flags & AF_ROUNDABOUT))
 917                         r="no: entering roundabout";
 918                 else if ((old->flags & AF_ROUNDABOUT) && (new->flags & AF_ROUNDABOUT))
 919                         r="no: staying in roundabout";
 920         }
 921         if (!r && abs(d) > 75) {
 922                 /* always make an announcement if you have to make a sharp turn */
 923                 r="yes: delta over 75";
 924                 ret=1;
 925         }
 926         cat=maneuver_category(old->item.type);
 927         ncat=maneuver_category(new->item.type);
 928         if (!r) {
 929                 /* Check whether the street keeps its name */
 930                 is_same_street=is_same_street2(old->name1, old->name2, new->name1, new->name2);
 931                 w = new->ways;
 932                 maxcat=-1;
 933                 while (w) {
 934                         dw=angle_delta(old->angle_end, w->angle2);
 935                         if (dw < 0) {
 936                                 if (dw > left)
 937                                         left=dw;
 938                         } else {
 939                                 if (dw < right)
 940                                         right=dw;
 941                         }
 942                         wcat=maneuver_category(w->item.type);
 943                         /* If any other street has the same name but isn't a highway (a highway might split up temporarily), then
 944                            we can't use the same name criterium  */
 945                         if (is_same_street && is_same_street2(old->name1, old->name2, w->name1, w->name2) && (cat != 7 || wcat != 7) && is_way_allowed(w))
 946                                 is_same_street=0;
 947                         /* Mark if the street has a higher or the same category */
 948                         if (wcat > maxcat)
 949                                 maxcat=wcat;
 950                         w = w->next;
 951                 }
 952                 /* get the delta limit for checking for other streets. It is lower if the street has no other
 953                    streets of the same or higher category */
 954                 if (ncat < cat)
 955                         dlim=80;
 956                 else
 957                         dlim=120;
 958                 /* if the street is really straight, the others might be closer to straight */
 959                 if (abs(d) < 20)
 960                         dlim/=2;
 961                 if ((maxcat == ncat && maxcat == cat) || (ncat == 0 && cat == 0))
 962                         dlim=abs(d)*620/256;
 963                 else if (maxcat < ncat && maxcat < cat)
 964                         dlim=abs(d)*128/256;
 965                 if (left < -dlim && right > dlim)
 966                         is_unambigous=1;
 967                 if (!is_same_street && is_unambigous < 1) {
 968                         ret=1;
 969                         r="yes: not same street or ambigous";
 970                 } else
 971                         r="no: same street and unambigous";
 972 #ifdef DEBUG
 973                 r=g_strdup_printf("yes: d %d left %d right %d dlim=%d cat old:%d new:%d max:%d unambigous=%d same_street=%d", d, left, right, dlim, cat, ncat, maxcat, is_unambigous, is_same_street);
 974 #endif
 975         }
 976         *delta=d;
 977         if (reason)
 978                 *reason=r;
 979         return ret;
 980
 981
 982 #if 0
 983         if (new->item.type == old->item.type || (new->item.type != type_ramp && old->item.type != type_ramp)) {
 984                 if (is_same_street2(old, new)) {
 985                         if (! entering_straight(new, abs(*delta))) {
 986                                 dbg(1, "maneuver_required: Not driving straight: yes\n");
 987                                 if (reason)
 988                                         *reason="yes: Not driving straight";
 989                                 return 1;
 990                         }
 991
 992                         if (check_multiple_streets(new)) {
 993                                 if (entering_straight(new,abs(*delta)*2)) {
 994                                         if (reason)
 995                                                 *reason="no: delta < ext_limit for same name";
 996                                         return 0;
 997                                 }
 998                                 if (reason)
 999                                         *reason="yes: delta > ext_limit for same name";
1000                                 return 1;
1001                         } else {
1002                                 dbg(1, "maneuver_required: Staying on the same street: no\n");
1003                                 if (reason)
1004                                         *reason="no: Staying on same street";
1005                                 return 0;
1006                         }
1007                 }
1008         } else
1009                 dbg(1, "maneuver_required: old or new is ramp\n");
1010 #if 0
1011         if (old->item.type == type_ramp && (new->item.type == type_highway_city || new->item.type == type_highway_land)) {
1012                 dbg(1, "no_maneuver_required: old is ramp new is highway\n");
1013                 if (reason)
1014                         *reason="no: old is ramp new is highway";
1015                 return 0;
1016         }
1017 #endif
1018 #if 0
1019         if (old->crossings_end == 2) {
1020                 dbg(1, "maneuver_required: only 2 connections: no\n");
1021                 return 0;
1022         }
1023 #endif
1024         dbg(1,"delta=%d-%d=%d\n", new->angle_start, old->angle_end, *delta);
1025         if ((new->item.type == type_highway_land || new->item.type == type_highway_city || old->item.type == type_highway_land || old->item.type == type_highway_city) && (!is_same_street_systematic(old, new) || (old->name2 != NULL && new->name2 == NULL))) {
1026                 dbg(1, "maneuver_required: highway changed name\n");
1027                 if (reason)
1028                         *reason="yes: highway changed name";
1029                 return 1;
1030         }
1031         if (abs(*delta) < straight_limit) {
1032                 if (! entering_straight(new,abs(*delta))) {
1033                         if (reason)
1034                                 *reason="yes: not straight";
1035                         dbg(1, "maneuver_required: not driving straight: yes\n");
1036                         return 1;
1037                 }
1038
1039                 dbg(1, "maneuver_required: delta(%d) < %d: no\n", *delta, straight_limit);
1040                 if (reason)
1041                         *reason="no: delta < limit";
1042                 return 0;
1043         }
1044         if (abs(*delta) < ext_straight_limit) {
1045                 if (entering_straight(new,abs(*delta)*2)) {
1046                         if (reason)
1047                                 *reason="no: delta < ext_limit";
1048                         return 0;
1049                 }
1050         }
1051
1052         if (! check_multiple_streets(new)) {
1053                 dbg(1, "maneuver_required: only one possibility: no\n");
1054                 if (reason)
1055                         *reason="no: only one possibility";
1056                 return 0;
1057         }
1058
1059         dbg(1, "maneuver_required: delta=%d: yes\n", *delta);
1060         if (reason)
1061                 *reason="yes: delta >= limit";
1062         return 1;
1063 #endif
1064 }
1065
1066 static struct navigation_command *
1067 command_new(struct navigation *this_, struct navigation_itm *itm, int delta)
1068 {
1069         struct navigation_command *ret=g_new0(struct navigation_command, 1);
1070         dbg(1,"enter this_=%p itm=%p delta=%d\n", this_, itm, delta);
1071         ret->delta=delta;
1072         ret->itm=itm;
1073         if (itm && itm->prev && !(itm->flags & AF_ROUNDABOUT) && (itm->prev->flags & AF_ROUNDABOUT)) {
1074                 int len=0;
1075                 int angle;
1076                 struct navigation_itm *itm2=itm->prev;
1077                 while (itm2 && (itm2->flags & AF_ROUNDABOUT)) {
1078                         len+=itm2->length;
1079                         angle=itm2->angle_end;
1080                         itm2=itm2->prev;
1081                 }
1082                 if (itm2)
1083                         ret->roundabout_delta=angle_delta(itm2->angle_end, itm->angle_start);
1084                 else {
1085                         if (delta > 0)
1086                                 angle-=90;
1087                         else
1088                                 angle+=90;
1089                         ret->roundabout_delta=angle_delta(angle % 360, itm->angle_start);
1090                 }
1091                 ret->length=len;
1092
1093         }
1094         if (this_->cmd_last)
1095                 this_->cmd_last->next=ret;
1096         this_->cmd_last=ret;
1097
1098         if (!this_->cmd_first)
1099                 this_->cmd_first=ret;
1100         return ret;
1101 }
1102
1103 static void
1104 make_maneuvers(struct navigation *this_, struct route *route)
1105 {
1106         struct navigation_itm *itm, *last=NULL, *last_itm=NULL;
1107         int delta;
1108         itm=this_->first;
1109         this_->cmd_last=NULL;
1110         this_->cmd_first=NULL;
1111         while (itm) {
1112                 if (last) {
1113                         if (maneuver_required2(last_itm, itm,&delta,NULL)) {
1114                                 command_new(this_, itm, delta);
1115                         }
1116                 } else
1117                         last=itm;
1118                 last_itm=itm;
1119                 itm=itm->next;
1120         }
1121         command_new(this_, last_itm, 0);
1122 }
1123
1124 static int
1125 contains_suffix(char *name, char *suffix)
1126 {
1127         if (!suffix)
1128                 return 0;
1129         if (strlen(name) < strlen(suffix))
1130                 return 0;
1131         return !strcasecmp(name+strlen(name)-strlen(suffix), suffix);
1132 }
1133
1134 static char *
1135 replace_suffix(char *name, char *search, char *replace)
1136 {
1137         int len=strlen(name)-strlen(search);
1138         char *ret=g_malloc(len+strlen(replace)+1);
1139         strncpy(ret, name, len);
1140         strcpy(ret+len, replace);
1141
1142         return ret;
1143 }
1144
1145 static char *
1146 navigation_item_destination(struct navigation_itm *itm, struct navigation_itm *next, char *prefix)
1147 {
1148         char *ret=NULL,*name1,*sep,*name2;
1149         int i,sex;
1150         if (! prefix)
1151                 prefix="";
1152         if(!itm->name1 && !itm->name2 && itm->item.type == type_ramp) {
1153                 dbg(1,">> Next is ramp %lx current is %lx \n", itm->item.type, next->item.type);
1154
1155                 if(next->item.type == type_ramp)
1156                         return NULL;
1157                 if(itm->item.type == type_highway_city || itm->item.type == type_highway_land )
1158                         return g_strdup_printf("%s%s",prefix,_("exit"));        /* %FIXME Can this even be reached? */
1159                 else
1160                         return g_strdup_printf("%s%s",prefix,_("into the ramp"));
1161
1162         }
1163         if (!itm->name1 && !itm->name2)
1164                 return NULL;
1165         if (itm->name1) {
1166                 sex=-1;
1167                 name1=NULL;
1168                 for (i = 0 ; i < sizeof(suffixes)/sizeof(suffixes[0]) ; i++) {
1169                         if (contains_suffix(itm->name1,suffixes[i].fullname)) {
1170                                 sex=suffixes[i].sex;
1171                                 name1=g_strdup(itm->name1);
1172                                 break;
1173                         }
1174                         if (contains_suffix(itm->name1,suffixes[i].abbrev)) {
1175                                 sex=suffixes[i].sex;
1176                                 name1=replace_suffix(itm->name1, suffixes[i].abbrev, suffixes[i].fullname);
1177                                 break;
1178                         }
1179                 }
1180                 if (itm->name2) {
1181                         name2=itm->name2;
1182                         sep=" ";
1183                 } else {
1184                         name2="";
1185                         sep="";
1186                 }
1187                 switch (sex) {
1188                 case -1:
1189                         /* TRANSLATORS: Arguments: 1: Prefix (Space if required) 2: Street Name 3: Separator (Space if required), 4: Systematic Street Name */
1190                         ret=g_strdup_printf(_("%sinto the street %s%s%s"),prefix,itm->name1, sep, name2);
1191                         break;
1192                 case 1:
1193                         /* TRANSLATORS: Arguments: 1: Prefix (Space if required) 2: Street Name 3: Separator (Space if required), 4: Systematic Street Name. Male form. The stuff after | doesn't have to be included */
1194                         ret=g_strdup_printf(_("%sinto the %s%s%s|male form"),prefix,name1, sep, name2);
1195                         break;
1196                 case 2:
1197                         /* TRANSLATORS: Arguments: 1: Prefix (Space if required) 2: Street Name 3: Separator (Space if required), 4: Systematic Street Name. Female form. The stuff after | doesn't have to be included */
1198                         ret=g_strdup_printf(_("%sinto the %s%s%s|female form"),prefix,name1, sep, name2);
1199                         break;
1200                 case 3:
1201                         /* TRANSLATORS: Arguments: 1: Prefix (Space if required) 2: Street Name 3: Separator (Space if required), 4: Systematic Street Name. Neutral form. The stuff after | doesn't have to be included */
1202                         ret=g_strdup_printf(_("%sinto the %s%s%s|neutral form"),prefix,name1, sep, name2);
1203                         break;
1204                 }
1205                 g_free(name1);
1206
1207         } else
1208                 /* TRANSLATORS: gives the name of the next road to turn into (into the E17) */
1209                 ret=g_strdup_printf(_("%sinto the %s"),prefix,itm->name2);
1210         name1=ret;
1211         while (*name1) {
1212                 switch (*name1) {
1213                 case '|':
1214                         *name1='\0';
1215                         break;
1216                 case '/':
1217                         *name1++=' ';
1218                         break;
1219                 default:
1220                         name1++;
1221                 }
1222         }
1223         return ret;
1224 }
1225
1226 static char *
1227 show_maneuver(struct navigation *nav, struct navigation_itm *itm, struct navigation_command *cmd, enum attr_type type)
1228 {
1229         /* TRANSLATORS: right, as in 'Turn right' */
1230         char *dir=_("right"),*strength="";
1231         int distance=itm->dest_length-cmd->itm->dest_length;
1232         char *d,*ret;
1233         int delta=cmd->delta;
1234         int level;
1235         int strength_needed;
1236         int skip_roads;
1237         int count_roundabout;
1238         struct navigation_itm *cur;
1239         struct navigation_way *w;
1240
1241         w = itm->next->ways;
1242         strength_needed = 0;
1243         if ((itm->next->angle_start - itm->angle_end) < 0) {
1244                 while (w) {
1245                         if (w->angle2-itm->next->angle_start < 0) {
1246                                 strength_needed = 1;
1247                                 break;
1248                         }
1249                         w = w->next;
1250                 }
1251         } else {
1252                 while (w) {
1253                         if (w->angle2-itm->next->angle_start > 0) {
1254                                 strength_needed = 1;
1255                                 break;
1256                         }
1257                         w = w->next;
1258                 }
1259         }
1260
1261         level=1;
1262         if (delta < 0) {
1263                 /* TRANSLATORS: left, as in 'Turn left' */
1264                 dir=_("left");
1265                 delta=-delta;
1266         }
1267
1268         if (strength_needed) {
1269                 if (delta < 45) {
1270                         /* TRANSLATORS: Don't forget the ending space */
1271                         strength=_("easily ");
1272                 } else if (delta < 105) {
1273                         strength="";
1274                 } else if (delta < 165) {
1275                         /* TRANSLATORS: Don't forget the ending space */
1276                         strength=_("strongly ");
1277                 } else {
1278                         dbg(1,"delta=%d\n", delta);
1279                         /* TRANSLATORS: Don't forget the ending space */
1280                         strength=_("unknown ");
1281                 }
1282         }
1283         if (type != attr_navigation_long_exact)
1284                 distance=round_distance(distance);
1285         if (type == attr_navigation_speech) {
1286                 if (nav->turn_around && nav->turn_around == nav->turn_around_limit)
1287                         return g_strdup(_("When possible, please turn around"));
1288                 level=navigation_get_announce_level(nav, itm->item.type, distance-cmd->length);
1289                 dbg(1,"distance=%d level=%d type=0x%x\n", distance, level, itm->item.type);
1290         }
1291
1292         if (cmd->itm->prev->flags & AF_ROUNDABOUT) {
1293                 switch (level) {
1294                 case 2:
1295                         return g_strdup(_("Enter the roundabout soon"));
1296                 case 1:
1297                         d = get_distance(distance, type, 1);
1298                         ret = g_strdup_printf(_("In %s, enter the roundabout"), d);
1299                         g_free(d);
1300                         return ret;
1301                 case 0:
1302                         cur = cmd->itm->prev;
1303                         count_roundabout = 0;
1304                         while (cur && (cur->flags & AF_ROUNDABOUT)) {
1305                                 if (cur->next->ways && is_way_allowed(cur->next->ways)) { // If the next segment has no exit or the exit isn't allowed, don't count it
1306                                         count_roundabout++;
1307                                 }
1308                                 cur = cur->prev;
1309                         }
1310                         ret = g_strdup_printf(_("Leave the roundabout at the %s exit"), get_count_str(count_roundabout));
1311                         return ret;
1312                 }
1313         }
1314
1315         switch(level) {
1316         case 3:
1317                 d=get_distance(distance, type, 1);
1318                 ret=g_strdup_printf(_("Follow the road for the next %s"), d);
1319                 g_free(d);
1320                 return ret;
1321         case 2:
1322                 d=g_strdup(_("soon"));
1323                 break;
1324         case 1:
1325                 d=get_distance(distance, type, 0);
1326                 break;
1327         case 0:
1328                 skip_roads = count_possible_turns(nav->first,cmd->itm,cmd->delta);
1329                 if (skip_roads > 0) {
1330                         if (get_count_str(skip_roads+1)) {
1331                                 /* TRANSLATORS: First argument is the how manieth street to take, second the direction */
1332                                 ret = g_strdup_printf(_("Take the %1$s road to the %2$s"), get_count_str(skip_roads+1), dir);
1333                                 return ret;
1334                         } else {
1335                                 d = g_strdup_printf(_("after %i roads"), skip_roads);
1336                         }
1337                 } else {
1338                         d=g_strdup(_("now"));
1339                 }
1340                 break;
1341         default:
1342                 d=g_strdup(_("error"));
1343         }
1344         if (cmd->itm->next) {
1345                 int tellstreetname = 0;
1346                 char *destination = NULL;
1347
1348                 if(type == attr_navigation_speech) { // In voice mode
1349                         // In Voice Mode only tell the street name in level 1 or in level 0 if level 1
1350                         // was skipped
1351
1352                         if (level == 1) { // we are close to the intersection
1353                                 cmd->itm->told = 1; // remeber to be checked when we turn
1354                                 tellstreetname = 1; // Ok so we tell the name of the street
1355                         }
1356
1357                         if (level == 0) {
1358                                 if(cmd->itm->told == 0) // we are right at the intersection
1359                                         tellstreetname = 1;
1360                                 else
1361                                         cmd->itm->told = 0;  // reset just in case we come to the same street again
1362                         }
1363
1364                 }
1365                 else
1366                      tellstreetname = 1;
1367
1368                 if(tellstreetname)
1369                         destination=navigation_item_destination(cmd->itm, itm, " ");
1370                 /* TRANSLATORS: The first argument is strength, the second direction, the third distance and the fourth destination Example: 'Turn 'slightly' 'left' in '100 m' 'onto baker street' */
1371                 ret=g_strdup_printf(_("Turn %1$s%2$s %3$s%4$s"), strength, dir, d, destination ? destination:"");
1372                 g_free(destination);
1373         } else
1374                 ret=g_strdup_printf(_("You have reached your destination %s"), d);
1375         g_free(d);
1376         return ret;
1377 }
1378
1379 static void
1380 navigation_call_callbacks(struct navigation *this_, int force_speech)
1381 {
1382         int distance, level = 0, level2;
1383         void *p=this_;
1384         if (!this_->cmd_first)
1385                 return;
1386         callback_list_call(this_->callback, 1, &p);
1387         dbg(1,"force_speech=%d turn_around=%d turn_around_limit=%d\n", force_speech, this_->turn_around, this_->turn_around_limit);
1388         distance=round_distance(this_->first->dest_length-this_->cmd_first->itm->dest_length);
1389         if (this_->turn_around_limit && this_->turn_around == this_->turn_around_limit) {
1390                 dbg(1,"distance=%d distance_turn=%d\n", distance, this_->distance_turn);
1391                 while (distance > this_->distance_turn) {
1392                         this_->level_last=4;
1393                         level=4;
1394                         force_speech=1;
1395                         if (this_->distance_turn >= 500)
1396                                 this_->distance_turn*=2;
1397                         else
1398                                 this_->distance_turn=500;
1399                 }
1400         } else if (!this_->turn_around_limit || this_->turn_around == -this_->turn_around_limit+1) {
1401                 this_->distance_turn=50;
1402                 distance-=this_->cmd_first->length;
1403                 level=navigation_get_announce_level(this_, this_->first->item.type, distance);
1404                 if (this_->cmd_first->itm->prev) {
1405                         level2=navigation_get_announce_level(this_, this_->cmd_first->itm->prev->item.type, distance);
1406                         if (level2 > level)
1407                                 level=level2;
1408                 }
1409                 if (level < this_->level_last) {
1410                         dbg(1,"level %d < %d\n", level, this_->level_last);
1411                         this_->level_last=level;
1412                         force_speech=1;
1413                 }
1414                 if (!item_is_equal(this_->cmd_first->itm->item, this_->item_last)) {
1415                         dbg(1,"item different\n");
1416                         this_->item_last=this_->cmd_first->itm->item;
1417                         force_speech=1;
1418                 }
1419         }
1420         if (force_speech) {
1421                 this_->level_last=level;
1422                 dbg(1,"distance=%d level=%d type=0x%x\n", distance, level, this_->first->item.type);
1423                 callback_list_call(this_->callback_speech, 1, &p);
1424         }
1425 }
1426
1427 void
1428 navigation_update(struct navigation *this_, struct route *route)
1429 {
1430         struct map *map;
1431         struct map_rect *mr;
1432         struct item *ritem;                     /* Holds an item from the route map */
1433         struct item *sitem;                     /* Holds the corresponding item from the actual map */
1434         struct attr street_item,street_direction;
1435         struct navigation_itm *itm;
1436         int incr=0,first=1;
1437
1438         if (! route)
1439                 return;
1440         map=route_get_map(route);
1441         if (! map)
1442                 return;
1443         mr=map_rect_new(map, NULL);
1444         if (! mr)
1445                 return;
1446         dbg(1,"enter\n");
1447         while ((ritem=map_rect_get_item(mr))) {
1448                 if (first && item_attr_get(ritem, attr_street_item, &street_item)) {
1449                         first=0;
1450                         if (!item_attr_get(ritem, attr_direction, &street_direction))
1451                                 street_direction.u.num=0;
1452                         sitem=street_item.u.item;
1453                         dbg(1,"sitem=%p\n", sitem);
1454                         itm=item_hash_lookup(this_->hash, sitem);
1455                         dbg(2,"itm for item with id (0x%x,0x%x) is %p\n", sitem->id_hi, sitem->id_lo, itm);
1456                         if (itm && itm->direction != street_direction.u.num) {
1457                                 dbg(2,"wrong direction\n");
1458                                 itm=NULL;
1459                         }
1460                         navigation_destroy_itms_cmds(this_, itm);
1461                         if (itm) {
1462                                 navigation_itm_update(itm, ritem);
1463                                 break;
1464                         }
1465                         dbg(1,"not on track\n");
1466                 }
1467                 navigation_itm_new(this_, ritem);
1468         }
1469         if (first)
1470                 navigation_destroy_itms_cmds(this_, NULL);
1471         else {
1472                 if (! ritem) {
1473                         navigation_itm_new(this_, NULL);
1474                         make_maneuvers(this_,route);
1475                 }
1476                 calculate_dest_distance(this_, incr);
1477                 dbg(2,"destination distance old=%d new=%d\n", this_->distance_last, this_->first->dest_length);
1478                 if (this_->first->dest_length > this_->distance_last && this_->distance_last >= 0)
1479                         this_->turn_around++;
1480                 else
1481                         this_->turn_around--;
1482                 if (this_->turn_around > this_->turn_around_limit)
1483                         this_->turn_around=this_->turn_around_limit;
1484                 else if (this_->turn_around < -this_->turn_around_limit+1)
1485                         this_->turn_around=-this_->turn_around_limit+1;
1486                 dbg(2,"turn_around=%d\n", this_->turn_around);
1487                 this_->distance_last=this_->first->dest_length;
1488                 profile(0,"end");
1489                 navigation_call_callbacks(this_, FALSE);
1490         }
1491         map_rect_destroy(mr);
1492 }
1493
1494 void
1495 navigation_flush(struct navigation *this_)
1496 {
1497         navigation_destroy_itms_cmds(this_, NULL);
1498 }
1499
1500
1501 void
1502 navigation_destroy(struct navigation *this_)
1503 {
1504         navigation_flush(this_);
1505         item_hash_destroy(this_->hash);
1506         callback_list_destroy(this_->callback);
1507         callback_list_destroy(this_->callback_speech);
1508         g_free(this_);
1509 }
1510
1511 int
1512 navigation_register_callback(struct navigation *this_, enum attr_type type, struct callback *cb)
1513 {
1514         if (type == attr_navigation_speech)
1515                 callback_list_add(this_->callback_speech, cb);
1516         else
1517                 callback_list_add(this_->callback, cb);
1518         return 1;
1519 }
1520
1521 void
1522 navigation_unregister_callback(struct navigation *this_, enum attr_type type, struct callback *cb)
1523 {
1524         if (type == attr_navigation_speech)
1525                 callback_list_remove_destroy(this_->callback_speech, cb);
1526         else
1527                 callback_list_remove_destroy(this_->callback, cb);
1528 }
1529
1530 struct map *
1531 navigation_get_map(struct navigation *this_)
1532 {
1533         if (! this_->map)
1534                 this_->map=map_new(NULL, (struct attr*[]){
1535                         &(struct attr){attr_type,{"navigation"}},
1536                         &(struct attr){attr_navigation,.u.navigation=this_},
1537                         &(struct attr){attr_data,{""}},
1538                         &(struct attr){attr_description,{"Navigation"}},
1539                         NULL});
1540         return this_->map;
1541 }
1542
1543 struct map_priv {
1544         struct navigation *navigation;
1545 };
1546
1547 struct map_rect_priv {
1548         struct navigation *nav;
1549         struct navigation_command *cmd;
1550         struct navigation_command *cmd_next;
1551         struct navigation_itm *itm;
1552         struct navigation_itm *itm_next;
1553         struct navigation_itm *cmd_itm;
1554         struct navigation_itm *cmd_itm_next;
1555         struct item item;
1556         enum attr_type attr_next;
1557         int ccount;
1558         int debug_idx;
1559         struct navigation_way *ways;
1560         int show_all;
1561         char *str;
1562 };
1563
1564 static int
1565 navigation_map_item_coord_get(void *priv_data, struct coord *c, int count)
1566 {
1567         struct map_rect_priv *this=priv_data;
1568         if (this->ccount || ! count)
1569                 return 0;
1570         *c=this->itm->start;
1571         this->ccount=1;
1572         return 1;
1573 }
1574
1575 static int
1576 navigation_map_item_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1577 {
1578         struct map_rect_priv *this_=priv_data;
1579         attr->type=attr_type;
1580         struct navigation_command *cmd=this_->cmd;
1581         struct navigation_itm *itm=this_->itm;
1582         struct navigation_itm *prev=itm->prev;
1583
1584         if (this_->str) {
1585                 g_free(this_->str);
1586                 this_->str=NULL;
1587         }
1588
1589         if (cmd) {
1590                 if (cmd->itm != itm)
1591                         cmd=NULL;
1592         }
1593         switch(attr_type) {
1594         case attr_navigation_short:
1595                 this_->attr_next=attr_navigation_long;
1596                 if (cmd) {
1597                         this_->str=attr->u.str=show_maneuver(this_->nav, this_->cmd_itm, cmd, attr_type);
1598                         return 1;
1599                 }
1600                 return 0;
1601         case attr_navigation_long:
1602                 this_->attr_next=attr_navigation_long_exact;
1603                 if (cmd) {
1604                         this_->str=attr->u.str=show_maneuver(this_->nav, this_->cmd_itm, cmd, attr_type);
1605                         return 1;
1606                 }
1607                 return 0;
1608         case attr_navigation_long_exact:
1609                 this_->attr_next=attr_navigation_speech;
1610                 if (cmd) {
1611                         this_->str=attr->u.str=show_maneuver(this_->nav, this_->cmd_itm, cmd, attr_type);
1612                         return 1;
1613                 }
1614                 return 0;
1615         case attr_navigation_speech:
1616                 this_->attr_next=attr_length;
1617                 if (cmd) {
1618                         this_->str=attr->u.str=show_maneuver(this_->nav, this_->cmd_itm, this_->cmd, attr_type);
1619                         return 1;
1620                 }
1621                 return 0;
1622         case attr_length:
1623                 this_->attr_next=attr_time;
1624                 if (cmd) {
1625                         attr->u.num=this_->cmd_itm->dest_length-cmd->itm->dest_length;
1626                         return 1;
1627                 }
1628                 return 0;
1629         case attr_time:
1630                 this_->attr_next=attr_destination_length;
1631                 if (cmd) {
1632                         attr->u.num=this_->cmd_itm->dest_time-cmd->itm->dest_time;
1633                         return 1;
1634                 }
1635                 return 0;
1636         case attr_destination_length:
1637                 attr->u.num=itm->dest_length;
1638                 this_->attr_next=attr_destination_time;
1639                 return 1;
1640         case attr_destination_time:
1641                 attr->u.num=itm->dest_time;
1642                 this_->attr_next=attr_street_name;
1643                 return 1;
1644         case attr_street_name:
1645                 attr->u.str=itm->name1;
1646                 this_->attr_next=attr_street_name_systematic;
1647                 if (attr->u.str)
1648                         return 1;
1649                 return 0;
1650         case attr_street_name_systematic:
1651                 attr->u.str=itm->name2;
1652                 this_->attr_next=attr_debug;
1653                 if (attr->u.str)
1654                         return 1;
1655                 return 0;
1656         case attr_debug:
1657                 switch(this_->debug_idx) {
1658                 case 0:
1659                         this_->debug_idx++;
1660                         this_->str=attr->u.str=g_strdup_printf("angle:%d (- %d)", itm->angle_start, itm->angle_end);
1661                         return 1;
1662                 case 1:
1663                         this_->debug_idx++;
1664                         this_->str=attr->u.str=g_strdup_printf("item type:%s", item_to_name(itm->item.type));
1665                         return 1;
1666                 case 2:
1667                         this_->debug_idx++;
1668                         if (cmd) {
1669                                 this_->str=attr->u.str=g_strdup_printf("delta:%d", cmd->delta);
1670                                 return 1;
1671                         }
1672                 case 3:
1673                         this_->debug_idx++;
1674                         if (prev) {
1675                                 this_->str=attr->u.str=g_strdup_printf("prev street_name:%s", prev->name1);
1676                                 return 1;
1677                         }
1678                 case 4:
1679                         this_->debug_idx++;
1680                         if (prev) {
1681                                 this_->str=attr->u.str=g_strdup_printf("prev street_name_systematic:%s", prev->name2);
1682                                 return 1;
1683                         }
1684                 case 5:
1685                         this_->debug_idx++;
1686                         if (prev) {
1687                                 this_->str=attr->u.str=g_strdup_printf("prev angle:(%d -) %d", prev->angle_start, prev->angle_end);
1688                                 return 1;
1689                         }
1690                 case 6:
1691                         this_->debug_idx++;
1692                         this_->ways=itm->ways;
1693                         if (prev) {
1694                                 this_->str=attr->u.str=g_strdup_printf("prev item type:%s", item_to_name(prev->item.type));
1695                                 return 1;
1696                         }
1697                 case 7:
1698                         if (this_->ways && prev) {
1699                                 this_->str=attr->u.str=g_strdup_printf("other item angle:%d delta:%d flags:%d dir:%d type:%s id:(0x%x,0x%x)", this_->ways->angle2, angle_delta(prev->angle_end, this_->ways->angle2), this_->ways->flags, this_->ways->dir, item_to_name(this_->ways->item.type), this_->ways->item.id_hi, this_->ways->item.id_lo);
1700                                 this_->ways=this_->ways->next;
1701                                 return 1;
1702                         }
1703                         this_->debug_idx++;
1704                 case 8:
1705                         this_->debug_idx++;
1706                         if (prev) {
1707                                 int delta=0;
1708                                 char *reason=NULL;
1709                                 maneuver_required2(prev, itm, &delta, &reason);
1710                                 this_->str=attr->u.str=g_strdup_printf("reason:%s",reason);
1711                                 return 1;
1712                         }
1713
1714                 default:
1715                         this_->attr_next=attr_none;
1716                         return 0;
1717                 }
1718         case attr_any:
1719                 while (this_->attr_next != attr_none) {
1720                         if (navigation_map_item_attr_get(priv_data, this_->attr_next, attr))
1721                                 return 1;
1722                 }
1723                 return 0;
1724         default:
1725                 attr->type=attr_none;
1726                 return 0;
1727         }
1728 }
1729
1730 static struct item_methods navigation_map_item_methods = {
1731         NULL,
1732         navigation_map_item_coord_get,
1733         NULL,
1734         navigation_map_item_attr_get,
1735 };
1736
1737
1738 static void
1739 navigation_map_destroy(struct map_priv *priv)
1740 {
1741         g_free(priv);
1742 }
1743
1744 static void
1745 navigation_map_rect_init(struct map_rect_priv *priv)
1746 {
1747         priv->cmd_next=priv->nav->cmd_first;
1748         priv->cmd_itm_next=priv->itm_next=priv->nav->first;
1749 }
1750
1751 static struct map_rect_priv *
1752 navigation_map_rect_new(struct map_priv *priv, struct map_selection *sel)
1753 {
1754         struct navigation *nav=priv->navigation;
1755         struct map_rect_priv *ret=g_new0(struct map_rect_priv, 1);
1756         ret->nav=nav;
1757         navigation_map_rect_init(ret);
1758         ret->item.meth=&navigation_map_item_methods;
1759         ret->item.priv_data=ret;
1760 #ifdef DEBUG
1761         ret->show_all=1;
1762 #endif
1763         return ret;
1764 }
1765
1766 static void
1767 navigation_map_rect_destroy(struct map_rect_priv *priv)
1768 {
1769         g_free(priv);
1770 }
1771
1772 static struct item *
1773 navigation_map_get_item(struct map_rect_priv *priv)
1774 {
1775         struct item *ret=&priv->item;
1776         int delta;
1777         if (!priv->itm_next)
1778                 return NULL;
1779         priv->itm=priv->itm_next;
1780         priv->cmd=priv->cmd_next;
1781         priv->cmd_itm=priv->cmd_itm_next;
1782         if (!priv->cmd)
1783                 return NULL;
1784         if (!priv->show_all && priv->itm->prev != NULL)
1785                 priv->itm=priv->cmd->itm;
1786         priv->itm_next=priv->itm->next;
1787         if (priv->itm->prev)
1788                 ret->type=type_nav_none;
1789         else
1790                 ret->type=type_nav_position;
1791         if (priv->cmd->itm == priv->itm) {
1792                 priv->cmd_itm_next=priv->cmd->itm;
1793                 priv->cmd_next=priv->cmd->next;
1794                 if (priv->cmd_itm_next && !priv->cmd_itm_next->next)
1795                         ret->type=type_nav_destination;
1796                 else {
1797                         if (priv->itm && priv->itm->prev && !(priv->itm->flags & AF_ROUNDABOUT) && (priv->itm->prev->flags & AF_ROUNDABOUT)) {
1798
1799                                 switch (((180+22)-priv->cmd->roundabout_delta)/45) {
1800                                 case 0:
1801                                 case 1:
1802                                         ret->type=type_nav_roundabout_r1;
1803                                         break;
1804                                 case 2:
1805                                         ret->type=type_nav_roundabout_r2;
1806                                         break;
1807                                 case 3:
1808                                         ret->type=type_nav_roundabout_r3;
1809                                         break;
1810                                 case 4:
1811                                         ret->type=type_nav_roundabout_r4;
1812                                         break;
1813                                 case 5:
1814                                         ret->type=type_nav_roundabout_r5;
1815                                         break;
1816                                 case 6:
1817                                         ret->type=type_nav_roundabout_r6;
1818                                         break;
1819                                 case 7:
1820                                         ret->type=type_nav_roundabout_r7;
1821                                         break;
1822                                 case 8:
1823                                         ret->type=type_nav_roundabout_r8;
1824                                         break;
1825                                 }
1826                         } else {
1827                                 delta=priv->cmd->delta;
1828                                 if (delta < 0) {
1829                                         delta=-delta;
1830                                         if (delta < 45)
1831                                                 ret->type=type_nav_left_1;
1832                                         else if (delta < 105)
1833                                                 ret->type=type_nav_left_2;
1834                                         else if (delta < 165)
1835                                                 ret->type=type_nav_left_3;
1836                                         else
1837                                                 ret->type=type_none;
1838                                 } else {
1839                                         if (delta < 45)
1840                                                 ret->type=type_nav_right_1;
1841                                         else if (delta < 105)
1842                                                 ret->type=type_nav_right_2;
1843                                         else if (delta < 165)
1844                                                 ret->type=type_nav_right_3;
1845                                         else
1846                                                 ret->type=type_none;
1847                                 }
1848                         }
1849                 }
1850         }
1851         priv->ccount=0;
1852         priv->debug_idx=0;
1853         priv->attr_next=attr_navigation_short;
1854
1855         ret->id_lo=priv->itm->dest_count;
1856         dbg(1,"type=%d\n", ret->type);
1857         return ret;
1858 }
1859
1860 static struct item *
1861 navigation_map_get_item_byid(struct map_rect_priv *priv, int id_hi, int id_lo)
1862 {
1863         struct item *ret;
1864         navigation_map_rect_init(priv);
1865         while ((ret=navigation_map_get_item(priv))) {
1866                 if (ret->id_hi == id_hi && ret->id_lo == id_lo)
1867                         return ret;
1868         }
1869         return NULL;
1870 }
1871
1872 static struct map_methods navigation_map_meth = {
1873         projection_mg,
1874         "utf-8",
1875         navigation_map_destroy,
1876         navigation_map_rect_new,
1877         navigation_map_rect_destroy,
1878         navigation_map_get_item,
1879         navigation_map_get_item_byid,
1880         NULL,
1881         NULL,
1882         NULL,
1883 };
1884
1885 static struct map_priv *
1886 navigation_map_new(struct map_methods *meth, struct attr **attrs)
1887 {
1888         struct map_priv *ret;
1889         struct attr *navigation_attr;
1890
1891         navigation_attr=attr_search(attrs, NULL, attr_navigation);
1892         if (! navigation_attr)
1893                 return NULL;
1894         ret=g_new0(struct map_priv, 1);
1895         *meth=navigation_map_meth;
1896         ret->navigation=navigation_attr->u.navigation;
1897
1898         return ret;
1899 }
1900
1901
1902 void
1903 navigation_init(void)
1904 {
1905         plugin_register_map_type("navigation", navigation_map_new);
1906 }