vcs.maemo.org Git - navit-package/blob - src/route.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #if 0
   4 #include <math.h>
   5 #include <assert.h>
   6 #include <unistd.h>
   7 #include <sys/time.h>
   8 #endif
   9 #include <glib.h>
  10 #include "config.h"
  11 #include "debug.h"
  12 #include "profile.h"
  13 #include "coord.h"
  14 #include "projection.h"
  15 #include "map.h"
  16 #include "mapset.h"
  17 #include "item.h"
  18 #include "route.h"
  19 #include "track.h"
  20 #include "point.h"
  21 #include "graphics.h"
  22 #include "transform.h"
  23 #include "fib.h"
  24
  25 #if 0
  26 static int speed_list[]={
  27         10, /* street_0 */
  28         10, /* street_1_city */
  29         30, /* street_2_city */
  30         40, /* street_3_city */
  31         50, /* street_4_city */
  32         80, /* highway_city */
  33         60, /* street_1_land */
  34         65, /* street_2_land */
  35         70, /* street_3_land */
  36         80, /* street_4_land */
  37         120, /* street_n_lanes */
  38         120, /* highway_land */
  39         40, /* ramp */
  40         30, /* ferry */
  41 };
  42 #endif
  43
  44 int debug_route=0;
  45
  46
  47 struct route_graph_point {
  48         struct route_graph_point *next;
  49         struct route_graph_point *hash_next;
  50         struct route_graph_segment *start;
  51         struct route_graph_segment *end;
  52         struct route_graph_segment *seg;
  53         struct fibheap_el *el;
  54         int value;
  55         struct coord c;
  56 };
  57
  58
  59 struct route_graph_segment {
  60         struct route_graph_segment *next;
  61         struct route_graph_segment *start_next;
  62         struct route_graph_segment *end_next;
  63         struct route_graph_point *start;
  64         struct route_graph_point *end;
  65         struct item item;
  66         int limit;
  67         int len;
  68 };
  69
  70 struct route_path_segment {
  71         struct item item;
  72         int time;
  73         int length;
  74         struct coord c[2];
  75         struct route_path_segment *next;
  76 };
  77
  78 struct route_info {
  79         struct coord c;
  80         struct coord lp;
  81         int pos;
  82
  83         int dist;
  84         int dir;
  85
  86         struct street_data *street;
  87 };
  88
  89 struct route_path {
  90         struct route_path_segment *path;
  91         struct route_path_segment *path_last;
  92         struct item_hash *path_hash;
  93 };
  94
  95
  96 struct route {
  97         int version;
  98         struct mapset *ms;
  99         struct route_info *pos;
 100         struct route_info *dst;
 101
 102         struct route_graph *graph;
 103         struct route_path *path2;
 104         int speedlist[route_item_last-route_item_first+1];
 105 };
 106
 107 struct route_graph {
 108         struct route_graph_point *route_points;
 109         struct route_graph_segment *route_segments;
 110 #define HASH_SIZE 8192
 111         struct route_graph_point *hash[HASH_SIZE];
 112 };
 113
 114 static struct route_info * route_find_nearest_street(struct mapset *ms, struct coord *c);
 115 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
 116 static void route_graph_update(struct route *this);
 117 static struct route_path *route_path_new(struct route_graph *this, struct route_info *pos, struct route_info *dst, int *speedlist);
 118 static void route_process_street_graph(struct route_graph *this, struct item *item);
 119 static void route_graph_destroy(struct route_graph *this);
 120 static void route_path_update(struct route *this);
 121
 122 static void
 123 route_path_destroy(struct route_path *this)
 124 {
 125         struct route_path_segment *c,*n;
 126         if (! this)
 127                 return;
 128         if (this->path_hash) {
 129                 item_hash_destroy(this->path_hash);
 130                 this->path_hash=NULL;
 131         }
 132         c=this->path;
 133         while (c) {
 134                 n=c->next;
 135                 g_free(c);
 136                 c=n;
 137         }
 138         g_free(this);
 139 }
 140
 141 struct route *
 142 route_new(struct mapset *ms)
 143 {
 144         struct route *this=g_new0(struct route, 1);
 145         this->ms=ms;
 146         return this;
 147 }
 148
 149 void
 150 route_set_mapset(struct route *this, struct mapset *ms)
 151 {
 152         this->ms=ms;
 153 }
 154
 155 struct mapset *
 156 route_get_mapset(struct route *this)
 157 {
 158         return this->ms;
 159 }
 160
 161 struct route_info *
 162 route_get_pos(struct route *this)
 163 {
 164         return this->pos;
 165 }
 166
 167 struct route_info *
 168 route_get_dst(struct route *this)
 169 {
 170         return this->dst;
 171 }
 172
 173 int *
 174 route_get_speedlist(struct route *this)
 175 {
 176         return this->speedlist;
 177 }
 178
 179 int
 180 route_set_speed(struct route *this, enum item_type type, int value)
 181 {
 182         if (type < route_item_first || type > route_item_last) {
 183                 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
 184                 return 0;
 185         }
 186         this->speedlist[type-route_item_first]=value;
 187         return 1;
 188 }
 189
 190 int
 191 route_contains(struct route *this, struct item *item)
 192 {
 193         if (! this->path2 || !this->path2->path_hash || !item_hash_lookup(this->path2->path_hash, item))
 194                 return 0;
 195         return 1;
 196 }
 197
 198 static void
 199 route_path_update(struct route *this)
 200 {
 201         route_path_destroy(this->path2);
 202         if (! this->pos || ! this->dst)
 203                 return;
 204         if (! this->graph || !(this->path2=route_path_new(this->graph, this->pos, this->dst, this->speedlist))) {
 205                 profile(0,NULL);
 206                 route_graph_update(this);
 207                 this->path2=route_path_new(this->graph, this->pos, this->dst, this->speedlist);
 208                 profile(1,"route_path_new");
 209                 profile(0,"end");
 210         }
 211 }
 212
 213 void
 214 route_set_position(struct route *this, struct coord *pos)
 215 {
 216         if (this->pos)
 217                 route_info_free(this->pos);
 218         this->pos=route_find_nearest_street(this->ms, pos);
 219         dbg(1,"this->pos=%p\n", this->pos);
 220         if (! this->pos)
 221                 return;
 222         if (this->dst)
 223                 route_path_update(this);
 224 }
 225
 226 void
 227 route_set_position_from_tracking(struct route *this, struct tracking *tracking)
 228 {
 229         struct coord *c;
 230         struct route_info *ret;
 231
 232         dbg(2,"enter\n");
 233         c=tracking_get_pos(tracking);
 234         ret=g_new0(struct route_info, 1);
 235         if (this->pos)
 236                 route_info_free(this->pos);
 237         ret->c=*c;
 238         ret->lp=*c;
 239         ret->pos=tracking_get_segment_pos(tracking);
 240         ret->dist=0;
 241         ret->dir=0;
 242         ret->street=street_data_dup(tracking_get_street_data(tracking));
 243         dbg(3,"c->x=0x%x, c->y=0x%x pos=%d item=(0x%x,0x%x)\n", c->x, c->y, ret->pos, ret->street->item.id_hi, ret->street->item.id_lo);
 244         dbg(3,"street 0=(0x%x,0x%x) %d=(0x%x,0x%x)\n", ret->street->c[0].x, ret->street->c[0].y, ret->street->count-1, ret->street->c[ret->street->count-1].x, ret->street->c[ret->street->count-1].y);
 245         this->pos=ret;
 246         if (this->dst)
 247                 route_path_update(this);
 248         dbg(2,"ret\n");
 249 }
 250
 251 struct map_selection *route_selection;
 252
 253 struct map_selection *
 254 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
 255 {
 256         int dx,dy,sx=1,sy=1,d,m;
 257         struct map_selection *sel=g_new(struct map_selection, 1);
 258         sel->order[layer_town]=0;
 259         sel->order[layer_poly]=0;
 260         sel->order[layer_street]=order;
 261         dbg(1,"%p %p\n", c1, c2);
 262         dx=c1->x-c2->x;
 263         dy=c1->y-c2->y;
 264         if (dx < 0) {
 265                 sx=-1;
 266                 sel->rect.lu.x=c1->x;
 267                 sel->rect.rl.x=c2->x;
 268         } else {
 269                 sel->rect.lu.x=c2->x;
 270                 sel->rect.rl.x=c1->x;
 271         }
 272         if (dy < 0) {
 273                 sy=-1;
 274                 sel->rect.lu.y=c2->y;
 275                 sel->rect.rl.y=c1->y;
 276         } else {
 277                 sel->rect.lu.y=c1->y;
 278                 sel->rect.rl.y=c2->y;
 279         }
 280         if (dx*sx > dy*sy)
 281                 d=dx*sx;
 282         else
 283                 d=dy*sy;
 284         m=d*rel/100+abs;
 285         sel->rect.lu.x-=m;
 286         sel->rect.rl.x+=m;
 287         sel->rect.lu.y+=m;
 288         sel->rect.rl.y-=m;
 289         sel->next=NULL;
 290         return sel;
 291 }
 292
 293 static struct map_selection *
 294 route_calc_selection(struct coord *c1, struct coord *c2)
 295 {
 296         struct map_selection *ret,*sel;
 297         sel=route_rect(4, c1, c2, 25, 0);
 298         ret=sel;
 299         sel->next=route_rect(8, c1, c1, 0, 40000);
 300         sel=sel->next;
 301         sel->next=route_rect(18, c1, c1, 0, 10000);
 302         sel=sel->next;
 303         sel->next=route_rect(8, c2, c2, 0, 40000);
 304         sel=sel->next;
 305         sel->next=route_rect(18, c2, c2, 0, 10000);
 306         /* route_selection=ret; */
 307         return ret;
 308 }
 309
 310 static void
 311 route_free_selection(struct map_selection *sel)
 312 {
 313         struct map_selection *next;
 314         while (sel) {
 315                 next=sel->next;
 316                 g_free(sel);
 317                 sel=next;
 318         }
 319 }
 320
 321
 322
 323 void
 324 route_set_destination(struct route *this, struct coord *dst)
 325 {
 326         profile(0,NULL);
 327         if (this->dst)
 328                 route_info_free(this->dst);
 329         this->dst=NULL;
 330         if (dst)
 331                 this->dst=route_find_nearest_street(this->ms, dst);
 332         profile(1,"find_nearest_street");
 333
 334         route_graph_destroy(this->graph);
 335         this->graph=NULL;
 336         route_path_update(this);
 337         profile(0,"end");
 338 }
 339
 340 static struct route_graph_point *
 341 route_graph_get_point(struct route_graph *this, struct coord *c)
 342 {
 343         struct route_graph_point *p=this->route_points;
 344         int hashval=(c->x +  c->y) & (HASH_SIZE-1);
 345         p=this->hash[hashval];
 346         while (p) {
 347                 if (p->c.x == c->x && p->c.y == c->y)
 348                         return p;
 349                 p=p->hash_next;
 350         }
 351         return NULL;
 352 }
 353
 354
 355 static struct route_graph_point *
 356 route_graph_add_point(struct route_graph *this, struct coord *f)
 357 {
 358         int hashval;
 359         struct route_graph_point *p;
 360
 361         p=route_graph_get_point(this,f);
 362         if (!p) {
 363                 hashval=(f->x +  f->y) & (HASH_SIZE-1);
 364                 if (debug_route)
 365                         printf("p (0x%x,0x%x)\n", f->x, f->y);
 366                 p=g_new(struct route_graph_point,1);
 367                 p->hash_next=this->hash[hashval];
 368                 this->hash[hashval]=p;
 369                 p->next=this->route_points;
 370                 p->el=NULL;
 371                 p->start=NULL;
 372                 p->end=NULL;
 373                 p->seg=NULL;
 374                 p->value=INT_MAX;
 375                 p->c=*f;
 376                 this->route_points=p;
 377         }
 378         return p;
 379 }
 380
 381
 382 static void
 383 route_graph_free_points(struct route_graph *this)
 384 {
 385         struct route_graph_point *curr,*next;
 386         curr=this->route_points;
 387         while (curr) {
 388                 next=curr->next;
 389                 g_free(curr);
 390                 curr=next;
 391         }
 392         this->route_points=NULL;
 393         memset(this->hash, 0, sizeof(this->hash));
 394 }
 395
 396 static void
 397 route_graph_add_segment(struct route_graph *this, struct route_graph_point *start, struct route_graph_point *end, int len, struct item *item, int limit)
 398 {
 399         struct route_graph_segment *s;
 400         s=g_new0(struct route_graph_segment,1);
 401         s->start=start;
 402         s->start_next=start->start;
 403         start->start=s;
 404         s->end=end;
 405         s->end_next=end->end;
 406         end->end=s;
 407         g_assert(len >= 0);
 408         s->len=len;
 409         s->item=*item;
 410         s->limit=limit;
 411         s->next=this->route_segments;
 412         this->route_segments=s;
 413         if (debug_route)
 414                 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
 415
 416 }
 417
 418 static void
 419 route_path_add_item(struct route_path *this, struct item *itm, struct coord *start, struct coord *end, int len, int time)
 420 {
 421         struct route_path_segment *segment=g_new0(struct route_path_segment,1);
 422         item_hash_insert(this->path_hash,  itm, (void *)1);
 423         segment->item=*itm;
 424         segment->next=NULL;
 425         segment->length=len;
 426         segment->time=time;
 427         if (start)
 428                 segment->c[0]=*start;
 429         if (end)
 430                 segment->c[1]=*end;
 431         if (!this->path)
 432                 this->path=segment;
 433         if (this->path_last)
 434                 this->path_last->next=segment;
 435         this->path_last=segment;
 436 }
 437
 438
 439 struct route_path_handle {
 440         struct route_path_segment *s;
 441 };
 442
 443 struct route_path_handle *
 444 route_path_open(struct route *this)
 445 {
 446         struct route_path_handle *ret=g_new(struct route_path_handle, 1);
 447
 448         ret->s=this->path2->path;
 449         return ret;
 450 }
 451
 452 struct route_path_segment *
 453 route_path_get_segment(struct route_path_handle *h)
 454 {
 455         struct route_path_segment *ret=h->s;
 456
 457         if (ret)
 458                 h->s=ret->next;
 459
 460         return ret;
 461 }
 462
 463 struct coord *
 464 route_path_segment_get_start(struct route_path_segment *s)
 465 {
 466         return &s->c[0];
 467 }
 468
 469 struct coord *
 470 route_path_segment_get_end(struct route_path_segment *s)
 471 {
 472         return &s->c[1];
 473 }
 474
 475 struct item *
 476 route_path_segment_get_item(struct route_path_segment *s)
 477 {
 478         return &s->item;
 479 }
 480
 481 int
 482 route_path_segment_get_length(struct route_path_segment *s)
 483 {
 484         return s->length;
 485 }
 486
 487 int
 488 route_path_segment_get_time(struct route_path_segment *s)
 489 {
 490         return s->time;
 491 }
 492
 493 void
 494 route_path_close(struct route_path_handle *h)
 495 {
 496         g_free(h);
 497 }
 498
 499
 500 static void
 501 route_graph_free_segments(struct route_graph *this)
 502 {
 503         struct route_graph_segment *curr,*next;
 504         curr=this->route_segments;
 505         while (curr) {
 506                 next=curr->next;
 507                 g_free(curr);
 508                 curr=next;
 509         }
 510         this->route_segments=NULL;
 511 }
 512
 513 static void
 514 route_graph_destroy(struct route_graph *this)
 515 {
 516         if (this) {
 517                 route_graph_free_points(this);
 518                 route_graph_free_segments(this);
 519                 g_free(this);
 520         }
 521 }
 522
 523 int
 524 route_time(int *speedlist, struct item *item, int len)
 525 {
 526         if (item->type < route_item_first || item->type > route_item_last) {
 527                 dbg(0,"street type %d out of range [%d,%d]", item->type, route_item_first, route_item_last);
 528                 return len*36;
 529         }
 530         return len*36/speedlist[item->type-route_item_first];
 531 }
 532
 533
 534 static int
 535 route_value(int *speedlist, struct item *item, int len)
 536 {
 537         int ret;
 538         if (len < 0) {
 539                 printf("len=%d\n", len);
 540         }
 541         g_assert(len >= 0);
 542         ret=route_time(speedlist, item, len);
 543         dbg(1, "route_value(0x%x, %d)=%d\n", item->type, len, ret);
 544         return ret;
 545 }
 546
 547 static void
 548 route_process_street_graph(struct route_graph *this, struct item *item)
 549 {
 550 #ifdef AVOID_FLOAT
 551         int len=0;
 552 #else
 553         double len=0;
 554 #endif
 555         struct route_graph_point *s_pnt,*e_pnt;
 556         struct coord c,l;
 557         struct attr attr;
 558
 559
 560         if (item_coord_get(item, &l, 1)) {
 561                 s_pnt=route_graph_add_point(this,&l);
 562                 while (item_coord_get(item, &c, 1)) {
 563                         len+=transform_distance(&l, &c);
 564                         l=c;
 565                 }
 566                 e_pnt=route_graph_add_point(this,&l);
 567                 g_assert(len >= 0);
 568                 if (item_attr_get(item, attr_limit, &attr))
 569                         route_graph_add_segment(this, s_pnt, e_pnt, len, item, attr.u.num);
 570                 else
 571                         route_graph_add_segment(this, s_pnt, e_pnt, len, item, 0);
 572         }
 573 }
 574
 575 static int
 576 compare(void *v1, void *v2)
 577 {
 578         struct route_graph_point *p1=v1;
 579         struct route_graph_point *p2=v2;
 580 #if 0
 581         if (debug_route)
 582                 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
 583 #endif
 584         return p1->value-p2->value;
 585 }
 586
 587 int
 588 route_info_length(struct route_info *pos, struct route_info *dst, int dir)
 589 {
 590         struct route_info_handle *h;
 591         struct coord *c,*l;
 592         int ret=0;
 593
 594         dbg(2,"enter pos=%p dst=%p dir=%d\n", pos, dst, dir);
 595         h=route_info_open(pos, dst, dir);
 596         if (! h) {
 597                 dbg(2,"ret=-1\n");
 598                 return -1;
 599         }
 600         l=route_info_get(h);
 601         while ((c=route_info_get(h))) {
 602                 dbg(3,"c=%p\n", c);
 603                 ret+=transform_distance(c, l);
 604                 l=c;
 605         }
 606         dbg(2,"ret=%d\n", ret);
 607         return ret;
 608 }
 609
 610 static void
 611 route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist)
 612 {
 613         struct route_graph_point *p_min,*end=NULL;
 614         struct route_graph_segment *s;
 615         int min,new,old,val;
 616         struct fibheap *heap;
 617         struct street_data *sd=dst->street;
 618
 619         heap = fh_makeheap();
 620         fh_setcmp(heap, compare);
 621
 622         if (! (sd->limit & 2)) {
 623                 end=route_graph_get_point(this, &sd->c[0]);
 624                 g_assert(end != 0);
 625                 end->value=route_value(speedlist, &sd->item, route_info_length(NULL, dst, -1));
 626                 end->el=fh_insert(heap, end);
 627         }
 628
 629         if (! (sd->limit & 1)) {
 630                 end=route_graph_get_point(this, &sd->c[sd->count-1]);
 631                 g_assert(end != 0);
 632                 end->value=route_value(speedlist, &sd->item, route_info_length(NULL, dst, 1));
 633                 end->el=fh_insert(heap, end);
 634         }
 635
 636         dbg(1,"0x%x,0x%x\n", end->c.x, end->c.y);
 637         for (;;) {
 638                 p_min=fh_extractmin(heap);
 639                 if (! p_min)
 640                         break;
 641                 min=p_min->value;
 642                 if (debug_route)
 643                         printf("extract p=%p free el=%p min=%d, 0x%x, 0x%x\n", p_min, p_min->el, min, p_min->c.x, p_min->c.y);
 644                 p_min->el=NULL;
 645                 s=p_min->start;
 646                 while (s) {
 647                         val=route_value(speedlist, &s->item, s->len);
 648 #if 0
 649                         val+=val*2*street_route_contained(s->str->segid);
 650 #endif
 651                         new=min+val;
 652                         if (debug_route)
 653                                 printf("begin %d len %d vs %d (0x%x,0x%x)\n",new,val,s->end->value, s->end->c.x, s->end->c.y);
 654                         if (new < s->end->value && !(s->limit & 1)) {
 655                                 s->end->value=new;
 656                                 s->end->seg=s;
 657                                 if (! s->end->el) {
 658                                         if (debug_route)
 659                                                 printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
 660                                         s->end->el=fh_insert(heap, s->end);
 661                                         if (debug_route)
 662                                                 printf("el new=%p\n", s->end->el);
 663                                 }
 664                                 else {
 665                                         if (debug_route)
 666                                                 printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
 667                                         fh_replacedata(heap, s->end->el, s->end);
 668                                 }
 669                         }
 670                         if (debug_route)
 671                                 printf("\n");
 672                         s=s->start_next;
 673                 }
 674                 s=p_min->end;
 675                 while (s) {
 676                         val=route_value(speedlist, &s->item, s->len);
 677                         new=min+val;
 678                         if (debug_route)
 679                                 printf("end %d len %d vs %d (0x%x,0x%x)\n",new,val,s->start->value,s->start->c.x, s->start->c.y);
 680                         if (new < s->start->value && !(s->limit & 2)) {
 681                                 old=s->start->value;
 682                                 s->start->value=new;
 683                                 s->start->seg=s;
 684                                 if (! s->start->el) {
 685                                         if (debug_route)
 686                                                 printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
 687                                         s->start->el=fh_insert(heap, s->start);
 688                                         if (debug_route)
 689                                                 printf("el new=%p\n", s->start->el);
 690                                 }
 691                                 else {
 692                                         if (debug_route)
 693                                                 printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
 694                                         fh_replacedata(heap, s->start->el, s->start);
 695                                 }
 696                         }
 697                         if (debug_route)
 698                                 printf("\n");
 699                         s=s->end_next;
 700                 }
 701         }
 702         fh_deleteheap(heap);
 703 }
 704
 705 static struct route_path *
 706 route_path_new(struct route_graph *this, struct route_info *pos, struct route_info *dst, int *speedlist)
 707 {
 708         struct route_graph_point *start1=NULL,*start2=NULL,*start;
 709         struct route_graph_segment *s=NULL;
 710         int len=0,segs=0;
 711         int ilen,seg_time,seg_len;
 712 #if 0
 713         int time=0,hr,min,sec
 714 #endif
 715         unsigned int val1=0xffffffff,val2=0xffffffff;
 716         struct street_data *sd=pos->street;
 717         struct route_path *ret;
 718
 719         if (! (sd->limit & 1)) {
 720                 start1=route_graph_get_point(this, &sd->c[0]);
 721                 if (! start1)
 722                         return NULL;
 723                 val1=start1->value+route_value(speedlist, &sd->item, route_info_length(pos, NULL, -1));
 724                 dbg(1,"start1: %d(route)+%d=%d\n", start1->value, val1-start1->value, val1);
 725         }
 726         if (! (sd->limit & 2)) {
 727                 start2=route_graph_get_point(this, &sd->c[sd->count-1]);
 728                 if (! start2)
 729                         return NULL;
 730                 val2=start2->value+route_value(speedlist, &sd->item, route_info_length(pos, NULL, 1));
 731                 dbg(1,"start2: %d(route)+%d=%d\n", start2->value, val2-start2->value, val2);
 732         }
 733         dbg(1,"val1=%d val2=%d\n", val1, val2);
 734         if (val1 == val2) {
 735                 val1=start1->start->start->value;
 736                 val2=start2->end->end->value;
 737         }
 738         if (start1 && (val1 < val2)) {
 739                 start=start1;
 740                 pos->dir=-1;
 741         } else {
 742                 if (start2) {
 743                         start=start2;
 744                         pos->dir=1;
 745                 } else {
 746                         printf("no route found, pos blocked\n");
 747                         return NULL;
 748                 }
 749         }
 750         ret=g_new0(struct route_path, 1);
 751         ret->path_hash=item_hash_new();
 752         dbg(1,"dir=%d\n", pos->dir);
 753         while ((s=start->seg)) {
 754                 segs++;
 755 #if 0
 756                 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
 757 #endif
 758                 seg_len=s->len;
 759                 seg_time=route_time(speedlist, &s->item, seg_len);
 760 #if 0
 761                 time+=seg_time;
 762 #endif
 763                 len+=seg_len;
 764                 if (s->start == start) {
 765                         route_path_add_item(ret, &s->item, &s->start->c, &s->end->c, seg_len, seg_time);
 766                         start=s->end;
 767                 } else {
 768                         route_path_add_item(ret, &s->item, &s->end->c, &s->start->c, seg_len, seg_time);
 769                         start=s->start;
 770                 }
 771         }
 772         sd=dst->street;
 773         dbg(1,"start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
 774         dbg(1,"dst sd->limit=%d sd->c[0]=0x%x,0x%x sd->c[sd->count-1]=0x%x,0x%x\n", sd->limit, sd->c[0].x,sd->c[0].y, sd->c[sd->count-1].x, sd->c[sd->count-1].y);
 775         if (start->c.x == sd->c[0].x && start->c.y == sd->c[0].y)
 776                 dst->dir=-1;
 777         else if (start->c.x == sd->c[sd->count-1].x && start->c.y == sd->c[sd->count-1].y)
 778                 dst->dir=1;
 779         else {
 780                 printf("no route found\n");
 781                 route_path_destroy(ret);
 782                 return NULL;
 783         }
 784         ilen=route_info_length(pos, NULL, 0);
 785 #if 0
 786         time+=route_time(&pos->street->item, ilen);
 787 #endif
 788         len+=ilen;
 789
 790         ilen=route_info_length(NULL, dst, 0);
 791 #if 0
 792         time+=route_time(&dst->street->item, ilen);
 793 #endif
 794         len+=ilen;
 795
 796         dbg(1, "%d segments\n", segs);
 797 #if 0
 798         dbg(1, "len %5.3f\n", len/1000.0);
 799         time/=10;
 800         sec=time;
 801         min=time/60;
 802         time-=min*60;
 803         hr=min/60;
 804         min-=hr*60;
 805         dbg(1, "time %02d:%02d:%02d (%d sec)\n", hr, min, time, sec);
 806         dbg(1, "speed %f km/h\n", len/sec*3.6);
 807 #endif
 808         return ret;
 809 }
 810
 811 static struct route_graph *
 812 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2)
 813 {
 814         struct route_graph *ret=g_new0(struct route_graph, 1);
 815         struct map_selection *sel;
 816         struct mapset_handle *h;
 817         struct map_rect *mr;
 818         struct map *m;
 819         struct item *item;
 820         struct coord e;
 821
 822         sel=route_calc_selection(c1, c2);
 823         h=mapset_open(ms);
 824         while ((m=mapset_next(h,1))) {
 825                 mr=map_rect_new(m, sel);
 826                 while ((item=map_rect_get_item(mr))) {
 827                         if (item->type >= type_street_0 && item->type <= type_ferry) {
 828                                 route_process_street_graph(ret, item);
 829                         } else
 830                                 while (item_coord_get(item, &e, 1));
 831                 }
 832                 map_rect_destroy(mr);
 833         }
 834         mapset_close(h);
 835         route_free_selection(sel);
 836
 837         return ret;
 838 }
 839
 840 static void
 841 route_graph_update(struct route *this)
 842 {
 843         route_graph_destroy(this->graph);
 844         profile(1,"graph_free");
 845         this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c);
 846         profile(1,"route_graph_build");
 847         route_graph_flood(this->graph, this->dst, this->speedlist);
 848         profile(1,"route_graph_flood");
 849         this->version++;
 850 }
 851
 852 struct street_data *
 853 street_get_data (struct item *item)
 854 {
 855         struct coord c[1000];
 856         int count=0;
 857         struct street_data *ret;
 858         struct attr attr;
 859
 860         while (count < 1000) {
 861                 if (!item_coord_get(item, &c[count], 1))
 862                         break;
 863                 count++;
 864         }
 865         g_assert(count < 1000);
 866         ret=g_malloc(sizeof(struct street_data)+count*sizeof(struct coord));
 867         ret->item=*item;
 868         ret->count=count;
 869         if (item_attr_get(item, attr_limit, &attr))
 870                 ret->limit=attr.u.num;
 871         else
 872                 ret->limit=0;
 873         memcpy(ret->c, c, count*sizeof(struct coord));
 874
 875         return ret;
 876
 877 }
 878
 879 struct street_data *
 880 street_data_dup(struct street_data *orig)
 881 {
 882         struct street_data *ret;
 883         int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
 884
 885         ret=g_malloc(size);
 886         memcpy(ret, orig, size);
 887
 888         return ret;
 889 }
 890
 891 void
 892 street_data_free(struct street_data *sd)
 893 {
 894         g_free(sd);
 895 }
 896
 897 static struct route_info *
 898 route_find_nearest_street(struct mapset *ms, struct coord *c)
 899 {
 900         struct route_info *ret=NULL;
 901         int max_dist=1000;
 902         struct map_selection *sel=route_rect(18, c, c, 0, max_dist);
 903         int dist,pos;
 904         struct mapset_handle *h;
 905         struct map *m;
 906         struct map_rect *mr;
 907         struct item *item;
 908         struct coord lp, sc[1000];
 909         struct street_data *sd;
 910
 911         h=mapset_open(ms);
 912         while ((m=mapset_next(h,1))) {
 913                 mr=map_rect_new(m, sel);
 914                while ((item=map_rect_get_item(mr))) {
 915                         if (item->type >= type_street_0 && item->type <= type_ferry) {
 916                                 sd=street_get_data(item);
 917                                 dist=transform_distance_polyline_sq(sd->c, sd->count, c, &lp, &pos);
 918                                 if (!ret || dist < ret->dist) {
 919                                         if (ret) {
 920                                                 street_data_free(ret->street);
 921                                                 g_free(ret);
 922                                         }
 923                                         ret=g_new(struct route_info, 1);
 924                                         ret->c=*c;
 925                                         ret->lp=lp;
 926                                         ret->pos=pos;
 927                                         ret->dist=dist;
 928                                         ret->dir=0;
 929                                         ret->street=sd;
 930                                         dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
 931                                 } else
 932                                         street_data_free(sd);
 933                         } else
 934                                 while (item_coord_get(item, &sc[0], 1));
 935                 }
 936                 map_rect_destroy(mr);
 937         }
 938         mapset_close(h);
 939
 940         return ret;
 941 }
 942
 943 void
 944 route_info_free(struct route_info *inf)
 945 {
 946         if (inf->street)
 947                 street_data_free(inf->street);
 948         g_free(inf);
 949 }
 950
 951
 952 #include "point.h"
 953
 954 struct street_data *
 955 route_info_street(struct route_info *rinf)
 956 {
 957         return rinf->street;
 958 }
 959
 960 struct coord *
 961 route_info_point(struct route_info *rinf, int point)
 962 {
 963         struct street_data *sd=rinf->street;
 964         int dir;
 965
 966         switch(point) {
 967         case -1:
 968         case 2:
 969                 dir=point == 2 ? rinf->dir : -rinf->dir;
 970                 if (dir > 0)
 971                         return &sd->c[sd->count-1];
 972                 else
 973                         return &sd->c[0];
 974         case 0:
 975                 return &rinf->c;
 976         case 1:
 977                 return &rinf->lp;
 978         }
 979         return NULL;
 980
 981 }
 982
 983 struct route_info_handle {
 984         struct route_info *start;
 985         struct route_info *curr;
 986         struct route_info *end;
 987         struct coord *last;
 988         int count;
 989         int iter;
 990         int pos;
 991         int endpos;
 992         int dir;
 993 };
 994
 995 struct route_info_handle *
 996 route_info_open(struct route_info *start, struct route_info *end, int dir)
 997 {
 998         struct route_info_handle *ret=g_new0(struct route_info_handle, 1);
 999
1000         struct route_info *curr;
1001         dbg(2,"enter start=%p end=%p dir=%d\n", start, end, dir);
1002         ret->start=start;
1003         ret->end=end;
1004         if (start)
1005                 curr=start;
1006         else
1007                 curr=end;
1008         ret->endpos=-2;
1009         if (start && end) {
1010                 if (start->street->item.map != end->street->item.map || start->street->item.id_hi != end->street->item.id_hi || start->street->item.id_lo != end->street->item.id_lo) {
1011                         dbg(1,"return NULL\n");
1012                         return NULL;
1013                 }
1014                 printf("trivial start=%d end=%d start dir %d end dir %d\n", start->pos, end->pos, start->dir, end->dir);
1015                 if (start->pos == end->pos) {
1016                         printf("fixme\n");
1017                         start->dir=0;
1018                         end->dir=0;
1019                 }
1020                 if (start->pos > end->pos) {
1021                         printf("fixme\n");
1022                         start->dir=-1;
1023                         end->dir=1;
1024                 }
1025                 if (start->pos < end->pos) {
1026                         printf("fixme\n");
1027                         start->dir=1;
1028                         end->dir=-1;
1029                 }
1030                 printf("trivial now start=%d end=%d start dir %d end dir %d\n", start->pos, end->pos, start->dir, end->dir);
1031                 ret->endpos=end->pos;
1032         }
1033
1034         if (!dir)
1035                 dir=curr->dir;
1036         dbg(2,"dir=%d\n", dir);
1037         ret->dir=dir;
1038         ret->curr=curr;
1039         ret->pos=curr->pos;
1040         if (dir > 0) {
1041                 ret->pos++;
1042                 ret->endpos++;
1043         }
1044         dbg(2,"ret=%p\n",ret);
1045         return ret;
1046 }
1047
1048 struct coord *
1049 route_info_get(struct route_info_handle *h)
1050 {
1051         struct coord *new;
1052         for (;;) {
1053                 new=NULL;
1054                 dbg(1,"iter=%d\n", h->iter);
1055                 switch(h->iter) {
1056                 case 0:
1057                         if (h->start) {
1058                                 new=&h->start->c;
1059                                 h->iter++;
1060                                 break;
1061                         } else {
1062                                 h->iter=2;
1063                                 continue;
1064                         }
1065                 case 1:
1066                         new=&h->start->lp;
1067                         h->iter++;
1068                         break;
1069                 case 2:
1070                         dbg(1,"h->pos=%d\n", h->pos);
1071                         if (h->dir && h->pos >= 0 && h->pos < h->curr->street->count && (h->end == NULL || h->endpos!=h->pos)) {
1072                                 new=&h->curr->street->c[h->pos];
1073                                 h->pos+=h->dir;
1074                         } else {
1075                                 h->iter++;
1076                                 continue;
1077                         }
1078                         break;
1079                 case 3:
1080                         if (h->end) {
1081                                 new=&h->end->lp;
1082                                 h->iter++;
1083                                 break;
1084                         }
1085                         break;
1086                 case 4:
1087                         new=&h->end->c;
1088                         h->iter++;
1089                         break;
1090
1091                 }
1092                 if (new) {
1093                         dbg(1,"new=%p (0x%x,0x%x) last=%p\n", new, new->x, new->y, h->last);
1094                         if (h->last && new->x == h->last->x && new->y == h->last->y)
1095                                 continue;
1096                         h->last=new;
1097                         return new;
1098                 }
1099                 return NULL;
1100         }
1101 }
1102
1103 void
1104 route_info_close(struct route_info_handle *h)
1105 {
1106         g_free(h);
1107 }
1108
1109
1110
1111
1112 static int
1113 route_draw_route_info(struct route_info *pos, struct route_info *dst, struct transformation *t, struct displaylist *dsp)
1114 {
1115         struct route_info_handle *h;
1116         struct coord *c;
1117         struct coord_rect r;
1118         struct item item;
1119         struct point pnt[100];
1120         int count=0;
1121
1122         item.id_lo=0;
1123         item.id_hi=0;
1124         item.map=NULL;
1125         item.type=type_street_route;
1126
1127         dbg(1, "enter\n");
1128         h=route_info_open(pos, dst, 0);
1129         dbg(1,"h=%p\n", h);
1130         if (! h) {
1131                 dbg(1, "return 0\n");
1132                 return 0;
1133         }
1134         if (pos)
1135                 dbg(1, "pos=%p pos->dir=%d pos->pos=%d\n", pos, pos->dir, pos->pos);
1136         c=route_info_get(h);
1137         r.lu=*c;
1138         r.rl=*c;
1139         while (c && count < 100) {
1140                 dbg(1,"c=%p (0x%x,0x%x)\n", c, c->x, c->y);
1141                 transform(t, projection_mg, c, &pnt[count++]);
1142                 coord_rect_extend(&r, c);
1143                 c=route_info_get(h);
1144
1145         }
1146         if (count && transform_contains(t, projection_mg, &r))
1147                 display_add(dsp, &item, count, pnt, "Route");
1148         route_info_close(h);
1149         dbg(1, "return 1\n");
1150         return 1;
1151 }
1152
1153 void
1154 route_draw(struct route *this, struct transformation *t, struct displaylist *dsp)
1155 {
1156         dbg(1,"enter\n");
1157         if (! this->pos || ! this->dst)
1158                 return;
1159         if (! route_draw_route_info(this->pos, this->dst, t, dsp)) {
1160                 route_draw_route_info(this->pos, NULL, t, dsp);
1161                 route_draw_route_info(NULL, this->dst, t, dsp);
1162         }
1163         dbg(1,"exit\n");
1164 }
1165
1166 #if 0
1167 struct route_crossings *
1168 route_crossings_get(struct route *this, struct coord *c)
1169 {
1170       struct route_point *pnt;
1171       struct route_segment *seg;
1172       int crossings=0;
1173       struct route_crossings *ret;
1174
1175        pnt=route_graph_get_point(this, c);
1176        seg=pnt->start;
1177        while (seg) {
1178                 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1179                crossings++;
1180                seg=seg->start_next;
1181        }
1182        seg=pnt->end;
1183        while (seg) {
1184                 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1185                crossings++;
1186                seg=seg->end_next;
1187        }
1188        ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
1189        ret->count=crossings;
1190        return ret;
1191 }
1192 #endif