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 = 0;
  45 int dbg_plan = 0;
  46 int dbg_requests = 0;
  47 int dbg_graph = 0;
  48 int dbg_bfs = 0;
  49 int dbg_map_parts = 0;
  50 int dbg_movement = 0;
  51 int dbg_init = 0;
  52
  53 int page_width_int;
  54 int page_height_int;
  55
  56 int num_edges_dbg;
  57 int num_nodes;
  58 int num_edges = 0;
  59 int dbg_num_hits = 0;
  60
  61 int conf_pop_size = 50;
  62
  63 int conf_penalty_bound = 0;
  64 int conf_stagnation_bound = 0;
  65 int conf_iteration_limit = 4;
  66
  67 int conf_term_cond = TERM_COND_ITERATIONS;
  68
  69 int conf_breed_rbest_perc = 80;
  70 int conf_breed_pop_size_perc = 20;
  71 int conf_breed_perc = 50;                       // Percentage of new pop created by breeding
  72
  73 bool conf_mutate_children = 1;
  74 int conf_mutate_children_prob = 0.3;
  75
  76 int conf_mutate_rbest_perc = 60;
  77 int conf_mutate_pop_size_perc = 20;
  78
  79 int conf_mutate_move_bound = 0.2;
  80 int conf_mutate_regen_bound = 0.1;
  81 int conf_mutate_chvar_bound = 0.1;
  82
  83 int conf_elite_perc = 5;
  84
  85 double conf_max_section_length = 100;
  86 double conf_max_section_overlay = 10;
  87
  88 int old_best = 0; // FIXME: Shall be int max
  89 int iteration = 0;
  90 int pop2_ind;
  91
  92 int conf_part_size = 50;
  93
  94 int move_min = 0;
  95 int move_max = 1;
  96
  97 int num_requests = 0;
  98
  99 int conf_map_part_width = 5;
 100 int conf_map_part_height = 5;
 101 int num_map_parts_row;
 102 int num_map_parts_col;
 103 int num_map_parts;
 104
 105 void make_graph(void);
 106 void label_graph(void);
 107 void join_edge(struct graph_edge *e, int dir);
 108 void bfs(uns longline);
 109 void make_segments(void);
 110
 111 void make_population(void);
 112 bool shall_terminate(void);
 113 void breed(void);
 114 void mutate(void);
 115 void elite(void);
 116 void rank_population(void);
 117 void plan_individual(struct individual *individual);
 118
 119 void make_bitmap(struct variant *v, struct symbol *sym);
 120 void make_bitmap_icon(struct variant *v, struct sym_icon *si);
 121 void make_bitmap_point(struct variant *v, struct sym_point *sp);
 122 void make_bitmap_label(struct variant *v, struct sym_text *text);
 123
 124 void cut_edge(struct graph_edge *e, double dist);
 125 struct request_line *make_new_line(void);
 126 struct request_section *make_new_section(struct request_line *rl);
 127 struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym);
 128
 129 void dump_bitmaps(struct individual *individual);
 130 void dump_graph(void);
 131 void bfs2(void);
 132 void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir);
 133 void bfs_wrapper(void);
 134 void oldbfs(void);
 135 void dump_longlines(void);
 136 void dump_linelabel_requests(void);
 137 void dump_individual(struct individual *individual);
 138 void print_label(struct symbol *sym);
 139
 140 double gen_movement(void);
 141 void gen_coords(struct placement *p);
 142 void gen_coords_point(struct placement *p);
 143 void gen_coords_segment(struct placement *p);
 144 void gen_coords_area(struct placement *p);
 145
 146 struct map_part **get_map_parts(struct placement *p);
 147 void update_map_parts(struct placement *p);
 148
 149 void make_segments_old(void);
 150
 151 void labeller_cleanup(void);
 152
 153 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2);
 154 void perform_mutation(struct individual *individual);
 155
 156 void hide_segment_labels(struct individual *individual);
 157 void init_placement(struct placement *p, struct individual *individual, struct request *r);
 158 void init_individual(struct individual *i);
 159 struct map_part **get_parts(struct placement *symbol, struct individual *individual);
 160
 161 int randint(int min, int max);
 162
 163 struct placement **get_closure(struct placement *placement, struct individual *parent1, struct individual *parent2);
 164 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child);
 165 void move_symbol(struct placement *p);
 166 void move_symbol_point(struct placement *p);
 167
 168 struct placement **get_overlapping(struct placement *p);
 169 void filter(struct placement **list, bool *pred);
 170
 171 int flip(int a, int b);
 172 double randdouble(void);
 173
 174 void cleanup(void);
 175
 176 void copy_individual(struct individual *src, struct individual *dest);
 177
 178 int max2(int a, int b);
 179 int min2(int a, int b);
 180 int max4(int a, int b, int c, int d);
 181 int min4(int a, int b, int c, int d);
 182
 183 struct placement dummy_placement;
 184
 185 int max2(int a, int b)
 186 {
 187   return (a > b ? a : b);
 188 }
 189
 190 int min2(int a, int b)
 191 {
 192   return (a < b ? a : b);
 193 }
 194
 195 int max4(int a, int b, int c, int d)
 196 {
 197   return max2(max2(a, b), max2(c, d));
 198 }
 199
 200 int min4(int a, int b, int c, int d)
 201 {
 202   return min2(min2(a, b), min2(c, d));
 203 }
 204
 205 void print_label(struct symbol *sym)
 206 {
 207   switch (sym->type)
 208   {
 209     case SYMBOLIZER_TEXT: ;
 210       struct sym_text *st = (struct sym_text *) sym;
 211       printf("%s\n", osm_val_decode(st->text));
 212     default:
 213       // FIXME
 214       ;
 215   }
 216 }
 217
 218 void labeller_init(void)
 219 {
 220   GARY_INIT(requests_point, 0);
 221   GARY_INIT(requests_line, 0);
 222   GARY_INIT(requests_area, 0);
 223   GARY_INIT(buffer_line, 0);
 224   GARY_INIT(buffer_linelabel, 0);
 225   ep_individuals = ep_new(sizeof(struct individual), 1);
 226
 227   page_width_int = floor(page_width);
 228   page_height_int = floor(page_height);
 229
 230   num_map_parts_row = (page_width_int + conf_map_part_width) / conf_map_part_width;
 231   num_map_parts_col = (page_height_int + conf_map_part_height) / conf_map_part_height;
 232   num_map_parts = num_map_parts_row * num_map_parts_col;
 233 }
 234
 235 void make_bitmap(struct variant *v, struct symbol *sym)
 236 {
 237   switch (sym->type)
 238   {
 239     case SYMBOLIZER_POINT:
 240       make_bitmap_point(v, (struct sym_point *) sym);
 241       break;
 242     case SYMBOLIZER_ICON:
 243       make_bitmap_icon(v, (struct sym_icon *) sym);
 244       break;
 245     case SYMBOLIZER_TEXT:
 246       make_bitmap_label(v, (struct sym_text *) sym);
 247       break;
 248     default:
 249       ASSERT(sym->type != SYMBOLIZER_INVALID);
 250   }
 251 }
 252
 253 void make_bitmap_icon(struct variant *v, struct sym_icon *si)
 254 {
 255   v->width = si->sir.width + 1;
 256   v->height = si->sir.height + 1;
 257   v->bitmap = malloc(v->width * v->height * sizeof(bool));
 258   for (int i=0; i<v->width*v->height; i++) v->bitmap[i] = 1;
 259 }
 260
 261 void make_bitmap_point(struct variant *v, struct sym_point *sp)
 262 {
 263   v->width = v->height = sp->size + 1;
 264   v->bitmap = malloc(v->width * v->height * sizeof(bool));
 265   // FIXME: Okay, memset would be much nicer here
 266   for (int i=0; i<sp->size*sp->size; i++) v->bitmap[i] = 1;
 267 }
 268
 269 void make_bitmap_label(struct variant *v, struct sym_text *text)
 270 {
 271   v->width = ceil(text->tw);
 272   v->height = ceil(text->th);
 273   v->bitmap = malloc(v->width * v->height * sizeof(bool));
 274   for (int i=0; i<v->height; i++)
 275     for (int j=0; j<v->width; j++)
 276     {
 277       v->bitmap[i*v->width + j] = 1;
 278     }
 279 }
 280
 281 void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex)
 282 {
 283   if (dbg_requests)
 284     printf("Adding point\n");
 285   if (object->type != OSM_TYPE_NODE)
 286   {
 287     printf("Warning: Point label requested on non-point object\n");
 288     return;
 289   }
 290
 291   struct request_point *r = GARY_PUSH(requests_point);
 292
 293   r->request.type = REQUEST_POINT;
 294   r->request.ind = num_requests++;
 295
 296   r->sym = sym;
 297   r->zindex = zindex;
 298
 299   r->offset_x = 0;
 300   r->offset_y = 0;
 301
 302   r->num_variants = 1;
 303   GARY_INIT(r->request.variants, 0);
 304
 305   struct variant *v = GARY_PUSH(r->request.variants);
 306
 307   struct osm_node *n = (struct osm_node *) object; // FIXME: Compiler warning
 308   r->x = n->x;
 309   r->y = n->y;
 310   switch (sym->type)
 311   {
 312     case SYMBOLIZER_ICON:
 313       make_bitmap_icon(v, (struct sym_icon *) sym);
 314       r->x = ((struct sym_icon *)sym)->sir.x;
 315       r->y = ((struct sym_icon *)sym)->sir.y;
 316       break;
 317     case SYMBOLIZER_POINT:
 318       make_bitmap_point(v, (struct sym_point *) sym);
 319       break;
 320     case SYMBOLIZER_TEXT: ;
 321       struct sym_text *st = (struct sym_text *) sym;
 322       struct osm_node *n = (struct osm_node *) object;
 323       make_bitmap_label(v, st);
 324     default:
 325       // FIXME
 326       return;
 327   }
 328
 329 //  printf("Inited point to [%.2f; %.2f] on %u\n", r->x, r->y, r->zindex);
 330 }
 331
 332 void labeller_add_line(struct symbol *sym, z_index_t zindex)
 333 {
 334   if (dbg_requests)
 335     printf("Adding line on %u\n", zindex);
 336   struct buffer_line *b = GARY_PUSH(buffer_line);
 337   b->line = (struct sym_line *) sym;
 338   b->zindex = zindex;
 339   sym_plan(sym, zindex);
 340 }
 341
 342 void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
 343 {
 344   if (o->type != OSM_TYPE_WAY)
 345   {
 346     // FIXME
 347     return;
 348   }
 349
 350   if (dbg_requests)
 351     printf("[LAB] Labelling way %ju on %u\n", o->id, zindex);
 352   struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
 353   ll->way = (struct osm_way *) o;
 354   ll->label = sym;
 355   ll->zindex = zindex;
 356 }
 357
 358 void labeller_add_arealabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
 359 {
 360   if (dbg_requests)
 361     printf("Adding area on %u\n", zindex);
 362   struct request_area *r = GARY_PUSH(requests_area);
 363
 364   r->request.type = REQUEST_AREA;
 365   r->request.ind = num_requests++;
 366
 367   r->o = (struct osm_multipolygon *) o;
 368   r->zindex = zindex;
 369   r->label = sym;
 370
 371   osm_obj_center(o, &(r->cx), &(r->cy));
 372
 373   GARY_INIT(r->request.variants, 0);
 374   struct variant *v = GARY_PUSH(r->request.variants);
 375   switch (sym->type)
 376   {
 377     case SYMBOLIZER_ICON:
 378       if (dbg_requests)
 379         printf("DEBUG: Icon label\n");
 380       make_bitmap_icon(v, (struct sym_icon *) sym);
 381       break;
 382     case SYMBOLIZER_TEXT:
 383       if (dbg_requests)
 384         printf("DEBUG: Text label\n");
 385       make_bitmap_label(v, (struct sym_text *) sym);
 386     default:
 387       // FIXME
 388       ;
 389   }
 390 }
 391
 392 void make_graph(void)
 393 {
 394   hash_init();
 395   struct mempool *mp_edges = mp_new(BLOCK_SIZE);
 396
 397   printf("Extracting nodes, will iterate over %lld ways\n", GARY_SIZE(buffer_line));
 398   for (uns i=0; i<GARY_SIZE(buffer_line); i++)
 399   {
 400     struct osm_way *way = (struct osm_way *) buffer_line[i].line->s.o;
 401     struct graph_node *g_prev = NULL;
 402     struct osm_node *o_prev = NULL;
 403
 404     CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
 405     {
 406       // FIXME: Shall osm_object's type be checked here?
 407       struct osm_node *o_node = (struct osm_node *) ref->o;
 408
 409       struct graph_node *g_node = hash_find(ref->o->id);
 410       if (!g_node)
 411       {
 412         g_node = hash_new(ref->o->id);
 413         GARY_INIT(g_node->edges, 0);
 414         g_node->o = o_node;
 415         g_node->id = ref->o->id;
 416         g_node->num = num_nodes++;
 417       }
 418
 419       if (! g_prev)
 420       {
 421         g_prev = g_node;
 422         o_prev = o_node;
 423         continue;
 424       }
 425
 426       struct graph_edge *e = mp_alloc(mp_edges, sizeof(struct graph_edge)); num_edges_dbg++;
 427       e->num = num_edges++;
 428       e->id = buffer_line[i].line->s.o->id;
 429       e->color = buffer_line[i].line->color;
 430       e->length = hypot(abs(o_prev->x - o_node->x), abs(o_prev->y - o_node->y));
 431       e->visited = -1;
 432       e->prev = NULL;
 433       e->next = NULL;
 434       e->n1 = g_prev;
 435       e->n2 = g_node;
 436       e->longline = (uns) -1;
 437       e->line = buffer_line[i].line;
 438       e->dir = DIR_UNSET;
 439       e->label = NULL;
 440
 441       struct graph_edge **edge = GARY_PUSH(g_prev->edges);
 442       *edge = e;
 443       edge = GARY_PUSH(g_node->edges);
 444       *edge = e;
 445
 446       g_prev = g_node;
 447       o_prev = o_node;
 448     }
 449   }
 450
 451   printf("Made graph with %d edges\n", num_edges_dbg);
 452 }
 453
 454 void dump_graph(void)
 455 {
 456   HASH_FOR_ALL(hash, node)
 457   {
 458     printf("* Node: (%d) #%ju [%.2f; %.2f]\n", node->num, node->id, node->o->x, node->o->y);
 459     for (uns i=0; i<GARY_SIZE(node->edges); i++)
 460     {
 461       struct graph_edge *e = node->edges[i];
 462       printf("\t edge (%d) #%ju to ", e->num, e->id);
 463       if (node->edges[i]->n1->id == node->id)
 464         printf("(%d) #%ju [%.2f; %.2f]\n", e->n2->num, e->n2->id, e->n2->o->x, e->n2->o->y);
 465       else if (node->edges[i]->n2->id == node->id)
 466         printf("(%d) #%ju [%.2f; %.2f]\n", e->n1->num, e->n1->id, e->n1->o->x, e->n1->o->y);
 467       else
 468         printf("BEWARE! BEWARE! BEWARE!\n");
 469
 470       printf("\t\t");
 471       if ((node->edges[i]->label)) printf("Labelled\n");
 472       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));
 473       printf(" colored %d;", node->edges[i]->color);
 474       printf("   length %.2f", node->edges[i]->length);
 475       printf("\n");
 476     }
 477   }
 478   HASH_END_FOR;
 479 }
 480
 481 void label_graph(void)
 482 {
 483   if (dbg_graph)
 484     printf("There are %u line labels requested\n", GARY_SIZE(buffer_linelabel));
 485   for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
 486   {
 487     if (buffer_linelabel[i].label->type == SYMBOLIZER_TEXT)
 488     if (dbg_graph)
 489       printf("Labelling nodes of way %s\n", osm_val_decode(((struct sym_text *) buffer_linelabel[i].label)->text));
 490     CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
 491     {
 492       if (dbg_graph)
 493         printf("Looking for node %ju\n", ref->o->id);
 494       struct graph_node *n = hash_find(ref->o->id);
 495       if (n == NULL)
 496       {
 497         // FIXME: What shall be done?
 498       }
 499       else
 500       {
 501         if (dbg_graph)
 502           printf("Searching among %u edges\n", GARY_SIZE(n->edges));
 503         for (uns j=0; j<GARY_SIZE(n->edges); j++)
 504         {
 505           if (n->edges[j]->id == buffer_linelabel[i].way->o.id)
 506           {
 507             if (dbg_graph)
 508               printf("Labelling node %ju\n", n->id);
 509             n->edges[j]->label = buffer_linelabel[i].label;
 510             n->edges[j]->zindex = buffer_linelabel[i].zindex;
 511           }
 512         }
 513       }
 514     }
 515   }
 516 }
 517
 518 void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir)
 519 {
 520   if (dbg_bfs)
 521     printf("BFS edge called for edge %d (going %d) in direction %d\n", e->num, e->dir, dir);
 522   struct graph_edge *candidate = NULL;
 523
 524   for (uns i=0; i<GARY_SIZE(node->edges); i++)
 525   {
 526     struct graph_edge *other = node->edges[i];
 527     if ((other->longline != (uns) -1) && (other->longline != e->longline)) continue;
 528
 529     if ((uns) other->visited != e->longline) {
 530     if (dbg_bfs)
 531       printf("Pushing new edge %d / %ju\n", other->num, other->id);
 532     struct graph_edge **e_ptr = GARY_PUSH(bfs_queue);
 533     *e_ptr = other;
 534     other->visited = e->longline;
 535     }
 536
 537     if (((other->n1->id == node->id) && (other->n2->id == anode->id)) ||
 538         ((other->n2->id == node->id) && (other->n1->id == anode->id)))
 539         continue;
 540
 541     if (((other->n1->id == node->id) || (other->n2->id == node->id)) &&
 542         (e->label) && (other->label) &&
 543         (e->label->type == SYMBOLIZER_TEXT) && (other->label->type == SYMBOLIZER_TEXT) &&
 544         (((struct sym_text *) e->label)->text == ((struct sym_text *) other->label)->text))
 545     {
 546       if (! candidate || (other->length > candidate->length))
 547       candidate = other;
 548     }
 549   }
 550
 551   if (candidate)
 552   {
 553     if (dbg_bfs)
 554       printf("New line in longline %u\n", e->longline);
 555     struct graph_edge *other = candidate;
 556       other->longline = e->longline;
 557       other->dir = dir;
 558       if (((dir == DIR_BWD) && (other->n1->id == node->id)) ||
 559           ((dir == DIR_FWD) && (other->n2->id == node->id)))
 560       {
 561         struct graph_node *swp = other->n2;
 562         other->n2 = other->n1;
 563         other->n1 = swp;
 564       }
 565
 566       switch (dir)
 567       {
 568         case DIR_BWD:
 569           e->prev = other;
 570           other->next = e;
 571           longlines[other->longline].first = other;
 572           break;
 573         case DIR_FWD:
 574           e->next = other;
 575           other->prev = e;
 576           break;
 577         default:
 578           printf("Oops\n");
 579           ASSERT(0);
 580       }
 581   }
 582 }
 583
 584 void bfs(uns longline)
 585 {
 586 if (dbg_bfs)
 587   printf("BFS called for longline %u\n", longline);
 588 if (dbg_bfs)
 589   printf("%d longlines are believed to exist, %d exist\n", num_longlines, GARY_SIZE(longlines));
 590   for (uns i=0; i<GARY_SIZE(bfs_queue); i++)
 591   {
 592     struct graph_edge *cur = bfs_queue[i];
 593     if (dbg_bfs)
 594       printf("Exploring new edge %d; %d remaining\n", cur->num, GARY_SIZE(bfs_queue));
 595     //ASSERT(! cur->visited);
 596
 597     cur->visited = longline;
 598
 599     if (cur->longline == (uns) -1)
 600       continue;
 601
 602     if (cur->dir == DIR_UNSET)
 603     {
 604       cur->dir = DIR_CENTER;
 605       bfs_edge(cur, cur->n1, cur->n2, DIR_BWD);
 606       bfs_edge(cur, cur->n2, cur->n1, DIR_FWD);
 607     }
 608     else
 609     {
 610       switch (cur->dir)
 611       {
 612         case DIR_BWD:
 613           bfs_edge(cur, cur->n1, cur->n2, cur->dir);
 614           break;
 615         case DIR_FWD:
 616           bfs_edge(cur, cur->n2, cur->n1, cur->dir);
 617           break;
 618         default:
 619           // FIXME
 620           ;
 621       }
 622     }
 623   }
 624 }
 625
 626 void bfs_wrapper(void)
 627 {
 628   GARY_INIT(bfs_queue, 0);
 629   GARY_INIT(longlines, 0);
 630
 631   HASH_FOR_ALL(hash, node)
 632   {
 633     for (uns i=0; i<GARY_SIZE(node->edges); i++)
 634     {
 635       if ((node->edges[i]->label) && (node->edges[i]->longline == (uns) -1))
 636       {
 637         GARY_PUSH(longlines);
 638         longlines[num_longlines].first = node->edges[i];
 639         if (dbg_bfs)
 640           printf("Running new BFS\n");
 641         if (dbg_bfs)
 642           printf("Creating longline %u\n", num_longlines);
 643         GARY_RESIZE(bfs_queue, 0);
 644         struct graph_edge **e = GARY_PUSH(bfs_queue);
 645         *e = node->edges[i];
 646         node->edges[i]->longline = num_longlines;
 647         bfs(node->edges[i]->longline);
 648         //dump_longlines();
 649         if (dbg_bfs)
 650           printf("Joined %d edges\n", dbg_num_hits); dbg_num_hits = 0;
 651         if (dbg_bfs)
 652           printf("Planned %u edges\n", GARY_SIZE(bfs_queue));
 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
 690   return rl;
 691 }
 692
 693 struct request_section *make_new_section(struct request_line *rl)
 694 {
 695   struct request_section *rls = GARY_PUSH(rl->sections);
 696   rls->request.ind = num_requests++;
 697   rls->request.type = REQUEST_SECTION;
 698   rls->num_segments = 0;
 699   GARY_INIT(rls->segments, 0);
 700
 701   return rls;
 702 }
 703
 704 struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym)
 705 {
 706   struct request_segment *rs = GARY_PUSH(rls->segments);
 707   rls->num_segments++;
 708
 709   rs->request.ind = num_requests++;
 710   rs->request.type = REQUEST_SEGMENT;
 711
 712   struct variant *v = malloc(sizeof(struct variant));
 713   make_bitmap(v, sym);
 714   rs->request.variants = v;
 715
 716   return rs;
 717 }
 718
 719 void cut_edge(struct graph_edge *e, double dist)
 720 {
 721   if (dbg_segments)
 722     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);
 723
 724   struct graph_edge *new = malloc(sizeof(struct graph_edge));
 725   *new = *e;
 726   e->next = new;
 727
 728   // FIXME? Create new label for new edge, don't only copy pointer?
 729
 730   struct osm_node *n1 = e->n1->o;
 731   struct osm_node *n2 = e->n2->o;
 732
 733   // FIXME
 734   if ((n1->x == n2->x) && (n1->y == n2->y))
 735   {
 736     printf("[%.2f; %.2f] -- [%.2f; %.2f]\n", n1->x, n1->y, n2->x, n2->y);
 737     printf("Won't cut point\n");
 738     return;
 739   }
 740
 741   struct osm_node *n11 = malloc(sizeof(struct osm_node));
 742   struct graph_node *gn = malloc(sizeof(struct graph_node));
 743   gn->o = n11;
 744   double vsize = sqrt(pow(n1->x - n2->x, 2) + pow(n1->y - n2->y, 2));
 745   n11->x = n1->x + (n2->x - n1->x) / vsize * dist;
 746   n11->y = n1->y + (n2->y - n1->y) / vsize * dist;
 747
 748   e->n2 = new->n1 = gn;
 749
 750   e->length = hypot(abs(n1->x - n11->x), abs(n1->y - n11->y));
 751   new->length = hypot(abs(n11->x - n2->x), abs(n11->y - n2->y));
 752   new->visited = 0;
 753 }
 754
 755 void make_segments(void)
 756 {
 757   for (uns i=0; i<GARY_SIZE(longlines); i++)
 758   {
 759     // Skip lines which are not labelled
 760     if (! (longlines[i].first && longlines[i].first->label))
 761       continue;
 762
 763     struct request_line *request = make_new_line();
 764     struct request_section *rls = make_new_section(request);
 765     struct request_segment *rs = NULL;
 766
 767     struct graph_edge *e = longlines[i].first;
 768     double cur_length = 0;
 769
 770     struct sym_text *st = NULL;
 771     if (e->label->type == SYMBOLIZER_TEXT)
 772     {
 773       st = (struct sym_text *) e->label;
 774     }
 775     else
 776     {
 777       if (dbg_segments)
 778         printf("Warning: Skipping line\n");
 779       continue;
 780       // FIXME;
 781     }
 782
 783     if (dbg_segments)
 784       printf("New longline\n");
 785     while (e)
 786     {
 787       if (e->visited < 0)
 788       {
 789         printf("BEWARE: Edge cycle\n");
 790         break;
 791       }
 792       e->visited = -1; // FIXME
 793
 794       if (dbg_segments)
 795         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);
 796
 797       if (st && (e->length < st->tw))
 798       {
 799         e = e->next;
 800         //printf("Warning: Skipping segment\n");
 801         continue;
 802       }
 803
 804       if (cur_length + e->length > conf_max_section_length + conf_max_section_overlay)
 805       {
 806         if (dbg_segments)
 807           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);
 808         // HACK to prevent cutting to 0 lenght
 809         cut_edge(e, max2(conf_max_section_length - cur_length, 2));
 810       }
 811
 812       rs = make_new_segment(rls, e->label);
 813       rs->label = malloc(sizeof(struct sym_text));
 814       *((struct sym_text *) rs->label) = *((struct sym_text *) e->label);
 815
 816       rs->x1 = e->n1->o->x;
 817       rs->y1 = e->n1->o->y;
 818       rs->x2 = e->n2->o->x;
 819       rs->y2 = e->n2->o->y;
 820
 821       // FIXME: Set text rotation
 822       rs->angle = atan2(rs->x2 - rs->x1, rs->y2 - rs->y1);
 823       rs->zindex = e->zindex;
 824
 825       cur_length += e->length;
 826       if (cur_length > conf_max_section_length)
 827       {
 828         if (dbg_segments)
 829           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);
 830
 831         rls = make_new_section(request);
 832         cur_length = 0;
 833       }
 834
 835       e = e->next;
 836     }
 837
 838     if (request->sections[0].num_segments == 0)
 839     {
 840       // FIXME
 841       printf("WARNING: 0 segment section\n");
 842       GARY_POP(requests_line);
 843       num_requests -= 2;
 844     }
 845   }
 846 }
 847
 848 void dump_linelabel_requests(void)
 849 {
 850   for (uns i=0; i<GARY_SIZE(requests_line); i++)
 851   {
 852     if (requests_line[i].sections[0].num_segments == 0)
 853     {
 854       printf("HEY!\n");
 855       continue;
 856     }
 857     printf("Request for linelabel, %d sections\n", GARY_SIZE(requests_line[i].sections));
 858     print_label(requests_line[i].sections[0].segments[0].label);
 859     for (uns j=0; j<GARY_SIZE(requests_line[i].sections); j++)
 860     {
 861       printf("%d section, %d segments\n", j, GARY_SIZE(requests_line[i].sections[j].segments));
 862       for (uns k=0; k<GARY_SIZE(requests_line[i].sections[j].segments); k++)
 863       {
 864         struct request_segment *rs = &requests_line[i].sections[j].segments[k];
 865         printf("[%.2f; %.2f] -- [%.2f; %.2f]\n", rs->x1, rs->y1, rs->x2, rs->y2);
 866       }
 867     }
 868     printf("\n");
 869   }
 870 }
 871
 872 void dump_bitmaps(struct individual *individual)
 873 {
 874   bool *bitmap = malloc(page_width_int * page_height_int * sizeof(bool));
 875   printf("Bitmap size is %d\n", page_width_int * page_height_int);
 876   for (int i=0; i<page_height_int; i++)
 877     for (int j=0; j<page_width_int; j++)
 878       bitmap[i*page_width_int + j] = 0;
 879
 880   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 881   {
 882     if (individual->placements[i].variant_used == -1) continue;
 883
 884     struct placement *p = &(individual->placements[i]);
 885     struct variant *v = NULL;
 886
 887     switch (p->request->type)
 888     {
 889       case REQUEST_SEGMENT: ;
 890       case REQUEST_POINT: ;
 891       case REQUEST_AREA: ;
 892         v = &(p->request->variants[p->variant_used]);
 893         break;
 894       default:
 895         ASSERT(p->request->type != REQUEST_INVALID);
 896         continue;
 897     }
 898
 899     for (int row = max2(p->y, 0); row < min2(p->y + v->height, page_height_int); row++)
 900     {
 901       for (int col = max2(p->x, 0); col < min2(p->x + v->width, page_width_int); col++)
 902       {
 903         bitmap[row * page_width_int + col] = 1;
 904       }
 905     }
 906   }
 907
 908   errno = 0;
 909   FILE *fd_dump = fopen("dump.pbm", "w");
 910   fprintf(fd_dump, "P1\n");
 911   fprintf(fd_dump, "%d %d\n", page_width_int, page_height_int);
 912   for (int i=0; i<page_height_int; i++)
 913   {
 914     for (int j=0; j<page_width_int; j++)
 915     {
 916       fprintf(fd_dump, "%d", bitmap[(int) (i*page_width_int + j)] ? 1 : 0);
 917     }
 918     fprintf(fd_dump, "\n");
 919   }
 920   fclose(fd_dump);
 921 }
 922
 923 void dump_individual(struct individual *individual)
 924 {
 925 printf("*** Dumping INDIVIDUAL ***\n");
 926 printf("(There are %d requests)\n", num_requests);
 927   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 928   {
 929     struct placement *p = &(individual->placements[i]);
 930
 931     switch (p->request->type)
 932     {
 933       case REQUEST_POINT:
 934         printf("Point at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_point *) p->request)->zindex);
 935         break;
 936       case REQUEST_LINE: ;
 937         struct request_line *rl = (struct request_line *) p->request;
 938         printf("Line: ");
 939         print_label(rl->sections[0].segments[0].label);
 940         break;
 941       case REQUEST_SECTION: ;
 942         printf("*");
 943         break;
 944       case REQUEST_SEGMENT: ;
 945         if (p->variant_used >= 0)
 946           printf("Segment placed at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_segment *) p->request)->zindex);
 947         else
 948           printf("Segment not placed\n");
 949         break;
 950       case REQUEST_AREA: ;
 951         struct request_area *ra = (struct request_area *) p->request;
 952         printf("Area label ");
 953         print_label(ra->label);
 954         printf(" at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_area *) p->request)->zindex);
 955         break;
 956       default:
 957         printf("Testing request type (dump_individual)\n");
 958         ASSERT(p->request->type != 0);
 959     }
 960   }
 961   printf("\nTotal penalty: %d\n", individual->penalty);
 962 }
 963
 964 void plan_individual(struct individual *individual)
 965 {
 966   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 967   {
 968     struct symbol *s = NULL;
 969     z_index_t zindex = 0;
 970     if (individual->placements[i].variant_used < 0) continue;
 971     switch (individual->placements[i].request->type)
 972     {
 973       case REQUEST_POINT: ;
 974         struct request_point *rp = (struct request_point *) individual->placements[i].request;
 975         s = rp->sym;
 976         zindex = rp->zindex;
 977         break;
 978       case REQUEST_SEGMENT: ;
 979         struct request_segment *rs = (struct request_segment *) individual->placements[i].request;
 980         s = rs->label;
 981         zindex = rs->zindex;
 982         break;
 983       case REQUEST_LINE: ;
 984         break;
 985       case REQUEST_AREA: ;
 986         struct request_area *ra = (struct request_area *) individual->placements[i].request;
 987         s = ra->label;
 988         zindex = ra->zindex;
 989         break;
 990       default:
 991         ASSERT(individual->placements[i].request != REQUEST_INVALID);
 992         continue;
 993     }
 994
 995 if (dbg_plan)
 996   printf("Will plan symbol at [%.2f; %.2f] on %u\n", individual->placements[i].x, individual->placements[i].y, zindex);
 997
 998     if (s) switch (s->type)
 999     {
1000       case SYMBOLIZER_POINT: ;
1001         struct sym_point *sp = (struct sym_point *) s;
1002         sp->x = individual->placements[i].x;
1003         sp->y = individual->placements[i].y;
1004         sym_plan((struct symbol *) sp, zindex);
1005         break;
1006       case SYMBOLIZER_ICON: ;
1007         struct sym_icon *si = (struct sym_icon *) s;
1008         si->sir.x = individual->placements[i].x;
1009         si->sir.y = individual->placements[i].y;
1010         sym_plan((struct symbol *) si, zindex);
1011         break;
1012       case SYMBOLIZER_TEXT: ;
1013         struct sym_text *st = (struct sym_text *) s;
1014         st->x = individual->placements[i].x;
1015         st->y = individual->placements[i].y;
1016         st->next_duplicate = NULL;
1017         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);
1018         sym_plan((struct symbol *) st, zindex);
1019         break;
1020       default:
1021         ASSERT(s->type != SYMBOLIZER_INVALID);
1022     }
1023   }
1024
1025 }
1026
1027 void labeller_label(void)
1028 {
1029   make_graph();
1030   label_graph();
1031   bfs_wrapper();
1032   make_segments();
1033
1034 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));
1035
1036   GARY_INIT(population1, conf_pop_size);
1037   GARY_INIT(population2, conf_pop_size);
1038   make_population();
1039
1040   printf("Dealing with %d requests\n", num_requests);
1041
1042 /*
1043   while (! shall_terminate())
1044   {
1045     iteration++;
1046
1047     struct individual **swp = population1;
1048     population1 = population2;
1049     population2 = swp;
1050     pop2_ind = 0;
1051   }
1052 */
1053
1054   plan_individual(population1[0]);
1055
1056   labeller_cleanup();
1057
1058   return;
1059 }
1060
1061 void labeller_cleanup(void)
1062 {
1063 }
1064
1065 void make_population(void)
1066 {
1067   for (int i=0; i<conf_pop_size; i++)
1068   {
1069     if (dbg_init)
1070       printf("Making individual %d\n", i);
1071     struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
1072     population1[i] = individual;
1073
1074     int p = 0;
1075     for (uns j=0; j<GARY_SIZE(requests_point); j++)
1076     {
1077       init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_point[j]);
1078     }
1079
1080     for (uns j=0; j<GARY_SIZE(requests_line); j++)
1081     {
1082       init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j]);
1083
1084       for (uns k=0; k<GARY_SIZE(requests_line[j].sections); k++)
1085       {
1086         init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k]);
1087
1088         for (uns l=0; l<GARY_SIZE(requests_line[j].sections[k].segments); l++)
1089         {
1090           init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k].segments[l]);
1091         }
1092       }
1093     }
1094
1095     for (uns j=0; j<GARY_SIZE(requests_area); j++)
1096     {
1097       init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_area[j]);
1098     }
1099
1100     hide_segment_labels(individual);
1101
1102     ASSERT(p == num_requests);
1103   }
1104 }
1105
1106 bool shall_terminate(void)
1107 {
1108   switch (conf_term_cond)
1109   {
1110     case TERM_COND_PENALTY:
1111       return (population1[0]->penalty < conf_penalty_bound);
1112     case TERM_COND_STAGNATION:
1113       return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
1114     case TERM_COND_ITERATIONS:
1115       return (iteration >= conf_iteration_limit);
1116     default:
1117       // FIXME: Warn the user that no condition is set
1118       return 1;
1119   }
1120 }
1121
1122 void breed(void)
1123 {
1124   int acc = 0;
1125   int i=0;
1126   printf("%.2f\n", ((double) conf_breed_pop_size_perc/100));
1127   int conf_breed_pop_size = ((double) conf_breed_pop_size_perc/100) * conf_pop_size;
1128   struct individual **breed_buffer;
1129   while (i < conf_breed_pop_size)
1130   {
1131   printf("%d < %d, breeding\n", i, conf_breed_pop_size);
1132     int parent1 = randint(1, conf_breed_pop_size);
1133     int parent2 = randint(1, conf_breed_pop_size);
1134     printf("Will breed %d and %d, chosen of %d best of %d population (intended to be %d)\n", parent1, parent2, conf_breed_pop_size, GARY_SIZE(population1), conf_pop_size);
1135     breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
1136     population2[pop2_ind++] = breed_buffer[0];
1137     population2[pop2_ind++] = breed_buffer[1];
1138     free(breed_buffer);
1139     i++;
1140   }
1141
1142   acc += conf_breed_rbest_perc;
1143
1144   return; // FIXME: DEBUG HACK
1145
1146   int remaining = (1 - acc) * (conf_pop_size * conf_breed_perc);
1147   int step = remaining / conf_pop_size;
1148   for (; i<conf_pop_size; i += 2)
1149   {
1150     printf("Asking for %d and %d of %d\n", i*step, i*(step+1), conf_pop_size);
1151     breed_buffer = perform_crossover(population1[i*step], population1[i*step+1]);
1152     population2[pop2_ind++] = breed_buffer[0];
1153     population2[pop2_ind++] = breed_buffer[1];
1154   }
1155
1156   // FIXME: Could there be one missing individual?
1157 }
1158
1159 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
1160 {
1161   struct individual **buffer = malloc(2*sizeof(struct individual));
1162   struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
1163   struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
1164
1165   printf("Performing crossover\n");
1166
1167   for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
1168   {
1169     printf("%dth placement out of %d\n", i, num_requests);
1170     if (! parent1->placements[i].processed)
1171     {
1172       struct placement **clos_symbols = get_closure(&(parent1->placements[i]), parent1, parent2);
1173       int x = randint(1, 2);
1174
1175       if (x == 1)
1176       {
1177         copy_symbols(clos_symbols, parent1, child1);
1178         copy_symbols(clos_symbols, parent2, child2);
1179       }
1180       else
1181       {
1182         copy_symbols(clos_symbols, parent2, child1);
1183         copy_symbols(clos_symbols, parent1, child2);
1184       }
1185       printf("Symbols copied; %lld\n", GARY_SIZE(clos_symbols));
1186       GARY_FREE(clos_symbols);
1187     }
1188
1189     if (conf_mutate_children)
1190     {
1191       if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child1);
1192       if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child2);
1193     }
1194   }
1195
1196   buffer[0] = child1;
1197   buffer[1] = child2;
1198   return buffer;
1199 }
1200
1201 void mutate(void)
1202 {
1203   int i = 0;
1204   int conf_mutate_pop_size = conf_mutate_pop_size_perc * conf_pop_size;
1205   while (i < conf_mutate_rbest_perc * conf_pop_size)
1206   {
1207     int ind = randint(1, conf_mutate_pop_size);
1208     copy_individual(population2[pop2_ind], population1[ind]);
1209     perform_mutation(population2[pop2_ind]);
1210     pop2_ind++;
1211   }
1212 }
1213
1214 void perform_mutation(struct individual *individual)
1215 {
1216   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1217   {
1218     int x = randint(1, 1000);
1219     int acc = 0;
1220
1221     if (x <= acc + conf_mutate_move_bound)
1222     {
1223       move_symbol(&(individual->placements[i]));
1224       continue;
1225     }
1226     acc += conf_mutate_move_bound;
1227
1228     if (x <= acc + conf_mutate_regen_bound)
1229     {
1230       gen_coords(&(individual->placements[i]));
1231       continue;
1232     }
1233     acc += conf_mutate_regen_bound;
1234
1235     if (x <= acc + conf_mutate_chvar_bound)
1236     {
1237       if (0) // if num_variants > 1
1238       {
1239         // FIXME: assign new variant
1240       }
1241     }
1242   }
1243 }
1244
1245 void elite(void)
1246 {
1247   for (int i=0; i<conf_elite_perc * conf_pop_size; i++)
1248   {
1249     population2[pop2_ind++] = population1[0];
1250   }
1251 }
1252
1253 void rank_population(void)
1254 {
1255   // FIXME
1256 }
1257
1258 struct map_part **get_map_parts(struct placement *p)
1259 {
1260   if (p->variant_used < 0) return NULL;
1261
1262   struct map_part **buffer;
1263   GARY_INIT(buffer, 0);
1264
1265   if (dbg_map_parts)
1266     printf("Looking for map parts containing placement of request %d, placed at [%.2f; %.2f]\n", p->request->ind, p->x, p->y);
1267
1268   struct variant v;
1269   switch (p->request->type)
1270   {
1271     case REQUEST_POINT:
1272     case REQUEST_SEGMENT:
1273     case REQUEST_AREA:
1274       v = p->request->variants[p->variant_used];
1275       break;
1276     default:
1277       return NULL;
1278   }
1279
1280   int x_min = max2(0, p->x) / conf_map_part_width;
1281   int x_max = min2(page_width_int, (p->x + v.width + conf_map_part_width - 1)) / conf_map_part_width;
1282   int y_min = max2(0, p->y) / conf_map_part_height;
1283   int y_max = min2(page_height_int, (p->y + v.height + conf_map_part_height - 1)) / conf_map_part_height;
1284
1285   if (dbg_map_parts)
1286     printf("Cells between [%d; %d] and [%d; %d] generated\n", x_min, y_min, x_max, y_max);
1287
1288   for (int y=y_min; y<=y_max; y++)
1289     for (int x=x_min; x<=x_max; x++)
1290     {
1291       struct map_part **m = GARY_PUSH(buffer);
1292       if (dbg_map_parts)
1293         printf("Asking for %d of %u\n", y * num_map_parts_row + x, GARY_SIZE(p->individual->map));
1294       *m = p->individual->map[y * num_map_parts_row + x];
1295     }
1296
1297   return buffer;
1298 }
1299
1300 void update_map_parts(struct placement *p)
1301 {
1302   struct placement_link *ml = p->map_links;
1303   while (ml)
1304   {
1305     struct map_placement *mp = ml->mp;
1306     mp->prev = mp->next;
1307     if (mp->next)
1308       mp->next->prev = mp->prev;
1309     free(mp);
1310
1311     struct placement_link *tmp = ml;
1312     ml = ml->next;
1313     free(tmp);
1314   }
1315
1316   struct map_part **parts = get_map_parts(p);
1317   if (parts == NULL) return;
1318
1319   for (uns i=0; i<GARY_SIZE(parts); i++)
1320   {
1321     struct map_placement *mp = malloc(sizeof(struct map_placement));
1322     mp->placement = p;
1323
1324     mp->next = parts[i]->placement->next;
1325     parts[i]->placement->next = mp;
1326     if (mp->next) mp->next->prev = mp;
1327
1328     struct placement_link *ml = malloc(sizeof(struct placement_link));
1329     ml->mp = mp;
1330     ml->next = p->map_links;
1331     p->map_links = ml;
1332   }
1333
1334   GARY_FREE(parts);
1335 }
1336
1337 void gen_coords(struct placement *p)
1338 {
1339   switch(p->request->type)
1340   {
1341     case REQUEST_POINT:
1342       gen_coords_point(p);
1343       break;
1344     case REQUEST_AREA:
1345       gen_coords_area(p);
1346       break;
1347     case REQUEST_SEGMENT:
1348       gen_coords_segment(p);
1349       break;
1350     case REQUEST_LINE:
1351       if (dbg_movement)
1352         printf("Not yet implemented\n");
1353       break;
1354     default:
1355       if (dbg_movement)
1356         printf("Testing request type\n");
1357       ASSERT(p->request->type != REQUEST_INVALID);
1358   }
1359
1360   update_map_parts(p);
1361 }
1362
1363 double gen_movement(void)
1364 {
1365   double m = (random() % 1000000) / 10000;
1366   m = pow(m, 1.0/3) * flip(1, -1);
1367   if (dbg_movement)
1368     printf("Movement %.2f\n", m);
1369   return m;
1370 }
1371
1372 void gen_coords_point(struct placement *p)
1373 {
1374   p->x = p->x + gen_movement();
1375 }
1376
1377 void gen_coords_segment(struct placement *p)
1378 {
1379   struct request_segment *rs = (struct request_segment *) p->request;
1380   int a = flip(1, 2);
1381   p->x = (a == 1 ? rs->x1 : rs->x2);
1382   p->y = (a == 1 ? rs->y1 : rs->y2);
1383 }
1384
1385 void gen_coords_area(struct placement *p)
1386 {
1387   struct request_area *ra = (struct request_area *) p->request;
1388
1389   p->x = p->x + gen_movement();
1390   p->y = p->y + gen_movement();
1391
1392   if (dbg_movement)
1393     printf("Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
1394 }
1395
1396 struct map_part **get_parts(struct placement *symbol, struct individual *individual)
1397 {
1398   struct map_part **buffer;
1399   GARY_INIT(buffer, 0);
1400   int x_min = symbol->x / conf_part_size;
1401   int x_max = (symbol->x /*+ symbol->bitmap->width*/ + conf_part_size - 1) / conf_part_size;
1402   int y_min = symbol->y / conf_part_size;
1403   int y_max = (symbol->y /*+ symbol->bitmap->height*/ + conf_part_size - 1) / conf_part_size;
1404
1405   for (int x=x_min; x < x_max; x++)
1406     for (int y=y_min; y < y_max; y++)
1407     {
1408       struct map_part *m = GARY_PUSH(buffer);
1409       *m = individual->map[x][y];
1410     }
1411
1412   return buffer;
1413 }
1414
1415 int randint(int min, int max)
1416 {
1417   if (min == max) return min;
1418   int r = random();
1419   //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)));
1420   return min + (r % (max - min));
1421   return (r * (max - min));
1422 }
1423
1424 struct placement **get_closure(struct placement *placement, struct individual *parent1, struct individual *parent2 UNUSED)
1425 {
1426   printf("Getting closure\n");
1427   struct placement **closure;
1428   GARY_INIT(closure, 0);
1429   bool *chosen = malloc(GARY_SIZE(parent1->placements) * sizeof(bool));
1430   chosen[placement->request->ind] = 1;
1431
1432   struct placement **p = GARY_PUSH(closure); *p = placement;
1433
1434   uns first = 0;
1435   while (first < GARY_SIZE(closure))
1436   {
1437     printf("Iterating, first is %d\n", first);
1438     struct placement **overlapping = get_overlapping(placement);
1439     filter(overlapping, chosen);
1440     for (uns j=0; j<GARY_SIZE(overlapping); j++)
1441     {
1442       p = GARY_PUSH(closure); *p = overlapping[j];
1443       chosen[overlapping[j]->request->ind] = 1;
1444     }
1445     GARY_FREE(overlapping);
1446     first++;
1447   }
1448
1449   return closure;
1450 }
1451
1452 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child)
1453 {
1454   //printf("%d\n", child->penalty);
1455   //printf("Closure size: %lld\n", GARY_SIZE(closure));
1456   for (uns i=0; i<GARY_SIZE(closure); i++)
1457   {
1458     int ind = closure[i]->request->ind;
1459     child->placements[ind] = parent->placements[ind];
1460     child->placements[ind].processed = 0;
1461   }
1462 }
1463
1464 void move_symbol(struct placement *p)
1465 {
1466   switch (p->request->type)
1467   {
1468     case REQUEST_POINT:
1469       move_symbol_point(p);
1470     case REQUEST_LINE:
1471     case REQUEST_SEGMENT:
1472     case REQUEST_AREA:
1473       if (dbg_movement)
1474         printf("Not yet implemented\n");
1475     default:
1476       ASSERT(p->request->type != REQUEST_INVALID);
1477   }
1478 }
1479
1480 void move_symbol_point(struct placement *p)
1481 {
1482   p->x += (double) (move_min + randdouble()) * flip(1, -1);
1483   p->y += (double) (move_min + randdouble()) * flip(1, -1);
1484 }
1485
1486 void hide_segment_labels(struct individual *individual)
1487 {
1488   // BEWARE: This fully depends on current genetic encoding
1489
1490   int used = -1, num = -1;
1491   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1492   {
1493     switch (individual->placements[i].request->type)
1494     {
1495       case REQUEST_SECTION:
1496         used = individual->placements[i].variant_used;
1497         num = 0;
1498         break;
1499       case REQUEST_SEGMENT:
1500         if (num == used)
1501           individual->placements[i].variant_used = 0;
1502         else
1503           individual->placements[i].variant_used = -1;
1504         num++;
1505         break;
1506       default:
1507         ;
1508     }
1509   }
1510 }
1511
1512 void init_placement(struct placement *p, struct individual *individual, struct request *r)
1513 {
1514   // FIXME
1515   p->request = r;
1516   p->processed = 0;
1517   p->x = p->y = 0; // To prevent valgrind from complaining
1518   p->variant_used = 0;
1519   p->map_links = NULL;
1520   p->individual = individual;
1521   switch (r->type)
1522   {
1523     case REQUEST_POINT: ;
1524       struct request_point *rp = (struct request_point *) r;
1525       p->x = rp->x;
1526       p->y = rp->y;
1527       break;
1528     case REQUEST_LINE: ;
1529       break;
1530     case REQUEST_SECTION: ;
1531       struct request_section *rls = (struct request_section *) r;
1532       p->variant_used = randint(0, rls->num_segments);
1533       break;
1534     case REQUEST_SEGMENT: ;
1535       struct request_segment *rs = (struct request_segment *) r;
1536       p->x = rs->x2;
1537       p->y = rs->y2;
1538       break;
1539     case REQUEST_AREA: ;
1540       struct request_area *ra = (struct request_area *) r;
1541       p->x = ra->cx;
1542       p->y = ra->cy;
1543       p->variant_used = 0;
1544       break;
1545     default:
1546       ASSERT(p->request->type != REQUEST_INVALID);
1547       printf("Valid request: %d\n", p->request->type);
1548   }
1549
1550   gen_coords(p);
1551   if (dbg_init)
1552     printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y);
1553 }
1554
1555 void init_individual(struct individual *i)
1556 {
1557 //printf("Initing individual\n");
1558   GARY_INIT(i->placements, num_requests);
1559   GARY_INIT(i->map, 0);
1560   for (uns j=0; j<num_map_parts; j++)
1561   {
1562     struct map_part *part = GARY_PUSH(i->map);
1563     GARY_INIT(part->placement, 0);
1564     struct map_placement *mp = GARY_PUSH(part->placement);
1565     mp->placement = &dummy_placement;
1566     mp->next = mp->prev = NULL;
1567   }
1568   i->penalty = 0; // FIXME
1569
1570   if (dbg_init)
1571     printf("Individual inited, has %u map parts\n", GARY_SIZE(i->map));
1572 }
1573
1574 struct placement **get_overlapping(struct placement *p UNUSED)
1575 {
1576   struct placement **buffer;
1577   GARY_INIT(buffer, 0);
1578   return buffer;
1579 }
1580
1581 void filter(struct placement **list UNUSED, bool *pred UNUSED)
1582 {
1583   // FIXME
1584 }
1585
1586 int flip(int a, int b)
1587 {
1588   return (random() % 2 ? a : b);
1589 }
1590
1591 double randdouble(void)
1592 {
1593   // FIXME: How the hell shall double in range <0, 1> be generated? O:)
1594   return 0.5;
1595 }
1596
1597 void cleanup(void)
1598 {
1599   hash_cleanup();
1600   GARY_FREE(requests_point);
1601   GARY_FREE(requests_line);
1602   GARY_FREE(requests_area);
1603 }
1604
1605 void copy_individual(struct individual *src, struct individual *dest)
1606 {
1607   src->penalty = dest->penalty;
1608   GARY_INIT(dest->placements, GARY_SIZE(src->placements));
1609   for (uns i=0; i<GARY_SIZE(src->placements); i++)
1610   {
1611     dest->placements[i] = src->placements[i];
1612   }
1613 }