3 #include <ucw/mempool.h>
4 #include <ucw/eltpool.h>
10 #define HASH_NODE struct graph_node
11 #define HASH_PREFIX(x) hash_##x
12 #define HASH_KEY_ATOMIC id
13 #define HASH_WANT_FIND
15 #define HASH_WANT_CLEANUP
16 #include <ucw/hashtable.h>
22 #define BLOCK_SIZE 4096
24 //struct mempool *mpool_requests;
26 static struct request_point *requests_point;
27 static struct request_line *requests_line;
28 static struct request_area *requests_area;
30 static struct graph_edge *bfs_queue;
31 static struct longline *longlines; int num_longlines;
32 static struct buffer_line *buffer_line;
33 static struct buffer_linelabel *buffer_linelabel;
35 struct eltpool *ep_individuals;
37 struct individual **population1;
38 struct individual **population2;
40 int conf_pop_size = 50;
42 int conf_penalty_bound = 0;
43 int conf_stagnation_bound = 0;
44 int conf_iteration_limit = 4;
46 int conf_term_cond = TERM_COND_ITERATIONS;
48 int conf_breed_rbest_perc = 80;
49 int conf_breed_pop_size_perc = 20;
50 int conf_breed_perc = 50; // Percentage of new pop created by breeding
52 bool conf_mutate_children = 1;
53 int conf_mutate_children_prob = 0.3;
55 int conf_mutate_rbest_perc = 60;
56 int conf_mutate_pop_size_perc = 20;
58 int conf_mutate_move_bound = 0.2;
59 int conf_mutate_regen_bound = 0.1;
60 int conf_mutate_chvar_bound = 0.1;
62 int conf_elite_perc = 5;
64 int old_best = 0; // FIXME: Shall be int max
68 int conf_part_size = 50;
75 void labeller_init(void)
77 // mpool_requests = mp_new(BLOCK_SIZE);
78 GARY_INIT(requests_point, 0);
79 GARY_INIT(requests_line, 0);
80 GARY_INIT(requests_area, 0);
81 GARY_INIT(buffer_line, 0);
82 GARY_INIT(buffer_linelabel, 0);
83 ep_individuals = ep_new(sizeof(struct individual), 1);
86 void make_bitmap_icon(struct point_variant *v, struct sym_icon *si)
88 v->width = si->sir.icon->width;
89 v->height = si->sir.icon->height;
90 v->bitmap = malloc((int) ceil(v->width * v->height * sizeof(bool)));
91 for (int i=0; i<v->width*v->height; i++) v->bitmap[i] = 1;
94 void make_bitmap_point(struct point_variant *v, struct sym_point *sp)
96 v->width = v->height = sp->size;
97 v->bitmap = malloc(sp->size*sp->size * sizeof(bool));
98 // FIXME: Okay, memset would be much nicer here
99 for (int i=0; i<sp->size*sp->size; i++) v->bitmap[i] = 1;
102 void make_bitmap_label(struct point_variant *v UNUSED, struct sym_text *text UNUSED)
106 void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex)
109 What does correct check look like?
110 if (object->type != OSM_TYPE_NODE)
117 struct request_point *r = GARY_PUSH(requests_point);
119 r->request.type = REQUEST_POINT;
120 r->request.ind = num_requests++;
126 struct osm_node *n = (struct osm_node *) object;
134 GARY_INIT(r->variants, 0);
136 struct point_variant *v = GARY_PUSH(r->variants);
140 case SYMBOLIZER_ICON:
141 make_bitmap_icon(v, (struct sym_icon *) sym);
143 case SYMBOLIZER_POINT:
144 make_bitmap_point(v, (struct sym_point *) sym);
153 void labeller_add_line(struct symbol *sym, z_index_t zindex)
155 struct buffer_line *b = GARY_PUSH(buffer_line);
156 b->line = (struct sym_line *) sym;
158 sym_plan(sym, zindex);
161 void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
163 struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
164 ll->way = (struct osm_way *) o;
165 ll->text = (struct sym_text *) sym;
169 void labeller_add_arealabel(struct symbol *sym UNUSED, struct osm_object *o, z_index_t zindex)
171 struct request_area *r = GARY_PUSH(requests_area);
173 r->request.type = REQUEST_AREALABEL;
174 r->request.ind = num_requests++;
176 r->o = (struct osm_multipolygon *) o;
178 r->sym = (struct sym_text *) sym;
180 GARY_INIT(r->text_variant, 0);
181 struct point_variant *v = GARY_PUSH(r->text_variant);
182 make_bitmap_label(v, r->sym);
185 void make_graph(void)
188 struct mempool *mp_edges = mp_new(BLOCK_SIZE);
190 printf("Extracting nodes, will iterate over %lld ways\n", GARY_SIZE(buffer_line));
191 for (uns i=0; i<GARY_SIZE(buffer_line); i++)
193 struct osm_way *way = (struct osm_way *) buffer_line[i].line->s.o;
194 struct graph_node *g_prev = NULL;
195 struct osm_node *o_prev = NULL;
197 CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
199 // FIXME: Shall osm_object's type be checked here?
200 struct osm_node *o_node = (struct osm_node *) ref->o;
202 struct graph_node *g_node = hash_find(ref->o->id);
205 g_node = hash_new(ref->o->id);
206 GARY_INIT(g_node->edges, 0);
217 struct graph_edge *e = mp_alloc(mp_edges, sizeof(struct graph_edge));
218 e->id = buffer_line[i].line->s.o->id;
219 e->color = buffer_line[i].line->color;
220 e->length = hypot(abs(o_prev->x - o_node->x), abs(o_prev->y - o_node->y));
226 e->longline = (uns) -1;
228 e->sym = buffer_line[i].line;
230 struct graph_edge **edge = GARY_PUSH(g_prev->edges);
232 edge = GARY_PUSH(g_node->edges);
238 void label_graph(void)
240 for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
242 CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
244 struct graph_node *n = hash_find(ref->o->id);
247 // FIXME: What shall be done?
251 for (uns j=0; j<GARY_SIZE(n->edges); j++)
253 if (n->edges[j]->id == buffer_linelabel[i].way->o.id)
255 n->edges[j]->text = buffer_linelabel[i].text;
256 n->edges[j]->zindex = buffer_linelabel[i].zindex;
264 void join_edge(struct graph_edge *e, int dir)
266 struct graph_node *other_node = NULL;
278 struct graph_edge *candidate = NULL;
279 for (uns i=0; i<GARY_SIZE(other_node->edges); i++)
281 struct graph_edge *other = other_node->edges[i];
282 if (! other->visited)
284 struct graph_edge **new = GARY_PUSH(bfs_queue);
285 *new = other_node->edges[i];
288 if ((!other->visited) && (e->text) && (other->text) && (e->text->text == other->text->text))
290 if (e->color == other_node->edges[i]->color)
292 if ((!candidate) || (candidate->length < other->length))
299 // Beware: Name conflict here
306 candidate->longline = e->longline;
309 if (candidate->n2 != e->n1)
311 candidate->n1 = candidate->n2;
312 candidate->n2 = e->n1;
317 longlines[e->longline].first = candidate;
321 if (candidate->n1 != e->n2)
323 candidate->n2 = candidate->n1;
324 candidate->n1 = e->n2;
334 GARY_INIT(bfs_queue, 0);
335 GARY_INIT(longlines, 0);
337 HASH_FOR_ALL(hash, node)
339 for (uns i=0; i<GARY_SIZE(node->edges); i++)
341 struct graph_edge *e = node->edges[i];
343 // printf("Examining edge from [%.2f; %.2f] to [%.2f; %.2f]\n",
344 // e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y);
346 // if (e->visited) HASH_CONTINUE; // FIXME: Is is correct?
347 if (e->visited) continue;
348 // printf("Continuing\n");
349 if (e->longline == (uns) -1)
351 GARY_PUSH(longlines);
352 e->longline = num_longlines++;
353 longlines[e->longline].first = e;
355 // printf("Longline is %u\n", e->longline);
371 GARY_FREE(bfs_queue);
374 void make_segments(void)
376 for (uns i=0; i<GARY_SIZE(longlines); i++)
378 if (! longlines[i].first->text) continue;
379 // printf("Survived! %s\n", osm_val_decode(longlines[i].first->text->text));
380 printf("New longline\n");
381 struct request_line *request = GARY_PUSH(requests_line);
382 request->request.ind = -1;
383 request->request.type = REQUEST_LINELABEL;
385 GARY_INIT(request->segments, 0);
386 request->num_segments = 0;
388 // ->num_variants FIXME
391 struct graph_edge *e = longlines[i].first;
393 if (! e) printf("Oops\n");
397 if (! e->text) break;
398 struct request_segment *r = GARY_PUSH(request->segments);
399 request->num_segments++;
401 r->request.ind = num_requests++;
402 r->request.type = REQUEST_SEGMENT;
404 struct osm_node *n = e->n1->o;
410 r->k = abs(r->x2 - r->x1) / (abs(r->y2 - r->y1) + 0.001); // FIXME: Hack to prevent floating point exception when y2 = y1
412 printf("Segment [%.2f; %.2f] -- [%.2f; %.2f]\n", r->x1, r->y1, r->x2, r->y2);
415 r->zindex = e->zindex;
416 r->text = malloc(sizeof(struct sym_text));
417 *(r->text) = *(e->text);
421 r->variant = malloc(sizeof(struct point_variant)); // FIXME
422 make_bitmap_label(r->variant, e->text);
429 void labeller_label(void)
436 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));
438 GARY_INIT(population1, conf_pop_size);
439 GARY_INIT(population2, conf_pop_size);
442 printf("Dealing with %d requests\n", num_requests);
444 while (! shall_terminate())
448 struct individual **swp = population1;
449 population1 = population2;
454 for (uns i=0; i<GARY_SIZE(population1[0]->placements); i++)
456 switch (population1[0]->placements[i].request->type)
458 case REQUEST_POINT: ;
459 struct request_point *rp = (struct request_point *) population1[0]->placements[i].request;
460 switch (rp->sym->type)
462 case SYMBOLIZER_POINT: ;
463 struct sym_point *sp = (struct sym_point *) rp->sym;
466 sym_plan((struct symbol *) sp, rp->zindex);
468 case SYMBOLIZER_ICON: ;
469 struct sym_icon *si = (struct sym_icon *) rp->sym;
470 si->sir.x = population1[0]->placements[i].x;
471 si->sir.y = population1[0]->placements[i].y;
472 sym_plan((struct symbol *) si, rp->zindex);
478 case REQUEST_AREALABEL: ;
479 struct request_area *ra = (struct request_area *) population1[0]->placements[i].request;
480 sym_plan((struct symbol *) ra->sym, ra->zindex);
483 case REQUEST_LINELABEL: ;
484 struct request_line *rl = (struct request_line *) population1[0]->placements[i].request;
485 for (uns j=0; j<GARY_SIZE(rl->segments); j++)
487 printf("Planning text %s to [%.2f; %.2f]\n", osm_val_decode(rl->segments[j].text->text), rl->segments[j].text->x, rl->segments[j].text->y);
488 rl->segments[j].text->next_duplicate = NULL;
489 rl->segments[j].text->next_in_tile = NULL;
490 sym_plan((struct symbol *) rl->segments[j].text, rl->segments[j].zindex); // FIXME: z-index
498 while (! shall_terminate())
506 // sort population by fitness
508 struct individual **swp = population1;
509 population1 = population2;
510 printf("Swapped populations\n");
512 // GARY_RESIZE(population2, 0) -- is it needed?
517 void make_population(void)
519 for (int i=0; i<conf_pop_size; i++)
521 struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
522 population1[i] = individual;
525 for (uns j=0; j<GARY_SIZE(requests_point); j++)
527 init_placement(&(individual->placements[p++]), (struct request *) &requests_point[j]);
529 for (uns j=0; j<GARY_SIZE(requests_line); j++)
531 init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j]);
532 for (uns k=0; k<GARY_SIZE(requests_line[j].segments); k++)
534 init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j].segments[k]);
537 for (uns j=0; j<GARY_SIZE(requests_area); j++)
539 init_placement(&(individual->placements[p++]), (struct request *) &requests_area[j]);
542 ASSERT(p == num_requests);
546 bool shall_terminate(void)
548 switch (conf_term_cond)
550 case TERM_COND_PENALTY:
551 return (population1[0]->penalty < conf_penalty_bound);
552 case TERM_COND_STAGNATION:
553 return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
554 case TERM_COND_ITERATIONS:
555 return (iteration >= conf_iteration_limit);
557 // FIXME: Warn the user that no condition is set
566 printf("%.2f\n", ((double) conf_breed_pop_size_perc/100));
567 int conf_breed_pop_size = ((double) conf_breed_pop_size_perc/100) * conf_pop_size;
568 struct individual **breed_buffer;
569 while (i < conf_breed_pop_size)
571 printf("%d < %d, breeding\n", i, conf_breed_pop_size);
572 int parent1 = randint(1, conf_breed_pop_size);
573 int parent2 = randint(1, conf_breed_pop_size);
574 printf("Will breed %d and %d, chosen of %d best of %d population (intended to be %d)\n", parent1, parent2, conf_breed_pop_size, GARY_SIZE(population1), conf_pop_size);
575 breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
576 population2[pop2_ind++] = breed_buffer[0];
577 population2[pop2_ind++] = breed_buffer[1];
582 acc += conf_breed_rbest_perc;
584 return; // FIXME: DEBUG HACK
586 int remaining = (1 - acc) * (conf_pop_size * conf_breed_perc);
587 int step = remaining / conf_pop_size;
588 for (; i<conf_pop_size; i += 2)
590 printf("Asking for %d and %d of %d\n", i*step, i*(step+1), conf_pop_size);
591 breed_buffer = perform_crossover(population1[i*step], population1[i*step+1]);
592 population2[pop2_ind++] = breed_buffer[0];
593 population2[pop2_ind++] = breed_buffer[1];
596 // FIXME: Could there be one missing individual?
599 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
601 struct individual **buffer = malloc(2*sizeof(struct individual));
602 struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
603 struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
605 printf("Performing crossover\n");
607 for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
609 printf("%dth placement out of %d\n", i, num_requests);
610 if (! parent1->placements[i].processed)
612 struct placement **clos_symbols = get_closure(&(parent1->placements[i]), parent1, parent2);
613 int x = randint(1, 2);
617 copy_symbols(clos_symbols, parent1, child1);
618 copy_symbols(clos_symbols, parent2, child2);
622 copy_symbols(clos_symbols, parent2, child1);
623 copy_symbols(clos_symbols, parent1, child2);
625 printf("Symbols copied; %lld\n", GARY_SIZE(clos_symbols));
626 GARY_FREE(clos_symbols);
629 if (conf_mutate_children)
631 if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child1);
632 if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child2);
644 int conf_mutate_pop_size = conf_mutate_pop_size_perc * conf_pop_size;
645 while (i < conf_mutate_rbest_perc * conf_pop_size)
647 int ind = randint(1, conf_mutate_pop_size);
648 copy_individual(population2[pop2_ind], population1[ind]);
649 perform_mutation(population2[pop2_ind]);
654 void perform_mutation(struct individual *individual)
656 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
658 int x = randint(1, 1000);
661 if (x <= acc + conf_mutate_move_bound)
663 move_symbol(&(individual->placements[i]));
666 acc += conf_mutate_move_bound;
668 if (x <= acc + conf_mutate_regen_bound)
670 gen_coords(&(individual->placements[i]));
673 acc += conf_mutate_regen_bound;
675 if (x <= acc + conf_mutate_chvar_bound)
677 if (0) // if num_variants > 1
679 // FIXME: assign new variant
687 for (int i=0; i<conf_elite_perc * conf_pop_size; i++)
689 population2[pop2_ind++] = population1[0];
693 void rank_population(void)
698 void gen_coords(struct placement *p)
700 switch(p->request->type)
707 void gen_coords_point(struct placement *p UNUSED)
712 struct map_part **get_parts(struct placement *symbol, struct individual *individual)
714 struct map_part **buffer;
715 GARY_INIT(buffer, 0);
716 int x_min = symbol->x / conf_part_size;
717 int x_max = (symbol->x /*+ symbol->bitmap->width*/ + conf_part_size - 1) / conf_part_size;
718 int y_min = symbol->y / conf_part_size;
719 int y_max = (symbol->y /*+ symbol->bitmap->height*/ + conf_part_size - 1) / conf_part_size;
721 for (int x=x_min; x < x_max; x++)
722 for (int y=y_min; y < y_max; y++)
724 struct map_part *m = GARY_PUSH(buffer);
725 *m = individual->map[x][y];
731 int randint(int min, int max)
734 //printf("Returning %d + (%d %% (%d - %d)) = %d + %d %% %d = %d + %d = %d\n", min, r, max, min, min, r, max-min, min, r%(max-min), min+(r%(max-min)));
735 return min + (r % (max - min));
736 return (r * (max - min));
739 struct placement **get_closure(struct placement *placement, struct individual *parent1, struct individual *parent2 UNUSED)
741 printf("Getting closure\n");
742 struct placement **closure;
743 GARY_INIT(closure, 0);
744 bool *chosen = malloc(GARY_SIZE(parent1->placements) * sizeof(bool));
745 chosen[placement->request->ind] = 1;
747 struct placement **p = GARY_PUSH(closure); *p = placement;
750 while (first < GARY_SIZE(closure))
752 printf("Iterating, first is %d\n", first);
753 struct placement **overlapping = get_overlapping(placement);
754 filter(overlapping, chosen);
755 for (uns j=0; j<GARY_SIZE(overlapping); j++)
757 p = GARY_PUSH(closure); *p = overlapping[j];
758 chosen[overlapping[j]->request->ind] = 1;
760 GARY_FREE(overlapping);
767 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child)
769 //printf("%d\n", child->penalty);
770 //printf("Closure size: %lld\n", GARY_SIZE(closure));
771 for (uns i=0; i<GARY_SIZE(closure); i++)
773 int ind = closure[i]->request->ind;
774 child->placements[ind] = parent->placements[ind];
775 child->placements[ind].processed = 0;
779 void move_symbol(struct placement *p)
781 switch (p->request->type)
784 move_symbol_point(p);
788 void move_symbol_point(struct placement *p)
790 p->x += (double) (move_min + randdouble()) * flip(1, -1);
791 p->y += (double) (move_min + randdouble()) * flip(1, -1);
794 void init_placement(struct placement *p, struct request *r)
801 void init_individual(struct individual *i)
803 //printf("Initing individual\n");
804 GARY_INIT(i->placements, num_requests);
805 GARY_INIT(i->map, 0);
806 i->penalty = 0; // FIXME
809 struct placement **get_overlapping(struct placement *p UNUSED)
811 struct placement **buffer;
812 GARY_INIT(buffer, 0);
816 void filter(struct placement **list UNUSED, bool *pred UNUSED)
821 int flip(int a, int b)
823 return (random() % 2 ? a : b);
826 double randdouble(void)
828 // FIXME: How the hell shall double in range <0, 1> be generated? O:)
835 GARY_FREE(requests_point);
836 GARY_FREE(requests_line);
837 GARY_FREE(requests_area);
840 void copy_individual(struct individual *src, struct individual *dest)
842 src->penalty = dest->penalty;
843 GARY_INIT(dest->placements, GARY_SIZE(src->placements));
844 for (uns i=0; i<GARY_SIZE(src->placements); i++)
846 dest->placements[i] = src->placements[i];