labeller.c

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