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