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