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

   1 /**
   2  * Navit, a modular navigation system.
   3  * Copyright (C) 2005-2008 Navit Team
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * version 2 as published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the
  16  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA  02110-1301, USA.
  18  */
  19
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <math.h>
  24 #include <glib.h>
  25 #include "debug.h"
  26 #include "profile.h"
  27 #include "navigation.h"
  28 #include "coord.h"
  29 #include "item.h"
  30 #include "route.h"
  31 #include "transform.h"
  32 #include "mapset.h"
  33 #include "projection.h"
  34 #include "map.h"
  35 #include "navit.h"
  36 #include "callback.h"
  37 #include "plugin.h"
  38 #include "navit_nls.h"
  39
  40 struct suffix {
  41         char *fullname;
  42         char *abbrev;
  43         int sex;
  44 } suffixes[]= {
  45         {"weg",NULL,1},
  46         {"platz","pl.",1},
  47         {"ring",NULL,1},
  48         {"allee",NULL,2},
  49         {"gasse",NULL,2},
  50         {"straße","str.",2},
  51         {"strasse",NULL,2},
  52 };
  53
  54 struct navigation {
  55         struct map *map;
  56         struct item_hash *hash;
  57         struct navigation_itm *first;
  58         struct navigation_itm *last;
  59         struct navigation_command *cmd_first;
  60         struct navigation_command *cmd_last;
  61         struct callback_list *callback_speech;
  62         struct callback_list *callback;
  63         int level_last;
  64         struct item item_last;
  65         int turn_around;
  66         int turn_around_limit;
  67         int distance_turn;
  68         int distance_last;
  69         int announce[route_item_last-route_item_first+1][3];
  70 };
  71
  72
  73 struct navigation_command {
  74         struct navigation_itm *itm;
  75         struct navigation_command *next;
  76         int delta;
  77 };
  78
  79 /**
  80  * @brief Calculates the delta between two angles
  81  * @param angle1 The first angle
  82  * @param angle2 The second angle
  83  * @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
  84  */
  85
  86 static int
  87 angle_delta(int angle1, int angle2)
  88 {
  89         int delta=angle2-angle1;
  90         if (delta <= -180)
  91                 delta+=360;
  92         if (delta > 180)
  93                 delta-=360;
  94         return delta;
  95 }
  96
  97 struct navigation *
  98 navigation_new(struct attr **attrs)
  99 {
 100         int i,j;
 101         struct navigation *ret=g_new0(struct navigation, 1);
 102         ret->hash=item_hash_new();
 103         ret->callback=callback_list_new();
 104         ret->callback_speech=callback_list_new();
 105         ret->level_last=-2;
 106         ret->distance_last=-2;
 107         ret->distance_turn=50;
 108         ret->turn_around_limit=3;
 109
 110         for (j = 0 ; j <= route_item_last-route_item_first ; j++) {
 111                 for (i = 0 ; i < 3 ; i++) {
 112                         ret->announce[j][i]=-1;
 113                 }
 114         }
 115
 116         return ret;
 117 }
 118
 119 int
 120 navigation_set_announce(struct navigation *this_, enum item_type type, int *level)
 121 {
 122         int i;
 123         if (type < route_item_first || type > route_item_last) {
 124                 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
 125                 return 0;
 126         }
 127         for (i = 0 ; i < 3 ; i++)
 128                 this_->announce[type-route_item_first][i]=level[i];
 129         return 1;
 130 }
 131
 132 static int
 133 navigation_get_announce_level(struct navigation *this_, enum item_type type, int dist)
 134 {
 135         int i;
 136
 137         if (type < route_item_first || type > route_item_last)
 138                 return -1;
 139         for (i = 0 ; i < 3 ; i++) {
 140                 if (dist <= this_->announce[type-route_item_first][i])
 141                         return i;
 142         }
 143         return i;
 144 }
 145
 146 /**
 147  * @brief Holds a way that one could possibly drive from a navigation item
 148  */
 149 struct navigation_way {
 150         struct navigation_way *next;            /**< Pointer to a linked-list of all navigation_ways from this navigation item */
 151         short dir;                      /**< The direction -1 or 1 of the way */
 152         short angle2;                   /**< The angle one has to steer to drive from the old item to this street */
 153         int flags;                      /**< The flags of the way */
 154         struct item item;               /**< The item of the way */
 155 };
 156
 157 struct navigation_itm {
 158         char *name1;
 159         char *name2;
 160         struct item item;
 161         int direction;
 162         int angle_start;
 163         int angle_end;
 164         struct coord start,end;
 165         int time;
 166         int length;
 167         int dest_time;
 168         int dest_length;
 169         int told;
 170         int dest_count;
 171         struct navigation_itm *next;
 172         struct navigation_itm *prev;
 173         struct navigation_way *ways;            /**< Pointer to all ways one could drive from here */
 174 };
 175
 176 /* 0=N,90=E */
 177 static int
 178 road_angle(struct coord *c1, struct coord *c2, int dir)
 179 {
 180         int ret=transform_get_angle_delta(c1, c2, dir);
 181         dbg(1, "road_angle(0x%x,0x%x - 0x%x,0x%x)=%d\n", c1->x, c1->y, c2->x, c2->y, ret);
 182         return ret;
 183 }
 184
 185 static int
 186 round_distance(int dist)
 187 {
 188         if (dist < 100) {
 189                 dist=(dist+5)/10;
 190                 return dist*10;
 191         }
 192         if (dist < 250) {
 193                 dist=(dist+13)/25;
 194                 return dist*25;
 195         }
 196         if (dist < 500) {
 197                 dist=(dist+25)/50;
 198                 return dist*50;
 199         }
 200         if (dist < 1000) {
 201                 dist=(dist+50)/100;
 202                 return dist*100;
 203         }
 204         if (dist < 5000) {
 205                 dist=(dist+50)/100;
 206                 return dist*100;
 207         }
 208         if (dist < 100000) {
 209                 dist=(dist+500)/1000;
 210                 return dist*1000;
 211         }
 212         dist=(dist+5000)/10000;
 213         return dist*10000;
 214 }
 215
 216 static char *
 217 get_distance(int dist, enum attr_type type, int is_length)
 218 {
 219         if (type == attr_navigation_long) {
 220                 if (is_length)
 221                         return g_strdup_printf(_("%d m"), dist);
 222                 else
 223                         return g_strdup_printf(_("in %d m"), dist);
 224         }
 225         if (dist < 1000) {
 226                 if (is_length)
 227                         return g_strdup_printf(_("%d meters"), dist);
 228                 else
 229                         return g_strdup_printf(_("in %d meters"), dist);
 230         }
 231         if (dist < 5000) {
 232                 int rem=(dist/100)%10;
 233                 if (rem) {
 234                         if (is_length)
 235                                 return g_strdup_printf(_("%d.%d kilometer"), dist/1000, rem);
 236                         else
 237                                 return g_strdup_printf(_("in %d.%d kilometers"), dist/1000, rem);
 238                 }
 239         }
 240         if (is_length)
 241                 return g_strdup_printf(ngettext("one kilometer","%d kilometers", dist/1000), dist/1000);
 242         else
 243                 return g_strdup_printf(ngettext("in one kilometer","in %d kilometers", dist/1000), dist/1000);
 244 }
 245
 246
 247 /**
 248  * @brief This calculates the angle with which an item starts or ends
 249  *
 250  * This function can be used to get the angle an item (from a route graph map)
 251  * starts or ends with. Note that the angle will point towards the inner of
 252  * the item.
 253  *
 254  * This is meant to be used with items from a route graph map
 255  * With other items this will probably not be optimal...
 256  *
 257  * @param w The way which should be calculated
 258  */
 259 static void
 260 calculate_angle(struct navigation_way *w)
 261 {
 262         struct coord cbuf[2];
 263         struct item *ritem; // the "real" item
 264         struct coord c;
 265         struct map_rect *mr;
 266         struct attr attr;
 267
 268         w->angle2=361;
 269         mr = map_rect_new(w->item.map, NULL);
 270         if (!mr)
 271                 return;
 272
 273         ritem = map_rect_get_item_byid(mr, w->item.id_hi, w->item.id_lo);
 274         if (!ritem) {
 275                 dbg(1,"Item from segment not found on map!\n");
 276                 map_rect_destroy(mr);
 277                 return;
 278         }
 279
 280         if (ritem->type < type_line || ritem->type >= type_area) {
 281                 map_rect_destroy(mr);
 282                 return;
 283         }
 284         if (item_attr_get(ritem, attr_flags, &attr))
 285                 w->flags=attr.u.num;
 286         else
 287                 w->flags=0;
 288
 289         if (w->dir < 0) {
 290                 if (item_coord_get(ritem, cbuf, 2) != 2) {
 291                         dbg(1,"Using calculate_angle() with a less-than-two-coords-item?\n");
 292                         map_rect_destroy(mr);
 293                         return;
 294                 }
 295
 296                 while (item_coord_get(ritem, &c, 1)) {
 297                         cbuf[0] = cbuf[1];
 298                         cbuf[1] = c;
 299                 }
 300
 301         } else {
 302                 if (item_coord_get(ritem, cbuf, 2) != 2) {
 303                         dbg(1,"Using calculate_angle() with a less-than-two-coords-item?\n");
 304                         map_rect_destroy(mr);
 305                         return;
 306                 }
 307                 c = cbuf[0];
 308                 cbuf[0] = cbuf[1];
 309                 cbuf[1] = c;
 310         }
 311
 312         map_rect_destroy(mr);
 313
 314         w->angle2=road_angle(&cbuf[1],&cbuf[0],0);
 315 }
 316
 317 /**
 318  * @brief Clears the ways one can drive from itm
 319  *
 320  * @param itm The item that should have its ways cleared
 321  */
 322 static void
 323 navigation_itm_ways_clear(struct navigation_itm *itm)
 324 {
 325         struct navigation_way *c,*n;
 326
 327         c = itm->ways;
 328         while (c) {
 329                 n = c->next;
 330                 g_free(c);
 331                 c = n;
 332         }
 333
 334         itm->ways = NULL;
 335 }
 336
 337 /**
 338  * @brief Updates the ways one can drive from itm
 339  *
 340  * This updates the list of possible ways to drive to from itm. The item "itm" is on
 341  * and the next navigation item are excluded.
 342  *
 343  * @param itm The item that should be updated
 344  * @param graph_map The route graph's map that these items are on
 345  */
 346 static void
 347 navigation_itm_ways_update(struct navigation_itm *itm, struct map *graph_map)
 348 {
 349         struct map_selection coord_sel;
 350         struct map_rect *g_rect; // Contains a map rectangle from the route graph's map
 351         struct item *i,*sitem;
 352         struct attr sitem_attr,direction_attr;
 353         struct navigation_way *w,*l;
 354
 355         navigation_itm_ways_clear(itm);
 356
 357         // These values cause the code in route.c to get us only the route graph point and connected segments
 358         coord_sel.next = NULL;
 359         coord_sel.u.c_rect.lu = itm->start;
 360         coord_sel.u.c_rect.rl = itm->start;
 361         // the selection's order is ignored
 362
 363         g_rect = map_rect_new(graph_map, &coord_sel);
 364
 365         i = map_rect_get_item(g_rect);
 366         if (!i || i->type != type_rg_point) { // probably offroad?
 367                 return ;
 368         }
 369
 370         w = NULL;
 371
 372         while (1) {
 373                 i = map_rect_get_item(g_rect);
 374
 375                 if (!i) {
 376                         break;
 377                 }
 378
 379                 if (i->type != type_rg_segment) {
 380                         continue;
 381                 }
 382
 383                 if (!item_attr_get(i,attr_street_item,&sitem_attr)) {
 384                         dbg(1, "Got no street item for route graph item in entering_straight()\n");
 385                         continue;
 386                 }
 387
 388                 if (!item_attr_get(i,attr_direction,&direction_attr)) {
 389                         continue;
 390                 }
 391
 392                 sitem = sitem_attr.u.item;
 393                 if (item_is_equal(itm->item,*sitem) || ((itm->prev) && item_is_equal(itm->prev->item,*sitem))) {
 394                         continue;
 395                 }
 396
 397                 l = w;
 398                 w = g_new(struct navigation_way, 1);
 399                 w->dir = direction_attr.u.num;
 400                 w->item = *sitem;
 401                 w->next = l;
 402                 calculate_angle(w);
 403         }
 404
 405         map_rect_destroy(g_rect);
 406
 407         itm->ways = w;
 408 }
 409
 410 static void
 411 navigation_destroy_itms_cmds(struct navigation *this_, struct navigation_itm *end)
 412 {
 413         struct navigation_itm *itm;
 414         struct navigation_command *cmd;
 415         dbg(2,"enter this_=%p this_->first=%p this_->cmd_first=%p end=%p\n", this_, this_->first, this_->cmd_first, end);
 416         if (this_->cmd_first)
 417                 dbg(2,"this_->cmd_first->itm=%p\n", this_->cmd_first->itm);
 418         while (this_->first && this_->first != end) {
 419                 itm=this_->first;
 420                 dbg(3,"destroying %p\n", itm);
 421                 item_hash_remove(this_->hash, &itm->item);
 422                 this_->first=itm->next;
 423                 if (this_->first)
 424                         this_->first->prev=NULL;
 425                 if (this_->cmd_first && this_->cmd_first->itm == itm->next) {
 426                         cmd=this_->cmd_first;
 427                         this_->cmd_first=cmd->next;
 428                         g_free(cmd);
 429                 }
 430                 map_convert_free(itm->name1);
 431                 map_convert_free(itm->name2);
 432                 navigation_itm_ways_clear(itm);
 433                 g_free(itm);
 434         }
 435         if (! this_->first)
 436                 this_->last=NULL;
 437         if (! this_->first && end)
 438                 dbg(0,"end wrong\n");
 439         dbg(2,"ret this_->first=%p this_->cmd_first=%p\n",this_->first, this_->cmd_first);
 440 }
 441
 442 static void
 443 navigation_itm_update(struct navigation_itm *itm, struct item *ritem)
 444 {
 445         struct attr length, time;
 446         if (! item_attr_get(ritem, attr_length, &length)) {
 447                 dbg(0,"no length\n");
 448                 return;
 449         }
 450         if (! item_attr_get(ritem, attr_time, &time)) {
 451                 dbg(0,"no time\n");
 452                 return;
 453         }
 454
 455         dbg(1,"length=%d time=%d\n", length.u.num, time.u.num);
 456         itm->length=length.u.num;
 457         itm->time=time.u.num;
 458 }
 459
 460 static struct navigation_itm *
 461 navigation_itm_new(struct navigation *this_, struct item *ritem)
 462 {
 463         struct navigation_itm *ret=g_new0(struct navigation_itm, 1);
 464         int i=0;
 465         struct item *sitem;
 466         struct map *graph_map = NULL;
 467         struct attr street_item,direction,route_attr;
 468         struct map_rect *mr;
 469         struct attr attr;
 470         struct coord c[5];
 471
 472         if (ritem) {
 473                 ret->told=0;
 474                 if (! item_attr_get(ritem, attr_street_item, &street_item)) {
 475                         dbg(0,"no street item\n");
 476                         return NULL;
 477                 }
 478                 if (item_attr_get(ritem, attr_direction, &direction))
 479                         ret->direction=direction.u.num;
 480                 else
 481                         ret->direction=0;
 482
 483                 item_attr_get(ritem, attr_route, &route_attr);
 484                 graph_map = route_get_graph_map(route_attr.u.route);
 485
 486                 sitem=street_item.u.item;
 487                 ret->item=*sitem;
 488                 item_hash_insert(this_->hash, sitem, ret);
 489                 mr=map_rect_new(sitem->map, NULL);
 490                 sitem=map_rect_get_item_byid(mr, sitem->id_hi, sitem->id_lo);
 491                 if (item_attr_get(sitem, attr_street_name, &attr))
 492                         ret->name1=map_convert_string(sitem->map,attr.u.str);
 493                 if (item_attr_get(sitem, attr_street_name_systematic, &attr))
 494                         ret->name2=map_convert_string(sitem->map,attr.u.str);
 495                 navigation_itm_update(ret, ritem);
 496
 497                 while (item_coord_get(ritem, &c[i], 1)) {
 498                         dbg(1, "coord %d 0x%x 0x%x\n", i, c[i].x ,c[i].y);
 499
 500                         if (i < 4)
 501                                 i++;
 502                         else {
 503                                 c[2]=c[3];
 504                                 c[3]=c[4];
 505                         }
 506                 }
 507                 dbg(1,"count=%d\n", i);
 508                 i--;
 509
 510                 ret->angle_start=road_angle(&c[0], &c[1], 0);
 511                 ret->angle_end=road_angle(&c[i-1], &c[i], 0);
 512
 513                 ret->start=c[0];
 514                 ret->end=c[i];
 515                 dbg(1,"i=%d start %d end %d '%s' '%s'\n", i, ret->angle_start, ret->angle_end, ret->name1, ret->name2);
 516                 map_rect_destroy(mr);
 517         } else {
 518                 if (this_->last)
 519                         ret->start=ret->end=this_->last->end;
 520         }
 521         if (! this_->first)
 522                 this_->first=ret;
 523         if (this_->last) {
 524                 this_->last->next=ret;
 525                 ret->prev=this_->last;
 526                 if (graph_map) {
 527                         navigation_itm_ways_update(ret,graph_map);
 528                 }
 529         }
 530         dbg(1,"ret=%p\n", ret);
 531         this_->last=ret;
 532         return ret;
 533 }
 534
 535 /**
 536  * @brief Calculates distance and time to the destination
 537  *
 538  * This function calculates the distance and the time to the destination of a
 539  * navigation. If incr is set, this is only calculated for the first navigation
 540  * item, which is a lot faster than re-calculation the whole destination, but works
 541  * only if the rest of the navigation already has been calculated.
 542  *
 543  * @param this_ The navigation whose destination / time should be calculated
 544  * @param incr Set this to true to only calculate the first item. See description.
 545  */
 546 static void
 547 calculate_dest_distance(struct navigation *this_, int incr)
 548 {
 549         int len=0, time=0, count=0;
 550         struct navigation_itm *next,*itm=this_->last;
 551         dbg(1, "enter this_=%p, incr=%d\n", this_, incr);
 552         if (incr) {
 553                 if (itm)
 554                         dbg(2, "old values: (%p) time=%d lenght=%d\n", itm, itm->dest_length, itm->dest_time);
 555                 else
 556                         dbg(2, "old values: itm is null\n");
 557                 itm=this_->first;
 558                 next=itm->next;
 559                 dbg(2, "itm values: time=%d lenght=%d\n", itm->length, itm->time);
 560                 dbg(2, "next values: (%p) time=%d lenght=%d\n", next, next->dest_length, next->dest_time);
 561                 itm->dest_length=next->dest_length+itm->length;
 562                 itm->dest_count=next->dest_count+1;
 563                 itm->dest_time=next->dest_time+itm->time;
 564                 dbg(2, "new values: time=%d lenght=%d\n", itm->dest_length, itm->dest_time);
 565                 return;
 566         }
 567         while (itm) {
 568                 len+=itm->length;
 569                 time+=itm->time;
 570                 itm->dest_length=len;
 571                 itm->dest_time=time;
 572                 itm->dest_count=count++;
 573                 itm=itm->prev;
 574         }
 575         dbg(1,"len %d time %d\n", len, time);
 576 }
 577
 578 /**
 579  * @brief Checks if two navigation items are on the same street
 580  *
 581  * This function checks if two navigation items are on the same street. It returns
 582  * true if either their name or their "systematic name" (e.g. "A6" or "B256") are the
 583  * same.
 584  *
 585  * @param old The first item to be checked
 586  * @param new The second item to be checked
 587  * @return True if both old and new are on the same street
 588  */
 589 static int
 590 is_same_street2(struct navigation_itm *old, struct navigation_itm *new)
 591 {
 592         if (old->name1 && new->name1 && !strcmp(old->name1, new->name1)) {
 593                 dbg(1,"is_same_street: '%s' '%s' vs '%s' '%s' yes (1.)\n", old->name2, new->name2, old->name1, new->name1);
 594                 return 1;
 595         }
 596         if (old->name2 && new->name2 && !strcmp(old->name2, new->name2)) {
 597                 dbg(1,"is_same_street: '%s' '%s' vs '%s' '%s' yes (2.)\n", old->name2, new->name2, old->name1, new->name1);
 598                 return 1;
 599         }
 600         dbg(1,"is_same_street: '%s' '%s' vs '%s' '%s' no\n", old->name2, new->name2, old->name1, new->name1);
 601         return 0;
 602 }
 603
 604 /**
 605  * @brief Checks if two navigation items are on the same street
 606  *
 607  * This function checks if two navigation items are on the same street. It returns
 608  * true if the first part of their "systematic name" is equal. If the "systematic name" is
 609  * for example "A352/E3" (a german highway which at the same time is part of the international
 610  * E-road network), it would only search for "A352" in the second item's systematic name.
 611  *
 612  * @param old The first item to be checked
 613  * @param new The second item to be checked
 614  * @return True if the "systematic name" of both items matches. See description.
 615  */
 616 static int
 617 is_same_street_systematic(struct navigation_itm *old, struct navigation_itm *new)
 618 {
 619         int slashold,slashnew;
 620         if (!old->name2 || !new->name2)
 621                 return 1;
 622         slashold=strcspn(old->name2, "/");
 623         slashnew=strcspn(new->name2, "/");
 624         if (slashold != slashnew || strncmp(old->name2, new->name2, slashold))
 625                 return 0;
 626         return 1;
 627 }
 628
 629
 630 /**
 631  * @brief Check if there are multiple possibilities to drive from old
 632  *
 633  * This function checks, if there are multiple streets connected to the exit of "old".
 634  * Sometimes it happens that an item on a map is just segmented, without any other streets
 635  * being connected there, and it is not useful if navit creates a maneuver there.
 636  *
 637  * @param new The navigation item we're driving to
 638  * @return True if there are multiple streets
 639  */
 640 static int
 641 check_multiple_streets(struct navigation_itm *new)
 642 {
 643         if (new->ways) {
 644                 return 1;
 645         } else {
 646                 return 0;
 647         }
 648 }
 649
 650 /**
 651  * @brief Check if the new item is entered "straight"
 652  *
 653  * This function checks if the new item is entered "straight" from the old item, i.e. if there
 654  * is no other street one could take from the old item on with less steering.
 655  *
 656  * @param new The navigation item we're driving to
 657  * @param diff The absolute angle one needs to steer to drive to this item
 658  * @return True if the new item is entered "straight"
 659  */
 660 static int
 661 entering_straight(struct navigation_itm *new, int diff)
 662 {
 663         int curr_diff;
 664         struct navigation_way *w;
 665
 666         w = new->ways;
 667         dbg(1,"diff=%d\n", diff);
 668         while (w) {
 669                 curr_diff=abs(angle_delta(new->prev->angle_end, w->angle2));
 670                 dbg(1,"curr_diff=%d\n", curr_diff);
 671                 if (curr_diff < diff) {
 672                         return 0;
 673                 }
 674                 w = w->next;
 675         }
 676         return 1;
 677 }
 678
 679 /**
 680  * @brief Checks if navit has to create a maneuver to drive from old to new
 681  *
 682  * This function checks if it has to create a "maneuver" - i.e. guide the user - to drive
 683  * from "old" to "new".
 684  *
 685  * @param old The old navigation item, where we're coming from
 686  * @param new The new navigation item, where we're going to
 687  * @param delta The angle the user has to steer to navigate from old to new
 688  * @param reason A text string explaining how the return value resulted
 689  * @return True if navit should guide the user, false otherwise
 690  */
 691 static int
 692 maneuver_required2(struct navigation_itm *old, struct navigation_itm *new, int *delta, char **reason)
 693 {
 694         int straight_limit=20,ext_straight_limit=45;
 695
 696         dbg(1,"enter %p %p %p\n",old, new, delta);
 697         *delta=angle_delta(old->angle_end, new->angle_start);
 698
 699         if (new->item.type == old->item.type || (new->item.type != type_ramp && old->item.type != type_ramp)) {
 700                 if (is_same_street2(old, new)) {
 701                         if (! entering_straight(new, abs(*delta))) {
 702                                 dbg(1, "maneuver_required: Not driving straight: yes\n");
 703                                 if (reason)
 704                                         *reason="yes: Not driving straight";
 705                                 return 1;
 706                         }
 707
 708                         if (check_multiple_streets(new)) {
 709                                 if (entering_straight(new,abs(*delta)*2)) {
 710                                         if (reason)
 711                                                 *reason="no: delta < ext_limit for same name";
 712                                         return 0;
 713                                 }
 714                                 if (reason)
 715                                         *reason="yes: delta > ext_limit for same name";
 716                                 return 1;
 717                         } else {
 718                                 dbg(1, "maneuver_required: Staying on the same street: no\n");
 719                                 if (reason)
 720                                         *reason="no: Staying on same street";
 721                                 return 0;
 722                         }
 723                 }
 724         } else
 725                 dbg(1, "maneuver_required: old or new is ramp\n");
 726 #if 0
 727         if (old->item.type == type_ramp && (new->item.type == type_highway_city || new->item.type == type_highway_land)) {
 728                 dbg(1, "no_maneuver_required: old is ramp new is highway\n");
 729                 if (reason)
 730                         *reason="no: old is ramp new is highway";
 731                 return 0;
 732         }
 733 #endif
 734 #if 0
 735         if (old->crossings_end == 2) {
 736                 dbg(1, "maneuver_required: only 2 connections: no\n");
 737                 return 0;
 738         }
 739 #endif
 740         dbg(1,"delta=%d-%d=%d\n", new->angle_start, old->angle_end, *delta);
 741         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))) {
 742                 dbg(1, "maneuver_required: highway changed name\n");
 743                 if (reason)
 744                         *reason="yes: highway changed name";
 745                 return 1;
 746         }
 747         if (abs(*delta) < straight_limit) {
 748                 if (! entering_straight(new,abs(*delta))) {
 749                         if (reason)
 750                                 *reason="yes: not straight";
 751                         dbg(1, "maneuver_required: not driving straight: yes\n");
 752                         return 1;
 753                 }
 754
 755                 dbg(1, "maneuver_required: delta(%d) < %d: no\n", *delta, straight_limit);
 756                 if (reason)
 757                         *reason="no: delta < limit";
 758                 return 0;
 759         }
 760         if (abs(*delta) < ext_straight_limit) {
 761                 if (entering_straight(new,abs(*delta)*2)) {
 762                         if (reason)
 763                                 *reason="no: delta < ext_limit";
 764                         return 0;
 765                 }
 766         }
 767
 768         if (! check_multiple_streets(new)) {
 769                 dbg(1, "maneuver_required: only one possibility: no\n");
 770                 if (reason)
 771                         *reason="no: only one possibility";
 772                 return 0;
 773         }
 774
 775         dbg(1, "maneuver_required: delta=%d: yes\n", *delta);
 776         if (reason)
 777                 *reason="yes: delta >= limit";
 778         return 1;
 779 }
 780
 781 static struct navigation_command *
 782 command_new(struct navigation *this_, struct navigation_itm *itm, int delta)
 783 {
 784         struct navigation_command *ret=g_new0(struct navigation_command, 1);
 785         dbg(1,"enter this_=%p itm=%p delta=%d\n", this_, itm, delta);
 786         ret->delta=delta;
 787         ret->itm=itm;
 788         if (this_->cmd_last)
 789                 this_->cmd_last->next=ret;
 790         this_->cmd_last=ret;
 791
 792         if (!this_->cmd_first)
 793                 this_->cmd_first=ret;
 794         return ret;
 795 }
 796
 797 static void
 798 make_maneuvers(struct navigation *this_, struct route *route)
 799 {
 800         struct navigation_itm *itm, *last=NULL, *last_itm=NULL;
 801         int delta;
 802         itm=this_->first;
 803         this_->cmd_last=NULL;
 804         this_->cmd_first=NULL;
 805         while (itm) {
 806                 if (last) {
 807                         if (maneuver_required2(last_itm, itm,&delta,NULL)) {
 808                                 command_new(this_, itm, delta);
 809                         }
 810                 } else
 811                         last=itm;
 812                 last_itm=itm;
 813                 itm=itm->next;
 814         }
 815 }
 816
 817 static int
 818 contains_suffix(char *name, char *suffix)
 819 {
 820         if (!suffix)
 821                 return 0;
 822         if (strlen(name) < strlen(suffix))
 823                 return 0;
 824         return !strcasecmp(name+strlen(name)-strlen(suffix), suffix);
 825 }
 826
 827 static char *
 828 replace_suffix(char *name, char *search, char *replace)
 829 {
 830         int len=strlen(name)-strlen(search);
 831         char *ret=g_malloc(len+strlen(replace)+1);
 832         strncpy(ret, name, len);
 833         strcpy(ret+len, replace);
 834
 835         return ret;
 836 }
 837
 838 static char *
 839 navigation_item_destination(struct navigation_itm *itm, struct navigation_itm *next, char *prefix)
 840 {
 841         char *ret=NULL,*name1,*sep,*name2;
 842         int i,sex;
 843         if (! prefix)
 844                 prefix="";
 845         if(!itm->name1 && !itm->name2 && itm->item.type == type_ramp) {
 846                 dbg(1,">> Next is ramp %lx current is %lx \n", itm->item.type, next->item.type);
 847
 848                 if(next->item.type == type_ramp)
 849                         return NULL;
 850                 if(itm->item.type == type_highway_city || itm->item.type == type_highway_land )
 851                         return g_strdup_printf("%s%s",prefix,_("exit"));        /* %FIXME Can this even be reached? */
 852                 else
 853                         return g_strdup_printf("%s%s",prefix,_("ramp"));
 854
 855         }
 856         if (!itm->name1 && !itm->name2)
 857                 return NULL;
 858         if (itm->name1) {
 859                 sex=-1;
 860                 name1=NULL;
 861                 for (i = 0 ; i < sizeof(suffixes)/sizeof(suffixes[0]) ; i++) {
 862                         if (contains_suffix(itm->name1,suffixes[i].fullname)) {
 863                                 sex=suffixes[i].sex;
 864                                 name1=g_strdup(itm->name1);
 865                                 break;
 866                         }
 867                         if (contains_suffix(itm->name1,suffixes[i].abbrev)) {
 868                                 sex=suffixes[i].sex;
 869                                 name1=replace_suffix(itm->name1, suffixes[i].abbrev, suffixes[i].fullname);
 870                                 break;
 871                         }
 872                 }
 873                 if (itm->name2) {
 874                         name2=itm->name2;
 875                         sep=" ";
 876                 } else {
 877                         name2="";
 878                         sep="";
 879                 }
 880                 switch (sex) {
 881                 case -1:
 882                         /* TRANSLATORS: Arguments: 1: Prefix (Space if required) 2: Street Name 3: Separator (Space if required), 4: Systematic Street Name */
 883                         ret=g_strdup_printf(_("%sinto the street %s%s%s"),prefix,itm->name1, sep, name2);
 884                         break;
 885                 case 1:
 886                         /* 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 */
 887                         ret=g_strdup_printf(_("%sinto the %s%s%s|male form"),prefix,name1, sep, name2);
 888                         break;
 889                 case 2:
 890                         /* 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 */
 891                         ret=g_strdup_printf(_("%sinto the %s%s%s|female form"),prefix,name1, sep, name2);
 892                         break;
 893                 case 3:
 894                         /* 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 */
 895                         ret=g_strdup_printf(_("%sinto the %s%s%s|neutral form"),prefix,name1, sep, name2);
 896                         break;
 897                 }
 898                 g_free(name1);
 899
 900         } else
 901                 /* TRANSLATORS: gives the name of the next road to turn into (into the E17) */
 902                 ret=g_strdup_printf(_("into the %s"),itm->name2);
 903         name1=ret;
 904         while (*name1) {
 905                 switch (*name1) {
 906                 case '|':
 907                         *name1='\0';
 908                         break;
 909                 case '/':
 910                         *name1++=' ';
 911                         break;
 912                 default:
 913                         name1++;
 914                 }
 915         }
 916         return ret;
 917 }
 918
 919 static char *
 920 show_maneuver(struct navigation *nav, struct navigation_itm *itm, struct navigation_command *cmd, enum attr_type type)
 921 {
 922         /* TRANSLATORS: right, as in 'Turn right' */
 923         char *dir=_("right"),*strength="";
 924         int distance=itm->dest_length-cmd->itm->dest_length;
 925         char *d,*ret;
 926         int delta=cmd->delta;
 927         int level;
 928         int strength_needed;
 929         struct navigation_way *w;
 930
 931         w = itm->next->ways;
 932         strength_needed = 0;
 933         if ((itm->next->angle_start - itm->angle_end) < 0) {
 934                 while (w) {
 935                         if (w->angle2-itm->next->angle_start < 0) {
 936                                 strength_needed = 1;
 937                                 break;
 938                         }
 939                         w = w->next;
 940                 }
 941         } else {
 942                 while (w) {
 943                         if (w->angle2-itm->next->angle_start > 0) {
 944                                 strength_needed = 1;
 945                                 break;
 946                         }
 947                         w = w->next;
 948                 }
 949         }
 950
 951         level=1;
 952         if (delta < 0) {
 953                 /* TRANSLATORS: left, as in 'Turn left' */
 954                 dir=_("left");
 955                 delta=-delta;
 956         }
 957
 958         if (strength_needed) {
 959                 if (delta < 45) {
 960                         /* TRANSLATORS: Don't forget the ending space */
 961                         strength=_("easily ");
 962                 } else if (delta < 105) {
 963                         strength="";
 964                 } else if (delta < 165) {
 965                         /* TRANSLATORS: Don't forget the ending space */
 966                         strength=_("strongly ");
 967                 } else {
 968                         dbg(1,"delta=%d\n", delta);
 969                         /* TRANSLATORS: Don't forget the ending space */
 970                         strength=_("unknown ");
 971                 }
 972         }
 973         if (type != attr_navigation_long_exact)
 974                 distance=round_distance(distance);
 975         if (type == attr_navigation_speech) {
 976                 if (nav->turn_around && nav->turn_around == nav->turn_around_limit)
 977                         return g_strdup(_("When possible, please turn around"));
 978                 level=navigation_get_announce_level(nav, itm->item.type, distance);
 979                 dbg(1,"distance=%d level=%d type=0x%x\n", distance, level, itm->item.type);
 980         }
 981         switch(level) {
 982         case 3:
 983                 d=get_distance(distance, type, 1);
 984                 ret=g_strdup_printf(_("Follow the road for the next %s"), d);
 985                 g_free(d);
 986                 return ret;
 987         case 2:
 988                 d=g_strdup(_("soon"));
 989                 break;
 990         case 1:
 991                 d=get_distance(distance, type, 0);
 992                 break;
 993         case 0:
 994                 d=g_strdup(_("now"));
 995                 break;
 996         default:
 997                 d=g_strdup(_("error"));
 998         }
 999         if (cmd->itm->next) {
1000                 int tellstreetname = 0;
1001                 char *destination = NULL;
1002
1003                 if(type == attr_navigation_speech) { // In voice mode
1004                         // In Voice Mode only tell the street name in level 1 or in level 0 if level 1
1005                         // was skipped
1006
1007                         if (level == 1) { // we are close to the intersection
1008                                 cmd->itm->told = 1; // remeber to be checked when we turn
1009                                 tellstreetname = 1; // Ok so we tell the name of the street
1010                         }
1011
1012                         if (level == 0) {
1013                                 if(cmd->itm->told == 0) // we are right at the intersection
1014                                         tellstreetname = 1;
1015                                 else
1016                                         cmd->itm->told = 0;  // reset just in case we come to the same street again
1017                         }
1018
1019                 }
1020                 else
1021                      tellstreetname = 1;
1022
1023                 if(tellstreetname)
1024                         destination=navigation_item_destination(cmd->itm, itm, " ");
1025                 /* 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' */
1026                 ret=g_strdup_printf(_("Turn %1$s%2$s %3$s%4$s"), strength, dir, d, destination ? destination:"");
1027                 g_free(destination);
1028         } else
1029                 ret=g_strdup_printf(_("You have reached your destination %s"), d);
1030         g_free(d);
1031         return ret;
1032 }
1033
1034 static void
1035 navigation_call_callbacks(struct navigation *this_, int force_speech)
1036 {
1037         int distance, level = 0;
1038         void *p=this_;
1039         if (!this_->cmd_first)
1040                 return;
1041         callback_list_call(this_->callback, 1, &p);
1042         dbg(1,"force_speech=%d turn_around=%d turn_around_limit=%d\n", force_speech, this_->turn_around, this_->turn_around_limit);
1043         distance=round_distance(this_->first->dest_length-this_->cmd_first->itm->dest_length);
1044         if (this_->turn_around_limit && this_->turn_around == this_->turn_around_limit) {
1045                 dbg(1,"distance=%d distance_turn=%d\n", distance, this_->distance_turn);
1046                 while (distance > this_->distance_turn) {
1047                         this_->level_last=4;
1048                         level=4;
1049                         force_speech=1;
1050                         if (this_->distance_turn >= 500)
1051                                 this_->distance_turn*=2;
1052                         else
1053                                 this_->distance_turn=500;
1054                 }
1055         } else if (!this_->turn_around_limit || this_->turn_around == -this_->turn_around_limit+1) {
1056                 this_->distance_turn=50;
1057                 level=navigation_get_announce_level(this_, this_->first->item.type, distance);
1058                 if (level < this_->level_last) {
1059                         dbg(1,"level %d < %d\n", level, this_->level_last);
1060                         this_->level_last=level;
1061                         force_speech=1;
1062                 }
1063                 if (!item_is_equal(this_->cmd_first->itm->item, this_->item_last)) {
1064                         dbg(1,"item different\n");
1065                         this_->item_last=this_->cmd_first->itm->item;
1066                         force_speech=1;
1067                 }
1068         }
1069         if (force_speech) {
1070                 this_->level_last=level;
1071                 dbg(1,"distance=%d level=%d type=0x%x\n", distance, level, this_->first->item.type);
1072                 callback_list_call(this_->callback_speech, 1, &p);
1073         }
1074 }
1075
1076 void
1077 navigation_update(struct navigation *this_, struct route *route)
1078 {
1079         struct map *map;
1080         struct map_rect *mr;
1081         struct item *ritem;                     /* Holds an item from the route map */
1082         struct item *sitem;                     /* Holds the corresponding item from the actual map */
1083         struct attr street_item,street_direction;
1084         struct navigation_itm *itm;
1085         int incr=0,first=1;
1086
1087         if (! route)
1088                 return;
1089         map=route_get_map(route);
1090         if (! map)
1091                 return;
1092         mr=map_rect_new(map, NULL);
1093         if (! mr)
1094                 return;
1095         dbg(1,"enter\n");
1096         while ((ritem=map_rect_get_item(mr))) {
1097                 if (first && item_attr_get(ritem, attr_street_item, &street_item)) {
1098                         first=0;
1099                         if (!item_attr_get(ritem, attr_direction, &street_direction))
1100                                 street_direction.u.num=0;
1101                         sitem=street_item.u.item;
1102                         dbg(1,"sitem=%p\n", sitem);
1103                         itm=item_hash_lookup(this_->hash, sitem);
1104                         dbg(2,"itm for item with id (0x%x,0x%x) is %p\n", sitem->id_hi, sitem->id_lo, itm);
1105                         if (itm && itm->direction != street_direction.u.num) {
1106                                 dbg(2,"wrong direction\n");
1107                                 itm=NULL;
1108                         }
1109                         navigation_destroy_itms_cmds(this_, itm);
1110                         if (itm) {
1111                                 navigation_itm_update(itm, ritem);
1112                                 break;
1113                         }
1114                         dbg(1,"not on track\n");
1115                 }
1116                 navigation_itm_new(this_, ritem);
1117         }
1118         if (first)
1119                 navigation_destroy_itms_cmds(this_, NULL);
1120         else {
1121                 if (! ritem) {
1122                         navigation_itm_new(this_, NULL);
1123                         make_maneuvers(this_,route);
1124                 }
1125                 calculate_dest_distance(this_, incr);
1126                 dbg(2,"destination distance old=%d new=%d\n", this_->distance_last, this_->first->dest_length);
1127                 if (this_->first->dest_length > this_->distance_last && this_->distance_last >= 0)
1128                         this_->turn_around++;
1129                 else
1130                         this_->turn_around--;
1131                 if (this_->turn_around > this_->turn_around_limit)
1132                         this_->turn_around=this_->turn_around_limit;
1133                 else if (this_->turn_around < -this_->turn_around_limit+1)
1134                         this_->turn_around=-this_->turn_around_limit+1;
1135                 dbg(2,"turn_around=%d\n", this_->turn_around);
1136                 this_->distance_last=this_->first->dest_length;
1137                 profile(0,"end");
1138                 navigation_call_callbacks(this_, FALSE);
1139         }
1140         map_rect_destroy(mr);
1141 }
1142
1143 void
1144 navigation_flush(struct navigation *this_)
1145 {
1146         navigation_destroy_itms_cmds(this_, NULL);
1147 }
1148
1149
1150 void
1151 navigation_destroy(struct navigation *this_)
1152 {
1153         navigation_flush(this_);
1154         item_hash_destroy(this_->hash);
1155         callback_list_destroy(this_->callback);
1156         callback_list_destroy(this_->callback_speech);
1157         g_free(this_);
1158 }
1159
1160 int
1161 navigation_register_callback(struct navigation *this_, enum attr_type type, struct callback *cb)
1162 {
1163         if (type == attr_navigation_speech)
1164                 callback_list_add(this_->callback_speech, cb);
1165         else
1166                 callback_list_add(this_->callback, cb);
1167         return 1;
1168 }
1169
1170 void
1171 navigation_unregister_callback(struct navigation *this_, enum attr_type type, struct callback *cb)
1172 {
1173         if (type == attr_navigation_speech)
1174                 callback_list_remove_destroy(this_->callback_speech, cb);
1175         else
1176                 callback_list_remove_destroy(this_->callback, cb);
1177 }
1178
1179 struct map *
1180 navigation_get_map(struct navigation *this_)
1181 {
1182         if (! this_->map)
1183                 this_->map=map_new(NULL, (struct attr*[]){
1184                         &(struct attr){attr_type,{"navigation"}},
1185                         &(struct attr){attr_navigation,.u.navigation=this_},
1186                         &(struct attr){attr_data,{""}},
1187                         &(struct attr){attr_description,{"Navigation"}},
1188                         NULL});
1189         return this_->map;
1190 }
1191
1192 struct map_priv {
1193         struct navigation *navigation;
1194 };
1195
1196 struct map_rect_priv {
1197         struct navigation *nav;
1198         struct navigation_command *cmd;
1199         struct navigation_command *cmd_next;
1200         struct navigation_itm *itm;
1201         struct navigation_itm *itm_next;
1202         struct navigation_itm *cmd_itm;
1203         struct navigation_itm *cmd_itm_next;
1204         struct item item;
1205         enum attr_type attr_next;
1206         int ccount;
1207         int debug_idx;
1208         struct navigation_way *ways;
1209         int show_all;
1210         char *str;
1211 };
1212
1213 static int
1214 navigation_map_item_coord_get(void *priv_data, struct coord *c, int count)
1215 {
1216         struct map_rect_priv *this=priv_data;
1217         if (this->ccount || ! count)
1218                 return 0;
1219         *c=this->itm->start;
1220         this->ccount=1;
1221         return 1;
1222 }
1223
1224 static int
1225 navigation_map_item_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1226 {
1227         struct map_rect_priv *this_=priv_data;
1228         attr->type=attr_type;
1229         struct navigation_command *cmd=this_->cmd;
1230         struct navigation_itm *itm=this_->itm;
1231         struct navigation_itm *prev=itm->prev;
1232
1233         if (this_->str) {
1234                 g_free(this_->str);
1235                 this_->str=NULL;
1236         }
1237
1238         if (cmd) {
1239                 if (cmd->itm != itm)
1240                         cmd=NULL;
1241         }
1242         switch(attr_type) {
1243         case attr_navigation_short:
1244                 this_->attr_next=attr_navigation_long;
1245                 if (cmd) {
1246                         this_->str=attr->u.str=show_maneuver(this_->nav, this_->cmd_itm, cmd, attr_type);
1247                         return 1;
1248                 }
1249                 return 0;
1250         case attr_navigation_long:
1251                 this_->attr_next=attr_navigation_long_exact;
1252                 if (cmd) {
1253                         this_->str=attr->u.str=show_maneuver(this_->nav, this_->cmd_itm, cmd, attr_type);
1254                         return 1;
1255                 }
1256                 return 0;
1257         case attr_navigation_long_exact:
1258                 this_->attr_next=attr_navigation_speech;
1259                 if (cmd) {
1260                         this_->str=attr->u.str=show_maneuver(this_->nav, this_->cmd_itm, cmd, attr_type);
1261                         return 1;
1262                 }
1263                 return 0;
1264         case attr_navigation_speech:
1265                 this_->attr_next=attr_length;
1266                 if (cmd) {
1267                         this_->str=attr->u.str=show_maneuver(this_->nav, this_->cmd_itm, this_->cmd, attr_type);
1268                         return 1;
1269                 }
1270                 return 0;
1271         case attr_length:
1272                 this_->attr_next=attr_time;
1273                 if (cmd) {
1274                         attr->u.num=this_->cmd_itm->dest_length-cmd->itm->dest_length;
1275                         return 1;
1276                 }
1277                 return 0;
1278         case attr_time:
1279                 this_->attr_next=attr_destination_length;
1280                 if (cmd) {
1281                         attr->u.num=this_->cmd_itm->dest_time-cmd->itm->dest_time;
1282                         return 1;
1283                 }
1284                 return 0;
1285         case attr_destination_length:
1286                 attr->u.num=itm->dest_length;
1287                 this_->attr_next=attr_destination_time;
1288                 return 1;
1289         case attr_destination_time:
1290                 attr->u.num=itm->dest_time;
1291                 this_->attr_next=attr_street_name;
1292                 return 1;
1293         case attr_street_name:
1294                 attr->u.str=itm->name1;
1295                 this_->attr_next=attr_street_name_systematic;
1296                 if (attr->u.str)
1297                         return 1;
1298         case attr_street_name_systematic:
1299                 attr->u.str=itm->name2;
1300                 this_->attr_next=attr_debug;
1301                 if (attr->u.str)
1302                         return 1;
1303         case attr_debug:
1304                 switch(this_->debug_idx) {
1305                 case 0:
1306                         this_->debug_idx++;
1307                         this_->str=attr->u.str=g_strdup_printf("angle:%d (- %d)", itm->angle_start, itm->angle_end);
1308                         return 1;
1309                 case 1:
1310                         this_->debug_idx++;
1311                         this_->str=attr->u.str=g_strdup_printf("item type:%s", item_to_name(itm->item.type));
1312                         return 1;
1313                 case 2:
1314                         this_->debug_idx++;
1315                         if (cmd) {
1316                                 this_->str=attr->u.str=g_strdup_printf("delta:%d", cmd->delta);
1317                                 return 1;
1318                         }
1319                 case 3:
1320                         this_->debug_idx++;
1321                         if (prev) {
1322                                 this_->str=attr->u.str=g_strdup_printf("prev street_name:%s", prev->name1);
1323                                 return 1;
1324                         }
1325                 case 4:
1326                         this_->debug_idx++;
1327                         if (prev) {
1328                                 this_->str=attr->u.str=g_strdup_printf("prev street_name_systematic:%s", prev->name2);
1329                                 return 1;
1330                         }
1331                 case 5:
1332                         this_->debug_idx++;
1333                         if (prev) {
1334                                 this_->str=attr->u.str=g_strdup_printf("prev angle:(%d -) %d", prev->angle_start, prev->angle_end);
1335                                 return 1;
1336                         }
1337                 case 6:
1338                         this_->debug_idx++;
1339                         this_->ways=itm->ways;
1340                         if (prev) {
1341                                 this_->str=attr->u.str=g_strdup_printf("prev item type:%s", item_to_name(prev->item.type));
1342                                 return 1;
1343                         }
1344                 case 7:
1345                         if (this_->ways && prev) {
1346                                 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);
1347                                 this_->ways=this_->ways->next;
1348                                 return 1;
1349                         }
1350                         this_->debug_idx++;
1351                 case 8:
1352                         this_->debug_idx++;
1353                         if (prev) {
1354                                 int delta=0;
1355                                 char *reason=NULL;
1356                                 maneuver_required2(prev, itm, &delta, &reason);
1357                                 this_->str=attr->u.str=g_strdup_printf("reason:%s",reason);
1358                                 return 1;
1359                         }
1360
1361                 default:
1362                         this_->attr_next=attr_none;
1363                         return 0;
1364                 }
1365         case attr_any:
1366                 while (this_->attr_next != attr_none) {
1367                         if (navigation_map_item_attr_get(priv_data, this_->attr_next, attr))
1368                                 return 1;
1369                 }
1370                 return 0;
1371         default:
1372                 attr->type=attr_none;
1373                 return 0;
1374         }
1375 }
1376
1377 static struct item_methods navigation_map_item_methods = {
1378         NULL,
1379         navigation_map_item_coord_get,
1380         NULL,
1381         navigation_map_item_attr_get,
1382 };
1383
1384
1385 static void
1386 navigation_map_destroy(struct map_priv *priv)
1387 {
1388         g_free(priv);
1389 }
1390
1391 static void
1392 navigation_map_rect_init(struct map_rect_priv *priv)
1393 {
1394         priv->cmd_next=priv->nav->cmd_first;
1395         priv->cmd_itm_next=priv->itm_next=priv->nav->first;
1396 }
1397
1398 static struct map_rect_priv *
1399 navigation_map_rect_new(struct map_priv *priv, struct map_selection *sel)
1400 {
1401         struct navigation *nav=priv->navigation;
1402         struct map_rect_priv *ret=g_new0(struct map_rect_priv, 1);
1403         ret->nav=nav;
1404         navigation_map_rect_init(ret);
1405         ret->item.meth=&navigation_map_item_methods;
1406         ret->item.priv_data=ret;
1407 #if 0
1408         ret->show_all=1;
1409 #endif
1410         return ret;
1411 }
1412
1413 static void
1414 navigation_map_rect_destroy(struct map_rect_priv *priv)
1415 {
1416         g_free(priv);
1417 }
1418
1419 static struct item *
1420 navigation_map_get_item(struct map_rect_priv *priv)
1421 {
1422         struct item *ret=&priv->item;
1423         int delta;
1424         if (!priv->itm_next)
1425                 return NULL;
1426         priv->itm=priv->itm_next;
1427         priv->cmd=priv->cmd_next;
1428         priv->cmd_itm=priv->cmd_itm_next;
1429         if (!priv->cmd)
1430                 return NULL;
1431         if (!priv->show_all && priv->itm->prev != NULL)
1432                 priv->itm=priv->cmd->itm;
1433         priv->itm_next=priv->itm->next;
1434         if (priv->itm->prev)
1435                 ret->type=type_nav_none;
1436         else
1437                 ret->type=type_nav_position;
1438         if (priv->cmd->itm == priv->itm) {
1439                 priv->cmd_itm_next=priv->cmd->itm;
1440                 priv->cmd_next=priv->cmd->next;
1441                 if (priv->cmd_itm_next && !priv->cmd_itm_next->next)
1442                         ret->type=type_nav_destination;
1443                 else {
1444                         delta=priv->cmd->delta;
1445                         if (delta < 0) {
1446                                 delta=-delta;
1447                                 if (delta < 45)
1448                                         ret->type=type_nav_left_1;
1449                                 else if (delta < 105)
1450                                         ret->type=type_nav_left_2;
1451                                 else if (delta < 165)
1452                                         ret->type=type_nav_left_3;
1453                                 else
1454                                         ret->type=type_none;
1455                         } else {
1456                                 if (delta < 45)
1457                                         ret->type=type_nav_right_1;
1458                                 else if (delta < 105)
1459                                         ret->type=type_nav_right_2;
1460                                 else if (delta < 165)
1461                                         ret->type=type_nav_right_3;
1462                                 else
1463                                         ret->type=type_none;
1464                         }
1465                 }
1466         }
1467         priv->ccount=0;
1468         priv->debug_idx=0;
1469         priv->attr_next=attr_navigation_short;
1470
1471         ret->id_lo=priv->itm->dest_count;
1472         dbg(1,"type=%d\n", ret->type);
1473         return ret;
1474 }
1475
1476 static struct item *
1477 navigation_map_get_item_byid(struct map_rect_priv *priv, int id_hi, int id_lo)
1478 {
1479         struct item *ret;
1480         navigation_map_rect_init(priv);
1481         while ((ret=navigation_map_get_item(priv))) {
1482                 if (ret->id_hi == id_hi && ret->id_lo == id_lo)
1483                         return ret;
1484         }
1485         return NULL;
1486 }
1487
1488 static struct map_methods navigation_map_meth = {
1489         projection_mg,
1490         "utf-8",
1491         navigation_map_destroy,
1492         navigation_map_rect_new,
1493         navigation_map_rect_destroy,
1494         navigation_map_get_item,
1495         navigation_map_get_item_byid,
1496         NULL,
1497         NULL,
1498         NULL,
1499 };
1500
1501 static struct map_priv *
1502 navigation_map_new(struct map_methods *meth, struct attr **attrs)
1503 {
1504         struct map_priv *ret;
1505         struct attr *navigation_attr;
1506
1507         navigation_attr=attr_search(attrs, NULL, attr_navigation);
1508         if (! navigation_attr)
1509                 return NULL;
1510         ret=g_new0(struct map_priv, 1);
1511         *meth=navigation_map_meth;
1512         ret->navigation=navigation_attr->u.navigation;
1513
1514         return ret;
1515 }
1516
1517
1518 void
1519 navigation_init(void)
1520 {
1521         plugin_register_map_type("navigation", navigation_map_new);
1522 }