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