labeller.c

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