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