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