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

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