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