navit/navit/route.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #if 0
   5 #include <math.h>
   6 #include <assert.h>
   7 #include <unistd.h>
   8 #include <sys/time.h>
   9 #endif
  10 #include <glib.h>
  11 #include "config.h"
  12 #include "debug.h"
  13 #include "profile.h"
  14 #include "coord.h"
  15 #include "projection.h"
  16 #include "map.h"
  17 #include "mapset.h"
  18 #include "item.h"
  19 #include "route.h"
  20 #include "track.h"
  21 #include "point.h"
  22 #include "graphics.h"
  23 #include "transform.h"
  24 #include "plugin.h"
  25 #include "fib.h"
  26
  27
  28 struct map_priv {
  29         struct route *route;
  30 };
  31
  32 int debug_route=0;
  33
  34 struct route_graph_point {
  35         struct route_graph_point *next;
  36         struct route_graph_point *hash_next;
  37         struct route_graph_segment *start;
  38         struct route_graph_segment *end;
  39         struct route_graph_segment *seg;
  40         struct fibheap_el *el;
  41         int value;
  42         struct coord c;
  43 };
  44
  45 struct route_graph_segment {
  46         struct route_graph_segment *next;
  47         struct route_graph_segment *start_next;
  48         struct route_graph_segment *end_next;
  49         struct route_graph_point *start;
  50         struct route_graph_point *end;
  51         struct item item;
  52         int flags;
  53         int len;
  54         int offset;
  55 };
  56
  57 struct route_path_segment {
  58         struct route_path_segment *next;
  59         struct item item;
  60         unsigned int offset;
  61 #if 0
  62         int time;
  63 #endif
  64         int length;
  65         int dir;
  66         unsigned ncoords;
  67         struct coord c[0];
  68 };
  69
  70 struct route_info {
  71         struct coord c;
  72         struct coord lp;
  73         int pos;
  74
  75         int dist;
  76         int dir;
  77
  78         struct street_data *street;
  79 };
  80
  81 struct route_path {
  82         struct route_path_segment *path;
  83         struct route_path_segment *path_last;
  84         /* XXX: path_hash is not necessery now */
  85         struct item_hash *path_hash;
  86 };
  87
  88 #define RF_FASTEST      (1<<0)
  89 #define RF_SHORTEST     (1<<1)
  90 #define RF_AVOIDHW      (1<<2)
  91 #define RF_AVOIDPAID    (1<<3)
  92 #define RF_LOCKONROAD   (1<<4)
  93 #define RF_SHOWGRAPH    (1<<5)
  94
  95 struct route {
  96         int version;
  97         struct mapset *ms;
  98         unsigned flags;
  99         struct route_info *pos;
 100         struct route_info *dst;
 101
 102         struct route_graph *graph;
 103         struct route_path *path2;
 104         struct map *map;
 105         struct map *graph_map;
 106         int speedlist[route_item_last-route_item_first+1];
 107 };
 108
 109 struct route_graph {
 110         struct route_graph_point *route_points;
 111         struct route_graph_segment *route_segments;
 112 #define HASH_SIZE 8192
 113         struct route_graph_point *hash[HASH_SIZE];
 114 };
 115
 116 #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
 117
 118 static struct route_info * route_find_nearest_street(struct mapset *ms, struct pcoord *c);
 119 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
 120 static void route_graph_update(struct route *this);
 121 static struct route_path *route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist);
 122 static void route_process_street_graph(struct route_graph *this, struct item *item);
 123 static void route_graph_destroy(struct route_graph *this);
 124 static void route_path_update(struct route *this);
 125
 126 static enum projection route_projection(struct route *route)
 127 {
 128         struct street_data *street;
 129         street = route->pos ? route->pos->street : route->dst->street;
 130         return map_projection(street->item.map);
 131 }
 132
 133 static void
 134 route_path_destroy(struct route_path *this)
 135 {
 136         struct route_path_segment *c,*n;
 137         if (! this)
 138                 return;
 139         if (this->path_hash) {
 140                 item_hash_destroy(this->path_hash);
 141                 this->path_hash=NULL;
 142         }
 143         c=this->path;
 144         while (c) {
 145                 n=c->next;
 146                 g_free(c);
 147                 c=n;
 148         }
 149         g_free(this);
 150 }
 151
 152 struct route *
 153 route_new(struct attr **attrs)
 154 {
 155         struct route *this=g_new0(struct route, 1);
 156         if (!this) {
 157                 printf("%s:Out of memory\n", __FUNCTION__);
 158                 return NULL;
 159         }
 160         return this;
 161 }
 162
 163 void
 164 route_set_mapset(struct route *this, struct mapset *ms)
 165 {
 166         this->ms=ms;
 167 }
 168
 169 struct mapset *
 170 route_get_mapset(struct route *this)
 171 {
 172         return this->ms;
 173 }
 174
 175 struct route_info *
 176 route_get_pos(struct route *this)
 177 {
 178         return this->pos;
 179 }
 180
 181 struct route_info *
 182 route_get_dst(struct route *this)
 183 {
 184         return this->dst;
 185 }
 186
 187 int *
 188 route_get_speedlist(struct route *this)
 189 {
 190         return this->speedlist;
 191 }
 192
 193 int
 194 route_get_path_set(struct route *this)
 195 {
 196         return this->path2 != NULL;
 197 }
 198
 199 int
 200 route_set_speed(struct route *this, enum item_type type, int value)
 201 {
 202         if (type < route_item_first || type > route_item_last) {
 203                 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
 204                 return 0;
 205         }
 206         this->speedlist[type-route_item_first]=value;
 207         return 1;
 208 }
 209
 210 int
 211 route_contains(struct route *this, struct item *item)
 212 {
 213         if (! this->path2 || !this->path2->path_hash)
 214                 return 0;
 215         return  (int)item_hash_lookup(this->path2->path_hash, item);
 216 }
 217
 218 static void
 219 route_path_update(struct route *this)
 220 {
 221         struct route_path *oldpath = NULL;
 222         if (! this->pos || ! this->dst) {
 223                 route_path_destroy(this->path2);
 224                 this->path2 = NULL;
 225                 return;
 226         }
 227         /* the graph is destroyed when setting the destination */
 228         if (this->graph && this->pos && this->dst && this->path2) {
 229                 // we can try to update
 230                 oldpath = this->path2;
 231                 this->path2 = NULL;
 232         }
 233         if (! this->graph || !(this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist))) {
 234                 profile(0,NULL);
 235                 route_graph_update(this);
 236                 this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist);
 237                 profile(1,"route_path_new");
 238                 profile(0,"end");
 239         }
 240         if (oldpath) {
 241                 /* Destroy what's left */
 242                 route_path_destroy(oldpath);
 243         }
 244 }
 245
 246 void
 247 route_set_position(struct route *this, struct pcoord *pos)
 248 {
 249         if (this->pos)
 250                 route_info_free(this->pos);
 251         this->pos=NULL;
 252         this->pos=route_find_nearest_street(this->ms, pos);
 253         dbg(1,"this->pos=%p\n", this->pos);
 254         if (! this->pos)
 255                 return;
 256         if (this->dst)
 257                 route_path_update(this);
 258 }
 259
 260 void
 261 route_set_position_from_tracking(struct route *this, struct tracking *tracking)
 262 {
 263         struct coord *c;
 264         struct route_info *ret;
 265
 266         dbg(2,"enter\n");
 267         c=tracking_get_pos(tracking);
 268         ret=g_new0(struct route_info, 1);
 269         if (!ret) {
 270                 printf("%s:Out of memory\n", __FUNCTION__);
 271                 return;
 272         }
 273         if (this->pos)
 274                 route_info_free(this->pos);
 275         this->pos=NULL;
 276         ret->c=*c;
 277         ret->lp=*c;
 278         ret->pos=tracking_get_segment_pos(tracking);
 279         ret->dist=0;
 280         ret->dir=0;
 281         ret->street=street_data_dup(tracking_get_street_data(tracking));
 282         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);
 283         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);
 284         this->pos=ret;
 285         if (this->dst)
 286                 route_path_update(this);
 287         dbg(2,"ret\n");
 288 }
 289
 290 /* Used for debuging of route_rect, what routing sees */
 291 struct map_selection *route_selection;
 292
 293 struct map_selection *
 294 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
 295 {
 296         int dx,dy,sx=1,sy=1,d,m;
 297         struct map_selection *sel=g_new(struct map_selection, 1);
 298         if (!sel) {
 299                 printf("%s:Out of memory\n", __FUNCTION__);
 300                 return sel;
 301         }
 302         sel->order[layer_town]=0;
 303         sel->order[layer_poly]=0;
 304         sel->order[layer_street]=order;
 305         dbg(1,"%p %p\n", c1, c2);
 306         dx=c1->x-c2->x;
 307         dy=c1->y-c2->y;
 308         if (dx < 0) {
 309                 sx=-1;
 310                 sel->u.c_rect.lu.x=c1->x;
 311                 sel->u.c_rect.rl.x=c2->x;
 312         } else {
 313                 sel->u.c_rect.lu.x=c2->x;
 314                 sel->u.c_rect.rl.x=c1->x;
 315         }
 316         if (dy < 0) {
 317                 sy=-1;
 318                 sel->u.c_rect.lu.y=c2->y;
 319                 sel->u.c_rect.rl.y=c1->y;
 320         } else {
 321                 sel->u.c_rect.lu.y=c1->y;
 322                 sel->u.c_rect.rl.y=c2->y;
 323         }
 324         if (dx*sx > dy*sy)
 325                 d=dx*sx;
 326         else
 327                 d=dy*sy;
 328         m=d*rel/100+abs;
 329         sel->u.c_rect.lu.x-=m;
 330         sel->u.c_rect.rl.x+=m;
 331         sel->u.c_rect.lu.y+=m;
 332         sel->u.c_rect.rl.y-=m;
 333         sel->next=NULL;
 334         return sel;
 335 }
 336
 337 static struct map_selection *
 338 route_calc_selection(struct coord *c1, struct coord *c2)
 339 {
 340         struct map_selection *ret,*sel;
 341         sel=route_rect(4, c1, c2, 25, 0);
 342         ret=sel;
 343         sel->next=route_rect(8, c1, c1, 0, 40000);
 344         sel=sel->next;
 345         sel->next=route_rect(18, c1, c1, 0, 10000);
 346         sel=sel->next;
 347         sel->next=route_rect(8, c2, c2, 0, 40000);
 348         sel=sel->next;
 349         sel->next=route_rect(18, c2, c2, 0, 10000);
 350         /* route_selection=ret; */
 351         return ret;
 352 }
 353
 354 static void
 355 route_free_selection(struct map_selection *sel)
 356 {
 357         struct map_selection *next;
 358         while (sel) {
 359                 next=sel->next;
 360                 g_free(sel);
 361                 sel=next;
 362         }
 363 }
 364
 365
 366
 367 void
 368 route_set_destination(struct route *this, struct pcoord *dst)
 369 {
 370         profile(0,NULL);
 371         if (this->dst)
 372                 route_info_free(this->dst);
 373         this->dst=NULL;
 374         if (dst)
 375                 this->dst=route_find_nearest_street(this->ms, dst);
 376         profile(1,"find_nearest_street");
 377         route_graph_destroy(this->graph);
 378         this->graph=NULL;
 379         route_path_update(this);
 380         profile(0,"end");
 381 }
 382
 383 static struct route_graph_point *
 384 route_graph_get_point(struct route_graph *this, struct coord *c)
 385 {
 386         struct route_graph_point *p;
 387         int hashval=HASHCOORD(c);
 388         p=this->hash[hashval];
 389         while (p) {
 390                 if (p->c.x == c->x && p->c.y == c->y)
 391                         return p;
 392                 p=p->hash_next;
 393         }
 394         return NULL;
 395 }
 396
 397
 398 static struct route_graph_point *
 399 route_graph_add_point(struct route_graph *this, struct coord *f)
 400 {
 401         int hashval;
 402         struct route_graph_point *p;
 403
 404         p=route_graph_get_point(this,f);
 405         if (!p) {
 406                 hashval=HASHCOORD(f);
 407                 if (debug_route)
 408                         printf("p (0x%x,0x%x)\n", f->x, f->y);
 409                 p=g_new(struct route_graph_point,1);
 410                 if (!p) {
 411                         printf("%s:Out of memory\n", __FUNCTION__);
 412                         return p;
 413                 }
 414                 p->hash_next=this->hash[hashval];
 415                 this->hash[hashval]=p;
 416                 p->next=this->route_points;
 417                 p->el=NULL;
 418                 p->start=NULL;
 419                 p->end=NULL;
 420                 p->seg=NULL;
 421                 p->value=INT_MAX;
 422                 p->c=*f;
 423                 this->route_points=p;
 424         }
 425         return p;
 426 }
 427
 428
 429 static void
 430 route_graph_free_points(struct route_graph *this)
 431 {
 432         struct route_graph_point *curr,*next;
 433         curr=this->route_points;
 434         while (curr) {
 435                 next=curr->next;
 436                 g_free(curr);
 437                 curr=next;
 438         }
 439         this->route_points=NULL;
 440         memset(this->hash, 0, sizeof(this->hash));
 441 }
 442
 443 static void
 444 route_graph_add_segment(struct route_graph *this, struct route_graph_point *start,
 445                         struct route_graph_point *end, int len, struct item *item,
 446                         int flags, int offset)
 447 {
 448         struct route_graph_segment *s;
 449         s = g_new0(struct route_graph_segment, 1);
 450         if (!s) {
 451                 printf("%s:Out of memory\n", __FUNCTION__);
 452                 return;
 453         }
 454         s->start=start;
 455         s->start_next=start->start;
 456         start->start=s;
 457         s->end=end;
 458         s->end_next=end->end;
 459         end->end=s;
 460         g_assert(len >= 0);
 461         s->len=len;
 462         s->item=*item;
 463         s->flags=flags;
 464         s->offset = offset;
 465         s->next=this->route_segments;
 466         this->route_segments=s;
 467         if (debug_route)
 468                 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
 469 }
 470
 471 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
 472                 struct route_graph_segment *rgs)
 473 {
 474         struct map_rect *mr;
 475         struct item *item;
 476         int rc = 0, fs = 0, p = 0;
 477         struct coord c1;
 478         mr=map_rect_new(i->map, NULL);
 479         if (!mr)
 480                 return 0;
 481         item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
 482         if (item) {
 483                 do {
 484                         rc = item_coord_get(item, &c1, 1);
 485                         if (rc) {
 486                                 if (!fs) {
 487                                         if (c1.x == rgs->start->c.x &&
 488                                                 c1.y == rgs->start->c.y)
 489                                                 fs = 1;
 490                                 }
 491                                 if (fs) {
 492                                         c[p++] = c1;
 493                                         if (c1.x == rgs->end->c.x &&
 494                                                 c1.y == rgs->end->c.y)
 495                                                 break;
 496                                 }
 497                         }
 498                 } while (rc);
 499         }
 500         map_rect_destroy(mr);
 501         return p;
 502 }
 503
 504 static struct route_path_segment *
 505 route_extract_segment_from_path(struct route_path *path, struct item *item,
 506                                                  int offset)
 507 {
 508         struct route_path_segment *sp = NULL, *s;
 509         s = path->path;
 510         while (s) {
 511                 if (s->offset == offset && item_is_equal(s->item,*item)) {
 512                         if (sp) {
 513                                 sp->next = s->next;
 514                                 break;
 515                         } else {
 516                                 path->path = s->next;
 517                                 break;
 518                         }
 519                 }
 520                 sp = s;
 521                 s = s->next;
 522         }
 523         if (s)
 524                 item_hash_remove(path->path_hash, item);
 525         return s;
 526 }
 527
 528 static void
 529 route_path_add_item(struct route_path *this, struct route_path *oldpath,
 530                 struct route_graph_segment *rgs, int len, int offset, int dir)
 531 {
 532         struct route_path_segment *segment;
 533         int ccnt = 0;
 534         struct coord ca[2048];
 535
 536         if (oldpath) {
 537                 ccnt = (int)item_hash_lookup(oldpath->path_hash, &rgs->item);
 538                 if (ccnt) {
 539                         segment = route_extract_segment_from_path(oldpath,
 540                                                          &rgs->item, offset);
 541                         if (segment)
 542                                 goto linkold;
 543                 }
 544         }
 545
 546         ccnt = get_item_seg_coords(&rgs->item, ca, 2047, rgs);
 547         segment= g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccnt);
 548         if (!segment) {
 549                 printf("%s:Out of memory\n", __FUNCTION__);
 550                 return;
 551         }
 552         memcpy(segment->c, ca, ccnt * sizeof(struct coord));
 553         segment->ncoords = ccnt;
 554         segment->item=rgs->item;
 555         segment->offset = offset;
 556 linkold:
 557         segment->length=len;
 558         segment->dir=dir;
 559         segment->next=NULL;
 560         item_hash_insert(this->path_hash,  &rgs->item, (void *)offset);
 561         if (!this->path)
 562                 this->path=segment;
 563         if (this->path_last)
 564                 this->path_last->next=segment;
 565         this->path_last=segment;
 566 }
 567
 568 struct route_path_handle {
 569         struct route_path_segment *s;
 570 };
 571
 572 struct route_path_handle *
 573 route_path_open(struct route *this)
 574 {
 575         struct route_path_handle *ret;
 576
 577         if (! this->path2 || ! this->path2->path)
 578                 return NULL;
 579
 580         ret=g_new(struct route_path_handle, 1);
 581         if (!ret) {
 582                 printf("%s:Out of memory\n", __FUNCTION__);
 583                 return ret;
 584         }
 585         ret->s=this->path2->path;
 586         return ret;
 587 }
 588
 589 struct route_path_segment *
 590 route_path_get_segment(struct route_path_handle *h)
 591 {
 592         struct route_path_segment *ret=h->s;
 593
 594         if (ret)
 595                 h->s=ret->next;
 596
 597         return ret;
 598 }
 599
 600 static struct coord *
 601 route_path_segment_get_helper(struct route_path_segment *s, int dir)
 602 {
 603         if (s->dir == dir)
 604                 return &s->c[0];
 605         else
 606                 return &s->c[s->ncoords-1];
 607 }
 608
 609 struct coord *
 610 route_path_segment_get_start(struct route_path_segment *s)
 611 {
 612         return route_path_segment_get_helper(s, 1);
 613 }
 614
 615 struct coord *
 616 route_path_segment_get_end(struct route_path_segment *s)
 617 {
 618         return route_path_segment_get_helper(s, -1);
 619 }
 620
 621 struct item *
 622 route_path_segment_get_item(struct route_path_segment *s)
 623 {
 624         return &s->item;
 625 }
 626
 627 void
 628 route_path_close(struct route_path_handle *h)
 629 {
 630         g_free(h);
 631 }
 632
 633 static void
 634 route_graph_free_segments(struct route_graph *this)
 635 {
 636         struct route_graph_segment *curr,*next;
 637         curr=this->route_segments;
 638         while (curr) {
 639                 next=curr->next;
 640                 g_free(curr);
 641                 curr=next;
 642         }
 643         this->route_segments=NULL;
 644 }
 645
 646 static void
 647 route_graph_destroy(struct route_graph *this)
 648 {
 649         if (this) {
 650                 route_graph_free_points(this);
 651                 route_graph_free_segments(this);
 652                 g_free(this);
 653         }
 654 }
 655
 656 int
 657 route_time(int *speedlist, struct item *item, int len)
 658 {
 659         if (item->type < route_item_first || item->type > route_item_last) {
 660                 dbg(0,"street type %d out of range [%d,%d]", item->type, route_item_first, route_item_last);
 661                 return len*36;
 662         }
 663         return len*36/speedlist[item->type-route_item_first];
 664 }
 665
 666
 667 static int
 668 route_value(int *speedlist, struct item *item, int len)
 669 {
 670         int ret;
 671         if (len < 0) {
 672                 printf("len=%d\n", len);
 673         }
 674         g_assert(len >= 0);
 675         ret=route_time(speedlist, item, len);
 676         dbg(1, "route_value(0x%x, %d)=%d\n", item->type, len, ret);
 677         return ret;
 678 }
 679
 680 static void
 681 route_process_street_graph(struct route_graph *this, struct item *item)
 682 {
 683 #ifdef AVOID_FLOAT
 684         int len=0;
 685 #else
 686         double len=0;
 687 #endif
 688         struct route_graph_point *s_pnt,*e_pnt;
 689         struct coord c,l;
 690         struct attr attr;
 691         int flags = 0;
 692         int segmented = 0;
 693         int offset = 1;
 694
 695         if (item_coord_get(item, &l, 1)) {
 696                 if (item_attr_get(item, attr_flags, &attr)) {
 697                         flags = attr.u.num;
 698                         if (flags & AF_SEGMENTED)
 699                                 segmented = 1;
 700                 }
 701                 s_pnt=route_graph_add_point(this,&l);
 702                 if (!segmented) {
 703                         while (item_coord_get(item, &c, 1)) {
 704                                 len+=transform_distance(map_projection(item->map), &l, &c);
 705                                 l=c;
 706                         }
 707                         e_pnt=route_graph_add_point(this,&l);
 708                         g_assert(len >= 0);
 709                         route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
 710                 } else {
 711                         int isseg,rc;
 712                         int sc = 0;
 713                         do {
 714                                 isseg = item_coord_is_segment(item);
 715                                 rc = item_coord_get(item, &c, 1);
 716                                 if (rc) {
 717                                         len+=transform_distance(map_projection(item->map), &l, &c);
 718                                         l=c;
 719                                         if (isseg) {
 720                                                 e_pnt=route_graph_add_point(this,&l);
 721                                                 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
 722                                                 offset++;
 723                                                 s_pnt=route_graph_add_point(this,&l);
 724                                                 len = 0;
 725                                         }
 726                                 }
 727                         } while(rc);
 728                         e_pnt=route_graph_add_point(this,&l);
 729                         g_assert(len >= 0);
 730                         sc++;
 731                         route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
 732                 }
 733         }
 734 }
 735
 736 static int
 737 compare(void *v1, void *v2)
 738 {
 739         struct route_graph_point *p1=v1;
 740         struct route_graph_point *p2=v2;
 741 #if 0
 742         if (debug_route)
 743                 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
 744 #endif
 745         return p1->value-p2->value;
 746 }
 747
 748 int
 749 route_info_length(struct route_info *pos, struct route_info *dst, int dir)
 750 {
 751         struct route_info_handle *h;
 752         struct coord *c,*l;
 753         int ret=0;
 754         struct street_data *street;
 755
 756         dbg(2,"enter pos=%p dst=%p dir=%d\n", pos, dst, dir);
 757         h=route_info_open(pos, dst, dir);
 758         if (! h) {
 759                 dbg(2,"ret=-1\n");
 760                 return -1;
 761         }
 762         street = pos ? pos->street : dst->street;
 763         l=route_info_get(h);
 764         while ((c=route_info_get(h))) {
 765                 dbg(3,"c=%p\n", c);
 766                 ret+=transform_distance(map_projection(street->item.map), c, l);
 767                 l=c;
 768         }
 769         dbg(2,"ret=%d\n", ret);
 770         return ret;
 771 }
 772
 773 static void
 774 route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist)
 775 {
 776         struct route_graph_point *p_min,*end=NULL;
 777         struct route_graph_segment *s;
 778         int min,new,old,val;
 779         struct fibheap *heap;
 780         struct street_data *sd=dst->street;
 781
 782         heap = fh_makeheap();
 783         fh_setcmp(heap, compare);
 784
 785         if (! (sd->flags & AF_ONEWAYREV)) {
 786                 end=route_graph_get_point(this, &sd->c[0]);
 787                 g_assert(end != 0);
 788                 end->value=route_value(speedlist, &sd->item, route_info_length(NULL, dst, -1));
 789                 end->el=fh_insert(heap, end);
 790         }
 791
 792         if (! (sd->flags & AF_ONEWAY)) {
 793                 end=route_graph_get_point(this, &sd->c[sd->count-1]);
 794                 g_assert(end != 0);
 795                 end->value=route_value(speedlist, &sd->item, route_info_length(NULL, dst, 1));
 796                 end->el=fh_insert(heap, end);
 797         }
 798
 799         dbg(1,"0x%x,0x%x\n", end->c.x, end->c.y);
 800         for (;;) {
 801                 p_min=fh_extractmin(heap);
 802                 if (! p_min)
 803                         break;
 804                 min=p_min->value;
 805                 if (debug_route)
 806                         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);
 807                 p_min->el=NULL;
 808                 s=p_min->start;
 809                 while (s) {
 810                         val=route_value(speedlist, &s->item, s->len);
 811 #if 0
 812                         val+=val*2*street_route_contained(s->str->segid);
 813 #endif
 814                         new=min+val;
 815                         if (debug_route)
 816                                 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);
 817                         if (new < s->end->value && !(s->flags & AF_ONEWAY)) {
 818                                 s->end->value=new;
 819                                 s->end->seg=s;
 820                                 if (! s->end->el) {
 821                                         if (debug_route)
 822                                                 printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
 823                                         s->end->el=fh_insert(heap, s->end);
 824                                         if (debug_route)
 825                                                 printf("el new=%p\n", s->end->el);
 826                                 }
 827                                 else {
 828                                         if (debug_route)
 829                                                 printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
 830                                         fh_replacedata(heap, s->end->el, s->end);
 831                                 }
 832                         }
 833                         if (debug_route)
 834                                 printf("\n");
 835                         s=s->start_next;
 836                 }
 837                 s=p_min->end;
 838                 while (s) {
 839                         val=route_value(speedlist, &s->item, s->len);
 840                         new=min+val;
 841                         if (debug_route)
 842                                 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);
 843                         if (new < s->start->value && !(s->flags & AF_ONEWAYREV)) {
 844                                 old=s->start->value;
 845                                 s->start->value=new;
 846                                 s->start->seg=s;
 847                                 if (! s->start->el) {
 848                                         if (debug_route)
 849                                                 printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
 850                                         s->start->el=fh_insert(heap, s->start);
 851                                         if (debug_route)
 852                                                 printf("el new=%p\n", s->start->el);
 853                                 }
 854                                 else {
 855                                         if (debug_route)
 856                                                 printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
 857                                         fh_replacedata(heap, s->start->el, s->start);
 858                                 }
 859                         }
 860                         if (debug_route)
 861                                 printf("\n");
 862                         s=s->end_next;
 863                 }
 864         }
 865         fh_deleteheap(heap);
 866 }
 867
 868 static struct route_path *
 869 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist)
 870 {
 871         struct route_graph_point *start1=NULL,*start2=NULL,*start;
 872         struct route_graph_segment *s=NULL;
 873         int len=0,segs=0;
 874         int ilen,seg_len;
 875 #if 0
 876         int time=0,hr,min,sec
 877 #endif
 878         unsigned int val1=0xffffffff,val2=0xffffffff;
 879         struct street_data *sd=pos->street;
 880         struct route_path *ret;
 881
 882         if (! (sd->flags & AF_ONEWAY)) {
 883                 start1=route_graph_get_point(this, &sd->c[0]);
 884                 if (! start1)
 885                         return NULL;
 886                 val1=start1->value+route_value(speedlist, &sd->item, route_info_length(pos, NULL, -1));
 887                 dbg(1,"start1: %d(route)+%d=%d\n", start1->value, val1-start1->value, val1);
 888         }
 889         if (! (sd->flags & AF_ONEWAYREV)) {
 890                 start2=route_graph_get_point(this, &sd->c[sd->count-1]);
 891                 if (! start2)
 892                         return NULL;
 893                 val2=start2->value+route_value(speedlist, &sd->item, route_info_length(pos, NULL, 1));
 894                 dbg(1,"start2: %d(route)+%d=%d\n", start2->value, val2-start2->value, val2);
 895         }
 896         dbg(1,"val1=%d val2=%d\n", val1, val2);
 897         if (val1 == val2) {
 898                 val1=start1->start->start->value;
 899                 val2=start2->end->end->value;
 900         }
 901         if (start1 && (val1 < val2)) {
 902                 start=start1;
 903                 pos->dir=-1;
 904         } else {
 905                 if (start2) {
 906                         start=start2;
 907                         pos->dir=1;
 908                 } else {
 909                         printf("no route found, pos blocked\n");
 910                         return NULL;
 911                 }
 912         }
 913         ret=g_new0(struct route_path, 1);
 914         if (!ret) {
 915                 printf("%s:Out of memory\n", __FUNCTION__);
 916                 return ret;
 917         }
 918         ret->path_hash=item_hash_new();
 919         dbg(1,"dir=%d\n", pos->dir);
 920         while ((s=start->seg)) {
 921                 segs++;
 922 #if 0
 923                 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
 924 #endif
 925                 seg_len=s->len;
 926                 len+=seg_len;
 927                 if (s->start == start) {
 928                         route_path_add_item(ret, oldpath, s, seg_len, s->offset, 1);
 929                         start=s->end;
 930                 } else {
 931                         route_path_add_item(ret, oldpath, s, seg_len, s->offset, -1);
 932                         start=s->start;
 933                 }
 934         }
 935         sd=dst->street;
 936         dbg(1,"start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
 937         dbg(1,"dst sd->flags=%d sd->c[0]=0x%x,0x%x sd->c[sd->count-1]=0x%x,0x%x\n", sd->flags, sd->c[0].x,sd->c[0].y, sd->c[sd->count-1].x, sd->c[sd->count-1].y);
 938         if (start->c.x == sd->c[0].x && start->c.y == sd->c[0].y)
 939                 dst->dir=-1;
 940         else if (start->c.x == sd->c[sd->count-1].x && start->c.y == sd->c[sd->count-1].y)
 941                 dst->dir=1;
 942         else {
 943                 printf("no route found\n");
 944                 route_path_destroy(ret);
 945                 return NULL;
 946         }
 947         ilen=route_info_length(pos, NULL, 0);
 948         len+=ilen;
 949
 950         ilen=route_info_length(NULL, dst, 0);
 951         len+=ilen;
 952
 953         dbg(1, "%d segments\n", segs);
 954         return ret;
 955 }
 956
 957 static struct route_graph *
 958 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2)
 959 {
 960         struct route_graph *ret=g_new0(struct route_graph, 1);
 961         struct map_selection *sel;
 962         struct mapset_handle *h;
 963         struct map_rect *mr;
 964         struct map *m;
 965         struct item *item;
 966
 967         if (!ret) {
 968                 printf("%s:Out of memory\n", __FUNCTION__);
 969                 return ret;
 970         }
 971         sel=route_calc_selection(c1, c2);
 972         h=mapset_open(ms);
 973         while ((m=mapset_next(h,1))) {
 974                 mr=map_rect_new(m, sel);
 975                 if (! mr)
 976                         continue;
 977                 while ((item=map_rect_get_item(mr))) {
 978                         if (item->type >= type_street_0 && item->type <= type_ferry) {
 979                                 route_process_street_graph(ret, item);
 980                         }
 981                 }
 982                 map_rect_destroy(mr);
 983         }
 984         mapset_close(h);
 985         route_free_selection(sel);
 986
 987         return ret;
 988 }
 989
 990 static void
 991 route_graph_update(struct route *this)
 992 {
 993         route_graph_destroy(this->graph);
 994         profile(1,"graph_free");
 995         this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c);
 996         profile(1,"route_graph_build");
 997         route_graph_flood(this->graph, this->dst, this->speedlist);
 998         profile(1,"route_graph_flood");
 999         this->version++;
1000 }
1001
1002 struct street_data *
1003 street_get_data (struct item *item)
1004 {
1005         int maxcount=2000;
1006         struct coord c[maxcount];
1007         int count=0;
1008         struct street_data *ret;
1009         struct attr attr;
1010
1011         while (count < maxcount) {
1012                 if (!item_coord_get(item, &c[count], 1))
1013                         break;
1014                 count++;
1015         }
1016         if (count >= maxcount) {
1017                 dbg(0, "count=%d maxcount=%d id_hi=0x%x id_lo=0x%x\n", count, maxcount, item->id_hi, item->id_lo);
1018                 if (item_attr_get(item, attr_debug, &attr))
1019                         dbg(0,"debug='%s'\n", attr.u.str);
1020         }
1021         g_assert(count < maxcount);
1022         ret=g_malloc(sizeof(struct street_data)+count*sizeof(struct coord));
1023         ret->item=*item;
1024         ret->count=count;
1025         if (item_attr_get(item, attr_flags, &attr))
1026                 ret->flags=attr.u.num;
1027         else
1028                 ret->flags=0;
1029         memcpy(ret->c, c, count*sizeof(struct coord));
1030
1031         return ret;
1032 }
1033
1034 struct street_data *
1035 street_data_dup(struct street_data *orig)
1036 {
1037         struct street_data *ret;
1038         int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
1039
1040         ret=g_malloc(size);
1041         memcpy(ret, orig, size);
1042
1043         return ret;
1044 }
1045
1046 void
1047 street_data_free(struct street_data *sd)
1048 {
1049         g_free(sd);
1050 }
1051
1052 static struct route_info *
1053 route_find_nearest_street(struct mapset *ms, struct pcoord *pc)
1054 {
1055         struct route_info *ret=NULL;
1056         int max_dist=1000;
1057         struct map_selection *sel;
1058         int dist,pos;
1059         struct mapset_handle *h;
1060         struct map *m;
1061         struct map_rect *mr;
1062         struct item *item;
1063         struct coord lp;
1064         struct street_data *sd;
1065         struct coord c;
1066         struct coord_geo g;
1067
1068         c.x = pc->x;
1069         c.y = pc->y;
1070         /*
1071          * This is not correct for two reasons:
1072          * - You may need to go back first
1073          * - Currently we allow mixing of mapsets
1074          */
1075         sel = route_rect(18, &c, &c, 0, max_dist);
1076         h=mapset_open(ms);
1077         while ((m=mapset_next(h,1))) {
1078                 c.x = pc->x;
1079                 c.y = pc->y;
1080                 if (map_projection(m) != pc->pro) {
1081                         transform_to_geo(pc->pro, &c, &g);
1082                         transform_from_geo(map_projection(m), &g, &c);
1083                 }
1084                 mr=map_rect_new(m, sel);
1085                 if (! mr)
1086                         continue;
1087                 while ((item=map_rect_get_item(mr))) {
1088                         if (item->type >= type_street_0 && item->type <= type_ferry) {
1089                                 sd=street_get_data(item);
1090                                 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
1091                                 if (!ret || dist < ret->dist) {
1092                                         if (ret) {
1093                                                 street_data_free(ret->street);
1094                                                 g_free(ret);
1095                                         }
1096                                         ret=g_new(struct route_info, 1);
1097                                         if (!ret) {
1098                                                 printf("%s:Out of memory\n", __FUNCTION__);
1099                                                 return ret;
1100                                         }
1101                                         ret->c=c;
1102                                         ret->lp=lp;
1103                                         ret->pos=pos;
1104                                         ret->dist=dist;
1105                                         ret->dir=0;
1106                                         ret->street=sd;
1107                                         dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
1108                                 } else
1109                                         street_data_free(sd);
1110                         }
1111                 }
1112                 map_rect_destroy(mr);
1113         }
1114         mapset_close(h);
1115         map_selection_destroy(sel);
1116
1117         return ret;
1118 }
1119
1120 void
1121 route_info_free(struct route_info *inf)
1122 {
1123         if (inf->street)
1124                 street_data_free(inf->street);
1125         g_free(inf);
1126 }
1127
1128
1129 #include "point.h"
1130
1131 struct street_data *
1132 route_info_street(struct route_info *rinf)
1133 {
1134         return rinf->street;
1135 }
1136
1137 struct coord *
1138 route_info_point(struct route_info *rinf, int point)
1139 {
1140         struct street_data *sd=rinf->street;
1141         int dir;
1142
1143         switch(point) {
1144         case -1:
1145         case 2:
1146                 dir=(point == 2) ? rinf->dir : -rinf->dir;
1147                 if (dir > 0)
1148                         return &sd->c[sd->count-1];
1149                 else
1150                         return &sd->c[0];
1151         case 0:
1152                 return &rinf->c;
1153         case 1:
1154                 return &rinf->lp;
1155         }
1156         return NULL;
1157
1158 }
1159
1160 struct route_info_handle {
1161         struct route_info *start;
1162         struct route_info *curr;
1163         struct route_info *end;
1164         struct coord *last;
1165         int count;
1166         int iter;
1167         int pos;
1168         int endpos;
1169         int dir;
1170 };
1171
1172 struct route_info_handle *
1173 route_info_open(struct route_info *start, struct route_info *end, int dir)
1174 {
1175         struct route_info_handle *ret=g_new0(struct route_info_handle, 1);
1176         struct route_info *curr;
1177         dbg(2,"enter start=%p end=%p dir=%d\n", start, end, dir);
1178         if (!ret) {
1179                 printf("%s:Out of memory\n", __FUNCTION__);
1180                 return ret;
1181         }
1182         ret->start=start;
1183         ret->end=end;
1184         if (start)
1185                 curr=start;
1186         else
1187                 curr=end;
1188         ret->endpos=-2;
1189         if (start && end) {
1190                 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) {
1191                         dbg(1,"return NULL\n");
1192                         return NULL;
1193                 }
1194                 printf("trivial start=%d end=%d start dir %d end dir %d\n", start->pos, end->pos, start->dir, end->dir);
1195                 if (start->pos == end->pos) {
1196                         printf("fixme\n");
1197                         start->dir=0;
1198                         end->dir=0;
1199                 }
1200                 if (start->pos > end->pos) {
1201                         printf("fixme\n");
1202                         start->dir=-1;
1203                         end->dir=1;
1204                 }
1205                 if (start->pos < end->pos) {
1206                         printf("fixme\n");
1207                         start->dir=1;
1208                         end->dir=-1;
1209                 }
1210                 printf("trivial now start=%d end=%d start dir %d end dir %d\n", start->pos, end->pos, start->dir, end->dir);
1211                 ret->endpos=end->pos;
1212         }
1213
1214         if (!dir)
1215                 dir=curr->dir;
1216         dbg(2,"dir=%d\n", dir);
1217         ret->dir=dir;
1218         ret->curr=curr;
1219         ret->pos=curr->pos;
1220         if (dir > 0) {
1221                 ret->pos++;
1222                 ret->endpos++;
1223         }
1224         dbg(2,"ret=%p\n",ret);
1225         return ret;
1226 }
1227
1228 struct coord *
1229 route_info_get(struct route_info_handle *h)
1230 {
1231         struct coord *new;
1232         for (;;) {
1233                 new=NULL;
1234                 dbg(1,"iter=%d\n", h->iter);
1235                 switch(h->iter) {
1236                 case 0:
1237                         if (h->start) {
1238                                 new=&h->start->c;
1239                                 h->iter++;
1240                                 break;
1241                         } else {
1242                                 h->iter=2;
1243                                 continue;
1244                         }
1245                 case 1:
1246                         new=&h->start->lp;
1247                         h->iter++;
1248                         break;
1249                 case 2:
1250                         dbg(1,"h->pos=%d\n", h->pos);
1251                         if (h->dir && h->pos >= 0 && h->pos < h->curr->street->count && (h->end == NULL || h->endpos!=h->pos)) {
1252                                 new=&h->curr->street->c[h->pos];
1253                                 h->pos+=h->dir;
1254                         } else {
1255                                 h->iter++;
1256                                 continue;
1257                         }
1258                         break;
1259                 case 3:
1260                         if (h->end) {
1261                                 new=&h->end->lp;
1262                                 h->iter++;
1263                                 break;
1264                         }
1265                         break;
1266                 case 4:
1267                         new=&h->end->c;
1268                         h->iter++;
1269                         break;
1270
1271                 }
1272                 if (new) {
1273                         dbg(1,"new=%p (0x%x,0x%x) last=%p\n", new, new->x, new->y, h->last);
1274                         if (h->last && new->x == h->last->x && new->y == h->last->y)
1275                                 continue;
1276                         h->last=new;
1277                         return new;
1278                 }
1279                 return NULL;
1280         }
1281 }
1282
1283 void
1284 route_info_close(struct route_info_handle *h)
1285 {
1286         g_free(h);
1287 }
1288
1289
1290 #if 0
1291 struct route_crossings *
1292 route_crossings_get(struct route *this, struct coord *c)
1293 {
1294       struct route_point *pnt;
1295       struct route_segment *seg;
1296       int crossings=0;
1297       struct route_crossings *ret;
1298
1299        pnt=route_graph_get_point(this, c);
1300        seg=pnt->start;
1301        while (seg) {
1302                 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1303                crossings++;
1304                seg=seg->start_next;
1305        }
1306        seg=pnt->end;
1307        while (seg) {
1308                 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1309                crossings++;
1310                seg=seg->end_next;
1311        }
1312        ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
1313        ret->count=crossings;
1314        return ret;
1315 }
1316 #endif
1317
1318
1319 struct map_rect_priv {
1320         struct route_info_handle *ri;
1321         enum attr_type attr_next;
1322         int pos_next;
1323         int pos;
1324         struct map_priv *mpriv;
1325         struct item item;
1326         struct item *sitem;
1327         int length;
1328         unsigned int last_coord;
1329         struct route_path_segment *seg;
1330         struct route_graph_point *point;
1331         struct route_graph_segment *rseg;
1332         char *str;
1333 };
1334
1335 static void
1336 rm_coord_rewind(void *priv_data)
1337 {
1338         struct map_rect_priv *mr = priv_data;
1339         mr->last_coord = 0;
1340 }
1341
1342 static void
1343 rm_attr_rewind(void *priv_data)
1344 {
1345         struct map_rect_priv *mr = priv_data;
1346         mr->attr_next = attr_street_item;
1347 }
1348
1349 static int
1350 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1351 {
1352         struct map_rect_priv *mr = priv_data;
1353         struct route_path_segment *seg=mr->seg;
1354         struct route *route=mr->mpriv->route;
1355         attr->type=attr_type;
1356         switch (attr_type) {
1357                 case attr_any:
1358                         while (mr->attr_next != attr_none) {
1359                                 if (rm_attr_get(priv_data, mr->attr_next, attr))
1360                                         return 1;
1361                         }
1362                         return 0;
1363                 case attr_street_item:
1364                         if (seg)
1365                                 attr->u.item=&seg->item;
1366                         else
1367                                 attr->u.item=mr->sitem;
1368                         mr->attr_next=attr_length;
1369                         return 1;
1370                 case attr_length:
1371                         if (seg)
1372                                 attr->u.num=seg->length;
1373                         else
1374                                 attr->u.num=mr->length;
1375                         mr->attr_next=attr_time;
1376                         return 1;
1377                 case attr_time:
1378                         if (seg)
1379                                 attr->u.num=route_time(route->speedlist, &seg->item, seg->length);
1380                         else
1381                                 attr->u.num=route_time(route->speedlist, mr->sitem, mr->length);
1382                         mr->attr_next=attr_none;
1383                         return 1;
1384                 default:
1385                         attr->type=attr_none;
1386                         return 0;
1387         }
1388         return 0;
1389 }
1390
1391 static int
1392 rm_coord_get(void *priv_data, struct coord *c, int count)
1393 {
1394         struct map_rect_priv *mr = priv_data;
1395         struct route_path_segment *seg = mr->seg;
1396         struct coord *c1;
1397         int rc = 0,i;
1398         dbg(1,"pos=%d seg=%p\n", mr->pos, seg);
1399         switch (mr->pos) {
1400         case -1:
1401                 for (i=0; i < count; i++) {
1402                         if ((c1=route_info_get(mr->ri))) {
1403                                 c[i]=*c1;
1404                                 rc++;
1405                         }
1406                 }
1407                 break;
1408         case 0:
1409                 for (i=0; i < count; i++) {
1410                         if (mr->last_coord >= seg->ncoords)
1411                                 break;
1412                         if (i >= seg->ncoords)
1413                                 break;
1414                         if (seg->dir < 0)
1415                                 c[i] = seg->c[seg->ncoords-++mr->last_coord];
1416                         else
1417                                 c[i] = seg->c[mr->last_coord++];
1418                         rc++;
1419                 }
1420                 break;
1421         case 1:
1422                 for (i=0; i < count; i++) {
1423                         if ((c1=route_info_get(mr->ri))) {
1424                                 c[i]=*c1;
1425                                 rc++;
1426                         }
1427                 }
1428                 break;
1429         default:
1430                 rc=0;
1431         }
1432         dbg(1,"return %d\n",rc);
1433         return rc;
1434 }
1435
1436 static struct item_methods methods_route_item = {
1437         rm_coord_rewind,
1438         rm_coord_get,
1439         rm_attr_rewind,
1440         rm_attr_get,
1441 };
1442
1443 static void
1444 rp_attr_rewind(void *priv_data)
1445 {
1446         struct map_rect_priv *mr = priv_data;
1447         mr->attr_next = attr_label;
1448 }
1449
1450 static int
1451 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1452 {
1453         struct map_rect_priv *mr = priv_data;
1454         struct route_graph_point *p = mr->point;
1455         if (mr->item.type != type_rg_point)
1456                 return 0;
1457         switch (attr_type) {
1458         case attr_any:
1459                 while (mr->attr_next != attr_none) {
1460                         if (rm_attr_get(priv_data, mr->attr_next, attr))
1461                                 return 1;
1462                 }
1463         case attr_label:
1464                 attr->type = attr_label;
1465                 if (mr->str)
1466                         g_free(mr->str);
1467                 if (p->value != INT_MAX)
1468                         mr->str=g_strdup_printf("%d", p->value);
1469                 else
1470                         mr->str=g_strdup("-");
1471                 attr->u.str = mr->str;
1472                 mr->attr_next=attr_none;
1473                 return 1;
1474         case attr_debug:
1475                 attr->type = attr_debug;
1476                 if (mr->str)
1477                         g_free(mr->str);
1478                 mr->str=g_strdup_printf("x=%d y=%d", p->c.x, p->c.y);
1479                 attr->u.str = mr->str;
1480                 mr->attr_next=attr_none;
1481                 return 1;
1482         default:
1483                 return 0;
1484         }
1485 }
1486
1487 static int
1488 rp_coord_get(void *priv_data, struct coord *c, int count)
1489 {
1490         struct map_rect_priv *mr = priv_data;
1491         struct route_graph_point *p = mr->point;
1492         struct route_graph_segment *seg = mr->rseg;
1493         int rc = 0,i;
1494         for (i=0; i < count; i++) {
1495                 if (mr->item.type == type_rg_point) {
1496                         if (mr->last_coord >= 1)
1497                                 break;
1498                         c[i] = p->c;
1499                 } else {
1500                         if (mr->last_coord >= 2)
1501                                 break;
1502                         if (mr->last_coord)
1503                                 c[i] = seg->end->c;
1504                         else
1505                                 c[i] = seg->start->c;
1506                 }
1507                 mr->last_coord++;
1508                 rc++;
1509         }
1510         return rc;
1511 }
1512
1513 static struct item_methods methods_point_item = {
1514         rm_coord_rewind,
1515         rp_coord_get,
1516         rp_attr_rewind,
1517         rp_attr_get,
1518 };
1519
1520 static void
1521 rm_destroy(struct map_priv *priv)
1522 {
1523         g_free(priv);
1524 }
1525
1526 static struct map_rect_priv *
1527 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
1528 {
1529         struct map_rect_priv * mr;
1530         dbg(1,"enter\n");
1531         if (! route_get_pos(priv->route))
1532                 return NULL;
1533         if (! route_get_dst(priv->route))
1534                 return NULL;
1535         if (! priv->route->path2)
1536                 return NULL;
1537         mr=g_new0(struct map_rect_priv, 1);
1538         mr->mpriv = priv;
1539         mr->ri=route_info_open(route_get_pos(priv->route), route_get_dst(priv->route), 0);
1540         mr->pos_next=1;
1541         mr->sitem=&(route_get_pos(priv->route)->street->item);
1542         mr->item.priv_data = mr;
1543         mr->item.type = type_street_route;
1544         mr->item.meth = &methods_route_item;
1545         if (mr->ri) {
1546                 mr->length=route_info_length(route_get_pos(priv->route), route_get_dst(priv->route), 0);
1547         } else {
1548                 mr->ri=route_info_open(route_get_pos(priv->route), NULL, 0);
1549                 mr->length=route_info_length(route_get_pos(priv->route), NULL, 0);
1550                 mr->pos_next=-1;
1551         }
1552         return mr;
1553 }
1554
1555 static struct map_rect_priv *
1556 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
1557 {
1558         struct map_rect_priv * mr;
1559         dbg(1,"enter\n");
1560         if (! priv->route->graph || ! priv->route->graph->route_points)
1561                 return NULL;
1562         mr=g_new0(struct map_rect_priv, 1);
1563         mr->mpriv = priv;
1564         mr->item.priv_data = mr;
1565         mr->item.type = type_rg_point;
1566         mr->item.meth = &methods_point_item;
1567         return mr;
1568 }
1569
1570 static void
1571 rm_rect_destroy(struct map_rect_priv *mr)
1572 {
1573         if (mr->ri)
1574                 route_info_close(mr->ri);
1575         if (mr->str)
1576                 g_free(mr->str);
1577         g_free(mr);
1578 }
1579
1580 static struct item *
1581 rp_get_item(struct map_rect_priv *mr)
1582 {
1583         struct route *r = mr->mpriv->route;
1584         struct route_graph_point *p = mr->point;
1585         struct route_graph_segment *seg = mr->rseg;
1586
1587         if (mr->item.type == type_rg_point) {
1588                 if (!p)
1589                         p = r->graph->route_points;
1590                 else
1591                         p = p->next;
1592                 if (p) {
1593                         mr->point = p;
1594                         mr->item.id_lo++;
1595                         rm_coord_rewind(mr);
1596                         rp_attr_rewind(mr);
1597                         return &mr->item;
1598                 } else
1599                         mr->item.type = type_rg_segment;
1600         }
1601         if (!seg)
1602                 seg=r->graph->route_segments;
1603         else
1604                 seg=seg->next;
1605         if (seg) {
1606                 mr->rseg = seg;
1607                 mr->item.id_lo++;
1608                 rm_coord_rewind(mr);
1609                 rp_attr_rewind(mr);
1610                 return &mr->item;
1611         }
1612         return NULL;
1613
1614 }
1615
1616 static struct item *
1617 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
1618 {
1619         struct item *ret=NULL;
1620         while (id_lo-- > 0)
1621                 ret=rp_get_item(mr);
1622         return ret;
1623 }
1624
1625
1626 static struct item *
1627 rm_get_item(struct map_rect_priv *mr)
1628 {
1629         struct route *r = mr->mpriv->route;
1630         struct route_path_segment *seg = mr->seg;
1631         dbg(1,"enter\n", mr->pos);
1632
1633         mr->pos=mr->pos_next;
1634         switch(mr->pos) {
1635         case -1:
1636                 mr->pos_next=0;
1637                 break;
1638         case 0:
1639                 if (!seg)
1640                         seg = r->path2->path;
1641                 else
1642                         seg = seg->next;
1643                 if (seg) {
1644                         mr->sitem = &seg->item;
1645                         break;
1646                 }
1647                 mr->pos=1;
1648                 route_info_close(mr->ri);
1649                 mr->ri=route_info_open(NULL, route_get_dst(r), 0);
1650                 mr->sitem=&(route_get_dst(r)->street->item);
1651                 mr->length=route_info_length(NULL, route_get_dst(r), 0);
1652         case 1:
1653                 mr->pos_next=2;
1654                 break;
1655         case 2:
1656                 return NULL;
1657         }
1658         mr->seg = seg;
1659         mr->last_coord = 0;
1660         mr->item.id_lo++;
1661         rm_attr_rewind(mr);
1662         return &mr->item;
1663 }
1664
1665 static struct item *
1666 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
1667 {
1668         struct item *ret=NULL;
1669         while (id_lo-- > 0)
1670                 ret=rm_get_item(mr);
1671         return ret;
1672 }
1673
1674 static struct map_methods route_meth = {
1675         projection_mg,
1676         NULL,
1677         rm_destroy,
1678         rm_rect_new,
1679         rm_rect_destroy,
1680         rm_get_item,
1681         rm_get_item_byid,
1682         NULL,
1683         NULL,
1684         NULL,
1685 };
1686
1687 static struct map_methods route_graph_meth = {
1688         projection_mg,
1689         NULL,
1690         rm_destroy,
1691         rp_rect_new,
1692         rm_rect_destroy,
1693         rp_get_item,
1694         rp_get_item_byid,
1695         NULL,
1696         NULL,
1697         NULL,
1698 };
1699
1700 void
1701 route_toggle_routegraph_display(struct route *route)
1702 {
1703         if (route->flags & RF_SHOWGRAPH) {
1704                 route->flags &= ~RF_SHOWGRAPH;
1705         } else {
1706                 route->flags |= RF_SHOWGRAPH;
1707         }
1708 }
1709
1710 static struct map_priv *
1711 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
1712 {
1713         struct map_priv *ret;
1714         struct attr *route_attr;
1715
1716         route_attr=attr_search(attrs, NULL, attr_route);
1717         if (! route_attr)
1718                 return NULL;
1719         ret=g_new0(struct map_priv, 1);
1720         if (graph)
1721                 *meth=route_graph_meth;
1722         else
1723                 *meth=route_meth;
1724         ret->route=route_attr->u.route;
1725
1726         return ret;
1727 }
1728
1729 static struct map_priv *
1730 route_map_new(struct map_methods *meth, struct attr **attrs)
1731 {
1732         return route_map_new_helper(meth, attrs, 0);
1733 }
1734
1735 static struct map_priv *
1736 route_graph_map_new(struct map_methods *meth, struct attr **attrs)
1737 {
1738         return route_map_new_helper(meth, attrs, 1);
1739 }
1740
1741 static struct map *
1742 route_get_map_helper(struct route *this_, struct map **map, char *type)
1743 {
1744         struct attr route_attr;
1745         struct attr data_attr;
1746         struct attr *attrs_route[]={&route_attr, &data_attr, NULL};
1747         route_attr.type=attr_route;
1748         route_attr.u.route=this_;
1749         data_attr.type=attr_data;
1750         data_attr.u.str="";
1751
1752         if (! *map)
1753                 *map=map_new(type,attrs_route);
1754         return *map;
1755 }
1756
1757 struct map *
1758 route_get_map(struct route *this_)
1759 {
1760         return route_get_map_helper(this_, &this_->map, "route");
1761 }
1762
1763
1764 struct map *
1765 route_get_graph_map(struct route *this_)
1766 {
1767         return route_get_map_helper(this_, &this_->graph_map, "route_graph");
1768 }
1769
1770 void
1771 route_set_projection(struct route *this_, enum projection pro)
1772 {
1773 }
1774
1775 void
1776 route_init(void)
1777 {
1778         plugin_register_map_type("route", route_map_new);
1779         plugin_register_map_type("route_graph", route_graph_map_new);
1780 }