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