labeller.c

   1 #include <ucw/lib.h>
   2 #include <ucw/gary.h>
   3 #include <ucw/mempool.h>
   4 #include <ucw/eltpool.h>
   5
   6 #include "leo.h"
   7 #include "sym.h"
   8 #include "map.h"
   9 #include "labeller.h"
  10
  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
  15 #define HASH_WANT_NEW
  16 #define HASH_WANT_CLEANUP
  17 #include <ucw/hashtable.h>
  18
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <math.h>
  22 #include <fcntl.h>
  23 #include <limits.h>
  24
  25 #define BLOCK_SIZE 4096
  26
  27 static struct request_point *requests_point;
  28 static struct request_line *requests_line;
  29 static struct request_area *requests_area;
  30
  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;
  35
  36 struct eltpool *ep_individuals;
  37
  38 struct individual **population1;
  39 struct individual **population2;
  40
  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;
  54
  55 int page_width_int;
  56 int page_height_int;
  57
  58 int num_nodes;
  59 int num_edges = 0;
  60 int dbg_num_hits = 0;
  61
  62 int conf_pop_size = 50;
  63 int conf_fit_size = 1;
  64
  65 int conf_penalty_bound = 0;
  66 int conf_stagnation_bound = 0;
  67 int conf_iteration_limit = 100;
  68
  69 int conf_term_cond = TERM_COND_ITERATIONS;
  70
  71 double conf_breed_pop_size = 0.4;
  72 double conf_breed_rbest = 0.2;
  73
  74 int breed_pop_size;
  75 int breed_rbest_size;
  76
  77 bool conf_mutate_children = 1;
  78 double conf_mutate_children_prob = 1.0;
  79
  80 double conf_mutate_pop_size = 0.4;
  81 double conf_mutate_rbest = 0.2;
  82
  83 double conf_mutate_move_bound = 0.1;
  84 double conf_mutate_regen_bound = 0.0;
  85 double conf_mutate_chvar_bound = 0.0;
  86
  87 int mutate_pop_size;
  88 int mutate_rbest_size;
  89
  90 double conf_elite_pop_size = 0.2;
  91 int elite_pop_size;
  92
  93 double conf_max_section_length = 100;
  94 double conf_max_section_overlay = 10;
  95
  96 int old_best = INT_MAX;
  97 int iteration = 0;
  98 int pop2_ind;
  99
 100 // In milimeters
 101 int move_min = 0;
 102 int move_max = 5;
 103
 104 int num_requests = 0;
 105 int num_placements = 0;
 106
 107 // In milimeters
 108 int conf_map_part_width = 5;
 109 int conf_map_part_height = 5;
 110
 111 uns num_map_parts_row;
 112 uns num_map_parts_col;
 113 uns num_map_parts;
 114
 115 void compute_sizes(void);
 116
 117 void make_population(void);
 118 bool shall_terminate(void);
 119 void breed(void);
 120 void mutate(void);
 121 void elite(void);
 122 void rank_population(void);
 123 void plan_individual(struct individual *individual);
 124
 125 int overlaps(struct placement *p1, struct placement *p2);
 126 int get_overlap(struct placement *p);
 127 int individual_overlap(struct individual *individual);
 128
 129 double get_distance(struct placement *p);
 130 double individual_distances(struct individual *individual);
 131
 132 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2);
 133 void perform_mutation(struct individual *individual);
 134 void init_placement(struct placement *p, struct individual *individual, struct request *r);
 135 void init_individual(struct individual *i);
 136 void copy_individual(struct individual *src, struct individual *dest);
 137 int cmp_individual(const void *a, const void *b);
 138
 139 void clear_individual(struct individual *individual);
 140 void clear_population(struct individual **pop);
 141
 142 void make_bitmap(struct variant *v, struct symbol *sym);
 143 void make_bitmap_icon(struct variant *v, struct sym_icon *si);
 144 void make_bitmap_point(struct variant *v, struct sym_point *sp);
 145 void make_bitmap_label(struct variant *v, struct sym_text *text);
 146
 147 double gen_movement(void);
 148 double gen_movement_uniform(void);
 149 void move_symbol(struct placement *p);
 150 void move_symbol_point(struct placement *p);
 151 void move_symbol_segment(struct placement *p);
 152 void hide_segment_labels(struct individual *individual);
 153
 154 void gen_coords(struct placement *p);
 155 void gen_coords_point(struct placement *p);
 156 void gen_coords_segment(struct placement *p);
 157 void gen_coords_area(struct placement *p);
 158
 159 struct map_part **get_map_parts(struct placement *p);
 160 void update_map_parts(struct placement *p);
 161 struct placement **get_closure(struct placement *placement);
 162 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child, bool **processed_ptr);
 163 struct placement **get_overlapping(struct placement *p);
 164 struct placement **filter(struct placement **list, bool **pred_ptr);
 165
 166
 167 void make_graph(void);
 168 void label_graph(void);
 169 void bfs_wrapper(void);
 170 void bfs(uns longline);
 171 void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir);
 172 void make_segments(void);
 173
 174 void cut_edge(struct graph_edge *e, double dist);
 175 struct request_line *make_new_line(void);
 176 struct request_section *make_new_section(struct request_line *rl);
 177 struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym);
 178
 179 void dump_bitmaps(struct individual *individual);
 180 void dump_graph(void);
 181 void dump_longlines(void);
 182 void dump_linelabel_requests(void);
 183 void dump_individual(struct individual *individual);
 184 void dump_label(struct symbol *sym);
 185 void dump_penalties(struct individual **population);
 186
 187 int randint(int min, int max);
 188 int flip(int a, int b);
 189 double randdouble(void);
 190
 191 int max2(int a, int b);
 192 int min2(int a, int b);
 193 int max4(int a, int b, int c, int d);
 194 int min4(int a, int b, int c, int d);
 195
 196 struct placement dummy_placement;
 197
 198 int max2(int a, int b)
 199 {
 200   return (a > b ? a : b);
 201 }
 202
 203 int min2(int a, int b)
 204 {
 205   return (a < b ? a : b);
 206 }
 207
 208 int max4(int a, int b, int c, int d)
 209 {
 210   return max2(max2(a, b), max2(c, d));
 211 }
 212
 213 int min4(int a, int b, int c, int d)
 214 {
 215   return min2(min2(a, b), min2(c, d));
 216 }
 217
 218 void dump_label(struct symbol *sym)
 219 {
 220   switch (sym->type)
 221   {
 222     case SYMBOLIZER_TEXT: ;
 223       struct sym_text *st = (struct sym_text *) sym;
 224       printf("%s\n", osm_val_decode(st->text));
 225     default:
 226       // FIXME
 227       ;
 228   }
 229 }
 230
 231 void labeller_init(void)
 232 {
 233   GARY_INIT(requests_point, 0);
 234   GARY_INIT(requests_line, 0);
 235   GARY_INIT(requests_area, 0);
 236   GARY_INIT(buffer_line, 0);
 237   GARY_INIT(buffer_linelabel, 0);
 238   ep_individuals = ep_new(sizeof(struct individual), 1);
 239
 240   compute_sizes();
 241 }
 242
 243 void make_bitmap(struct variant *v, struct symbol *sym)
 244 {
 245   v->offset_x = v->offset_y = 0;
 246
 247   switch (sym->type)
 248   {
 249     case SYMBOLIZER_POINT:
 250       make_bitmap_point(v, (struct sym_point *) sym);
 251       break;
 252     case SYMBOLIZER_ICON:
 253       make_bitmap_icon(v, (struct sym_icon *) sym);
 254       break;
 255     case SYMBOLIZER_TEXT:
 256       make_bitmap_label(v, (struct sym_text *) sym);
 257       break;
 258     default:
 259       ASSERT(sym->type != SYMBOLIZER_INVALID);
 260   }
 261 }
 262
 263 void make_bitmap_icon(struct variant *v, struct sym_icon *si)
 264 {
 265   v->width = si->sir.width + 1;
 266   v->height = si->sir.height + 1;
 267   v->bitmap = malloc(v->width * v->height * sizeof(bool));
 268   for (int i=0; i<v->width*v->height; i++) v->bitmap[i] = 1;
 269 }
 270
 271 void make_bitmap_point(struct variant *v, struct sym_point *sp)
 272 {
 273   v->width = v->height = sp->size + 1;
 274   v->bitmap = malloc(v->width * v->height * sizeof(bool));
 275   // FIXME: Okay, memset would be much nicer here
 276   for (int i=0; i<sp->size*sp->size; i++) v->bitmap[i] = 1;
 277 }
 278
 279 void make_bitmap_label(struct variant *v, struct sym_text *text)
 280 {
 281   v->width = ceil(text->tw);
 282   v->height = ceil(text->th);
 283   v->bitmap = malloc(v->width * v->height * sizeof(bool));
 284   for (int i=0; i<v->height; i++)
 285     for (int j=0; j<v->width; j++)
 286     {
 287       v->bitmap[i*v->width + j] = 1;
 288     }
 289 }
 290
 291 void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex)
 292 {
 293   if (dbg_requests >= VERBOSITY_PLACEMENT)
 294     printf("Adding point\n");
 295   if (object->type != OSM_TYPE_NODE)
 296   {
 297     printf("Warning: Point label requested on non-point object\n");
 298     return;
 299   }
 300
 301   struct request_point *r = GARY_PUSH(requests_point);
 302
 303   r->request.type = REQUEST_POINT;
 304   r->request.ind = num_requests++;
 305
 306   r->sym = sym;
 307   r->zindex = zindex;
 308
 309   r->offset_x = 0;
 310   r->offset_y = 0;
 311
 312   r->num_variants = 1;
 313   GARY_INIT(r->request.variants, 0);
 314
 315   struct variant *v = GARY_PUSH(r->request.variants);
 316
 317   struct osm_node *n = (struct osm_node *) object; // FIXME: Compiler warning
 318   r->x = n->x;
 319   r->y = n->y;
 320   make_bitmap(v, sym);
 321   switch (sym->type)
 322   {
 323     case SYMBOLIZER_ICON:
 324       // FIXME: Really?
 325       r->x = ((struct sym_icon *)sym)->sir.x;
 326       r->y = ((struct sym_icon *)sym)->sir.y;
 327       break;
 328     default:
 329       // FIXME
 330       return;
 331   }
 332
 333   if (dbg_requests >= VERBOSITY_PLACEMENT)
 334     printf("Inited point to [%.2f; %.2f] on %u\n", r->x, r->y, r->zindex);
 335 }
 336
 337 void labeller_add_line(struct symbol *sym, z_index_t zindex)
 338 {
 339   if (dbg_requests >= VERBOSITY_PLACEMENT)
 340     printf("Adding line on %u\n", zindex);
 341   struct buffer_line *b = GARY_PUSH(buffer_line);
 342   b->line = (struct sym_line *) sym;
 343   b->zindex = zindex;
 344   sym_plan(sym, zindex);
 345 }
 346
 347 void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
 348 {
 349   if (o->type != OSM_TYPE_WAY)
 350   {
 351     printf("Linelabel request on object which is not way\n");
 352     return;
 353   }
 354
 355   if (dbg_requests >= VERBOSITY_PLACEMENT)
 356     printf("Labelling way %ju on %u\n", o->id, zindex);
 357   struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
 358   ll->way = (struct osm_way *) o;
 359   ll->label = sym;
 360   ll->zindex = zindex;
 361 }
 362
 363 void labeller_add_arealabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
 364 {
 365   if (dbg_requests >= VERBOSITY_PLACEMENT)
 366     printf("Adding area on %u\n", zindex);
 367   struct request_area *r = GARY_PUSH(requests_area);
 368
 369   r->request.type = REQUEST_AREA;
 370   r->request.ind = num_requests++;
 371
 372   r->o = (struct osm_multipolygon *) o;
 373   r->zindex = zindex;
 374   r->label = sym;
 375
 376   osm_obj_center(o, &(r->cx), &(r->cy));
 377
 378   GARY_INIT(r->request.variants, 0);
 379   struct variant *v = GARY_PUSH(r->request.variants);
 380   make_bitmap(v, sym);
 381 }
 382
 383 void make_graph(void)
 384 {
 385   hash_init();
 386   struct mempool *mp_edges = mp_new(BLOCK_SIZE);
 387
 388   if (dbg_graph >= VERBOSITY_GENERAL)
 389     printf("Extracting nodes, will iterate over %lld ways\n", GARY_SIZE(buffer_line));
 390   for (uns i=0; i<GARY_SIZE(buffer_line); i++)
 391   {
 392     struct osm_way *way = (struct osm_way *) buffer_line[i].line->s.o;
 393     struct graph_node *g_prev = NULL;
 394     struct osm_node *o_prev = NULL;
 395
 396     CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
 397     {
 398       // FIXME: Shall osm_object's type be checked here?
 399       struct osm_node *o_node = (struct osm_node *) ref->o;
 400
 401       struct graph_node *g_node = hash_find(ref->o->id);
 402       if (!g_node)
 403       {
 404         g_node = hash_new(ref->o->id);
 405         GARY_INIT(g_node->edges, 0);
 406         g_node->o = o_node;
 407         g_node->id = ref->o->id;
 408         g_node->num = num_nodes++;
 409       }
 410
 411       if (! g_prev)
 412       {
 413         g_prev = g_node;
 414         o_prev = o_node;
 415         continue;
 416       }
 417
 418       struct graph_edge *e = mp_alloc(mp_edges, sizeof(struct graph_edge));
 419       e->num = num_edges++;
 420       e->id = buffer_line[i].line->s.o->id;
 421       e->color = buffer_line[i].line->color;
 422       e->length = hypot(abs(o_prev->x - o_node->x), abs(o_prev->y - o_node->y));
 423       e->visited = -1;
 424       e->prev = NULL;
 425       e->next = NULL;
 426       e->n1 = g_prev;
 427       e->n2 = g_node;
 428       e->longline = (uns) -1;
 429       e->line = buffer_line[i].line;
 430       e->dir = DIR_UNSET;
 431       e->label = NULL;
 432
 433       struct graph_edge **edge = GARY_PUSH(g_prev->edges);
 434       *edge = e;
 435       edge = GARY_PUSH(g_node->edges);
 436       *edge = e;
 437
 438       g_prev = g_node;
 439       o_prev = o_node;
 440     }
 441   }
 442 }
 443
 444 void dump_graph(void)
 445 {
 446   HASH_FOR_ALL(hash, node)
 447   {
 448     printf("* Node: (%d) #%ju [%.2f; %.2f]\n", node->num, node->id, node->o->x, node->o->y);
 449     for (uns i=0; i<GARY_SIZE(node->edges); i++)
 450     {
 451       struct graph_edge *e = node->edges[i];
 452       printf("\t edge (%d) #%ju to ", e->num, e->id);
 453       if (node->edges[i]->n1->id == node->id)
 454         printf("(%d) #%ju [%.2f; %.2f]\n", e->n2->num, e->n2->id, e->n2->o->x, e->n2->o->y);
 455       else if (node->edges[i]->n2->id == node->id)
 456         printf("(%d) #%ju [%.2f; %.2f]\n", e->n1->num, e->n1->id, e->n1->o->x, e->n1->o->y);
 457       else
 458       {
 459         // This shouldn't ever happen
 460         printf("BEWARE! Edge is associated with a node it doesn't belongs to!\n");
 461       }
 462
 463       printf("\t\t");
 464
 465       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));
 466       else if ((node->edges[i]->label)) printf("Labelled\n");
 467
 468       printf(" colored %d;", node->edges[i]->color);
 469       printf("   length %.2f", node->edges[i]->length);
 470       printf("\n");
 471     }
 472   }
 473   HASH_END_FOR;
 474 }
 475
 476 void label_graph(void)
 477 {
 478   if (dbg_graph >= VERBOSITY_GENERAL)
 479     printf("There are %u line labels requested\n", GARY_SIZE(buffer_linelabel));
 480   for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
 481   {
 482     if (buffer_linelabel[i].label->type == SYMBOLIZER_TEXT)
 483     if (dbg_graph >= VERBOSITY_INDIVIDUAL)
 484       printf("Labelling nodes of way %s\n", osm_val_decode(((struct sym_text *) buffer_linelabel[i].label)->text));
 485     CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
 486     {
 487       if (dbg_graph >= VERBOSITY_PLACEMENT)
 488         printf("Looking for node %ju\n", ref->o->id);
 489       struct graph_node *n = hash_find(ref->o->id);
 490       if (n == NULL)
 491       {
 492         printf("BEWARE! Requested node couldn't be found.\n");
 493       }
 494       else
 495       {
 496         if (dbg_graph >= VERBOSITY_ALL)
 497           printf("Searching among %u edges\n", GARY_SIZE(n->edges));
 498         for (uns j=0; j<GARY_SIZE(n->edges); j++)
 499         {
 500           if (n->edges[j]->id == buffer_linelabel[i].way->o.id)
 501           {
 502             if (dbg_graph >= VERBOSITY_ALL)
 503               printf("Labelling node %ju\n", n->id);
 504             n->edges[j]->label = buffer_linelabel[i].label;
 505             n->edges[j]->zindex = buffer_linelabel[i].zindex;
 506           }
 507         }
 508       }
 509     }
 510   }
 511 }
 512
 513 void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir)
 514 {
 515   if (dbg_bfs >= VERBOSITY_PLACEMENT)
 516     printf("BFS edge called for edge %d (going %d) in direction %d\n", e->num, e->dir, dir);
 517   struct graph_edge *candidate = NULL;
 518
 519   for (uns i=0; i<GARY_SIZE(node->edges); i++)
 520   {
 521     struct graph_edge *other = node->edges[i];
 522     if ((other->longline != (uns) -1) && (other->longline != e->longline)) continue;
 523
 524     if ((uns) other->visited != e->longline) {
 525     if (dbg_bfs >= VERBOSITY_PLACEMENT)
 526       printf("Pushing new edge %d / %ju\n", other->num, other->id);
 527     struct graph_edge **e_ptr = GARY_PUSH(bfs_queue);
 528     *e_ptr = other;
 529     other->visited = e->longline;
 530     }
 531
 532     if (((other->n1->id == node->id) && (other->n2->id == anode->id)) ||
 533         ((other->n2->id == node->id) && (other->n1->id == anode->id)))
 534         continue;
 535
 536     if (((other->n1->id == node->id) || (other->n2->id == node->id)) &&
 537         (e->label) && (other->label) &&
 538         (e->label->type == SYMBOLIZER_TEXT) && (other->label->type == SYMBOLIZER_TEXT) &&
 539         (((struct sym_text *) e->label)->text == ((struct sym_text *) other->label)->text))
 540     {
 541       if (! candidate || (other->length > candidate->length))
 542       candidate = other;
 543     }
 544   }
 545
 546   if (candidate)
 547   {
 548     if (dbg_bfs >= VERBOSITY_PLACEMENT)
 549       printf("New line in longline %u\n", e->longline);
 550     struct graph_edge *other = candidate;
 551       other->longline = e->longline;
 552       other->dir = dir;
 553       if (((dir == DIR_BWD) && (other->n1->id == node->id)) ||
 554           ((dir == DIR_FWD) && (other->n2->id == node->id)))
 555       {
 556         struct graph_node *swp = other->n2;
 557         other->n2 = other->n1;
 558         other->n1 = swp;
 559       }
 560
 561       switch (dir)
 562       {
 563         case DIR_BWD:
 564           e->prev = other;
 565           other->next = e;
 566           longlines[other->longline].first = other;
 567           break;
 568         case DIR_FWD:
 569           e->next = other;
 570           other->prev = e;
 571           break;
 572         default:
 573           printf("Oops\n");
 574           ASSERT(0);
 575       }
 576   }
 577 }
 578
 579 void bfs(uns longline)
 580 {
 581   if (dbg_bfs >= VERBOSITY_INDIVIDUAL)
 582   {
 583     printf("BFS called for longline %u\n", longline);
 584     printf("%d longlines are believed to exist, %d exist\n", num_longlines, GARY_SIZE(longlines));
 585   }
 586
 587   for (uns i=0; i<GARY_SIZE(bfs_queue); i++)
 588   {
 589     struct graph_edge *cur = bfs_queue[i];
 590     if (dbg_bfs >= VERBOSITY_PLACEMENT)
 591       printf("Exploring new edge %d; %d remaining\n", cur->num, GARY_SIZE(bfs_queue));
 592
 593     cur->visited = longline;
 594
 595     if (cur->longline == (uns) -1)
 596       continue;
 597
 598     if (cur->dir == DIR_UNSET)
 599     {
 600       cur->dir = DIR_CENTER;
 601       bfs_edge(cur, cur->n1, cur->n2, DIR_BWD);
 602       bfs_edge(cur, cur->n2, cur->n1, DIR_FWD);
 603     }
 604     else
 605     {
 606       switch (cur->dir)
 607       {
 608         case DIR_BWD:
 609           bfs_edge(cur, cur->n1, cur->n2, cur->dir);
 610           break;
 611         case DIR_FWD:
 612           bfs_edge(cur, cur->n2, cur->n1, cur->dir);
 613           break;
 614         default:
 615           // FIXME
 616           ;
 617       }
 618     }
 619   }
 620 }
 621
 622 void bfs_wrapper(void)
 623 {
 624   GARY_INIT(bfs_queue, 0);
 625   GARY_INIT(longlines, 0);
 626
 627   HASH_FOR_ALL(hash, node)
 628   {
 629     for (uns i=0; i<GARY_SIZE(node->edges); i++)
 630     {
 631       if ((node->edges[i]->label) && (node->edges[i]->longline == (uns) -1))
 632       {
 633         GARY_PUSH(longlines);
 634         longlines[num_longlines].first = node->edges[i];
 635
 636         if (dbg_bfs >= VERBOSITY_INDIVIDUAL)
 637         {
 638           printf("Running new BFS\n");
 639           printf("Creating longline %u\n", num_longlines);
 640         }
 641
 642         GARY_RESIZE(bfs_queue, 0);
 643         struct graph_edge **e = GARY_PUSH(bfs_queue);
 644         *e = node->edges[i];
 645         node->edges[i]->longline = num_longlines;
 646         bfs(node->edges[i]->longline);
 647
 648         if (dbg_bfs >= VERBOSITY_INDIVIDUAL)
 649         {
 650           printf("Joined %d edges\n", dbg_num_hits); dbg_num_hits = 0;
 651           printf("Planned %u edges\n", GARY_SIZE(bfs_queue));
 652         }
 653         num_longlines++;
 654       }
 655     }
 656   }
 657   HASH_END_FOR;
 658
 659   GARY_FREE(bfs_queue);
 660 }
 661
 662 void dump_longlines(void)
 663 {
 664   printf("*** Longlines dump\n");
 665   for (uns i=0; i<GARY_SIZE(longlines); i++)
 666   {
 667     printf("Longline %u:", i);
 668     struct graph_edge *e = longlines[i].first;
 669     if ((e->label) && (e->label->type == SYMBOLIZER_TEXT))
 670       printf(" labelled %s", osm_val_decode(((struct sym_text *) e->label)->text));
 671     printf("\n");
 672
 673     while (e)
 674     {
 675       printf("\t#%ju (%d): [%.2f; %.2f] -- [%.2f; %.2f] (dir %d)\n",
 676              e->id, e->num, e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y, e->dir);
 677
 678       e = e->next;
 679     }
 680   }
 681 }
 682
 683 struct request_line *make_new_line(void)
 684 {
 685   struct request_line *rl = GARY_PUSH(requests_line);
 686   rl->request.ind = num_requests++;
 687   rl->request.type = REQUEST_LINE;
 688   GARY_INIT(rl->sections, 0);
 689   GARY_INIT(rl->request.variants, 0);
 690
 691   return rl;
 692 }
 693
 694 struct request_section *make_new_section(struct request_line *rl)
 695 {
 696   struct request_section *rls = GARY_PUSH(rl->sections);
 697   rls->request.ind = num_requests++;
 698   rls->request.type = REQUEST_SECTION;
 699   rls->num_segments = 0;
 700   GARY_INIT(rls->segments, 0);
 701   GARY_INIT(rls->request.variants, 0);
 702
 703   return rls;
 704 }
 705
 706 struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym)
 707 {
 708   struct request_segment *rs = GARY_PUSH(rls->segments);
 709   rls->num_segments++;
 710
 711   rs->request.ind = num_requests++;
 712   rs->request.type = REQUEST_SEGMENT;
 713
 714   GARY_INIT(rs->request.variants, 0);
 715   struct variant *v = GARY_PUSH(rs->request.variants);
 716   make_bitmap(v, sym);
 717
 718   return rs;
 719 }
 720
 721 void cut_edge(struct graph_edge *e, double dist)
 722 {
 723   if (dbg_segments >= VERBOSITY_PLACEMENT)
 724     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);
 725
 726   struct graph_edge *new = malloc(sizeof(struct graph_edge));
 727   *new = *e;
 728   e->next = new;
 729
 730   switch (e->label->type)
 731   {
 732     case SYMBOLIZER_TEXT:
 733       new->label = malloc(sizeof(struct sym_text));
 734       *((struct sym_text *) new->label) = *((struct sym_text *) e->label);
 735       break;
 736     default:
 737       ;
 738   }
 739
 740   struct osm_node *n1 = e->n1->o;
 741   struct osm_node *n2 = e->n2->o;
 742
 743   if ((n1->x == n2->x) && (n1->y == n2->y))
 744   {
 745     printf("[%.2f; %.2f] -- [%.2f; %.2f]\n", n1->x, n1->y, n2->x, n2->y);
 746     if (dbg_segments >= VERBOSITY_PLACEMENT)
 747       printf("Won't cut point\n");
 748     return;
 749   }
 750
 751   struct osm_node *n11 = malloc(sizeof(struct osm_node));
 752   struct graph_node *gn = malloc(sizeof(struct graph_node));
 753   gn->o = n11;
 754   double vsize = sqrt(pow(n1->x - n2->x, 2) + pow(n1->y - n2->y, 2));
 755   n11->x = n1->x + (n2->x - n1->x) / vsize * dist;
 756   n11->y = n1->y + (n2->y - n1->y) / vsize * dist;
 757
 758   e->n2 = new->n1 = gn;
 759
 760   e->length = hypot(abs(n1->x - n11->x), abs(n1->y - n11->y));
 761   new->length = hypot(abs(n11->x - n2->x), abs(n11->y - n2->y));
 762   new->visited = 0;
 763 }
 764
 765 void make_segments(void)
 766 {
 767   for (uns i=0; i<GARY_SIZE(longlines); i++)
 768   {
 769     // Skip lines which are not labelled
 770     if (! (longlines[i].first && longlines[i].first->label))
 771       continue;
 772
 773     struct request_line *request = make_new_line();
 774     struct request_section *rls = make_new_section(request);
 775     struct request_segment *rs = NULL;
 776
 777     struct graph_edge *e = longlines[i].first;
 778     double cur_length = 0;
 779
 780     struct sym_text *st = NULL;
 781     if (e->label->type == SYMBOLIZER_TEXT)
 782     {
 783       st = (struct sym_text *) e->label;
 784     }
 785     else
 786     {
 787       // FIXME: Should other label types be supported in future?
 788       if (dbg_segments >= VERBOSITY_PLACEMENT)
 789         printf("Warning: Skipping line\n");
 790       continue;
 791     }
 792
 793     if (dbg_segments >= VERBOSITY_INDIVIDUAL)
 794       printf("New longline\n");
 795
 796     while (e)
 797     {
 798       if (e->visited < 0)
 799       {
 800         if (dbg_segments >= VERBOSITY_PLACEMENT)
 801           printf("BEWARE: Edge cycle\n");
 802         break;
 803       }
 804       e->visited = -1;
 805
 806       if (dbg_segments >= VERBOSITY_PLACEMENT)
 807         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);
 808
 809       if (st && (e->length < st->tw))
 810       {
 811         e = e->next;
 812         if (dbg_segments >= VERBOSITY_PLACEMENT)
 813           printf("Warning: Skipping segment\n");
 814         continue;
 815       }
 816
 817       if (cur_length + e->length > conf_max_section_length + conf_max_section_overlay)
 818       {
 819         if (dbg_segments >= VERBOSITY_PLACEMENT)
 820           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);
 821         // HACK to prevent cutting to 0 lenght
 822         cut_edge(e, max2(conf_max_section_length - cur_length, 2));
 823       }
 824
 825       rs = make_new_segment(rls, e->label);
 826       rs->label = malloc(sizeof(struct sym_text));
 827       *((struct sym_text *) rs->label) = *((struct sym_text *) e->label);
 828
 829       rs->x1 = e->n1->o->x;
 830       rs->y1 = e->n1->o->y;
 831       rs->x2 = e->n2->o->x;
 832       rs->y2 = e->n2->o->y;
 833
 834       rs->slope = (rs->y2 - rs->y1) / (rs->x2 - rs->x1);
 835       rs->zindex = e->zindex;
 836
 837       cur_length += e->length;
 838       if (cur_length > conf_max_section_length)
 839       {
 840         if (dbg_segments >= VERBOSITY_PLACEMENT)
 841           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);
 842
 843         rls = make_new_section(request);
 844         cur_length = 0;
 845       }
 846
 847       e = e->next;
 848     }
 849
 850     if (request->sections[0].num_segments == 0)
 851     {
 852       if (dbg_segments >= VERBOSITY_INDIVIDUAL)
 853         printf("WARNING: Longline without any segment, skipped\n");
 854
 855       struct request_section *rls = &request->sections[0];
 856       GARY_FREE(rls->segments);
 857       GARY_FREE(rls->request.variants);
 858
 859       struct request_line *rl = &requests_line[GARY_SIZE(requests_line)-1];
 860       GARY_FREE(rl->sections);
 861       GARY_FREE(rl->request.variants);
 862
 863       GARY_POP(requests_line);
 864       num_requests -= 2;
 865     }
 866   }
 867 }
 868
 869 void dump_linelabel_requests(void)
 870 {
 871   for (uns i=0; i<GARY_SIZE(requests_line); i++)
 872   {
 873     if (requests_line[i].sections[0].num_segments == 0)
 874     {
 875       if (dbg_segments >= VERBOSITY_INDIVIDUAL)
 876         printf("Beware: Longline without any segment\n");
 877       continue;
 878     }
 879
 880     printf("Request for linelabel, %d sections\n", GARY_SIZE(requests_line[i].sections));
 881     dump_label(requests_line[i].sections[0].segments[0].label);
 882     for (uns j=0; j<GARY_SIZE(requests_line[i].sections); j++)
 883     {
 884       printf("%d section, %d segments\n", j, GARY_SIZE(requests_line[i].sections[j].segments));
 885       for (uns k=0; k<GARY_SIZE(requests_line[i].sections[j].segments); k++)
 886       {
 887         struct request_segment *rs = &requests_line[i].sections[j].segments[k];
 888         printf("[%.2f; %.2f] -- [%.2f; %.2f]\n", rs->x1, rs->y1, rs->x2, rs->y2);
 889       }
 890     }
 891     printf("\n");
 892   }
 893 }
 894
 895 void dump_bitmaps(struct individual *individual)
 896 {
 897   bool *bitmap = malloc(page_width_int * page_height_int * sizeof(bool));
 898   printf("Bitmap size is %d\n", page_width_int * page_height_int);
 899   for (int i=0; i<page_height_int; i++)
 900     for (int j=0; j<page_width_int; j++)
 901       bitmap[i*page_width_int + j] = 0;
 902
 903   int total = 0;
 904   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 905   {
 906     if (individual->placements[i].variant_used == -1) continue;
 907
 908     struct placement *p = &(individual->placements[i]);
 909     struct variant *v = NULL;
 910
 911     switch (p->request->type)
 912     {
 913       case REQUEST_SEGMENT: ;
 914       case REQUEST_POINT: ;
 915       case REQUEST_AREA: ;
 916         v = &(p->request->variants[p->variant_used]);
 917         break;
 918       default:
 919         ASSERT(p->request->type != REQUEST_INVALID);
 920         continue;
 921     }
 922
 923     for (int row = max2(p->y, 0); row < min2(p->y + v->height, page_height_int); row++)
 924     {
 925       for (int col = max2(p->x, 0); col < min2(p->x + v->width, page_width_int); col++)
 926       {
 927         if (bitmap[row * page_width_int + col] == 1) total += 1;
 928         bitmap[row * page_width_int + col] = 1;
 929       }
 930     }
 931   }
 932   if (dbg_overlaps >= VERBOSITY_GENERAL)
 933     printf("There were %d collisions during bitmap dump\n", total);
 934
 935   FILE *fd_dump = fopen("dump.pbm", "w");
 936   fprintf(fd_dump, "P1\n");
 937   fprintf(fd_dump, "%d %d\n", page_width_int, page_height_int);
 938   for (int i=0; i<page_height_int; i++)
 939   {
 940     for (int j=0; j<page_width_int; j++)
 941     {
 942       fprintf(fd_dump, "%d", bitmap[(int) (i*page_width_int + j)] ? 1 : 0);
 943     }
 944     fprintf(fd_dump, "\n");
 945   }
 946   fclose(fd_dump);
 947
 948   free(bitmap);
 949 }
 950
 951 void dump_individual(struct individual *individual)
 952 {
 953   printf("*** Individual dump\n");
 954   printf("(There are %d requests)\n", num_requests);
 955
 956   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 957   {
 958     struct placement *p = &(individual->placements[i]);
 959
 960     switch (p->request->type)
 961     {
 962       case REQUEST_POINT:
 963         printf("Point at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_point *) p->request)->zindex);
 964         break;
 965       case REQUEST_LINE: ;
 966         struct request_line *rl = (struct request_line *) p->request;
 967         printf("Line: ");
 968         dump_label(rl->sections[0].segments[0].label);
 969         break;
 970       case REQUEST_SECTION: ;
 971         printf("*");
 972         break;
 973       case REQUEST_SEGMENT: ;
 974         if (p->variant_used >= 0)
 975           printf("Segment placed at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_segment *) p->request)->zindex);
 976         else
 977           printf("Segment not placed\n");
 978         break;
 979       case REQUEST_AREA: ;
 980         struct request_area *ra = (struct request_area *) p->request;
 981         printf("Area label ");
 982         dump_label(ra->label);
 983         printf(" at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_area *) p->request)->zindex);
 984         break;
 985       default:
 986         ASSERT(p->request->type != 0);
 987     }
 988   }
 989   printf("\nTotal penalty: %d\n", individual->penalty);
 990 }
 991
 992 void plan_individual(struct individual *individual)
 993 {
 994   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 995   {
 996     struct symbol *s = NULL;
 997     z_index_t zindex = 0;
 998     if (individual->placements[i].variant_used < 0) continue;
 999     switch (individual->placements[i].request->type)
1000     {
1001       case REQUEST_POINT: ;
1002         struct request_point *rp = (struct request_point *) individual->placements[i].request;
1003         s = rp->sym;
1004         zindex = rp->zindex;
1005         break;
1006       case REQUEST_SEGMENT: ;
1007         struct request_segment *rs = (struct request_segment *) individual->placements[i].request;
1008         s = rs->label;
1009         zindex = rs->zindex;
1010         break;
1011       case REQUEST_LINE: ;
1012         break;
1013       case REQUEST_AREA: ;
1014         struct request_area *ra = (struct request_area *) individual->placements[i].request;
1015         s = ra->label;
1016         zindex = ra->zindex;
1017         break;
1018       default:
1019         ASSERT(individual->placements[i].request != REQUEST_INVALID);
1020         continue;
1021     }
1022
1023   if (dbg_plan >= VERBOSITY_PLACEMENT)
1024     printf("Will plan symbol at [%.2f; %.2f] on %u\n", individual->placements[i].x, individual->placements[i].y, zindex);
1025
1026     if (s) switch (s->type)
1027     {
1028       case SYMBOLIZER_POINT: ;
1029         struct sym_point *sp = (struct sym_point *) s;
1030         sp->x = individual->placements[i].x;
1031         sp->y = individual->placements[i].y;
1032         sym_plan((struct symbol *) sp, zindex);
1033         break;
1034       case SYMBOLIZER_ICON: ;
1035         struct sym_icon *si = (struct sym_icon *) s;
1036         si->sir.x = individual->placements[i].x;
1037         si->sir.y = individual->placements[i].y;
1038         sym_plan((struct symbol *) si, zindex);
1039         break;
1040       case SYMBOLIZER_TEXT: ;
1041         struct sym_text *st = (struct sym_text *) s;
1042         st->x = individual->placements[i].x;
1043         st->y = individual->placements[i].y;
1044         st->next_duplicate = NULL;
1045         if (dbg_plan >= VERBOSITY_PLACEMENT)
1046           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);
1047         sym_plan((struct symbol *) st, zindex);
1048         break;
1049       default:
1050         ASSERT(s->type != SYMBOLIZER_INVALID);
1051     }
1052   }
1053 }
1054
1055 void dump_penalties(struct individual **population)
1056 {
1057   for (int i=0; i<conf_pop_size; i++)
1058   {
1059     printf("Individual %d has penalty %d\n", i, population[i]->penalty);
1060   }
1061 }
1062
1063 void compute_sizes(void)
1064 {
1065   page_width_int = floor(page_width);
1066   page_height_int = floor(page_height);
1067
1068   num_map_parts_row = (page_width_int + conf_map_part_width) / conf_map_part_width;
1069   num_map_parts_col = (page_height_int + conf_map_part_height) / conf_map_part_height;
1070   num_map_parts = num_map_parts_row * num_map_parts_col;
1071
1072   breed_pop_size = conf_breed_pop_size * conf_pop_size;
1073   breed_rbest_size = conf_breed_rbest * conf_pop_size;
1074   if (dbg_evolution >= VERBOSITY_GENERAL)
1075   {
1076     printf("Breeding parameters:\n");
1077     printf(" %d individuals are created\n", breed_pop_size);
1078     printf(" %d best individuals in old population are considered\n", breed_rbest_size);
1079   }
1080
1081   mutate_pop_size = conf_mutate_pop_size * conf_pop_size;
1082   mutate_rbest_size = conf_mutate_rbest * conf_pop_size;
1083   if (dbg_evolution >= VERBOSITY_GENERAL)
1084   {
1085     printf("Mutation parameters:\n");
1086     printf(" %d individuals are created\n", mutate_pop_size);
1087     printf(" %d best individuals in old population are considered\n", mutate_rbest_size);
1088   }
1089
1090   elite_pop_size = conf_elite_pop_size * conf_pop_size;
1091   if (dbg_evolution >= VERBOSITY_GENERAL)
1092   {
1093     printf("Elitism parameters:\n");
1094     printf(" %d best individuals are copied\n", elite_pop_size);
1095   }
1096
1097   if (breed_pop_size + mutate_pop_size + elite_pop_size != conf_pop_size)
1098   {
1099     if (conf_fit_size)
1100     {
1101       elite_pop_size += conf_pop_size - (breed_pop_size + mutate_pop_size + elite_pop_size);
1102     }
1103     else
1104     {
1105       fprintf(stderr, "Breeding + mutation + elitism won't create correct number of individuals\n");
1106       fprintf(stderr, "Please fix conf_breed_pop_size, conf_mutate_pop_size and conf_elite_pop_size parameters\n");
1107       exit(2);
1108     }
1109   }
1110 }
1111
1112 void labeller_label(void)
1113 {
1114   make_graph();
1115   label_graph();
1116   bfs_wrapper();
1117   make_segments();
1118
1119   GARY_INIT(population1, conf_pop_size);
1120   GARY_INIT(population2, conf_pop_size);
1121   make_population();
1122   rank_population();
1123   qsort(population1, conf_pop_size, sizeof(struct individual *), cmp_individual);
1124
1125   if (dbg_evolution >= VERBOSITY_GENERAL)
1126   {
1127     printf("Penalties after initialization\n");
1128     dump_penalties(population1);
1129   }
1130
1131   while (! shall_terminate())
1132   {
1133     iteration++;
1134     if (dbg_evolution)
1135       printf("\n*** Iteration %d ***\n", iteration);
1136
1137     breed();
1138     mutate();
1139     elite();
1140
1141     struct individual **swp = population1;
1142     population1 = population2;
1143     population2 = swp;
1144     pop2_ind = 0;
1145     clear_population(population2);
1146
1147     rank_population();
1148
1149     if (dbg_evolution >= VERBOSITY_GENERAL)
1150       printf("Sorting population\n");
1151     qsort(population1, conf_pop_size, sizeof(struct individual *), cmp_individual);
1152
1153     if (dbg_evolution >= VERBOSITY_GENERAL)
1154     {
1155       printf("Penalties after sort\n");
1156       dump_penalties(population1);
1157     }
1158
1159     old_best = population1[0]->penalty;
1160   }
1161
1162   if (dbg_overlaps >= VERBOSITY_GENERAL)
1163     dump_bitmaps(population1[0]);
1164
1165   plan_individual(population1[0]);
1166
1167   labeller_cleanup();
1168
1169   return;
1170 }
1171
1172 void labeller_cleanup(void)
1173 {
1174   hash_cleanup();
1175   GARY_FREE(requests_point);
1176   GARY_FREE(requests_line);
1177   GARY_FREE(requests_area);
1178 }
1179
1180 void make_population(void)
1181 {
1182   for (int i=0; i<conf_pop_size; i++)
1183   {
1184     num_placements = 0; // FIXME: This IS a terrible HACK
1185     struct individual *i2 = ep_alloc(ep_individuals);
1186     init_individual(i2);
1187     population2[i] = i2;
1188
1189     if (dbg_init >= VERBOSITY_INDIVIDUAL)
1190       printf("Making individual %d\n", i);
1191     struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
1192     population1[i] = individual;
1193
1194     int p = 0;
1195     for (uns j=0; j<GARY_SIZE(requests_point); j++)
1196     {
1197       init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_point[j]);
1198     }
1199
1200     for (uns j=0; j<GARY_SIZE(requests_line); j++)
1201     {
1202       init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j]);
1203
1204       for (uns k=0; k<GARY_SIZE(requests_line[j].sections); k++)
1205       {
1206         init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k]);
1207
1208         for (uns l=0; l<GARY_SIZE(requests_line[j].sections[k].segments); l++)
1209         {
1210           init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k].segments[l]);
1211         }
1212       }
1213     }
1214
1215     for (uns j=0; j<GARY_SIZE(requests_area); j++)
1216     {
1217       init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_area[j]);
1218     }
1219
1220     hide_segment_labels(individual);
1221
1222     ASSERT(p == num_requests);
1223   }
1224 }
1225
1226 bool shall_terminate(void)
1227 {
1228   switch (conf_term_cond)
1229   {
1230     case TERM_COND_PENALTY:
1231       return (population1[0]->penalty < conf_penalty_bound);
1232     case TERM_COND_STAGNATION:
1233       return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
1234     case TERM_COND_ITERATIONS:
1235       return (iteration >= conf_iteration_limit);
1236     default:
1237       fprintf(stderr, "Warning: No termination condition is set, terminating\n");
1238       return 1;
1239   }
1240 }
1241
1242 void breed(void)
1243 {
1244   int i=0;
1245
1246   struct individual **breed_buffer;
1247   while (i < breed_pop_size)
1248   {
1249     int parent1 = randint(0, breed_rbest_size);
1250     int parent2 = randint(0, breed_rbest_size);
1251     if (dbg_breeding >= VERBOSITY_INDIVIDUAL)
1252       printf("Will breed %d and %d\n", parent1, parent2);
1253
1254     breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
1255     population2[pop2_ind++] = breed_buffer[0];
1256     population2[pop2_ind++] = breed_buffer[1];
1257     free(breed_buffer);
1258     i += 2;
1259   }
1260
1261   return;
1262 }
1263
1264 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
1265 {
1266   struct individual **buffer = malloc(2*sizeof(struct individual));
1267   struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
1268   struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
1269
1270   bool *processed;
1271   GARY_INIT_ZERO(processed, GARY_SIZE(parent1->placements));
1272
1273   for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
1274   {
1275     if (! processed[parent1->placements[i].ind])
1276     {
1277       if (dbg_breeding >= VERBOSITY_PLACEMENT)
1278         printf("Creating symbol closure for placement %u\n", i);
1279
1280       struct placement **clos_symbols = get_closure(&(parent1->placements[i]));
1281       int x = randint(0, 2);
1282
1283       if (x == 0)
1284       {
1285         if (dbg_breeding >= VERBOSITY_PLACEMENT)
1286           printf("Copying parent->child 1->1 and 2->2\n");
1287         copy_symbols(clos_symbols, parent1, child1, &processed);
1288         copy_symbols(clos_symbols, parent2, child2, &processed);
1289       }
1290       else
1291       {
1292         if (dbg_breeding >= VERBOSITY_PLACEMENT)
1293           printf("Copying parent->child 2->1 and 1->2\n");
1294         copy_symbols(clos_symbols, parent2, child1, &processed);
1295         copy_symbols(clos_symbols, parent1, child2, &processed);
1296       }
1297
1298       GARY_FREE(clos_symbols);
1299     }
1300   }
1301
1302   GARY_FREE(processed);
1303
1304   if (conf_mutate_children)
1305   {
1306     if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child1);
1307     if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child2);
1308   }
1309
1310   buffer[0] = child1;
1311   buffer[1] = child2;
1312   return buffer;
1313 }
1314
1315 void mutate(void)
1316 {
1317   for (int i=0; i < mutate_pop_size; i++)
1318   {
1319     if (dbg_mutation >= VERBOSITY_INDIVIDUAL)
1320       printf("Creating %d-th individual by mutation\n", i);
1321     int ind = randint(0, mutate_rbest_size);
1322     if (dbg_mutation >= VERBOSITY_INDIVIDUAL)
1323       printf("Mutating %d-th individual of original population\n", ind);
1324     population2[pop2_ind] = ep_alloc(ep_individuals);
1325     copy_individual(population1[ind], population2[pop2_ind]);
1326     if (dbg_mutation >= VERBOSITY_INDIVIDUAL)
1327       printf("Individual %d in pop2 inited from individual %d in pop1\n", pop2_ind, ind);
1328     perform_mutation(population2[pop2_ind]);
1329     pop2_ind++;
1330   }
1331 }
1332
1333 void perform_mutation(struct individual *individual)
1334 {
1335   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1336   {
1337     double x = randdouble();
1338     double acc = 0;
1339
1340     if (x <= acc + conf_mutate_move_bound)
1341     {
1342       if (dbg_mutation >= VERBOSITY_PLACEMENT)
1343         printf("Mutation: Moving symbol in placement %u\n", i);
1344       move_symbol(&(individual->placements[i]));
1345       continue;
1346     }
1347     acc += conf_mutate_move_bound;
1348
1349     if (x <= acc + conf_mutate_regen_bound)
1350     {
1351       gen_coords(&(individual->placements[i]));
1352       continue;
1353     }
1354     acc += conf_mutate_regen_bound;
1355
1356     if (x <= acc + conf_mutate_chvar_bound)
1357     {
1358       struct placement *p = &(individual->placements[i]);
1359       switch (p->request->type)
1360       {
1361         case REQUEST_POINT:
1362         case REQUEST_SEGMENT:
1363         case REQUEST_AREA:
1364           // Does nothing when there are 0 variants... does it mind?
1365           p->variant_used = randint(0, GARY_SIZE(p->request->variants) - 1);
1366           break;
1367         case REQUEST_SECTION:
1368           p->variant_used = randint(0, GARY_SIZE(((struct request_section *) p->request)->segments)-1);
1369           break;
1370         default:
1371           ;
1372       }
1373     }
1374   }
1375
1376   hide_segment_labels(individual);
1377 }
1378
1379 void elite(void)
1380 {
1381   for (int i=0; i<elite_pop_size; i++)
1382   {
1383     population2[pop2_ind] = ep_alloc(ep_individuals);
1384     copy_individual(population1[i], population2[pop2_ind++]);
1385   }
1386 }
1387
1388 int overlaps(struct placement *p1, struct placement *p2)
1389 {
1390   if (p1->request->type != REQUEST_POINT &&
1391       p1->request->type != REQUEST_SEGMENT &&
1392       p1->request->type != REQUEST_AREA)
1393     return 0;
1394
1395   if (p2->request->type != REQUEST_POINT &&
1396       p2->request->type != REQUEST_SEGMENT &&
1397       p2->request->type != REQUEST_AREA)
1398     return 0;
1399
1400   if (p1->variant_used == -1 || p2->variant_used == -1)
1401     return 0;
1402
1403   struct variant *v1, *v2;
1404
1405   v1 = &(p1->request->variants[p1->variant_used]);
1406   v2 = &(p2->request->variants[p2->variant_used]);
1407
1408   // FIXME: This doesn't fully respect offset which it probably should
1409   int p1x = p1->x; int p1y = p1->y;
1410   int p2x = p2->x; int p2y = p2->y;
1411
1412   int overlap = 0;
1413   for (int y=max2(0, max2(p1y, p2y)); y<min2(page_height_int, min2(p1y+v1->height, p2y+v2->height)); y++)
1414     for (int x=max2(0, max2(p1x, p2x)); x<min2(page_width_int, min2(p1x+v1->width, p2x+v2->width)); x++)
1415     {
1416       if (v1->bitmap[(y-p1y)*v1->width + (x-p1x)] &&
1417           v2->bitmap[(y-p2y)*v2->width + (x-p2x)])
1418         overlap++;
1419     }
1420
1421   return overlap;
1422 }
1423
1424 int get_overlap(struct placement *p)
1425 {
1426   struct map_part **parts = get_map_parts(p);
1427   if (! parts)
1428   {
1429     if (dbg_overlaps >= VERBOSITY_PLACEMENT)
1430       printf("Placement of request %d seems not to be placed\n", p->request->ind);
1431     return 0;
1432   }
1433
1434   struct placement **others;
1435   bool *planned;
1436
1437   GARY_INIT_ZERO(planned, num_requests);
1438   planned[p->request->ind] = 1;
1439   GARY_INIT(others, 0);
1440
1441   for (uns i=0; i<GARY_SIZE(parts); i++)
1442   {
1443     struct map_placement *mp = parts[i]->placement->next_in_map;
1444     while (mp)
1445     {
1446       if (! planned[mp->placement->request->ind])
1447       {
1448         struct placement **p = GARY_PUSH(others);
1449         *p = mp->placement;
1450         planned[mp->placement->request->ind] = true;
1451       }
1452       mp = mp->next_in_map;
1453     }
1454   }
1455
1456   int overlap = 0;
1457   for (uns i=0; i<GARY_SIZE(others); i++)
1458   {
1459     overlap += overlaps(p, others[i]);
1460   }
1461
1462   GARY_FREE(planned);
1463   GARY_FREE(parts);
1464   GARY_FREE(others);
1465
1466   if (dbg_overlaps >= VERBOSITY_PLACEMENT)
1467     printf("Placement of request %d add %d to overlaps\n", p->request->ind, overlap);
1468
1469   return overlap;
1470 }
1471
1472 int individual_overlap(struct individual *individual)
1473 {
1474   int overlap = 0;
1475
1476   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1477   {
1478     overlap += get_overlap(&individual->placements[i]);
1479   }
1480
1481   return overlap;
1482 }
1483
1484 double get_distance(struct placement *p)
1485 {
1486   if (p->variant_used < 0) return 0;
1487   struct variant *v = &p->request->variants[p->variant_used];
1488
1489   double dx, dy, distance;
1490   switch (p->request->type)
1491   {
1492     case REQUEST_POINT: ;
1493       struct request_point *rp = (struct request_point *) p->request;
1494       dx = rp->x + v->offset_x - p->x;
1495       dy = rp->y + v->offset_y - p->y;
1496       distance = sqrt(dx*dx + dy*dy);
1497       if (dbg_rank >= VERBOSITY_PLACEMENT)
1498         printf("Point placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, rp->x, rp->y);
1499       break;
1500     case REQUEST_AREA: ;
1501       struct request_area *ra = (struct request_area *) p->request;
1502       dx = ra->cx + v->offset_x - p->x;
1503       dy = ra->cy + v->offset_y - p->y;
1504       distance = sqrt(dx*dx + dy*dy);
1505       if (dbg_rank >= VERBOSITY_PLACEMENT)
1506         printf("Area placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
1507       break;
1508     default:
1509       return 0;
1510   }
1511
1512   if (dbg_rank >= VERBOSITY_PLACEMENT)
1513     printf("Placement %d has distance %.2f\n", p->ind, distance);
1514   return distance;
1515 }
1516
1517 double individual_distances(struct individual *individual)
1518 {
1519   int distances = 0;
1520
1521   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1522   {
1523     distances += get_distance(&individual->placements[i]);
1524   }
1525
1526   return distances;
1527 }
1528
1529 int cmp_individual(const void *a, const void *b)
1530 {
1531   struct individual **ia = (struct individual **) a;
1532   struct individual **ib = (struct individual **) b;
1533
1534   return (*ia)->penalty - (*ib)->penalty;
1535 }
1536
1537 void rank_population(void)
1538 {
1539   int penalty;
1540
1541   for (int i=0; i<conf_pop_size; i++)
1542   {
1543     if (dbg_rank >= VERBOSITY_INDIVIDUAL)
1544       printf("Individual %d\n", i);
1545     population1[i]->penalty = 0;
1546
1547     penalty = individual_overlap(population1[i]);
1548     if (dbg_rank >= VERBOSITY_INDIVIDUAL)
1549       printf("Increasing penalty by %d for overlap\n", penalty);
1550     population1[i]->penalty += penalty;
1551
1552     penalty = individual_distances(population1[i]);
1553     if (dbg_rank >= VERBOSITY_INDIVIDUAL)
1554       printf("Increasing penalty by %d for distances\n", penalty);
1555     population1[i]->penalty += penalty;
1556   }
1557 }
1558
1559 struct map_part **get_map_parts(struct placement *p)
1560 {
1561   if (p->variant_used < 0) return NULL;
1562
1563   struct map_part **buffer;
1564   GARY_INIT(buffer, 0);
1565
1566   if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1567     printf("Looking for map parts containing placement of request %d, placed at [%.2f; %.2f]\n", p->request->ind, p->x, p->y);
1568
1569   struct variant v;
1570   switch (p->request->type)
1571   {
1572     case REQUEST_POINT:
1573     case REQUEST_SEGMENT:
1574     case REQUEST_AREA:
1575       v = p->request->variants[p->variant_used];
1576       break;
1577     default:
1578       if (dbg_map_parts >= VERBOSITY_ALL)
1579         printf("Skipping unsupported request type (%d)\n", p->request->type);
1580       return NULL;
1581   }
1582
1583   if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1584     printf("Bitmap is %d x %d\n", v.width, v.height);
1585
1586   int x_min = max2(0, p->x) / conf_map_part_width;
1587   // CHECK ME: Is rounding needed?
1588   int x_max = min2(page_width_int, (p->x + v.width)) / conf_map_part_width;
1589   int y_min = max2(0, p->y) / conf_map_part_height;
1590   // CHECK ME: Is rounding needed?
1591   int y_max = min2(page_height_int, (p->y + v.height)) / conf_map_part_height;
1592
1593   if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1594     printf("Cells between [%d; %d] and [%d; %d] generated\n", x_min, y_min, x_max, y_max);
1595
1596   for (int y=y_min; y<=y_max; y++)
1597     for (int x=x_min; x<=x_max; x++)
1598     {
1599       struct map_part **m = GARY_PUSH(buffer);
1600       if (dbg_map_parts >= VERBOSITY_ALL)
1601         printf("Asking for %d of %u\n", y * num_map_parts_row + x, GARY_SIZE(p->individual->map));
1602       *m = p->individual->map[y * num_map_parts_row + x];
1603     }
1604
1605   if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1606     printf("Returning %u map parts potentially containing the symbol\n", GARY_SIZE(buffer));
1607
1608   return buffer;
1609 }
1610
1611 void update_map_parts_delete(struct placement *p)
1612 {
1613   struct map_placement *mp = p->map_links;
1614   while (mp)
1615   {
1616     mp->prev_in_map->next_in_map = mp->next_in_map;
1617     if (mp->next_in_map)
1618       mp->next_in_map->prev_in_map = mp->prev_in_map;
1619
1620     struct map_placement *tmp = mp;
1621     mp = mp->next_in_placement;
1622     free(tmp);
1623   }
1624   p->map_links = NULL;
1625 }
1626
1627 void update_map_parts_create(struct placement *p)
1628 {
1629   struct map_part **parts = get_map_parts(p);
1630   if (parts == NULL) return;
1631
1632   for (uns i=0; i<GARY_SIZE(parts); i++)
1633   {
1634     struct map_placement *mp = malloc(sizeof(struct map_placement));
1635     mp->placement = p;
1636     mp->part = parts[i];
1637
1638     mp->next_in_map = parts[i]->placement->next_in_map;
1639     mp->prev_in_map = parts[i]->placement;
1640     parts[i]->placement->next_in_map = mp;
1641     if (mp->next_in_map) mp->next_in_map->prev_in_map = mp;
1642
1643     mp->next_in_placement = p->map_links;
1644     mp->prev_in_placement = NULL;
1645     p->map_links = mp;
1646   }
1647
1648   GARY_FREE(parts);
1649 }
1650
1651 void update_map_parts(struct placement *p)
1652 {
1653   update_map_parts_delete(p);
1654   update_map_parts_create(p);
1655 }
1656
1657 void gen_coords(struct placement *p)
1658 {
1659   switch(p->request->type)
1660   {
1661     case REQUEST_POINT:
1662       gen_coords_point(p);
1663       break;
1664     case REQUEST_AREA:
1665       gen_coords_area(p);
1666       break;
1667     case REQUEST_SEGMENT:
1668       gen_coords_segment(p);
1669       break;
1670     case REQUEST_LINE:
1671       if (dbg_movement)
1672         printf("Not yet implemented\n");
1673       break;
1674     default:
1675       if (dbg_movement >= VERBOSITY_ALL)
1676         printf("Testing request type\n");
1677       ASSERT(p->request->type != REQUEST_INVALID);
1678   }
1679
1680   update_map_parts(p);
1681 }
1682
1683 double gen_movement(void)
1684 {
1685   double m = (random() % 100000) / 10000;
1686   m = pow(m, 1.0/3) * flip(1, -1);
1687   if (dbg_movement >= VERBOSITY_ALL)
1688     printf("Movement %.2f\n", m);
1689   return m;
1690 }
1691
1692 double gen_movement_uniform(void)
1693 {
1694   return (move_max - move_min) * randdouble() * flip(1, -1);
1695 }
1696
1697 void gen_coords_point(struct placement *p)
1698 {
1699   p->x = p->x + gen_movement();
1700 }
1701
1702 void gen_coords_segment(struct placement *p)
1703 {
1704   struct request_segment *rs = (struct request_segment *) p->request;
1705   int a = flip(1, 2);
1706   p->x = (a == 1 ? rs->x1 : rs->x2);
1707   p->y = (a == 1 ? rs->y1 : rs->y2);
1708 }
1709
1710 void gen_coords_area(struct placement *p)
1711 {
1712   struct request_area *ra = (struct request_area *) p->request;
1713
1714   p->x = p->x + gen_movement();
1715   p->y = p->y + gen_movement();
1716
1717   if (dbg_movement >= VERBOSITY_PLACEMENT)
1718     printf("Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
1719 }
1720
1721 int randint(int min, int max)
1722 {
1723   if (min == max) return min;
1724   int r = random();
1725   return min + (r % (max - min));
1726 }
1727
1728 struct placement **get_closure(struct placement *placement)
1729 {
1730   struct placement **closure;
1731   GARY_INIT(closure, 0);
1732   bool *chosen = malloc(GARY_SIZE(placement->individual->placements) * sizeof(bool));
1733   for (uns i=0; i<GARY_SIZE(placement->individual->placements); i++) { chosen[i] = 0; }
1734   chosen[placement->request->ind] = 1;
1735
1736   struct placement **p = GARY_PUSH(closure); *p = placement;
1737
1738   uns first = 0;
1739   while (first < GARY_SIZE(closure))
1740   {
1741     if (dbg_breeding >= VERBOSITY_ALL)
1742       printf("Iterating, first is %d of current %u\n", first, GARY_SIZE(closure));
1743     struct placement **overlapping = get_overlapping(placement);
1744     if (! overlapping) { first++; continue; }
1745
1746     struct placement **filtered = filter(overlapping, &chosen);
1747     if (dbg_breeding >= VERBOSITY_ALL)
1748       printf("There are %u new overlapping symbols\n", GARY_SIZE(filtered));
1749     GARY_FREE(overlapping);
1750     overlapping = filtered;
1751     for (uns j=0; j<GARY_SIZE(overlapping); j++)
1752     {
1753       if (! chosen[overlapping[j]->request->ind])
1754       {
1755         if (overlaps(*p, overlapping[j]))
1756         {
1757           p = GARY_PUSH(closure); *p = overlapping[j];
1758           if (dbg_breeding >= VERBOSITY_ALL)
1759             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);
1760           chosen[overlapping[j]->request->ind] = 1;
1761         }
1762       }
1763     }
1764     GARY_FREE(overlapping);
1765     first++;
1766   }
1767
1768   free(chosen);
1769
1770   return closure;
1771 }
1772
1773 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child, bool **processed_ptr)
1774 {
1775   bool *processed = *processed_ptr;
1776   if (dbg_breeding >= VERBOSITY_ALL)
1777     printf("Will copy %u symbols\n", GARY_SIZE(closure));
1778
1779   for (uns i=0; i<GARY_SIZE(closure); i++)
1780   {
1781     processed[closure[i]->ind] = 1;
1782     int ind = closure[i]->ind;
1783     child->placements[ind] = parent->placements[ind];
1784     child->placements[ind].individual = child;
1785     child->placements[ind].processed = 0;
1786     child->placements[ind].map_links = NULL;
1787     update_map_parts(&child->placements[ind]);
1788   }
1789 }
1790
1791 void move_symbol(struct placement *p)
1792 {
1793   switch (p->request->type)
1794   {
1795     case REQUEST_POINT:
1796     case REQUEST_AREA:
1797       move_symbol_point(p);
1798       break;
1799     case REQUEST_SEGMENT:
1800       move_symbol_segment(p);
1801       break;
1802     default:
1803       ASSERT(p->request->type != REQUEST_INVALID);
1804   }
1805 }
1806
1807 void move_symbol_point(struct placement *p)
1808 {
1809   p->x += gen_movement_uniform();
1810   p->y += gen_movement_uniform();
1811 }
1812
1813 void move_symbol_segment(struct placement *p)
1814 {
1815   double m = gen_movement_uniform();
1816   // CHECK ME
1817   p->x += m;
1818   p->y += m * ((struct request_segment *) p->request)->slope;
1819 }
1820
1821 void hide_segment_labels(struct individual *individual)
1822 {
1823   // BEWARE: This fully depends on current genetic encoding
1824
1825   int used = -1, num = -1;
1826   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1827   {
1828     switch (individual->placements[i].request->type)
1829     {
1830       case REQUEST_SECTION:
1831         used = individual->placements[i].variant_used;
1832         num = 0;
1833         break;
1834       case REQUEST_SEGMENT:
1835         if (num == used)
1836           individual->placements[i].variant_used = 0;
1837         else
1838           individual->placements[i].variant_used = -1;
1839         num++;
1840         break;
1841       default:
1842         ;
1843     }
1844   }
1845 }
1846
1847 void init_placement(struct placement *p, struct individual *individual, struct request *r)
1848 {
1849   p->ind = num_placements++;
1850   p->request = r;
1851   p->processed = 0;
1852   p->x = p->y = 0; // To prevent valgrind from complaining
1853   p->variant_used = 0;
1854   p->map_links = NULL;
1855   p->individual = individual;
1856   switch (r->type)
1857   {
1858     case REQUEST_POINT: ;
1859       struct request_point *rp = (struct request_point *) r;
1860       p->x = rp->x;
1861       p->y = rp->y;
1862       break;
1863     case REQUEST_LINE: ;
1864       break;
1865     case REQUEST_SECTION: ;
1866       struct request_section *rls = (struct request_section *) r;
1867       p->variant_used = randint(0, rls->num_segments);
1868       break;
1869     case REQUEST_SEGMENT: ;
1870       struct request_segment *rs = (struct request_segment *) r;
1871       p->x = rs->x2;
1872       p->y = rs->y2;
1873       break;
1874     case REQUEST_AREA: ;
1875       struct request_area *ra = (struct request_area *) r;
1876       p->x = ra->cx;
1877       p->y = ra->cy;
1878       p->variant_used = 0;
1879       break;
1880     default:
1881       ASSERT(p->request->type != REQUEST_INVALID);
1882   }
1883
1884   gen_coords(p);
1885   if (dbg_init >= VERBOSITY_PLACEMENT)
1886     printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y);
1887 }
1888
1889 void reset_individual_map(struct individual *i)
1890 {
1891   for (uns j=0; j<num_map_parts; j++)
1892   {
1893     struct map_placement *mp = i->map[j]->placement;
1894     while (mp)
1895     {
1896       struct map_placement *tmp = mp;
1897       mp = mp->next_in_map;
1898       free(tmp);
1899     }
1900
1901     free(i->map[j]);
1902     struct map_part *part = malloc(sizeof(struct map_part));
1903     part->ind = j;
1904
1905     mp = malloc(sizeof(struct map_placement));
1906     part->placement = mp;
1907     mp->placement = &dummy_placement;
1908     mp->next_in_map = mp->prev_in_map = NULL;
1909     mp->next_in_placement = mp->prev_in_placement = NULL;
1910     i->map[j] = part;
1911   }
1912 }
1913
1914 void update_individual(struct individual *individual)
1915 {
1916   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1917   {
1918     update_map_parts_delete(&individual->placements[i]);
1919   }
1920 }
1921
1922 void clear_individual(struct individual *individual)
1923 {
1924   for (uns j=0; j<num_map_parts; j++)
1925   {
1926     struct map_placement *mp = individual->map[j]->placement;
1927     while (mp)
1928     {
1929       struct map_placement *tmp = mp;
1930       mp = mp->next_in_map;
1931       free(tmp);
1932     }
1933
1934     free(individual->map[j]);
1935   }
1936
1937   GARY_FREE(individual->map);
1938   GARY_FREE(individual->placements);
1939   ep_free(ep_individuals, individual);
1940 }
1941
1942 void clear_population(struct individual **pop)
1943 {
1944   for (uns i=0; i<GARY_SIZE(pop); i++)
1945   {
1946     clear_individual(pop[i]);
1947   }
1948 }
1949
1950 struct placement **get_overlapping(struct placement *p)
1951 {
1952   struct placement **buffer;
1953   GARY_INIT(buffer, 0);
1954
1955   struct map_part **parts = get_map_parts(p);
1956   if (! parts) return NULL;
1957
1958   for (uns i=0; i<GARY_SIZE(parts); i++)
1959   {
1960     struct map_placement *mp = parts[i]->placement->next_in_map;
1961     while (mp)
1962     {
1963       if (p->variant_used >= 0)
1964       {
1965         struct placement **p = GARY_PUSH(buffer);
1966         *p = mp->placement;
1967       }
1968       mp = mp->next_in_map;
1969     }
1970   }
1971   GARY_FREE(parts);
1972
1973   if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1974     printf("Returning %u potentially overlapping placements\n", GARY_SIZE(buffer));
1975
1976   return buffer;
1977 }
1978
1979 struct placement **filter(struct placement **list, bool **pred_ptr)
1980 {
1981   bool *pred = *pred_ptr; // As GARY can't be passed directly
1982   struct placement **filtered;
1983   GARY_INIT(filtered, 0);
1984
1985   for (uns i=0; i<GARY_SIZE(list); i++)
1986   {
1987     if (pred[list[i]->request->ind])
1988       continue;
1989
1990     struct placement **p = GARY_PUSH(filtered);
1991     *p = list[i];
1992   }
1993
1994   return filtered;
1995 }
1996
1997 int flip(int a, int b)
1998 {
1999   return (random() % 2 ? a : b);
2000 }
2001
2002 double randdouble(void)
2003 {
2004   return ((double) rand() / (double) RAND_MAX);
2005 }
2006
2007 void init_individual(struct individual *individual)
2008 {
2009   GARY_INIT(individual->placements, num_requests);
2010   GARY_INIT(individual->map, 0);
2011   for (uns j=0; j<num_map_parts; j++)
2012   {
2013     GARY_PUSH(individual->map);
2014     struct map_part *part = malloc(sizeof(struct map_part));
2015     struct map_placement *mp = malloc(sizeof(struct map_placement));
2016     part->placement = mp;
2017     part->ind = j;
2018     mp->placement = &dummy_placement;
2019     mp->next_in_map = mp->prev_in_map = NULL;
2020     mp->next_in_placement = mp->prev_in_placement = NULL;
2021     individual->map[j] = part;
2022   }
2023   individual->penalty = 0;
2024 }
2025
2026 void copy_individual(struct individual *src, struct individual *dest)
2027 {
2028   init_individual(dest);
2029   dest->penalty = src->penalty;
2030
2031   for (uns i=0; i<GARY_SIZE(src->placements); i++)
2032   {
2033     dest->placements[i] = src->placements[i];
2034     dest->placements[i].map_links = NULL;
2035     dest->placements[i].individual = dest;
2036
2037     update_map_parts_create(&dest->placements[i]);
2038   }
2039 }