navit/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 <stdlib.h>
  21 #include <glib.h>
  22 #include <string.h>
  23 #include <math.h>
  24 #include "debug.h"
  25 #include "projection.h"
  26 #include "item.h"
  27 #include "map.h"
  28 #include "mapset.h"
  29 #include "coord.h"
  30 #include "transform.h"
  31 #include "search.h"
  32 #include "country.h"
  33 #include "linguistics.h"
  34
  35 #if HAVE_API_ANDROID
  36 #include "android.h"
  37 #endif
  38 #include "layout.h"
  39
  40 static struct search_list_result *search_list_result_dup(struct search_list_result *slr);
  41 static void search_list_country_destroy(struct search_list_country *this_);
  42 static void search_list_town_destroy(struct search_list_town *this_);
  43 static void search_list_street_destroy(struct search_list_street *this_);
  44 static void search_list_house_number_destroy(struct search_list_house_number *this_);
  45
  46 struct search_list_level {
  47         struct mapset *ms;
  48         struct search_list_common *parent;
  49         struct attr *attr;
  50         int partial;
  51         int selected;
  52         struct mapset_search *search;
  53         GHashTable *hash;
  54         GList *list,*curr,*last;
  55 };
  56
  57 struct interpolation {
  58         int side, mode, rev;
  59         char *first, *last, *curr;
  60 };
  61
  62 struct search_list {
  63         struct mapset *ms;
  64         struct item *item;
  65         int level;
  66         struct search_list_level levels[4];
  67         struct search_list_result result;
  68         struct search_list_result last_result;
  69         int last_result_valid;
  70         char *postal;
  71         struct interpolation inter;
  72         int use_address_results;
  73         GList *address_results,*address_results_pos;
  74 };
  75
  76 static guint
  77 search_item_hash_hash(gconstpointer key)
  78 {
  79         const struct item *itm=key;
  80         gconstpointer hashkey=(gconstpointer)GINT_TO_POINTER(itm->id_hi^itm->id_lo);
  81         return g_direct_hash(hashkey);
  82 }
  83
  84 static gboolean
  85 search_item_hash_equal(gconstpointer a, gconstpointer b)
  86 {
  87         const struct item *itm_a=a;
  88         const struct item *itm_b=b;
  89         if (item_is_equal_id(*itm_a, *itm_b))
  90                 return TRUE;
  91         return FALSE;
  92 }
  93
  94 /**
  95  * @brief Create new instance of search_list to run a search.
  96  *
  97  * @param ms mapset that is to be searched
  98  * @returns new search_list
  99  */
 100 struct search_list *
 101 search_list_new(struct mapset *ms)
 102 {
 103         struct search_list *ret;
 104
 105         ret=g_new0(struct search_list, 1);
 106         ret->ms=ms;
 107
 108         return ret;
 109 }
 110
 111 static void search_list_search_free(struct search_list *sl, int level);
 112
 113 /**
 114  * @brief Determine search list level for given attr_type.
 115  * @param attr_type attribute value
 116  * @return corresponding search list level (country=0, town=1, ...)
 117  */
 118 int
 119 search_list_level(enum attr_type attr_type)
 120 {
 121         switch(attr_type) {
 122         case attr_country_all:
 123         case attr_country_id:
 124         case attr_country_iso2:
 125         case attr_country_iso3:
 126         case attr_country_car:
 127         case attr_country_name:
 128                 return 0;
 129         case attr_town_postal:
 130                 return 1;
 131         case attr_town_name:
 132         case attr_district_name:
 133         case attr_town_or_district_name:
 134                 return 1;
 135         case attr_street_name:
 136                 return 2;
 137         case attr_house_number:
 138                 return 3;
 139         case attr_postal:
 140                 return -1;
 141         default:
 142                 dbg(0,"unknown search '%s'\n",attr_to_name(attr_type));
 143                 return -1;
 144         }
 145 }
 146
 147 static void
 148 interpolation_clear(struct interpolation *inter)
 149 {
 150         inter->mode=inter->side=0;
 151         g_free(inter->first);
 152         g_free(inter->last);
 153         g_free(inter->curr);
 154         inter->first=inter->last=inter->curr=NULL;
 155 }
 156
 157 static char *
 158 search_fix_spaces(char *str)
 159 {
 160         int i;
 161         int len=strlen(str);
 162         char c,*s,*d,*ret=g_strdup(str);
 163
 164         for (i = 0 ; i < len ; i++) {
 165                 if (ret[i] == ',' || ret[i] == ',' || ret[i] == '/')
 166                         ret[i]=' ';
 167         }
 168         s=ret;
 169         d=ret;
 170         len=0;
 171         do {
 172                 c=*s++;
 173                 if (c != ' ' || len != 0) {
 174                         *d++=c;
 175                         len++;
 176                 }
 177                 while (c == ' ' && *s == ' ')
 178                         s++;
 179                 if (c == ' ' && *s == '\0') {
 180                         d--;
 181                         len--;
 182                 }
 183         } while (c);
 184         return ret;
 185 }
 186
 187 struct phrase {
 188         char *start;
 189         char *end;
 190         int wordcount;
 191 };
 192
 193 static GList *
 194 search_split_phrases(char *str)
 195 {
 196         char *s,*d;
 197         int wordcount=0;
 198         GList *ret=NULL;
 199         s=str;
 200         do {
 201                 d=s;
 202                 wordcount=0;
 203                 do {
 204                         d++;
 205                         if (*d == ' ' || *d == '\0') {
 206                                 struct phrase *phrase=g_new(struct phrase, 1);
 207                                 phrase->start=s;
 208                                 phrase->end=d;
 209                                 phrase->wordcount=++wordcount;
 210                                 ret=g_list_append(ret, phrase);
 211                         }
 212                 } while (*d != '\0');
 213                 do {
 214                         s++;
 215                         if (*s == ' ') {
 216                                 s++;
 217                                 break;
 218                         }
 219                 } while (*s != '\0');
 220         } while (*s != '\0');
 221         return ret;
 222 }
 223
 224 static char *
 225 search_phrase_str(struct phrase *p)
 226 {
 227         int len=p->end-p->start;
 228         char *ret=g_malloc(len+1);
 229         strncpy(ret, p->start, len);
 230         ret[len]='\0';
 231         return ret;
 232 }
 233
 234 static int
 235 search_phrase_used(struct phrase *p, GList *used_phrases)
 236 {
 237         while (used_phrases) {
 238                 struct phrase *pu=used_phrases->data;
 239                 dbg(1,"'%s'-'%s' vs '%s'-'%s'\n",p->start,p->end,pu->start,pu->end);
 240                 if (p->start < pu->end && p->end > pu->start)
 241                         return 1;
 242                 dbg(1,"unused\n");
 243                 used_phrases=g_list_next(used_phrases);
 244         }
 245         return 0;
 246 }
 247
 248 static gint
 249 search_by_address_compare(gconstpointer a, gconstpointer b)
 250 {
 251         const struct search_list_result *slra=a;
 252         const struct search_list_result *slrb=b;
 253         return slrb->id-slra->id;
 254 }
 255
 256
 257 static GList *
 258 search_by_address_attr(GList *results, struct search_list *sl, GList *phrases, GList *exclude, enum attr_type attr_type, int wordcount)
 259 {
 260         GList *tmp=phrases;
 261         struct attr attr;
 262         attr.type=attr_type;
 263         while (tmp) {
 264                 if (!search_phrase_used(tmp->data, exclude)) {
 265                         struct phrase *p=tmp->data;
 266                         int count=0,wordcount_all=wordcount+p->wordcount;
 267                         struct search_list_result *slr;
 268                         attr.u.str=search_phrase_str(p);
 269                         dbg(1,"%s phrase '%s'\n",attr_to_name(attr_type),attr.u.str);
 270                         search_list_search(sl, &attr, 0);
 271                         while ((slr=search_list_get_result(sl))) {
 272                                 if (attr_type != attr_country_all) {
 273                                         struct search_list_result *slrd=search_list_result_dup(slr);
 274                                         slrd->id=wordcount_all;
 275                                         results=g_list_insert_sorted(results, slrd, search_by_address_compare);
 276                                 }
 277                                 count++;
 278                         }
 279                         dbg(1,"%d results wordcount %d\n",count,wordcount_all);
 280                         if (count) {
 281                                 GList *used=g_list_prepend(g_list_copy(exclude), tmp->data);
 282                                 enum attr_type new_attr_type=attr_none;
 283                                 switch (attr_type) {
 284                                 case attr_country_all:
 285                                         new_attr_type=attr_town_or_district_name;
 286                                         break;
 287                                 case attr_town_or_district_name:
 288                                         new_attr_type=attr_street_name;
 289                                         break;
 290                                 case attr_street_name:
 291                                         new_attr_type=attr_house_number;
 292                                         break;
 293                                 default:
 294                                         break;
 295                                 }
 296                                 if (new_attr_type != attr_none)
 297                                         results=search_by_address_attr(results, sl, phrases, used, new_attr_type, wordcount_all);
 298                                 g_list_free(used);
 299                         }
 300                         g_free(attr.u.str);
 301                 }
 302                 tmp=g_list_next(tmp);
 303         }
 304         return results;
 305 }
 306
 307 static void
 308 search_by_address(struct search_list *this_, char *addr)
 309 {
 310         char *str=search_fix_spaces(addr);
 311         GList *tmp,*phrases=search_split_phrases(str);
 312         struct search_list *sl=search_list_new(this_->ms);
 313         this_->address_results=search_by_address_attr(NULL, sl, phrases, NULL, attr_country_all, 0);
 314         this_->address_results_pos=this_->address_results;
 315         search_list_destroy(sl);
 316         tmp=phrases;
 317         while (tmp) {
 318                 g_free(tmp->data);
 319                 tmp=g_list_next(tmp);
 320         }
 321         g_list_free(phrases);
 322 }
 323
 324 static void
 325 search_address_results_free(struct search_list *this_)
 326 {
 327         GList *tmp;
 328         tmp=this_->address_results;
 329         while (tmp) {
 330                 struct search_list_result *slr=tmp->data;
 331                 if (slr->country);
 332                         search_list_country_destroy(slr->country);
 333                 if (slr->town)
 334                         search_list_town_destroy(slr->town);
 335                 if (slr->street)
 336                         search_list_street_destroy(slr->street);
 337                 if (slr->house_number)
 338                         search_list_house_number_destroy(slr->house_number);
 339                 if (slr->c)
 340                         g_free(slr->c);
 341                 g_free(slr);
 342                 tmp=g_list_next(tmp);
 343         }
 344         g_list_free(this_->address_results);
 345         this_->address_results=this_->address_results_pos=NULL;
 346 }
 347
 348 /**
 349  * @brief Start a search.
 350  *
 351  * @param this search_list to use for the search
 352  * @param search_attr attributes to use for the search
 353  * @param partial do partial search? (1=yes,0=no)
 354  */
 355 void
 356 search_list_search(struct search_list *this_, struct attr *search_attr, int partial)
 357 {
 358         struct search_list_level *le;
 359         int level;
 360         search_address_results_free(this_);
 361         if (search_attr->type == attr_address) {
 362                 search_by_address(this_, search_attr->u.str);
 363                 this_->use_address_results=1;
 364                 return;
 365         }
 366         this_->use_address_results=0;
 367         level=search_list_level(search_attr->type);
 368         this_->item=NULL;
 369         interpolation_clear(&this_->inter);
 370         //dbg(0,"level=%d\n", level);
 371         if (level != -1) {
 372                 this_->result.id=0;
 373                 this_->level=level;
 374                 le=&this_->levels[level];
 375                 search_list_search_free(this_, level);
 376                 le->attr=attr_dup(search_attr);
 377                 le->partial=partial;
 378                 if (level > 0) {
 379                         le=&this_->levels[level-1];
 380                         le->curr=le->list;
 381                 }
 382                 //dbg(0,"le=%p partial=%d\n", le, partial);
 383         } else if (search_attr->type == attr_postal) {
 384                 g_free(this_->postal);
 385                 this_->postal=g_strdup(search_attr->u.str);
 386         }
 387 }
 388
 389 struct search_list_common *
 390 search_list_select(struct search_list *this_, enum attr_type attr_type, int id, int mode)
 391 {
 392         int level=search_list_level(attr_type);
 393         int num=0;
 394         struct search_list_level *le;
 395         struct search_list_common *slc;
 396         GList *curr;
 397         le=&this_->levels[level];
 398         curr=le->list;
 399         if (mode > 0 || !id)
 400                 le->selected=mode;
 401         //dbg(0,"enter level=%d %d %d %p\n", level, id, mode, curr);
 402         while (curr) {
 403                 num++;
 404                 if (! id || num == id) {
 405                         slc=curr->data;
 406                         slc->selected=mode;
 407                         if (id) {
 408                                 le->last=curr;
 409                                 //dbg(0,"found\n");
 410                                 return slc;
 411                         }
 412                 }
 413                 curr=g_list_next(curr);
 414         }
 415         //dbg(0,"not found\n");
 416         return NULL;
 417 }
 418
 419 static void
 420 search_list_common_new(struct item *item, struct search_list_common *common)
 421 {
 422         struct attr attr;
 423         if (item_attr_get(item, attr_town_name, &attr))
 424                 common->town_name=map_convert_string(item->map, attr.u.str);
 425         else
 426                 common->town_name=NULL;
 427         if (item_attr_get(item, attr_county_name, &attr))
 428                 common->county_name=map_convert_string(item->map, attr.u.str);
 429         else
 430                 common->county_name=NULL;
 431         if (item_attr_get(item, attr_district_name, &attr))
 432                 common->district_name=map_convert_string(item->map, attr.u.str);
 433         else
 434                 common->district_name=NULL;
 435         if (item_attr_get(item, attr_postal, &attr))
 436                 common->postal=map_convert_string(item->map, attr.u.str);
 437         else if (item_attr_get(item, attr_town_postal, &attr))
 438                 common->postal=map_convert_string(item->map, attr.u.str);
 439         else
 440                 common->postal=NULL;
 441         if (item_attr_get(item, attr_postal_mask, &attr))
 442                 common->postal_mask=map_convert_string(item->map, attr.u.str);
 443         else
 444                 common->postal_mask=NULL;
 445 }
 446
 447 static void
 448 search_list_common_dup(struct search_list_common *src, struct search_list_common *dst)
 449 {
 450         dst->town_name=map_convert_dup(src->town_name);
 451         dst->district_name=map_convert_dup(src->district_name);
 452         dst->county_name=map_convert_dup(src->county_name);
 453         dst->postal=map_convert_dup(src->postal);
 454         dst->postal_mask=map_convert_dup(src->postal_mask);
 455         if (src->c) {
 456                 dst->c=g_new(struct pcoord, 1);
 457                 *dst->c=*src->c;
 458         } else
 459                 dst->c=NULL;
 460 }
 461
 462 static void
 463 search_list_common_destroy(struct search_list_common *common)
 464 {
 465         map_convert_free(common->town_name);
 466         map_convert_free(common->district_name);
 467         map_convert_free(common->county_name);
 468         map_convert_free(common->postal);
 469         map_convert_free(common->postal_mask);
 470         if (common->c)
 471                 g_free(common->c);
 472         common->town_name=NULL;
 473         common->district_name=NULL;
 474         common->county_name=NULL;
 475         common->postal=NULL;
 476         common->postal_mask=NULL;
 477         common->c=NULL;
 478 }
 479
 480 static struct search_list_country *
 481 search_list_country_new(struct item *item)
 482 {
 483         struct search_list_country *ret=g_new0(struct search_list_country, 1);
 484         struct attr attr;
 485
 486         ret->common.item=ret->common.unique=*item;
 487         if (item_attr_get(item, attr_country_car, &attr))
 488                 ret->car=g_strdup(attr.u.str);
 489         if (item_attr_get(item, attr_country_iso2, &attr)) {
 490 #if HAVE_API_ANDROID
 491                 ret->iso2=g_malloc(strlen(attr.u.str)+1);
 492                 strtolower(ret->iso2, attr.u.str);
 493 #else
 494                 ret->iso2=g_strdup(attr.u.str);
 495 #endif
 496                 ret->flag=g_strdup_printf("country_%s", ret->iso2);
 497         }
 498         if (item_attr_get(item, attr_country_iso3, &attr))
 499                 ret->iso3=g_strdup(attr.u.str);
 500         if (item_attr_get(item, attr_country_name, &attr))
 501                 ret->name=g_strdup(attr.u.str);
 502         return ret;
 503 }
 504
 505 static struct search_list_country *
 506 search_list_country_dup(struct search_list_country *this_)
 507 {
 508         struct search_list_country *ret=g_new(struct search_list_country, 1);
 509         ret->car=g_strdup(this_->car);
 510         ret->iso2=g_strdup(this_->iso2);
 511         ret->iso3=g_strdup(this_->iso3);
 512         ret->flag=g_strdup(this_->flag);
 513         ret->name=g_strdup(this_->name);
 514         return ret;
 515 }
 516
 517 static void
 518 search_list_country_destroy(struct search_list_country *this_)
 519 {
 520         g_free(this_->car);
 521         g_free(this_->iso2);
 522         g_free(this_->iso3);
 523         g_free(this_->flag);
 524         g_free(this_->name);
 525         g_free(this_);
 526 }
 527
 528 static struct search_list_town *
 529 search_list_town_new(struct item *item)
 530 {
 531         struct search_list_town *ret=g_new0(struct search_list_town, 1);
 532         struct attr attr;
 533         struct coord c;
 534
 535         ret->itemt=*item;
 536         ret->common.item=ret->common.unique=*item;
 537         if (item_attr_get(item, attr_town_streets_item, &attr)) {
 538                 dbg(1,"town_assoc 0x%x 0x%x\n", attr.u.item->id_hi, attr.u.item->id_lo);
 539                 ret->common.unique=*attr.u.item;
 540         }
 541         search_list_common_new(item, &ret->common);
 542         if (item_attr_get(item, attr_county_name, &attr))
 543                 ret->county=map_convert_string(item->map,attr.u.str);
 544         else
 545                 ret->county=NULL;
 546         if (item_coord_get(item, &c, 1)) {
 547                 ret->common.c=g_new(struct pcoord, 1);
 548                 ret->common.c->x=c.x;
 549                 ret->common.c->y=c.y;
 550                 ret->common.c->pro = map_projection(item->map);
 551         }
 552         return ret;
 553 }
 554
 555 static struct search_list_town *
 556 search_list_town_dup(struct search_list_town *this_)
 557 {
 558         struct search_list_town *ret=g_new0(struct search_list_town, 1);
 559         ret->county=map_convert_dup(this_->county);
 560         search_list_common_dup(&this_->common, &ret->common);
 561         return ret;
 562 }
 563
 564 static void
 565 search_list_town_destroy(struct search_list_town *this_)
 566 {
 567         map_convert_free(this_->county);
 568         search_list_common_destroy(&this_->common);
 569         g_free(this_);
 570 }
 571
 572
 573 static struct search_list_street *
 574 search_list_street_new(struct item *item)
 575 {
 576         struct search_list_street *ret=g_new0(struct search_list_street, 1);
 577         struct attr attr;
 578         struct coord c;
 579
 580         ret->common.item=ret->common.unique=*item;
 581         if (item_attr_get(item, attr_street_name, &attr))
 582                 ret->name=map_convert_string(item->map, attr.u.str);
 583         else
 584                 ret->name=NULL;
 585         search_list_common_new(item, &ret->common);
 586         if (item_coord_get(item, &c, 1)) {
 587                 ret->common.c=g_new(struct pcoord, 1);
 588                 ret->common.c->x=c.x;
 589                 ret->common.c->y=c.y;
 590                 ret->common.c->pro = map_projection(item->map);
 591         }
 592         return ret;
 593 }
 594
 595 static struct search_list_street *
 596 search_list_street_dup(struct search_list_street *this_)
 597 {
 598         struct search_list_street *ret=g_new0(struct search_list_street, 1);
 599         ret->name=map_convert_dup(this_->name);
 600         search_list_common_dup(&this_->common, &ret->common);
 601         return ret;
 602 }
 603
 604 static void
 605 search_list_street_destroy(struct search_list_street *this_)
 606 {
 607         map_convert_free(this_->name);
 608         search_list_common_destroy(&this_->common);
 609         g_free(this_);
 610 }
 611
 612 static char *
 613 search_interpolate(struct interpolation *inter)
 614 {
 615         dbg(1,"interpolate %s-%s %s\n",inter->first,inter->last,inter->curr);
 616         if (!inter->first || !inter->last)
 617                 return NULL;
 618         if (!inter->curr)
 619                 inter->curr=g_strdup(inter->first);
 620         else {
 621                 if (strcmp(inter->curr, inter->last)) {
 622                         int next=atoi(inter->curr)+(inter->mode?2:1);
 623                         g_free(inter->curr);
 624                         if (next == atoi(inter->last))
 625                                 inter->curr=g_strdup(inter->last);
 626                         else
 627                                 inter->curr=g_strdup_printf("%d",next);
 628                 } else {
 629                         g_free(inter->curr);
 630                         inter->curr=NULL;
 631                 }
 632         }
 633         dbg(1,"interpolate result %s\n",inter->curr);
 634         return inter->curr;
 635 }
 636
 637 static void
 638 search_interpolation_split(char *str, struct interpolation *inter)
 639 {
 640         char *pos=strchr(str,'-');
 641         char *first,*last;
 642         int len;
 643         if (!pos) {
 644                 inter->first=g_strdup(str);
 645                 inter->last=g_strdup(str);
 646                 inter->rev=0;
 647                 return;
 648         }
 649         len=pos-str;
 650         first=g_malloc(len+1);
 651         strncpy(first, str, len);
 652         first[len]='\0';
 653         last=g_strdup(pos+1);
 654         dbg(1,"%s = %s - %s\n",str, first, last);
 655         if (atoi(first) > atoi(last)) {
 656                 inter->first=last;
 657                 inter->last=first;
 658                 inter->rev=1;
 659         } else {
 660                 inter->first=first;
 661                 inter->last=last;
 662                 inter->rev=0;
 663         }
 664 }
 665
 666 static int
 667 search_setup_interpolation(struct item *item, enum attr_type i0, enum attr_type i1, enum attr_type i2, struct interpolation *inter)
 668 {
 669         struct attr attr;
 670         g_free(inter->first);
 671         g_free(inter->last);
 672         g_free(inter->curr);
 673         inter->first=inter->last=inter->curr=NULL;
 674         dbg(1,"setup %s\n",attr_to_name(i0));
 675         if (item_attr_get(item, i0, &attr)) {
 676                 search_interpolation_split(attr.u.str, inter);
 677                 inter->mode=0;
 678         } else if (item_attr_get(item, i1, &attr)) {
 679                 search_interpolation_split(attr.u.str, inter);
 680                 inter->mode=1;
 681         } else if (item_attr_get(item, i2, &attr)) {
 682                 search_interpolation_split(attr.u.str, inter);
 683                 inter->mode=2;
 684         } else
 685                 return 0;
 686         return 1;
 687 }
 688
 689 static int
 690 search_match(char *str, char *search, int partial)
 691 {
 692         if (!partial)
 693                 return (!g_strcasecmp(str, search));
 694         else
 695                 return (!g_strncasecmp(str, search, strlen(search)));
 696 }
 697
 698 static struct pcoord *
 699 search_house_number_coordinate(struct item *item, struct interpolation *inter)
 700 {
 701         struct pcoord *ret=g_new(struct pcoord, 1);
 702         ret->pro = map_projection(item->map);
 703         dbg(1,"%s\n",item_to_name(item->type));
 704         if (item->type<type_house_number_interpolation_even || item->type>type_house_number_interpolation_alphabetic) {
 705                 struct coord c;
 706                 if (item_coord_get(item, &c, 1)) {
 707                         ret->x=c.x;
 708                         ret->y=c.y;
 709                 } else {
 710                         g_free(ret);
 711                         ret=NULL;
 712                 }
 713         } else {
 714                 int count,max=1024;
 715                 int hn_pos,hn_length;
 716                 struct coord *c=g_alloca(sizeof(struct coord)*max);
 717                 item_coord_rewind(item);
 718                 count=item_coord_get(item, c, max);
 719                 hn_length=atoi(inter->last)-atoi(inter->first);
 720                 if (inter->rev)
 721                         hn_pos=atoi(inter->last)-atoi(inter->curr);
 722                 else
 723                         hn_pos=atoi(inter->curr)-atoi(inter->first);
 724                 if (count) {
 725                         int i,distance_sum=0,hn_distance;
 726                         int *distances=g_alloca(sizeof(int)*(count-1));
 727                         dbg(1,"count=%d hn_length=%d hn_pos=%d (%s of %s-%s)\n",count,hn_length,hn_pos,inter->curr,inter->first,inter->last);
 728                         if (!hn_length) {
 729                                 hn_length=2;
 730                                 hn_pos=1;
 731                         }
 732                         if (count == max)
 733                                 dbg(0,"coordinate overflow\n");
 734                         for (i = 0 ; i < count-1 ; i++) {
 735                                 distances[i]=navit_sqrt(transform_distance_sq(&c[i],&c[i+1]));
 736                                 distance_sum+=distances[i];
 737                                 dbg(1,"distance[%d]=%d\n",i,distances[i]);
 738                         }
 739                         dbg(1,"sum=%d\n",distance_sum);
 740                         hn_distance=distance_sum*hn_pos/hn_length;
 741                         dbg(1,"hn_distance=%d\n",hn_distance);
 742                         i=0;
 743                         while (i < count-1 && hn_distance > distances[i])
 744                                 hn_distance-=distances[i++];
 745                         dbg(1,"remaining distance=%d from %d\n",hn_distance,distances[i]);
 746                         ret->x=(c[i+1].x-c[i].x)*hn_distance/distances[i]+c[i].x;
 747                         ret->y=(c[i+1].y-c[i].y)*hn_distance/distances[i]+c[i].y;
 748                         g_free(distances);
 749                 }
 750                 g_free(c);
 751         }
 752         return ret;
 753 }
 754
 755 static struct search_list_house_number *
 756 search_list_house_number_new(struct item *item, struct interpolation *inter, char *inter_match, int inter_partial)
 757 {
 758         struct search_list_house_number *ret=g_new0(struct search_list_house_number, 1);
 759         struct attr attr;
 760         char *hn;
 761
 762         ret->common.item=ret->common.unique=*item;
 763         //if (item_attr_get(item, attr_street_name, &attr))
 764         //      dbg(0,"xx1 %s\n",attr.u.str);
 765         if (item_attr_get(item, attr_house_number, &attr))
 766                 ret->house_number=map_convert_string(item->map, attr.u.str);
 767         else {
 768                 //if (item_attr_get(item, attr_street_name, &attr))
 769                 //      dbg(0,"xx2 %s\n",attr.u.str);
 770                 for (;;) {
 771                         //dbg(0,"interpolate 11");
 772                         ret->interpolation=1;
 773                         switch(inter->side) {
 774                         case 0:
 775                                 //dbg(0,"interpolate 11 0");
 776                                 inter->side=-1;
 777                                 search_setup_interpolation(item, attr_house_number_left, attr_house_number_left_odd, attr_house_number_left_even, inter);
 778                         case -1:
 779                                 //dbg(0,"interpolate 11 -1");
 780                                 if ((hn=search_interpolate(inter)))
 781                                         break;
 782                                 inter->side=1;
 783                                 search_setup_interpolation(item, attr_house_number_right, attr_house_number_right_odd, attr_house_number_right_even, inter);
 784                         case 1:
 785                                 //dbg(0,"interpolate 11 1");
 786                                 if ((hn=search_interpolate(inter)))
 787                                         break;
 788                         default:
 789                                 //dbg(0,"interpolate 11 default");
 790                                 g_free(ret);
 791                                 return NULL;
 792                         }
 793                         if (search_match(hn, inter_match, inter_partial))
 794                         {
 795                                 //dbg(0,"interpolate 22");
 796                                 //dbg(0,"match %s %s-%s\n",hn, inter->first, inter->last);
 797                                 ret->house_number=map_convert_string(item->map, hn);
 798                                 break;
 799                         }
 800                 }
 801         }
 802         //dbg(0,"interpolate 33");
 803         search_list_common_new(item, &ret->common);
 804         ret->common.c=search_house_number_coordinate(item, ret->interpolation?inter:NULL);
 805         //dbg(0,"interpolate 44");
 806         return ret;
 807 }
 808
 809 static struct search_list_house_number *
 810 search_list_house_number_dup(struct search_list_house_number *this_)
 811 {
 812         struct search_list_house_number *ret=g_new0(struct search_list_house_number, 1);
 813         ret->house_number=map_convert_dup(this_->house_number);
 814         search_list_common_dup(&this_->common, &ret->common);
 815         return ret;
 816 }
 817
 818 static void
 819 search_list_house_number_destroy(struct search_list_house_number *this_)
 820 {
 821         map_convert_free(this_->house_number);
 822         search_list_common_destroy(&this_->common);
 823         g_free(this_);
 824 }
 825
 826 static void
 827 search_list_result_destroy(int level, void *p)
 828 {
 829         switch (level) {
 830         case 0:
 831                 search_list_country_destroy(p);
 832                 break;
 833         case 1:
 834                 search_list_town_destroy(p);
 835                 break;
 836         case 2:
 837                 search_list_street_destroy(p);
 838                 break;
 839         case 3:
 840                 search_list_house_number_destroy(p);
 841                 break;
 842         }
 843 }
 844
 845 static struct search_list_result *
 846 search_list_result_dup(struct search_list_result *slr)
 847 {
 848         struct search_list_result *ret=g_new0(struct search_list_result, 1);
 849         ret->id=slr->id;
 850         if (slr->c) {
 851                 ret->c=g_new(struct pcoord, 1);
 852                 *ret->c=*slr->c;
 853         }
 854         if (slr->country)
 855                 ret->country=search_list_country_dup(slr->country);
 856         if (slr->town)
 857                 ret->town=search_list_town_dup(slr->town);
 858         if (slr->street)
 859                 ret->street=search_list_street_dup(slr->street);
 860         if (slr->house_number)
 861                 ret->house_number=search_list_house_number_dup(slr->house_number);
 862         return ret;
 863 }
 864
 865 static void
 866 search_list_search_free(struct search_list *sl, int level)
 867 {
 868         struct search_list_level *le=&sl->levels[level];
 869         GList *next,*curr;
 870         if (le->search)
 871         {
 872                 mapset_search_destroy(le->search);
 873                 le->search=NULL;
 874         }
 875 #if 0 /* FIXME */
 876         if (le->hash) {
 877                 g_hash_table_destroy(le->hash);
 878                 le->hash=NULL;
 879         }
 880 #endif
 881         curr=le->list;
 882         while (curr)
 883         {
 884                 search_list_result_destroy(level, curr->data);
 885                 next=g_list_next(curr);
 886                 curr=next;
 887         }
 888         attr_free(le->attr);
 889         g_list_free(le->list);
 890         le->list=NULL;
 891         le->curr=NULL;
 892         le->last=NULL;
 893 }
 894
 895 char *
 896 search_postal_merge(char *mask, char *new)
 897 {
 898         int i;
 899         char *ret=NULL;
 900         dbg(1,"enter %s %s\n", mask, new);
 901         if (!new)
 902                 return NULL;
 903         if (!mask)
 904                 return g_strdup(new);
 905         i=0;
 906         while (mask[i] && new[i]) {
 907                 if (mask[i] != '.' && mask[i] != new[i])
 908                         break;
 909                 i++;
 910
 911         }
 912         if (mask[i]) {
 913                 ret=g_strdup(mask);
 914                 while (mask[i])
 915                         ret[i++]='.';
 916         }
 917         dbg(1,"merged %s with %s as %s\n", mask, new, ret);
 918         return ret;
 919 }
 920
 921 char *
 922 search_postal_merge_replace(char *mask, char *new)
 923 {
 924         char *ret=search_postal_merge(mask, new);
 925         if (!ret)
 926                 return mask;
 927         g_free(mask);
 928         return ret;
 929 }
 930
 931
 932 static int
 933 postal_match(char *postal, char *mask)
 934 {
 935         for (;;) {
 936                 if ((*postal != *mask) && (*mask != '.'))
 937                         return 0;
 938                 if (!*postal) {
 939                         if (!*mask)
 940                                 return 1;
 941                         else
 942                                 return 0;
 943                 }
 944                 postal++;
 945                 mask++;
 946         }
 947 }
 948
 949 static int
 950 search_add_result(struct search_list_level *le, struct search_list_common *slc)
 951 {
 952         struct search_list_common *slo;
 953         char *merged;
 954         slo=g_hash_table_lookup(le->hash, &slc->unique);
 955         if (!slo) {
 956                 g_hash_table_insert(le->hash, &slc->unique, slc);
 957                 if (slc->postal && !slc->postal_mask) {
 958                         slc->postal_mask=g_strdup(slc->postal);
 959                 }
 960                 le->list=g_list_append(le->list, slc);
 961                 return 1;
 962         }
 963         merged=search_postal_merge(slo->postal_mask, slc->postal);
 964         if (merged) {
 965                 g_free(slo->postal_mask);
 966                 slo->postal_mask=merged;
 967         }
 968         return 0;
 969 }
 970
 971 static char *
 972 search_list_get_unique_truncate(char *common, char *result)
 973 {
 974         dbg(1,"%s vs %s\n",common,result);
 975         while (*common) {
 976                 if (g_utf8_get_char(common) != g_utf8_get_char(result)) {
 977                         dbg(1,"truncating at %s vs %s\n",common,result);
 978                         return common;
 979                 }
 980                 result=g_utf8_next_char(result);
 981                 common=g_utf8_next_char(common);
 982         }
 983         return common;
 984 }
 985
 986 static char *
 987 search_list_get_unique_append(char *list, char *append)
 988 {
 989         char *c=list;
 990         int llen=list?strlen(list):0;
 991         int len=g_utf8_next_char(append)-append;
 992         gunichar a=g_utf8_get_char(append);
 993         while(c && *c) {
 994                 if (g_utf8_get_char(c) == a)
 995                         return list;
 996                 c=g_utf8_next_char(c);
 997         }
 998         list=g_renew(char, list, llen+len+1);
 999         strncpy(list+llen,append,len);
1000         list[llen+len]='\0';
1001         return list;
1002 }
1003
1004 char *
1005 search_list_get_unique(struct search_list *this_, char *unique)
1006 {
1007         int level=this_->level;
1008         struct search_list_level *le=&this_->levels[level];
1009         struct search_list_country *slc;
1010         struct search_list_town *slt;
1011         struct search_list_street *sls;
1012         struct search_list_house_number *slh;
1013         char *retf=NULL,*ret=NULL;
1014         char *strings[4]={NULL,};
1015         char *search=g_utf8_casefold(unique?unique:le->attr->u.str,-1);
1016         char *name,*max;
1017         int search_len=strlen(search);
1018         int i,count=sizeof(strings)/sizeof(char *);
1019         GList *l;
1020
1021         dbg(0,"enter level=%d %s %s\n",level,search,unique);
1022         l=le->list;
1023         while (l) {
1024                 switch (level) {
1025                 case 0:
1026                         slc=l->data;
1027                         strings[0]=g_strdup(slc->name);
1028                         strings[1]=g_strdup(slc->car);
1029                         strings[2]=g_strdup(slc->iso2);
1030                         strings[3]=g_strdup(slc->iso3);
1031                         break;
1032                 case 1:
1033                         slt=l->data;
1034                         name=slt->common.town_name;
1035                         for (i = 0 ; i < 3 ; i++)
1036                                 strings[i]=linguistics_expand_special(name, i);
1037                         break;
1038                 case 2:
1039                         sls=l->data;
1040                         name=sls->name;
1041                         for (i = 0 ; i < 3 ; i++)
1042                                 strings[i]=linguistics_expand_special(name, i);
1043                         break;
1044                 case 3:
1045                         slh=l->data;
1046                         name=slh->house_number;
1047                         for (i = 0 ; i < 3 ; i++)
1048                                 strings[i]=linguistics_expand_special(name, i);
1049                         break;
1050                 default:
1051                         dbg(0,"entry\n");
1052                 }
1053                 dbg(1,"entry %s %s %s %s\n",strings[0],strings[1],strings[2],strings[3]);
1054                 max=NULL;
1055                 for (i = 0 ; i < count ; i++) {
1056                         char *str=strings[i];
1057                         while (str) {
1058                                 char *strf=g_utf8_casefold(str,-1);
1059                                 dbg(1,"word %s\n",strf);
1060                                 if (!strncmp(strf, search, search_len)) {
1061                                         dbg(1,"match\n");
1062                                         if (unique) {
1063                                                 dbg(1,"possible next %s %s ret %s\n",strf+search_len,str+search_len,ret);
1064                                                 ret=search_list_get_unique_append(ret, strf+search_len);
1065                                                 ret=search_list_get_unique_append(ret, str+search_len);
1066                                                 dbg(1,"ret now %s\n",ret);
1067                                         } else {
1068                                                 if (!ret) {
1069                                                         ret=g_strdup(str);
1070                                                         retf=g_utf8_casefold(ret,-1);
1071                                                         dbg(1,"ret now %s\n",ret);
1072                                                 } else {
1073                                                         char *end=search_list_get_unique_truncate(retf,strf);
1074                                                         dbg(1,"%d characters\n",end-retf);
1075                                                         if (!max || max < end)
1076                                                                 max=end;
1077                                                 }
1078                                         }
1079                                 }
1080                                 g_free(strf);
1081                                 str=linguistics_next_word(str);
1082                         }
1083                         g_free(strings[i]);
1084                 }
1085                 if (!unique) {
1086                         if (max) {
1087                                 dbg(1,"max %s (%d characters)\n",max,max-retf);
1088                                 ret[max-retf]='\0';
1089                         } else {
1090                                 dbg(1,"new max\n");
1091                         }
1092                 }
1093                 dbg(1,"common %s\n",ret);
1094                 l=g_list_next(l);
1095         }
1096         g_free(search);
1097         g_free(retf);
1098         dbg(0,"return %s\n",ret);
1099         return ret;
1100 }
1101
1102 /**
1103  * @brief Get (next) result from a search.
1104  *
1105  * @param this_ search_list representing the search
1106  * @return next result
1107  */
1108 struct search_list_result *
1109 search_list_get_result(struct search_list *this_)
1110 {
1111         struct search_list_level *le,*leu;
1112         int level=this_->level;
1113         struct attr attr2;
1114         int has_street_name=0;
1115
1116         if (this_->use_address_results) {
1117                 struct search_list_result *ret=NULL;
1118                 if (this_->address_results_pos) {
1119                         ret=this_->address_results_pos->data;
1120                         this_->address_results_pos=g_list_next(this_->address_results_pos);
1121                 }
1122                 return ret;
1123         }
1124
1125         //dbg(0,"enter\n");
1126         le=&this_->levels[level];
1127         //dbg(0,"le=%p\n", le);
1128         for (;;)
1129         {
1130                 //dbg(0,"le->search=%p\n", le->search);
1131                 if (! le->search)
1132                 {
1133                         //dbg(0,"partial=%d level=%d\n", le->partial, level);
1134                         if (! level)
1135                                 le->parent=NULL;
1136                         else
1137                         {
1138                                 leu=&this_->levels[level-1];
1139                                 //dbg(0,"leu->curr=%p\n", leu->curr);
1140                                 for (;;)
1141                                 {
1142                                         //dbg(0,"*********########");
1143
1144                                         struct search_list_common *slc;
1145                                         if (! leu->curr)
1146                                         {
1147                                                 return NULL;
1148                                         }
1149                                         le->parent=leu->curr->data;
1150                                         leu->last=leu->curr;
1151                                         leu->curr=g_list_next(leu->curr);
1152                                         slc=(struct search_list_common *)(le->parent);
1153                                         if (!slc)
1154                                                 break;
1155                                         if (slc->selected == leu->selected)
1156                                                 break;
1157                                 }
1158                         }
1159                         if (le->parent)
1160                         {
1161                                 //dbg(0,"mapset_search_new with item(%d,%d)\n", le->parent->item.id_hi, le->parent->item.id_lo);
1162                         }
1163                         //dbg(0,"############## attr=%s\n", attr_to_name(le->attr->type));
1164                         le->search=mapset_search_new(this_->ms, &le->parent->item, le->attr, le->partial);
1165                         le->hash=g_hash_table_new(search_item_hash_hash, search_item_hash_equal);
1166                 }
1167                 //dbg(0,"le->search=%p\n", le->search);
1168                 if (!this_->item)
1169                 {
1170                         //dbg(0,"sssss 1");
1171                         this_->item=mapset_search_get_item(le->search);
1172                         //dbg(0,"sssss 1 %p\n",this_->item);
1173                 }
1174                 if (this_->item)
1175                 {
1176                         void *p=NULL;
1177                         //dbg(0,"id_hi=%d id_lo=%d\n", this_->item->id_hi, this_->item->id_lo);
1178                         if (this_->postal)
1179                         {
1180                                 struct attr postal;
1181                                 if (item_attr_get(this_->item, attr_postal_mask, &postal)) {
1182                                         if (!postal_match(this_->postal, postal.u.str))
1183                                                 continue;
1184                                 } else if (item_attr_get(this_->item, attr_postal, &postal)) {
1185                                         if (strcmp(this_->postal, postal.u.str))
1186                                                 continue;
1187                                 }
1188                         }
1189                         this_->result.country=NULL;
1190                         this_->result.town=NULL;
1191                         this_->result.street=NULL;
1192                         this_->result.c=NULL;
1193                         //dbg(0,"case x LEVEL start %d\n",level);
1194                         switch (level)
1195                         {
1196                         case 0:
1197                                 //dbg(0,"case 0 COUNTRY");
1198                                 p=search_list_country_new(this_->item);
1199                                 this_->result.country=p;
1200                                 this_->result.country->common.parent=NULL;
1201                                 this_->result.town=NULL;
1202                                 this_->result.street=NULL;
1203                                 this_->result.house_number=NULL;
1204                                 this_->item=NULL;
1205                                 break;
1206                         case 1:
1207                                 //dbg(0,"case 1 TOWN");
1208                                 p=search_list_town_new(this_->item);
1209                                 this_->result.town=p;
1210                                 this_->result.town->common.parent=this_->levels[0].last->data;
1211                                 this_->result.country=this_->result.town->common.parent;
1212                                 this_->result.c=this_->result.town->common.c;
1213                                 this_->result.street=NULL;
1214                                 this_->result.house_number=NULL;
1215                                 this_->item=NULL;
1216                                 break;
1217                         case 2:
1218                                 //dbg(0,"case 2 STREET");
1219                                 p=search_list_street_new(this_->item);
1220                                 this_->result.street=p;
1221                                 this_->result.street->common.parent=this_->levels[1].last->data;
1222                                 this_->result.town=this_->result.street->common.parent;
1223                                 this_->result.country=this_->result.town->common.parent;
1224                                 this_->result.c=this_->result.street->common.c;
1225                                 this_->result.house_number=NULL;
1226                                 this_->item=NULL;
1227                                 break;
1228                         case 3:
1229                                 dbg(1,"case 3 HOUSENUMBER\n");
1230                                 has_street_name=0;
1231
1232                                 // if this housenumber has a streetname tag, set the name now
1233                                 if (item_attr_get(this_->item, attr_street_name, &attr2))
1234                                 {
1235                                         dbg(1,"streetname: %s\n",attr2.u.str);
1236                                         has_street_name=1;
1237                                 }
1238
1239                                 p=search_list_house_number_new(this_->item, &this_->inter, le->attr->u.str, le->partial);
1240                                 if (!p)
1241                                 {
1242                                         interpolation_clear(&this_->inter);
1243                                         this_->item=NULL;
1244                                         continue;
1245                                 }
1246
1247                                 this_->result.house_number=p;
1248                                 if (!this_->result.house_number->interpolation)
1249                                 {
1250                                         this_->item=NULL;
1251                                 } else {
1252                                         dbg(0,"interpolation!\n");
1253                                 }
1254
1255                                 if(le->parent && has_street_name) {
1256                                         struct search_list_street *street=this_->levels[level-1].last->data;
1257                                         char *s1,*s2;
1258                                         int cmpres;
1259                                         s1=g_utf8_casefold(street->name,-1);
1260                                         s2=g_utf8_casefold(attr2.u.str,-1);
1261                                         cmpres=strcmp(s1,s2);
1262                                         dbg(1,"Compared %s with %s, got %d\n",s1,s2,cmpres);
1263                                         g_free(s1);
1264                                         g_free(s2);
1265                                         if(cmpres) {
1266                                                 search_list_house_number_destroy(p);
1267                                                 //this_->item=NULL;
1268                                                 continue;
1269                                         }
1270                                 }
1271
1272
1273                                 this_->result.house_number->common.parent=this_->levels[2].last->data;
1274                                 this_->result.street=this_->result.house_number->common.parent;
1275                                 this_->result.town=this_->result.street->common.parent;
1276                                 this_->result.country=this_->result.town->common.parent;
1277                                 this_->result.c=this_->result.house_number->common.c;
1278
1279 #if 0
1280                                 if(!has_street_name) {
1281                                         static struct search_list_street null_street;
1282                                         this_->result.street=&null_street;
1283                                 }
1284 #endif
1285                         }
1286                         if (p)
1287                         {
1288                                 if (search_add_result(le, p))
1289                                 {
1290                                         this_->result.id++;
1291                                         return &this_->result;
1292                                 }
1293                                 else
1294                                 {
1295                                         search_list_result_destroy(level, p);
1296                                 }
1297                         }
1298                 } else {
1299                         mapset_search_destroy(le->search);
1300                         le->search=NULL;
1301                         g_hash_table_destroy(le->hash);
1302                         if (! level)
1303                                 break;
1304                 }
1305         }
1306         return NULL;
1307 }
1308
1309 void
1310 search_list_destroy(struct search_list *this_)
1311 {
1312         g_free(this_->postal);
1313         g_free(this_);
1314 }
1315
1316 void
1317 search_init(void)
1318 {
1319 }