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