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 shure 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 shure 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 kilometer"), 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                 sitem=map_rect_get_item_byid(mr, sitem->id_hi, sitem->id_lo);
 691                 if (item_attr_get(sitem, attr_street_name, &attr))
 692                         ret->name1=map_convert_string(sitem->map,attr.u.str);
 693                 if (item_attr_get(sitem, attr_street_name_systematic, &attr))
 694                         ret->name2=map_convert_string(sitem->map,attr.u.str);
 695                 navigation_itm_update(ret, ritem);
 696
 697                 while (item_coord_get(ritem, &c[i], 1)) {
 698                         dbg(1, "coord %d 0x%x 0x%x\n", i, c[i].x ,c[i].y);
 699
 700                         if (i < 4)
 701                                 i++;
 702                         else {
 703                                 c[2]=c[3];
 704                                 c[3]=c[4];
 705                         }
 706                 }
 707                 dbg(1,"count=%d\n", i);
 708                 i--;
 709
 710                 ret->angle_start=road_angle(&c[0], &c[1], 0);
 711                 ret->angle_end=road_angle(&c[i-1], &c[i], 0);
 712
 713                 ret->start=c[0];
 714                 ret->end=c[i];
 715
 716                 item_attr_get(ritem, attr_route, &route_attr);
 717                 graph_map = route_get_graph_map(route_attr.u.route);
 718                 if (check_roundabout(ret, graph_map)) {
 719                         ret->flags |= AF_ROUNDABOUT;
 720                 }
 721
 722                 dbg(1,"i=%d start %d end %d '%s' '%s'\n", i, ret->angle_start, ret->angle_end, ret->name1, ret->name2);
 723                 map_rect_destroy(mr);
 724         } else {
 725                 if (this_->last)
 726                         ret->start=ret->end=this_->last->end;
 727         }
 728         if (! this_->first)
 729                 this_->first=ret;
 730         if (this_->last) {
 731                 this_->last->next=ret;
 732                 ret->prev=this_->last;
 733                 if (graph_map) {
 734                         navigation_itm_ways_update(ret,graph_map);
 735                 }
 736         }
 737         dbg(1,"ret=%p\n", ret);
 738         this_->last=ret;
 739         return ret;
 740 }
 741
 742 /**
 743  * @brief Counts how many times a driver could turn right/left
 744  *
 745  * This function counts how many times the driver theoretically could
 746  * turn right/left between two navigation items, not counting the final
 747  * turn itself.
 748  *
 749  * @param from The navigation item which should form the start
 750  * @param to The navigation item which should form the end
 751  * @param direction Set to < 0 to count turns to the left >= 0 for turns to the right
 752  * @return The number of possibilities to turn or -1 on error
 753  */
 754 static int
 755 count_possible_turns(struct navigation_itm *from, struct navigation_itm *to, int direction)
 756 {
 757         int count;
 758         struct navigation_itm *curr;
 759         struct navigation_way *w;
 760
 761         count = 0;
 762         curr = from->next;
 763         while (curr && (curr != to)) {
 764                 w = curr->ways;
 765
 766                 while (w) {
 767                         if (direction < 0) {
 768                                 if (angle_delta(curr->prev->angle_end, w->angle2) < 0) {
 769                                         count++;
 770                                         break;
 771                                 }
 772                         } else {
 773                                 if (angle_delta(curr->prev->angle_end, w->angle2) > 0) {
 774                                         count++;
 775                                         break;
 776                                 }
 777                         }
 778                         w = w->next;
 779                 }
 780                 curr = curr->next;
 781         }
 782
 783         if (!curr) { // from does not lead to to?
 784                 return -1;
 785         }
 786
 787         return count;
 788 }
 789
 790 /**
 791  * @brief Calculates distance and time to the destination
 792  *
 793  * This function calculates the distance and the time to the destination of a
 794  * navigation. If incr is set, this is only calculated for the first navigation
 795  * item, which is a lot faster than re-calculation the whole destination, but works
 796  * only if the rest of the navigation already has been calculated.
 797  *
 798  * @param this_ The navigation whose destination / time should be calculated
 799  * @param incr Set this to true to only calculate the first item. See description.
 800  */
 801 static void
 802 calculate_dest_distance(struct navigation *this_, int incr)
 803 {
 804         int len=0, time=0, count=0;
 805         struct navigation_itm *next,*itm=this_->last;
 806         dbg(1, "enter this_=%p, incr=%d\n", this_, incr);
 807         if (incr) {
 808                 if (itm)
 809                         dbg(2, "old values: (%p) time=%d lenght=%d\n", itm, itm->dest_length, itm->dest_time);
 810                 else
 811                         dbg(2, "old values: itm is null\n");
 812                 itm=this_->first;
 813                 next=itm->next;
 814                 dbg(2, "itm values: time=%d lenght=%d\n", itm->length, itm->time);
 815                 dbg(2, "next values: (%p) time=%d lenght=%d\n", next, next->dest_length, next->dest_time);
 816                 itm->dest_length=next->dest_length+itm->length;
 817                 itm->dest_count=next->dest_count+1;
 818                 itm->dest_time=next->dest_time+itm->time;
 819                 dbg(2, "new values: time=%d lenght=%d\n", itm->dest_length, itm->dest_time);
 820                 return;
 821         }
 822         while (itm) {
 823                 len+=itm->length;
 824                 time+=itm->time;
 825                 itm->dest_length=len;
 826                 itm->dest_time=time;
 827                 itm->dest_count=count++;
 828                 itm=itm->prev;
 829         }
 830         dbg(1,"len %d time %d\n", len, time);
 831 }
 832
 833 /**
 834  * @brief Checks if two navigation items are on the same street
 835  *
 836  * This function checks if two navigation items are on the same street. It returns
 837  * true if either their name or their "systematic name" (e.g. "A6" or "B256") are the
 838  * same.
 839  *
 840  * @param old The first item to be checked
 841  * @param new The second item to be checked
 842  * @return True if both old and new are on the same street
 843  */
 844 static int
 845 is_same_street2(char *old_name1, char *old_name2, char *new_name1, char *new_name2)
 846 {
 847         if (old_name1 && new_name1 && !strcmp(old_name1, new_name1)) {
 848                 dbg(1,"is_same_street: '%s' '%s' vs '%s' '%s' yes (1.)\n", old_name2, new_name2, old_name1, new_name1);
 849                 return 1;
 850         }
 851         if (old_name2 && new_name2 && !strcmp(old_name2, new_name2)) {
 852                 dbg(1,"is_same_street: '%s' '%s' vs '%s' '%s' yes (2.)\n", old_name2, new_name2, old_name1, new_name1);
 853                 return 1;
 854         }
 855         dbg(1,"is_same_street: '%s' '%s' vs '%s' '%s' no\n", old_name2, new_name2, old_name1, new_name1);
 856         return 0;
 857 }
 858
 859 #if 0
 860 /**
 861  * @brief Checks if two navigation items are on the same street
 862  *
 863  * This function checks if two navigation items are on the same street. It returns
 864  * true if the first part of their "systematic name" is equal. If the "systematic name" is
 865  * for example "A352/E3" (a german highway which at the same time is part of the international
 866  * E-road network), it would only search for "A352" in the second item's systematic name.
 867  *
 868  * @param old The first item to be checked
 869  * @param new The second item to be checked
 870  * @return True if the "systematic name" of both items matches. See description.
 871  */
 872 static int
 873 is_same_street_systematic(struct navigation_itm *old, struct navigation_itm *new)
 874 {
 875         int slashold,slashnew;
 876         if (!old->name2 || !new->name2)
 877                 return 1;
 878         slashold=strcspn(old->name2, "/");
 879         slashnew=strcspn(new->name2, "/");
 880         if (slashold != slashnew || strncmp(old->name2, new->name2, slashold))
 881                 return 0;
 882         return 1;
 883 }
 884
 885
 886 /**
 887  * @brief Check if there are multiple possibilities to drive from old
 888  *
 889  * This function checks, if there are multiple streets connected to the exit of "old".
 890  * Sometimes it happens that an item on a map is just segmented, without any other streets
 891  * being connected there, and it is not useful if navit creates a maneuver there.
 892  *
 893  * @param new The navigation item we're driving to
 894  * @return True if there are multiple streets
 895  */
 896 static int
 897 maneuver_multiple_streets(struct navigation_itm *new)
 898 {
 899         if (new->ways) {
 900                 return 1;
 901         } else {
 902                 return 0;
 903         }
 904 }
 905
 906
 907 /**
 908  * @brief Check if the new item is entered "straight"
 909  *
 910  * This function checks if the new item is entered "straight" from the old item, i.e. if there
 911  * is no other street one could take from the old item on with less steering.
 912  *
 913  * @param new The navigation item we're driving to
 914  * @param diff The absolute angle one needs to steer to drive to this item
 915  * @return True if the new item is entered "straight"
 916  */
 917 static int
 918 maneuver_straight(struct navigation_itm *new, int diff)
 919 {
 920         int curr_diff;
 921         struct navigation_way *w;
 922
 923         w = new->ways;
 924         dbg(1,"diff=%d\n", diff);
 925         while (w) {
 926                 curr_diff=abs(angle_delta(new->prev->angle_end, w->angle2));
 927                 dbg(1,"curr_diff=%d\n", curr_diff);
 928                 if (curr_diff < diff) {
 929                         return 0;
 930                 }
 931                 w = w->next;
 932         }
 933         return 1;
 934 }
 935 #endif
 936
 937 static int maneuver_category(enum item_type type)
 938 {
 939         switch (type) {
 940         case type_street_0:
 941                 return 1;
 942         case type_street_1_city:
 943                 return 2;
 944         case type_street_2_city:
 945                 return 3;
 946         case type_street_3_city:
 947                 return 4;
 948         case type_street_4_city:
 949                 return 5;
 950         case type_highway_city:
 951                 return 7;
 952         case type_street_1_land:
 953                 return 2;
 954         case type_street_2_land:
 955                 return 3;
 956         case type_street_3_land:
 957                 return 4;
 958         case type_street_4_land:
 959                 return 5;
 960         case type_street_n_lanes:
 961                 return 6;
 962         case type_highway_land:
 963                 return 7;
 964         case type_ramp:
 965                 return 0;
 966         case type_roundabout:
 967                 return 0;
 968         case type_ferry:
 969                 return 0;
 970         default:
 971                 return 0;
 972         }
 973
 974
 975 }
 976
 977 static int
 978 is_way_allowed(struct navigation_way *way)
 979 {
 980         if (way->dir > 0) {
 981                 if (way->flags & AF_ONEWAYREV)
 982                         return 0;
 983         } else {
 984                 if (way->flags & AF_ONEWAY)
 985                         return 0;
 986         }
 987         return 1;
 988 }
 989
 990 /**
 991  * @brief Checks if navit has to create a maneuver to drive from old to new
 992  *
 993  * This function checks if it has to create a "maneuver" - i.e. guide the user - to drive
 994  * from "old" to "new".
 995  *
 996  * @param old The old navigation item, where we're coming from
 997  * @param new The new navigation item, where we're going to
 998  * @param delta The angle the user has to steer to navigate from old to new
 999  * @param reason A text string explaining how the return value resulted
1000  * @return True if navit should guide the user, false otherwise
1001  */
1002 static int
1003 maneuver_required2(struct navigation_itm *old, struct navigation_itm *new, int *delta, char **reason)
1004 {
1005         int ret=0,d,dw,dlim;
1006         char *r=NULL;
1007         struct navigation_way *w;
1008         int cat,ncat,wcat,maxcat,left=-180,right=180,is_unambigous=0,is_same_street;
1009
1010         dbg(1,"enter %p %p %p\n",old, new, delta);
1011         d=angle_delta(old->angle_end, new->angle_start);
1012         if (!new->ways) {
1013                 /* No announcement necessary */
1014                 r="no: Only one possibility";
1015         } else if (!new->ways->next && new->ways->item.type == type_ramp && !is_way_allowed(new->ways)) {
1016                 /* If the other way is only a ramp and it is one-way in the wrong direction, no announcement necessary */
1017                 r="no: Only ramp";
1018         }
1019         if (! r) {
1020                 if ((old->flags & AF_ROUNDABOUT) && ! (new->flags & AF_ROUNDABOUT)) {
1021                         r="yes: leaving roundabout";
1022                         ret=1;
1023                 } else  if (!(old->flags & AF_ROUNDABOUT) && (new->flags & AF_ROUNDABOUT))
1024                         r="no: entering roundabout";
1025                 else if ((old->flags & AF_ROUNDABOUT) && (new->flags & AF_ROUNDABOUT))
1026                         r="no: staying in roundabout";
1027         }
1028         if (!r && abs(d) > 75) {
1029                 /* always make an announcement if you have to make a sharp turn */
1030                 r="yes: delta over 75";
1031                 ret=1;
1032         }
1033         cat=maneuver_category(old->item.type);
1034         ncat=maneuver_category(new->item.type);
1035         if (!r) {
1036                 /* Check whether the street keeps its name */
1037                 is_same_street=is_same_street2(old->name1, old->name2, new->name1, new->name2);
1038                 w = new->ways;
1039                 maxcat=-1;
1040                 while (w) {
1041                         dw=angle_delta(old->angle_end, w->angle2);
1042                         if (dw < 0) {
1043                                 if (dw > left)
1044                                         left=dw;
1045                         } else {
1046                                 if (dw < right)
1047                                         right=dw;
1048                         }
1049                         wcat=maneuver_category(w->item.type);
1050                         /* If any other street has the same name but isn't a highway (a highway might split up temporarily), then
1051                            we can't use the same name criterium  */
1052                         if (is_same_street && is_same_street2(old->name1, old->name2, w->name1, w->name2) && (cat != 7 || wcat != 7) && is_way_allowed(w))
1053                                 is_same_street=0;
1054                         /* Mark if the street has a higher or the same category */
1055                         if (wcat > maxcat)
1056                                 maxcat=wcat;
1057                         w = w->next;
1058                 }
1059                 /* get the delta limit for checking for other streets. It is lower if the street has no other
1060                    streets of the same or higher category */
1061                 if (ncat < cat)
1062                         dlim=80;
1063                 else
1064                         dlim=120;
1065                 /* if the street is really straight, the others might be closer to straight */
1066                 if (abs(d) < 20)
1067                         dlim/=2;
1068                 if ((maxcat == ncat && maxcat == cat) || (ncat == 0 && cat == 0))
1069                         dlim=abs(d)*620/256;
1070                 else if (maxcat < ncat && maxcat < cat)
1071                         dlim=abs(d)*128/256;
1072                 if (left < -dlim && right > dlim)
1073                         is_unambigous=1;
1074                 if (!is_same_street && is_unambigous < 1) {
1075                         ret=1;
1076                         r="yes: not same street or ambigous";
1077                 } else
1078                         r="no: same street and unambigous";
1079 #ifdef DEBUG
1080                 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);
1081 #endif
1082         }
1083         *delta=d;
1084         if (reason)
1085                 *reason=r;
1086         return ret;
1087
1088
1089 #if 0
1090         if (new->item.type == old->item.type || (new->item.type != type_ramp && old->item.type != type_ramp)) {
1091                 if (is_same_street2(old, new)) {
1092                         if (! entering_straight(new, abs(*delta))) {
1093                                 dbg(1, "maneuver_required: Not driving straight: yes\n");
1094                                 if (reason)
1095                                         *reason="yes: Not driving straight";
1096                                 return 1;
1097                         }
1098
1099                         if (check_multiple_streets(new)) {
1100                                 if (entering_straight(new,abs(*delta)*2)) {
1101                                         if (reason)
1102                                                 *reason="no: delta < ext_limit for same name";
1103                                         return 0;
1104                                 }
1105                                 if (reason)
1106                                         *reason="yes: delta > ext_limit for same name";
1107                                 return 1;
1108                         } else {
1109                                 dbg(1, "maneuver_required: Staying on the same street: no\n");
1110                                 if (reason)
1111                                         *reason="no: Staying on same street";
1112                                 return 0;
1113                         }
1114                 }
1115         } else
1116                 dbg(1, "maneuver_required: old or new is ramp\n");
1117 #if 0
1118         if (old->item.type == type_ramp && (new->item.type == type_highway_city || new->item.type == type_highway_land)) {
1119                 dbg(1, "no_maneuver_required: old is ramp new is highway\n");
1120                 if (reason)
1121                         *reason="no: old is ramp new is highway";
1122                 return 0;
1123         }
1124 #endif
1125 #if 0
1126         if (old->crossings_end == 2) {
1127                 dbg(1, "maneuver_required: only 2 connections: no\n");
1128                 return 0;
1129         }
1130 #endif
1131         dbg(1,"delta=%d-%d=%d\n", new->angle_start, old->angle_end, *delta);
1132         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))) {
1133                 dbg(1, "maneuver_required: highway changed name\n");
1134                 if (reason)
1135                         *reason="yes: highway changed name";
1136                 return 1;
1137         }
1138         if (abs(*delta) < straight_limit) {
1139                 if (! entering_straight(new,abs(*delta))) {
1140                         if (reason)
1141                                 *reason="yes: not straight";
1142                         dbg(1, "maneuver_required: not driving straight: yes\n");
1143                         return 1;
1144                 }
1145
1146                 dbg(1, "maneuver_required: delta(%d) < %d: no\n", *delta, straight_limit);
1147                 if (reason)
1148                         *reason="no: delta < limit";
1149                 return 0;
1150         }
1151         if (abs(*delta) < ext_straight_limit) {
1152                 if (entering_straight(new,abs(*delta)*2)) {
1153                         if (reason)
1154                                 *reason="no: delta < ext_limit";
1155                         return 0;
1156                 }
1157         }
1158
1159         if (! check_multiple_streets(new)) {
1160                 dbg(1, "maneuver_required: only one possibility: no\n");
1161                 if (reason)
1162                         *reason="no: only one possibility";
1163                 return 0;
1164         }
1165
1166         dbg(1, "maneuver_required: delta=%d: yes\n", *delta);
1167         if (reason)
1168                 *reason="yes: delta >= limit";
1169         return 1;
1170 #endif
1171 }
1172
1173 static struct navigation_command *
1174 command_new(struct navigation *this_, struct navigation_itm *itm, int delta)
1175 {
1176         struct navigation_command *ret=g_new0(struct navigation_command, 1);
1177         dbg(1,"enter this_=%p itm=%p delta=%d\n", this_, itm, delta);
1178         ret->delta=delta;
1179         ret->itm=itm;
1180         if (itm && itm->prev && itm->ways && itm->prev->ways && !(itm->flags & AF_ROUNDABOUT) && (itm->prev->flags & AF_ROUNDABOUT)) {
1181                 int len=0;
1182                 int angle=0;
1183                 int entry_angle;
1184                 struct navigation_itm *itm2=itm->prev;
1185                 int exit_angle=angle_median(itm->prev->angle_end, itm->ways->angle2);
1186                 dbg(1,"exit %d median from %d,%d\n", exit_angle,itm->prev->angle_end, itm->ways->angle2);
1187                 while (itm2 && (itm2->flags & AF_ROUNDABOUT)) {
1188                         len+=itm2->length;
1189                         angle=itm2->angle_end;
1190                         itm2=itm2->prev;
1191                 }
1192                 if (itm2 && itm2->next && itm2->next->ways) {
1193                         itm2=itm2->next;
1194                         entry_angle=angle_median(angle_opposite(itm2->angle_start), itm2->ways->angle2);
1195                         dbg(1,"entry %d median from %d(%d),%d\n", entry_angle,angle_opposite(itm2->angle_start), itm2->angle_start, itm2->ways->angle2);
1196                 } else {
1197                         entry_angle=angle_opposite(angle);
1198                 }
1199                 dbg(0,"entry %d exit %d\n", entry_angle, exit_angle);
1200                 ret->roundabout_delta=angle_delta(entry_angle, exit_angle);
1201                 ret->length=len;
1202
1203         }
1204         if (this_->cmd_last) {
1205                 this_->cmd_last->next=ret;
1206                 ret->prev = this_->cmd_last;
1207         }
1208         this_->cmd_last=ret;
1209
1210         if (!this_->cmd_first)
1211                 this_->cmd_first=ret;
1212         return ret;
1213 }
1214
1215 static void
1216 make_maneuvers(struct navigation *this_, struct route *route)
1217 {
1218         struct navigation_itm *itm, *last=NULL, *last_itm=NULL;
1219         int delta;
1220         itm=this_->first;
1221         this_->cmd_last=NULL;
1222         this_->cmd_first=NULL;
1223         while (itm) {
1224                 if (last) {
1225                         if (maneuver_required2(last_itm, itm,&delta,NULL)) {
1226                                 command_new(this_, itm, delta);
1227                         }
1228                 } else
1229                         last=itm;
1230                 last_itm=itm;
1231                 itm=itm->next;
1232         }
1233         command_new(this_, last_itm, 0);
1234 }
1235
1236 static int
1237 contains_suffix(char *name, char *suffix)
1238 {
1239         if (!suffix)
1240                 return 0;
1241         if (strlen(name) < strlen(suffix))
1242                 return 0;
1243         return !strcasecmp(name+strlen(name)-strlen(suffix), suffix);
1244 }
1245
1246 static char *
1247 replace_suffix(char *name, char *search, char *replace)
1248 {
1249         int len=strlen(name)-strlen(search);
1250         char *ret=g_malloc(len+strlen(replace)+1);
1251         strncpy(ret, name, len);
1252         strcpy(ret+len, replace);
1253         if (isupper(name[len])) {
1254                 ret[len]=toupper(ret[len]);
1255         }
1256
1257         return ret;
1258 }
1259
1260 static char *
1261 navigation_item_destination(struct navigation_itm *itm, struct navigation_itm *next, char *prefix)
1262 {
1263         char *ret=NULL,*name1,*sep,*name2;
1264         int i,sex;
1265         if (! prefix)
1266                 prefix="";
1267         if(!itm->name1 && !itm->name2 && itm->item.type == type_ramp) {
1268                 dbg(1,">> Next is ramp %lx current is %lx \n", itm->item.type, next->item.type);
1269
1270                 if(next->item.type == type_ramp)
1271                         return NULL;
1272                 if(itm->item.type == type_highway_city || itm->item.type == type_highway_land )
1273                         return g_strdup_printf("%s%s",prefix,_("exit"));        /* %FIXME Can this even be reached? */
1274                 else
1275                         return g_strdup_printf("%s%s",prefix,_("into the ramp"));
1276
1277         }
1278         if (!itm->name1 && !itm->name2)
1279                 return NULL;
1280         if (itm->name1) {
1281                 sex=-1;
1282                 name1=NULL;
1283                 for (i = 0 ; i < sizeof(suffixes)/sizeof(suffixes[0]) ; i++) {
1284                         if (contains_suffix(itm->name1,suffixes[i].fullname)) {
1285                                 sex=suffixes[i].sex;
1286                                 name1=g_strdup(itm->name1);
1287                                 break;
1288                         }
1289                         if (contains_suffix(itm->name1,suffixes[i].abbrev)) {
1290                                 sex=suffixes[i].sex;
1291                                 name1=replace_suffix(itm->name1, suffixes[i].abbrev, suffixes[i].fullname);
1292                                 break;
1293                         }
1294                 }
1295                 if (itm->name2) {
1296                         name2=itm->name2;
1297                         sep=" ";
1298                 } else {
1299                         name2="";
1300                         sep="";
1301                 }
1302                 switch (sex) {
1303                 case -1:
1304                         /* TRANSLATORS: Arguments: 1: Prefix (Space if required) 2: Street Name 3: Separator (Space if required), 4: Systematic Street Name */
1305                         ret=g_strdup_printf(_("%sinto the street %s%s%s"),prefix,itm->name1, sep, name2);
1306                         break;
1307                 case 1:
1308                         /* 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 */
1309                         ret=g_strdup_printf(_("%sinto the %s%s%s|male form"),prefix,name1, sep, name2);
1310                         break;
1311                 case 2:
1312                         /* 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 */
1313                         ret=g_strdup_printf(_("%sinto the %s%s%s|female form"),prefix,name1, sep, name2);
1314                         break;
1315                 case 3:
1316                         /* 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 */
1317                         ret=g_strdup_printf(_("%sinto the %s%s%s|neutral form"),prefix,name1, sep, name2);
1318                         break;
1319                 }
1320                 g_free(name1);
1321
1322         } else
1323                 /* TRANSLATORS: gives the name of the next road to turn into (into the E17) */
1324                 ret=g_strdup_printf(_("%sinto the %s"),prefix,itm->name2);
1325         name1=ret;
1326         while (name1 && *name1) {
1327                 switch (*name1) {
1328                 case '|':
1329                         *name1='\0';
1330                         break;
1331                 case '/':
1332                         *name1++=' ';
1333                         break;
1334                 default:
1335                         name1++;
1336                 }
1337         }
1338         return ret;
1339 }
1340
1341 static char *
1342 show_maneuver(struct navigation *nav, struct navigation_itm *itm, struct navigation_command *cmd, enum attr_type type, int connect)
1343 {
1344         /* TRANSLATORS: right, as in 'Turn right' */
1345         char *dir=_("right"),*strength="";
1346         int distance=itm->dest_length-cmd->itm->dest_length;
1347         char *d,*ret=NULL;
1348         int delta=cmd->delta;
1349         int level;
1350         int strength_needed;
1351         int skip_roads;
1352         int count_roundabout;
1353         struct navigation_itm *cur;
1354         struct navigation_way *w;
1355
1356         if (connect) {
1357                 level = -2; // level = -2 means "connect to another maneuver via 'then ...'"
1358         } else {
1359                 level=1;
1360         }
1361
1362         w = itm->next->ways;
1363         strength_needed = 0;
1364         if (angle_delta(itm->next->angle_start,itm->angle_end) < 0) {
1365                 while (w) {
1366                         if (angle_delta(w->angle2,itm->angle_end) < 0) {
1367                                 strength_needed = 1;
1368                                 break;
1369                         }
1370                         w = w->next;
1371                 }
1372         } else {
1373                 while (w) {
1374                         if (angle_delta(w->angle2,itm->angle_end) > 0) {
1375                                 strength_needed = 1;
1376                                 break;
1377                         }
1378                         w = w->next;
1379                 }
1380         }
1381
1382         if (delta < 0) {
1383                 /* TRANSLATORS: left, as in 'Turn left' */
1384                 dir=_("left");
1385                 delta=-delta;
1386         }
1387
1388         if (strength_needed) {
1389                 if (delta < 45) {
1390                         /* TRANSLATORS: Don't forget the ending space */
1391                         strength=_("easily ");
1392                 } else if (delta < 105) {
1393                         strength="";
1394                 } else if (delta < 165) {
1395                         /* TRANSLATORS: Don't forget the ending space */
1396                         strength=_("strongly ");
1397                 } else if (delta < 180) {
1398                         /* TRANSLATORS: Don't forget the ending space */
1399                         strength=_("really strongly ");
1400                 } else {
1401                         dbg(1,"delta=%d\n", delta);
1402                         /* TRANSLATORS: Don't forget the ending space */
1403                         strength=_("unknown ");
1404                 }
1405         }
1406         if (type != attr_navigation_long_exact)
1407                 distance=round_distance(distance);
1408         if (type == attr_navigation_speech) {
1409                 if (nav->turn_around && nav->turn_around == nav->turn_around_limit)
1410                         return g_strdup(_("When possible, please turn around"));
1411                 if (!connect) {
1412                         level=navigation_get_announce_level(nav, itm->item.type, distance-cmd->length);
1413                 }
1414                 dbg(1,"distance=%d level=%d type=0x%x\n", distance, level, itm->item.type);
1415         }
1416
1417         if (cmd->itm->prev->flags & AF_ROUNDABOUT) {
1418                 switch (level) {
1419                 case 2:
1420                         return g_strdup(_("Enter the roundabout soon"));
1421                 case 1:
1422                         d = get_distance(distance, type, 1);
1423                         /* TRANSLATORS: %s is the distance to the roundabout */
1424                         ret = g_strdup_printf(_("In %s, enter the roundabout"), d);
1425                         g_free(d);
1426                         return ret;
1427                 case -2:
1428                 case 0:
1429                         cur = cmd->itm->prev;
1430                         count_roundabout = 0;
1431                         while (cur && (cur->flags & AF_ROUNDABOUT)) {
1432                                 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
1433                                         count_roundabout++;
1434                                 }
1435                                 cur = cur->prev;
1436                         }
1437                         switch (level) {
1438                         case 0:
1439                                 ret = g_strdup_printf(_("Leave the roundabout at the %s"), get_exit_count_str(count_roundabout));
1440                                 break;
1441                         case -2:
1442                                 ret = g_strdup_printf(_("then leave the roundabout at the %s"), get_exit_count_str(count_roundabout));
1443                                 break;
1444                         }
1445                         return ret;
1446                 }
1447         }
1448
1449         switch(level) {
1450         case 3:
1451                 d=get_distance(distance, type, 1);
1452                 ret=g_strdup_printf(_("Follow the road for the next %s"), d);
1453                 g_free(d);
1454                 return ret;
1455         case 2:
1456                 d=g_strdup(_("soon"));
1457                 break;
1458         case 1:
1459                 d=get_distance(distance, type, 0);
1460                 break;
1461         case 0:
1462                 skip_roads = count_possible_turns(nav->first,cmd->itm,cmd->delta);
1463                 if (skip_roads > 0) {
1464                         if (get_count_str(skip_roads+1)) {
1465                                 /* TRANSLATORS: First argument is the how manieth street to take, second the direction */
1466                                 ret = g_strdup_printf(_("Take the %1$s road to the %2$s"), get_count_str(skip_roads+1), dir);
1467                                 return ret;
1468                         } else {
1469                                 d = g_strdup_printf(_("after %i roads"), skip_roads);
1470                         }
1471                 } else {
1472                         d=g_strdup(_("now"));
1473                 }
1474                 break;
1475         case -2:
1476                 skip_roads = count_possible_turns(cmd->prev->itm,cmd->itm,cmd->delta);
1477                 if (skip_roads > 0) {
1478                         /* TRANSLATORS: First argument is the how manieth street to take, second the direction */
1479                         if (get_count_str(skip_roads+1)) {
1480                                 ret = g_strdup_printf(_("then take the %1$s road to the %2$s"), get_count_str(skip_roads+1), dir);
1481                                 return ret;
1482                         } else {
1483                                 d = g_strdup_printf(_("after %i roads"), skip_roads);
1484                         }
1485
1486                 } else {
1487                         d = g_strdup("");
1488                 }
1489                 break;
1490         default:
1491                 d=g_strdup(_("error"));
1492         }
1493         if (cmd->itm->next) {
1494                 int tellstreetname = 0;
1495                 char *destination = NULL;
1496
1497                 if(type == attr_navigation_speech) { // In voice mode
1498                         // In Voice Mode only tell the street name in level 1 or in level 0 if level 1
1499                         // was skipped
1500
1501                         if (level == 1) { // we are close to the intersection
1502                                 cmd->itm->streetname_told = 1; // remeber to be checked when we turn
1503                                 tellstreetname = 1; // Ok so we tell the name of the street
1504                         }
1505
1506                         if (level == 0) {
1507                                 if(cmd->itm->streetname_told == 0) // we are right at the intersection
1508                                         tellstreetname = 1;
1509                                 else
1510                                         cmd->itm->streetname_told = 0;  // reset just in case we come to the same street again
1511                         }
1512
1513                 }
1514                 else
1515                      tellstreetname = 1;
1516
1517                 if(nav->tell_street_name && tellstreetname)
1518                         destination=navigation_item_destination(cmd->itm, itm, " ");
1519
1520                 if (level != -2) {
1521                         /* 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' */
1522                         ret=g_strdup_printf(_("Turn %1$s%2$s %3$s%4$s"), strength, dir, d, destination ? destination:"");
1523                 } else {
1524                         /* TRANSLATORS: First argument is strength, second direction, third how many roads to skip, fourth destination */
1525                         ret=g_strdup_printf(_("then turn %1$s%2$s %3$s%4$s"), strength, dir, d, destination ? destination:"");
1526                 }
1527                 g_free(destination);
1528         } else {
1529                 if (!connect) {
1530                         ret=g_strdup_printf(_("You have reached your destination %s"), d);
1531                 } else {
1532                         ret=g_strdup_printf(_("then you have reached your destination."));
1533                 }
1534         }
1535         g_free(d);
1536         return ret;
1537 }
1538
1539 /**
1540  * @brief Creates announcements for maneuvers, plus maneuvers immediately following the next maneuver
1541  *
1542  * This function does create an announcement for the current maneuver and for maneuvers
1543  * immediately following that maneuver, if these are too close and we're in speech navigation.
1544  *
1545  * @return An announcement that should be made
1546  */
1547 static char *
1548 show_next_maneuvers(struct navigation *nav, struct navigation_itm *itm, struct navigation_command *cmd, enum attr_type type)
1549 {
1550         struct navigation_command *cur,*prev;
1551         int distance=itm->dest_length-cmd->itm->dest_length;
1552         int level, dist, i, time;
1553         int speech_time,time2nav;
1554         char *ret,*old,*buf,*next;
1555
1556         if (type != attr_navigation_speech) {
1557                 return show_maneuver(nav, itm, cmd, type, 0); // We accumulate maneuvers only in speech navigation
1558         }
1559
1560         level=navigation_get_announce_level(nav, itm->item.type, distance-cmd->length);
1561
1562         if (level > 1) {
1563                 return show_maneuver(nav, itm, cmd, type, 0); // We accumulate maneuvers only if they are close
1564         }
1565
1566         if (cmd->itm->told) {
1567                 return g_strdup("");
1568         }
1569
1570         ret = show_maneuver(nav, itm, cmd, type, 0);
1571         time2nav = navigation_time(itm,cmd->itm->prev);
1572         old = NULL;
1573
1574         cur = cmd->next;
1575         prev = cmd;
1576         i = 0;
1577         while (cur && cur->itm) {
1578                 // We don't merge more than 3 announcements...
1579                 if (i > 1) { // if you change this, please also change the value below, that is used to terminate the loop
1580                         break;
1581                 }
1582
1583                 next = show_maneuver(nav,prev->itm, cur, type, 0);
1584                 speech_time = navit_speech_estimate(nav->navit,next);
1585                 g_free(next);
1586
1587                 if (speech_time == -1) { // user didn't set cps
1588                         speech_time = 30; // assume 3 seconds
1589                 }
1590
1591                 dist = prev->itm->dest_length - cur->itm->dest_length;
1592                 time = navigation_time(prev->itm,cur->itm->prev);
1593
1594                 if (time >= (speech_time + 30)) { // 3 seconds for understanding what has been said
1595                         break;
1596                 }
1597
1598                 old = ret;
1599                 buf = show_maneuver(nav, prev->itm, cur, type, 1);
1600                 ret = g_strdup_printf("%s, %s", old, buf);
1601                 g_free(buf);
1602                 if (navit_speech_estimate(nav->navit,ret) > time2nav) {
1603                         g_free(ret);
1604                         ret = old;
1605                         i = 2; // This will terminate the loop
1606                 } else {
1607                         g_free(old);
1608                 }
1609
1610                 // If the two maneuvers are *really* close, we shouldn't tell the second one again, because TTS won't be fast enough
1611                 if (time <= speech_time) {
1612                         cur->itm->told = 1;
1613                 }
1614
1615                 prev = cur;
1616                 cur = cur->next;
1617                 i++;
1618         }
1619
1620         return ret;
1621 }
1622
1623 static void
1624 navigation_call_callbacks(struct navigation *this_, int force_speech)
1625 {
1626         int distance, level = 0, level2;
1627         void *p=this_;
1628         if (!this_->cmd_first)
1629                 return;
1630         callback_list_call(this_->callback, 1, &p);
1631         dbg(1,"force_speech=%d turn_around=%d turn_around_limit=%d\n", force_speech, this_->turn_around, this_->turn_around_limit);
1632         distance=round_distance(this_->first->dest_length-this_->cmd_first->itm->dest_length);
1633         if (this_->turn_around_limit && this_->turn_around == this_->turn_around_limit) {
1634                 dbg(1,"distance=%d distance_turn=%d\n", distance, this_->distance_turn);
1635                 while (distance > this_->distance_turn) {
1636                         this_->level_last=4;
1637                         level=4;
1638                         force_speech=1;
1639                         if (this_->distance_turn >= 500)
1640                                 this_->distance_turn*=2;
1641                         else
1642                                 this_->distance_turn=500;
1643                 }
1644         } else if (!this_->turn_around_limit || this_->turn_around == -this_->turn_around_limit+1) {
1645                 this_->distance_turn=50;
1646                 distance-=this_->cmd_first->length;
1647                 level=navigation_get_announce_level(this_, this_->first->item.type, distance);
1648                 if (this_->cmd_first->itm->prev) {
1649                         level2=navigation_get_announce_level(this_, this_->cmd_first->itm->prev->item.type, distance);
1650                         if (level2 > level)
1651                                 level=level2;
1652                 }
1653                 if (level < this_->level_last) {
1654                         dbg(1,"level %d < %d\n", level, this_->level_last);
1655                         this_->level_last=level;
1656                         force_speech=1;
1657                 }
1658                 if (!item_is_equal(this_->cmd_first->itm->item, this_->item_last)) {
1659                         dbg(1,"item different\n");
1660                         this_->item_last=this_->cmd_first->itm->item;
1661                         force_speech=1;
1662                 }
1663         }
1664         if (force_speech) {
1665                 this_->level_last=level;
1666                 dbg(1,"distance=%d level=%d type=0x%x\n", distance, level, this_->first->item.type);
1667                 callback_list_call(this_->callback_speech, 1, &p);
1668         }
1669 }
1670
1671 static void
1672 navigation_update(struct navigation *this_, struct route *route, struct attr *attr)
1673 {
1674         struct map *map;
1675         struct map_rect *mr;
1676         struct item *ritem;                     /* Holds an item from the route map */
1677         struct item *sitem;                     /* Holds the corresponding item from the actual map */
1678         struct attr street_item,street_direction;
1679         struct navigation_itm *itm;
1680         int mode=0, incr=0, first=1;
1681         if (attr->type != attr_route_status)
1682                 return;
1683
1684         dbg(1,"enter %d\n", mode);
1685         if (attr->u.num == route_status_no_destination || attr->u.num == route_status_not_found || attr->u.num == route_status_path_done_new)
1686                 navigation_flush(this_);
1687         if (attr->u.num != route_status_path_done_new && attr->u.num != route_status_path_done_incremental)
1688                 return;
1689
1690         if (! this_->route)
1691                 return;
1692         map=route_get_map(this_->route);
1693         if (! map)
1694                 return;
1695         mr=map_rect_new(map, NULL);
1696         if (! mr)
1697                 return;
1698         dbg(1,"enter\n");
1699         while ((ritem=map_rect_get_item(mr))) {
1700                 if (ritem->type == type_route_start && this_->turn_around > -this_->turn_around_limit+1)
1701                         this_->turn_around--;
1702                 if (ritem->type == type_route_start_reverse && this_->turn_around < this_->turn_around_limit)
1703                         this_->turn_around++;
1704                 if (ritem->type != type_street_route)
1705                         continue;
1706                 if (first && item_attr_get(ritem, attr_street_item, &street_item)) {
1707                         first=0;
1708                         if (!item_attr_get(ritem, attr_direction, &street_direction))
1709                                 street_direction.u.num=0;
1710                         sitem=street_item.u.item;
1711                         dbg(1,"sitem=%p\n", sitem);
1712                         itm=item_hash_lookup(this_->hash, sitem);
1713                         dbg(2,"itm for item with id (0x%x,0x%x) is %p\n", sitem->id_hi, sitem->id_lo, itm);
1714                         if (itm && itm->direction != street_direction.u.num) {
1715                                 dbg(2,"wrong direction\n");
1716                                 itm=NULL;
1717                         }
1718                         navigation_destroy_itms_cmds(this_, itm);
1719                         if (itm) {
1720                                 navigation_itm_update(itm, ritem);
1721                                 break;
1722                         }
1723                         dbg(1,"not on track\n");
1724                 }
1725                 navigation_itm_new(this_, ritem);
1726         }
1727         dbg(2,"turn_around=%d\n", this_->turn_around);
1728         if (first)
1729                 navigation_destroy_itms_cmds(this_, NULL);
1730         else {
1731                 if (! ritem) {
1732                         navigation_itm_new(this_, NULL);
1733                         make_maneuvers(this_,this_->route);
1734                 }
1735                 calculate_dest_distance(this_, incr);
1736                 profile(0,"end");
1737                 navigation_call_callbacks(this_, FALSE);
1738         }
1739         map_rect_destroy(mr);
1740 }
1741
1742 static void
1743 navigation_flush(struct navigation *this_)
1744 {
1745         navigation_destroy_itms_cmds(this_, NULL);
1746 }
1747
1748
1749 void
1750 navigation_destroy(struct navigation *this_)
1751 {
1752         navigation_flush(this_);
1753         item_hash_destroy(this_->hash);
1754         callback_list_destroy(this_->callback);
1755         callback_list_destroy(this_->callback_speech);
1756         g_free(this_);
1757 }
1758
1759 int
1760 navigation_register_callback(struct navigation *this_, enum attr_type type, struct callback *cb)
1761 {
1762         if (type == attr_navigation_speech)
1763                 callback_list_add(this_->callback_speech, cb);
1764         else
1765                 callback_list_add(this_->callback, cb);
1766         return 1;
1767 }
1768
1769 void
1770 navigation_unregister_callback(struct navigation *this_, enum attr_type type, struct callback *cb)
1771 {
1772         if (type == attr_navigation_speech)
1773                 callback_list_remove_destroy(this_->callback_speech, cb);
1774         else
1775                 callback_list_remove_destroy(this_->callback, cb);
1776 }
1777
1778 struct map *
1779 navigation_get_map(struct navigation *this_)
1780 {
1781         if (! this_->map)
1782                 this_->map=map_new(NULL, (struct attr*[]){
1783                         &(struct attr){attr_type,{"navigation"}},
1784                         &(struct attr){attr_navigation,.u.navigation=this_},
1785                         &(struct attr){attr_data,{""}},
1786                         &(struct attr){attr_description,{"Navigation"}},
1787                         NULL});
1788         return this_->map;
1789 }
1790
1791 struct map_priv {
1792         struct navigation *navigation;
1793 };
1794
1795 struct map_rect_priv {
1796         struct navigation *nav;
1797         struct navigation_command *cmd;
1798         struct navigation_command *cmd_next;
1799         struct navigation_itm *itm;
1800         struct navigation_itm *itm_next;
1801         struct navigation_itm *cmd_itm;
1802         struct navigation_itm *cmd_itm_next;
1803         struct item item;
1804         enum attr_type attr_next;
1805         int ccount;
1806         int debug_idx;
1807         struct navigation_way *ways;
1808         int show_all;
1809         char *str;
1810 };
1811
1812 static int
1813 navigation_map_item_coord_get(void *priv_data, struct coord *c, int count)
1814 {
1815         struct map_rect_priv *this=priv_data;
1816         if (this->ccount || ! count)
1817                 return 0;
1818         *c=this->itm->start;
1819         this->ccount=1;
1820         return 1;
1821 }
1822
1823 static int
1824 navigation_map_item_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1825 {
1826         struct map_rect_priv *this_=priv_data;
1827         attr->type=attr_type;
1828         struct navigation_command *cmd=this_->cmd;
1829         struct navigation_itm *itm=this_->itm;
1830         struct navigation_itm *prev=itm->prev;
1831
1832         if (this_->str) {
1833                 g_free(this_->str);
1834                 this_->str=NULL;
1835         }
1836
1837         if (cmd) {
1838                 if (cmd->itm != itm)
1839                         cmd=NULL;
1840         }
1841         switch(attr_type) {
1842         case attr_navigation_short:
1843                 this_->attr_next=attr_navigation_long;
1844                 if (cmd) {
1845                         this_->str=attr->u.str=show_next_maneuvers(this_->nav, this_->cmd_itm, cmd, attr_type);
1846                         return 1;
1847                 }
1848                 return 0;
1849         case attr_navigation_long:
1850                 this_->attr_next=attr_navigation_long_exact;
1851                 if (cmd) {
1852                         this_->str=attr->u.str=show_next_maneuvers(this_->nav, this_->cmd_itm, cmd, attr_type);
1853                         return 1;
1854                 }
1855                 return 0;
1856         case attr_navigation_long_exact:
1857                 this_->attr_next=attr_navigation_speech;
1858                 if (cmd) {
1859                         this_->str=attr->u.str=show_next_maneuvers(this_->nav, this_->cmd_itm, cmd, attr_type);
1860                         return 1;
1861                 }
1862                 return 0;
1863         case attr_navigation_speech:
1864                 this_->attr_next=attr_length;
1865                 if (cmd) {
1866                         this_->str=attr->u.str=show_next_maneuvers(this_->nav, this_->cmd_itm, this_->cmd, attr_type);
1867                         return 1;
1868                 }
1869                 return 0;
1870         case attr_length:
1871                 this_->attr_next=attr_time;
1872                 if (cmd) {
1873                         attr->u.num=this_->cmd_itm->dest_length-cmd->itm->dest_length;
1874                         return 1;
1875                 }
1876                 return 0;
1877         case attr_time:
1878                 this_->attr_next=attr_destination_length;
1879                 if (cmd) {
1880                         attr->u.num=this_->cmd_itm->dest_time-cmd->itm->dest_time;
1881                         return 1;
1882                 }
1883                 return 0;
1884         case attr_destination_length:
1885                 attr->u.num=itm->dest_length;
1886                 this_->attr_next=attr_destination_time;
1887                 return 1;
1888         case attr_destination_time:
1889                 attr->u.num=itm->dest_time;
1890                 this_->attr_next=attr_street_name;
1891                 return 1;
1892         case attr_street_name:
1893                 attr->u.str=itm->name1;
1894                 this_->attr_next=attr_street_name_systematic;
1895                 if (attr->u.str)
1896                         return 1;
1897                 return 0;
1898         case attr_street_name_systematic:
1899                 attr->u.str=itm->name2;
1900                 this_->attr_next=attr_debug;
1901                 if (attr->u.str)
1902                         return 1;
1903                 return 0;
1904         case attr_debug:
1905                 switch(this_->debug_idx) {
1906                 case 0:
1907                         this_->debug_idx++;
1908                         this_->str=attr->u.str=g_strdup_printf("angle:%d (- %d)", itm->angle_start, itm->angle_end);
1909                         return 1;
1910                 case 1:
1911                         this_->debug_idx++;
1912                         this_->str=attr->u.str=g_strdup_printf("item type:%s", item_to_name(itm->item.type));
1913                         return 1;
1914                 case 2:
1915                         this_->debug_idx++;
1916                         if (cmd) {
1917                                 this_->str=attr->u.str=g_strdup_printf("delta:%d", cmd->delta);
1918                                 return 1;
1919                         }
1920                 case 3:
1921                         this_->debug_idx++;
1922                         if (prev) {
1923                                 this_->str=attr->u.str=g_strdup_printf("prev street_name:%s", prev->name1);
1924                                 return 1;
1925                         }
1926                 case 4:
1927                         this_->debug_idx++;
1928                         if (prev) {
1929                                 this_->str=attr->u.str=g_strdup_printf("prev street_name_systematic:%s", prev->name2);
1930                                 return 1;
1931                         }
1932                 case 5:
1933                         this_->debug_idx++;
1934                         if (prev) {
1935                                 this_->str=attr->u.str=g_strdup_printf("prev angle:(%d -) %d", prev->angle_start, prev->angle_end);
1936                                 return 1;
1937                         }
1938                 case 6:
1939                         this_->debug_idx++;
1940                         this_->ways=itm->ways;
1941                         if (prev) {
1942                                 this_->str=attr->u.str=g_strdup_printf("prev item type:%s", item_to_name(prev->item.type));
1943                                 return 1;
1944                         }
1945                 case 7:
1946                         if (this_->ways && prev) {
1947                                 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);
1948                                 this_->ways=this_->ways->next;
1949                                 return 1;
1950                         }
1951                         this_->debug_idx++;
1952                 case 8:
1953                         this_->debug_idx++;
1954                         if (prev) {
1955                                 int delta=0;
1956                                 char *reason=NULL;
1957                                 maneuver_required2(prev, itm, &delta, &reason);
1958                                 this_->str=attr->u.str=g_strdup_printf("reason:%s",reason);
1959                                 return 1;
1960                         }
1961
1962                 default:
1963                         this_->attr_next=attr_none;
1964                         return 0;
1965                 }
1966         case attr_any:
1967                 while (this_->attr_next != attr_none) {
1968                         if (navigation_map_item_attr_get(priv_data, this_->attr_next, attr))
1969                                 return 1;
1970                 }
1971                 return 0;
1972         default:
1973                 attr->type=attr_none;
1974                 return 0;
1975         }
1976 }
1977
1978 static struct item_methods navigation_map_item_methods = {
1979         NULL,
1980         navigation_map_item_coord_get,
1981         NULL,
1982         navigation_map_item_attr_get,
1983 };
1984
1985
1986 static void
1987 navigation_map_destroy(struct map_priv *priv)
1988 {
1989         g_free(priv);
1990 }
1991
1992 static void
1993 navigation_map_rect_init(struct map_rect_priv *priv)
1994 {
1995         priv->cmd_next=priv->nav->cmd_first;
1996         priv->cmd_itm_next=priv->itm_next=priv->nav->first;
1997 }
1998
1999 static struct map_rect_priv *
2000 navigation_map_rect_new(struct map_priv *priv, struct map_selection *sel)
2001 {
2002         struct navigation *nav=priv->navigation;
2003         struct map_rect_priv *ret=g_new0(struct map_rect_priv, 1);
2004         ret->nav=nav;
2005         navigation_map_rect_init(ret);
2006         ret->item.meth=&navigation_map_item_methods;
2007         ret->item.priv_data=ret;
2008 #ifdef DEBUG
2009         ret->show_all=1;
2010 #endif
2011         return ret;
2012 }
2013
2014 static void
2015 navigation_map_rect_destroy(struct map_rect_priv *priv)
2016 {
2017         g_free(priv);
2018 }
2019
2020 static struct item *
2021 navigation_map_get_item(struct map_rect_priv *priv)
2022 {
2023         struct item *ret=&priv->item;
2024         int delta;
2025         if (!priv->itm_next)
2026                 return NULL;
2027         priv->itm=priv->itm_next;
2028         priv->cmd=priv->cmd_next;
2029         priv->cmd_itm=priv->cmd_itm_next;
2030         if (!priv->cmd)
2031                 return NULL;
2032         if (!priv->show_all && priv->itm->prev != NULL)
2033                 priv->itm=priv->cmd->itm;
2034         priv->itm_next=priv->itm->next;
2035         if (priv->itm->prev)
2036                 ret->type=type_nav_none;
2037         else
2038                 ret->type=type_nav_position;
2039         if (priv->cmd->itm == priv->itm) {
2040                 priv->cmd_itm_next=priv->cmd->itm;
2041                 priv->cmd_next=priv->cmd->next;
2042                 if (priv->cmd_itm_next && !priv->cmd_itm_next->next)
2043                         ret->type=type_nav_destination;
2044                 else {
2045                         if (priv->itm && priv->itm->prev && !(priv->itm->flags & AF_ROUNDABOUT) && (priv->itm->prev->flags & AF_ROUNDABOUT)) {
2046
2047                                 switch (((180+22)-priv->cmd->roundabout_delta)/45) {
2048                                 case 0:
2049                                 case 1:
2050                                         ret->type=type_nav_roundabout_r1;
2051                                         break;
2052                                 case 2:
2053                                         ret->type=type_nav_roundabout_r2;
2054                                         break;
2055                                 case 3:
2056                                         ret->type=type_nav_roundabout_r3;
2057                                         break;
2058                                 case 4:
2059                                         ret->type=type_nav_roundabout_r4;
2060                                         break;
2061                                 case 5:
2062                                         ret->type=type_nav_roundabout_r5;
2063                                         break;
2064                                 case 6:
2065                                         ret->type=type_nav_roundabout_r6;
2066                                         break;
2067                                 case 7:
2068                                         ret->type=type_nav_roundabout_r7;
2069                                         break;
2070                                 case 8:
2071                                         ret->type=type_nav_roundabout_r8;
2072                                         break;
2073                                 }
2074                         } else {
2075                                 delta=priv->cmd->delta;
2076                                 if (delta < 0) {
2077                                         delta=-delta;
2078                                         if (delta < 45)
2079                                                 ret->type=type_nav_left_1;
2080                                         else if (delta < 105)
2081                                                 ret->type=type_nav_left_2;
2082                                         else if (delta < 165)
2083                                                 ret->type=type_nav_left_3;
2084                                         else
2085                                                 ret->type=type_none;
2086                                 } else {
2087                                         if (delta < 45)
2088                                                 ret->type=type_nav_right_1;
2089                                         else if (delta < 105)
2090                                                 ret->type=type_nav_right_2;
2091                                         else if (delta < 165)
2092                                                 ret->type=type_nav_right_3;
2093                                         else
2094                                                 ret->type=type_none;
2095                                 }
2096                         }
2097                 }
2098         }
2099         priv->ccount=0;
2100         priv->debug_idx=0;
2101         priv->attr_next=attr_navigation_short;
2102
2103         ret->id_lo=priv->itm->dest_count;
2104         dbg(1,"type=%d\n", ret->type);
2105         return ret;
2106 }
2107
2108 static struct item *
2109 navigation_map_get_item_byid(struct map_rect_priv *priv, int id_hi, int id_lo)
2110 {
2111         struct item *ret;
2112         navigation_map_rect_init(priv);
2113         while ((ret=navigation_map_get_item(priv))) {
2114                 if (ret->id_hi == id_hi && ret->id_lo == id_lo)
2115                         return ret;
2116         }
2117         return NULL;
2118 }
2119
2120 static struct map_methods navigation_map_meth = {
2121         projection_mg,
2122         "utf-8",
2123         navigation_map_destroy,
2124         navigation_map_rect_new,
2125         navigation_map_rect_destroy,
2126         navigation_map_get_item,
2127         navigation_map_get_item_byid,
2128         NULL,
2129         NULL,
2130         NULL,
2131 };
2132
2133 static struct map_priv *
2134 navigation_map_new(struct map_methods *meth, struct attr **attrs)
2135 {
2136         struct map_priv *ret;
2137         struct attr *navigation_attr;
2138
2139         navigation_attr=attr_search(attrs, NULL, attr_navigation);
2140         if (! navigation_attr)
2141                 return NULL;
2142         ret=g_new0(struct map_priv, 1);
2143         *meth=navigation_map_meth;
2144         ret->navigation=navigation_attr->u.navigation;
2145
2146         return ret;
2147 }
2148
2149 void
2150 navigation_set_route(struct navigation *this_, struct route *route)
2151 {
2152         struct attr callback;
2153         this_->route=route;
2154         this_->route_cb=callback_new_attr_1(callback_cast(navigation_update), attr_route_status, this_);
2155         callback.type=attr_callback;
2156         callback.u.callback=this_->route_cb;
2157         route_add_attr(route, &callback);
2158 }
2159
2160 void
2161 navigation_init(void)
2162 {
2163         plugin_register_map_type("navigation", navigation_map_new);
2164 }