labeller.c

   1 #include <ucw/lib.h>
   2 #include <ucw/gary.h>
   3 #include <ucw/mempool.h>
   4 #include <ucw/eltpool.h>
   5
   6 #include "leo.h"
   7 #include "sym.h"
   8 #include "labeller.h"
   9
  10 #define HASH_NODE struct graph_node
  11 #define HASH_PREFIX(x) hash_##x
  12 #define HASH_KEY_ATOMIC id
  13 #define HASH_WANT_FIND
  14 #define HASH_WANT_NEW
  15 #define HASH_WANT_CLEANUP
  16 #include <ucw/hashtable.h>
  17
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <math.h>
  21
  22 #define BLOCK_SIZE 4096
  23
  24 //struct mempool *mpool_requests;
  25
  26 static struct request_point *requests_point;
  27 static struct request_line *requests_line;
  28 static struct request_area *requests_area;
  29
  30 static struct graph_edge *bfs_queue;
  31 static struct longline *longlines; int num_longlines;
  32 static struct buffer_line *buffer_line;
  33 static struct buffer_linelabel *buffer_linelabel;
  34
  35 struct eltpool *ep_individuals;
  36
  37 struct individual **population1;
  38 struct individual **population2;
  39
  40 int conf_pop_size = 50;
  41
  42 int conf_penalty_bound = 0;
  43 int conf_stagnation_bound = 0;
  44 int conf_iteration_limit = 4;
  45
  46 int conf_term_cond = TERM_COND_ITERATIONS;
  47
  48 int conf_breed_rbest_perc = 80;
  49 int conf_breed_pop_size_perc = 20;
  50 int conf_breed_perc = 50;                       // Percentage of new pop created by breeding
  51
  52 bool conf_mutate_children = 1;
  53 int conf_mutate_children_prob = 0.3;
  54
  55 int conf_mutate_rbest_perc = 60;
  56 int conf_mutate_pop_size_perc = 20;
  57
  58 int conf_mutate_move_bound = 0.2;
  59 int conf_mutate_regen_bound = 0.1;
  60 int conf_mutate_chvar_bound = 0.1;
  61
  62 int conf_elite_perc = 5;
  63
  64 int old_best = 0; // FIXME: Shall be int max
  65 int iteration = 0;
  66 int pop2_ind;
  67
  68 int conf_part_size = 50;
  69
  70 int move_min = 0;
  71 int move_max = 1;
  72
  73 int num_requests = 0;
  74
  75 void labeller_init(void)
  76 {
  77 //  mpool_requests = mp_new(BLOCK_SIZE);
  78   GARY_INIT(requests_point, 0);
  79   GARY_INIT(requests_line, 0);
  80   GARY_INIT(requests_area, 0);
  81   GARY_INIT(buffer_line, 0);
  82   GARY_INIT(buffer_linelabel, 0);
  83   ep_individuals = ep_new(sizeof(struct individual), 1);
  84 }
  85
  86 void make_bitmap_icon(struct point_variant *v, struct sym_icon *si)
  87 {
  88   v->width = si->sir.icon->width;
  89   v->height = si->sir.icon->height;
  90   v->bitmap = malloc((int) ceil(v->width * v->height * sizeof(bool)));
  91   for (int i=0; i<v->width*v->height; i++) v->bitmap[i] = 1;
  92 }
  93
  94 void make_bitmap_point(struct point_variant *v, struct sym_point *sp)
  95 {
  96   v->width = v->height = sp->size;
  97   v->bitmap = malloc(sp->size*sp->size * sizeof(bool));
  98   // FIXME: Okay, memset would be much nicer here
  99   for (int i=0; i<sp->size*sp->size; i++) v->bitmap[i] = 1;
 100 }
 101
 102 void make_bitmap_label(struct point_variant *v UNUSED, struct sym_text *text UNUSED)
 103 {
 104 }
 105
 106 void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex)
 107 {
 108 /* FIXME
 109    What does correct check look like?
 110   if (object->type != OSM_TYPE_NODE)
 111   {
 112     // FIXME
 113     return;
 114   }
 115 */
 116
 117   struct request_point *r = GARY_PUSH(requests_point);
 118
 119   r->request.type = REQUEST_POINT;
 120   r->request.ind = num_requests++;
 121
 122   r->sym = sym;
 123   r->object = object;
 124   r->zindex = zindex;
 125
 126   struct osm_node *n = (struct osm_node *) object;
 127   r->x = n->x;
 128   r->y = n->y;
 129
 130   r->offset_x = 0;
 131   r->offset_y = 0;
 132
 133   r->num_variants = 1;
 134   GARY_INIT(r->variants, 0);
 135
 136   struct point_variant *v = GARY_PUSH(r->variants);
 137
 138   switch (sym->type)
 139   {
 140     case SYMBOLIZER_ICON:
 141       make_bitmap_icon(v, (struct sym_icon *) sym);
 142       break;
 143     case SYMBOLIZER_POINT:
 144       make_bitmap_point(v, (struct sym_point *) sym);
 145       break;
 146     default:
 147       // Oops :)
 148       // FIXME
 149       return;
 150   }
 151 }
 152
 153 void labeller_add_line(struct symbol *sym, z_index_t zindex)
 154 {
 155   struct buffer_line *b = GARY_PUSH(buffer_line);
 156   b->line = (struct sym_line *) sym;
 157   b->zindex = zindex;
 158   sym_plan(sym, zindex);
 159 }
 160
 161 void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
 162 {
 163   struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
 164   ll->way = (struct osm_way *) o;
 165   ll->text = (struct sym_text *) sym;
 166   ll->zindex = zindex;
 167 }
 168
 169 void labeller_add_arealabel(struct symbol *sym UNUSED, struct osm_object *o, z_index_t zindex)
 170 {
 171   struct request_area *r = GARY_PUSH(requests_area);
 172
 173   r->request.type = REQUEST_AREALABEL;
 174   r->request.ind = num_requests++;
 175
 176   r->o = (struct osm_multipolygon *) o;
 177   r->zindex = zindex;
 178   r->sym = (struct sym_text *) sym;
 179
 180   GARY_INIT(r->text_variant, 0);
 181   struct point_variant *v = GARY_PUSH(r->text_variant);
 182   make_bitmap_label(v, r->sym);
 183 }
 184
 185 void make_graph(void)
 186 {
 187   hash_init();
 188   struct mempool *mp_edges = mp_new(BLOCK_SIZE);
 189
 190   printf("Extracting nodes, will iterate over %lld ways\n", GARY_SIZE(buffer_line));
 191   for (uns i=0; i<GARY_SIZE(buffer_line); i++)
 192   {
 193     struct osm_way *way = (struct osm_way *) buffer_line[i].line->s.o;
 194     struct graph_node *g_prev = NULL;
 195     struct osm_node *o_prev = NULL;
 196
 197     CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
 198     {
 199       // FIXME: Shall osm_object's type be checked here?
 200       struct osm_node *o_node = (struct osm_node *) ref->o;
 201
 202       struct graph_node *g_node = hash_find(ref->o->id);
 203       if (!g_node)
 204       {
 205         g_node = hash_new(ref->o->id);
 206         GARY_INIT(g_node->edges, 0);
 207         g_node->o = o_node;
 208       }
 209
 210       if (! g_prev)
 211       {
 212         g_prev = g_node;
 213         o_prev = o_node;
 214         continue;
 215       }
 216
 217       struct graph_edge *e = mp_alloc(mp_edges, sizeof(struct graph_edge));
 218       e->id = buffer_line[i].line->s.o->id;
 219       e->color = buffer_line[i].line->color;
 220       e->length = hypot(abs(o_prev->x - o_node->x), abs(o_prev->y - o_node->y));
 221       e->visited = 0;
 222       e->prev = NULL;
 223       e->next = NULL;
 224       e->n1 = g_prev;
 225       e->n2 = g_node;
 226       e->longline = (uns) -1;
 227       e->text = NULL;
 228       e->sym = buffer_line[i].line;
 229
 230       struct graph_edge **edge = GARY_PUSH(g_prev->edges);
 231       *edge = e;
 232       edge = GARY_PUSH(g_node->edges);
 233       *edge = e;
 234     }
 235   }
 236 }
 237
 238 void label_graph(void)
 239 {
 240   for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
 241   {
 242     CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
 243     {
 244       struct graph_node *n = hash_find(ref->o->id);
 245       if (n == NULL)
 246       {
 247         // FIXME: What shall be done?
 248       }
 249       else
 250       {
 251         for (uns j=0; j<GARY_SIZE(n->edges); j++)
 252         {
 253           if (n->edges[j]->id == buffer_linelabel[i].way->o.id)
 254           {
 255             n->edges[j]->text = buffer_linelabel[i].text;
 256             n->edges[j]->zindex = buffer_linelabel[i].zindex;
 257           }
 258         }
 259       }
 260     }
 261   }
 262 }
 263
 264 void join_edge(struct graph_edge *e, int dir)
 265 {
 266   struct graph_node *other_node = NULL;
 267   switch (dir)
 268   {
 269     case 1:
 270       other_node = e->n2;
 271       break;
 272     case 2:
 273       other_node = e->n1;
 274       break;
 275     // FIXME: default?
 276   }
 277
 278   struct graph_edge *candidate = NULL;
 279   for (uns i=0; i<GARY_SIZE(other_node->edges); i++)
 280   {
 281     struct graph_edge *other = other_node->edges[i];
 282     if (! other->visited)
 283     {
 284     struct graph_edge **new = GARY_PUSH(bfs_queue);
 285     *new = other_node->edges[i];
 286     }
 287
 288     if ((!other->visited) && (e->text) && (other->text) && (e->text->text == other->text->text))
 289     {
 290       if (e->color == other_node->edges[i]->color)
 291       {
 292         if ((!candidate) || (candidate->length < other->length))
 293         {
 294           candidate = other;
 295         }
 296       }
 297       else
 298       {
 299         // Beware: Name conflict here
 300       }
 301     }
 302   }
 303
 304   if (candidate)
 305   {
 306     candidate->longline = e->longline;
 307     if (dir == 1)
 308     {
 309       if (candidate->n2 != e->n1)
 310       {
 311         candidate->n1 = candidate->n2;
 312         candidate->n2 = e->n1;
 313       }
 314       e->prev = candidate;
 315       candidate->next = e;
 316
 317       longlines[e->longline].first = candidate;
 318     }
 319     else
 320     {
 321       if (candidate->n1 != e->n2)
 322       {
 323         candidate->n2 = candidate->n1;
 324         candidate->n1 = e->n2;
 325       }
 326       e->next = candidate;
 327       candidate->prev = e;
 328     }
 329   }
 330 }
 331
 332 void bfs(void)
 333 {
 334   GARY_INIT(bfs_queue, 0);
 335   GARY_INIT(longlines, 0);
 336
 337   HASH_FOR_ALL(hash, node)
 338   {
 339     for (uns i=0; i<GARY_SIZE(node->edges); i++)
 340     {
 341       struct graph_edge *e = node->edges[i];
 342
 343 //      printf("Examining edge from [%.2f; %.2f] to [%.2f; %.2f]\n",
 344 //              e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y);
 345
 346       // if (e->visited) HASH_CONTINUE; // FIXME: Is is correct?
 347       if (e->visited) continue;
 348 //      printf("Continuing\n");
 349       if (e->longline == (uns) -1)
 350       {
 351         GARY_PUSH(longlines);
 352         e->longline = num_longlines++;
 353         longlines[e->longline].first = e;
 354       }
 355 //      printf("Longline is %u\n", e->longline);
 356
 357       e->visited = 1;
 358
 359       if (! e->prev)
 360       {
 361         join_edge(e, 1);
 362       }
 363       if (! e->next)
 364       {
 365         join_edge(e, 2);
 366       }
 367     }
 368   }
 369   HASH_END_FOR;
 370
 371   GARY_FREE(bfs_queue);
 372 }
 373
 374 void make_segments(void)
 375 {
 376   for (uns i=0; i<GARY_SIZE(longlines); i++)
 377   {
 378     if (! longlines[i].first->text) continue;
 379 //    printf("Survived! %s\n", osm_val_decode(longlines[i].first->text->text));
 380 printf("New longline\n");
 381     struct request_line *request = GARY_PUSH(requests_line);
 382     request->request.ind = -1;
 383     request->request.type = REQUEST_LINELABEL;
 384
 385     GARY_INIT(request->segments, 0);
 386     request->num_segments = 0;
 387
 388     // ->num_variants FIXME
 389     // ->variants FIXME
 390
 391     struct graph_edge *e = longlines[i].first;
 392
 393     if (! e) printf("Oops\n");
 394     num_requests++;
 395     while (e)
 396     {
 397       if (! e->text) break;
 398       struct request_segment *r = GARY_PUSH(request->segments);
 399       request->num_segments++;
 400
 401       r->request.ind = num_requests++;
 402       r->request.type = REQUEST_SEGMENT;
 403
 404       struct osm_node *n = e->n1->o;
 405       r->x1 = n->x;
 406       r->y1 = n->y;
 407       n = e->n2->o;
 408       r->x2 = n->x;
 409       r->y2 = n->y;
 410       r->k = abs(r->x2 - r->x1) / (abs(r->y2 - r->y1) + 0.001); // FIXME: Hack to prevent floating point exception when y2 = y1
 411
 412 printf("Segment [%.2f; %.2f] -- [%.2f; %.2f]\n", r->x1, r->y1, r->x2, r->y2);
 413
 414       r->sym = e->sym;
 415       r->zindex = e->zindex;
 416       r->text = malloc(sizeof(struct sym_text));
 417       *(r->text) = *(e->text);
 418       r->text->x = r->x1;
 419       r->text->y = r->y1;
 420
 421       r->variant = malloc(sizeof(struct point_variant)); // FIXME
 422       make_bitmap_label(r->variant, e->text);
 423
 424       e = e->next;
 425     }
 426   }
 427 }
 428
 429 void labeller_label(void)
 430 {
 431   make_graph();
 432   label_graph();
 433   bfs();
 434   make_segments();
 435
 436 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));
 437
 438   GARY_INIT(population1, conf_pop_size);
 439   GARY_INIT(population2, conf_pop_size);
 440   make_population();
 441
 442   printf("Dealing with %d requests\n", num_requests);
 443
 444   while (! shall_terminate())
 445   {
 446     iteration++;
 447
 448     struct individual **swp = population1;
 449     population1 = population2;
 450     population2 = swp;
 451     pop2_ind = 0;
 452   }
 453
 454   for (uns i=0; i<GARY_SIZE(population1[0]->placements); i++)
 455   {
 456     switch (population1[0]->placements[i].request->type)
 457     {
 458       case REQUEST_POINT: ;
 459         struct request_point *rp = (struct request_point *) population1[0]->placements[i].request;
 460         switch (rp->sym->type)
 461         {
 462           case SYMBOLIZER_POINT: ;
 463             struct sym_point *sp = (struct sym_point *) rp->sym;
 464             sp->x = i*10;
 465             sp->y = i*10;
 466             sym_plan((struct symbol *) sp, rp->zindex);
 467             break;
 468           case SYMBOLIZER_ICON: ;
 469             struct sym_icon *si = (struct sym_icon *) rp->sym;
 470             si->sir.x = population1[0]->placements[i].x;
 471             si->sir.y = population1[0]->placements[i].y;
 472             sym_plan((struct symbol *) si, rp->zindex);
 473             break;
 474           default:
 475             ;
 476         }
 477         break;
 478       case REQUEST_AREALABEL: ;
 479         struct request_area *ra = (struct request_area *) population1[0]->placements[i].request;
 480         sym_plan((struct symbol *) ra->sym, ra->zindex);
 481         break;
 482
 483       case REQUEST_LINELABEL: ;
 484         struct request_line *rl = (struct request_line *) population1[0]->placements[i].request;
 485         for (uns j=0; j<GARY_SIZE(rl->segments); j++)
 486         {
 487           printf("Planning text %s to [%.2f; %.2f]\n", osm_val_decode(rl->segments[j].text->text), rl->segments[j].text->x, rl->segments[j].text->y);
 488           rl->segments[j].text->next_duplicate = NULL;
 489           rl->segments[j].text->next_in_tile = NULL;
 490           sym_plan((struct symbol *) rl->segments[j].text, rl->segments[j].zindex); // FIXME: z-index
 491         }
 492
 493     }
 494   }
 495
 496   return;
 497
 498   while (! shall_terminate())
 499   {
 500     iteration++;
 501
 502     breed();
 503     mutate();
 504     elite();
 505     rank_population();
 506     // sort population by fitness
 507
 508     struct individual **swp = population1;
 509     population1 = population2;
 510     printf("Swapped populations\n");
 511     population2 = swp;
 512     // GARY_RESIZE(population2, 0) -- is it needed?
 513     pop2_ind = 0;
 514   }
 515 }
 516
 517 void make_population(void)
 518 {
 519   for (int i=0; i<conf_pop_size; i++)
 520   {
 521     struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
 522     population1[i] = individual;
 523
 524     int p = 0;
 525     for (uns j=0; j<GARY_SIZE(requests_point); j++)
 526     {
 527       init_placement(&(individual->placements[p++]), (struct request *) &requests_point[j]);
 528     }
 529     for (uns j=0; j<GARY_SIZE(requests_line); j++)
 530     {
 531       init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j]);
 532       for (uns k=0; k<GARY_SIZE(requests_line[j].segments); k++)
 533       {
 534         init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j].segments[k]);
 535       }
 536     }
 537     for (uns j=0; j<GARY_SIZE(requests_area); j++)
 538     {
 539       init_placement(&(individual->placements[p++]), (struct request *) &requests_area[j]);
 540     }
 541
 542     ASSERT(p == num_requests);
 543   }
 544 }
 545
 546 bool shall_terminate(void)
 547 {
 548   switch (conf_term_cond)
 549   {
 550     case TERM_COND_PENALTY:
 551       return (population1[0]->penalty < conf_penalty_bound);
 552     case TERM_COND_STAGNATION:
 553       return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
 554     case TERM_COND_ITERATIONS:
 555       return (iteration >= conf_iteration_limit);
 556     default:
 557       // FIXME: Warn the user that no condition is set
 558       return 1;
 559   }
 560 }
 561
 562 void breed(void)
 563 {
 564   int acc = 0;
 565   int i=0;
 566   printf("%.2f\n", ((double) conf_breed_pop_size_perc/100));
 567   int conf_breed_pop_size = ((double) conf_breed_pop_size_perc/100) * conf_pop_size;
 568   struct individual **breed_buffer;
 569   while (i < conf_breed_pop_size)
 570   {
 571   printf("%d < %d, breeding\n", i, conf_breed_pop_size);
 572     int parent1 = randint(1, conf_breed_pop_size);
 573     int parent2 = randint(1, conf_breed_pop_size);
 574     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);
 575     breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
 576     population2[pop2_ind++] = breed_buffer[0];
 577     population2[pop2_ind++] = breed_buffer[1];
 578     free(breed_buffer);
 579     i++;
 580   }
 581
 582   acc += conf_breed_rbest_perc;
 583
 584   return; // FIXME: DEBUG HACK
 585
 586   int remaining = (1 - acc) * (conf_pop_size * conf_breed_perc);
 587   int step = remaining / conf_pop_size;
 588   for (; i<conf_pop_size; i += 2)
 589   {
 590     printf("Asking for %d and %d of %d\n", i*step, i*(step+1), conf_pop_size);
 591     breed_buffer = perform_crossover(population1[i*step], population1[i*step+1]);
 592     population2[pop2_ind++] = breed_buffer[0];
 593     population2[pop2_ind++] = breed_buffer[1];
 594   }
 595
 596   // FIXME: Could there be one missing individual?
 597 }
 598
 599 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
 600 {
 601   struct individual **buffer = malloc(2*sizeof(struct individual));
 602   struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
 603   struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
 604
 605   printf("Performing crossover\n");
 606
 607   for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
 608   {
 609     printf("%dth placement out of %d\n", i, num_requests);
 610     if (! parent1->placements[i].processed)
 611     {
 612       struct placement **clos_symbols = get_closure(&(parent1->placements[i]), parent1, parent2);
 613       int x = randint(1, 2);
 614
 615       if (x == 1)
 616       {
 617         copy_symbols(clos_symbols, parent1, child1);
 618         copy_symbols(clos_symbols, parent2, child2);
 619       }
 620       else
 621       {
 622         copy_symbols(clos_symbols, parent2, child1);
 623         copy_symbols(clos_symbols, parent1, child2);
 624       }
 625       printf("Symbols copied; %lld\n", GARY_SIZE(clos_symbols));
 626       GARY_FREE(clos_symbols);
 627     }
 628
 629     if (conf_mutate_children)
 630     {
 631       if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child1);
 632       if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child2);
 633     }
 634   }
 635
 636   buffer[0] = child1;
 637   buffer[1] = child2;
 638   return buffer;
 639 }
 640
 641 void mutate(void)
 642 {
 643   int i = 0;
 644   int conf_mutate_pop_size = conf_mutate_pop_size_perc * conf_pop_size;
 645   while (i < conf_mutate_rbest_perc * conf_pop_size)
 646   {
 647     int ind = randint(1, conf_mutate_pop_size);
 648     copy_individual(population2[pop2_ind], population1[ind]);
 649     perform_mutation(population2[pop2_ind]);
 650     pop2_ind++;
 651   }
 652 }
 653
 654 void perform_mutation(struct individual *individual)
 655 {
 656   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 657   {
 658     int x = randint(1, 1000);
 659     int acc = 0;
 660
 661     if (x <= acc + conf_mutate_move_bound)
 662     {
 663       move_symbol(&(individual->placements[i]));
 664       continue;
 665     }
 666     acc += conf_mutate_move_bound;
 667
 668     if (x <= acc + conf_mutate_regen_bound)
 669     {
 670       gen_coords(&(individual->placements[i]));
 671       continue;
 672     }
 673     acc += conf_mutate_regen_bound;
 674
 675     if (x <= acc + conf_mutate_chvar_bound)
 676     {
 677       if (0) // if num_variants > 1
 678       {
 679         // FIXME: assign new variant
 680       }
 681     }
 682   }
 683 }
 684
 685 void elite(void)
 686 {
 687   for (int i=0; i<conf_elite_perc * conf_pop_size; i++)
 688   {
 689     population2[pop2_ind++] = population1[0];
 690   }
 691 }
 692
 693 void rank_population(void)
 694 {
 695   // FIXME
 696 }
 697
 698 void gen_coords(struct placement *p)
 699 {
 700   switch(p->request->type)
 701   {
 702     case REQUEST_POINT:
 703       gen_coords_point(p);
 704   }
 705 }
 706
 707 void gen_coords_point(struct placement *p UNUSED)
 708 {
 709   // FIXME
 710 }
 711
 712 struct map_part **get_parts(struct placement *symbol, struct individual *individual)
 713 {
 714   struct map_part **buffer;
 715   GARY_INIT(buffer, 0);
 716   int x_min = symbol->x / conf_part_size;
 717   int x_max = (symbol->x /*+ symbol->bitmap->width*/ + conf_part_size - 1) / conf_part_size;
 718   int y_min = symbol->y / conf_part_size;
 719   int y_max = (symbol->y /*+ symbol->bitmap->height*/ + conf_part_size - 1) / conf_part_size;
 720
 721   for (int x=x_min; x < x_max; x++)
 722     for (int y=y_min; y < y_max; y++)
 723     {
 724       struct map_part *m = GARY_PUSH(buffer);
 725       *m = individual->map[x][y];
 726     }
 727
 728   return buffer;
 729 }
 730
 731 int randint(int min, int max)
 732 {
 733   int r = random();
 734   //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)));
 735   return min + (r % (max - min));
 736   return (r * (max - min));
 737 }
 738
 739 struct placement **get_closure(struct placement *placement, struct individual *parent1, struct individual *parent2 UNUSED)
 740 {
 741   printf("Getting closure\n");
 742   struct placement **closure;
 743   GARY_INIT(closure, 0);
 744   bool *chosen = malloc(GARY_SIZE(parent1->placements) * sizeof(bool));
 745   chosen[placement->request->ind] = 1;
 746
 747   struct placement **p = GARY_PUSH(closure); *p = placement;
 748
 749   uns first = 0;
 750   while (first < GARY_SIZE(closure))
 751   {
 752     printf("Iterating, first is %d\n", first);
 753     struct placement **overlapping = get_overlapping(placement);
 754     filter(overlapping, chosen);
 755     for (uns j=0; j<GARY_SIZE(overlapping); j++)
 756     {
 757       p = GARY_PUSH(closure); *p = overlapping[j];
 758       chosen[overlapping[j]->request->ind] = 1;
 759     }
 760     GARY_FREE(overlapping);
 761     first++;
 762   }
 763
 764   return closure;
 765 }
 766
 767 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child)
 768 {
 769   //printf("%d\n", child->penalty);
 770   //printf("Closure size: %lld\n", GARY_SIZE(closure));
 771   for (uns i=0; i<GARY_SIZE(closure); i++)
 772   {
 773     int ind = closure[i]->request->ind;
 774     child->placements[ind] = parent->placements[ind];
 775     child->placements[ind].processed = 0;
 776   }
 777 }
 778
 779 void move_symbol(struct placement *p)
 780 {
 781   switch (p->request->type)
 782   {
 783     case REQUEST_POINT:
 784       move_symbol_point(p);
 785   }
 786 }
 787
 788 void move_symbol_point(struct placement *p)
 789 {
 790   p->x += (double) (move_min + randdouble()) * flip(1, -1);
 791   p->y += (double) (move_min + randdouble()) * flip(1, -1);
 792 }
 793
 794 void init_placement(struct placement *p, struct request *r)
 795 {
 796   // FIXME
 797   p->request = r;
 798   p->processed = 0;
 799 }
 800
 801 void init_individual(struct individual *i)
 802 {
 803 //printf("Initing individual\n");
 804   GARY_INIT(i->placements, num_requests);
 805   GARY_INIT(i->map, 0);
 806   i->penalty = 0; // FIXME
 807 }
 808
 809 struct placement **get_overlapping(struct placement *p UNUSED)
 810 {
 811   struct placement **buffer;
 812   GARY_INIT(buffer, 0);
 813   return buffer;
 814 }
 815
 816 void filter(struct placement **list UNUSED, bool *pred UNUSED)
 817 {
 818   // FIXME
 819 }
 820
 821 int flip(int a, int b)
 822 {
 823   return (random() % 2 ? a : b);
 824 }
 825
 826 double randdouble(void)
 827 {
 828   // FIXME: How the hell shall double in range <0, 1> be generated? O:)
 829   return 0.5;
 830 }
 831
 832 void cleanup(void)
 833 {
 834   hash_cleanup();
 835   GARY_FREE(requests_point);
 836   GARY_FREE(requests_line);
 837   GARY_FREE(requests_area);
 838 }
 839
 840 void copy_individual(struct individual *src, struct individual *dest)
 841 {
 842   src->penalty = dest->penalty;
 843   GARY_INIT(dest->placements, GARY_SIZE(src->placements));
 844   for (uns i=0; i<GARY_SIZE(src->placements); i++)
 845   {
 846     dest->placements[i] = src->placements[i];
 847   }
 848 }