navit/map.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 /** @file
  21  *
  22  * @brief Contains code that makes navit able to load maps
  23  *
  24  * This file contains the code that makes navit able to load maps. Because
  25  * navit is able to open maps in different formats, this code does not handle
  26  * any map format itself. This is done by map plugins which register to this
  27  * code by calling plugin_register_map_type().
  28  *
  29  * When opening a new map, the map plugin will return a pointer to a map_priv
  30  * struct, which can be defined by the map plugin and contains whatever private
  31  * data the map plugin needs to access the map. This pointer will also be used
  32  * as a "handle" to access the map opened.
  33  *
  34  * A common task is to create a "map rect". A map rect is a rectangular part of
  35  * the map, that one can for example retrieve items from. It is not possible to
  36  * retrieve items directly from the complete map. Creating a map rect returns a
  37  * pointer to a map_rect_priv, which contains private data for the map rect and
  38  * will be used as "handle" for this map rect.
  39  */
  40
  41 #include <glib.h>
  42 #include <string.h>
  43 #include "debug.h"
  44 #include "coord.h"
  45 #include "projection.h"
  46 #include "item.h"
  47 #include "map.h"
  48 #include "maptype.h"
  49 #include "transform.h"
  50 #include "plugin.h"
  51 #include "callback.h"
  52 #include "country.h"
  53
  54 /**
  55  * @brief Holds information about a map
  56  *
  57  * This structure holds information about a map.
  58  */
  59 struct map {
  60         struct map_methods meth;                        /**< Structure with pointers to the map plugin's functions */
  61         struct map_priv *priv;                          /**< Private data of the map, only known to the map plugin */
  62         struct attr **attrs;                            /**< Attributes of this map */
  63         struct callback_list *attr_cbl;         /**< List of callbacks that are called when attributes change */
  64         int refcount;
  65 };
  66
  67 /**
  68  * @brief Describes a rectangular extract of a map
  69  *
  70  * This structure describes a rectangular extract of a map.
  71  */
  72 struct map_rect {
  73         struct map *m;                          /**< The map this extract is from */
  74         struct map_rect_priv *priv; /**< Private data of this map rect, only known to the map plugin */
  75 };
  76
  77 /**
  78  * @brief Opens a new map
  79  *
  80  * This function opens a new map based on the attributes passed. This function
  81  * takes the attribute "attr_type" to determine which type of map to open and passes
  82  * all attributes to the map plugin's function that was specified in the
  83  * plugin_register_new_map_type()-call.
  84  *
  85  * Note that every plugin should accept an attribute of type "attr_data" to be passed
  86  * with the filename of the map to be opened as value.
  87  *
  88  * @param attrs Attributes specifying which map to open, see description
  89  * @return The opened map or NULL on failure
  90  */
  91 struct map *
  92 map_new(struct attr *parent, struct attr **attrs)
  93 {
  94         struct map *m;
  95         struct map_priv *(*maptype_new)(struct map_methods *meth, struct attr **attrs, struct callback_list *cbl);
  96         struct attr *type=attr_search(attrs, NULL, attr_type);
  97
  98         if (! type) {
  99                 dbg(0,"missing type\n");
 100                 return NULL;
 101         }
 102         maptype_new=plugin_get_map_type(type->u.str);
 103         if (! maptype_new) {
 104                 dbg(0,"invalid type '%s'\n", type->u.str);
 105                 return NULL;
 106         }
 107
 108         m=g_new0(struct map, 1);
 109         m->attrs=attr_list_dup(attrs);
 110         m->attr_cbl=callback_list_new();
 111         m->priv=maptype_new(&m->meth, attrs, m->attr_cbl);
 112         if (! m->priv) {
 113                 m->refcount = 1;
 114                 map_destroy(m);
 115                 m=NULL;
 116         }
 117         else {
 118                 m->refcount = 0;
 119         }
 120         return m;
 121 }
 122
 123 void
 124 map_ref(struct map* m)
 125 {
 126         m->refcount++;
 127 }
 128
 129
 130 /**
 131  * @brief Gets an attribute from a map
 132  *
 133  * @param this_ The map the attribute should be read from
 134  * @param type The type of the attribute to be read
 135  * @param attr Pointer to an attrib-structure where the attribute should be written to
 136  * @param iter (NOT IMPLEMENTED) Used to iterate through all attributes of a type. Set this to NULL to get the first attribute, set this to an attr_iter to get the next attribute
 137  * @return True if the attribute type was found, false if not
 138  */
 139 int
 140 map_get_attr(struct map *this_, enum attr_type type, struct attr *attr, struct attr_iter *iter)
 141 {
 142         int ret=0;
 143         if (this_->meth.map_get_attr)
 144                 ret=this_->meth.map_get_attr(this_->priv, type, attr);
 145         if (!ret)
 146                 ret=attr_generic_get_attr(this_->attrs, NULL, type, attr, iter);
 147         return ret;
 148 }
 149
 150 /**
 151  * @brief Sets an attribute of a map
 152  *
 153  * This sets an attribute of a map, overwriting an attribute of the same type if it
 154  * already exists. This function also calls all the callbacks that are registred
 155  * to be called when attributes change.
 156  *
 157  * @param this_ The map to set the attribute of
 158  * @param attr The attribute to set
 159  * @return True if the attr could be set, false otherwise
 160  */
 161 int
 162 map_set_attr(struct map *this_, struct attr *attr)
 163 {
 164         this_->attrs=attr_generic_set_attr(this_->attrs, attr);
 165         if (this_->meth.map_set_attr)
 166                 this_->meth.map_set_attr(this_->priv, attr);
 167         callback_list_call_attr_2(this_->attr_cbl, attr->type, this_, attr);
 168         return 1;
 169 }
 170
 171 /**
 172  * @brief Registers a new callback for attribute-change
 173  *
 174  * This function registers a new callback function that should be called if the attributes
 175  * of the map change.
 176  *
 177  * @param this_ The map to associate the callback with
 178  * @param cb The callback to add
 179  */
 180 void
 181 map_add_callback(struct map *this_, struct callback *cb)
 182 {
 183         callback_list_add(this_->attr_cbl, cb);
 184 }
 185
 186 /**
 187  * @brief Removes a callback from the list of attribute-change callbacks
 188  *
 189  * This function removes one callback from the list of callbacks functions that should be called
 190  * when attributes of the map change.
 191  *
 192  * @param this_ The map to remove the callback from
 193  * @param cb The callback to remove
 194  */
 195 void
 196 map_remove_callback(struct map *this_, struct callback *cb)
 197 {
 198         callback_list_remove(this_->attr_cbl, cb);
 199 }
 200
 201
 202 /**
 203  * @brief Checks if strings from a map have to be converted
 204  *
 205  * @param this_ Map to be checked for the need to convert strings
 206  * @return True if strings from the map have to be converted, false otherwise
 207  */
 208 int
 209 map_requires_conversion(struct map *this_)
 210 {
 211         return (this_->meth.charset != NULL && strcmp(this_->meth.charset, "utf-8"));
 212 }
 213
 214 /**
 215  * @brief Converts a string from a map
 216  *
 217  * @param this_ The map the string to be converted is from
 218  * @param str The string to be converted
 219  * @return The converted string. It has to be map_convert_free()d after use.
 220  */
 221 char *
 222 map_convert_string(struct map *this_, char *str)
 223 {
 224         return g_convert(str, -1,"utf-8",this_->meth.charset,NULL,NULL,NULL);
 225 }
 226
 227 /**
 228  * @brief Frees the memory allocated for a converted string
 229  *
 230  * @param str The string to be freed
 231  */
 232 void
 233 map_convert_free(char *str)
 234 {
 235         g_free(str);
 236 }
 237
 238 /**
 239  * @brief Returns the projection of a map
 240  *
 241  * @param this_ The map to return the projection of
 242  * @return The projection of the map
 243  */
 244 enum projection
 245 map_projection(struct map *this_)
 246 {
 247         return this_->meth.pro;
 248 }
 249
 250 /**
 251  * @brief Sets the projection of a map
 252  *
 253  * @param this_ The map to set the projection of
 254  * @param pro The projection to be set
 255  */
 256 void
 257 map_set_projection(struct map *this_, enum projection pro)
 258 {
 259         this_->meth.pro=pro;
 260 }
 261
 262 void
 263 map_destroy_do(struct map *m)
 264 {
 265         if (m->priv)
 266                 m->meth.map_destroy(m->priv);
 267         attr_list_free(m->attrs);
 268         callback_list_destroy(m->attr_cbl);
 269         g_free(m);
 270 }
 271
 272 /**
 273  * @brief Destroys an opened map
 274  *
 275  * @param m The map to be destroyed
 276  */
 277 void
 278 map_destroy(struct map *m)
 279 {
 280         if (!m)
 281                 return;
 282
 283         if(0<m->refcount) {
 284                 m->refcount--;
 285         }
 286         if(0 == m->refcount) {
 287                 map_destroy_do(m);
 288         }
 289 }
 290
 291 /**
 292  * @brief Creates a new map rect
 293  *
 294  * This creates a new map rect, which can be used to retrieve items from a map. If
 295  * sel is a linked-list of selections, all of them will be used. If you pass NULL as
 296  * sel, this means "get me the whole map".
 297  *
 298  * @param m The map to build the rect on
 299  * @param sel Map selection to choose the rectangle - may be NULL, see description
 300  * @return A new map rect
 301  */
 302 struct map_rect *
 303 map_rect_new(struct map *m, struct map_selection *sel)
 304 {
 305         struct map_rect *mr;
 306
 307 #if 0
 308         printf("map_rect_new 0x%x,0x%x-0x%x,0x%x\n", r->lu.x, r->lu.y, r->rl.x, r->rl.y);
 309 #endif
 310         mr=g_new0(struct map_rect, 1);
 311         mr->m=m;
 312         mr->priv=m->meth.map_rect_new(m->priv, sel);
 313         if (! mr->priv) {
 314                 g_free(mr);
 315                 mr=NULL;
 316         }
 317
 318         return mr;
 319 }
 320
 321 /**
 322  * @brief Gets the next item from a map rect
 323  *
 324  * Returns an item from a map rect and advances the "item pointer" one step further,
 325  * so that at the next call the next item is returned. Returns NULL if there are no more items.
 326  *
 327  * @param mr The map rect to return an item from
 328  * @return An item from the map rect
 329  */
 330 struct item *
 331 map_rect_get_item(struct map_rect *mr)
 332 {
 333         struct item *ret;
 334         dbg_assert(mr != NULL);
 335         dbg_assert(mr->m != NULL);
 336         dbg_assert(mr->m->meth.map_rect_get_item != NULL);
 337         ret=mr->m->meth.map_rect_get_item(mr->priv);
 338         if (ret)
 339                 ret->map=mr->m;
 340         return ret;
 341 }
 342
 343 /**
 344  * @brief Returns the item specified by the ID
 345  *
 346  * @param mr The map rect to search for the item
 347  * @param id_hi High part of the ID to be found
 348  * @param id_lo Low part of the ID to be found
 349  * @return The item with the specified ID or NULL if not found
 350  */
 351 struct item *
 352 map_rect_get_item_byid(struct map_rect *mr, int id_hi, int id_lo)
 353 {
 354         struct item *ret=NULL;
 355         dbg_assert(mr != NULL);
 356         dbg_assert(mr->m != NULL);
 357         if (mr->m->meth.map_rect_get_item_byid)
 358                 ret=mr->m->meth.map_rect_get_item_byid(mr->priv, id_hi, id_lo);
 359         if (ret)
 360                 ret->map=mr->m;
 361         return ret;
 362 }
 363
 364 /**
 365  * @brief Destroys a map rect
 366  *
 367  * @param mr The map rect to be destroyed
 368  */
 369 void
 370 map_rect_destroy(struct map_rect *mr)
 371 {
 372         if (mr) {
 373                 mr->m->meth.map_rect_destroy(mr->priv);
 374                 g_free(mr);
 375         }
 376 }
 377
 378 /**
 379  * @brief Holds information about a search on a map
 380  *
 381  * This structure holds information about a search performed on a map. This can be
 382  * used as "handle" to retrieve items from a search.
 383  */
 384 struct map_search {
 385         struct map *m;
 386         struct attr search_attr;
 387         void *priv;
 388 };
 389
 390 /**
 391  * @brief Starts a search on a map
 392  *
 393  * This function starts a search on a map. What attributes one can search for depends on the
 394  * map plugin.
 395  *
 396  * The OSM/binfile plugin currently supports: attr_town_name, attr_street_name
 397  * The MG plugin currently supports: ttr_town_postal, attr_town_name, attr_street_name
 398  *
 399  * If you enable partial matches bear in mind that the search matches only the begin of the
 400  * strings - a search for a street named "street" would match to "streetfoo", but not to
 401  * "somestreet". Search is case insensitive.
 402  *
 403  * The item passed to this function specifies a "superior item" to "search within" - e.g. a town
 404  * in which we want to search for a street, or a country in which to search for a town.
 405  *
 406  * Please also note that the search for countries is not handled by map plugins but by navit internally -
 407  * have a look into country.c for details. Because of that every map plugin has to accept a country item
 408  * to be passed as "superior item".
 409  *
 410  * Note: If you change something here, please make sure to also update the documentation of mapset_search_new()
 411  * in mapset.c!
 412  *
 413  * @param m The map that should be searched
 414  * @param item Specifies a superior item to "search within" (see description)
 415  * @param search_attr Attribute specifying what to search for. See description.
 416  * @param partial Set this to true to also have partial matches. See description.
 417  * @return A new map search struct for this search
 418  */
 419 struct map_search *
 420 map_search_new(struct map *m, struct item *item, struct attr *search_attr, int partial)
 421 {
 422         struct map_search *this_;
 423         dbg(1,"enter(%p,%p,%p,%d)\n", m, item, search_attr, partial);
 424         dbg(1,"0x%x 0x%x 0x%x\n", attr_country_all, search_attr->type, attr_country_name);
 425         this_=g_new0(struct map_search,1);
 426         this_->m=m;
 427         this_->search_attr=*search_attr;
 428         if ((search_attr->type >= attr_country_all && search_attr->type <= attr_country_name) || search_attr->type == attr_country_id)
 429                 this_->priv=country_search_new(&this_->search_attr, partial);
 430         else {
 431                 if (m->meth.map_search_new) {
 432                         if (m->meth.charset)
 433                                 this_->search_attr.u.str=g_convert(this_->search_attr.u.str, -1,m->meth.charset,"utf-8",NULL,NULL,NULL);
 434                         this_->priv=m->meth.map_search_new(m->priv, item, &this_->search_attr, partial);
 435                         if (! this_->priv) {
 436                                 g_free(this_);
 437                                 this_=NULL;
 438                         }
 439                 } else {
 440                         g_free(this_);
 441                         this_=NULL;
 442                 }
 443         }
 444         return this_;
 445 }
 446
 447 /**
 448  * @brief Returns an item from a map search
 449  *
 450  * This returns an item of the result of a search on a map and advances the "item pointer" one step,
 451  * so that at the next call the next item will be returned. If there are no more items in the result
 452  * NULL is returned.
 453  *
 454  * @param this_ Map search struct of the search
 455  * @return One item of the result
 456  */
 457 struct item *
 458 map_search_get_item(struct map_search *this_)
 459 {
 460         struct item *ret;
 461
 462         if (! this_)
 463                 return NULL;
 464         if ((this_->search_attr.type >= attr_country_all && this_->search_attr.type <= attr_country_name) || this_->search_attr.type == attr_country_id)
 465                 return country_search_get_item(this_->priv);
 466         ret=this_->m->meth.map_search_get_item(this_->priv);
 467         if (ret)
 468                 ret->map=this_->m;
 469         return ret;
 470 }
 471
 472 /**
 473  * @brief Destroys a map search struct
 474  *
 475  * @param this_ The map search struct to be destroyed
 476  */
 477 void
 478 map_search_destroy(struct map_search *this_)
 479 {
 480         if (! this_)
 481                 return;
 482         if (this_->search_attr.type >= attr_country_all && this_->search_attr.type <= attr_country_name)
 483                 country_search_destroy(this_->priv);
 484         else {
 485                 if (this_->m->meth.charset)
 486                                 g_free(this_->search_attr.u.str);
 487                 this_->m->meth.map_search_destroy(this_->priv);
 488         }
 489         g_free(this_);
 490 }
 491
 492 /**
 493  * @brief Creates a new rectangular map selection
 494  *
 495  * @param center Coordinates of the center of the new rectangle
 496  * @param distance Distance of the rectangle's borders from the center
 497  * @param order Desired order of the new selection
 498  * @return The new map selection
 499  */
 500 struct map_selection *
 501 map_selection_rect_new(struct pcoord *center, int distance, int order)
 502 {
 503         struct map_selection *ret=g_new0(struct map_selection, 1);
 504         ret->order=order;
 505         ret->range=item_range_all;
 506         ret->u.c_rect.lu.x=center->x-distance;
 507         ret->u.c_rect.lu.y=center->y+distance;
 508         ret->u.c_rect.rl.x=center->x+distance;
 509         ret->u.c_rect.rl.y=center->y-distance;
 510         return ret;
 511 }
 512
 513 /**
 514  * @brief Duplicates a map selection, transforming coordinates
 515  *
 516  * This duplicates a map selection and at the same time transforms the internal
 517  * coordinates of the selection from one projection to another.
 518  *
 519  * @param sel The map selection to be duplicated
 520  * @param from The projection used for the selection at the moment
 521  * @param to The projection that should be used for the duplicated selection
 522  * @return A duplicated, transformed map selection
 523  */
 524 struct map_selection *
 525 map_selection_dup_pro(struct map_selection *sel, enum projection from, enum projection to)
 526 {
 527         struct map_selection *next,**last;
 528         struct map_selection *ret=NULL;
 529         last=&ret;
 530         while (sel) {
 531                 next = g_new(struct map_selection, 1);
 532                 *next=*sel;
 533                 if (from != projection_none || to != projection_none) {
 534                         transform_from_to(&sel->u.c_rect.lu, from, &next->u.c_rect.lu, to);
 535                         transform_from_to(&sel->u.c_rect.rl, from, &next->u.c_rect.rl, to);
 536                 }
 537                 *last=next;
 538                 last=&next->next;
 539                 sel = sel->next;
 540         }
 541         return ret;
 542 }
 543
 544 /**
 545  * @brief Duplicates a map selection
 546  *
 547  * @param sel The map selection to duplicate
 548  * @return The duplicated map selection
 549  */
 550 struct map_selection *
 551 map_selection_dup(struct map_selection *sel)
 552 {
 553         return map_selection_dup_pro(sel, projection_none, projection_none);
 554 }
 555
 556 /**
 557  * @brief Destroys a map selection
 558  *
 559  * @param sel The map selection to be destroyed
 560  */
 561 void
 562 map_selection_destroy(struct map_selection *sel)
 563 {
 564         struct map_selection *next;
 565         while (sel) {
 566                 next = sel->next;
 567                 g_free(sel);
 568                 sel = next;
 569         }
 570 }
 571
 572 /**
 573  * @brief Checks if a selection contains a rectangle containing an item
 574  *
 575  * This function checks if a selection contains a rectangle which exactly contains
 576  * an item. The rectangle is automatically built around the given item.
 577  *
 578  * @param sel The selection to be checked
 579  * @param item The item that the rectangle should be built around
 580  * @return True if the rectangle is within the selection, false otherwise
 581  */
 582 int
 583 map_selection_contains_item_rect(struct map_selection *sel, struct item *item)
 584 {
 585         struct coord c;
 586         struct coord_rect r;
 587         int count=0;
 588         while (item_coord_get(item, &c, 1)) {
 589                 if (! count) {
 590                         r.lu=c;
 591                         r.rl=c;
 592                 } else
 593                         coord_rect_extend(&r, &c);
 594                 count++;
 595         }
 596         if (! count)
 597                 return 0;
 598         return map_selection_contains_rect(sel, &r);
 599
 600 }
 601
 602
 603 /**
 604  * @brief Checks if a selection contains a item range
 605  *
 606  * This function checks if a selection contains at least one of the items in range
 607  *
 608  * @param sel The selection to be checked
 609  * @param follow Whether the next pointer of the selection should be followed
 610  * @param ranges The item ranges to be checked
 611  * @count the number of elements in ranges
 612  * @return True if there is a match, false otherwise
 613  */
 614
 615 int
 616 map_selection_contains_item_range(struct map_selection *sel, int follow, struct item_range *range, int count)
 617 {
 618         int i;
 619         if (! sel)
 620                 return 1;
 621         while (sel) {
 622                 for (i = 0 ; i < count ; i++) {
 623                         if (item_range_intersects_range(&sel->range, &range[i]))
 624                                 return 1;
 625                 }
 626                 if (! follow)
 627                         break;
 628                 sel=sel->next;
 629         }
 630         return 0;
 631 }
 632 /**
 633  * @brief Checks if a selection contains a item
 634  *
 635  * This function checks if a selection contains a item type
 636  *
 637  * @param sel The selection to be checked
 638  * @param follow Whether the next pointer of the selection should be followed
 639  * @param item The item type to be checked
 640  * @return True if there is a match, false otherwise
 641  */
 642
 643 int
 644 map_selection_contains_item(struct map_selection *sel, int follow, enum item_type type)
 645 {
 646         if (! sel)
 647                 return 1;
 648         while (sel) {
 649                 if (item_range_contains_item(&sel->range, type))
 650                         return 1;
 651                 if (! follow)
 652                         break;
 653                 sel=sel->next;
 654         }
 655         return 0;
 656 }
 657
 658
 659
 660 /**
 661  * @brief Checks if a pointer points to the private data of a map
 662  *
 663  * @param map The map whose private data should be checked.
 664  * @param priv The private data that should be checked.
 665  * @return True if priv is the private data of map
 666  */
 667 int
 668 map_priv_is(struct map *map, struct map_priv *priv)
 669 {
 670         return (map->priv == priv);
 671 }
 672
 673 void
 674 map_dump_filedesc(struct map *map, FILE *out)
 675 {
 676         struct map_rect *mr=map_rect_new(map, NULL);
 677         struct item *item;
 678
 679         while ((item = map_rect_get_item(mr)))
 680                 item_dump_filedesc(item, map, out);
 681         map_rect_destroy(mr);
 682 }
 683
 684 void
 685 map_dump_file(struct map *map, const char *file)
 686 {
 687         FILE *f;
 688         f=fopen(file,"w");
 689         if (f) {
 690                 map_dump_filedesc(map, f);
 691                 fclose(f);
 692         } else
 693                 dbg(0,"failed to open file '%s'\n",file);
 694 }
 695
 696 void
 697 map_dump(struct map *map)
 698 {
 699         map_dump_filedesc(map, stdout);
 700 }
 701
 702 struct item *
 703 map_rect_create_item(struct map_rect *mr, enum item_type type_)
 704 {
 705         if(mr && mr->priv && mr->m) {
 706                 return mr->m->meth.map_rect_create_item(mr->priv, type_) ;
 707         }
 708         else {
 709                 return NULL;
 710         }
 711 }
 712
 713
 714