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