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;
45 int conf_pop_size = 50;
47 int conf_penalty_bound = 0;
48 int conf_stagnation_bound = 0;
49 int conf_iteration_limit = 4;
51 int conf_term_cond = TERM_COND_ITERATIONS;
53 int conf_breed_rbest_perc = 80;
54 int conf_breed_pop_size_perc = 20;
55 int conf_breed_perc = 50; // Percentage of new pop created by breeding
57 bool conf_mutate_children = 1;
58 int conf_mutate_children_prob = 0.3;
60 int conf_mutate_rbest_perc = 60;
61 int conf_mutate_pop_size_perc = 20;
63 int conf_mutate_move_bound = 0.2;
64 int conf_mutate_regen_bound = 0.1;
65 int conf_mutate_chvar_bound = 0.1;
67 int conf_elite_perc = 5;
69 int old_best = 0; // FIXME: Shall be int max
73 int conf_part_size = 50;
80 void dump_graph(void);
82 void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, int dir);
83 void bfs_wrapper(void);
85 void dump_longlines(void);
86 void dump_linelabel_requests(void);
87 void dump_individual(struct individual *individual);
88 void print_label(struct symbol *sym);
90 void print_label(struct symbol *sym)
94 case SYMBOLIZER_TEXT: ;
95 struct sym_text *st = (struct sym_text *) sym;
96 printf("%s\n", osm_val_decode(st->text));
103 void labeller_init(void)
105 GARY_INIT(requests_point, 0);
106 GARY_INIT(requests_line, 0);
107 GARY_INIT(requests_area, 0);
108 GARY_INIT(buffer_line, 0);
109 GARY_INIT(buffer_linelabel, 0);
110 ep_individuals = ep_new(sizeof(struct individual), 1);
113 void make_bitmap_icon(struct point_variant *v, struct sym_icon *si)
115 v->width = si->sir.icon->width;
116 v->height = si->sir.icon->height;
117 v->bitmap = malloc((int) ceil(v->width * v->height * sizeof(bool)));
118 for (int i=0; i<v->width*v->height; i++) v->bitmap[i] = 1;
121 void make_bitmap_point(struct point_variant *v, struct sym_point *sp)
123 v->width = v->height = sp->size;
124 v->bitmap = malloc(sp->size*sp->size * sizeof(bool));
125 // FIXME: Okay, memset would be much nicer here
126 for (int i=0; i<sp->size*sp->size; i++) v->bitmap[i] = 1;
129 void make_bitmap_label(struct point_variant *v UNUSED, struct sym_text *text UNUSED)
133 void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex)
135 printf("Adding point\n");
136 if (object->type != OSM_TYPE_NODE)
138 printf("Warning: Point label requested on non-point object\n");
142 struct request_point *r = GARY_PUSH(requests_point);
144 r->request.type = REQUEST_POINT;
145 r->request.ind = num_requests++;
154 GARY_INIT(r->variants, 0);
156 struct point_variant *v = GARY_PUSH(r->variants);
158 struct osm_node *n = (struct osm_node *) object; // FIXME: Compiler warning
163 case SYMBOLIZER_ICON:
164 make_bitmap_icon(v, (struct sym_icon *) sym);
165 r->x = ((struct sym_icon *)sym)->sir.x;
166 r->y = ((struct sym_icon *)sym)->sir.y;
168 case SYMBOLIZER_POINT:
169 make_bitmap_point(v, (struct sym_point *) sym);
171 case SYMBOLIZER_TEXT: ;
172 struct sym_text *st = (struct sym_text *) sym;
173 struct osm_node *n = (struct osm_node *) object;
174 make_bitmap_label(v, st);
180 printf("Inited point to [%.2f; %.2f]\n", r->x, r->y);
183 void labeller_add_line(struct symbol *sym, z_index_t zindex)
185 printf("Adding line\n");
186 struct buffer_line *b = GARY_PUSH(buffer_line);
187 b->line = (struct sym_line *) sym;
189 sym_plan(sym, zindex);
192 void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
194 if (o->type != OSM_TYPE_WAY)
200 printf("[LAB] Labelling way %ju\n", o->id);
201 struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
202 ll->way = (struct osm_way *) o;
207 void labeller_add_arealabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
209 printf("Adding area\n");
210 struct request_area *r = GARY_PUSH(requests_area);
212 r->request.type = REQUEST_AREA;
213 r->request.ind = num_requests++;
215 r->o = (struct osm_multipolygon *) o;
219 osm_obj_center(o, &(r->cx), &(r->cy));
221 GARY_INIT(r->variants, 0);
222 struct point_variant *v = GARY_PUSH(r->variants);
225 case SYMBOLIZER_ICON:
226 make_bitmap_icon(v, (struct sym_icon *) sym);
228 case SYMBOLIZER_TEXT:
229 make_bitmap_label(v, (struct sym_text *) sym);
236 void make_graph(void)
239 struct mempool *mp_edges = mp_new(BLOCK_SIZE);
241 printf("Extracting nodes, will iterate over %lld ways\n", GARY_SIZE(buffer_line));
242 for (uns i=0; i<GARY_SIZE(buffer_line); i++)
244 struct osm_way *way = (struct osm_way *) buffer_line[i].line->s.o;
245 struct graph_node *g_prev = NULL;
246 struct osm_node *o_prev = NULL;
248 CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
250 // FIXME: Shall osm_object's type be checked here?
251 struct osm_node *o_node = (struct osm_node *) ref->o;
253 struct graph_node *g_node = hash_find(ref->o->id);
256 g_node = hash_new(ref->o->id);
257 GARY_INIT(g_node->edges, 0);
259 g_node->id = ref->o->id;
260 g_node->num = num_nodes++;
270 struct graph_edge *e = mp_alloc(mp_edges, sizeof(struct graph_edge)); num_edges_dbg++;
271 e->num = num_edges++;
272 e->id = buffer_line[i].line->s.o->id;
273 e->color = buffer_line[i].line->color;
274 e->length = hypot(abs(o_prev->x - o_node->x), abs(o_prev->y - o_node->y));
280 e->longline = (uns) -1;
281 e->line = buffer_line[i].line;
285 struct graph_edge **edge = GARY_PUSH(g_prev->edges);
287 edge = GARY_PUSH(g_node->edges);
296 void dump_graph(void)
298 HASH_FOR_ALL(hash, node)
300 printf("* Node: (%d) #%ju [%.2f; %.2f]\n", node->num, node->id, node->o->x, node->o->y);
301 for (uns i=0; i<GARY_SIZE(node->edges); i++)
303 struct graph_edge *e = node->edges[i];
304 printf("\t edge (%d) #%ju to ", e->num, e->id);
305 if (node->edges[i]->n1->id == node->id)
306 printf("(%d) #%ju [%.2f; %.2f]\n", e->n2->num, e->n2->id, e->n2->o->x, e->n2->o->y);
307 else if (node->edges[i]->n2->id == node->id)
308 printf("(%d) #%ju [%.2f; %.2f]\n", e->n1->num, e->n1->id, e->n1->o->x, e->n1->o->y);
310 printf("BEWARE! BEWARE! BEWARE!\n");
313 if ((node->edges[i]->label)) printf("Labelled\n");
314 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));
315 printf(" colored %d;", node->edges[i]->color);
316 printf(" length %.2f", node->edges[i]->length);
323 void label_graph(void)
325 printf("There are %u line labels requested\n", GARY_SIZE(buffer_linelabel));
326 for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
328 if (buffer_linelabel[i].label->type == SYMBOLIZER_TEXT)
329 printf("Labelling nodes of way %s\n", osm_val_decode(((struct sym_text *) buffer_linelabel[i].label)->text));
330 CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
332 printf("Looking for node %ju\n", ref->o->id);
333 struct graph_node *n = hash_find(ref->o->id);
336 // FIXME: What shall be done?
340 printf("Searching among %u edges\n", GARY_SIZE(n->edges));
341 for (uns j=0; j<GARY_SIZE(n->edges); j++)
343 if (n->edges[j]->id == buffer_linelabel[i].way->o.id)
345 printf("Labelling node %ju\n", n->id);
346 n->edges[j]->label = buffer_linelabel[i].label;
347 n->edges[j]->zindex = buffer_linelabel[i].zindex;
358 * void join_edge(struct graph_edge *e, int dir)
360 * struct graph_node *other_node = NULL;
364 * other_node = e->n2;
367 * other_node = e->n1;
372 * struct graph_edge *candidate = NULL;
373 * for (uns i=0; i<GARY_SIZE(other_node->edges); i++)
375 * struct graph_edge *other = other_node->edges[i];
376 * if (! other->visited)
378 * struct graph_edge **new = GARY_PUSH(bfs_queue);
379 * *new = other_node->edges[i];
382 * if ((!other->visited) && (e->text) && (other->text) && (e->text->text == other->text->text))
384 * if (e->color == other_node->edges[i]->color)
386 * if ((!candidate) || (candidate->length < other->length))
393 * // Beware: Name conflict here
400 * candidate->longline = e->longline;
403 * if (candidate->n2 != e->n1)
405 * candidate->n1 = candidate->n2;
406 * candidate->n2 = e->n1;
408 * e->prev = candidate;
409 * candidate->next = e;
411 * longlines[e->longline].first = candidate;
415 * if (candidate->n1 != e->n2)
417 * candidate->n2 = candidate->n1;
418 * candidate->n1 = e->n2;
420 * e->next = candidate;
421 * candidate->prev = e;
430 * GARY_INIT(bfs_queue, 0);
431 * GARY_INIT(longlines, 0);
433 * printf("Making longlines from %u causal lines, using %d graph edges\n", GARY_SIZE(buffer_line), num_edges_dbg);
435 * HASH_FOR_ALL(hash, node)
437 * for (uns i=0; i<GARY_SIZE(node->edges); i++)
439 * struct graph_edge *e = node->edges[i];
441 * // printf("Examining edge from [%.2f; %.2f] to [%.2f; %.2f]\n",
442 * // e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y);
444 * // if (e->visited) HASH_CONTINUE; // FIXME: Is is correct?
445 * if (e->visited) continue;
446 * // printf("Continuing\n");
447 * if (e->longline == (uns) -1)
449 * GARY_PUSH(longlines);
450 * e->longline = num_longlines++;
451 * longlines[e->longline].first = e;
453 * // printf("Longline is %u\n", e->longline);
469 * GARY_FREE(bfs_queue);
473 void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, int dir)
476 struct graph_edge *candidate = NULL;
478 if ((e->num > 31) && (e->num < 48)) printf("Searching for neighbours of %d, in longline %u, BFS dir is %d, edge's dir is %d\n", e->num, e->longline, dir, e->dir);
481 for (uns i=0; i<GARY_SIZE(node->edges); i++)
483 struct graph_edge *other = node->edges[i];
484 printf("Touching %d\n", other->num);
485 if (other->num == 44) printf("Longline of 44 is %u\n", other->longline);
486 if ((other->longline != (uns) -1) && (other->longline != e->longline)) continue;
488 if (! other->visited) {
489 struct graph_edge **e_ptr = GARY_PUSH(bfs_queue);
494 if (((other->n1->id == node->id) && (other->n2->id == anode->id)) ||
495 ((other->n2->id == node->id) && (other->n1->id == anode->id)))
498 if (((other->n1->id == node->id) || (other->n2->id == node->id)) &&
499 (e->label) && (other->label) &&
500 (e->label->type == SYMBOLIZER_TEXT) && (other->label->type == SYMBOLIZER_TEXT) &&
501 (((struct sym_text *) e->label)->text == ((struct sym_text *) other->label)->text))
502 // (e->text) && (other->text) && (e->text->text == other->text->text))
504 if (! candidate || (other->length > candidate->length))
511 struct graph_edge *other = candidate;
513 other->longline = e->longline;
515 other->anode = (other->n1->id == node->id ? other->n2 : other->n1);
516 other->bnode = (other->n1->id == node->id ? other->n1 : other->n2);
522 longlines[other->longline].first = other;
537 for (uns i=0; i<GARY_SIZE(bfs_queue); i++)
539 struct graph_edge *cur = bfs_queue[i];
540 printf("Exploring new edge, %d\n", cur->num);
541 //ASSERT(! cur->visited);
544 if (cur->longline == (uns) -1)
546 GARY_PUSH(longlines);
547 cur->longline = num_longlines++;
548 longlines[cur->longline].first = cur;
553 bfs_edge(cur, cur->n1, cur->n2, 1);
554 bfs_edge(cur, cur->n2, cur->n1, 2);
558 bfs_edge(cur, cur->anode, cur->bnode, cur->dir);
563 void bfs_wrapper(void)
565 GARY_INIT(bfs_queue, 0);
566 GARY_INIT(longlines, 0);
568 HASH_FOR_ALL(hash, node)
570 for (uns i=0; i<GARY_SIZE(node->edges); i++)
572 if (! node->edges[i]->visited)
574 printf("Running new BFS\n");
575 GARY_RESIZE(bfs_queue, 0);
576 struct graph_edge **e = GARY_PUSH(bfs_queue);
580 printf("Joined %d edges\n", dbg_num_hits); dbg_num_hits = 0;
581 printf("Planned %u edges\n", GARY_SIZE(bfs_queue));
587 GARY_FREE(bfs_queue);
593 * printf("Starting outer BFS\n");
594 * printf("There are %u buffered lines and %d eges\n", GARY_SIZE(buffer_line), num_edges_dbg);
596 * GARY_INIT(bfs_queue, 0);
597 * GARY_INIT(longlines, 0);
599 * int dbg_bfs_continues = 0;
601 * HASH_FOR_ALL(hash, node)
603 * // FIXME: Skip if visited node
605 * for (uns i=0; i<GARY_SIZE(node->edges); i++)
607 * struct graph_edge *e = node->edges[i];
609 * if (e->visited) continue;
612 * for (uns i1=0; i1<GARY_SIZE(e->n1->edges); i1++)
614 * struct graph_edge *other = e->n1->edges[i1];
615 * if (other->visited) { dbg_bfs_continues++; continue; }
617 * if (((other->n1->id == e->n1->id) || (other->n2->id == e->n1->id)) &&
618 * (e->text) && (other->text) && (e->text->text == other->text->text))
620 * // printf("Hit\n");
621 * other->visited = 1;
624 * for (uns i2=0; i2<GARY_SIZE(e->n2->edges); i2++)
626 * struct graph_edge *other = e->n2->edges[i2];
627 * if (other->visited) {dbg_bfs_continues++; continue; }
629 * if (((other->n1->id == e->n2->id) || (other->n2->id == e->n2->id)) &&
630 * (e->text) && (other->text) && (e->text->text == other->text->text))
632 * // printf("Hit\n");
633 * other->visited = 1;
640 * printf("Total: %d hits, %d visited edges skipped\n", dbg_num_hits, dbg_bfs_continues);
642 * GARY_FREE(bfs_queue);
646 void dump_longlines(void)
648 for (uns i=0; i<GARY_SIZE(longlines); i++)
650 struct graph_edge *e = longlines[i].first;
652 printf("> Longline %u;", i);
653 if (longlines[i].first->label && longlines[i].first->label->type == SYMBOLIZER_TEXT) printf(" labelled %s", osm_val_decode(((struct sym_text *) longlines[i].first->label)->text));
657 printf("\t#%ju (%d)", e->id, e->num);
661 printf("[%.2f; %.2f] -- #%ju [%.2f; %.2f] (dir %d)\n", e->anode->o->x, e->anode->o->y, e->bnode->o->o.id, e->bnode->o->x, e->bnode->o->y, e->dir);
664 printf("[%.2f; %.2f] -- #%ju [%.2f; %.2f] (dir %d)\n", e->bnode->o->x, e->bnode->o->y, e->anode->o->o.id, e->anode->o->x, e->anode->o->y, e->dir);
667 printf("[%.2f; %.2f] -- #%ju [%.2f; %.2f] (dir %d)\n", e->n1->o->x, e->n1->o->y, e->n2->o->o.id, e->n2->o->x, e->n2->o->y, e->dir);
670 printf("%d\n", e->dir);
678 void make_segments(void)
680 printf("Analysing %u longlines\n", GARY_SIZE(longlines));
681 for (uns i=0; i<GARY_SIZE(longlines); i++)
683 if (! longlines[i].first->label) continue;
684 // printf("Survived! %s\n", osm_val_decode(longlines[i].first->text->text));
685 printf("New longline\n");
687 if (longlines[i].first->label->type != SYMBOLIZER_TEXT)
692 struct request_line *request = GARY_PUSH(requests_line);
693 request->request.ind = -1;
694 request->request.type = REQUEST_LINE;
696 GARY_INIT(request->segments, 0);
697 request->num_segments = 0;
699 // ->num_variants FIXME
702 struct graph_edge *e = longlines[i].first;
704 if (! e) printf("Oops\n");
708 if (! e->label) break;
709 struct request_segment *r = GARY_PUSH(request->segments);
710 request->num_segments++;
712 r->request.ind = num_requests++;
713 r->request.type = REQUEST_SEGMENT;
715 struct osm_node *n = e->n1->o;
721 r->k = abs(r->x2 - r->x1) / (abs(r->y2 - r->y1) + 0.001); // FIXME: Hack to prevent floating point exception when y2 = y1
723 printf("Segment [%.2f; %.2f] -- [%.2f; %.2f]\n", r->x1, r->y1, r->x2, r->y2);
726 r->zindex = e->zindex;
727 r->variant = malloc(sizeof(struct point_variant)); // FIXME
728 switch (e->label->type)
730 case SYMBOLIZER_TEXT: ;
731 struct sym_text *st = malloc(sizeof(struct sym_text));
732 ((struct symbol *) st)->o = e->label->o;
733 ((struct symbol *) st)->type = SYMBOLIZER_TEXT;
736 st->text = ((struct sym_text *) e->label)->text;
737 st->text_color = ((struct sym_text *) e->label)->text_color;
738 st->font = ((struct sym_text *) e->label)->font;
739 st->opacity = ((struct sym_text *) e->label)->opacity;
740 st->halo_color = ((struct sym_text *) e->label)->halo_color;
741 st->halo_radius = ((struct sym_text *) e->label)->halo_radius;
742 st->halo_opacity = ((struct sym_text *) e->label)->halo_opacity;
743 st->tw = ((struct sym_text *) e->label)->tw;
744 st->th = ((struct sym_text *) e->label)->th;
745 st->td = ((struct sym_text *) e->label)->td;
746 r->label = (struct symbol *) st;
747 // FIXME: This shall be done in more elegant way
748 make_bitmap_label(r->variant, (struct sym_text *) e->label);
752 printf("Got here?\n");
761 void dump_linelabel_requests(void)
763 for (uns i=0; i<GARY_SIZE(requests_line); i++)
765 print_label(requests_line[i].segments[0].label);
769 void dump_individual(struct individual *individual)
771 printf("(There are %d requests)\n", num_requests);
772 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
774 struct placement *p = &(individual->placements[i]);
776 switch (p->request->type)
779 printf("Point at [%.2f; %.2f]\n", p->x, p->y);
782 struct request_line *rl = (struct request_line *) p->request;
783 print_label(rl->segments[0].label);
785 case REQUEST_SEGMENT: ;
788 struct request_area *ra = (struct request_area *) p->request;
789 printf("Area label ");
790 print_label(ra->label);
791 printf(" at [%.2f; %.2f]\n", p->x, p->y);
794 ASSERT(p->request->type != 0);
797 printf("\nTotal penalty: %d\n", individual->penalty);
800 void labeller_label(void)
808 dump_linelabel_requests();
810 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));
812 GARY_INIT(population1, conf_pop_size);
813 GARY_INIT(population2, conf_pop_size);
816 printf("Dealing with %d requests\n", num_requests);
819 while (! shall_terminate())
823 struct individual **swp = population1;
824 population1 = population2;
830 dump_individual(population1[0]);
832 for (uns i=0; i<GARY_SIZE(population1[0]->placements); i++)
834 printf("Coping with %d\n", population1[0]->placements[i].request->type);
835 switch (population1[0]->placements[i].request->type)
837 case REQUEST_POINT: ;
838 struct request_point *rp = (struct request_point *) population1[0]->placements[i].request;
839 switch (rp->sym->type)
841 case SYMBOLIZER_POINT: ;
842 printf("Moving point to final destination\n");
843 struct sym_point *sp = (struct sym_point *) rp->sym;
844 sp->x = population1[0]->placements[i].x;
845 sp->y = population1[0]->placements[i].y;
846 sym_plan((struct symbol *) sp, rp->zindex);
848 case SYMBOLIZER_ICON: ;
849 printf("Moving icon to final destination\n");
850 struct sym_icon *si = (struct sym_icon *) rp->sym;
851 si->sir.x = population1[0]->placements[i].x;
852 si->sir.y = population1[0]->placements[i].y;
853 sym_plan((struct symbol *) si, rp->zindex);
856 printf("Haúúú 1\n");
861 struct request_area *ra = (struct request_area *) population1[0]->placements[i].request;
862 if (ra->label->type == SYMBOLIZER_INVALID) printf("Haúúú 2\n");
863 sym_plan((struct symbol *) ra->label, ra->zindex);
867 struct request_line *rl = (struct request_line *) population1[0]->placements[i].request;
868 for (uns j=0; j<GARY_SIZE(rl->segments); j++)
870 switch (rl->segments[j].label->type)
872 case SYMBOLIZER_TEXT:
873 ((struct sym_text *) rl->segments[j].label)->next_duplicate = NULL;
874 ((struct sym_text *) rl->segments[j].label)->next_in_tile = NULL;
875 printf("Planning text ");
876 print_label(rl->segments[j].label);
878 printf("Haúúú 3\n");
882 sym_plan((struct symbol *) rl->segments[j].label, rl->segments[j].zindex); // FIXME: z-index
886 case REQUEST_SEGMENT: ;
887 //struct request_segment *rs = (struct request_segment *) population1[0]->placements[i].request;
888 printf("Segment!\n");
891 ASSERT(population1[0]->placements[i].request->type != REQUEST_INVALID);
897 while (! shall_terminate())
905 // sort population by fitness
907 struct individual **swp = population1;
908 population1 = population2;
909 printf("Swapped populations\n");
911 // GARY_RESIZE(population2, 0) -- is it needed?
916 void make_population(void)
918 for (int i=0; i<conf_pop_size; i++)
920 struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
921 population1[i] = individual;
924 for (uns j=0; j<GARY_SIZE(requests_point); j++)
926 init_placement(&(individual->placements[p++]), (struct request *) &requests_point[j]);
928 for (uns j=0; j<GARY_SIZE(requests_line); j++)
930 init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j]);
931 for (uns k=0; k<GARY_SIZE(requests_line[j].segments); k++)
933 init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j].segments[k]);
936 for (uns j=0; j<GARY_SIZE(requests_area); j++)
938 init_placement(&(individual->placements[p++]), (struct request *) &requests_area[j]);
941 ASSERT(p == num_requests);
945 bool shall_terminate(void)
947 switch (conf_term_cond)
949 case TERM_COND_PENALTY:
950 return (population1[0]->penalty < conf_penalty_bound);
951 case TERM_COND_STAGNATION:
952 return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
953 case TERM_COND_ITERATIONS:
954 return (iteration >= conf_iteration_limit);
956 // FIXME: Warn the user that no condition is set
965 printf("%.2f\n", ((double) conf_breed_pop_size_perc/100));
966 int conf_breed_pop_size = ((double) conf_breed_pop_size_perc/100) * conf_pop_size;
967 struct individual **breed_buffer;
968 while (i < conf_breed_pop_size)
970 printf("%d < %d, breeding\n", i, conf_breed_pop_size);
971 int parent1 = randint(1, conf_breed_pop_size);
972 int parent2 = randint(1, conf_breed_pop_size);
973 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);
974 breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
975 population2[pop2_ind++] = breed_buffer[0];
976 population2[pop2_ind++] = breed_buffer[1];
981 acc += conf_breed_rbest_perc;
983 return; // FIXME: DEBUG HACK
985 int remaining = (1 - acc) * (conf_pop_size * conf_breed_perc);
986 int step = remaining / conf_pop_size;
987 for (; i<conf_pop_size; i += 2)
989 printf("Asking for %d and %d of %d\n", i*step, i*(step+1), conf_pop_size);
990 breed_buffer = perform_crossover(population1[i*step], population1[i*step+1]);
991 population2[pop2_ind++] = breed_buffer[0];
992 population2[pop2_ind++] = breed_buffer[1];
995 // FIXME: Could there be one missing individual?
998 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
1000 struct individual **buffer = malloc(2*sizeof(struct individual));
1001 struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
1002 struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
1004 printf("Performing crossover\n");
1006 for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
1008 printf("%dth placement out of %d\n", i, num_requests);
1009 if (! parent1->placements[i].processed)
1011 struct placement **clos_symbols = get_closure(&(parent1->placements[i]), parent1, parent2);
1012 int x = randint(1, 2);
1016 copy_symbols(clos_symbols, parent1, child1);
1017 copy_symbols(clos_symbols, parent2, child2);
1021 copy_symbols(clos_symbols, parent2, child1);
1022 copy_symbols(clos_symbols, parent1, child2);
1024 printf("Symbols copied; %lld\n", GARY_SIZE(clos_symbols));
1025 GARY_FREE(clos_symbols);
1028 if (conf_mutate_children)
1030 if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child1);
1031 if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child2);
1043 int conf_mutate_pop_size = conf_mutate_pop_size_perc * conf_pop_size;
1044 while (i < conf_mutate_rbest_perc * conf_pop_size)
1046 int ind = randint(1, conf_mutate_pop_size);
1047 copy_individual(population2[pop2_ind], population1[ind]);
1048 perform_mutation(population2[pop2_ind]);
1053 void perform_mutation(struct individual *individual)
1055 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1057 int x = randint(1, 1000);
1060 if (x <= acc + conf_mutate_move_bound)
1062 move_symbol(&(individual->placements[i]));
1065 acc += conf_mutate_move_bound;
1067 if (x <= acc + conf_mutate_regen_bound)
1069 gen_coords(&(individual->placements[i]));
1072 acc += conf_mutate_regen_bound;
1074 if (x <= acc + conf_mutate_chvar_bound)
1076 if (0) // if num_variants > 1
1078 // FIXME: assign new variant
1086 for (int i=0; i<conf_elite_perc * conf_pop_size; i++)
1088 population2[pop2_ind++] = population1[0];
1092 void rank_population(void)
1097 void gen_coords(struct placement *p)
1099 switch(p->request->type)
1102 gen_coords_point(p);
1104 case REQUEST_SEGMENT:
1106 printf("Not yet implemented\n");
1108 ASSERT(p->request->type != REQUEST_INVALID);
1112 void gen_coords_point(struct placement *p UNUSED)
1117 struct map_part **get_parts(struct placement *symbol, struct individual *individual)
1119 struct map_part **buffer;
1120 GARY_INIT(buffer, 0);
1121 int x_min = symbol->x / conf_part_size;
1122 int x_max = (symbol->x /*+ symbol->bitmap->width*/ + conf_part_size - 1) / conf_part_size;
1123 int y_min = symbol->y / conf_part_size;
1124 int y_max = (symbol->y /*+ symbol->bitmap->height*/ + conf_part_size - 1) / conf_part_size;
1126 for (int x=x_min; x < x_max; x++)
1127 for (int y=y_min; y < y_max; y++)
1129 struct map_part *m = GARY_PUSH(buffer);
1130 *m = individual->map[x][y];
1136 int randint(int min, int max)
1139 //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)));
1140 return min + (r % (max - min));
1141 return (r * (max - min));
1144 struct placement **get_closure(struct placement *placement, struct individual *parent1, struct individual *parent2 UNUSED)
1146 printf("Getting closure\n");
1147 struct placement **closure;
1148 GARY_INIT(closure, 0);
1149 bool *chosen = malloc(GARY_SIZE(parent1->placements) * sizeof(bool));
1150 chosen[placement->request->ind] = 1;
1152 struct placement **p = GARY_PUSH(closure); *p = placement;
1155 while (first < GARY_SIZE(closure))
1157 printf("Iterating, first is %d\n", first);
1158 struct placement **overlapping = get_overlapping(placement);
1159 filter(overlapping, chosen);
1160 for (uns j=0; j<GARY_SIZE(overlapping); j++)
1162 p = GARY_PUSH(closure); *p = overlapping[j];
1163 chosen[overlapping[j]->request->ind] = 1;
1165 GARY_FREE(overlapping);
1172 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child)
1174 //printf("%d\n", child->penalty);
1175 //printf("Closure size: %lld\n", GARY_SIZE(closure));
1176 for (uns i=0; i<GARY_SIZE(closure); i++)
1178 int ind = closure[i]->request->ind;
1179 child->placements[ind] = parent->placements[ind];
1180 child->placements[ind].processed = 0;
1184 void move_symbol(struct placement *p)
1186 switch (p->request->type)
1189 move_symbol_point(p);
1191 case REQUEST_SEGMENT:
1193 printf("Not yet implemented\n");
1195 ASSERT(p->request->type != REQUEST_INVALID);
1199 void move_symbol_point(struct placement *p)
1201 p->x += (double) (move_min + randdouble()) * flip(1, -1);
1202 p->y += (double) (move_min + randdouble()) * flip(1, -1);
1205 void init_placement(struct placement *p, struct request *r)
1212 case REQUEST_POINT: ;
1213 struct request_point *rp = (struct request_point *) r;
1217 case REQUEST_LINE: ;
1219 case REQUEST_SEGMENT: ;
1220 struct request_segment *rs = (struct request_segment *) r;
1224 case REQUEST_AREA: ;
1225 struct request_area *ra = (struct request_area *) r;
1229 ASSERT(p->request->type != REQUEST_INVALID);
1232 printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y);
1235 void init_individual(struct individual *i)
1237 //printf("Initing individual\n");
1238 GARY_INIT(i->placements, num_requests);
1239 GARY_INIT(i->map, 0);
1240 i->penalty = 0; // FIXME
1243 struct placement **get_overlapping(struct placement *p UNUSED)
1245 struct placement **buffer;
1246 GARY_INIT(buffer, 0);
1250 void filter(struct placement **list UNUSED, bool *pred UNUSED)
1255 int flip(int a, int b)
1257 return (random() % 2 ? a : b);
1260 double randdouble(void)
1262 // FIXME: How the hell shall double in range <0, 1> be generated? O:)
1269 GARY_FREE(requests_point);
1270 GARY_FREE(requests_line);
1271 GARY_FREE(requests_area);
1274 void copy_individual(struct individual *src, struct individual *dest)
1276 src->penalty = dest->penalty;
1277 GARY_INIT(dest->placements, GARY_SIZE(src->placements));
1278 for (uns i=0; i<GARY_SIZE(src->placements); i++)
1280 dest->placements[i] = src->placements[i];