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