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