labeller.c

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