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