git.maemo.org Git - navit-package/blob - navit/search.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 <glib.h>
  21 #include <string.h>
  22 #include "debug.h"
  23 #include "projection.h"
  24 #include "item.h"
  25 #include "map.h"
  26 #include "mapset.h"
  27 #include "coord.h"
  28 #include "search.h"
  29
  30 struct search_list_level {
  31         struct mapset *ms;
  32         struct search_list_common *parent;
  33         struct attr *attr;
  34         int partial;
  35         int selected;
  36         struct mapset_search *search;
  37         GHashTable *hash;
  38         GList *list,*curr,*last;
  39 };
  40
  41 struct search_list {
  42         struct mapset *ms;
  43         int level;
  44         struct search_list_level levels[4];
  45         struct search_list_result result;
  46         struct search_list_result last_result;
  47         int last_result_valid;
  48 };
  49
  50 static guint
  51 search_item_hash_hash(gconstpointer key)
  52 {
  53         const struct item *itm=key;
  54         gconstpointer hashkey=(gconstpointer)GINT_TO_POINTER(itm->id_hi^itm->id_lo);
  55         return g_direct_hash(hashkey);
  56 }
  57
  58 static gboolean
  59 search_item_hash_equal(gconstpointer a, gconstpointer b)
  60 {
  61         const struct item *itm_a=a;
  62         const struct item *itm_b=b;
  63         if (item_is_equal_id(*itm_a, *itm_b))
  64                 return TRUE;
  65         return FALSE;
  66 }
  67
  68 struct search_list *
  69 search_list_new(struct mapset *ms)
  70 {
  71         struct search_list *ret;
  72
  73         ret=g_new0(struct search_list, 1);
  74         ret->ms=ms;
  75
  76         return ret;
  77 }
  78
  79 static void search_list_search_free(struct search_list *sl, int level);
  80
  81 static int
  82 search_list_level(enum attr_type attr_type)
  83 {
  84         switch(attr_type) {
  85         case attr_country_all:
  86         case attr_country_id:
  87         case attr_country_iso2:
  88         case attr_country_iso3:
  89         case attr_country_car:
  90         case attr_country_name:
  91                 return 0;
  92         case attr_town_postal:
  93                 return 1;
  94         case attr_town_name:
  95         case attr_district_name:
  96         case attr_town_or_district_name:
  97                 return 1;
  98         case attr_street_name:
  99                 return 2;
 100         case attr_house_number:
 101                 return 3;
 102         default:
 103                 dbg(0,"unknown search '%s'\n",attr_to_name(attr_type));
 104                 return -1;
 105         }
 106 }
 107
 108 void
 109 search_list_search(struct search_list *this_, struct attr *search_attr, int partial)
 110 {
 111         struct search_list_level *le;
 112         int level=search_list_level(search_attr->type);
 113         dbg(1,"level=%d\n", level);
 114         if (level != -1) {
 115                 this_->result.id=0;
 116                 this_->level=level;
 117                 le=&this_->levels[level];
 118                 search_list_search_free(this_, level);
 119                 le->attr=attr_dup(search_attr);
 120                 le->partial=partial;
 121                 if (level > 0) {
 122                         le=&this_->levels[level-1];
 123                         le->curr=le->list;
 124                 }
 125                 dbg(1,"le=%p partial=%d\n", le, partial);
 126         }
 127 }
 128
 129 struct search_list_common *
 130 search_list_select(struct search_list *this_, enum attr_type attr_type, int id, int mode)
 131 {
 132         int level=search_list_level(attr_type);
 133         int num=0;
 134         struct search_list_level *le;
 135         struct search_list_common *slc;
 136         GList *curr;
 137         le=&this_->levels[level];
 138         curr=le->list;
 139         if (mode > 0 || !id)
 140                 le->selected=mode;
 141         dbg(1,"enter level=%d %d %d %p\n", level, id, mode, curr);
 142         while (curr) {
 143                 num++;
 144                 if (! id || num == id) {
 145                         slc=curr->data;
 146                         slc->selected=mode;
 147                         if (id) {
 148                                 le->last=curr;
 149                                 dbg(0,"found\n");
 150                                 return slc;
 151                         }
 152                 }
 153                 curr=g_list_next(curr);
 154         }
 155         dbg(1,"not found\n");
 156         return NULL;
 157 }
 158
 159 static void
 160 search_list_common_new(struct item *item, struct search_list_common *common)
 161 {
 162         struct attr attr;
 163         if (item_attr_get(item, attr_town_name, &attr))
 164                 common->town_name=map_convert_string(item->map, attr.u.str);
 165         else
 166                 common->town_name=NULL;
 167         if (item_attr_get(item, attr_district_name, &attr))
 168                 common->district_name=map_convert_string(item->map, attr.u.str);
 169         else
 170                 common->district_name=NULL;
 171         if (item_attr_get(item, attr_postal, &attr))
 172                 common->postal=map_convert_string(item->map, attr.u.str);
 173         else
 174                 common->postal=NULL;
 175         if (item_attr_get(item, attr_postal_mask, &attr))
 176                 common->postal_mask=map_convert_string(item->map, attr.u.str);
 177         else
 178                 common->postal_mask=NULL;
 179 }
 180
 181 static void
 182 search_list_common_destroy(struct search_list_common *common)
 183 {
 184         map_convert_free(common->town_name);
 185         map_convert_free(common->district_name);
 186         map_convert_free(common->postal);
 187         map_convert_free(common->postal_mask);
 188 }
 189
 190 static struct search_list_country *
 191 search_list_country_new(struct item *item)
 192 {
 193         struct search_list_country *ret=g_new0(struct search_list_country, 1);
 194         struct attr attr;
 195
 196         ret->common.item=ret->common.unique=*item;
 197         if (item_attr_get(item, attr_country_car, &attr))
 198                 ret->car=g_strdup(attr.u.str);
 199         if (item_attr_get(item, attr_country_iso2, &attr)) {
 200                 ret->iso2=g_strdup(attr.u.str);
 201                 ret->flag=g_strdup_printf("country_%s", ret->iso2);
 202         }
 203         if (item_attr_get(item, attr_country_iso3, &attr))
 204                 ret->iso3=g_strdup(attr.u.str);
 205         if (item_attr_get(item, attr_country_name, &attr))
 206                 ret->name=g_strdup(attr.u.str);
 207         return ret;
 208 }
 209
 210 static void
 211 search_list_country_destroy(struct search_list_country *this_)
 212 {
 213         g_free(this_->car);
 214         g_free(this_->iso2);
 215         g_free(this_->iso3);
 216         g_free(this_->flag);
 217         g_free(this_->name);
 218         g_free(this_);
 219 }
 220
 221 static struct search_list_town *
 222 search_list_town_new(struct item *item)
 223 {
 224         struct search_list_town *ret=g_new0(struct search_list_town, 1);
 225         struct attr attr;
 226         struct coord c;
 227
 228         ret->itemt=*item;
 229         ret->common.item=ret->common.unique=*item;
 230         if (item_attr_get(item, attr_town_streets_item, &attr)) {
 231                 dbg(1,"town_assoc 0x%x 0x%x\n", attr.u.item->id_hi, attr.u.item->id_lo);
 232                 ret->common.unique=*attr.u.item;
 233         }
 234         search_list_common_new(item, &ret->common);
 235         if (item_attr_get(item, attr_county_name, &attr))
 236                 ret->county=map_convert_string(item->map,attr.u.str);
 237         else
 238                 ret->county=NULL;
 239         if (item_coord_get(item, &c, 1)) {
 240                 ret->common.c=g_new(struct pcoord, 1);
 241                 ret->common.c->x=c.x;
 242                 ret->common.c->y=c.y;
 243                 ret->common.c->pro = map_projection(item->map);
 244         }
 245         return ret;
 246 }
 247
 248 static void
 249 search_list_town_destroy(struct search_list_town *this_)
 250 {
 251         map_convert_free(this_->county);
 252         search_list_common_destroy(&this_->common);
 253         if (this_->common.c)
 254                 g_free(this_->common.c);
 255         g_free(this_);
 256 }
 257
 258
 259 static struct search_list_street *
 260 search_list_street_new(struct item *item)
 261 {
 262         struct search_list_street *ret=g_new0(struct search_list_street, 1);
 263         struct attr attr;
 264         struct coord c;
 265
 266         ret->common.item=ret->common.unique=*item;
 267         if (item_attr_get(item, attr_street_name, &attr))
 268                 ret->name=map_convert_string(item->map, attr.u.str);
 269         else
 270                 ret->name=NULL;
 271         search_list_common_new(item, &ret->common);
 272         if (item_coord_get(item, &c, 1)) {
 273                 ret->common.c=g_new(struct pcoord, 1);
 274                 ret->common.c->x=c.x;
 275                 ret->common.c->y=c.y;
 276                 ret->common.c->pro = map_projection(item->map);
 277         }
 278         return ret;
 279 }
 280
 281
 282 static void
 283 search_list_street_destroy(struct search_list_street *this_)
 284 {
 285         map_convert_free(this_->name);
 286         search_list_common_destroy(&this_->common);
 287         if (this_->common.c)
 288                 g_free(this_->common.c);
 289         g_free(this_);
 290 }
 291
 292 static struct search_list_house_number *
 293 search_list_house_number_new(struct item *item)
 294 {
 295         struct search_list_house_number *ret=g_new0(struct search_list_house_number, 1);
 296         struct attr attr;
 297         struct coord c;
 298
 299         ret->common.item=ret->common.unique=*item;
 300         if (item_attr_get(item, attr_house_number, &attr))
 301                 ret->house_number=map_convert_string(item->map, attr.u.str);
 302         search_list_common_new(item, &ret->common);
 303         if (item_coord_get(item, &c, 1)) {
 304                 ret->common.c=g_new(struct pcoord, 1);
 305                 ret->common.c->x=c.x;
 306                 ret->common.c->y=c.y;
 307                 ret->common.c->pro = map_projection(item->map);
 308         }
 309         return ret;
 310 }
 311
 312 static void
 313 search_list_house_number_destroy(struct search_list_house_number *this_)
 314 {
 315         map_convert_free(this_->house_number);
 316         search_list_common_destroy(&this_->common);
 317         if (this_->common.c)
 318                 g_free(this_->common.c);
 319         g_free(this_);
 320 }
 321
 322 static void
 323 search_list_result_destroy(int level, void *p)
 324 {
 325         switch (level) {
 326         case 0:
 327                 search_list_country_destroy(p);
 328                 break;
 329         case 1:
 330                 search_list_town_destroy(p);
 331                 break;
 332         case 2:
 333                 search_list_street_destroy(p);
 334                 break;
 335         case 3:
 336                 search_list_house_number_destroy(p);
 337                 break;
 338         }
 339 }
 340
 341 static void
 342 search_list_search_free(struct search_list *sl, int level)
 343 {
 344         struct search_list_level *le=&sl->levels[level];
 345         GList *next,*curr;
 346         if (le->search) {
 347                 mapset_search_destroy(le->search);
 348                 le->search=NULL;
 349         }
 350 #if 0 /* FIXME */
 351         if (le->hash) {
 352                 g_hash_table_destroy(le->hash);
 353                 le->hash=NULL;
 354         }
 355 #endif
 356         curr=le->list;
 357         while (curr) {
 358                 search_list_result_destroy(level, curr->data);
 359                 next=g_list_next(curr);
 360                 curr=next;
 361         }
 362         attr_free(le->attr);
 363         g_list_free(le->list);
 364         le->list=NULL;
 365         le->curr=NULL;
 366         le->last=NULL;
 367
 368 }
 369
 370 static char *
 371 postal_merge(char *mask, char *new)
 372 {
 373         dbg(1,"enter %s %s\n", mask, new);
 374         int i;
 375         char *ret=NULL;
 376         if (!new)
 377                 return NULL;
 378         if (!mask)
 379                 return g_strdup(new);
 380         i=0;
 381         while (mask[i] && new[i]) {
 382                 if (mask[i] != '.' && mask[i] != new[i])
 383                         break;
 384                 i++;
 385
 386         }
 387         if (mask[i]) {
 388                 ret=g_strdup(mask);
 389                 while (mask[i])
 390                         ret[i++]='.';
 391         }
 392         dbg(1,"merged %s with %s as %s\n", mask, new, ret);
 393         return ret;
 394 }
 395
 396 static int
 397 search_add_result(struct search_list_level *le, struct search_list_common *slc)
 398 {
 399         struct search_list_common *slo;
 400         char *merged;
 401         slo=g_hash_table_lookup(le->hash, &slc->unique);
 402         if (!slo) {
 403                 g_hash_table_insert(le->hash, &slc->unique, slc);
 404                 if (slc->postal && !slc->postal_mask) {
 405                         slc->postal_mask=g_strdup(slc->postal);
 406                 }
 407                 le->list=g_list_append(le->list, slc);
 408                 return 1;
 409         }
 410         merged=postal_merge(slo->postal_mask, slc->postal);
 411         if (merged) {
 412                 g_free(slo->postal_mask);
 413                 slo->postal_mask=merged;
 414         }
 415         return 0;
 416 }
 417
 418 struct search_list_result *
 419 search_list_get_result(struct search_list *this_)
 420 {
 421         struct search_list_level *le,*leu;
 422         struct item *item;
 423         int level=this_->level;
 424
 425         dbg(1,"enter\n");
 426         le=&this_->levels[level];
 427         dbg(1,"le=%p\n", le);
 428         for (;;) {
 429                 dbg(1,"le->search=%p\n", le->search);
 430                 if (! le->search) {
 431                         dbg(1,"partial=%d level=%d\n", le->partial, level);
 432                         if (! level)
 433                                 le->parent=NULL;
 434                         else {
 435                                 leu=&this_->levels[level-1];
 436                                 dbg(1,"leu->curr=%p\n", leu->curr);
 437                                 for (;;) {
 438                                         struct search_list_common *slc;
 439                                         if (! leu->curr)
 440                                                 return NULL;
 441                                         le->parent=leu->curr->data;
 442                                         leu->last=leu->curr;
 443                                         leu->curr=g_list_next(leu->curr);
 444                                         slc=(struct search_list_common *)(le->parent);
 445                                         if (!slc)
 446                                                 break;
 447                                         if (slc->selected == leu->selected)
 448                                                 break;
 449                                 }
 450                         }
 451                         if (le->parent)
 452                                 dbg(1,"mapset_search_new with item(%d,%d)\n", le->parent->item.id_hi, le->parent->item.id_lo);
 453                         dbg(1,"attr=%s\n", attr_to_name(le->attr->type));
 454                         le->search=mapset_search_new(this_->ms, &le->parent->item, le->attr, le->partial);
 455                         le->hash=g_hash_table_new(search_item_hash_hash, search_item_hash_equal);
 456                 }
 457                 dbg(1,"le->search=%p\n", le->search);
 458                 item=mapset_search_get_item(le->search);
 459                 dbg(1,"item=%p\n", item);
 460                 if (item) {
 461                         void *p=NULL;
 462                         dbg(1,"id_hi=%d id_lo=%d\n", item->id_hi, item->id_lo);
 463                         this_->result.country=NULL;
 464                         this_->result.town=NULL;
 465                         this_->result.street=NULL;
 466                         this_->result.c=NULL;
 467                         switch (level) {
 468                         case 0:
 469                                 p=search_list_country_new(item);
 470                                 this_->result.country=p;
 471                                 this_->result.country->common.parent=NULL;
 472                                 break;
 473                         case 1:
 474                                 p=search_list_town_new(item);
 475                                 this_->result.town=p;
 476                                 this_->result.town->common.parent=this_->levels[0].last->data;
 477                                 this_->result.country=this_->result.town->common.parent;
 478                                 this_->result.c=this_->result.town->common.c;
 479                                 break;
 480                         case 2:
 481                                 p=search_list_street_new(item);
 482                                 this_->result.street=p;
 483                                 this_->result.street->common.parent=this_->levels[1].last->data;
 484                                 this_->result.town=this_->result.street->common.parent;
 485                                 this_->result.country=this_->result.town->common.parent;
 486                                 this_->result.c=this_->result.street->common.c;
 487                                 break;
 488                         case 3:
 489                                 p=search_list_house_number_new(item);
 490                                 this_->result.house_number=p;
 491                                 this_->result.house_number->common.parent=this_->levels[2].last->data;
 492                                 this_->result.street=this_->result.house_number->common.parent;
 493                                 this_->result.town=this_->result.street->common.parent;
 494                                 this_->result.country=this_->result.town->common.parent;
 495                                 this_->result.c=this_->result.house_number->common.c;
 496
 497                         }
 498                         if (p) {
 499                                 if (search_add_result(le, p)) {
 500                                         this_->result.id++;
 501                                         return &this_->result;
 502                                 } else
 503                                         search_list_result_destroy(level, p);
 504                         }
 505                 } else {
 506                         mapset_search_destroy(le->search);
 507                         le->search=NULL;
 508                         g_hash_table_destroy(le->hash);
 509                         if (! level)
 510                                 break;
 511                 }
 512         }
 513         return NULL;
 514 }
 515
 516 void
 517 search_list_destroy(struct search_list *this_)
 518 {
 519         g_free(this_);
 520 }
 521
 522 void
 523 search_init(void)
 524 {
 525 }
 526
 527 #if 0
 528 static char *
 529 search_fix_spaces(char *str)
 530 {
 531         int i;
 532         int len=strlen(str);
 533         char c,*s,*d,*ret=g_strdup(str);
 534
 535         for (i = 0 ; i < len ; i++) {
 536                 if (ret[i] == ',' || ret[i] == ',' || ret[i] == '/')
 537                         ret[i]=' ';
 538         }
 539         s=ret;
 540         d=ret;
 541         len=0;
 542         do {
 543                 c=*s++;
 544                 if (c != ' ' || len != 0) {
 545                         *d++=c;
 546                         len++;
 547                 }
 548                 while (c == ' ' && *s == ' ')
 549                         s++;
 550                 if (c == ' ' && *s == '\0') {
 551                         d--;
 552                         len--;
 553                 }
 554         } while (c);
 555         return ret;
 556 }
 557
 558 static GList *
 559 search_split_phrases(char *str)
 560 {
 561         char *tmp,*s,*d;
 562         s=str;
 563         GList *ret=NULL;
 564         do {
 565                 tmp=g_strdup(s);
 566                 d=tmp+strlen(s)-1;
 567                 ret=g_list_append(ret, g_strdup(s));
 568                 while (d >= tmp) {
 569                         if (*d == ' ') {
 570                                 *d = '\0';
 571                                 ret=g_list_append(ret, g_strdup(tmp));
 572                         }
 573                         d--;
 574                 }
 575                 g_free(tmp);
 576                 do {
 577                         s++;
 578                         if (*s == ' ') {
 579                                 s++;
 580                                 break;
 581                         }
 582                 } while (*s != '\0');
 583         } while (*s != '\0');
 584         return ret;
 585 }
 586
 587 static void
 588 search_address_housenumber(struct search_list *sl, GList *phrases, GList *exclude1, GList *exclude2, GList *exclude3)
 589 {
 590         struct search_list_result *slr;
 591         GList *tmp=phrases;
 592         int count=0;
 593         struct attr attr;
 594         attr.type=attr_street_name;
 595         while (slr=search_list_get_result(sl)) {
 596                 dbg(0,"%p\n",slr);
 597                 dbg(0,"%p %p\n",slr->country,slr->town);
 598                 dbg(0,"%s %s %s %s %s\n",slr->country->car,slr->town->common.postal,slr->town->name,slr->town->district,slr->street->name);
 599                 count++;
 600         }
 601         if (!count)
 602                 return;
 603         dbg(0,"count %d\n",count);
 604         while (tmp) {
 605                 if (tmp != exclude1 && tmp != exclude2 && tmp != exclude3) {
 606                         attr.type=attr_house_number;
 607                         attr.u.str=tmp->data;
 608                         search_list_search(sl, &attr, 0);
 609                         while (slr=search_list_get_result(sl)) {
 610                                 dbg(0,"result %s %s(%s) %s %s\n",slr->house_number->common.postal,slr->house_number->common.town_name, slr->house_number->common.district_name,slr->street->name,slr->house_number->house_number);
 611                         }
 612
 613                 }
 614                 tmp=g_list_next(tmp);
 615         }
 616 }
 617 static void
 618 search_address_street(struct search_list *sl, GList *phrases, GList *exclude1, GList *exclude2)
 619 {
 620         struct search_list_result *slr;
 621         GList *tmp=phrases;
 622         int count=0;
 623         struct attr attr;
 624         attr.type=attr_street_name;
 625         while (slr=search_list_get_result(sl)) {
 626 #if 0
 627                 dbg(0,"%s %s %s %s",slr->country->car,slr->town->name,slr->town->district,slr->street->name);
 628 #endif
 629                 dbg(0,"%s %s %s %s\n",slr->country->car,slr->town->common.postal,slr->town->name,slr->town->district);
 630                 count++;
 631         }
 632         if (!count)
 633                 return;
 634         dbg(0,"count %d\n",count);
 635         while (tmp) {
 636                 if (tmp != exclude1 && tmp != exclude2) {
 637                         attr.u.str=tmp->data;
 638                         search_list_search(sl, &attr, 0);
 639                         search_address_housenumber(sl, phrases, exclude1, exclude2, tmp);
 640                 }
 641                 tmp=g_list_next(tmp);
 642         }
 643 }
 644
 645 static void
 646 search_address_town(struct search_list *sl, GList *phrases, GList *exclude)
 647 {
 648         GList *tmp=phrases;
 649         int count=0;
 650         struct attr attr;
 651         attr.type=attr_town_or_district_name;
 652         while (search_list_get_result(sl))
 653                 count++;
 654         if (!count)
 655                 return;
 656         dbg(0,"count %d\n",count);
 657         while (tmp) {
 658                 if (tmp != exclude) {
 659                         attr.u.str=tmp->data;
 660                         search_list_search(sl, &attr, 0);
 661                         search_address_street(sl, phrases, exclude, tmp);
 662                 }
 663                 tmp=g_list_next(tmp);
 664         }
 665 }
 666
 667 void
 668 search_by_address(struct mapset *ms, char *addr)
 669 {
 670         char *str=search_fix_spaces(addr);
 671         GList *tmp,*phrases=search_split_phrases(str);
 672         dbg(0,"enter %s\n",addr);
 673         struct search_list *sl;
 674         struct search_list_result *slr;
 675         struct attr attr;
 676         attr.type=attr_country_all;
 677         tmp=phrases;
 678         sl=search_list_new(ms);
 679         while (tmp) {
 680                 attr.u.str=tmp->data;
 681                 search_list_search(sl, &attr, 0);
 682                 search_address_town(sl, phrases, tmp);
 683                 tmp=g_list_next(tmp);
 684         }
 685         search_list_search(sl, country_default(), 0);
 686         search_address_town(sl, phrases, NULL);
 687
 688         g_free(str);
 689 }
 690 #endif
 691