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     if (individual->placements[i].variant_used < 0) continue;
 953     switch (individual->placements[i].request->type)
 954     {
 955       case REQUEST_POINT: ;
 956         struct request_point *rp = (struct request_point *) individual->placements[i].request;
 957         s = rp->sym;
 958         zindex = rp->zindex;
 959         break;
 960       case REQUEST_SEGMENT: ;
 961         struct request_segment *rs = (struct request_segment *) individual->placements[i].request;
 962         s = rs->label;
 963         zindex = rs->zindex;
 964         break;
 965       case REQUEST_LINE: ;
 966         break;
 967       case REQUEST_AREA: ;
 968         struct request_area *ra = (struct request_area *) individual->placements[i].request;
 969         s = ra->label;
 970         zindex = ra->zindex;
 971         break;
 972       default:
 973         ASSERT(individual->placements[i].request != REQUEST_INVALID);
 974         continue;
 975     }
 976
 977 if (dbg_plan)
 978   printf("Will plan symbol at [%.2f; %.2f] on %u\n", individual->placements[i].x, individual->placements[i].y, zindex);
 979
 980     if (s) switch (s->type)
 981     {
 982       case SYMBOLIZER_POINT: ;
 983         struct sym_point *sp = (struct sym_point *) s;
 984         sp->x = individual->placements[i].x;
 985         sp->y = individual->placements[i].y;
 986         sym_plan((struct symbol *) sp, zindex);
 987         break;
 988       case SYMBOLIZER_ICON: ;
 989         struct sym_icon *si = (struct sym_icon *) s;
 990         si->sir.x = individual->placements[i].x;
 991         si->sir.y = individual->placements[i].y;
 992         sym_plan((struct symbol *) si, zindex);
 993         break;
 994       case SYMBOLIZER_TEXT: ;
 995         struct sym_text *st = (struct sym_text *) s;
 996         st->x = individual->placements[i].x;
 997         st->y = individual->placements[i].y;
 998         st->next_duplicate = NULL;
 999         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);
1000         sym_plan((struct symbol *) st, zindex);
1001         break;
1002       default:
1003         ASSERT(s->type != SYMBOLIZER_INVALID);
1004     }
1005   }
1006
1007 }
1008
1009 void labeller_label(void)
1010 {
1011   make_graph();
1012   label_graph();
1013 //dump_graph();
1014   bfs_wrapper();
1015 //dump_longlines();
1016   make_segments();
1017 dump_linelabel_requests();
1018
1019 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));
1020
1021   GARY_INIT(population1, conf_pop_size);
1022   GARY_INIT(population2, conf_pop_size);
1023   make_population();
1024
1025   printf("Dealing with %d requests\n", num_requests);
1026
1027 /*
1028   while (! shall_terminate())
1029   {
1030     iteration++;
1031
1032     struct individual **swp = population1;
1033     population1 = population2;
1034     population2 = swp;
1035     pop2_ind = 0;
1036   }
1037 */
1038
1039   dump_individual(population1[0]);
1040 //dump_bitmaps(population1[0]);
1041
1042   plan_individual(population1[0]);
1043
1044   labeller_cleanup();
1045
1046   return;
1047 }
1048
1049 void labeller_cleanup(void)
1050 {
1051 }
1052
1053 void make_population(void)
1054 {
1055   for (int i=0; i<conf_pop_size; i++)
1056   {
1057     printf("Making individual %d\n", i);
1058     struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
1059     population1[i] = individual;
1060
1061     int p = 0;
1062     for (uns j=0; j<GARY_SIZE(requests_point); j++)
1063     {
1064       init_placement(&(individual->placements[p++]), (struct request *) &requests_point[j]);
1065     }
1066
1067     for (uns j=0; j<GARY_SIZE(requests_line); j++)
1068     {
1069       init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j]);
1070
1071       for (uns k=0; k<GARY_SIZE(requests_line[j].sections); k++)
1072       {
1073         init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j].sections[k]);
1074
1075         for (uns l=0; l<GARY_SIZE(requests_line[j].sections[k].segments); l++)
1076         {
1077           init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j].sections[k].segments[l]);
1078         }
1079       }
1080     }
1081
1082     for (uns j=0; j<GARY_SIZE(requests_area); j++)
1083     {
1084       init_placement(&(individual->placements[p++]), (struct request *) &requests_area[j]);
1085     }
1086
1087 if (p != num_requests)
1088 {
1089   printf("Say bye\n");
1090   exit(42);
1091 }
1092
1093 printf("Testing p\n");
1094     ASSERT(p == num_requests);
1095   }
1096 }
1097
1098 bool shall_terminate(void)
1099 {
1100   switch (conf_term_cond)
1101   {
1102     case TERM_COND_PENALTY:
1103       return (population1[0]->penalty < conf_penalty_bound);
1104     case TERM_COND_STAGNATION:
1105       return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
1106     case TERM_COND_ITERATIONS:
1107       return (iteration >= conf_iteration_limit);
1108     default:
1109       // FIXME: Warn the user that no condition is set
1110       return 1;
1111   }
1112 }
1113
1114 void breed(void)
1115 {
1116   int acc = 0;
1117   int i=0;
1118   printf("%.2f\n", ((double) conf_breed_pop_size_perc/100));
1119   int conf_breed_pop_size = ((double) conf_breed_pop_size_perc/100) * conf_pop_size;
1120   struct individual **breed_buffer;
1121   while (i < conf_breed_pop_size)
1122   {
1123   printf("%d < %d, breeding\n", i, conf_breed_pop_size);
1124     int parent1 = randint(1, conf_breed_pop_size);
1125     int parent2 = randint(1, conf_breed_pop_size);
1126     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);
1127     breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
1128     population2[pop2_ind++] = breed_buffer[0];
1129     population2[pop2_ind++] = breed_buffer[1];
1130     free(breed_buffer);
1131     i++;
1132   }
1133
1134   acc += conf_breed_rbest_perc;
1135
1136   return; // FIXME: DEBUG HACK
1137
1138   int remaining = (1 - acc) * (conf_pop_size * conf_breed_perc);
1139   int step = remaining / conf_pop_size;
1140   for (; i<conf_pop_size; i += 2)
1141   {
1142     printf("Asking for %d and %d of %d\n", i*step, i*(step+1), conf_pop_size);
1143     breed_buffer = perform_crossover(population1[i*step], population1[i*step+1]);
1144     population2[pop2_ind++] = breed_buffer[0];
1145     population2[pop2_ind++] = breed_buffer[1];
1146   }
1147
1148   // FIXME: Could there be one missing individual?
1149 }
1150
1151 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
1152 {
1153   struct individual **buffer = malloc(2*sizeof(struct individual));
1154   struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
1155   struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
1156
1157   printf("Performing crossover\n");
1158
1159   for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
1160   {
1161     printf("%dth placement out of %d\n", i, num_requests);
1162     if (! parent1->placements[i].processed)
1163     {
1164       struct placement **clos_symbols = get_closure(&(parent1->placements[i]), parent1, parent2);
1165       int x = randint(1, 2);
1166
1167       if (x == 1)
1168       {
1169         copy_symbols(clos_symbols, parent1, child1);
1170         copy_symbols(clos_symbols, parent2, child2);
1171       }
1172       else
1173       {
1174         copy_symbols(clos_symbols, parent2, child1);
1175         copy_symbols(clos_symbols, parent1, child2);
1176       }
1177       printf("Symbols copied; %lld\n", GARY_SIZE(clos_symbols));
1178       GARY_FREE(clos_symbols);
1179     }
1180
1181     if (conf_mutate_children)
1182     {
1183       if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child1);
1184       if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child2);
1185     }
1186   }
1187
1188   buffer[0] = child1;
1189   buffer[1] = child2;
1190   return buffer;
1191 }
1192
1193 void mutate(void)
1194 {
1195   int i = 0;
1196   int conf_mutate_pop_size = conf_mutate_pop_size_perc * conf_pop_size;
1197   while (i < conf_mutate_rbest_perc * conf_pop_size)
1198   {
1199     int ind = randint(1, conf_mutate_pop_size);
1200     copy_individual(population2[pop2_ind], population1[ind]);
1201     perform_mutation(population2[pop2_ind]);
1202     pop2_ind++;
1203   }
1204 }
1205
1206 void perform_mutation(struct individual *individual)
1207 {
1208   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1209   {
1210     int x = randint(1, 1000);
1211     int acc = 0;
1212
1213     if (x <= acc + conf_mutate_move_bound)
1214     {
1215       move_symbol(&(individual->placements[i]));
1216       continue;
1217     }
1218     acc += conf_mutate_move_bound;
1219
1220     if (x <= acc + conf_mutate_regen_bound)
1221     {
1222       gen_coords(&(individual->placements[i]));
1223       continue;
1224     }
1225     acc += conf_mutate_regen_bound;
1226
1227     if (x <= acc + conf_mutate_chvar_bound)
1228     {
1229       if (0) // if num_variants > 1
1230       {
1231         // FIXME: assign new variant
1232       }
1233     }
1234   }
1235 }
1236
1237 void elite(void)
1238 {
1239   for (int i=0; i<conf_elite_perc * conf_pop_size; i++)
1240   {
1241     population2[pop2_ind++] = population1[0];
1242   }
1243 }
1244
1245 void rank_population(void)
1246 {
1247   // FIXME
1248 }
1249
1250 void gen_coords(struct placement *p)
1251 {
1252   switch(p->request->type)
1253   {
1254     case REQUEST_POINT:
1255       gen_coords_point(p);
1256       break;
1257     case REQUEST_AREA:
1258       gen_coords_area(p);
1259       break;
1260     case REQUEST_SEGMENT:
1261       gen_coords_segment(p);
1262       break;
1263     case REQUEST_LINE:
1264       printf("Not yet implemented\n");
1265       break;
1266     default:
1267       printf("Testing request type\n");
1268       ASSERT(p->request->type != REQUEST_INVALID);
1269   }
1270 }
1271
1272 double gen_movement(void)
1273 {
1274   double m = (random() % 1000000) / 10000;
1275   m = pow(m, 1.0/3) * flip(1, -1);
1276   printf("Movement %.2f\n", m);
1277   return m;
1278 }
1279
1280 void gen_coords_point(struct placement *p)
1281 {
1282   p->x = p->x + gen_movement();
1283 }
1284
1285 void gen_coords_segment(struct placement *p)
1286 {
1287   struct request_segment *rs = (struct request_segment *) p->request;
1288   int a = flip(1, 2);
1289   p->x = (a == 1 ? rs->x1 : rs->x2);
1290   p->y = (a == 1 ? rs->y1 : rs->y2);
1291 }
1292
1293 void gen_coords_area(struct placement *p)
1294 {
1295   struct request_area *ra = (struct request_area *) p->request;
1296
1297   p->x = p->x + gen_movement();
1298   p->y = p->y + gen_movement();
1299
1300   printf("Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
1301 }
1302
1303 struct map_part **get_parts(struct placement *symbol, struct individual *individual)
1304 {
1305   struct map_part **buffer;
1306   GARY_INIT(buffer, 0);
1307   int x_min = symbol->x / conf_part_size;
1308   int x_max = (symbol->x /*+ symbol->bitmap->width*/ + conf_part_size - 1) / conf_part_size;
1309   int y_min = symbol->y / conf_part_size;
1310   int y_max = (symbol->y /*+ symbol->bitmap->height*/ + conf_part_size - 1) / conf_part_size;
1311
1312   for (int x=x_min; x < x_max; x++)
1313     for (int y=y_min; y < y_max; y++)
1314     {
1315       struct map_part *m = GARY_PUSH(buffer);
1316       *m = individual->map[x][y];
1317     }
1318
1319   return buffer;
1320 }
1321
1322 int randint(int min, int max)
1323 {
1324   if (min == max) return min;
1325   int r = random();
1326   //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)));
1327   return min + (r % (max - min));
1328   return (r * (max - min));
1329 }
1330
1331 struct placement **get_closure(struct placement *placement, struct individual *parent1, struct individual *parent2 UNUSED)
1332 {
1333   printf("Getting closure\n");
1334   struct placement **closure;
1335   GARY_INIT(closure, 0);
1336   bool *chosen = malloc(GARY_SIZE(parent1->placements) * sizeof(bool));
1337   chosen[placement->request->ind] = 1;
1338
1339   struct placement **p = GARY_PUSH(closure); *p = placement;
1340
1341   uns first = 0;
1342   while (first < GARY_SIZE(closure))
1343   {
1344     printf("Iterating, first is %d\n", first);
1345     struct placement **overlapping = get_overlapping(placement);
1346     filter(overlapping, chosen);
1347     for (uns j=0; j<GARY_SIZE(overlapping); j++)
1348     {
1349       p = GARY_PUSH(closure); *p = overlapping[j];
1350       chosen[overlapping[j]->request->ind] = 1;
1351     }
1352     GARY_FREE(overlapping);
1353     first++;
1354   }
1355
1356   return closure;
1357 }
1358
1359 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child)
1360 {
1361   //printf("%d\n", child->penalty);
1362   //printf("Closure size: %lld\n", GARY_SIZE(closure));
1363   for (uns i=0; i<GARY_SIZE(closure); i++)
1364   {
1365     int ind = closure[i]->request->ind;
1366     child->placements[ind] = parent->placements[ind];
1367     child->placements[ind].processed = 0;
1368   }
1369 }
1370
1371 void move_symbol(struct placement *p)
1372 {
1373   switch (p->request->type)
1374   {
1375     case REQUEST_POINT:
1376       move_symbol_point(p);
1377     case REQUEST_LINE:
1378     case REQUEST_SEGMENT:
1379     case REQUEST_AREA:
1380       printf("Not yet implemented\n");
1381     default:
1382       ASSERT(p->request->type != REQUEST_INVALID);
1383   }
1384 }
1385
1386 void move_symbol_point(struct placement *p)
1387 {
1388   p->x += (double) (move_min + randdouble()) * flip(1, -1);
1389   p->y += (double) (move_min + randdouble()) * flip(1, -1);
1390 }
1391
1392 void init_placement(struct placement *p, struct request *r)
1393 {
1394   // FIXME
1395   p->request = r;
1396   p->processed = 0;
1397   p->x = p->y = 0; // To prevent valgrind from complaining
1398   p->variant_used = 0;
1399   switch (r->type)
1400   {
1401     case REQUEST_POINT: ;
1402       struct request_point *rp = (struct request_point *) r;
1403       p->x = rp->x;
1404       p->y = rp->y;
1405       break;
1406     case REQUEST_LINE: ;
1407       break;
1408     case REQUEST_SECTION: ;
1409       struct request_section *rls = (struct request_section *) r;
1410       p->variant_used = randint(0, rls->num_segments);
1411       break;
1412     case REQUEST_SEGMENT: ;
1413       struct request_segment *rs = (struct request_segment *) r;
1414       p->x = rs->x2;
1415       p->y = rs->y2;
1416       break;
1417     case REQUEST_AREA: ;
1418       struct request_area *ra = (struct request_area *) r;
1419       p->x = ra->cx;
1420       p->y = ra->cy;
1421       p->variant_used = 0;
1422       break;
1423     default:
1424       ASSERT(p->request->type != REQUEST_INVALID);
1425       printf("Valid request: %d\n", p->request->type);
1426   }
1427
1428   gen_coords(p);
1429 //  printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y);
1430 }
1431
1432 void init_individual(struct individual *i)
1433 {
1434 //printf("Initing individual\n");
1435   GARY_INIT(i->placements, num_requests);
1436   GARY_INIT(i->map, 0);
1437   i->penalty = 0; // FIXME
1438 }
1439
1440 struct placement **get_overlapping(struct placement *p UNUSED)
1441 {
1442   struct placement **buffer;
1443   GARY_INIT(buffer, 0);
1444   return buffer;
1445 }
1446
1447 void filter(struct placement **list UNUSED, bool *pred UNUSED)
1448 {
1449   // FIXME
1450 }
1451
1452 int flip(int a, int b)
1453 {
1454   return (random() % 2 ? a : b);
1455 }
1456
1457 double randdouble(void)
1458 {
1459   // FIXME: How the hell shall double in range <0, 1> be generated? O:)
1460   return 0.5;
1461 }
1462
1463 void cleanup(void)
1464 {
1465   hash_cleanup();
1466   GARY_FREE(requests_point);
1467   GARY_FREE(requests_line);
1468   GARY_FREE(requests_area);
1469 }
1470
1471 void copy_individual(struct individual *src, struct individual *dest)
1472 {
1473   src->penalty = dest->penalty;
1474   GARY_INIT(dest->placements, GARY_SIZE(src->placements));
1475   for (uns i=0; i<GARY_SIZE(src->placements); i++)
1476   {
1477     dest->placements[i] = src->placements[i];
1478   }
1479 }