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