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