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