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