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

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