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