3 #include <ucw/mempool.h>
4 #include <ucw/eltpool.h>
11 #define HASH_NODE struct graph_node
12 #define HASH_PREFIX(x) hash_##x
13 #define HASH_KEY_ATOMIC id
14 #define HASH_WANT_FIND
16 #define HASH_WANT_CLEANUP
17 #include <ucw/hashtable.h>
25 #define BLOCK_SIZE 4096
27 static struct request_point *requests_point;
28 static struct request_line *requests_line;
29 static struct request_area *requests_area;
31 static struct graph_edge **bfs_queue;
32 static struct longline *longlines; int num_longlines;
33 static struct buffer_line *buffer_line;
34 static struct buffer_linelabel *buffer_linelabel;
36 struct eltpool *ep_individuals;
38 struct individual **population1;
39 struct individual **population2;
41 int dbg_segments = VERBOSITY_NONE;
42 int dbg_plan = VERBOSITY_NONE;
43 int dbg_requests = VERBOSITY_NONE;
44 int dbg_graph = VERBOSITY_NONE;
45 int dbg_bfs = VERBOSITY_NONE;
46 int dbg_map_parts = VERBOSITY_NONE;
47 int dbg_movement = VERBOSITY_NONE;
48 int dbg_init = VERBOSITY_NONE;
49 int dbg_overlaps = VERBOSITY_NONE;
50 int dbg_rank = VERBOSITY_NONE;
51 int dbg_evolution = VERBOSITY_INDIVIDUAL;
52 int dbg_mutation = VERBOSITY_NONE;
53 int dbg_breeding = VERBOSITY_NONE;
62 int conf_pop_size = 50;
64 int conf_penalty_bound = 0;
65 int conf_stagnation_bound = 0;
66 int conf_iteration_limit = 100;
68 int conf_term_cond = TERM_COND_ITERATIONS;
70 double conf_breed_pop_size = 0.4;
71 double conf_breed_rbest = 0.2;
76 bool conf_mutate_children = 1;
77 double conf_mutate_children_prob = 1.0;
79 double conf_mutate_pop_size = 0.4;
80 double conf_mutate_rbest = 0.2;
82 double conf_mutate_move_bound = 0.1;
83 double conf_mutate_regen_bound = 0.0;
84 double conf_mutate_chvar_bound = 0.0;
87 int mutate_rbest_size;
89 double conf_elite_pop_size = 0.2;
92 double conf_max_section_length = 100;
93 double conf_max_section_overlay = 10;
95 int old_best = INT_MAX;
103 int num_requests = 0;
104 int num_placements = 0;
107 int conf_map_part_width = 5;
108 int conf_map_part_height = 5;
110 uns num_map_parts_row;
111 uns num_map_parts_col;
114 void compute_sizes(void);
116 void make_population(void);
117 bool shall_terminate(void);
121 void rank_population(void);
122 void plan_individual(struct individual *individual);
124 int overlaps(struct placement *p1, struct placement *p2);
125 int get_overlap(struct placement *p);
126 int individual_overlap(struct individual *individual);
128 double get_distance(struct placement *p);
129 double individual_distances(struct individual *individual);
131 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2);
132 void perform_mutation(struct individual *individual);
133 void init_placement(struct placement *p, struct individual *individual, struct request *r);
134 void init_individual(struct individual *i);
135 void copy_individual(struct individual *src, struct individual *dest);
136 int cmp_individual(const void *a, const void *b);
138 void make_bitmap(struct variant *v, struct symbol *sym);
139 void make_bitmap_icon(struct variant *v, struct sym_icon *si);
140 void make_bitmap_point(struct variant *v, struct sym_point *sp);
141 void make_bitmap_label(struct variant *v, struct sym_text *text);
143 double gen_movement(void);
144 double gen_movement_uniform(void);
145 void move_symbol(struct placement *p);
146 void move_symbol_point(struct placement *p);
147 void move_symbol_segment(struct placement *p);
148 void hide_segment_labels(struct individual *individual);
150 void gen_coords(struct placement *p);
151 void gen_coords_point(struct placement *p);
152 void gen_coords_segment(struct placement *p);
153 void gen_coords_area(struct placement *p);
155 struct map_part **get_map_parts(struct placement *p);
156 void update_map_parts(struct placement *p);
157 struct placement **get_closure(struct placement *placement);
158 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child, bool **processed_ptr);
159 struct placement **get_overlapping(struct placement *p);
160 struct placement **filter(struct placement **list, bool **pred_ptr);
163 void make_graph(void);
164 void label_graph(void);
165 void bfs_wrapper(void);
166 void bfs(uns longline);
167 void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir);
168 void make_segments(void);
170 void cut_edge(struct graph_edge *e, double dist);
171 struct request_line *make_new_line(void);
172 struct request_section *make_new_section(struct request_line *rl);
173 struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym);
175 void dump_bitmaps(struct individual *individual);
176 void dump_graph(void);
177 void dump_longlines(void);
178 void dump_linelabel_requests(void);
179 void dump_individual(struct individual *individual);
180 void dump_label(struct symbol *sym);
181 void dump_penalties(struct individual **population);
183 int randint(int min, int max);
184 int flip(int a, int b);
185 double randdouble(void);
187 int max2(int a, int b);
188 int min2(int a, int b);
189 int max4(int a, int b, int c, int d);
190 int min4(int a, int b, int c, int d);
192 struct placement dummy_placement;
194 int max2(int a, int b)
196 return (a > b ? a : b);
199 int min2(int a, int b)
201 return (a < b ? a : b);
204 int max4(int a, int b, int c, int d)
206 return max2(max2(a, b), max2(c, d));
209 int min4(int a, int b, int c, int d)
211 return min2(min2(a, b), min2(c, d));
214 void dump_label(struct symbol *sym)
218 case SYMBOLIZER_TEXT: ;
219 struct sym_text *st = (struct sym_text *) sym;
220 printf("%s\n", osm_val_decode(st->text));
227 void labeller_init(void)
229 GARY_INIT(requests_point, 0);
230 GARY_INIT(requests_line, 0);
231 GARY_INIT(requests_area, 0);
232 GARY_INIT(buffer_line, 0);
233 GARY_INIT(buffer_linelabel, 0);
234 ep_individuals = ep_new(sizeof(struct individual), 1);
239 void make_bitmap(struct variant *v, struct symbol *sym)
241 v->offset_x = v->offset_y = 0;
245 case SYMBOLIZER_POINT:
246 make_bitmap_point(v, (struct sym_point *) sym);
248 case SYMBOLIZER_ICON:
249 make_bitmap_icon(v, (struct sym_icon *) sym);
251 case SYMBOLIZER_TEXT:
252 make_bitmap_label(v, (struct sym_text *) sym);
255 ASSERT(sym->type != SYMBOLIZER_INVALID);
259 void make_bitmap_icon(struct variant *v, struct sym_icon *si)
261 v->width = si->sir.width + 1;
262 v->height = si->sir.height + 1;
263 v->bitmap = malloc(v->width * v->height * sizeof(bool));
264 for (int i=0; i<v->width*v->height; i++) v->bitmap[i] = 1;
267 void make_bitmap_point(struct variant *v, struct sym_point *sp)
269 v->width = v->height = sp->size + 1;
270 v->bitmap = malloc(v->width * v->height * sizeof(bool));
271 // FIXME: Okay, memset would be much nicer here
272 for (int i=0; i<sp->size*sp->size; i++) v->bitmap[i] = 1;
275 void make_bitmap_label(struct variant *v, struct sym_text *text)
277 v->width = ceil(text->tw);
278 v->height = ceil(text->th);
279 v->bitmap = malloc(v->width * v->height * sizeof(bool));
280 for (int i=0; i<v->height; i++)
281 for (int j=0; j<v->width; j++)
283 v->bitmap[i*v->width + j] = 1;
287 void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex)
289 if (dbg_requests >= VERBOSITY_PLACEMENT)
290 printf("Adding point\n");
291 if (object->type != OSM_TYPE_NODE)
293 printf("Warning: Point label requested on non-point object\n");
297 struct request_point *r = GARY_PUSH(requests_point);
299 r->request.type = REQUEST_POINT;
300 r->request.ind = num_requests++;
309 GARY_INIT(r->request.variants, 0);
311 struct variant *v = GARY_PUSH(r->request.variants);
313 struct osm_node *n = (struct osm_node *) object; // FIXME: Compiler warning
319 case SYMBOLIZER_ICON:
321 r->x = ((struct sym_icon *)sym)->sir.x;
322 r->y = ((struct sym_icon *)sym)->sir.y;
329 if (dbg_requests >= VERBOSITY_PLACEMENT)
330 printf("Inited point to [%.2f; %.2f] on %u\n", r->x, r->y, r->zindex);
333 void labeller_add_line(struct symbol *sym, z_index_t zindex)
335 if (dbg_requests >= VERBOSITY_PLACEMENT)
336 printf("Adding line on %u\n", zindex);
337 struct buffer_line *b = GARY_PUSH(buffer_line);
338 b->line = (struct sym_line *) sym;
340 sym_plan(sym, zindex);
343 void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
345 if (o->type != OSM_TYPE_WAY)
347 printf("Linelabel request on object which is not way\n");
351 if (dbg_requests >= VERBOSITY_PLACEMENT)
352 printf("Labelling way %ju on %u\n", o->id, zindex);
353 struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
354 ll->way = (struct osm_way *) o;
359 void labeller_add_arealabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
361 if (dbg_requests >= VERBOSITY_PLACEMENT)
362 printf("Adding area on %u\n", zindex);
363 struct request_area *r = GARY_PUSH(requests_area);
365 r->request.type = REQUEST_AREA;
366 r->request.ind = num_requests++;
368 r->o = (struct osm_multipolygon *) o;
372 osm_obj_center(o, &(r->cx), &(r->cy));
374 GARY_INIT(r->request.variants, 0);
375 struct variant *v = GARY_PUSH(r->request.variants);
379 void make_graph(void)
382 struct mempool *mp_edges = mp_new(BLOCK_SIZE);
384 if (dbg_graph >= VERBOSITY_GENERAL)
385 printf("Extracting nodes, will iterate over %lld ways\n", GARY_SIZE(buffer_line));
386 for (uns i=0; i<GARY_SIZE(buffer_line); i++)
388 struct osm_way *way = (struct osm_way *) buffer_line[i].line->s.o;
389 struct graph_node *g_prev = NULL;
390 struct osm_node *o_prev = NULL;
392 CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
394 // FIXME: Shall osm_object's type be checked here?
395 struct osm_node *o_node = (struct osm_node *) ref->o;
397 struct graph_node *g_node = hash_find(ref->o->id);
400 g_node = hash_new(ref->o->id);
401 GARY_INIT(g_node->edges, 0);
403 g_node->id = ref->o->id;
404 g_node->num = num_nodes++;
414 struct graph_edge *e = mp_alloc(mp_edges, sizeof(struct graph_edge));
415 e->num = num_edges++;
416 e->id = buffer_line[i].line->s.o->id;
417 e->color = buffer_line[i].line->color;
418 e->length = hypot(abs(o_prev->x - o_node->x), abs(o_prev->y - o_node->y));
424 e->longline = (uns) -1;
425 e->line = buffer_line[i].line;
429 struct graph_edge **edge = GARY_PUSH(g_prev->edges);
431 edge = GARY_PUSH(g_node->edges);
440 void dump_graph(void)
442 HASH_FOR_ALL(hash, node)
444 printf("* Node: (%d) #%ju [%.2f; %.2f]\n", node->num, node->id, node->o->x, node->o->y);
445 for (uns i=0; i<GARY_SIZE(node->edges); i++)
447 struct graph_edge *e = node->edges[i];
448 printf("\t edge (%d) #%ju to ", e->num, e->id);
449 if (node->edges[i]->n1->id == node->id)
450 printf("(%d) #%ju [%.2f; %.2f]\n", e->n2->num, e->n2->id, e->n2->o->x, e->n2->o->y);
451 else if (node->edges[i]->n2->id == node->id)
452 printf("(%d) #%ju [%.2f; %.2f]\n", e->n1->num, e->n1->id, e->n1->o->x, e->n1->o->y);
455 // This shouldn't ever happen
456 printf("BEWARE! Edge is associated with a node it doesn't belongs to!\n");
461 if ((node->edges[i]->label) && (node->edges[i]->label->type == SYMBOLIZER_TEXT)) printf(" labelled %s;", osm_val_decode(((struct sym_text *) node->edges[i]->label)->text));
462 else if ((node->edges[i]->label)) printf("Labelled\n");
464 printf(" colored %d;", node->edges[i]->color);
465 printf(" length %.2f", node->edges[i]->length);
472 void label_graph(void)
474 if (dbg_graph >= VERBOSITY_GENERAL)
475 printf("There are %u line labels requested\n", GARY_SIZE(buffer_linelabel));
476 for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
478 if (buffer_linelabel[i].label->type == SYMBOLIZER_TEXT)
479 if (dbg_graph >= VERBOSITY_INDIVIDUAL)
480 printf("Labelling nodes of way %s\n", osm_val_decode(((struct sym_text *) buffer_linelabel[i].label)->text));
481 CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
483 if (dbg_graph >= VERBOSITY_PLACEMENT)
484 printf("Looking for node %ju\n", ref->o->id);
485 struct graph_node *n = hash_find(ref->o->id);
488 printf("BEWARE! Requested node couldn't be found.\n");
492 if (dbg_graph >= VERBOSITY_ALL)
493 printf("Searching among %u edges\n", GARY_SIZE(n->edges));
494 for (uns j=0; j<GARY_SIZE(n->edges); j++)
496 if (n->edges[j]->id == buffer_linelabel[i].way->o.id)
498 if (dbg_graph >= VERBOSITY_ALL)
499 printf("Labelling node %ju\n", n->id);
500 n->edges[j]->label = buffer_linelabel[i].label;
501 n->edges[j]->zindex = buffer_linelabel[i].zindex;
509 void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir)
511 if (dbg_bfs >= VERBOSITY_PLACEMENT)
512 printf("BFS edge called for edge %d (going %d) in direction %d\n", e->num, e->dir, dir);
513 struct graph_edge *candidate = NULL;
515 for (uns i=0; i<GARY_SIZE(node->edges); i++)
517 struct graph_edge *other = node->edges[i];
518 if ((other->longline != (uns) -1) && (other->longline != e->longline)) continue;
520 if ((uns) other->visited != e->longline) {
521 if (dbg_bfs >= VERBOSITY_PLACEMENT)
522 printf("Pushing new edge %d / %ju\n", other->num, other->id);
523 struct graph_edge **e_ptr = GARY_PUSH(bfs_queue);
525 other->visited = e->longline;
528 if (((other->n1->id == node->id) && (other->n2->id == anode->id)) ||
529 ((other->n2->id == node->id) && (other->n1->id == anode->id)))
532 if (((other->n1->id == node->id) || (other->n2->id == node->id)) &&
533 (e->label) && (other->label) &&
534 (e->label->type == SYMBOLIZER_TEXT) && (other->label->type == SYMBOLIZER_TEXT) &&
535 (((struct sym_text *) e->label)->text == ((struct sym_text *) other->label)->text))
537 if (! candidate || (other->length > candidate->length))
544 if (dbg_bfs >= VERBOSITY_PLACEMENT)
545 printf("New line in longline %u\n", e->longline);
546 struct graph_edge *other = candidate;
547 other->longline = e->longline;
549 if (((dir == DIR_BWD) && (other->n1->id == node->id)) ||
550 ((dir == DIR_FWD) && (other->n2->id == node->id)))
552 struct graph_node *swp = other->n2;
553 other->n2 = other->n1;
562 longlines[other->longline].first = other;
575 void bfs(uns longline)
577 if (dbg_bfs >= VERBOSITY_INDIVIDUAL)
579 printf("BFS called for longline %u\n", longline);
580 printf("%d longlines are believed to exist, %d exist\n", num_longlines, GARY_SIZE(longlines));
583 for (uns i=0; i<GARY_SIZE(bfs_queue); i++)
585 struct graph_edge *cur = bfs_queue[i];
586 if (dbg_bfs >= VERBOSITY_PLACEMENT)
587 printf("Exploring new edge %d; %d remaining\n", cur->num, GARY_SIZE(bfs_queue));
589 cur->visited = longline;
591 if (cur->longline == (uns) -1)
594 if (cur->dir == DIR_UNSET)
596 cur->dir = DIR_CENTER;
597 bfs_edge(cur, cur->n1, cur->n2, DIR_BWD);
598 bfs_edge(cur, cur->n2, cur->n1, DIR_FWD);
605 bfs_edge(cur, cur->n1, cur->n2, cur->dir);
608 bfs_edge(cur, cur->n2, cur->n1, cur->dir);
618 void bfs_wrapper(void)
620 GARY_INIT(bfs_queue, 0);
621 GARY_INIT(longlines, 0);
623 HASH_FOR_ALL(hash, node)
625 for (uns i=0; i<GARY_SIZE(node->edges); i++)
627 if ((node->edges[i]->label) && (node->edges[i]->longline == (uns) -1))
629 GARY_PUSH(longlines);
630 longlines[num_longlines].first = node->edges[i];
632 if (dbg_bfs >= VERBOSITY_INDIVIDUAL)
634 printf("Running new BFS\n");
635 printf("Creating longline %u\n", num_longlines);
638 GARY_RESIZE(bfs_queue, 0);
639 struct graph_edge **e = GARY_PUSH(bfs_queue);
641 node->edges[i]->longline = num_longlines;
642 bfs(node->edges[i]->longline);
644 if (dbg_bfs >= VERBOSITY_INDIVIDUAL)
646 printf("Joined %d edges\n", dbg_num_hits); dbg_num_hits = 0;
647 printf("Planned %u edges\n", GARY_SIZE(bfs_queue));
655 GARY_FREE(bfs_queue);
658 void dump_longlines(void)
660 printf("*** Longlines dump\n");
661 for (uns i=0; i<GARY_SIZE(longlines); i++)
663 printf("Longline %u:", i);
664 struct graph_edge *e = longlines[i].first;
665 if ((e->label) && (e->label->type == SYMBOLIZER_TEXT))
666 printf(" labelled %s", osm_val_decode(((struct sym_text *) e->label)->text));
671 printf("\t#%ju (%d): [%.2f; %.2f] -- [%.2f; %.2f] (dir %d)\n",
672 e->id, e->num, e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y, e->dir);
679 struct request_line *make_new_line(void)
681 struct request_line *rl = GARY_PUSH(requests_line);
682 rl->request.ind = num_requests++;
683 rl->request.type = REQUEST_LINE;
684 GARY_INIT(rl->sections, 0);
685 GARY_INIT(rl->request.variants, 0);
690 struct request_section *make_new_section(struct request_line *rl)
692 struct request_section *rls = GARY_PUSH(rl->sections);
693 rls->request.ind = num_requests++;
694 rls->request.type = REQUEST_SECTION;
695 rls->num_segments = 0;
696 GARY_INIT(rls->segments, 0);
697 GARY_INIT(rls->request.variants, 0);
702 struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym)
704 struct request_segment *rs = GARY_PUSH(rls->segments);
707 rs->request.ind = num_requests++;
708 rs->request.type = REQUEST_SEGMENT;
710 GARY_INIT(rs->request.variants, 0);
711 struct variant *v = GARY_PUSH(rs->request.variants);
717 void cut_edge(struct graph_edge *e, double dist)
719 if (dbg_segments >= VERBOSITY_PLACEMENT)
720 printf("Cutting [%.2f; %.2f] -- [%.2f; %.2f] to dist %.2f\n", e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y, dist);
722 struct graph_edge *new = malloc(sizeof(struct graph_edge));
726 switch (e->label->type)
728 case SYMBOLIZER_TEXT:
729 new->label = malloc(sizeof(struct sym_text));
730 *((struct sym_text *) new->label) = *((struct sym_text *) e->label);
736 struct osm_node *n1 = e->n1->o;
737 struct osm_node *n2 = e->n2->o;
739 if ((n1->x == n2->x) && (n1->y == n2->y))
741 printf("[%.2f; %.2f] -- [%.2f; %.2f]\n", n1->x, n1->y, n2->x, n2->y);
742 if (dbg_segments >= VERBOSITY_PLACEMENT)
743 printf("Won't cut point\n");
747 struct osm_node *n11 = malloc(sizeof(struct osm_node));
748 struct graph_node *gn = malloc(sizeof(struct graph_node));
750 double vsize = sqrt(pow(n1->x - n2->x, 2) + pow(n1->y - n2->y, 2));
751 n11->x = n1->x + (n2->x - n1->x) / vsize * dist;
752 n11->y = n1->y + (n2->y - n1->y) / vsize * dist;
754 e->n2 = new->n1 = gn;
756 e->length = hypot(abs(n1->x - n11->x), abs(n1->y - n11->y));
757 new->length = hypot(abs(n11->x - n2->x), abs(n11->y - n2->y));
761 void make_segments(void)
763 for (uns i=0; i<GARY_SIZE(longlines); i++)
765 // Skip lines which are not labelled
766 if (! (longlines[i].first && longlines[i].first->label))
769 struct request_line *request = make_new_line();
770 struct request_section *rls = make_new_section(request);
771 struct request_segment *rs = NULL;
773 struct graph_edge *e = longlines[i].first;
774 double cur_length = 0;
776 struct sym_text *st = NULL;
777 if (e->label->type == SYMBOLIZER_TEXT)
779 st = (struct sym_text *) e->label;
783 // FIXME: Should other label types be supported in future?
784 if (dbg_segments >= VERBOSITY_PLACEMENT)
785 printf("Warning: Skipping line\n");
789 if (dbg_segments >= VERBOSITY_INDIVIDUAL)
790 printf("New longline\n");
796 if (dbg_segments >= VERBOSITY_PLACEMENT)
797 printf("BEWARE: Edge cycle\n");
802 if (dbg_segments >= VERBOSITY_PLACEMENT)
803 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);
805 if (st && (e->length < st->tw))
808 if (dbg_segments >= VERBOSITY_PLACEMENT)
809 printf("Warning: Skipping segment\n");
813 if (cur_length + e->length > conf_max_section_length + conf_max_section_overlay)
815 if (dbg_segments >= VERBOSITY_PLACEMENT)
816 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);
817 // HACK to prevent cutting to 0 lenght
818 cut_edge(e, max2(conf_max_section_length - cur_length, 2));
821 rs = make_new_segment(rls, e->label);
822 rs->label = malloc(sizeof(struct sym_text));
823 *((struct sym_text *) rs->label) = *((struct sym_text *) e->label);
825 rs->x1 = e->n1->o->x;
826 rs->y1 = e->n1->o->y;
827 rs->x2 = e->n2->o->x;
828 rs->y2 = e->n2->o->y;
830 rs->slope = (rs->y2 - rs->y1) / (rs->x2 - rs->x1);
831 rs->zindex = e->zindex;
833 cur_length += e->length;
834 if (cur_length > conf_max_section_length)
836 if (dbg_segments >= VERBOSITY_PLACEMENT)
837 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);
839 rls = make_new_section(request);
846 if (request->sections[0].num_segments == 0)
848 if (dbg_segments >= VERBOSITY_INDIVIDUAL)
849 printf("WARNING: Longline without any segment, skipped\n");
850 GARY_POP(requests_line);
856 void dump_linelabel_requests(void)
858 for (uns i=0; i<GARY_SIZE(requests_line); i++)
860 if (requests_line[i].sections[0].num_segments == 0)
862 if (dbg_segments >= VERBOSITY_INDIVIDUAL)
863 printf("Beware: Longline without any segment\n");
867 printf("Request for linelabel, %d sections\n", GARY_SIZE(requests_line[i].sections));
868 dump_label(requests_line[i].sections[0].segments[0].label);
869 for (uns j=0; j<GARY_SIZE(requests_line[i].sections); j++)
871 printf("%d section, %d segments\n", j, GARY_SIZE(requests_line[i].sections[j].segments));
872 for (uns k=0; k<GARY_SIZE(requests_line[i].sections[j].segments); k++)
874 struct request_segment *rs = &requests_line[i].sections[j].segments[k];
875 printf("[%.2f; %.2f] -- [%.2f; %.2f]\n", rs->x1, rs->y1, rs->x2, rs->y2);
882 void dump_bitmaps(struct individual *individual)
884 bool *bitmap = malloc(page_width_int * page_height_int * sizeof(bool));
885 printf("Bitmap size is %d\n", page_width_int * page_height_int);
886 for (int i=0; i<page_height_int; i++)
887 for (int j=0; j<page_width_int; j++)
888 bitmap[i*page_width_int + j] = 0;
891 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
893 if (individual->placements[i].variant_used == -1) continue;
895 struct placement *p = &(individual->placements[i]);
896 struct variant *v = NULL;
898 switch (p->request->type)
900 case REQUEST_SEGMENT: ;
901 case REQUEST_POINT: ;
903 v = &(p->request->variants[p->variant_used]);
906 ASSERT(p->request->type != REQUEST_INVALID);
910 for (int row = max2(p->y, 0); row < min2(p->y + v->height, page_height_int); row++)
912 for (int col = max2(p->x, 0); col < min2(p->x + v->width, page_width_int); col++)
914 if (bitmap[row * page_width_int + col] == 1) total += 1;
915 bitmap[row * page_width_int + col] = 1;
919 if (dbg_overlaps >= VERBOSITY_GENERAL)
920 printf("There were %d collisions during bitmap dump\n", total);
922 FILE *fd_dump = fopen("dump.pbm", "w");
923 fprintf(fd_dump, "P1\n");
924 fprintf(fd_dump, "%d %d\n", page_width_int, page_height_int);
925 for (int i=0; i<page_height_int; i++)
927 for (int j=0; j<page_width_int; j++)
929 fprintf(fd_dump, "%d", bitmap[(int) (i*page_width_int + j)] ? 1 : 0);
931 fprintf(fd_dump, "\n");
936 void dump_individual(struct individual *individual)
938 printf("*** Individual dump\n");
939 printf("(There are %d requests)\n", num_requests);
941 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
943 struct placement *p = &(individual->placements[i]);
945 switch (p->request->type)
948 printf("Point at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_point *) p->request)->zindex);
951 struct request_line *rl = (struct request_line *) p->request;
953 dump_label(rl->sections[0].segments[0].label);
955 case REQUEST_SECTION: ;
958 case REQUEST_SEGMENT: ;
959 if (p->variant_used >= 0)
960 printf("Segment placed at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_segment *) p->request)->zindex);
962 printf("Segment not placed\n");
965 struct request_area *ra = (struct request_area *) p->request;
966 printf("Area label ");
967 dump_label(ra->label);
968 printf(" at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_area *) p->request)->zindex);
971 ASSERT(p->request->type != 0);
974 printf("\nTotal penalty: %d\n", individual->penalty);
977 void plan_individual(struct individual *individual)
979 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
981 struct symbol *s = NULL;
982 z_index_t zindex = 0;
983 if (individual->placements[i].variant_used < 0) continue;
984 switch (individual->placements[i].request->type)
986 case REQUEST_POINT: ;
987 struct request_point *rp = (struct request_point *) individual->placements[i].request;
991 case REQUEST_SEGMENT: ;
992 struct request_segment *rs = (struct request_segment *) individual->placements[i].request;
999 struct request_area *ra = (struct request_area *) individual->placements[i].request;
1001 zindex = ra->zindex;
1004 ASSERT(individual->placements[i].request != REQUEST_INVALID);
1008 if (dbg_plan >= VERBOSITY_PLACEMENT)
1009 printf("Will plan symbol at [%.2f; %.2f] on %u\n", individual->placements[i].x, individual->placements[i].y, zindex);
1011 if (s) switch (s->type)
1013 case SYMBOLIZER_POINT: ;
1014 struct sym_point *sp = (struct sym_point *) s;
1015 sp->x = individual->placements[i].x;
1016 sp->y = individual->placements[i].y;
1017 sym_plan((struct symbol *) sp, zindex);
1019 case SYMBOLIZER_ICON: ;
1020 struct sym_icon *si = (struct sym_icon *) s;
1021 si->sir.x = individual->placements[i].x;
1022 si->sir.y = individual->placements[i].y;
1023 sym_plan((struct symbol *) si, zindex);
1025 case SYMBOLIZER_TEXT: ;
1026 struct sym_text *st = (struct sym_text *) s;
1027 st->x = individual->placements[i].x;
1028 st->y = individual->placements[i].y;
1029 st->next_duplicate = NULL;
1030 if (dbg_plan >= VERBOSITY_PLACEMENT)
1031 printf("Planning text %s at [%.2f; %.2f] on %u, with rotation %.2f\n", osm_val_decode(st->text), st->x, st->y, zindex, st->rotate);
1032 sym_plan((struct symbol *) st, zindex);
1035 ASSERT(s->type != SYMBOLIZER_INVALID);
1040 void dump_penalties(struct individual **population)
1042 for (int i=0; i<conf_pop_size; i++)
1044 printf("Individual %d has penalty %d\n", i, population[i]->penalty);
1048 void compute_sizes(void)
1050 page_width_int = floor(page_width);
1051 page_height_int = floor(page_height);
1053 num_map_parts_row = (page_width_int + conf_map_part_width) / conf_map_part_width;
1054 num_map_parts_col = (page_height_int + conf_map_part_height) / conf_map_part_height;
1055 num_map_parts = num_map_parts_row * num_map_parts_col;
1057 breed_pop_size = conf_breed_pop_size * conf_pop_size;
1058 breed_rbest_size = conf_breed_rbest * conf_pop_size;
1059 if (dbg_evolution >= VERBOSITY_GENERAL)
1061 printf("Breeding parameters:\n");
1062 printf(" %d individuals are created\n", breed_pop_size);
1063 printf(" %d best individuals in old population are considered\n", breed_rbest_size);
1066 mutate_pop_size = conf_mutate_pop_size * conf_pop_size;
1067 mutate_rbest_size = conf_mutate_rbest * conf_pop_size;
1068 if (dbg_evolution >= VERBOSITY_GENERAL)
1070 printf("Mutation parameters:\n");
1071 printf(" %d individuals are created\n", mutate_pop_size);
1072 printf(" %d best individuals in old population are considered\n", mutate_rbest_size);
1075 elite_pop_size = conf_elite_pop_size * conf_pop_size;
1076 if (dbg_evolution >= VERBOSITY_GENERAL)
1078 printf("Elitism parameters:\n");
1079 printf(" %d best individuals are copied\n", elite_pop_size);
1082 if (breed_pop_size + mutate_pop_size + elite_pop_size != conf_pop_size)
1084 fprintf(stderr, "Breeding + mutation + elitism won't create correct number of individuals\n");
1085 fprintf(stderr, "Please fix conf_breed_pop_size, conf_mutate_pop_size and conf_elite_pop_size parameters\n");
1090 void labeller_label(void)
1097 GARY_INIT(population1, conf_pop_size);
1098 GARY_INIT(population2, conf_pop_size);
1101 qsort(population1, conf_pop_size, sizeof(struct individual *), cmp_individual);
1103 if (dbg_evolution >= VERBOSITY_GENERAL)
1105 printf("Penalties after initialization\n");
1106 dump_penalties(population1);
1109 while (! shall_terminate())
1113 printf("\n*** Iteration %d ***\n", iteration);
1119 struct individual **swp = population1;
1120 population1 = population2;
1126 if (dbg_evolution >= VERBOSITY_GENERAL)
1127 printf("Sorting population\n");
1128 qsort(population1, conf_pop_size, sizeof(struct individual *), cmp_individual);
1130 if (dbg_evolution >= VERBOSITY_GENERAL)
1132 printf("Penalties after sort\n");
1133 dump_penalties(population1);
1136 old_best = population1[0]->penalty;
1139 if (dbg_overlaps >= VERBOSITY_GENERAL)
1140 dump_bitmaps(population1[0]);
1142 plan_individual(population1[0]);
1149 void labeller_cleanup(void)
1152 GARY_FREE(requests_point);
1153 GARY_FREE(requests_line);
1154 GARY_FREE(requests_area);
1157 void make_population(void)
1159 for (int i=0; i<conf_pop_size; i++)
1161 num_placements = 0; // FIXME: This IS a terrible HACK
1162 struct individual *i2 = ep_alloc(ep_individuals);
1163 init_individual(i2);
1164 population2[i] = i2;
1166 if (dbg_init >= VERBOSITY_INDIVIDUAL)
1167 printf("Making individual %d\n", i);
1168 struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
1169 population1[i] = individual;
1172 for (uns j=0; j<GARY_SIZE(requests_point); j++)
1174 init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_point[j]);
1177 for (uns j=0; j<GARY_SIZE(requests_line); j++)
1179 init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j]);
1181 for (uns k=0; k<GARY_SIZE(requests_line[j].sections); k++)
1183 init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k]);
1185 for (uns l=0; l<GARY_SIZE(requests_line[j].sections[k].segments); l++)
1187 init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k].segments[l]);
1192 for (uns j=0; j<GARY_SIZE(requests_area); j++)
1194 init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_area[j]);
1197 hide_segment_labels(individual);
1199 ASSERT(p == num_requests);
1203 bool shall_terminate(void)
1205 switch (conf_term_cond)
1207 case TERM_COND_PENALTY:
1208 return (population1[0]->penalty < conf_penalty_bound);
1209 case TERM_COND_STAGNATION:
1210 return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
1211 case TERM_COND_ITERATIONS:
1212 return (iteration >= conf_iteration_limit);
1214 fprintf(stderr, "Warning: No termination condition is set, terminating\n");
1223 struct individual **breed_buffer;
1224 while (i < breed_pop_size)
1226 int parent1 = randint(0, breed_rbest_size);
1227 int parent2 = randint(0, breed_rbest_size);
1228 if (dbg_breeding >= VERBOSITY_INDIVIDUAL)
1229 printf("Will breed %d and %d\n", parent1, parent2);
1231 breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
1232 population2[pop2_ind++] = breed_buffer[0];
1233 population2[pop2_ind++] = breed_buffer[1];
1241 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
1243 struct individual **buffer = malloc(2*sizeof(struct individual));
1244 struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
1245 struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
1248 GARY_INIT_ZERO(processed, GARY_SIZE(parent1->placements));
1250 for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
1252 if (! processed[parent1->placements[i].ind])
1254 if (dbg_breeding >= VERBOSITY_PLACEMENT)
1255 printf("Creating symbol closure for placement %u\n", i);
1257 struct placement **clos_symbols = get_closure(&(parent1->placements[i]));
1258 int x = randint(1, 2);
1262 if (dbg_breeding >= VERBOSITY_PLACEMENT)
1263 printf("Copying parent->child 1->1 and 2->2\n");
1264 copy_symbols(clos_symbols, parent1, child1, &processed);
1265 copy_symbols(clos_symbols, parent2, child2, &processed);
1269 if (dbg_breeding >= VERBOSITY_PLACEMENT)
1270 printf("Copying parent->child 2->1 and 1->2\n");
1271 copy_symbols(clos_symbols, parent2, child1, &processed);
1272 copy_symbols(clos_symbols, parent1, child2, &processed);
1275 GARY_FREE(clos_symbols);
1279 GARY_FREE(processed);
1281 if (conf_mutate_children)
1283 if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child1);
1284 if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child2);
1294 for (int i=0; i < mutate_pop_size; i++)
1296 if (dbg_mutation >= VERBOSITY_INDIVIDUAL)
1297 printf("Creating %d-th individual by mutation\n", i);
1298 int ind = randint(1, mutate_rbest_size);
1299 if (dbg_mutation >= VERBOSITY_INDIVIDUAL)
1300 printf("Mutating %d-th individual of original population\n", ind);
1301 copy_individual(population1[ind], population2[pop2_ind]);
1302 if (dbg_mutation >= VERBOSITY_INDIVIDUAL)
1303 printf("Individual %d in pop2 inited from individual %d in pop1\n", pop2_ind, ind);
1304 perform_mutation(population2[pop2_ind]);
1309 void perform_mutation(struct individual *individual)
1311 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1313 double x = randdouble();
1316 if (x <= acc + conf_mutate_move_bound)
1318 if (dbg_mutation >= VERBOSITY_PLACEMENT)
1319 printf("Mutation: Moving symbol in placement %u\n", i);
1320 move_symbol(&(individual->placements[i]));
1323 acc += conf_mutate_move_bound;
1325 if (x <= acc + conf_mutate_regen_bound)
1327 gen_coords(&(individual->placements[i]));
1330 acc += conf_mutate_regen_bound;
1332 if (x <= acc + conf_mutate_chvar_bound)
1334 struct placement *p = &(individual->placements[i]);
1335 switch (p->request->type)
1338 case REQUEST_SEGMENT:
1340 // Does nothing when there are 0 variants... does it mind?
1341 p->variant_used = randint(0, GARY_SIZE(p->request->variants) - 1);
1343 case REQUEST_SECTION:
1344 p->variant_used = randint(0, GARY_SIZE(((struct request_section *) p->request)->segments)-1);
1352 hide_segment_labels(individual);
1357 for (int i=0; i<elite_pop_size; i++)
1359 copy_individual(population1[i], population2[pop2_ind++]);
1363 int overlaps(struct placement *p1, struct placement *p2)
1365 if (p1->request->type != REQUEST_POINT &&
1366 p1->request->type != REQUEST_SEGMENT &&
1367 p1->request->type != REQUEST_AREA)
1370 if (p2->request->type != REQUEST_POINT &&
1371 p2->request->type != REQUEST_SEGMENT &&
1372 p2->request->type != REQUEST_AREA)
1375 if (p1->variant_used == -1 || p2->variant_used == -1)
1378 struct variant *v1, *v2;
1380 v1 = &(p1->request->variants[p1->variant_used]);
1381 v2 = &(p2->request->variants[p2->variant_used]);
1383 // FIXME: This doesn't fully respect offset which it probably should
1384 int p1x = p1->x; int p1y = p1->y;
1385 int p2x = p2->x; int p2y = p2->y;
1388 for (int y=max2(0, max2(p1y, p2y)); y<min2(page_height_int, min2(p1y+v1->height, p2y+v2->height)); y++)
1389 for (int x=max2(0, max2(p1x, p2x)); x<min2(page_width_int, min2(p1x+v1->width, p2x+v2->width)); x++)
1391 if (v1->bitmap[(y-p1y)*v1->width + (x-p1x)] &&
1392 v2->bitmap[(y-p2y)*v2->width + (x-p2x)])
1399 int get_overlap(struct placement *p)
1401 struct map_part **parts = get_map_parts(p);
1404 if (dbg_overlaps >= VERBOSITY_PLACEMENT)
1405 printf("Placement of request %d seems not to be placed\n", p->request->ind);
1409 struct placement **others;
1412 GARY_INIT_ZERO(planned, num_requests);
1413 planned[p->request->ind] = 1;
1414 GARY_INIT(others, 0);
1416 for (uns i=0; i<GARY_SIZE(parts); i++)
1418 struct map_placement *mp = parts[i]->placement->next;
1421 if (! planned[mp->placement->request->ind])
1423 struct placement **p = GARY_PUSH(others);
1425 planned[mp->placement->request->ind] = true;
1432 for (uns i=0; i<GARY_SIZE(others); i++)
1434 overlap += overlaps(p, others[i]);
1441 if (dbg_overlaps >= VERBOSITY_PLACEMENT)
1442 printf("Placement of request %d add %d to overlaps\n", p->request->ind, overlap);
1447 int individual_overlap(struct individual *individual)
1451 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1453 overlap += get_overlap(&individual->placements[i]);
1459 double get_distance(struct placement *p)
1461 if (p->variant_used < 0) return 0;
1462 struct variant *v = &p->request->variants[p->variant_used];
1464 double dx, dy, distance;
1465 switch (p->request->type)
1467 case REQUEST_POINT: ;
1468 struct request_point *rp = (struct request_point *) p->request;
1469 dx = rp->x + v->offset_x - p->x;
1470 dy = rp->y + v->offset_y - p->y;
1471 distance = sqrt(dx*dx + dy*dy);
1472 if (dbg_rank >= VERBOSITY_PLACEMENT)
1473 printf("Point placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, rp->x, rp->y);
1475 case REQUEST_AREA: ;
1476 struct request_area *ra = (struct request_area *) p->request;
1477 dx = ra->cx + v->offset_x - p->x;
1478 dy = ra->cy + v->offset_y - p->y;
1479 distance = sqrt(dx*dx + dy*dy);
1480 if (dbg_rank >= VERBOSITY_PLACEMENT)
1481 printf("Area placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
1487 if (dbg_rank >= VERBOSITY_PLACEMENT)
1488 printf("Placement %d has distance %.2f\n", p->ind, distance);
1492 double individual_distances(struct individual *individual)
1496 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1498 distances += get_distance(&individual->placements[i]);
1504 int cmp_individual(const void *a, const void *b)
1506 struct individual **ia = (struct individual **) a;
1507 struct individual **ib = (struct individual **) b;
1509 return (*ia)->penalty - (*ib)->penalty;
1512 void rank_population(void)
1516 for (int i=0; i<conf_pop_size; i++)
1518 if (dbg_rank >= VERBOSITY_INDIVIDUAL)
1519 printf("Individual %d\n", i);
1520 population1[i]->penalty = 0;
1522 penalty = individual_overlap(population1[i]);
1523 if (dbg_rank >= VERBOSITY_INDIVIDUAL)
1524 printf("Increasing penalty by %d for overlap\n", penalty);
1525 population1[i]->penalty += penalty;
1527 penalty = individual_distances(population1[i]);
1528 if (dbg_rank >= VERBOSITY_INDIVIDUAL)
1529 printf("Increasing penalty by %d for distances\n", penalty);
1530 population1[i]->penalty += penalty;
1534 struct map_part **get_map_parts(struct placement *p)
1536 if (p->variant_used < 0) return NULL;
1538 struct map_part **buffer;
1539 GARY_INIT(buffer, 0);
1541 if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1542 printf("Looking for map parts containing placement of request %d, placed at [%.2f; %.2f]\n", p->request->ind, p->x, p->y);
1545 switch (p->request->type)
1548 case REQUEST_SEGMENT:
1550 v = p->request->variants[p->variant_used];
1553 if (dbg_map_parts >= VERBOSITY_ALL)
1554 printf("Skipping unsupported request type (%d)\n", p->request->type);
1558 if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1559 printf("Bitmap is %d x %d\n", v.width, v.height);
1561 int x_min = max2(0, p->x) / conf_map_part_width;
1562 // CHECK ME: Is rounding needed?
1563 int x_max = min2(page_width_int, (p->x + v.width)) / conf_map_part_width;
1564 int y_min = max2(0, p->y) / conf_map_part_height;
1565 // CHECK ME: Is rounding needed?
1566 int y_max = min2(page_height_int, (p->y + v.height)) / conf_map_part_height;
1568 if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1569 printf("Cells between [%d; %d] and [%d; %d] generated\n", x_min, y_min, x_max, y_max);
1571 for (int y=y_min; y<=y_max; y++)
1572 for (int x=x_min; x<=x_max; x++)
1574 struct map_part **m = GARY_PUSH(buffer);
1575 if (dbg_map_parts >= VERBOSITY_ALL)
1576 printf("Asking for %d of %u\n", y * num_map_parts_row + x, GARY_SIZE(p->individual->map));
1577 *m = p->individual->map[y * num_map_parts_row + x];
1580 if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1581 printf("Returning %u map parts potentially containing the symbol\n", GARY_SIZE(buffer));
1586 void update_map_parts(struct placement *p)
1588 struct placement_link *ml = p->map_links;
1591 struct map_placement *mp = ml->mp;
1593 mp->prev->next = mp->next;
1595 mp->next->prev = mp->prev;
1598 struct placement_link *tmp = ml;
1602 p->map_links = NULL;
1604 struct map_part **parts = get_map_parts(p);
1605 if (parts == NULL) return;
1607 for (uns i=0; i<GARY_SIZE(parts); i++)
1609 struct map_placement *mp = malloc(sizeof(struct map_placement));
1612 mp->next = parts[i]->placement->next;
1613 mp->prev = parts[i]->placement;
1614 parts[i]->placement->next = mp;
1615 if (mp->next) mp->next->prev = mp;
1617 struct placement_link *ml = malloc(sizeof(struct placement_link));
1619 ml->next = p->map_links;
1626 void gen_coords(struct placement *p)
1628 switch(p->request->type)
1631 gen_coords_point(p);
1636 case REQUEST_SEGMENT:
1637 gen_coords_segment(p);
1641 printf("Not yet implemented\n");
1644 if (dbg_movement >= VERBOSITY_ALL)
1645 printf("Testing request type\n");
1646 ASSERT(p->request->type != REQUEST_INVALID);
1649 update_map_parts(p);
1652 double gen_movement(void)
1654 double m = (random() % 100000) / 10000;
1655 m = pow(m, 1.0/3) * flip(1, -1);
1656 if (dbg_movement >= VERBOSITY_ALL)
1657 printf("Movement %.2f\n", m);
1661 double gen_movement_uniform(void)
1663 return (move_max - move_min) * randdouble() * flip(1, -1);
1666 void gen_coords_point(struct placement *p)
1668 p->x = p->x + gen_movement();
1671 void gen_coords_segment(struct placement *p)
1673 struct request_segment *rs = (struct request_segment *) p->request;
1675 p->x = (a == 1 ? rs->x1 : rs->x2);
1676 p->y = (a == 1 ? rs->y1 : rs->y2);
1679 void gen_coords_area(struct placement *p)
1681 struct request_area *ra = (struct request_area *) p->request;
1683 p->x = p->x + gen_movement();
1684 p->y = p->y + gen_movement();
1686 if (dbg_movement >= VERBOSITY_PLACEMENT)
1687 printf("Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
1690 int randint(int min, int max)
1692 if (min == max) return min;
1694 return min + (r % (max - min));
1697 struct placement **get_closure(struct placement *placement)
1699 struct placement **closure;
1700 GARY_INIT(closure, 0);
1701 bool *chosen = malloc(GARY_SIZE(placement->individual->placements) * sizeof(bool));
1702 for (uns i=0; i<GARY_SIZE(placement->individual->placements); i++) { chosen[i] = 0; }
1703 chosen[placement->request->ind] = 1;
1705 struct placement **p = GARY_PUSH(closure); *p = placement;
1708 while (first < GARY_SIZE(closure))
1710 if (dbg_breeding >= VERBOSITY_ALL)
1711 printf("Iterating, first is %d of current %u\n", first, GARY_SIZE(closure));
1712 struct placement **overlapping = get_overlapping(placement);
1713 if (! overlapping) { first++; continue; }
1715 struct placement **filtered = filter(overlapping, &chosen);
1716 if (dbg_breeding >= VERBOSITY_ALL)
1717 printf("There are %u new overlapping symbols\n", GARY_SIZE(filtered));
1718 GARY_FREE(overlapping);
1719 overlapping = filtered;
1720 for (uns j=0; j<GARY_SIZE(overlapping); j++)
1722 if (! chosen[overlapping[j]->request->ind])
1724 if (overlaps(*p, overlapping[j]))
1726 p = GARY_PUSH(closure); *p = overlapping[j];
1727 if (dbg_breeding >= VERBOSITY_ALL)
1728 printf("Adding placement of request %d (in fact at [%.2f; %.2f] of size %d x %d)\n", overlapping[j]->request->ind, overlapping[j]->x, overlapping[j]->y, overlapping[j]->request->variants[overlapping[j]->variant_used].width, overlapping[j]->request->variants[overlapping[j]->variant_used].height);
1729 chosen[overlapping[j]->request->ind] = 1;
1733 GARY_FREE(overlapping);
1740 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child, bool **processed_ptr)
1742 bool *processed = *processed_ptr;
1743 if (dbg_breeding >= VERBOSITY_ALL)
1744 printf("Will copy %u symbols\n", GARY_SIZE(closure));
1746 for (uns i=0; i<GARY_SIZE(closure); i++)
1748 processed[closure[i]->ind] = 1;
1749 int ind = closure[i]->ind;
1750 child->placements[ind] = parent->placements[ind];
1751 child->placements[ind].processed = 0;
1752 child->placements[ind].map_links = NULL;
1753 update_map_parts(&child->placements[ind]);
1757 void move_symbol(struct placement *p)
1759 switch (p->request->type)
1763 move_symbol_point(p);
1765 case REQUEST_SEGMENT:
1766 move_symbol_segment(p);
1769 ASSERT(p->request->type != REQUEST_INVALID);
1773 void move_symbol_point(struct placement *p)
1775 p->x += gen_movement_uniform();
1776 p->y += gen_movement_uniform();
1779 void move_symbol_segment(struct placement *p)
1781 double m = gen_movement_uniform();
1784 p->y += m * ((struct request_segment *) p->request)->slope;
1787 void hide_segment_labels(struct individual *individual)
1789 // BEWARE: This fully depends on current genetic encoding
1791 int used = -1, num = -1;
1792 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1794 switch (individual->placements[i].request->type)
1796 case REQUEST_SECTION:
1797 used = individual->placements[i].variant_used;
1800 case REQUEST_SEGMENT:
1802 individual->placements[i].variant_used = 0;
1804 individual->placements[i].variant_used = -1;
1813 void init_placement(struct placement *p, struct individual *individual, struct request *r)
1815 p->ind = num_placements++;
1818 p->x = p->y = 0; // To prevent valgrind from complaining
1819 p->variant_used = 0;
1820 p->map_links = NULL;
1821 p->individual = individual;
1824 case REQUEST_POINT: ;
1825 struct request_point *rp = (struct request_point *) r;
1829 case REQUEST_LINE: ;
1831 case REQUEST_SECTION: ;
1832 struct request_section *rls = (struct request_section *) r;
1833 p->variant_used = randint(0, rls->num_segments);
1835 case REQUEST_SEGMENT: ;
1836 struct request_segment *rs = (struct request_segment *) r;
1840 case REQUEST_AREA: ;
1841 struct request_area *ra = (struct request_area *) r;
1844 p->variant_used = 0;
1847 ASSERT(p->request->type != REQUEST_INVALID);
1851 if (dbg_init >= VERBOSITY_PLACEMENT)
1852 printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y);
1855 void init_individual(struct individual *i)
1857 if (dbg_init >= VERBOSITY_INDIVIDUAL)
1858 printf("Initing individual\n");
1859 GARY_INIT(i->placements, num_requests);
1860 GARY_INIT(i->map, 0);
1861 for (uns j=0; j<num_map_parts; j++)
1863 struct map_part *part = GARY_PUSH(i->map);
1864 GARY_INIT(part->placement, 0);
1865 struct map_placement *mp = GARY_PUSH(part->placement);
1866 mp->placement = &dummy_placement;
1867 mp->next = mp->prev = NULL;
1869 i->penalty = 0; // FIXME
1871 if (dbg_init >= VERBOSITY_INDIVIDUAL)
1872 printf("Individual inited, has %u map parts\n", GARY_SIZE(i->map));
1875 struct placement **get_overlapping(struct placement *p)
1877 struct placement **buffer;
1878 GARY_INIT(buffer, 0);
1880 struct map_part **parts = get_map_parts(p);
1881 if (! parts) return NULL;
1883 for (uns i=0; i<GARY_SIZE(parts); i++)
1885 struct map_placement *mp = parts[i]->placement->next;
1888 if (p->variant_used >= 0)
1890 struct placement **p = GARY_PUSH(buffer);
1898 if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1899 printf("Returning %u potentially overlapping placements\n", GARY_SIZE(buffer));
1904 struct placement **filter(struct placement **list, bool **pred_ptr)
1906 bool *pred = *pred_ptr; // As GARY can't be passed directly
1907 struct placement **filtered;
1908 GARY_INIT(filtered, 0);
1910 for (uns i=0; i<GARY_SIZE(list); i++)
1912 if (pred[list[i]->request->ind])
1915 struct placement **p = GARY_PUSH(filtered);
1922 int flip(int a, int b)
1924 return (random() % 2 ? a : b);
1927 double randdouble(void)
1929 return ((double) rand() / (double) RAND_MAX);
1932 void copy_individual(struct individual *src, struct individual *dest)
1934 dest->penalty = src->penalty;
1935 GARY_INIT(dest->placements, GARY_SIZE(src->placements));
1936 for (uns i=0; i<GARY_SIZE(src->placements); i++)
1938 dest->placements[i] = src->placements[i];
1939 dest->placements[i].map_links = NULL;
1941 for (uns j=0; j<num_map_parts; j++)
1943 struct map_part *part = GARY_PUSH(dest->map);
1944 GARY_INIT(part->placement, 0);
1945 struct map_placement *mp = GARY_PUSH(part->placement);
1946 mp->placement = &dummy_placement;
1947 mp->next = mp->prev = NULL;