2 * Navit, a modular navigation system.
3 * Copyright (C) 2005-2008 Navit Team
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.
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.
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.
34 #include "projection.h"
42 #include "transform.h"
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;
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;
76 struct route_path_segment {
77 struct route_path_segment *next;
97 struct street_data *street;
101 struct route_path_segment *path;
102 struct route_path_segment *path_last;
103 /* XXX: path_hash is not necessery now */
104 struct item_hash *path_hash;
107 #define RF_FASTEST (1<<0)
108 #define RF_SHORTEST (1<<1)
109 #define RF_AVOIDHW (1<<2)
110 #define RF_AVOIDPAID (1<<3)
111 #define RF_LOCKONROAD (1<<4)
112 #define RF_SHOWGRAPH (1<<5)
118 struct route_info *pos;
119 struct route_info *dst;
121 struct route_graph *graph;
122 struct route_path *path2;
124 struct map *graph_map;
125 int speedlist[route_item_last-route_item_first+1];
129 struct route_graph_point *route_points;
130 struct route_graph_segment *route_segments;
131 #define HASH_SIZE 8192
132 struct route_graph_point *hash[HASH_SIZE];
135 #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
137 static struct route_info * route_find_nearest_street(struct mapset *ms, struct pcoord *c);
138 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
139 static void route_graph_update(struct route *this);
140 static struct route_path *route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist);
141 static void route_process_street_graph(struct route_graph *this, struct item *item);
142 static void route_graph_destroy(struct route_graph *this);
143 static void route_path_update(struct route *this);
145 static enum projection route_projection(struct route *route)
147 struct street_data *street;
148 street = route->pos ? route->pos->street : route->dst->street;
149 return map_projection(street->item.map);
153 route_path_destroy(struct route_path *this)
155 struct route_path_segment *c,*n;
158 if (this->path_hash) {
159 item_hash_destroy(this->path_hash);
160 this->path_hash=NULL;
172 route_new(struct attr **attrs)
174 struct route *this=g_new0(struct route, 1);
176 printf("%s:Out of memory\n", __FUNCTION__);
183 route_set_mapset(struct route *this, struct mapset *ms)
189 route_get_mapset(struct route *this)
195 route_get_pos(struct route *this)
201 route_get_dst(struct route *this)
207 route_get_speedlist(struct route *this)
209 return this->speedlist;
213 route_get_path_set(struct route *this)
215 return this->path2 != NULL;
219 route_set_speed(struct route *this, enum item_type type, int value)
221 if (type < route_item_first || type > route_item_last) {
222 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
225 this->speedlist[type-route_item_first]=value;
230 route_contains(struct route *this, struct item *item)
232 if (! this->path2 || !this->path2->path_hash)
234 return (int)item_hash_lookup(this->path2->path_hash, item);
238 route_path_update(struct route *this)
240 struct route_path *oldpath = NULL;
241 if (! this->pos || ! this->dst) {
242 route_path_destroy(this->path2);
246 /* the graph is destroyed when setting the destination */
247 if (this->graph && this->pos && this->dst && this->path2) {
248 // we can try to update
249 oldpath = this->path2;
252 if (! this->graph || !(this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist))) {
254 route_graph_update(this);
255 this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist);
256 profile(1,"route_path_new");
260 /* Destroy what's left */
261 route_path_destroy(oldpath);
266 route_set_position(struct route *this, struct pcoord *pos)
269 route_info_free(this->pos);
271 this->pos=route_find_nearest_street(this->ms, pos);
272 dbg(1,"this->pos=%p\n", this->pos);
276 route_path_update(this);
280 route_set_position_from_tracking(struct route *this, struct tracking *tracking)
283 struct route_info *ret;
286 c=tracking_get_pos(tracking);
287 ret=g_new0(struct route_info, 1);
289 printf("%s:Out of memory\n", __FUNCTION__);
293 route_info_free(this->pos);
297 ret->pos=tracking_get_segment_pos(tracking);
300 ret->street=street_data_dup(tracking_get_street_data(tracking));
301 dbg(3,"c->x=0x%x, c->y=0x%x pos=%d item=(0x%x,0x%x)\n", c->x, c->y, ret->pos, ret->street->item.id_hi, ret->street->item.id_lo);
302 dbg(3,"street 0=(0x%x,0x%x) %d=(0x%x,0x%x)\n", ret->street->c[0].x, ret->street->c[0].y, ret->street->count-1, ret->street->c[ret->street->count-1].x, ret->street->c[ret->street->count-1].y);
305 route_path_update(this);
309 /* Used for debuging of route_rect, what routing sees */
310 struct map_selection *route_selection;
312 struct map_selection *
313 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
315 int dx,dy,sx=1,sy=1,d,m;
316 struct map_selection *sel=g_new(struct map_selection, 1);
318 printf("%s:Out of memory\n", __FUNCTION__);
321 sel->order[layer_town]=0;
322 sel->order[layer_poly]=0;
323 sel->order[layer_street]=order;
324 dbg(1,"%p %p\n", c1, c2);
329 sel->u.c_rect.lu.x=c1->x;
330 sel->u.c_rect.rl.x=c2->x;
332 sel->u.c_rect.lu.x=c2->x;
333 sel->u.c_rect.rl.x=c1->x;
337 sel->u.c_rect.lu.y=c2->y;
338 sel->u.c_rect.rl.y=c1->y;
340 sel->u.c_rect.lu.y=c1->y;
341 sel->u.c_rect.rl.y=c2->y;
348 sel->u.c_rect.lu.x-=m;
349 sel->u.c_rect.rl.x+=m;
350 sel->u.c_rect.lu.y+=m;
351 sel->u.c_rect.rl.y-=m;
356 static struct map_selection *
357 route_calc_selection(struct coord *c1, struct coord *c2)
359 struct map_selection *ret,*sel;
360 sel=route_rect(4, c1, c2, 25, 0);
362 sel->next=route_rect(8, c1, c1, 0, 40000);
364 sel->next=route_rect(18, c1, c1, 0, 10000);
366 sel->next=route_rect(8, c2, c2, 0, 40000);
368 sel->next=route_rect(18, c2, c2, 0, 10000);
369 /* route_selection=ret; */
374 route_free_selection(struct map_selection *sel)
376 struct map_selection *next;
387 route_set_destination(struct route *this, struct pcoord *dst)
391 route_info_free(this->dst);
394 this->dst=route_find_nearest_street(this->ms, dst);
395 profile(1,"find_nearest_street");
396 route_graph_destroy(this->graph);
398 route_path_update(this);
402 static struct route_graph_point *
403 route_graph_get_point(struct route_graph *this, struct coord *c)
405 struct route_graph_point *p;
406 int hashval=HASHCOORD(c);
407 p=this->hash[hashval];
409 if (p->c.x == c->x && p->c.y == c->y)
417 static struct route_graph_point *
418 route_graph_add_point(struct route_graph *this, struct coord *f)
421 struct route_graph_point *p;
423 p=route_graph_get_point(this,f);
425 hashval=HASHCOORD(f);
427 printf("p (0x%x,0x%x)\n", f->x, f->y);
428 p=g_new(struct route_graph_point,1);
430 printf("%s:Out of memory\n", __FUNCTION__);
433 p->hash_next=this->hash[hashval];
434 this->hash[hashval]=p;
435 p->next=this->route_points;
442 this->route_points=p;
449 route_graph_free_points(struct route_graph *this)
451 struct route_graph_point *curr,*next;
452 curr=this->route_points;
458 this->route_points=NULL;
459 memset(this->hash, 0, sizeof(this->hash));
463 route_graph_add_segment(struct route_graph *this, struct route_graph_point *start,
464 struct route_graph_point *end, int len, struct item *item,
465 int flags, int offset)
467 struct route_graph_segment *s;
468 s = g_new0(struct route_graph_segment, 1);
470 printf("%s:Out of memory\n", __FUNCTION__);
474 s->start_next=start->start;
477 s->end_next=end->end;
484 s->next=this->route_segments;
485 this->route_segments=s;
487 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
490 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
491 struct route_graph_segment *rgs)
495 int rc = 0, fs = 0, p = 0;
497 mr=map_rect_new(i->map, NULL);
500 item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
503 rc = item_coord_get(item, &c1, 1);
506 if (c1.x == rgs->start->c.x &&
507 c1.y == rgs->start->c.y)
512 if (c1.x == rgs->end->c.x &&
513 c1.y == rgs->end->c.y)
519 map_rect_destroy(mr);
523 static struct route_path_segment *
524 route_extract_segment_from_path(struct route_path *path, struct item *item,
527 struct route_path_segment *sp = NULL, *s;
530 if (s->offset == offset && item_is_equal(s->item,*item)) {
535 path->path = s->next;
543 item_hash_remove(path->path_hash, item);
548 route_path_add_item(struct route_path *this, struct route_path *oldpath,
549 struct route_graph_segment *rgs, int len, int offset, int dir)
551 struct route_path_segment *segment;
553 struct coord ca[2048];
556 ccnt = (int)item_hash_lookup(oldpath->path_hash, &rgs->item);
558 segment = route_extract_segment_from_path(oldpath,
565 ccnt = get_item_seg_coords(&rgs->item, ca, 2047, rgs);
566 segment= g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccnt);
568 printf("%s:Out of memory\n", __FUNCTION__);
571 memcpy(segment->c, ca, ccnt * sizeof(struct coord));
572 segment->ncoords = ccnt;
573 segment->item=rgs->item;
574 segment->offset = offset;
579 item_hash_insert(this->path_hash, &rgs->item, (void *)offset);
583 this->path_last->next=segment;
584 this->path_last=segment;
587 struct route_path_handle {
588 struct route_path_segment *s;
591 struct route_path_handle *
592 route_path_open(struct route *this)
594 struct route_path_handle *ret;
596 if (! this->path2 || ! this->path2->path)
599 ret=g_new(struct route_path_handle, 1);
601 printf("%s:Out of memory\n", __FUNCTION__);
604 ret->s=this->path2->path;
608 struct route_path_segment *
609 route_path_get_segment(struct route_path_handle *h)
611 struct route_path_segment *ret=h->s;
619 static struct coord *
620 route_path_segment_get_helper(struct route_path_segment *s, int dir)
625 return &s->c[s->ncoords-1];
629 route_path_segment_get_start(struct route_path_segment *s)
631 return route_path_segment_get_helper(s, 1);
635 route_path_segment_get_end(struct route_path_segment *s)
637 return route_path_segment_get_helper(s, -1);
641 route_path_segment_get_item(struct route_path_segment *s)
647 route_path_close(struct route_path_handle *h)
653 route_graph_free_segments(struct route_graph *this)
655 struct route_graph_segment *curr,*next;
656 curr=this->route_segments;
662 this->route_segments=NULL;
666 route_graph_destroy(struct route_graph *this)
669 route_graph_free_points(this);
670 route_graph_free_segments(this);
676 route_time(int *speedlist, struct item *item, int len)
678 if (item->type < route_item_first || item->type > route_item_last) {
679 dbg(0,"street type %d out of range [%d,%d]", item->type, route_item_first, route_item_last);
682 return len*36/speedlist[item->type-route_item_first];
687 route_value(int *speedlist, struct item *item, int len)
691 printf("len=%d\n", len);
694 ret=route_time(speedlist, item, len);
695 dbg(1, "route_value(0x%x, %d)=%d\n", item->type, len, ret);
700 route_process_street_graph(struct route_graph *this, struct item *item)
707 struct route_graph_point *s_pnt,*e_pnt;
714 if (item_coord_get(item, &l, 1)) {
715 if (item_attr_get(item, attr_flags, &attr)) {
717 if (flags & AF_SEGMENTED)
720 s_pnt=route_graph_add_point(this,&l);
722 while (item_coord_get(item, &c, 1)) {
723 len+=transform_distance(map_projection(item->map), &l, &c);
726 e_pnt=route_graph_add_point(this,&l);
728 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
733 isseg = item_coord_is_segment(item);
734 rc = item_coord_get(item, &c, 1);
736 len+=transform_distance(map_projection(item->map), &l, &c);
739 e_pnt=route_graph_add_point(this,&l);
740 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
742 s_pnt=route_graph_add_point(this,&l);
747 e_pnt=route_graph_add_point(this,&l);
750 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
756 compare(void *v1, void *v2)
758 struct route_graph_point *p1=v1;
759 struct route_graph_point *p2=v2;
762 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
764 return p1->value-p2->value;
768 route_info_length(struct route_info *pos, struct route_info *dst, int dir)
770 struct route_info_handle *h;
773 struct street_data *street;
775 dbg(2,"enter pos=%p dst=%p dir=%d\n", pos, dst, dir);
776 h=route_info_open(pos, dst, dir);
781 street = pos ? pos->street : dst->street;
783 while ((c=route_info_get(h))) {
785 ret+=transform_distance(map_projection(street->item.map), c, l);
788 dbg(2,"ret=%d\n", ret);
793 route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist)
795 struct route_graph_point *p_min,*end=NULL;
796 struct route_graph_segment *s;
798 struct fibheap *heap;
799 struct street_data *sd=dst->street;
801 heap = fh_makeheap();
802 fh_setcmp(heap, compare);
804 if (! (sd->flags & AF_ONEWAYREV)) {
805 end=route_graph_get_point(this, &sd->c[0]);
807 end->value=route_value(speedlist, &sd->item, route_info_length(NULL, dst, -1));
808 end->el=fh_insert(heap, end);
811 if (! (sd->flags & AF_ONEWAY)) {
812 end=route_graph_get_point(this, &sd->c[sd->count-1]);
814 end->value=route_value(speedlist, &sd->item, route_info_length(NULL, dst, 1));
815 end->el=fh_insert(heap, end);
818 dbg(1,"0x%x,0x%x\n", end->c.x, end->c.y);
820 p_min=fh_extractmin(heap);
825 printf("extract p=%p free el=%p min=%d, 0x%x, 0x%x\n", p_min, p_min->el, min, p_min->c.x, p_min->c.y);
829 val=route_value(speedlist, &s->item, s->len);
831 val+=val*2*street_route_contained(s->str->segid);
835 printf("begin %d len %d vs %d (0x%x,0x%x)\n",new,val,s->end->value, s->end->c.x, s->end->c.y);
836 if (new < s->end->value && !(s->flags & AF_ONEWAY)) {
841 printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
842 s->end->el=fh_insert(heap, s->end);
844 printf("el new=%p\n", s->end->el);
848 printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
849 fh_replacedata(heap, s->end->el, s->end);
858 val=route_value(speedlist, &s->item, s->len);
861 printf("end %d len %d vs %d (0x%x,0x%x)\n",new,val,s->start->value,s->start->c.x, s->start->c.y);
862 if (new < s->start->value && !(s->flags & AF_ONEWAYREV)) {
866 if (! s->start->el) {
868 printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
869 s->start->el=fh_insert(heap, s->start);
871 printf("el new=%p\n", s->start->el);
875 printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
876 fh_replacedata(heap, s->start->el, s->start);
887 static struct route_path *
888 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist)
890 struct route_graph_point *start1=NULL,*start2=NULL,*start;
891 struct route_graph_segment *s=NULL;
895 int time=0,hr,min,sec
897 unsigned int val1=0xffffffff,val2=0xffffffff;
898 struct street_data *sd=pos->street;
899 struct route_path *ret;
901 if (! (sd->flags & AF_ONEWAY)) {
902 start1=route_graph_get_point(this, &sd->c[0]);
905 val1=start1->value+route_value(speedlist, &sd->item, route_info_length(pos, NULL, -1));
906 dbg(1,"start1: %d(route)+%d=%d\n", start1->value, val1-start1->value, val1);
908 if (! (sd->flags & AF_ONEWAYREV)) {
909 start2=route_graph_get_point(this, &sd->c[sd->count-1]);
912 val2=start2->value+route_value(speedlist, &sd->item, route_info_length(pos, NULL, 1));
913 dbg(1,"start2: %d(route)+%d=%d\n", start2->value, val2-start2->value, val2);
915 dbg(1,"val1=%d val2=%d\n", val1, val2);
917 val1=start1->start->start->value;
918 val2=start2->end->end->value;
920 if (start1 && (val1 < val2)) {
928 printf("no route found, pos blocked\n");
932 ret=g_new0(struct route_path, 1);
934 printf("%s:Out of memory\n", __FUNCTION__);
937 ret->path_hash=item_hash_new();
938 dbg(1,"dir=%d\n", pos->dir);
939 while ((s=start->seg)) {
942 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
946 if (s->start == start) {
947 route_path_add_item(ret, oldpath, s, seg_len, s->offset, 1);
950 route_path_add_item(ret, oldpath, s, seg_len, s->offset, -1);
955 dbg(1,"start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
956 dbg(1,"dst sd->flags=%d sd->c[0]=0x%x,0x%x sd->c[sd->count-1]=0x%x,0x%x\n", sd->flags, sd->c[0].x,sd->c[0].y, sd->c[sd->count-1].x, sd->c[sd->count-1].y);
957 if (start->c.x == sd->c[0].x && start->c.y == sd->c[0].y)
959 else if (start->c.x == sd->c[sd->count-1].x && start->c.y == sd->c[sd->count-1].y)
962 printf("no route found\n");
963 route_path_destroy(ret);
966 ilen=route_info_length(pos, NULL, 0);
969 ilen=route_info_length(NULL, dst, 0);
972 dbg(1, "%d segments\n", segs);
976 static struct route_graph *
977 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2)
979 struct route_graph *ret=g_new0(struct route_graph, 1);
980 struct map_selection *sel;
981 struct mapset_handle *h;
987 printf("%s:Out of memory\n", __FUNCTION__);
990 sel=route_calc_selection(c1, c2);
992 while ((m=mapset_next(h,1))) {
993 mr=map_rect_new(m, sel);
996 while ((item=map_rect_get_item(mr))) {
997 if (item->type >= type_street_0 && item->type <= type_ferry) {
998 route_process_street_graph(ret, item);
1001 map_rect_destroy(mr);
1004 route_free_selection(sel);
1010 route_graph_update(struct route *this)
1012 route_graph_destroy(this->graph);
1013 profile(1,"graph_free");
1014 this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c);
1015 profile(1,"route_graph_build");
1016 route_graph_flood(this->graph, this->dst, this->speedlist);
1017 profile(1,"route_graph_flood");
1021 struct street_data *
1022 street_get_data (struct item *item)
1025 struct coord c[maxcount];
1027 struct street_data *ret;
1030 while (count < maxcount) {
1031 if (!item_coord_get(item, &c[count], 1))
1035 if (count >= maxcount) {
1036 dbg(0, "count=%d maxcount=%d id_hi=0x%x id_lo=0x%x\n", count, maxcount, item->id_hi, item->id_lo);
1037 if (item_attr_get(item, attr_debug, &attr))
1038 dbg(0,"debug='%s'\n", attr.u.str);
1040 g_assert(count < maxcount);
1041 ret=g_malloc(sizeof(struct street_data)+count*sizeof(struct coord));
1044 if (item_attr_get(item, attr_flags, &attr))
1045 ret->flags=attr.u.num;
1048 memcpy(ret->c, c, count*sizeof(struct coord));
1053 struct street_data *
1054 street_data_dup(struct street_data *orig)
1056 struct street_data *ret;
1057 int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
1060 memcpy(ret, orig, size);
1066 street_data_free(struct street_data *sd)
1071 static struct route_info *
1072 route_find_nearest_street(struct mapset *ms, struct pcoord *pc)
1074 struct route_info *ret=NULL;
1076 struct map_selection *sel;
1078 struct mapset_handle *h;
1080 struct map_rect *mr;
1083 struct street_data *sd;
1090 * This is not correct for two reasons:
1091 * - You may need to go back first
1092 * - Currently we allow mixing of mapsets
1094 sel = route_rect(18, &c, &c, 0, max_dist);
1096 while ((m=mapset_next(h,1))) {
1099 if (map_projection(m) != pc->pro) {
1100 transform_to_geo(pc->pro, &c, &g);
1101 transform_from_geo(map_projection(m), &g, &c);
1103 mr=map_rect_new(m, sel);
1106 while ((item=map_rect_get_item(mr))) {
1107 if (item->type >= type_street_0 && item->type <= type_ferry) {
1108 sd=street_get_data(item);
1109 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
1110 if (!ret || dist < ret->dist) {
1112 street_data_free(ret->street);
1115 ret=g_new(struct route_info, 1);
1117 printf("%s:Out of memory\n", __FUNCTION__);
1126 dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
1128 street_data_free(sd);
1131 map_rect_destroy(mr);
1134 map_selection_destroy(sel);
1140 route_info_free(struct route_info *inf)
1143 street_data_free(inf->street);
1150 struct street_data *
1151 route_info_street(struct route_info *rinf)
1153 return rinf->street;
1157 route_info_point(struct route_info *rinf, int point)
1159 struct street_data *sd=rinf->street;
1165 dir=(point == 2) ? rinf->dir : -rinf->dir;
1167 return &sd->c[sd->count-1];
1179 struct route_info_handle {
1180 struct route_info *start;
1181 struct route_info *curr;
1182 struct route_info *end;
1191 struct route_info_handle *
1192 route_info_open(struct route_info *start, struct route_info *end, int dir)
1194 struct route_info_handle *ret=g_new0(struct route_info_handle, 1);
1195 struct route_info *curr;
1196 dbg(2,"enter start=%p end=%p dir=%d\n", start, end, dir);
1198 printf("%s:Out of memory\n", __FUNCTION__);
1209 if (start->street->item.map != end->street->item.map || start->street->item.id_hi != end->street->item.id_hi || start->street->item.id_lo != end->street->item.id_lo) {
1210 dbg(1,"return NULL\n");
1213 printf("trivial start=%d end=%d start dir %d end dir %d\n", start->pos, end->pos, start->dir, end->dir);
1214 if (start->pos == end->pos) {
1219 if (start->pos > end->pos) {
1224 if (start->pos < end->pos) {
1229 printf("trivial now start=%d end=%d start dir %d end dir %d\n", start->pos, end->pos, start->dir, end->dir);
1230 ret->endpos=end->pos;
1235 dbg(2,"dir=%d\n", dir);
1243 dbg(2,"ret=%p\n",ret);
1248 route_info_get(struct route_info_handle *h)
1253 dbg(1,"iter=%d\n", h->iter);
1269 dbg(1,"h->pos=%d\n", h->pos);
1270 if (h->dir && h->pos >= 0 && h->pos < h->curr->street->count && (h->end == NULL || h->endpos!=h->pos)) {
1271 new=&h->curr->street->c[h->pos];
1292 dbg(1,"new=%p (0x%x,0x%x) last=%p\n", new, new->x, new->y, h->last);
1293 if (h->last && new->x == h->last->x && new->y == h->last->y)
1303 route_info_close(struct route_info_handle *h)
1310 struct route_crossings *
1311 route_crossings_get(struct route *this, struct coord *c)
1313 struct route_point *pnt;
1314 struct route_segment *seg;
1316 struct route_crossings *ret;
1318 pnt=route_graph_get_point(this, c);
1321 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1323 seg=seg->start_next;
1327 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1331 ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
1332 ret->count=crossings;
1338 struct map_rect_priv {
1339 struct route_info_handle *ri;
1340 enum attr_type attr_next;
1343 struct map_priv *mpriv;
1347 unsigned int last_coord;
1348 struct route_path_segment *seg;
1349 struct route_graph_point *point;
1350 struct route_graph_segment *rseg;
1355 rm_coord_rewind(void *priv_data)
1357 struct map_rect_priv *mr = priv_data;
1362 rm_attr_rewind(void *priv_data)
1364 struct map_rect_priv *mr = priv_data;
1365 mr->attr_next = attr_street_item;
1369 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1371 struct map_rect_priv *mr = priv_data;
1372 struct route_path_segment *seg=mr->seg;
1373 struct route *route=mr->mpriv->route;
1374 attr->type=attr_type;
1375 switch (attr_type) {
1377 while (mr->attr_next != attr_none) {
1378 if (rm_attr_get(priv_data, mr->attr_next, attr))
1382 case attr_street_item:
1384 attr->u.item=&seg->item;
1386 attr->u.item=mr->sitem;
1387 mr->attr_next=attr_length;
1391 attr->u.num=seg->length;
1393 attr->u.num=mr->length;
1394 mr->attr_next=attr_time;
1398 attr->u.num=route_time(route->speedlist, &seg->item, seg->length);
1400 attr->u.num=route_time(route->speedlist, mr->sitem, mr->length);
1401 mr->attr_next=attr_none;
1404 attr->type=attr_none;
1411 rm_coord_get(void *priv_data, struct coord *c, int count)
1413 struct map_rect_priv *mr = priv_data;
1414 struct route_path_segment *seg = mr->seg;
1417 dbg(1,"pos=%d seg=%p\n", mr->pos, seg);
1420 for (i=0; i < count; i++) {
1421 if ((c1=route_info_get(mr->ri))) {
1428 for (i=0; i < count; i++) {
1429 if (mr->last_coord >= seg->ncoords)
1431 if (i >= seg->ncoords)
1434 c[i] = seg->c[seg->ncoords-++mr->last_coord];
1436 c[i] = seg->c[mr->last_coord++];
1441 for (i=0; i < count; i++) {
1442 if ((c1=route_info_get(mr->ri))) {
1451 dbg(1,"return %d\n",rc);
1455 static struct item_methods methods_route_item = {
1463 rp_attr_rewind(void *priv_data)
1465 struct map_rect_priv *mr = priv_data;
1466 mr->attr_next = attr_label;
1470 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1472 struct map_rect_priv *mr = priv_data;
1473 struct route_graph_point *p = mr->point;
1474 if (mr->item.type != type_rg_point)
1476 switch (attr_type) {
1478 while (mr->attr_next != attr_none) {
1479 if (rm_attr_get(priv_data, mr->attr_next, attr))
1483 attr->type = attr_label;
1486 if (p->value != INT_MAX)
1487 mr->str=g_strdup_printf("%d", p->value);
1489 mr->str=g_strdup("-");
1490 attr->u.str = mr->str;
1491 mr->attr_next=attr_none;
1494 attr->type = attr_debug;
1497 mr->str=g_strdup_printf("x=%d y=%d", p->c.x, p->c.y);
1498 attr->u.str = mr->str;
1499 mr->attr_next=attr_none;
1507 rp_coord_get(void *priv_data, struct coord *c, int count)
1509 struct map_rect_priv *mr = priv_data;
1510 struct route_graph_point *p = mr->point;
1511 struct route_graph_segment *seg = mr->rseg;
1513 for (i=0; i < count; i++) {
1514 if (mr->item.type == type_rg_point) {
1515 if (mr->last_coord >= 1)
1519 if (mr->last_coord >= 2)
1524 c[i] = seg->start->c;
1532 static struct item_methods methods_point_item = {
1540 rm_destroy(struct map_priv *priv)
1545 static struct map_rect_priv *
1546 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
1548 struct map_rect_priv * mr;
1550 if (! route_get_pos(priv->route))
1552 if (! route_get_dst(priv->route))
1554 if (! priv->route->path2)
1556 mr=g_new0(struct map_rect_priv, 1);
1558 mr->ri=route_info_open(route_get_pos(priv->route), route_get_dst(priv->route), 0);
1560 mr->sitem=&(route_get_pos(priv->route)->street->item);
1561 mr->item.priv_data = mr;
1562 mr->item.type = type_street_route;
1563 mr->item.meth = &methods_route_item;
1565 mr->length=route_info_length(route_get_pos(priv->route), route_get_dst(priv->route), 0);
1567 mr->ri=route_info_open(route_get_pos(priv->route), NULL, 0);
1568 mr->length=route_info_length(route_get_pos(priv->route), NULL, 0);
1574 static struct map_rect_priv *
1575 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
1577 struct map_rect_priv * mr;
1579 if (! priv->route->graph || ! priv->route->graph->route_points)
1581 mr=g_new0(struct map_rect_priv, 1);
1583 mr->item.priv_data = mr;
1584 mr->item.type = type_rg_point;
1585 mr->item.meth = &methods_point_item;
1590 rm_rect_destroy(struct map_rect_priv *mr)
1593 route_info_close(mr->ri);
1599 static struct item *
1600 rp_get_item(struct map_rect_priv *mr)
1602 struct route *r = mr->mpriv->route;
1603 struct route_graph_point *p = mr->point;
1604 struct route_graph_segment *seg = mr->rseg;
1606 if (mr->item.type == type_rg_point) {
1608 p = r->graph->route_points;
1614 rm_coord_rewind(mr);
1618 mr->item.type = type_rg_segment;
1621 seg=r->graph->route_segments;
1627 rm_coord_rewind(mr);
1635 static struct item *
1636 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
1638 struct item *ret=NULL;
1640 ret=rp_get_item(mr);
1645 static struct item *
1646 rm_get_item(struct map_rect_priv *mr)
1648 struct route *r = mr->mpriv->route;
1649 struct route_path_segment *seg = mr->seg;
1650 dbg(1,"enter\n", mr->pos);
1652 mr->pos=mr->pos_next;
1659 seg = r->path2->path;
1663 mr->sitem = &seg->item;
1667 route_info_close(mr->ri);
1668 mr->ri=route_info_open(NULL, route_get_dst(r), 0);
1669 mr->sitem=&(route_get_dst(r)->street->item);
1670 mr->length=route_info_length(NULL, route_get_dst(r), 0);
1684 static struct item *
1685 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
1687 struct item *ret=NULL;
1689 ret=rm_get_item(mr);
1693 static struct map_methods route_meth = {
1706 static struct map_methods route_graph_meth = {
1720 route_toggle_routegraph_display(struct route *route)
1722 if (route->flags & RF_SHOWGRAPH) {
1723 route->flags &= ~RF_SHOWGRAPH;
1725 route->flags |= RF_SHOWGRAPH;
1729 static struct map_priv *
1730 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
1732 struct map_priv *ret;
1733 struct attr *route_attr;
1735 route_attr=attr_search(attrs, NULL, attr_route);
1738 ret=g_new0(struct map_priv, 1);
1740 *meth=route_graph_meth;
1743 ret->route=route_attr->u.route;
1748 static struct map_priv *
1749 route_map_new(struct map_methods *meth, struct attr **attrs)
1751 return route_map_new_helper(meth, attrs, 0);
1754 static struct map_priv *
1755 route_graph_map_new(struct map_methods *meth, struct attr **attrs)
1757 return route_map_new_helper(meth, attrs, 1);
1761 route_get_map_helper(struct route *this_, struct map **map, char *type)
1763 struct attr route_attr;
1764 struct attr data_attr;
1765 struct attr *attrs_route[]={&route_attr, &data_attr, NULL};
1766 route_attr.type=attr_route;
1767 route_attr.u.route=this_;
1768 data_attr.type=attr_data;
1772 *map=map_new(type,attrs_route);
1777 route_get_map(struct route *this_)
1779 return route_get_map_helper(this_, &this_->map, "route");
1784 route_get_graph_map(struct route *this_)
1786 return route_get_map_helper(this_, &this_->graph_map, "route_graph");
1790 route_set_projection(struct route *this_, enum projection pro)
1797 plugin_register_map_type("route", route_map_new);
1798 plugin_register_map_type("route_graph", route_graph_map_new);