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