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