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       rs->angle = atan2(rs->x2 - rs->x1, rs->y2 - rs->y1);
 801       rs->zindex = e->zindex;
 802
 803       cur_length += e->length;
 804       e = e->next;
 805     }
 806
 807     if (request->sections[0].num_segments == 0)
 808     {
 809       // FIXME
 810       printf("WARNING: 0 segment section\n");
 811       GARY_POP(requests_line);
 812       num_requests -= 2;
 813     }
 814   }
 815 }
 816
 817 void dump_linelabel_requests(void)
 818 {
 819   for (uns i=0; i<GARY_SIZE(requests_line); i++)
 820   {
 821     if (requests_line[i].sections[0].num_segments == 0)
 822     {
 823       printf("HEY!\n");
 824       continue;
 825     }
 826     printf("Request for linelabel, %d sections\n", GARY_SIZE(requests_line[i].sections));
 827     print_label(requests_line[i].sections[0].segments[0].label);
 828     for (uns j=0; j<GARY_SIZE(requests_line[i].sections); j++)
 829     {
 830       printf("%d section, %d segments\n", j, GARY_SIZE(requests_line[i].sections[j].segments));
 831       for (uns k=0; k<GARY_SIZE(requests_line[i].sections[j].segments); k++)
 832       {
 833         struct request_segment *rs = &requests_line[i].sections[j].segments[k];
 834         printf("[%.2f; %.2f] -- [%.2f; %.2f]\n", rs->x1, rs->y1, rs->x2, rs->y2);
 835       }
 836     }
 837     printf("\n");
 838   }
 839 }
 840
 841 void dump_bitmaps(struct individual *individual)
 842 {
 843   bool *bitmap = malloc(page_width_int * page_height_int * sizeof(bool));
 844   printf("Bitmap size is %d\n", page_width_int * page_height_int);
 845   for (int i=0; i<page_height_int; i++)
 846     for (int j=0; j<page_width_int; j++)
 847       bitmap[i*page_width_int + j] = 0;
 848
 849   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 850   {
 851 fprintf(stderr, "%d-th placement\n", i);
 852     struct placement *p = &(individual->placements[i]);
 853     struct point_variant *v = NULL;
 854
 855     switch (p->request->type)
 856     {
 857       case REQUEST_SEGMENT: ;
 858         struct request_segment *rs = (struct request_segment *) p->request;
 859         v = rs->variant;
 860         break;
 861       case REQUEST_POINT: ;
 862         struct request_point *rp = (struct request_point *) p->request;
 863         v = &(rp->variants[p->variant_used]);
 864         break;
 865       case REQUEST_AREA: ;
 866         struct request_area *ra = (struct request_area *) p->request;
 867         printf("Using %d-th of %d variants\n", p->variant_used, GARY_SIZE(ra->variants));
 868         v = &(ra->variants[p->variant_used]);
 869         break;
 870       default:
 871         printf("Testing request type (dump_bitmaps): %d\n", p->request->type);
 872         ASSERT(p->request->type != REQUEST_INVALID);
 873         continue;
 874     }
 875
 876     printf("Got after with %d-th placement of request type %d\n", i, p->request->type);
 877
 878     printf("Rendering %d-th label %d x %d (w x h)\n", i, v->width, v->height);
 879     for (int row = max2(p->y, 0); row < min2(p->y + v->height, page_height_int); row++)
 880     {
 881       for (int col = max2(p->x, 0); col < min2(p->x + v->width, page_width_int); col++)
 882       {
 883         printf("Writing to %d\n", row*page_width_int + col);
 884         bitmap[row * page_width_int + col] = 1;
 885       }
 886     }
 887   }
 888
 889   errno = 0;
 890   FILE *fd_dump = fopen("dump.pbm", "w");
 891   fprintf(fd_dump, "P1\n");
 892   fprintf(fd_dump, "%d %d\n", page_width_int, page_height_int);
 893   for (int i=0; i<page_height_int; i++)
 894   {
 895     for (int j=0; j<page_width_int; j++)
 896     {
 897       fprintf(fd_dump, "%d", bitmap[(int) (i*page_width_int + j)] ? 1 : 0);
 898     }
 899     fprintf(fd_dump, "\n");
 900   }
 901   fclose(fd_dump);
 902 }
 903
 904 void dump_individual(struct individual *individual)
 905 {
 906 printf("*** Dumping INDIVIDUAL ***\n");
 907 printf("(There are %d requests)\n", num_requests);
 908   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 909   {
 910     struct placement *p = &(individual->placements[i]);
 911
 912     switch (p->request->type)
 913     {
 914       case REQUEST_POINT:
 915         printf("Point at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_point *) p->request)->zindex);
 916         break;
 917       case REQUEST_LINE: ;
 918         struct request_line *rl = (struct request_line *) p->request;
 919         printf("Line: ");
 920         print_label(rl->sections[0].segments[0].label);
 921         break;
 922       case REQUEST_SECTION: ;
 923         printf("*");
 924         break;
 925       case REQUEST_SEGMENT: ;
 926         if (p->variant_used >= 0)
 927           printf("Segment placed at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_segment *) p->request)->zindex);
 928         else
 929           printf("Segment not placed\n");
 930         break;
 931       case REQUEST_AREA: ;
 932         struct request_area *ra = (struct request_area *) p->request;
 933         printf("Area label ");
 934         print_label(ra->label);
 935         printf(" at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_area *) p->request)->zindex);
 936         break;
 937       default:
 938         printf("Testing request type (dump_individual)\n");
 939         ASSERT(p->request->type != 0);
 940     }
 941   }
 942   printf("\nTotal penalty: %d\n", individual->penalty);
 943 }
 944
 945 void plan_individual(struct individual *individual)
 946 {
 947   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 948   {
 949     struct symbol *s = NULL;
 950     z_index_t zindex = 0;
 951     switch (individual->placements[i].request->type)
 952     {
 953       case REQUEST_POINT: ;
 954         struct request_point *rp = (struct request_point *) individual->placements[i].request;
 955         s = rp->sym;
 956         zindex = rp->zindex;
 957         break;
 958       case REQUEST_SEGMENT: ;
 959         struct request_segment *rs = (struct request_segment *) individual->placements[i].request;
 960         s = rs->label;
 961         zindex = rs->zindex;
 962         break;
 963       case REQUEST_LINE: ;
 964         break;
 965       case REQUEST_AREA: ;
 966         struct request_area *ra = (struct request_area *) individual->placements[i].request;
 967         s = ra->label;
 968         zindex = ra->zindex;
 969         break;
 970       default:
 971         ASSERT(individual->placements[i].request != REQUEST_INVALID);
 972         continue;
 973     }
 974
 975 if (dbg_plan)
 976   printf("Will plan symbol at [%.2f; %.2f] on %u\n", individual->placements[i].x, individual->placements[i].y, zindex);
 977
 978     if (s) switch (s->type)
 979     {
 980       case SYMBOLIZER_POINT: ;
 981         struct sym_point *sp = (struct sym_point *) s;
 982         sp->x = individual->placements[i].x;
 983         sp->y = individual->placements[i].y;
 984         sym_plan((struct symbol *) sp, zindex);
 985         break;
 986       case SYMBOLIZER_ICON: ;
 987         struct sym_icon *si = (struct sym_icon *) s;
 988         si->sir.x = individual->placements[i].x;
 989         si->sir.y = individual->placements[i].y;
 990         sym_plan((struct symbol *) si, zindex);
 991         break;
 992       case SYMBOLIZER_TEXT: ;
 993         struct sym_text *st = (struct sym_text *) s;
 994         st->x = individual->placements[i].x;
 995         st->y = individual->placements[i].y;
 996         st->next_duplicate = NULL;
 997         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);
 998         sym_plan((struct symbol *) st, zindex);
 999         break;
1000       default:
1001         ASSERT(s->type != SYMBOLIZER_INVALID);
1002     }
1003   }
1004
1005 }
1006
1007 void labeller_label(void)
1008 {
1009   make_graph();
1010   label_graph();
1011 //dump_graph();
1012   bfs_wrapper();
1013 //dump_longlines();
1014   make_segments();
1015 dump_linelabel_requests();
1016
1017 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));
1018
1019   GARY_INIT(population1, conf_pop_size);
1020   GARY_INIT(population2, conf_pop_size);
1021   make_population();
1022
1023   printf("Dealing with %d requests\n", num_requests);
1024
1025 /*
1026   while (! shall_terminate())
1027   {
1028     iteration++;
1029
1030     struct individual **swp = population1;
1031     population1 = population2;
1032     population2 = swp;
1033     pop2_ind = 0;
1034   }
1035 */
1036
1037   dump_individual(population1[0]);
1038 //dump_bitmaps(population1[0]);
1039
1040   plan_individual(population1[0]);
1041
1042   labeller_cleanup();
1043
1044   return;
1045 }
1046
1047 void labeller_cleanup(void)
1048 {
1049 }
1050
1051 void make_population(void)
1052 {
1053   for (int i=0; i<conf_pop_size; i++)
1054   {
1055     printf("Making individual %d\n", i);
1056     struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
1057     population1[i] = individual;
1058
1059     int p = 0;
1060     for (uns j=0; j<GARY_SIZE(requests_point); j++)
1061     {
1062       init_placement(&(individual->placements[p++]), (struct request *) &requests_point[j]);
1063     }
1064
1065     for (uns j=0; j<GARY_SIZE(requests_line); j++)
1066     {
1067       init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j]);
1068
1069       for (uns k=0; k<GARY_SIZE(requests_line[j].sections); k++)
1070       {
1071         init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j].sections[k]);
1072
1073         for (uns l=0; l<GARY_SIZE(requests_line[j].sections[k].segments); l++)
1074         {
1075           init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j].sections[k].segments[l]);
1076         }
1077       }
1078     }
1079
1080     for (uns j=0; j<GARY_SIZE(requests_area); j++)
1081     {
1082       init_placement(&(individual->placements[p++]), (struct request *) &requests_area[j]);
1083     }
1084
1085 if (p != num_requests)
1086 {
1087   printf("Say bye\n");
1088   exit(42);
1089 }
1090
1091 printf("Testing p\n");
1092     ASSERT(p == num_requests);
1093   }
1094 }
1095
1096 bool shall_terminate(void)
1097 {
1098   switch (conf_term_cond)
1099   {
1100     case TERM_COND_PENALTY:
1101       return (population1[0]->penalty < conf_penalty_bound);
1102     case TERM_COND_STAGNATION:
1103       return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
1104     case TERM_COND_ITERATIONS:
1105       return (iteration >= conf_iteration_limit);
1106     default:
1107       // FIXME: Warn the user that no condition is set
1108       return 1;
1109   }
1110 }
1111
1112 void breed(void)
1113 {
1114   int acc = 0;
1115   int i=0;
1116   printf("%.2f\n", ((double) conf_breed_pop_size_perc/100));
1117   int conf_breed_pop_size = ((double) conf_breed_pop_size_perc/100) * conf_pop_size;
1118   struct individual **breed_buffer;
1119   while (i < conf_breed_pop_size)
1120   {
1121   printf("%d < %d, breeding\n", i, conf_breed_pop_size);
1122     int parent1 = randint(1, conf_breed_pop_size);
1123     int parent2 = randint(1, conf_breed_pop_size);
1124     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);
1125     breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
1126     population2[pop2_ind++] = breed_buffer[0];
1127     population2[pop2_ind++] = breed_buffer[1];
1128     free(breed_buffer);
1129     i++;
1130   }
1131
1132   acc += conf_breed_rbest_perc;
1133
1134   return; // FIXME: DEBUG HACK
1135
1136   int remaining = (1 - acc) * (conf_pop_size * conf_breed_perc);
1137   int step = remaining / conf_pop_size;
1138   for (; i<conf_pop_size; i += 2)
1139   {
1140     printf("Asking for %d and %d of %d\n", i*step, i*(step+1), conf_pop_size);
1141     breed_buffer = perform_crossover(population1[i*step], population1[i*step+1]);
1142     population2[pop2_ind++] = breed_buffer[0];
1143     population2[pop2_ind++] = breed_buffer[1];
1144   }
1145
1146   // FIXME: Could there be one missing individual?
1147 }
1148
1149 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
1150 {
1151   struct individual **buffer = malloc(2*sizeof(struct individual));
1152   struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
1153   struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
1154
1155   printf("Performing crossover\n");
1156
1157   for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
1158   {
1159     printf("%dth placement out of %d\n", i, num_requests);
1160     if (! parent1->placements[i].processed)
1161     {
1162       struct placement **clos_symbols = get_closure(&(parent1->placements[i]), parent1, parent2);
1163       int x = randint(1, 2);
1164
1165       if (x == 1)
1166       {
1167         copy_symbols(clos_symbols, parent1, child1);
1168         copy_symbols(clos_symbols, parent2, child2);
1169       }
1170       else
1171       {
1172         copy_symbols(clos_symbols, parent2, child1);
1173         copy_symbols(clos_symbols, parent1, child2);
1174       }
1175       printf("Symbols copied; %lld\n", GARY_SIZE(clos_symbols));
1176       GARY_FREE(clos_symbols);
1177     }
1178
1179     if (conf_mutate_children)
1180     {
1181       if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child1);
1182       if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child2);
1183     }
1184   }
1185
1186   buffer[0] = child1;
1187   buffer[1] = child2;
1188   return buffer;
1189 }
1190
1191 void mutate(void)
1192 {
1193   int i = 0;
1194   int conf_mutate_pop_size = conf_mutate_pop_size_perc * conf_pop_size;
1195   while (i < conf_mutate_rbest_perc * conf_pop_size)
1196   {
1197     int ind = randint(1, conf_mutate_pop_size);
1198     copy_individual(population2[pop2_ind], population1[ind]);
1199     perform_mutation(population2[pop2_ind]);
1200     pop2_ind++;
1201   }
1202 }
1203
1204 void perform_mutation(struct individual *individual)
1205 {
1206   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
1207   {
1208     int x = randint(1, 1000);
1209     int acc = 0;
1210
1211     if (x <= acc + conf_mutate_move_bound)
1212     {
1213       move_symbol(&(individual->placements[i]));
1214       continue;
1215     }
1216     acc += conf_mutate_move_bound;
1217
1218     if (x <= acc + conf_mutate_regen_bound)
1219     {
1220       gen_coords(&(individual->placements[i]));
1221       continue;
1222     }
1223     acc += conf_mutate_regen_bound;
1224
1225     if (x <= acc + conf_mutate_chvar_bound)
1226     {
1227       if (0) // if num_variants > 1
1228       {
1229         // FIXME: assign new variant
1230       }
1231     }
1232   }
1233 }
1234
1235 void elite(void)
1236 {
1237   for (int i=0; i<conf_elite_perc * conf_pop_size; i++)
1238   {
1239     population2[pop2_ind++] = population1[0];
1240   }
1241 }
1242
1243 void rank_population(void)
1244 {
1245   // FIXME
1246 }
1247
1248 void gen_coords(struct placement *p)
1249 {
1250   switch(p->request->type)
1251   {
1252     case REQUEST_POINT:
1253       gen_coords_point(p);
1254       break;
1255     case REQUEST_AREA:
1256       gen_coords_area(p);
1257       break;
1258     case REQUEST_SEGMENT:
1259       gen_coords_segment(p);
1260       break;
1261     case REQUEST_LINE:
1262       printf("Not yet implemented\n");
1263       break;
1264     default:
1265       printf("Testing request type\n");
1266       ASSERT(p->request->type != REQUEST_INVALID);
1267   }
1268 }
1269
1270 double gen_movement(void)
1271 {
1272   double m = (random() % 1000000) / 10000;
1273   m = pow(m, 1.0/3) * flip(1, -1);
1274   printf("Movement %.2f\n", m);
1275   return m;
1276 }
1277
1278 void gen_coords_point(struct placement *p)
1279 {
1280   p->x = p->x + gen_movement();
1281 }
1282
1283 void gen_coords_segment(struct placement *p)
1284 {
1285   struct request_segment *rs = (struct request_segment *) p->request;
1286   int a = flip(1, 2);
1287   p->x = (a == 1 ? rs->x1 : rs->x2);
1288   p->y = (a == 1 ? rs->y1 : rs->y2);
1289 }
1290
1291 void gen_coords_area(struct placement *p)
1292 {
1293   struct request_area *ra = (struct request_area *) p->request;
1294
1295   p->x = p->x + gen_movement();
1296   p->y = p->y + gen_movement();
1297
1298   printf("Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
1299 }
1300
1301 struct map_part **get_parts(struct placement *symbol, struct individual *individual)
1302 {
1303   struct map_part **buffer;
1304   GARY_INIT(buffer, 0);
1305   int x_min = symbol->x / conf_part_size;
1306   int x_max = (symbol->x /*+ symbol->bitmap->width*/ + conf_part_size - 1) / conf_part_size;
1307   int y_min = symbol->y / conf_part_size;
1308   int y_max = (symbol->y /*+ symbol->bitmap->height*/ + conf_part_size - 1) / conf_part_size;
1309
1310   for (int x=x_min; x < x_max; x++)
1311     for (int y=y_min; y < y_max; y++)
1312     {
1313       struct map_part *m = GARY_PUSH(buffer);
1314       *m = individual->map[x][y];
1315     }
1316
1317   return buffer;
1318 }
1319
1320 int randint(int min, int max)
1321 {
1322   if (min == max) return min;
1323   int r = random();
1324   //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)));
1325   return min + (r % (max - min));
1326   return (r * (max - min));
1327 }
1328
1329 struct placement **get_closure(struct placement *placement, struct individual *parent1, struct individual *parent2 UNUSED)
1330 {
1331   printf("Getting closure\n");
1332   struct placement **closure;
1333   GARY_INIT(closure, 0);
1334   bool *chosen = malloc(GARY_SIZE(parent1->placements) * sizeof(bool));
1335   chosen[placement->request->ind] = 1;
1336
1337   struct placement **p = GARY_PUSH(closure); *p = placement;
1338
1339   uns first = 0;
1340   while (first < GARY_SIZE(closure))
1341   {
1342     printf("Iterating, first is %d\n", first);
1343     struct placement **overlapping = get_overlapping(placement);
1344     filter(overlapping, chosen);
1345     for (uns j=0; j<GARY_SIZE(overlapping); j++)
1346     {
1347       p = GARY_PUSH(closure); *p = overlapping[j];
1348       chosen[overlapping[j]->request->ind] = 1;
1349     }
1350     GARY_FREE(overlapping);
1351     first++;
1352   }
1353
1354   return closure;
1355 }
1356
1357 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child)
1358 {
1359   //printf("%d\n", child->penalty);
1360   //printf("Closure size: %lld\n", GARY_SIZE(closure));
1361   for (uns i=0; i<GARY_SIZE(closure); i++)
1362   {
1363     int ind = closure[i]->request->ind;
1364     child->placements[ind] = parent->placements[ind];
1365     child->placements[ind].processed = 0;
1366   }
1367 }
1368
1369 void move_symbol(struct placement *p)
1370 {
1371   switch (p->request->type)
1372   {
1373     case REQUEST_POINT:
1374       move_symbol_point(p);
1375     case REQUEST_LINE:
1376     case REQUEST_SEGMENT:
1377     case REQUEST_AREA:
1378       printf("Not yet implemented\n");
1379     default:
1380       ASSERT(p->request->type != REQUEST_INVALID);
1381   }
1382 }
1383
1384 void move_symbol_point(struct placement *p)
1385 {
1386   p->x += (double) (move_min + randdouble()) * flip(1, -1);
1387   p->y += (double) (move_min + randdouble()) * flip(1, -1);
1388 }
1389
1390 void init_placement(struct placement *p, struct request *r)
1391 {
1392   // FIXME
1393   p->request = r;
1394   p->processed = 0;
1395   p->x = p->y = 0; // To prevent valgrind from complaining
1396   p->variant_used = 0;
1397   switch (r->type)
1398   {
1399     case REQUEST_POINT: ;
1400       struct request_point *rp = (struct request_point *) r;
1401       p->x = rp->x;
1402       p->y = rp->y;
1403       break;
1404     case REQUEST_LINE: ;
1405       break;
1406     case REQUEST_SECTION: ;
1407       struct request_section *rls = (struct request_section *) r;
1408       p->variant_used = randint(0, rls->num_segments);
1409       break;
1410     case REQUEST_SEGMENT: ;
1411       struct request_segment *rs = (struct request_segment *) r;
1412       p->x = rs->x2;
1413       p->y = rs->y2;
1414       break;
1415     case REQUEST_AREA: ;
1416       struct request_area *ra = (struct request_area *) r;
1417       p->x = ra->cx;
1418       p->y = ra->cy;
1419       p->variant_used = 0;
1420       break;
1421     default:
1422       ASSERT(p->request->type != REQUEST_INVALID);
1423       printf("Valid request: %d\n", p->request->type);
1424   }
1425
1426   gen_coords(p);
1427 //  printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y);
1428 }
1429
1430 void init_individual(struct individual *i)
1431 {
1432 //printf("Initing individual\n");
1433   GARY_INIT(i->placements, num_requests);
1434   GARY_INIT(i->map, 0);
1435   i->penalty = 0; // FIXME
1436 }
1437
1438 struct placement **get_overlapping(struct placement *p UNUSED)
1439 {
1440   struct placement **buffer;
1441   GARY_INIT(buffer, 0);
1442   return buffer;
1443 }
1444
1445 void filter(struct placement **list UNUSED, bool *pred UNUSED)
1446 {
1447   // FIXME
1448 }
1449
1450 int flip(int a, int b)
1451 {
1452   return (random() % 2 ? a : b);
1453 }
1454
1455 double randdouble(void)
1456 {
1457   // FIXME: How the hell shall double in range <0, 1> be generated? O:)
1458   return 0.5;
1459 }
1460
1461 void cleanup(void)
1462 {
1463   hash_cleanup();
1464   GARY_FREE(requests_point);
1465   GARY_FREE(requests_line);
1466   GARY_FREE(requests_area);
1467 }
1468
1469 void copy_individual(struct individual *src, struct individual *dest)
1470 {
1471   src->penalty = dest->penalty;
1472   GARY_INIT(dest->placements, GARY_SIZE(src->placements));
1473   for (uns i=0; i<GARY_SIZE(src->placements); i++)
1474   {
1475     dest->placements[i] = src->placements[i];
1476   }
1477 }