From 95f97879ee6a68212bf11fa1134f9761c8772cbe Mon Sep 17 00:00:00 2001 From: tegzed Date: Sat, 19 Mar 2011 22:31:36 +0000 Subject: [PATCH] Add:map/csv: - added the possibility to add map items, add or change map item attributes at runtime and save changed map data on exit git-svn-id: https://navit.svn.sourceforge.net/svnroot/navit/trunk@4371 ffa7fe5e-494d-0410-b361-a75ebd5db220 --- navit/navit/map/csv/csv.c | 213 ++++++++++++++++++++++++++++++----------- navit/navit/map/csv/csv.h | 2 + navit/navit/map/csv/quadtree.c | 85 ++++++++++++++++ navit/navit/map/csv/quadtree.h | 2 + 4 files changed, 245 insertions(+), 57 deletions(-) diff --git a/navit/navit/map/csv/csv.c b/navit/navit/map/csv/csv.c index 2e25be4..32b3509 100644 --- a/navit/navit/map/csv/csv.c +++ b/navit/navit/map/csv/csv.c @@ -44,6 +44,7 @@ static int map_id; //prototype static int csv_coord_set(void *priv_data, struct coord *c, int count, enum change_mode mode); +static struct item * csv_create_item(struct map_rect_priv *mr, enum item_type it_type); struct quadtree_data { @@ -113,7 +114,6 @@ save_map_csv(struct map_priv *m) } else { //TODO handle this error } - } csv_line = g_strdup_printf("%s%s",csv_line,tmpstr); g_free(tmpstr); @@ -150,6 +150,7 @@ map_destroy_csv(struct map_priv *m) g_free(m->attr_types); g_free(m); g_hash_table_destroy(m->item_hash); + g_hash_table_destroy(m->qitem_hash); quadtree_destroy(m->tree_root); g_free(m->filename); } @@ -181,12 +182,25 @@ csv_attr_rewind(void *priv_data) static int csv_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr) -{ +{ + int i, bAttrFound = 0; GList* attr_list; struct map_rect_priv *mr=priv_data; + enum attr_type *at = mr->m->attr_types; + + for(i=0;im->attr_cnt;++i) { + if(*at == attr_type) { + bAttrFound = 1; + break; + } + ++at; + } + + if(!bAttrFound) { + return 0; + } - if(!mr || !mr->curr_item || !mr->curr_item->data) { - attr = NULL; + if(!mr || !mr->curr_item || !mr->curr_item->data ) { return 0; } @@ -199,7 +213,6 @@ csv_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr) } attr_list = g_list_next(attr_list); } - attr = NULL; return 0; } @@ -211,12 +224,19 @@ csv_attr_set(void *priv_data, struct attr *attr, enum change_mode mode) int i, bFound = 0; struct attr *attr_new; GList *attr_list, *curr_attr_list; + enum attr_type *at = m->attr_types; + + if(!mr || !mr->curr_item || !mr->curr_item->data ) { + return 0; + } + //if attribute is not supported by this csv map return 0 for(i=0;iattr_cnt;++i) { - if(attr_type==attr->type) { + if(*at==attr->type) { bFound = 1; break; } + ++at; } if( ! bFound) { return 0; @@ -252,6 +272,7 @@ csv_attr_set(void *priv_data, struct attr *attr, enum change_mode mode) if( mode==change_mode_modify || mode==change_mode_prepend || mode==change_mode_append) { //add new attribute curr_attr_list = g_list_prepend(curr_attr_list, attr_new); + ((struct quadtree_data*)(((struct quadtree_item*)(mr->curr_item->data))->data))->attr_list = curr_attr_list; return 1; } g_free(attr_new); @@ -268,58 +289,72 @@ static struct item_methods methods_csv = { csv_coord_set, }; + +/* + * Sets coordinate of an existing item (either on the new list or an item with coord ) + */ static int csv_coord_set(void *priv_data, struct coord *c, int count, enum change_mode mode) { - struct map_rect_priv* mr = (struct map_rect_priv*)priv_data; - struct map_priv* m = mr->m; + struct quadtree_item query_item, insert_item, *query_res; struct coord_geo cg; - struct quadtree_item *item; - struct quadtree_item query_item; - int i; - int ret = 1; - - for (i=0;itree_root, &query_item); - - if(item) { //already exists skip - ret = 0; - continue; + struct map_rect_priv* mr; + struct map_priv* m; + struct quadtree_item* qi; + + //for now we only support coord modification only + if( ! change_mode_modify) { + return 0; + } + //csv driver supports one coord per record only + if( count != 1) { + return 0; + } + + //get curr_item of given map_rect + mr = (struct map_rect_priv*)priv_data; + m = mr->m; + + if(!mr->curr_item || !mr->curr_item->data) { + return 0; + } + + qi = mr->curr_item->data; + + transform_to_geo(projection_mg, &c[0], &cg); + + //if it is on the new list remove from new list and add it to the tree with the coord + GList* new_it = m->new_items; + while(new_it) { + if(new_it->data==qi) { + break; } - m->dirty = 1; - //add item to the map - - curr_item = item_new("",zoom_max); - curr_item->type = m->item_type; - curr_item->id_lo = m->next_item_idx; - if (m->flags & 1) - curr_item->id_hi=1; - else - curr_item->id_hi=0; - curr_item->meth=&methods_csv; - - qd = g_new0(struct quadtree_data,1); - qi = g_new (struct quadtree_item,1); - pID = g_new(int,1); - qd->item = curr_item; - qd->attr_list = NULL; - qi->data = qd; + new_it = g_list_next(new_it); + } + if(new_it) { qi->longitude = cg.lng; - qi->latitude = cg.lat; - quadtree_add(m->tree_root, qi); - *pID = m->next_item_idx; - g_hash_table_insert(m->item_hash, pID,curr_item); - ++m->next_item_idx; + qi->latitude = cg.lat; + quadtree_add( m->tree_root, qi); + m->new_items = g_list_remove_link(m->new_items,new_it); + return 0; + } + + //else update quadtree item with the new coord + // remove item from the quadtree (to be implemented) + query_item.longitude = cg.lng; + query_item.latitude = cg.lat; + query_res = quadtree_find_item(m->tree_root, &query_item); + if(!query_res) { + return 0; } - return ret; + // add item to the tree with the new coord + insert_item = *query_res; + insert_item.longitude = cg.lng; + insert_item.latitude = cg.lat; + quadtree_delete_item(m->tree_root, query_res); + g_free(query_res); + quadtree_add( m->tree_root, &insert_item); + return 1; } static struct map_rect_priv * @@ -386,7 +421,6 @@ map_rect_get_item_csv(struct map_rect_priv *mr) ret = ((struct quadtree_data*)(((struct quadtree_item*)(mr->curr_item->data))->data))->item; return ret; } - } return NULL; } @@ -395,7 +429,15 @@ static struct item * map_rect_get_item_byid_csv(struct map_rect_priv *mr, int id_hi, int id_lo) { //currently id_hi is ignored - return g_hash_table_lookup(mr->m->item_hash,&id_lo); + struct item *it = g_hash_table_lookup(mr->m->item_hash,&id_lo); + struct quadtree_item *qit = g_hash_table_lookup(mr->m->qitem_hash,&id_lo); + if(it && qit) { + mr->curr_item = g_list_prepend(NULL, qit); + } + else { + mr->curr_item = NULL; + } + return it; } static int @@ -404,6 +446,58 @@ csv_get_attr(struct map_priv *m, enum attr_type type, struct attr *attr) return 0; } +static struct item * +csv_create_item(struct map_rect_priv *mr, enum item_type it_type) +{ + struct map_priv* m; + struct quadtree_data* qd; + struct quadtree_item* qi; + struct item* curr_item; + int* pID; + if(mr && mr->m) { + m = mr->m; + } + else { + return NULL; + } + + if( m->item_type != it_type) { + return NULL; + } + + m->dirty = 1; + //add item to the map + curr_item = item_new("",zoom_max); + curr_item->type = m->item_type; + curr_item->priv_data = mr; + + curr_item->id_lo = m->next_item_idx; + if (m->flags & 1) + curr_item->id_hi=1; + else + curr_item->id_hi=0; + curr_item->meth=&methods_csv; + + qd = g_new0(struct quadtree_data,1); + qi = g_new0(struct quadtree_item,1); + qd->item = curr_item; + qd->attr_list = NULL; + qi->data = qd; + //we don`t have valid coord yet + qi->longitude = 0; + qi->latitude = 0; + //add the coord less item to the new list + //TODO remove unnecessary indirection + m->new_items = g_list_prepend(m->new_items, qi); + mr->curr_item = m->new_items; + //don't add to the quadtree yet, wait until we have a valid coord + pID = g_new(int,1); + *pID = m->next_item_idx; + g_hash_table_insert(m->item_hash, pID,curr_item); + g_hash_table_insert(m->qitem_hash, pID,qi); + ++m->next_item_idx; + return curr_item; +} static struct map_methods map_methods_csv = { projection_mg, @@ -416,7 +510,7 @@ static struct map_methods map_methods_csv = { NULL, NULL, NULL, - NULL, + csv_create_item, csv_get_attr, }; @@ -436,6 +530,7 @@ map_new_csv(struct map_methods *meth, struct attr **attrs, struct callback_list struct quadtree_node* tree_root = quadtree_node_new(NULL,-90,90,-90,90); m = g_new0(struct map_priv, 1); m->id = ++map_id; + m->qitem_hash = g_hash_table_new(g_int_hash, g_int_equal); m->item_hash = g_hash_table_new_full(g_int_hash, g_int_equal,g_free,g_free); item_type = attr_search(attrs, NULL, attr_item_type); @@ -484,12 +579,15 @@ map_new_csv(struct map_methods *meth, struct attr **attrs, struct callback_list char *line=g_alloca(sizeof(char)*max_line_len); while(!feof(fp)) { if(fgets(line,max_line_len,fp)) { - char*line2 = g_strdup(line); - //count columns - //TODO make delimiter parameter + char*line2; char* delim = ","; int col_cnt=0; char*tok; + + if(line[strlen(line)-1]=='\n' || line[strlen(line)-1]=='\r') { + line[strlen(line)-1] = '\0'; + } + line2 = g_strdup(line); while((tok=strtok( (col_cnt==0)?line:NULL , delim))) { ++col_cnt; } @@ -554,6 +652,7 @@ map_new_csv(struct map_methods *meth, struct attr **attrs, struct callback_list quadtree_add(tree_root, qi); *pID = m->next_item_idx; g_hash_table_insert(m->item_hash, pID,curr_item); + g_hash_table_insert(m->qitem_hash, pID,qi); ++m->next_item_idx; } else { diff --git a/navit/navit/map/csv/csv.h b/navit/navit/map/csv/csv.h index 4e7829d..7bf2403 100644 --- a/navit/navit/map/csv/csv.h +++ b/navit/navit/map/csv/csv.h @@ -30,12 +30,14 @@ struct map_priv { struct quadtree_node* tree_root; int flags; GHashTable*item_hash; + GHashTable*qitem_hash; char* filename; int dirty; //need to write map file on exit int attr_cnt; enum attr_type *attr_types; int next_item_idx; enum item_type item_type; + GList* new_items; //list of quadtree items that have no coord set yet () }; struct map_rect_priv { diff --git a/navit/navit/map/csv/quadtree.c b/navit/navit/map/csv/quadtree.c index 1d1460f..8782576 100644 --- a/navit/navit/map/csv/quadtree.c +++ b/navit/navit/map/csv/quadtree.c @@ -163,6 +163,86 @@ quadtree_find_item(struct quadtree_node* this_, struct quadtree_item* item) { return res; } +/* + * returns the containing node for an item + */ +struct quadtree_node* +quadtree_find_containing_node(struct quadtree_node* root, struct quadtree_item* item) +{ + struct quadtree_node*res = NULL; + + if( ! root ) { + return NULL; + } + + if( root->is_leaf ) { + int i; + for(i=0;inode_num;++i) { + if(item == &root->items[i]) { + res = root; + } + } + } + else { + if( + root->aa && + root->aa->xmin<=item->longitude && item->longitudeaa->xmax && + root->aa->ymin<=item->latitude && item->latitudeaa->ymax + ) { + res = quadtree_find_containing_node(root->aa,item); + } + else if( + root->ab && + root->ab->xmin<=item->longitude && item->longitudeab->xmax && + root->ab->ymin<=item->latitude && item->latitudeab->ymax + ) { + res = quadtree_find_containing_node(root->ab,item); + } + else if( + root->ba && + root->ba->xmin<=item->longitude && item->longitudeba->xmax && + root->ba->ymin<=item->latitude && item->latitudeba->ymax + ) { + res = quadtree_find_containing_node(root->ba,item); + } + else if( + root->bb && + root->bb->xmin<=item->longitude && item->longitudebb->xmax && + root->bb->ymin<=item->latitude && item->latitudebb->ymax + ) { + res = quadtree_find_containing_node(root->bb,item); + } + else { + //this should not happen + } + } + return res; +} + + +int quadtree_delete_item(struct quadtree_node* root, struct quadtree_item* item) +{ + struct quadtree_node* qn = quadtree_find_containing_node(root,item); + int i, bFound = 0; + + if(!qn || !qn->node_num) { + return 0; + } + + for(i=0;inode_num;++i) { + if( &qn->items[i] == item) { + bFound = 1; + } + if(bFound && inode_num-1) { + qn->items[i] = qn->items[i+1]; + } + } + if(bFound) { + --qn->node_num; + } + return bFound; +} + /* * tries to find closest item, first it descend into the quadtree as much as possible, then if no point is found go up n levels and flood @@ -241,6 +321,7 @@ quadtree_find_nearest(struct quadtree_node* this_, struct quadtree_item* item) { } } return res; + } void @@ -340,15 +421,19 @@ void quadtree_destroy(struct quadtree_node* this_) { if(this_->aa) { quadtree_destroy(this_->aa); + this_->aa = NULL; } if(this_->ab) { quadtree_destroy(this_->ab); + this_->ab = NULL; } if(this_->ba) { quadtree_destroy(this_->ba); + this_->ba = NULL; } if(this_->bb) { quadtree_destroy(this_->bb); + this_->bb = NULL; } free(this_); } diff --git a/navit/navit/map/csv/quadtree.h b/navit/navit/map/csv/quadtree.h index 69785ca..027828c 100644 --- a/navit/navit/map/csv/quadtree.h +++ b/navit/navit/map/csv/quadtree.h @@ -27,6 +27,8 @@ struct quadtree_node* quadtree_node_new(struct quadtree_node* parent, double xmi struct quadtree_item* quadtree_find_nearest_flood(struct quadtree_node* this_, struct quadtree_item* item, double current_max, struct quadtree_node* toSkip); struct quadtree_item* quadtree_find_nearest(struct quadtree_node* this_, struct quadtree_item* item); struct quadtree_item* quadtree_find_item(struct quadtree_node* this_, struct quadtree_item* item); +struct quadtree_node* quadtree_find_containing_node(struct quadtree_node* root, struct quadtree_item* item); +int quadtree_delete_item(struct quadtree_node* root, struct quadtree_item* item); void quadtree_find_rect_items(struct quadtree_node* this_, double dXMin, double dXMax, double dYMin, double dYMax, GList**out); void quadtree_split(struct quadtree_node* this_); void quadtree_add(struct quadtree_node* this_, struct quadtree_item* item); -- 2.7.4