labeller.c

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