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

   1 /**
   2  * Navit, a modular navigation system.
   3  * Copyright (C) 2005-2008 Navit Team
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * version 2 as published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the
  16  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA  02110-1301, USA.
  18  */
  19
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <math.h>
  24 #include <glib.h>
  25 #include <libintl.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
  40 #define _(STRING)    gettext(STRING)
  41
  42 struct suffix {
  43         char *fullname;
  44         char *abbrev;
  45         int sex;
  46 } suffixes[]= {
  47         {"weg",NULL,1},
  48         {"platz","pl.",1},
  49         {"ring",NULL,1},
  50         {"allee",NULL,2},
  51         {"gasse",NULL,2},
  52         {"straße","str.",2},
  53         {"strasse",NULL,2},
  54 };
  55
  56 struct navigation {
  57         struct map *map;
  58         struct item_hash *hash;
  59         struct navigation_itm *first;
  60         struct navigation_itm *last;
  61         struct navigation_command *cmd_first;
  62         struct navigation_command *cmd_last;
  63         struct callback_list *callback_speech;
  64         struct callback_list *callback;
  65         int level_last;
  66         struct item item_last;
  67         int turn_around;
  68         int turn_around_limit;
  69         int distance_turn;
  70         int distance_last;
  71         int announce[route_item_last-route_item_first+1][3];
  72 };
  73
  74
  75 struct navigation_command {
  76         struct navigation_itm *itm;
  77         struct navigation_command *next;
  78         int delta;
  79 };
  80
  81 struct navigation *
  82 navigation_new(struct attr **attrs)
  83 {
  84         int i,j;
  85         struct navigation *ret=g_new0(struct navigation, 1);
  86         ret->hash=item_hash_new();
  87         ret->callback=callback_list_new();
  88         ret->callback_speech=callback_list_new();
  89         ret->level_last=-2;
  90         ret->distance_last=-2;
  91         ret->distance_turn=50;
  92         ret->turn_around_limit=3;
  93
  94         for (j = 0 ; j <= route_item_last-route_item_first ; j++) {
  95                 for (i = 0 ; i < 3 ; i++) {
  96                         ret->announce[j][i]=-1;
  97                 }
  98         }
  99
 100         return ret;
 101 }
 102
 103 int
 104 navigation_set_announce(struct navigation *this_, enum item_type type, int *level)
 105 {
 106         int i;
 107         if (type < route_item_first || type > route_item_last) {
 108                 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
 109                 return 0;
 110         }
 111         for (i = 0 ; i < 3 ; i++)
 112                 this_->announce[type-route_item_first][i]=level[i];
 113         return 1;
 114 }
 115
 116 static int
 117 navigation_get_announce_level(struct navigation *this_, enum item_type type, int dist)
 118 {
 119         int i;
 120
 121         if (type < route_item_first || type > route_item_last)
 122                 return -1;
 123         for (i = 0 ; i < 3 ; i++) {
 124                 if (dist <= this_->announce[type-route_item_first][i])
 125                         return i;
 126         }
 127         return i;
 128 }
 129
 130 struct navigation_itm {
 131         char *name1;
 132         char *name2;
 133         struct item item;
 134         int direction;
 135         int straight;
 136         int angle_start;
 137         int angle_end;
 138         struct coord c;
 139         int time;
 140         int length;
 141         int dest_time;
 142         int dest_length;
 143         int told;
 144         int dest_count;
 145         struct navigation_itm *next;
 146         struct navigation_itm *prev;
 147 };
 148
 149 /* 0=N,90=E */
 150 static int
 151 road_angle(struct coord *c1, struct coord *c2, int dir)
 152 {
 153         int ret=transform_get_angle_delta(c1, c2, dir);
 154         dbg(1, "road_angle(0x%x,0x%x - 0x%x,0x%x)=%d\n", c1->x, c1->y, c2->x, c2->y, ret);
 155         return ret;
 156 }
 157
 158 static int
 159 round_distance(int dist)
 160 {
 161         if (dist < 100) {
 162                 dist=(dist+5)/10;
 163                 return dist*10;
 164         }
 165         if (dist < 250) {
 166                 dist=(dist+13)/25;
 167                 return dist*25;
 168         }
 169         if (dist < 500) {
 170                 dist=(dist+25)/50;
 171                 return dist*50;
 172         }
 173         if (dist < 1000) {
 174                 dist=(dist+50)/100;
 175                 return dist*100;
 176         }
 177         if (dist < 5000) {
 178                 dist=(dist+50)/100;
 179                 return dist*100;
 180         }
 181         if (dist < 100000) {
 182                 dist=(dist+500)/1000;
 183                 return dist*1000;
 184         }
 185         dist=(dist+5000)/10000;
 186         return dist*10000;
 187 }
 188
 189 static char *
 190 get_distance(int dist, enum attr_type type, int is_length)
 191 {
 192         if (type == attr_navigation_long) {
 193                 if (is_length)
 194                         return g_strdup_printf(_("%d m"), dist);
 195                 else
 196                         return g_strdup_printf(_("in %d m"), dist);
 197         }
 198         if (dist < 1000) {
 199                 if (is_length)
 200                         return g_strdup_printf(_("%d meters"), dist);
 201                 else
 202                         return g_strdup_printf(_("in %d meters"), dist);
 203         }
 204         if (dist < 5000) {
 205                 int rem=(dist/100)%10;
 206                 if (rem) {
 207                         if (is_length)
 208                                 return g_strdup_printf(_("%d.%d kilometer"), dist/1000, rem);
 209                         else
 210                                 return g_strdup_printf(_("in %d.%d kilometers"), dist/1000, rem);
 211                 }
 212         }
 213         if (is_length)
 214                 return g_strdup_printf(ngettext("one kilometer","%d kilometers", dist/1000), dist/1000);
 215         else
 216                 return g_strdup_printf(ngettext("in one kilometer","in %d kilometers", dist/1000), dist/1000);
 217 }
 218
 219 static void
 220 navigation_destroy_itms_cmds(struct navigation *this_, struct navigation_itm *end)
 221 {
 222         struct navigation_itm *itm;
 223         struct navigation_command *cmd;
 224         dbg(2,"enter this_=%p this_->first=%p this_->cmd_first=%p end=%p\n", this_, this_->first, this_->cmd_first, end);
 225         if (this_->cmd_first)
 226                 dbg(2,"this_->cmd_first->itm=%p\n", this_->cmd_first->itm);
 227         while (this_->first && this_->first != end) {
 228                 itm=this_->first;
 229                 dbg(3,"destroying %p\n", itm);
 230                 item_hash_remove(this_->hash, &itm->item);
 231                 this_->first=itm->next;
 232                 if (this_->first)
 233                         this_->first->prev=NULL;
 234                 if (this_->cmd_first && this_->cmd_first->itm == itm->next) {
 235                         cmd=this_->cmd_first;
 236                         this_->cmd_first=cmd->next;
 237                         g_free(cmd);
 238                 }
 239                 map_convert_free(itm->name1);
 240                 map_convert_free(itm->name2);
 241                 g_free(itm);
 242         }
 243         if (! this_->first)
 244                 this_->last=NULL;
 245         if (! this_->first && end)
 246                 dbg(0,"end wrong\n");
 247         dbg(2,"ret this_->first=%p this_->cmd_first=%p\n",this_->first, this_->cmd_first);
 248 }
 249
 250 static void
 251 navigation_itm_update(struct navigation_itm *itm, struct item *ritem)
 252 {
 253         struct attr length, time, straight;
 254         if (! item_attr_get(ritem, attr_length, &length)) {
 255                 dbg(0,"no length\n");
 256                 return;
 257         }
 258         if (! item_attr_get(ritem, attr_time, &time)) {
 259                 dbg(0,"no time\n");
 260                 return;
 261         }
 262
 263         if (item_attr_get(ritem, attr_route_follow_straight, &straight)) {
 264                 itm->straight = straight.u.num;
 265         } else {
 266                 itm->straight = 0;
 267         }
 268
 269         dbg(1,"length=%d time=%d\n", length.u.num, time.u.num);
 270         itm->length=length.u.num;
 271         itm->time=time.u.num;
 272 }
 273
 274 static struct navigation_itm *
 275 navigation_itm_new(struct navigation *this_, struct item *ritem)
 276 {
 277         struct navigation_itm *ret=g_new0(struct navigation_itm, 1);
 278         int i=0;
 279         struct item *sitem;
 280         struct attr street_item,direction;
 281         struct map_rect *mr;
 282         struct attr attr;
 283         struct coord c[5];
 284
 285         if (ritem) {
 286                 ret->told=0;
 287                 if (! item_attr_get(ritem, attr_street_item, &street_item)) {
 288                         dbg(0,"no street item\n");
 289                         return NULL;
 290                 }
 291                 if (item_attr_get(ritem, attr_direction, &direction))
 292                         ret->direction=direction.u.num;
 293                 else
 294                         ret->direction=0;
 295                 sitem=street_item.u.item;
 296                 ret->item=*sitem;
 297                 item_hash_insert(this_->hash, sitem, ret);
 298                 mr=map_rect_new(sitem->map, NULL);
 299                 sitem=map_rect_get_item_byid(mr, sitem->id_hi, sitem->id_lo);
 300                 if (item_attr_get(sitem, attr_street_name, &attr))
 301                         ret->name1=map_convert_string(sitem->map,attr.u.str);
 302                 if (item_attr_get(sitem, attr_street_name_systematic, &attr))
 303                         ret->name2=map_convert_string(sitem->map,attr.u.str);
 304                 navigation_itm_update(ret, ritem);
 305
 306                 while (item_coord_get(ritem, &c[i], 1)) {
 307                         dbg(1, "coord %d 0x%x 0x%x\n", i, c[i].x ,c[i].y);
 308
 309                         if (i < 4)
 310                                 i++;
 311                         else {
 312                                 c[2]=c[3];
 313                                 c[3]=c[4];
 314                         }
 315                 }
 316                 dbg(1,"count=%d\n", i);
 317                 i--;
 318
 319                 ret->angle_start=road_angle(&c[0], &c[1], 0);
 320                 ret->angle_end=road_angle(&c[i-1], &c[i], 0);
 321
 322                 ret->c=c[0];
 323                 dbg(1,"i=%d start %d end %d '%s' '%s'\n", i, ret->angle_start, ret->angle_end, ret->name1, ret->name2);
 324                 map_rect_destroy(mr);
 325         }
 326         if (! this_->first)
 327                 this_->first=ret;
 328         if (this_->last) {
 329                 this_->last->next=ret;
 330                 ret->prev=this_->last;
 331         }
 332         dbg(1,"ret=%p\n", ret);
 333         this_->last=ret;
 334         return ret;
 335 }
 336
 337 /**
 338  * @brief Calculates distance and time to the destination
 339  *
 340  * This function calculates the distance and the time to the destination of a
 341  * navigation. If incr is set, this is only calculated for the first navigation
 342  * item, which is a lot faster than re-calculation the whole destination, but works
 343  * only if the rest of the navigation already has been calculated.
 344  *
 345  * @param this_ The navigation whose destination / time should be calculated
 346  * @param incr Set this to true to only calculate the first item. See description.
 347  */
 348 static void
 349 calculate_dest_distance(struct navigation *this_, int incr)
 350 {
 351         int len=0, time=0, count=0;
 352         struct navigation_itm *next,*itm=this_->last;
 353         dbg(1, "enter this_=%p, incr=%d\n", this_, incr);
 354         if (incr) {
 355                 if (itm)
 356                         dbg(2, "old values: (%p) time=%d lenght=%d\n", itm, itm->dest_length, itm->dest_time);
 357                 else
 358                         dbg(2, "old values: itm is null\n");
 359                 itm=this_->first;
 360                 next=itm->next;
 361                 dbg(2, "itm values: time=%d lenght=%d\n", itm->length, itm->time);
 362                 dbg(2, "next values: (%p) time=%d lenght=%d\n", next, next->dest_length, next->dest_time);
 363                 itm->dest_length=next->dest_length+itm->length;
 364                 itm->dest_count=next->dest_count+1;
 365                 itm->dest_time=next->dest_time+itm->time;
 366                 dbg(2, "new values: time=%d lenght=%d\n", itm->dest_length, itm->dest_time);
 367                 return;
 368         }
 369         while (itm) {
 370                 len+=itm->length;
 371                 time+=itm->time;
 372                 itm->dest_length=len;
 373                 itm->dest_time=time;
 374                 itm->dest_count=count++;
 375                 itm=itm->prev;
 376         }
 377         dbg(1,"len %d time %d\n", len, time);
 378 }
 379
 380 /**
 381  * @brief Checks if two navigation items are on the same street
 382  *
 383  * This function checks if two navigation items are on the same street. It returns
 384  * true if either their name or their "systematic name" (e.g. "A6" or "B256") are the
 385  * same.
 386  *
 387  * @param old The first item to be checked
 388  * @param new The second item to be checked
 389  * @return True if both old and new are on the same street
 390  */
 391 static int
 392 is_same_street2(struct navigation_itm *old, struct navigation_itm *new)
 393 {
 394         if (old->name1 && new->name1 && !strcmp(old->name1, new->name1)) {
 395                 dbg(1,"is_same_street: '%s' '%s' vs '%s' '%s' yes (1.)\n", old->name2, new->name2, old->name1, new->name1);
 396                 return 1;
 397         }
 398         if (old->name2 && new->name2 && !strcmp(old->name2, new->name2)) {
 399                 dbg(1,"is_same_street: '%s' '%s' vs '%s' '%s' yes (2.)\n", old->name2, new->name2, old->name1, new->name1);
 400                 return 1;
 401         }
 402         dbg(1,"is_same_street: '%s' '%s' vs '%s' '%s' no\n", old->name2, new->name2, old->name1, new->name1);
 403         return 0;
 404 }
 405
 406 /**
 407  * @brief Checks if two navigation items are on the same street
 408  *
 409  * This function checks if two navigation items are on the same street. It returns
 410  * true if the first part of their "systematic name" is equal. If the "systematic name" is
 411  * for example "A352/E3" (a german highway which at the same time is part of the international
 412  * E-road network), it would only search for "A352" in the second item's systematic name.
 413  *
 414  * @param old The first item to be checked
 415  * @param new The second item to be checked
 416  * @return True if the "systematic name" of both items matches. See description.
 417  */
 418 static int
 419 is_same_street_systematic(struct navigation_itm *old, struct navigation_itm *new)
 420 {
 421         int slashold,slashnew;
 422         if (!old->name2 || !new->name2)
 423                 return 1;
 424         slashold=strcspn(old->name2, "/");
 425         slashnew=strcspn(new->name2, "/");
 426         if (slashold != slashnew || strncmp(old->name2, new->name2, slashold))
 427                 return 0;
 428         return 1;
 429 }
 430
 431 /**
 432  * @brief Checks if navit has to create a maneuver to drive from old to new
 433  *
 434  * This function checks if it has to create a "maneuver" - i.e. guide the user - to drive
 435  * from "old" to "new".
 436  *
 437  * @param old The old navigation item, where we're coming from
 438  * @param new The new navigation item, where we're going to
 439  * @param delta The angle the user has to steer to navigate from old to new
 440  * @return True if navit should guide the user, false otherwise
 441  */
 442 static int
 443 maneuver_required2(struct navigation_itm *old, struct navigation_itm *new, int *delta)
 444 {
 445         dbg(1,"enter %p %p %p\n",old, new, delta);
 446         if (new->item.type == old->item.type || (new->item.type != type_ramp && old->item.type != type_ramp)) {
 447                 if (is_same_street2(old, new)) {
 448                         return 0;
 449                 }
 450         } else
 451                 dbg(1, "maneuver_required: old or new is ramp\n");
 452         if (old->item.type == type_ramp && (new->item.type == type_highway_city || new->item.type == type_highway_land)) {
 453                 dbg(1, "no_maneuver_required: old is ramp new is highway\n");
 454                 return 0;
 455         }
 456 #if 0
 457         if (old->crossings_end == 2) {
 458                 dbg(1, "maneuver_required: only 2 connections: no\n");
 459                 return 0;
 460         }
 461 #endif
 462         *delta=new->angle_start-old->angle_end;
 463         if (*delta < -180)
 464                 *delta+=360;
 465         if (*delta > 180)
 466                 *delta-=360;
 467         dbg(1,"delta=%d-%d=%d\n", new->angle_start, old->angle_end, *delta);
 468         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))) {
 469                 dbg(1, "maneuver_required: highway changed name\n");
 470                 return 1;
 471         }
 472         if (*delta < 20 && *delta >-20) {
 473                 if (! new->straight) { /* We're not entering this item straight, so have a maneuver */
 474                         return 1;
 475                 }
 476
 477                 dbg(1, "maneuver_required: delta(%d) < 20: no\n", *delta);
 478                 return 0;
 479         }
 480         dbg(1, "maneuver_required: delta=%d: yes\n", *delta);
 481         return 1;
 482 }
 483
 484 static struct navigation_command *
 485 command_new(struct navigation *this_, struct navigation_itm *itm, int delta)
 486 {
 487         struct navigation_command *ret=g_new0(struct navigation_command, 1);
 488         dbg(1,"enter this_=%p itm=%p delta=%d\n", this_, itm, delta);
 489         ret->delta=delta;
 490         ret->itm=itm;
 491         if (this_->cmd_last)
 492                 this_->cmd_last->next=ret;
 493         this_->cmd_last=ret;
 494
 495         if (!this_->cmd_first)
 496                 this_->cmd_first=ret;
 497         return ret;
 498 }
 499
 500 static void
 501 make_maneuvers(struct navigation *this_)
 502 {
 503         struct navigation_itm *itm, *last=NULL, *last_itm=NULL;
 504         int delta;
 505         itm=this_->first;
 506         this_->cmd_last=NULL;
 507         this_->cmd_first=NULL;
 508         while (itm) {
 509                 if (last) {
 510                         if (maneuver_required2(last_itm, itm, &delta)) {
 511                                 command_new(this_, itm, delta);
 512                         }
 513                 } else
 514                         last=itm;
 515                 last_itm=itm;
 516                 itm=itm->next;
 517         }
 518 }
 519
 520 static int
 521 contains_suffix(char *name, char *suffix)
 522 {
 523         if (!suffix)
 524                 return 0;
 525         if (strlen(name) < strlen(suffix))
 526                 return 0;
 527         return !strcasecmp(name+strlen(name)-strlen(suffix), suffix);
 528 }
 529
 530 static char *
 531 replace_suffix(char *name, char *search, char *replace)
 532 {
 533         int len=strlen(name)-strlen(search);
 534         char *ret=g_malloc(len+strlen(replace)+1);
 535         strncpy(ret, name, len);
 536         strcpy(ret+len, replace);
 537
 538         return ret;
 539 }
 540
 541 static char *
 542 navigation_item_destination(struct navigation_itm *itm, struct navigation_itm *next, char *prefix)
 543 {
 544         char *ret=NULL,*name1,*sep,*name2;
 545         int i,sex;
 546         if (! prefix)
 547                 prefix="";
 548         if(!itm->name1 && !itm->name2 && itm->item.type == type_ramp) {
 549                 dbg(1,">> Next is ramp %lx current is %lx \n", itm->item.type, next->item.type);
 550
 551                 if(next->item.type == type_ramp)
 552                         return NULL;
 553                 if(itm->item.type == type_highway_city || itm->item.type == type_highway_land )
 554                         return g_strdup_printf("%s%s",prefix,_("exit"));        /* %FIXME Can this even be reached? */
 555                 else
 556                         return g_strdup_printf("%s%s",prefix,_("ramp"));
 557
 558         }
 559         if (!itm->name1 && !itm->name2)
 560                 return NULL;
 561         if (itm->name1) {
 562                 sex=-1;
 563                 name1=NULL;
 564                 for (i = 0 ; i < sizeof(suffixes)/sizeof(suffixes[0]) ; i++) {
 565                         if (contains_suffix(itm->name1,suffixes[i].fullname)) {
 566                                 sex=suffixes[i].sex;
 567                                 name1=g_strdup(itm->name1);
 568                                 break;
 569                         }
 570                         if (contains_suffix(itm->name1,suffixes[i].abbrev)) {
 571                                 sex=suffixes[i].sex;
 572                                 name1=replace_suffix(itm->name1, suffixes[i].abbrev, suffixes[i].fullname);
 573                                 break;
 574                         }
 575                 }
 576                 if (itm->name2) {
 577                         name2=itm->name2;
 578                         sep=" ";
 579                 } else {
 580                         name2="";
 581                         sep="";
 582                 }
 583                 switch (sex) {
 584                 case -1:
 585                         /* TRANSLATORS: Arguments: 1: Prefix (Space if required) 2: Street Name 3: Separator (Space if required), 4: Systematic Street Name */
 586                         ret=g_strdup_printf(_("%sinto the street %s%s%s"),prefix,itm->name1, sep, name2);
 587                         break;
 588                 case 1:
 589                         /* 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 */
 590                         ret=g_strdup_printf(_("%sinto the %s%s%s|male form"),prefix,name1, sep, name2);
 591                         break;
 592                 case 2:
 593                         /* 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 */
 594                         ret=g_strdup_printf(_("%sinto the %s%s%s|female form"),prefix,name1, sep, name2);
 595                         break;
 596                 case 3:
 597                         /* 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 */
 598                         ret=g_strdup_printf(_("%sinto the %s%s%s|neutral form"),prefix,name1, sep, name2);
 599                         break;
 600                 }
 601                 g_free(name1);
 602
 603         } else
 604                 /* TRANSLATORS: gives the name of the next road to turn into (into the E17) */
 605                 ret=g_strdup_printf(_("into the %s"),itm->name2);
 606         name1=ret;
 607         while (*name1) {
 608                 switch (*name1) {
 609                 case '|':
 610                         *name1='\0';
 611                         break;
 612                 case '/':
 613                         *name1++=' ';
 614                         break;
 615                 default:
 616                         name1++;
 617                 }
 618         }
 619         return ret;
 620 }
 621
 622
 623 static char *
 624 show_maneuver(struct navigation *nav, struct navigation_itm *itm, struct navigation_command *cmd, enum attr_type type)
 625 {
 626         /* TRANSLATORS: right, as in 'Turn right' */
 627         char *dir=_("right"),*strength="";
 628         int distance=itm->dest_length-cmd->itm->dest_length;
 629         char *d,*ret;
 630         int delta=cmd->delta;
 631         int level;
 632         level=1;
 633         if (delta < 0) {
 634                 /* TRANSLATORS: left, as in 'Turn left' */
 635                 dir=_("left");
 636                 delta=-delta;
 637         }
 638         if (delta < 45) {
 639                 /* TRANSLATORS: Don't forget the ending space */
 640                 strength=_("easily ");
 641         } else if (delta < 105) {
 642                 strength="";
 643         } else if (delta < 165) {
 644                 /* TRANSLATORS: Don't forget the ending space */
 645                 strength=_("strongly ");
 646         } else {
 647                 dbg(1,"delta=%d\n", delta);
 648                 /* TRANSLATORS: Don't forget the ending space */
 649                 strength=_("unknown ");
 650         }
 651         if (type != attr_navigation_long_exact)
 652                 distance=round_distance(distance);
 653         if (type == attr_navigation_speech) {
 654                 if (nav->turn_around && nav->turn_around == nav->turn_around_limit)
 655                         return g_strdup(_("When possible, please turn around"));
 656                 level=navigation_get_announce_level(nav, itm->item.type, distance);
 657                 dbg(1,"distance=%d level=%d type=0x%x\n", distance, level, itm->item.type);
 658         }
 659         switch(level) {
 660         case 3:
 661                 d=get_distance(distance, type, 1);
 662                 ret=g_strdup_printf(_("Follow the road for the next %s"), d);
 663                 g_free(d);
 664                 return ret;
 665         case 2:
 666                 d=g_strdup(_("soon"));
 667                 break;
 668         case 1:
 669                 d=get_distance(distance, type, 0);
 670                 break;
 671         case 0:
 672                 d=g_strdup(_("now"));
 673                 break;
 674         default:
 675                 d=g_strdup(_("error"));
 676         }
 677         if (cmd->itm->next) {
 678                 int tellstreetname = 0;
 679                 char *destination = NULL;
 680
 681                 if(type == attr_navigation_speech) { // In voice mode
 682                         // In Voice Mode only tell the street name in level 1 or in level 0 if level 1
 683                         // was skipped
 684
 685                         if (level == 1) { // we are close to the intersection
 686                                 cmd->itm->told = 1; // remeber to be checked when we turn
 687                                 tellstreetname = 1; // Ok so we tell the name of the street
 688                         }
 689
 690                         if (level == 0) {
 691                                 if(cmd->itm->told == 0) // we are write at the intersection
 692                                         tellstreetname = 1;
 693                                 else
 694                                         cmd->itm->told = 0;  // reset just in case we come to the same street again
 695                         }
 696
 697                 }
 698                 else
 699                      tellstreetname = 1;
 700
 701                 if(tellstreetname)
 702                         destination=navigation_item_destination(cmd->itm, itm, " ");
 703                 /* 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' */
 704                 ret=g_strdup_printf(_("Turn %1$s%2$s %3$s%4$s"), strength, dir, d, destination ? destination:"");
 705                 g_free(destination);
 706         } else
 707                 ret=g_strdup_printf(_("You have reached your destination %s"), d);
 708         g_free(d);
 709         return ret;
 710 }
 711
 712 static void
 713 navigation_call_callbacks(struct navigation *this_, int force_speech)
 714 {
 715         int distance, level = 0;
 716         void *p=this_;
 717         if (!this_->cmd_first)
 718                 return;
 719         callback_list_call(this_->callback, 1, &p);
 720         dbg(1,"force_speech=%d turn_around=%d turn_around_limit=%d\n", force_speech, this_->turn_around, this_->turn_around_limit);
 721         distance=round_distance(this_->first->dest_length-this_->cmd_first->itm->dest_length);
 722         if (this_->turn_around_limit && this_->turn_around == this_->turn_around_limit) {
 723                 dbg(1,"distance=%d distance_turn=%d\n", distance, this_->distance_turn);
 724                 while (distance > this_->distance_turn) {
 725                         this_->level_last=4;
 726                         level=4;
 727                         force_speech=1;
 728                         if (this_->distance_turn >= 500)
 729                                 this_->distance_turn*=2;
 730                         else
 731                                 this_->distance_turn=500;
 732                 }
 733         } else if (!this_->turn_around_limit || this_->turn_around == -this_->turn_around_limit+1) {
 734                 this_->distance_turn=50;
 735                 level=navigation_get_announce_level(this_, this_->first->item.type, distance);
 736                 if (level < this_->level_last) {
 737                         dbg(1,"level %d < %d\n", level, this_->level_last);
 738                         this_->level_last=level;
 739                         force_speech=1;
 740                 }
 741                 if (!item_is_equal(this_->cmd_first->itm->item, this_->item_last)) {
 742                         dbg(1,"item different\n");
 743                         this_->item_last=this_->cmd_first->itm->item;
 744                         force_speech=1;
 745                 }
 746         }
 747         if (force_speech) {
 748                 this_->level_last=level;
 749                 dbg(1,"distance=%d level=%d type=0x%x\n", distance, level, this_->first->item.type);
 750                 callback_list_call(this_->callback_speech, 1, &p);
 751         }
 752 }
 753
 754 void
 755 navigation_update(struct navigation *this_, struct route *route)
 756 {
 757         struct map *map;
 758         struct map_rect *mr;
 759         struct item *ritem;                     /* Holds an item from the route map */
 760         struct item *sitem;                     /* Holds the corresponding item from the actual map */
 761         struct attr street_item,street_direction;
 762         struct navigation_itm *itm;
 763         int incr=0;
 764
 765         if (! route)
 766                 return;
 767         map=route_get_map(route);
 768         if (! map)
 769                 return;
 770         mr=map_rect_new(map, NULL);
 771         if (! mr)
 772                 return;
 773         dbg(1,"enter\n");
 774         ritem=map_rect_get_item(mr);
 775         if (ritem) {
 776                 if (!item_attr_get(ritem, attr_street_item, &street_item)) {
 777                         ritem=map_rect_get_item(mr);
 778                         if (! ritem) {
 779                                 return;
 780                         }
 781                         if (!item_attr_get(ritem, attr_street_item, &street_item)) {
 782                                 dbg(0,"no street item\n");
 783                         }
 784                 }
 785                 if (!item_attr_get(ritem, attr_direction, &street_direction))
 786                         street_direction.u.num=0;
 787                 sitem=street_item.u.item;
 788                 dbg(1,"sitem=%p\n", sitem);
 789                 itm=item_hash_lookup(this_->hash, sitem);
 790                 dbg(2,"itm for item with id (0x%x,0x%x) is %p\n", sitem->id_hi, sitem->id_lo, itm);
 791                 if (itm && itm->direction != street_direction.u.num) {
 792                         dbg(2,"wrong direction\n");
 793                         itm=NULL;
 794                 }
 795                 navigation_destroy_itms_cmds(this_, itm);
 796                 if (itm) {
 797                         incr=1;
 798                         navigation_itm_update(itm, ritem);
 799                 } else {
 800                         dbg(1,"not on track\n");
 801                         do {
 802                                 dbg(1,"item\n");
 803                                 navigation_itm_new(this_, ritem);
 804                                 ritem=map_rect_get_item(mr);
 805                         } while (ritem);
 806                         itm=navigation_itm_new(this_, NULL);
 807                         make_maneuvers(this_);
 808                 }
 809                 calculate_dest_distance(this_, incr);
 810                 dbg(2,"destination distance old=%d new=%d\n", this_->distance_last, this_->first->dest_length);
 811                 if (this_->first->dest_length > this_->distance_last && this_->distance_last >= 0)
 812                         this_->turn_around++;
 813                 else
 814                         this_->turn_around--;
 815                 if (this_->turn_around > this_->turn_around_limit)
 816                         this_->turn_around=this_->turn_around_limit;
 817                 else if (this_->turn_around < -this_->turn_around_limit+1)
 818                         this_->turn_around=-this_->turn_around_limit+1;
 819                 dbg(2,"turn_around=%d\n", this_->turn_around);
 820                 this_->distance_last=this_->first->dest_length;
 821                 profile(0,"end");
 822                 navigation_call_callbacks(this_, FALSE);
 823         } else
 824                 navigation_destroy_itms_cmds(this_, NULL);
 825         map_rect_destroy(mr);
 826
 827 #if 0
 828         struct route_path_handle *rph;
 829         struct route_path_segment *s;
 830         struct navigation_itm *itm;
 831         struct route_info *pos,*dst;
 832         struct street_data *sd;
 833         int *speedlist;
 834         int len,end_flag=0;
 835         int incr;
 836
 837         profile(0,NULL);
 838         pos=route_get_pos(route);
 839         dst=route_get_dst(route);
 840         if (! pos || ! dst)
 841                 return;
 842         speedlist=route_get_speedlist(route);
 843         len=route_info_length(pos, dst, 0);
 844         dbg(2,"len pos,dst = %d\n", len);
 845         if (len == -1) {
 846                 len=route_info_length(pos, NULL, 0);
 847                 dbg(2,"len pos = %d\n", len);
 848                 end_flag=1;
 849         }
 850         sd=route_info_street(pos);
 851         itm=item_hash_lookup(this_->hash, &sd->item);
 852         dbg(2,"itm for item with id (0x%x,0x%x) is %p\n", sd->item.id_hi, sd->item.id_lo, itm);
 853         navigation_destroy_itms_cmds(this_, itm);
 854         if (itm)
 855                 incr=1;
 856         else {
 857                 itm=navigation_itm_new(this_, &sd->item, route_info_point(pos, -1));
 858                 incr=0;
 859         }
 860         itm->length=len;
 861         itm->time=route_time(speedlist, &sd->item, len);
 862         dbg(2,"%p time = %d\n", itm, itm->time);
 863         if (!incr) {
 864                 printf("not on track\n");
 865                 rph=route_path_open(route);
 866                 if (rph) {
 867                         while((s=route_path_get_segment(rph))) {
 868                                 itm=navigation_itm_new(this_, route_path_segment_get_item(s),route_path_segment_get_start(s));
 869                                 itm->time=route_path_segment_get_time(s);
 870                                 itm->length=route_path_segment_get_length(s);
 871                         }
 872                         route_path_close(rph);
 873                 }
 874                 if (end_flag) {
 875                         len=route_info_length(NULL, dst, 0);
 876                         dbg(1, "end %d\n", len);
 877                         sd=route_info_street(dst);
 878                         itm=navigation_itm_new(this_, &sd->item, route_info_point(pos, 2));
 879                         itm->length=len;
 880                         itm->time=route_time(speedlist, &sd->item, len);
 881                 }
 882                 itm=navigation_itm_new(this_, NULL, NULL);
 883                 make_maneuvers(this_);
 884         }
 885         calculate_dest_distance(this_, incr);
 886         dbg(2,"destination distance old=%d new=%d\n", this_->distance_last, this_->first->dest_length);
 887         if (this_->first->dest_length > this_->distance_last && this_->distance_last >= 0)
 888                 this_->turn_around=1;
 889         else
 890                 this_->turn_around=0;
 891         dbg(2,"turn_around=%d\n", this_->turn_around);
 892         this_->distance_last=this_->first->dest_length;
 893         profile(0,"end");
 894         navigation_call_callbacks(this_, FALSE);
 895 #endif
 896 }
 897
 898 void
 899 navigation_flush(struct navigation *this_)
 900 {
 901         navigation_destroy_itms_cmds(this_, NULL);
 902 }
 903
 904
 905 void
 906 navigation_destroy(struct navigation *this_)
 907 {
 908         navigation_flush(this_);
 909         item_hash_destroy(this_->hash);
 910         callback_list_destroy(this_->callback);
 911         callback_list_destroy(this_->callback_speech);
 912         g_free(this_);
 913 }
 914
 915 int
 916 navigation_register_callback(struct navigation *this_, enum attr_type type, struct callback *cb)
 917 {
 918         if (type == attr_navigation_speech)
 919                 callback_list_add(this_->callback_speech, cb);
 920         else
 921                 callback_list_add(this_->callback, cb);
 922         return 1;
 923 }
 924
 925 void
 926 navigation_unregister_callback(struct navigation *this_, enum attr_type type, struct callback *cb)
 927 {
 928         if (type == attr_navigation_speech)
 929                 callback_list_remove_destroy(this_->callback_speech, cb);
 930         else
 931                 callback_list_remove_destroy(this_->callback, cb);
 932 }
 933
 934 struct map *
 935 navigation_get_map(struct navigation *this_)
 936 {
 937         if (! this_->map)
 938                 this_->map=map_new((struct attr*[]){
 939                         &(struct attr){attr_type,{"navigation"}},
 940                         &(struct attr){attr_navigation,.u.navigation=this_},
 941                         &(struct attr){attr_data,{""}},
 942                         &(struct attr){attr_description,{"Navigation"}},
 943                         NULL});
 944         return this_->map;
 945 }
 946
 947 struct map_priv {
 948         struct navigation *navigation;
 949 };
 950
 951 struct map_rect_priv {
 952         struct navigation *nav;
 953         struct navigation_command *cmd;
 954         struct navigation_command *cmd_next;
 955         struct navigation_itm *itm;
 956         struct navigation_itm *itm_next;
 957         struct navigation_itm *cmd_itm;
 958         struct navigation_itm *cmd_itm_next;
 959         struct item item;
 960         enum attr_type attr_next;
 961         int ccount;
 962         int debug_idx;
 963         int show_all;
 964         char *str;
 965 };
 966
 967 static int
 968 navigation_map_item_coord_get(void *priv_data, struct coord *c, int count)
 969 {
 970         struct map_rect_priv *this=priv_data;
 971         if (this->ccount || ! count)
 972                 return 0;
 973         *c=this->itm->c;
 974         this->ccount=1;
 975         return 1;
 976 }
 977
 978 static int
 979 navigation_map_item_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
 980 {
 981         struct map_rect_priv *this_=priv_data;
 982         attr->type=attr_type;
 983         struct navigation_command *cmd=this_->cmd;
 984         struct navigation_itm *itm=this_->itm;
 985         struct navigation_itm *prev=itm->prev;
 986
 987         if (this_->str) {
 988                 g_free(this_->str);
 989                 this_->str=NULL;
 990         }
 991
 992         if (cmd) {
 993                 if (cmd->itm != itm)
 994                         cmd=NULL;
 995         }
 996         switch(attr_type) {
 997         case attr_navigation_short:
 998                 this_->attr_next=attr_navigation_long;
 999                 if (cmd) {
1000                         this_->str=attr->u.str=show_maneuver(this_->nav, this_->cmd_itm, cmd, attr_type);
1001                         return 1;
1002                 }
1003                 return 0;
1004         case attr_navigation_long:
1005                 this_->attr_next=attr_navigation_long_exact;
1006                 if (cmd) {
1007                         this_->str=attr->u.str=show_maneuver(this_->nav, this_->cmd_itm, cmd, attr_type);
1008                         return 1;
1009                 }
1010                 return 0;
1011         case attr_navigation_long_exact:
1012                 this_->attr_next=attr_navigation_speech;
1013                 if (cmd) {
1014                         this_->str=attr->u.str=show_maneuver(this_->nav, this_->cmd_itm, cmd, attr_type);
1015                         return 1;
1016                 }
1017                 return 0;
1018         case attr_navigation_speech:
1019                 this_->attr_next=attr_length;
1020                 if (cmd) {
1021                         this_->str=attr->u.str=show_maneuver(this_->nav, this_->cmd_itm, this_->cmd, attr_type);
1022                         return 1;
1023                 }
1024                 return 0;
1025         case attr_length:
1026                 this_->attr_next=attr_time;
1027                 if (cmd) {
1028                         attr->u.num=this_->cmd_itm->dest_length-cmd->itm->dest_length;
1029                         return 1;
1030                 }
1031                 return 0;
1032         case attr_time:
1033                 this_->attr_next=attr_destination_length;
1034                 if (cmd) {
1035                         attr->u.num=this_->cmd_itm->dest_time-cmd->itm->dest_time;
1036                         return 1;
1037                 }
1038                 return 0;
1039         case attr_destination_length:
1040                 attr->u.num=itm->dest_length;
1041                 this_->attr_next=attr_destination_time;
1042                 return 1;
1043         case attr_destination_time:
1044                 attr->u.num=itm->dest_time;
1045                 this_->attr_next=attr_street_name;
1046                 return 1;
1047         case attr_street_name:
1048                 attr->u.str=itm->name1;
1049                 this_->attr_next=attr_street_name_systematic;
1050                 return 1;
1051         case attr_street_name_systematic:
1052                 attr->u.str=itm->name2;
1053                 this_->attr_next=attr_debug;
1054                 return 1;
1055         case attr_debug:
1056                 switch(this_->debug_idx) {
1057                 case 0:
1058                         this_->debug_idx++;
1059                         this_->str=attr->u.str=g_strdup_printf("angle:%d - %d", itm->angle_start, itm->angle_end);
1060                         return 1;
1061                 case 1:
1062                         this_->debug_idx++;
1063                         this_->str=attr->u.str=g_strdup_printf("item type:%s", item_to_name(itm->item.type));
1064                         return 1;
1065                 case 2:
1066                         this_->debug_idx++;
1067                         if (cmd) {
1068                                 this_->str=attr->u.str=g_strdup_printf("delta:%d", cmd->delta);
1069                                 return 1;
1070                         }
1071                 case 3:
1072                         this_->debug_idx++;
1073                         if (prev) {
1074                                 this_->str=attr->u.str=g_strdup_printf("prev street_name:%s", prev->name1);
1075                                 return 1;
1076                         }
1077                 case 4:
1078                         this_->debug_idx++;
1079                         if (prev) {
1080                                 this_->str=attr->u.str=g_strdup_printf("prev street_name_systematic:%s", prev->name2);
1081                                 return 1;
1082                         }
1083                 case 5:
1084                         this_->debug_idx++;
1085                         this_->str=attr->u.str=g_strdup_printf("prev angle:%d - %d", prev->angle_start, prev->angle_end);
1086                         return 1;
1087                 case 6:
1088                         this_->debug_idx++;
1089                         if (prev) {
1090                                 this_->str=attr->u.str=g_strdup_printf("prev item type:%s", item_to_name(prev->item.type));
1091                                 return 1;
1092                         }
1093                 default:
1094                         this_->attr_next=attr_none;
1095                         return 0;
1096                 }
1097         case attr_any:
1098                 while (this_->attr_next != attr_none) {
1099                         if (navigation_map_item_attr_get(priv_data, this_->attr_next, attr))
1100                                 return 1;
1101                 }
1102                 return 0;
1103         default:
1104                 attr->type=attr_none;
1105                 return 0;
1106         }
1107 }
1108
1109 static struct item_methods navigation_map_item_methods = {
1110         NULL,
1111         navigation_map_item_coord_get,
1112         NULL,
1113         navigation_map_item_attr_get,
1114 };
1115
1116
1117 static void
1118 navigation_map_destroy(struct map_priv *priv)
1119 {
1120         g_free(priv);
1121 }
1122
1123 static void
1124 navigation_map_rect_init(struct map_rect_priv *priv)
1125 {
1126         priv->cmd_next=priv->nav->cmd_first;
1127         priv->cmd_itm_next=priv->itm_next=priv->nav->first;
1128 }
1129
1130 static struct map_rect_priv *
1131 navigation_map_rect_new(struct map_priv *priv, struct map_selection *sel)
1132 {
1133         struct navigation *nav=priv->navigation;
1134         struct map_rect_priv *ret=g_new0(struct map_rect_priv, 1);
1135         ret->nav=nav;
1136         navigation_map_rect_init(ret);
1137         ret->item.meth=&navigation_map_item_methods;
1138         ret->item.priv_data=ret;
1139         return ret;
1140 }
1141
1142 static void
1143 navigation_map_rect_destroy(struct map_rect_priv *priv)
1144 {
1145         g_free(priv);
1146 }
1147
1148 static struct item *
1149 navigation_map_get_item(struct map_rect_priv *priv)
1150 {
1151         struct item *ret=&priv->item;
1152         int delta;
1153         if (!priv->itm_next)
1154                 return NULL;
1155         priv->itm=priv->itm_next;
1156         priv->cmd=priv->cmd_next;
1157         priv->cmd_itm=priv->cmd_itm_next;
1158         if (!priv->show_all) {
1159                 if (!priv->cmd)
1160                         return NULL;
1161                 priv->itm=priv->cmd->itm;
1162         }
1163         priv->itm_next=priv->itm->next;
1164         ret->type=type_nav_none;
1165         if (priv->cmd->itm == priv->itm) {
1166                 priv->cmd_itm_next=priv->cmd->itm;
1167                 priv->cmd_next=priv->cmd->next;
1168                 delta=priv->cmd->delta;
1169                 if (delta < 0) {
1170                         delta=-delta;
1171                         if (delta < 45)
1172                                 ret->type=type_nav_left_1;
1173                         else if (delta < 105)
1174                                 ret->type=type_nav_left_2;
1175                         else if (delta < 165)
1176                                 ret->type=type_nav_left_3;
1177                         else
1178                                 ret->type=type_none;
1179                 } else {
1180                         if (delta < 45)
1181                                 ret->type=type_nav_right_1;
1182                         else if (delta < 105)
1183                                 ret->type=type_nav_right_2;
1184                         else if (delta < 165)
1185                                 ret->type=type_nav_right_3;
1186                         else
1187                                 ret->type=type_none;
1188                 }
1189         }
1190         priv->ccount=0;
1191         priv->debug_idx=0;
1192         priv->attr_next=attr_navigation_short;
1193
1194         ret->id_lo=priv->itm->dest_count;
1195         dbg(1,"type=%d\n", ret->type);
1196         return ret;
1197 }
1198
1199 static struct item *
1200 navigation_map_get_item_byid(struct map_rect_priv *priv, int id_hi, int id_lo)
1201 {
1202         struct item *ret;
1203         navigation_map_rect_init(priv);
1204         while ((ret=navigation_map_get_item(priv))) {
1205                 if (ret->id_hi == id_hi && ret->id_lo == id_lo)
1206                         return ret;
1207         }
1208         return NULL;
1209 }
1210
1211 static struct map_methods navigation_map_meth = {
1212         projection_mg,
1213         "utf-8",
1214         navigation_map_destroy,
1215         navigation_map_rect_new,
1216         navigation_map_rect_destroy,
1217         navigation_map_get_item,
1218         navigation_map_get_item_byid,
1219         NULL,
1220         NULL,
1221         NULL,
1222 };
1223
1224 static struct map_priv *
1225 navigation_map_new(struct map_methods *meth, struct attr **attrs)
1226 {
1227         struct map_priv *ret;
1228         struct attr *navigation_attr;
1229
1230         navigation_attr=attr_search(attrs, NULL, attr_navigation);
1231         if (! navigation_attr)
1232                 return NULL;
1233         ret=g_new0(struct map_priv, 1);
1234         *meth=navigation_map_meth;
1235         ret->navigation=navigation_attr->u.navigation;
1236
1237         return ret;
1238 }
1239
1240
1241 void
1242 navigation_init(void)
1243 {
1244         plugin_register_map_type("navigation", navigation_map_new);
1245 }