X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=labeller.c;h=1db25fca59721a57be2199c4e79154de98772460;hb=3232a51a5fed20b6d3f0d6b9df0b8c66fdc75ca4;hp=8428711a857c428c1d5dfc99885e925dc6ede8ff;hpb=4e4fa03742d87360c0203606e94cb1cc15f00887;p=leo.git diff --git a/labeller.c b/labeller.c index 8428711..1db25fc 100644 --- a/labeller.c +++ b/labeller.c @@ -43,6 +43,14 @@ struct individual **population2; int dbg_segments = 0; int dbg_plan = 0; +int dbg_requests = 0; +int dbg_graph = 0; +int dbg_bfs = 0; +int dbg_map_parts = 0; +int dbg_movement = 0; +int dbg_init = 0; +int dbg_overlaps = 0; +int dbg_rank = 0; int page_width_int; int page_height_int; @@ -90,12 +98,22 @@ int move_max = 1; int num_requests = 0; +int conf_map_part_width = 5; +int conf_map_part_height = 5; +int num_map_parts_row; +int num_map_parts_col; +int num_map_parts; + void make_graph(void); void label_graph(void); void join_edge(struct graph_edge *e, int dir); void bfs(uns longline); void make_segments(void); +int overlaps(struct placement *p1, struct placement *p2); +int get_overlap(struct placement *p); +int individual_overlap(struct individual *individual); + void make_population(void); bool shall_terminate(void); void breed(void); @@ -104,10 +122,12 @@ void elite(void); void rank_population(void); void plan_individual(struct individual *individual); -void make_bitmap(struct point_variant *v, struct symbol *sym); -void make_bitmap_icon(struct point_variant *v, struct sym_icon *si); -void make_bitmap_point(struct point_variant *v, struct sym_point *sp); -void make_bitmap_label(struct point_variant *v, struct sym_text *text); +int cmp_individual(const void *a, const void *b); + +void make_bitmap(struct variant *v, struct symbol *sym); +void make_bitmap_icon(struct variant *v, struct sym_icon *si); +void make_bitmap_point(struct variant *v, struct sym_point *sp); +void make_bitmap_label(struct variant *v, struct sym_text *text); void cut_edge(struct graph_edge *e, double dist); struct request_line *make_new_line(void); @@ -131,6 +151,9 @@ void gen_coords_point(struct placement *p); void gen_coords_segment(struct placement *p); void gen_coords_area(struct placement *p); +struct map_part **get_map_parts(struct placement *p); +void update_map_parts(struct placement *p); + void make_segments_old(void); void labeller_cleanup(void); @@ -138,7 +161,8 @@ void labeller_cleanup(void); struct individual **perform_crossover(struct individual *parent1, struct individual *parent2); void perform_mutation(struct individual *individual); -void init_placement(struct placement *p, struct request *r); +void hide_segment_labels(struct individual *individual); +void init_placement(struct placement *p, struct individual *individual, struct request *r); void init_individual(struct individual *i); struct map_part **get_parts(struct placement *symbol, struct individual *individual); @@ -164,6 +188,8 @@ int min2(int a, int b); int max4(int a, int b, int c, int d); int min4(int a, int b, int c, int d); +struct placement dummy_placement; + int max2(int a, int b) { return (a > b ? a : b); @@ -208,9 +234,13 @@ void labeller_init(void) page_width_int = floor(page_width); page_height_int = floor(page_height); + + num_map_parts_row = (page_width_int + conf_map_part_width) / conf_map_part_width; + num_map_parts_col = (page_height_int + conf_map_part_height) / conf_map_part_height; + num_map_parts = num_map_parts_row * num_map_parts_col; } -void make_bitmap(struct point_variant *v, struct symbol *sym) +void make_bitmap(struct variant *v, struct symbol *sym) { switch (sym->type) { @@ -228,52 +258,38 @@ void make_bitmap(struct point_variant *v, struct symbol *sym) } } -void make_bitmap_icon(struct point_variant *v, struct sym_icon *si) +void make_bitmap_icon(struct variant *v, struct sym_icon *si) { - v->width = si->sir.icon->width; - v->height = si->sir.icon->height; - v->bitmap = malloc((int) ceil(v->width * v->height * sizeof(bool))); + v->width = si->sir.width + 1; + v->height = si->sir.height + 1; + v->bitmap = malloc(v->width * v->height * sizeof(bool)); for (int i=0; iwidth*v->height; i++) v->bitmap[i] = 1; } -void make_bitmap_point(struct point_variant *v, struct sym_point *sp) +void make_bitmap_point(struct variant *v, struct sym_point *sp) { - v->width = v->height = sp->size; - v->bitmap = malloc(sp->size*sp->size * sizeof(bool)); + v->width = v->height = sp->size + 1; + v->bitmap = malloc(v->width * v->height * sizeof(bool)); // FIXME: Okay, memset would be much nicer here for (int i=0; isize*sp->size; i++) v->bitmap[i] = 1; } -void make_bitmap_label(struct point_variant *v, struct sym_text *text) +void make_bitmap_label(struct variant *v, struct sym_text *text) { - int x_ld = 0; - int y_ld = 0; - int x_lu = 0; - int y_lu = 0; - int x_rd = 0; - int y_rd = 0; - int x_ru = 0; - int y_ru = 0; - - v->width = max4(x_ld, x_lu, x_rd, x_ru) - min4(x_ld, x_lu, x_rd, x_ru); - v->height = max4(y_ld, y_lu, y_rd, y_ru) - min4(y_ld, y_lu, y_rd, y_ru); - //v->bitmap = malloc((int) (ceil(v->width) * ceil(v->height) * sizeof(bool))); - v->width = ceil(text->tw); v->height = ceil(text->th); v->bitmap = malloc(v->width * v->height * sizeof(bool)); -// printf("Allocated bitmap of %d bools for %d x %d label\n", v->width * v->height, v->width, v->height); for (int i=0; iheight; i++) for (int j=0; jwidth; j++) { v->bitmap[i*v->width + j] = 1; -// printf("Writing at %d\n", i*v->width + j); } } void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex) { -printf("Adding point\n"); + if (dbg_requests) + printf("Adding point\n"); if (object->type != OSM_TYPE_NODE) { printf("Warning: Point label requested on non-point object\n"); @@ -292,9 +308,9 @@ printf("Adding point\n"); r->offset_y = 0; r->num_variants = 1; - GARY_INIT(r->variants, 0); + GARY_INIT(r->request.variants, 0); - struct point_variant *v = GARY_PUSH(r->variants); + struct variant *v = GARY_PUSH(r->request.variants); struct osm_node *n = (struct osm_node *) object; // FIXME: Compiler warning r->x = n->x; @@ -323,7 +339,8 @@ printf("Adding point\n"); void labeller_add_line(struct symbol *sym, z_index_t zindex) { -printf("Adding line on %u\n", zindex); + if (dbg_requests) + printf("Adding line on %u\n", zindex); struct buffer_line *b = GARY_PUSH(buffer_line); b->line = (struct sym_line *) sym; b->zindex = zindex; @@ -338,7 +355,8 @@ void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t return; } - printf("[LAB] Labelling way %ju on %u\n", o->id, zindex); + if (dbg_requests) + printf("[LAB] Labelling way %ju on %u\n", o->id, zindex); struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel); ll->way = (struct osm_way *) o; ll->label = sym; @@ -347,7 +365,8 @@ void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t void labeller_add_arealabel(struct symbol *sym, struct osm_object *o, z_index_t zindex) { -printf("Adding area on %u\n", zindex); + if (dbg_requests) + printf("Adding area on %u\n", zindex); struct request_area *r = GARY_PUSH(requests_area); r->request.type = REQUEST_AREA; @@ -359,16 +378,18 @@ printf("Adding area on %u\n", zindex); osm_obj_center(o, &(r->cx), &(r->cy)); - GARY_INIT(r->variants, 0); - struct point_variant *v = GARY_PUSH(r->variants); + GARY_INIT(r->request.variants, 0); + struct variant *v = GARY_PUSH(r->request.variants); switch (sym->type) { case SYMBOLIZER_ICON: - printf("DEBUG: Icon label\n"); + if (dbg_requests) + printf("DEBUG: Icon label\n"); make_bitmap_icon(v, (struct sym_icon *) sym); break; case SYMBOLIZER_TEXT: - printf("DEBUG: Text label\n"); + if (dbg_requests) + printf("DEBUG: Text label\n"); make_bitmap_label(v, (struct sym_text *) sym); default: // FIXME @@ -467,14 +488,17 @@ void dump_graph(void) void label_graph(void) { -printf("There are %u line labels requested\n", GARY_SIZE(buffer_linelabel)); + if (dbg_graph) + printf("There are %u line labels requested\n", GARY_SIZE(buffer_linelabel)); for (uns i=0; itype == SYMBOLIZER_TEXT) - printf("Labelling nodes of way %s\n", osm_val_decode(((struct sym_text *) buffer_linelabel[i].label)->text)); + if (dbg_graph) + printf("Labelling nodes of way %s\n", osm_val_decode(((struct sym_text *) buffer_linelabel[i].label)->text)); CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes) { - printf("Looking for node %ju\n", ref->o->id); + if (dbg_graph) + printf("Looking for node %ju\n", ref->o->id); struct graph_node *n = hash_find(ref->o->id); if (n == NULL) { @@ -482,12 +506,14 @@ printf("There are %u line labels requested\n", GARY_SIZE(buffer_linelabel)); } else { - printf("Searching among %u edges\n", GARY_SIZE(n->edges)); + if (dbg_graph) + printf("Searching among %u edges\n", GARY_SIZE(n->edges)); for (uns j=0; jedges); j++) { if (n->edges[j]->id == buffer_linelabel[i].way->o.id) { - printf("Labelling node %ju\n", n->id); + if (dbg_graph) + printf("Labelling node %ju\n", n->id); n->edges[j]->label = buffer_linelabel[i].label; n->edges[j]->zindex = buffer_linelabel[i].zindex; } @@ -499,19 +525,18 @@ printf("There are %u line labels requested\n", GARY_SIZE(buffer_linelabel)); void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir) { -printf("BFS edge called for edge %d (going %d) in direction %d\n", e->num, e->dir, dir); + if (dbg_bfs) + printf("BFS edge called for edge %d (going %d) in direction %d\n", e->num, e->dir, dir); struct graph_edge *candidate = NULL; for (uns i=0; iedges); i++) { struct graph_edge *other = node->edges[i]; -if (e->num == 987) printf("Got label %d\n", e->num); if ((other->longline != (uns) -1) && (other->longline != e->longline)) continue; -if (e->num == 987) printf("Continuing with edge %d\n", e->num); -printf("Testing %d ?= %d\n", other->visited, e->longline); if ((uns) other->visited != e->longline) { - printf("Pushing new edge %d / %ju\n", other->num, other->id); + if (dbg_bfs) + printf("Pushing new edge %d / %ju\n", other->num, other->id); struct graph_edge **e_ptr = GARY_PUSH(bfs_queue); *e_ptr = other; other->visited = e->longline; @@ -533,7 +558,8 @@ printf("Testing %d ?= %d\n", other->visited, e->longline); if (candidate) { -printf("New line in longline %u\n", e->longline); + if (dbg_bfs) + printf("New line in longline %u\n", e->longline); struct graph_edge *other = candidate; other->longline = e->longline; other->dir = dir; @@ -565,12 +591,15 @@ printf("New line in longline %u\n", e->longline); void bfs(uns longline) { -printf("BFS called for longline %u\n", longline); -printf("%d longlines are believed to exist, %d exist\n", num_longlines, GARY_SIZE(longlines)); +if (dbg_bfs) + printf("BFS called for longline %u\n", longline); +if (dbg_bfs) + printf("%d longlines are believed to exist, %d exist\n", num_longlines, GARY_SIZE(longlines)); for (uns i=0; inum, GARY_SIZE(bfs_queue)); + if (dbg_bfs) + printf("Exploring new edge %d; %d remaining\n", cur->num, GARY_SIZE(bfs_queue)); //ASSERT(! cur->visited); cur->visited = longline; @@ -615,16 +644,20 @@ void bfs_wrapper(void) { GARY_PUSH(longlines); longlines[num_longlines].first = node->edges[i]; - printf("Running new BFS\n"); - printf("Creating longline %u\n", num_longlines); + if (dbg_bfs) + printf("Running new BFS\n"); + if (dbg_bfs) + printf("Creating longline %u\n", num_longlines); GARY_RESIZE(bfs_queue, 0); struct graph_edge **e = GARY_PUSH(bfs_queue); *e = node->edges[i]; node->edges[i]->longline = num_longlines; bfs(node->edges[i]->longline); //dump_longlines(); - printf("Joined %d edges\n", dbg_num_hits); dbg_num_hits = 0; - printf("Planned %u edges\n", GARY_SIZE(bfs_queue)); + if (dbg_bfs) + printf("Joined %d edges\n", dbg_num_hits); dbg_num_hits = 0; + if (dbg_bfs) + printf("Planned %u edges\n", GARY_SIZE(bfs_queue)); num_longlines++; } } @@ -684,9 +717,9 @@ struct request_segment *make_new_segment(struct request_section *rls, struct sym rs->request.ind = num_requests++; rs->request.type = REQUEST_SEGMENT; - struct point_variant *v = malloc(sizeof(struct point_variant)); + struct variant *v = malloc(sizeof(struct variant)); make_bitmap(v, sym); - rs->variant = v; + rs->request.variants = v; return rs; } @@ -700,6 +733,8 @@ void cut_edge(struct graph_edge *e, double dist) *new = *e; e->next = new; + // FIXME? Create new label for new edge, don't only copy pointer? + struct osm_node *n1 = e->n1->o; struct osm_node *n2 = e->n2->o; @@ -722,6 +757,7 @@ void cut_edge(struct graph_edge *e, double dist) e->length = hypot(abs(n1->x - n11->x), abs(n1->y - n11->y)); new->length = hypot(abs(n11->x - n2->x), abs(n11->y - n2->y)); + new->visited = 0; } void make_segments(void) @@ -746,48 +782,41 @@ void make_segments(void) } else { - printf("Warning: Skipping line\n"); + if (dbg_segments) + printf("Warning: Skipping line\n"); continue; // FIXME; } - printf("New longline\n"); + if (dbg_segments) + printf("New longline\n"); while (e) { - if (cur_length + e->length > conf_max_section_length + conf_max_section_overlay) + if (e->visited < 0) { - if (dbg_segments) - printf("Edge too long, length is %.2f; %.2f - %.2f = %.2f\n", e->length, conf_max_section_length, cur_length, conf_max_section_length - cur_length); - cut_edge(e, conf_max_section_length - cur_length); + printf("BEWARE: Edge cycle\n"); + break; } + e->visited = -1; // FIXME - if (cur_length + e->length > conf_max_section_length) - { - if (dbg_segments) - printf("Making new section, new length would be %f, allowed is %.2f / %.2f\n", cur_length + e->length, conf_max_section_length, conf_max_section_overlay); - - struct osm_node *n1 = e->n1->o; - struct osm_node *n2 = e->n2->o; - rs = make_new_segment(rls, e->label); - rs->x1 = n1->x; - rs->y1 = n1->y; - rs->x2 = n2->x; - rs->y2 = n2->y; - rs->zindex = e->zindex; - - rs->label = malloc(sizeof(struct sym_text)); - *((struct sym_text *) rs->label) = *((struct sym_text *) e->label); - rls = make_new_section(request); - cur_length = 0; - } + if (dbg_segments) + printf("Taking edge from [%.2f; %.2f] to [%.2f; %.2f] of length %.2f\n", e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y, e->length); if (st && (e->length < st->tw)) { e = e->next; - printf("Warning: Skipping segment\n"); + //printf("Warning: Skipping segment\n"); continue; } + if (cur_length + e->length > conf_max_section_length + conf_max_section_overlay) + { + if (dbg_segments) + printf("Edge too long, length is %.2f; %.2f - %.2f = %.2f\n", e->length, conf_max_section_length, cur_length, conf_max_section_length - cur_length); + // HACK to prevent cutting to 0 lenght + cut_edge(e, max2(conf_max_section_length - cur_length, 2)); + } + rs = make_new_segment(rls, e->label); rs->label = malloc(sizeof(struct sym_text)); *((struct sym_text *) rs->label) = *((struct sym_text *) e->label); @@ -802,6 +831,15 @@ void make_segments(void) rs->zindex = e->zindex; cur_length += e->length; + if (cur_length > conf_max_section_length) + { + if (dbg_segments) + printf("Making new section, new length would be %f, allowed is %.2f / %.2f\n", cur_length + e->length, conf_max_section_length, conf_max_section_overlay); + + rls = make_new_section(request); + cur_length = 0; + } + e = e->next; } @@ -849,39 +887,27 @@ void dump_bitmaps(struct individual *individual) for (uns i=0; iplacements); i++) { -fprintf(stderr, "%d-th placement\n", i); + if (individual->placements[i].variant_used == -1) continue; + struct placement *p = &(individual->placements[i]); - struct point_variant *v = NULL; + struct variant *v = NULL; switch (p->request->type) { case REQUEST_SEGMENT: ; - struct request_segment *rs = (struct request_segment *) p->request; - v = rs->variant; - break; case REQUEST_POINT: ; - struct request_point *rp = (struct request_point *) p->request; - v = &(rp->variants[p->variant_used]); - break; case REQUEST_AREA: ; - struct request_area *ra = (struct request_area *) p->request; - printf("Using %d-th of %d variants\n", p->variant_used, GARY_SIZE(ra->variants)); - v = &(ra->variants[p->variant_used]); + v = &(p->request->variants[p->variant_used]); break; default: - printf("Testing request type (dump_bitmaps): %d\n", p->request->type); ASSERT(p->request->type != REQUEST_INVALID); continue; } - printf("Got after with %d-th placement of request type %d\n", i, p->request->type); - - printf("Rendering %d-th label %d x %d (w x h)\n", i, v->width, v->height); for (int row = max2(p->y, 0); row < min2(p->y + v->height, page_height_int); row++) { for (int col = max2(p->x, 0); col < min2(p->x + v->width, page_width_int); col++) { - printf("Writing to %d\n", row*page_width_int + col); bitmap[row * page_width_int + col] = 1; } } @@ -949,6 +975,7 @@ void plan_individual(struct individual *individual) { struct symbol *s = NULL; z_index_t zindex = 0; + if (individual->placements[i].variant_used < 0) continue; switch (individual->placements[i].request->type) { case REQUEST_POINT: ; @@ -1009,11 +1036,8 @@ void labeller_label(void) { make_graph(); label_graph(); -//dump_graph(); bfs_wrapper(); -//dump_longlines(); make_segments(); -dump_linelabel_requests(); printf("Having %u point requests, %u line requests and %u area requests\n", GARY_SIZE(requests_point), GARY_SIZE(requests_line), GARY_SIZE(requests_area)); @@ -1035,9 +1059,6 @@ printf("Having %u point requests, %u line requests and %u area requests\n", GARY } */ - dump_individual(population1[0]); -//dump_bitmaps(population1[0]); - plan_individual(population1[0]); labeller_cleanup(); @@ -1053,43 +1074,43 @@ void make_population(void) { for (int i=0; iplacements[p++]), (struct request *) &requests_point[j]); + init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_point[j]); } for (uns j=0; jplacements[p++]), (struct request *) &requests_line[j]); + init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j]); for (uns k=0; kplacements[p++]), (struct request *) &requests_line[j].sections[k]); + init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k]); for (uns l=0; lplacements[p++]), (struct request *) &requests_line[j].sections[k].segments[l]); + init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k].segments[l]); } } } for (uns j=0; jplacements[p++]), (struct request *) &requests_area[j]); + init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_area[j]); } -if (p != num_requests) -{ - printf("Say bye\n"); - exit(42); -} + hide_segment_labels(individual); -printf("Testing p\n"); ASSERT(p == num_requests); } } @@ -1241,9 +1262,200 @@ void elite(void) } } +int overlaps(struct placement *p1, struct placement *p2) +{ + if (p1->request->type != REQUEST_POINT && + p1->request->type != REQUEST_SEGMENT && + p1->request->type != REQUEST_AREA) + return 0; + + if (p2->request->type != REQUEST_POINT && + p2->request->type != REQUEST_SEGMENT && + p2->request->type != REQUEST_AREA) + return 0; + + if (p1->variant_used == -1 || p2->variant_used == -1) + return 0; + + struct variant *v1, *v2; + + v1 = &(p1->request->variants[p1->variant_used]); + v2 = &(p2->request->variants[p2->variant_used]); + + int p1x = p1->x; int p1y = p1->y; + int p2x = p2->x; int p2y = p2->y; + + int overlap = 0; + for (int y=max2(p1y, p2y); y<=min2(p1y+v1->height, p2y+v2->height); y++) + for (int x=max2(p1x, p2x); x<=min2(p1x+v1->width, p2x+v2->width); x++) + { + if (v1->bitmap[(y-p1y)*v1->width + (x-p1x)] && + v2->bitmap[(y-p2y)*v2->width + (x-p2x)]) + overlap++; + } + + return overlap; +} + +int get_overlap(struct placement *p) +{ + struct map_part **parts = get_map_parts(p); + if (! parts) + { + if (dbg_overlaps) + printf("Placement of request %d seems not to be placed\n", p->request->ind); + return 0; + } + + struct placement **others; + bool *planned; + + GARY_INIT_ZERO(planned, num_requests); + planned[p->request->ind] = 1; + GARY_INIT(others, 0); + + for (uns i=0; iplacement->next; + while (mp) + { + if (! planned[mp->placement->request->ind]) + { + struct placement **p = GARY_PUSH(others); + *p = mp->placement; + planned[mp->placement->request->ind] = true; + } + mp = mp->next; + } + } + + int overlap = 0; + for (uns i=0; iplacements); i++) + { + overlap += get_overlap(&individual->placements[i]); + } + + return overlap; +} + +int cmp_individual(const void *a, const void *b) +{ + struct individual **ia = (struct individual **) a; + struct individual **ib = (struct individual **) b; + + return (*ia)->penalty - (*ib)->penalty; +} + void rank_population(void) { - // FIXME + int penalty; + + for (int i=0; ipenalty = 0; + + penalty = individual_overlap(population1[i]); + if (dbg_rank) + printf("Increasing penalty by %d for overlap\n", penalty); + population1[i]->penalty += penalty; + } +} + +struct map_part **get_map_parts(struct placement *p) +{ + if (p->variant_used < 0) return NULL; + + struct map_part **buffer; + GARY_INIT(buffer, 0); + + if (dbg_map_parts) + printf("Looking for map parts containing placement of request %d, placed at [%.2f; %.2f]\n", p->request->ind, p->x, p->y); + + struct variant v; + switch (p->request->type) + { + case REQUEST_POINT: + case REQUEST_SEGMENT: + case REQUEST_AREA: + v = p->request->variants[p->variant_used]; + break; + default: + return NULL; + } + + int x_min = max2(0, p->x) / conf_map_part_width; + int x_max = min2(page_width_int, (p->x + v.width + conf_map_part_width - 1)) / conf_map_part_width; + int y_min = max2(0, p->y) / conf_map_part_height; + int y_max = min2(page_height_int, (p->y + v.height + conf_map_part_height - 1)) / conf_map_part_height; + + if (dbg_map_parts) + printf("Cells between [%d; %d] and [%d; %d] generated\n", x_min, y_min, x_max, y_max); + + for (int y=y_min; y<=y_max; y++) + for (int x=x_min; x<=x_max; x++) + { + struct map_part **m = GARY_PUSH(buffer); + if (dbg_map_parts) + printf("Asking for %d of %u\n", y * num_map_parts_row + x, GARY_SIZE(p->individual->map)); + *m = p->individual->map[y * num_map_parts_row + x]; + } + + return buffer; +} + +void update_map_parts(struct placement *p) +{ + struct placement_link *ml = p->map_links; + while (ml) + { + struct map_placement *mp = ml->mp; + mp->prev = mp->next; + if (mp->next) + mp->next->prev = mp->prev; + free(mp); + + struct placement_link *tmp = ml; + ml = ml->next; + free(tmp); + } + + struct map_part **parts = get_map_parts(p); + if (parts == NULL) return; + + for (uns i=0; iplacement = p; + + mp->next = parts[i]->placement->next; + parts[i]->placement->next = mp; + if (mp->next) mp->next->prev = mp; + + struct placement_link *ml = malloc(sizeof(struct placement_link)); + ml->mp = mp; + ml->next = p->map_links; + p->map_links = ml; + } + + GARY_FREE(parts); } void gen_coords(struct placement *p) @@ -1260,19 +1472,24 @@ void gen_coords(struct placement *p) gen_coords_segment(p); break; case REQUEST_LINE: - printf("Not yet implemented\n"); + if (dbg_movement) + printf("Not yet implemented\n"); break; default: - printf("Testing request type\n"); + if (dbg_movement) + printf("Testing request type\n"); ASSERT(p->request->type != REQUEST_INVALID); } + + update_map_parts(p); } double gen_movement(void) { double m = (random() % 1000000) / 10000; m = pow(m, 1.0/3) * flip(1, -1); - printf("Movement %.2f\n", m); + if (dbg_movement) + printf("Movement %.2f\n", m); return m; } @@ -1296,7 +1513,8 @@ void gen_coords_area(struct placement *p) p->x = p->x + gen_movement(); p->y = p->y + gen_movement(); - printf("Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy); + if (dbg_movement) + printf("Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy); } struct map_part **get_parts(struct placement *symbol, struct individual *individual) @@ -1376,7 +1594,8 @@ void move_symbol(struct placement *p) case REQUEST_LINE: case REQUEST_SEGMENT: case REQUEST_AREA: - printf("Not yet implemented\n"); + if (dbg_movement) + printf("Not yet implemented\n"); default: ASSERT(p->request->type != REQUEST_INVALID); } @@ -1388,13 +1607,41 @@ void move_symbol_point(struct placement *p) p->y += (double) (move_min + randdouble()) * flip(1, -1); } -void init_placement(struct placement *p, struct request *r) +void hide_segment_labels(struct individual *individual) +{ + // BEWARE: This fully depends on current genetic encoding + + int used = -1, num = -1; + for (uns i=0; iplacements); i++) + { + switch (individual->placements[i].request->type) + { + case REQUEST_SECTION: + used = individual->placements[i].variant_used; + num = 0; + break; + case REQUEST_SEGMENT: + if (num == used) + individual->placements[i].variant_used = 0; + else + individual->placements[i].variant_used = -1; + num++; + break; + default: + ; + } + } +} + +void init_placement(struct placement *p, struct individual *individual, struct request *r) { // FIXME p->request = r; p->processed = 0; p->x = p->y = 0; // To prevent valgrind from complaining p->variant_used = 0; + p->map_links = NULL; + p->individual = individual; switch (r->type) { case REQUEST_POINT: ; @@ -1425,7 +1672,8 @@ void init_placement(struct placement *p, struct request *r) } gen_coords(p); -// printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y); + if (dbg_init) + printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y); } void init_individual(struct individual *i) @@ -1433,7 +1681,18 @@ void init_individual(struct individual *i) //printf("Initing individual\n"); GARY_INIT(i->placements, num_requests); GARY_INIT(i->map, 0); + for (uns j=0; jmap); + GARY_INIT(part->placement, 0); + struct map_placement *mp = GARY_PUSH(part->placement); + mp->placement = &dummy_placement; + mp->next = mp->prev = NULL; + } i->penalty = 0; // FIXME + + if (dbg_init) + printf("Individual inited, has %u map parts\n", GARY_SIZE(i->map)); } struct placement **get_overlapping(struct placement *p UNUSED) @@ -1455,8 +1714,7 @@ int flip(int a, int b) double randdouble(void) { - // FIXME: How the hell shall double in range <0, 1> be generated? O:) - return 0.5; + return ((double) rand() / (double) RAND_MAX); } void cleanup(void) @@ -1469,10 +1727,19 @@ void cleanup(void) void copy_individual(struct individual *src, struct individual *dest) { - src->penalty = dest->penalty; + dest->penalty = src->penalty; GARY_INIT(dest->placements, GARY_SIZE(src->placements)); for (uns i=0; iplacements); i++) { dest->placements[i] = src->placements[i]; + dest->placements[i].map_links = NULL; + } + for (uns j=0; jmap); + GARY_INIT(part->placement, 0); + struct map_placement *mp = GARY_PUSH(part->placement); + mp->placement = &dummy_placement; + mp->next = mp->prev = NULL; } }