navit/navit/route.c

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