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   if (p->variant_used == -1) return 0;
1427
1428   struct map_part **parts = get_map_parts(p);
1429   if (! parts)
1430   {
1431     if (dbg_overlaps >= VERBOSITY_PLACEMENT)
1432       printf("Placement of request %d seems not to be placed\n", p->request->ind);
1433     return 0;
1434   }
1435
1436   struct placement **others;
1437   bool *planned;
1438
1439   GARY_INIT_ZERO(planned, num_requests);
1440   planned[p->request->ind] = 1;
1441   GARY_INIT(others, 0);
1442
1443   for (uns i=0; i<GARY_SIZE(parts); i++)
1444   {
1445     struct map_placement *mp = parts[i]->placement->next_in_map;
1446     while (mp)
1447     {
1448       if (! planned[mp->placement->request->ind])
1449       {
1450         struct placement **p = GARY_PUSH(others);
1451         *p = mp->placement;
1452         planned[mp->placement->request->ind] = true;
1453       }
1454       mp = mp->next_in_map;
1455     }
1456   }
1457
1458   int overlap = 0;
1459   for (uns i=0; i<GARY_SIZE(others); i++)
1460   {
1461     overlap += overlaps(p, others[i]);
1462   }
1463
1464   GARY_FREE(planned);
1465   GARY_FREE(parts);
1466   GARY_FREE(others);
1467
1468   if (dbg_overlaps >= VERBOSITY_PLACEMENT)
1469     printf("Placement of request %d add %d to overlaps\n", p->request->ind, overlap);
1470
1471   if (p->x < 0) overlap += 0 - p->x;
1472   if (p->x + p->request->variants[p->variant_used].width > page_width_int)
1473     overlap += p->x + p->request->variants[p->variant_used].width - page_width_int;
1474
1475   if (p->y < 0) overlap += 0 - p->y;
1476   if (p->y + p->request->variants[p->variant_used].height > page_height_int)
1477     overlap += p->y + p->request->variants[p->variant_used].height - page_height_int;
1478
1479   return overlap;
1480 }
1481
1482 int individual_overlap(struct individual *individual)
1483 {
1484   int overlap = 0;
1485
1486   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1487   {
1488     overlap += get_overlap(&individual->placements[i]);
1489   }
1490
1491   return overlap;
1492 }
1493
1494 double get_distance(struct placement *p)
1495 {
1496   if (p->variant_used < 0) return 0;
1497   struct variant *v = &p->request->variants[p->variant_used];
1498
1499   double dx, dy, distance;
1500   switch (p->request->type)
1501   {
1502     case REQUEST_POINT: ;
1503       struct request_point *rp = (struct request_point *) p->request;
1504       dx = rp->x + v->offset_x - p->x;
1505       dy = rp->y + v->offset_y - p->y;
1506       distance = sqrt(dx*dx + dy*dy);
1507       if (dbg_rank >= VERBOSITY_PLACEMENT)
1508         printf("Point placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, rp->x, rp->y);
1509       break;
1510     case REQUEST_AREA: ;
1511       struct request_area *ra = (struct request_area *) p->request;
1512       dx = ra->cx + v->offset_x - p->x;
1513       dy = ra->cy + v->offset_y - p->y;
1514       distance = sqrt(dx*dx + dy*dy);
1515       if (dbg_rank >= VERBOSITY_PLACEMENT)
1516         printf("Area placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
1517       break;
1518     default:
1519       return 0;
1520   }
1521
1522   if (dbg_rank >= VERBOSITY_PLACEMENT)
1523     printf("Placement %d has distance %.2f\n", p->ind, distance);
1524   return distance;
1525 }
1526
1527 double individual_distances(struct individual *individual)
1528 {
1529   int distances = 0;
1530
1531   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1532   {
1533     distances += get_distance(&individual->placements[i]);
1534   }
1535
1536   return distances;
1537 }
1538
1539 int cmp_individual(const void *a, const void *b)
1540 {
1541   struct individual **ia = (struct individual **) a;
1542   struct individual **ib = (struct individual **) b;
1543
1544   return (*ia)->penalty - (*ib)->penalty;
1545 }
1546
1547 void rank_population(void)
1548 {
1549   int penalty;
1550
1551   for (int i=0; i<conf_pop_size; i++)
1552   {
1553     if (dbg_rank >= VERBOSITY_INDIVIDUAL)
1554       printf("Individual %d\n", i);
1555     population1[i]->penalty = 0;
1556
1557     penalty = individual_overlap(population1[i]);
1558     if (dbg_rank >= VERBOSITY_INDIVIDUAL)
1559       printf("Increasing penalty by %d for overlap\n", penalty);
1560     population1[i]->penalty += penalty;
1561
1562     penalty = individual_distances(population1[i]);
1563     if (dbg_rank >= VERBOSITY_INDIVIDUAL)
1564       printf("Increasing penalty by %d for distances\n", penalty);
1565     population1[i]->penalty += penalty;
1566   }
1567 }
1568
1569 struct map_part **get_map_parts(struct placement *p)
1570 {
1571   if (p->variant_used < 0) return NULL;
1572
1573   struct map_part **buffer;
1574   GARY_INIT(buffer, 0);
1575
1576   if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1577     printf("Looking for map parts containing placement of request %d, placed at [%.2f; %.2f]\n", p->request->ind, p->x, p->y);
1578
1579   struct variant v;
1580   switch (p->request->type)
1581   {
1582     case REQUEST_POINT:
1583     case REQUEST_SEGMENT:
1584     case REQUEST_AREA:
1585       v = p->request->variants[p->variant_used];
1586       break;
1587     default:
1588       if (dbg_map_parts >= VERBOSITY_ALL)
1589         printf("Skipping unsupported request type (%d)\n", p->request->type);
1590       return NULL;
1591   }
1592
1593   if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1594     printf("Bitmap is %d x %d\n", v.width, v.height);
1595
1596   int x_min = max2(0, p->x) / conf_map_part_width;
1597   // CHECK ME: Is rounding needed?
1598   int x_max = min2(page_width_int, (p->x + v.width)) / conf_map_part_width;
1599   int y_min = max2(0, p->y) / conf_map_part_height;
1600   // CHECK ME: Is rounding needed?
1601   int y_max = min2(page_height_int, (p->y + v.height)) / conf_map_part_height;
1602
1603   if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1604     printf("Cells between [%d; %d] and [%d; %d] generated\n", x_min, y_min, x_max, y_max);
1605
1606   for (int y=y_min; y<=y_max; y++)
1607     for (int x=x_min; x<=x_max; x++)
1608     {
1609       struct map_part **m = GARY_PUSH(buffer);
1610       if (dbg_map_parts >= VERBOSITY_ALL)
1611         printf("Asking for %d of %u\n", y * num_map_parts_row + x, GARY_SIZE(p->individual->map));
1612       *m = p->individual->map[y * num_map_parts_row + x];
1613     }
1614
1615   if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1616     printf("Returning %u map parts potentially containing the symbol\n", GARY_SIZE(buffer));
1617
1618   return buffer;
1619 }
1620
1621 void update_map_parts_delete(struct placement *p)
1622 {
1623   struct map_placement *mp = p->map_links;
1624   while (mp)
1625   {
1626     mp->prev_in_map->next_in_map = mp->next_in_map;
1627     if (mp->next_in_map)
1628       mp->next_in_map->prev_in_map = mp->prev_in_map;
1629
1630     struct map_placement *tmp = mp;
1631     mp = mp->next_in_placement;
1632     free(tmp);
1633   }
1634   p->map_links = NULL;
1635 }
1636
1637 void update_map_parts_create(struct placement *p)
1638 {
1639   struct map_part **parts = get_map_parts(p);
1640   if (parts == NULL) return;
1641
1642   for (uns i=0; i<GARY_SIZE(parts); i++)
1643   {
1644     struct map_placement *mp = malloc(sizeof(struct map_placement));
1645     mp->placement = p;
1646     mp->part = parts[i];
1647
1648     mp->next_in_map = parts[i]->placement->next_in_map;
1649     mp->prev_in_map = parts[i]->placement;
1650     parts[i]->placement->next_in_map = mp;
1651     if (mp->next_in_map) mp->next_in_map->prev_in_map = mp;
1652
1653     mp->next_in_placement = p->map_links;
1654     mp->prev_in_placement = NULL;
1655     p->map_links = mp;
1656   }
1657
1658   GARY_FREE(parts);
1659 }
1660
1661 void update_map_parts(struct placement *p)
1662 {
1663   update_map_parts_delete(p);
1664   update_map_parts_create(p);
1665 }
1666
1667 void gen_coords(struct placement *p)
1668 {
1669   switch(p->request->type)
1670   {
1671     case REQUEST_POINT:
1672       gen_coords_point(p);
1673       break;
1674     case REQUEST_AREA:
1675       gen_coords_area(p);
1676       break;
1677     case REQUEST_SEGMENT:
1678       gen_coords_segment(p);
1679       break;
1680     case REQUEST_LINE:
1681       if (dbg_movement)
1682         printf("Not yet implemented\n");
1683       break;
1684     default:
1685       if (dbg_movement >= VERBOSITY_ALL)
1686         printf("Testing request type\n");
1687       ASSERT(p->request->type != REQUEST_INVALID);
1688   }
1689
1690   update_map_parts(p);
1691 }
1692
1693 double gen_movement(void)
1694 {
1695   double m = (random() % 100000) / 10000;
1696   m = pow(m, 1.0/3) * flip(1, -1);
1697   if (dbg_movement >= VERBOSITY_ALL)
1698     printf("Movement %.2f\n", m);
1699   return m;
1700 }
1701
1702 double gen_movement_uniform(void)
1703 {
1704   return (move_max - move_min) * randdouble() * flip(1, -1);
1705 }
1706
1707 void gen_coords_point(struct placement *p)
1708 {
1709   p->x = p->x + gen_movement();
1710 }
1711
1712 void gen_coords_segment(struct placement *p)
1713 {
1714   struct request_segment *rs = (struct request_segment *) p->request;
1715   int a = flip(1, 2);
1716   p->x = (a == 1 ? rs->x1 : rs->x2);
1717   p->y = (a == 1 ? rs->y1 : rs->y2);
1718 }
1719
1720 void gen_coords_area(struct placement *p)
1721 {
1722   struct request_area *ra = (struct request_area *) p->request;
1723
1724   p->x = p->x + gen_movement();
1725   p->y = p->y + gen_movement();
1726
1727   if (dbg_movement >= VERBOSITY_PLACEMENT)
1728     printf("Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
1729 }
1730
1731 int randint(int min, int max)
1732 {
1733   if (min == max) return min;
1734   int r = random();
1735   return min + (r % (max - min));
1736 }
1737
1738 struct placement **get_closure(struct placement *placement)
1739 {
1740   struct placement **closure;
1741   GARY_INIT(closure, 0);
1742   bool *chosen = malloc(GARY_SIZE(placement->individual->placements) * sizeof(bool));
1743   for (uns i=0; i<GARY_SIZE(placement->individual->placements); i++) { chosen[i] = 0; }
1744   chosen[placement->request->ind] = 1;
1745
1746   struct placement **p = GARY_PUSH(closure); *p = placement;
1747
1748   uns first = 0;
1749   while (first < GARY_SIZE(closure))
1750   {
1751     if (dbg_breeding >= VERBOSITY_ALL)
1752       printf("Iterating, first is %d of current %u\n", first, GARY_SIZE(closure));
1753     struct placement **overlapping = get_overlapping(placement);
1754     if (! overlapping) { first++; continue; }
1755
1756     struct placement **filtered = filter(overlapping, &chosen);
1757     if (dbg_breeding >= VERBOSITY_ALL)
1758       printf("There are %u new overlapping symbols\n", GARY_SIZE(filtered));
1759     GARY_FREE(overlapping);
1760     overlapping = filtered;
1761     for (uns j=0; j<GARY_SIZE(overlapping); j++)
1762     {
1763       if (! chosen[overlapping[j]->request->ind])
1764       {
1765         if (overlaps(*p, overlapping[j]))
1766         {
1767           p = GARY_PUSH(closure); *p = overlapping[j];
1768           if (dbg_breeding >= VERBOSITY_ALL)
1769             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);
1770           chosen[overlapping[j]->request->ind] = 1;
1771         }
1772       }
1773     }
1774     GARY_FREE(overlapping);
1775     first++;
1776   }
1777
1778   free(chosen);
1779
1780   return closure;
1781 }
1782
1783 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child, bool **processed_ptr)
1784 {
1785   bool *processed = *processed_ptr;
1786   if (dbg_breeding >= VERBOSITY_ALL)
1787     printf("Will copy %u symbols\n", GARY_SIZE(closure));
1788
1789   for (uns i=0; i<GARY_SIZE(closure); i++)
1790   {
1791     processed[closure[i]->ind] = 1;
1792     int ind = closure[i]->ind;
1793     child->placements[ind] = parent->placements[ind];
1794     child->placements[ind].individual = child;
1795     child->placements[ind].processed = 0;
1796     child->placements[ind].map_links = NULL;
1797     update_map_parts(&child->placements[ind]);
1798   }
1799 }
1800
1801 void move_symbol(struct placement *p)
1802 {
1803   switch (p->request->type)
1804   {
1805     case REQUEST_POINT:
1806     case REQUEST_AREA:
1807       move_symbol_point(p);
1808       break;
1809     case REQUEST_SEGMENT:
1810       move_symbol_segment(p);
1811       break;
1812     default:
1813       ASSERT(p->request->type != REQUEST_INVALID);
1814   }
1815 }
1816
1817 void move_symbol_point(struct placement *p)
1818 {
1819   p->x += gen_movement_uniform();
1820   p->y += gen_movement_uniform();
1821 }
1822
1823 void move_symbol_segment(struct placement *p)
1824 {
1825   double m = gen_movement_uniform();
1826   // CHECK ME
1827   p->x += m;
1828   p->y += m * ((struct request_segment *) p->request)->slope;
1829 }
1830
1831 void hide_segment_labels(struct individual *individual)
1832 {
1833   // BEWARE: This fully depends on current genetic encoding
1834
1835   int used = -1, num = -1;
1836   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1837   {
1838     switch (individual->placements[i].request->type)
1839     {
1840       case REQUEST_SECTION:
1841         used = individual->placements[i].variant_used;
1842         num = 0;
1843         break;
1844       case REQUEST_SEGMENT:
1845         if (num == used)
1846           individual->placements[i].variant_used = 0;
1847         else
1848           individual->placements[i].variant_used = -1;
1849         num++;
1850         break;
1851       default:
1852         ;
1853     }
1854   }
1855 }
1856
1857 void init_placement(struct placement *p, struct individual *individual, struct request *r)
1858 {
1859   p->ind = num_placements++;
1860   p->request = r;
1861   p->processed = 0;
1862   p->x = p->y = 0; // To prevent valgrind from complaining
1863   p->variant_used = 0;
1864   p->map_links = NULL;
1865   p->individual = individual;
1866   switch (r->type)
1867   {
1868     case REQUEST_POINT: ;
1869       struct request_point *rp = (struct request_point *) r;
1870       p->x = rp->x;
1871       p->y = rp->y;
1872       break;
1873     case REQUEST_LINE: ;
1874       break;
1875     case REQUEST_SECTION: ;
1876       struct request_section *rls = (struct request_section *) r;
1877       p->variant_used = randint(0, rls->num_segments);
1878       break;
1879     case REQUEST_SEGMENT: ;
1880       struct request_segment *rs = (struct request_segment *) r;
1881       p->x = rs->x2;
1882       p->y = rs->y2;
1883       break;
1884     case REQUEST_AREA: ;
1885       struct request_area *ra = (struct request_area *) r;
1886       p->x = ra->cx;
1887       p->y = ra->cy;
1888       p->variant_used = 0;
1889       break;
1890     default:
1891       ASSERT(p->request->type != REQUEST_INVALID);
1892   }
1893
1894   gen_coords(p);
1895   if (dbg_init >= VERBOSITY_PLACEMENT)
1896     printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y);
1897 }
1898
1899 void reset_individual_map(struct individual *i)
1900 {
1901   for (uns j=0; j<num_map_parts; j++)
1902   {
1903     struct map_placement *mp = i->map[j]->placement;
1904     while (mp)
1905     {
1906       struct map_placement *tmp = mp;
1907       mp = mp->next_in_map;
1908       free(tmp);
1909     }
1910
1911     free(i->map[j]);
1912     struct map_part *part = malloc(sizeof(struct map_part));
1913     part->ind = j;
1914
1915     mp = malloc(sizeof(struct map_placement));
1916     part->placement = mp;
1917     mp->placement = &dummy_placement;
1918     mp->next_in_map = mp->prev_in_map = NULL;
1919     mp->next_in_placement = mp->prev_in_placement = NULL;
1920     i->map[j] = part;
1921   }
1922 }
1923
1924 void update_individual(struct individual *individual)
1925 {
1926   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1927   {
1928     update_map_parts_delete(&individual->placements[i]);
1929   }
1930 }
1931
1932 void clear_individual(struct individual *individual)
1933 {
1934   for (uns j=0; j<num_map_parts; j++)
1935   {
1936     struct map_placement *mp = individual->map[j]->placement;
1937     while (mp)
1938     {
1939       struct map_placement *tmp = mp;
1940       mp = mp->next_in_map;
1941       free(tmp);
1942     }
1943
1944     free(individual->map[j]);
1945   }
1946
1947   GARY_FREE(individual->map);
1948   GARY_FREE(individual->placements);
1949   ep_free(ep_individuals, individual);
1950 }
1951
1952 void clear_population(struct individual **pop)
1953 {
1954   for (uns i=0; i<GARY_SIZE(pop); i++)
1955   {
1956     clear_individual(pop[i]);
1957   }
1958 }
1959
1960 struct placement **get_overlapping(struct placement *p)
1961 {
1962   struct placement **buffer;
1963   GARY_INIT(buffer, 0);
1964
1965   struct map_part **parts = get_map_parts(p);
1966   if (! parts) return NULL;
1967
1968   for (uns i=0; i<GARY_SIZE(parts); i++)
1969   {
1970     struct map_placement *mp = parts[i]->placement->next_in_map;
1971     while (mp)
1972     {
1973       if (p->variant_used >= 0)
1974       {
1975         struct placement **p = GARY_PUSH(buffer);
1976         *p = mp->placement;
1977       }
1978       mp = mp->next_in_map;
1979     }
1980   }
1981   GARY_FREE(parts);
1982
1983   if (dbg_map_parts >= VERBOSITY_PLACEMENT)
1984     printf("Returning %u potentially overlapping placements\n", GARY_SIZE(buffer));
1985
1986   return buffer;
1987 }
1988
1989 struct placement **filter(struct placement **list, bool **pred_ptr)
1990 {
1991   bool *pred = *pred_ptr; // As GARY can't be passed directly
1992   struct placement **filtered;
1993   GARY_INIT(filtered, 0);
1994
1995   for (uns i=0; i<GARY_SIZE(list); i++)
1996   {
1997     if (pred[list[i]->request->ind])
1998       continue;
1999
2000     struct placement **p = GARY_PUSH(filtered);
2001     *p = list[i];
2002   }
2003
2004   return filtered;
2005 }
2006
2007 int flip(int a, int b)
2008 {
2009   return (random() % 2 ? a : b);
2010 }
2011
2012 double randdouble(void)
2013 {
2014   return ((double) rand() / (double) RAND_MAX);
2015 }
2016
2017 void init_individual(struct individual *individual)
2018 {
2019   GARY_INIT(individual->placements, num_requests);
2020   GARY_INIT(individual->map, 0);
2021   for (uns j=0; j<num_map_parts; j++)
2022   {
2023     GARY_PUSH(individual->map);
2024     struct map_part *part = malloc(sizeof(struct map_part));
2025     struct map_placement *mp = malloc(sizeof(struct map_placement));
2026     part->placement = mp;
2027     part->ind = j;
2028     mp->placement = &dummy_placement;
2029     mp->next_in_map = mp->prev_in_map = NULL;
2030     mp->next_in_placement = mp->prev_in_placement = NULL;
2031     individual->map[j] = part;
2032   }
2033   individual->penalty = 0;
2034 }
2035
2036 void copy_individual(struct individual *src, struct individual *dest)
2037 {
2038   init_individual(dest);
2039   dest->penalty = src->penalty;
2040
2041   for (uns i=0; i<GARY_SIZE(src->placements); i++)
2042   {
2043     dest->placements[i] = src->placements[i];
2044     dest->placements[i].map_links = NULL;
2045     dest->placements[i].individual = dest;
2046
2047     update_map_parts_create(&dest->placements[i]);
2048   }
2049 }