labeller.c

   1 #include <ucw/lib.h>
   2 #include <ucw/gary.h>
   3 #include <ucw/mempool.h>
   4 #include <ucw/eltpool.h>
   5
   6 #include "leo.h"
   7 #include "sym.h"
   8 #include "labeller.h"
   9
  10 #define HASH_NODE struct graph_node
  11 #define HASH_PREFIX(x) hash_##x
  12 #define HASH_KEY_ATOMIC id
  13 #define HASH_WANT_FIND
  14 #define HASH_WANT_NEW
  15 #define HASH_WANT_CLEANUP
  16 #include <ucw/hashtable.h>
  17
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <math.h>
  21
  22 #define BLOCK_SIZE 4096
  23
  24 //struct mempool *mpool_requests;
  25
  26 static struct request_point *requests_point;
  27 static struct request_line *requests_line;
  28 static struct request_area *requests_area;
  29
  30 static struct graph_edge **bfs_queue;
  31 static struct longline *longlines; int num_longlines;
  32 static struct buffer_line *buffer_line;
  33 static struct buffer_linelabel *buffer_linelabel;
  34
  35 struct eltpool *ep_individuals;
  36
  37 struct individual **population1;
  38 struct individual **population2;
  39
  40 int num_edges_dbg;
  41 int num_nodes;
  42 int num_edges = 0;
  43 int dbg_num_hits = 0;
  44
  45 int conf_pop_size = 50;
  46
  47 int conf_penalty_bound = 0;
  48 int conf_stagnation_bound = 0;
  49 int conf_iteration_limit = 4;
  50
  51 int conf_term_cond = TERM_COND_ITERATIONS;
  52
  53 int conf_breed_rbest_perc = 80;
  54 int conf_breed_pop_size_perc = 20;
  55 int conf_breed_perc = 50;                       // Percentage of new pop created by breeding
  56
  57 bool conf_mutate_children = 1;
  58 int conf_mutate_children_prob = 0.3;
  59
  60 int conf_mutate_rbest_perc = 60;
  61 int conf_mutate_pop_size_perc = 20;
  62
  63 int conf_mutate_move_bound = 0.2;
  64 int conf_mutate_regen_bound = 0.1;
  65 int conf_mutate_chvar_bound = 0.1;
  66
  67 int conf_elite_perc = 5;
  68
  69 int old_best = 0; // FIXME: Shall be int max
  70 int iteration = 0;
  71 int pop2_ind;
  72
  73 int conf_part_size = 50;
  74
  75 int move_min = 0;
  76 int move_max = 1;
  77
  78 int num_requests = 0;
  79
  80 void labeller_init(void)
  81 {
  82 //  mpool_requests = mp_new(BLOCK_SIZE);
  83   GARY_INIT(requests_point, 0);
  84   GARY_INIT(requests_line, 0);
  85   GARY_INIT(requests_area, 0);
  86   GARY_INIT(buffer_line, 0);
  87   GARY_INIT(buffer_linelabel, 0);
  88   ep_individuals = ep_new(sizeof(struct individual), 1);
  89 }
  90
  91 void make_bitmap_icon(struct point_variant *v, struct sym_icon *si)
  92 {
  93   v->width = si->sir.icon->width;
  94   v->height = si->sir.icon->height;
  95   v->bitmap = malloc((int) ceil(v->width * v->height * sizeof(bool)));
  96   for (int i=0; i<v->width*v->height; i++) v->bitmap[i] = 1;
  97 }
  98
  99 void make_bitmap_point(struct point_variant *v, struct sym_point *sp)
 100 {
 101   v->width = v->height = sp->size;
 102   v->bitmap = malloc(sp->size*sp->size * sizeof(bool));
 103   // FIXME: Okay, memset would be much nicer here
 104   for (int i=0; i<sp->size*sp->size; i++) v->bitmap[i] = 1;
 105 }
 106
 107 void make_bitmap_label(struct point_variant *v UNUSED, struct sym_text *text UNUSED)
 108 {
 109 }
 110
 111 void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex)
 112 {
 113 /* FIXME
 114    What does correct check look like?
 115   if (object->type != OSM_TYPE_NODE)
 116   {
 117     // FIXME
 118     return;
 119   }
 120 */
 121
 122   struct request_point *r = GARY_PUSH(requests_point);
 123
 124   r->request.type = REQUEST_POINT;
 125   r->request.ind = num_requests++;
 126
 127   r->sym = sym;
 128   r->object = object;
 129   r->zindex = zindex;
 130
 131   r->offset_x = 0;
 132   r->offset_y = 0;
 133
 134   r->num_variants = 1;
 135   GARY_INIT(r->variants, 0);
 136
 137   struct point_variant *v = GARY_PUSH(r->variants);
 138
 139   switch (sym->type)
 140   {
 141     case SYMBOLIZER_ICON:
 142       make_bitmap_icon(v, (struct sym_icon *) sym);
 143       r->x = ((struct sym_icon *)sym)->sir.x;
 144       r->y = ((struct sym_icon *)sym)->sir.y;
 145       break;
 146     case SYMBOLIZER_POINT:
 147       make_bitmap_point(v, (struct sym_point *) sym);
 148       struct osm_node *n = (struct osm_node *) object;
 149       r->x = n->x;
 150       r->y = n->y;
 151       break;
 152     default:
 153       // Oops :)
 154       // FIXME
 155       return;
 156   }
 157
 158   printf("Inited point to [%.2f; %.2f]\n", r->x, r->y);
 159 }
 160
 161 void labeller_add_line(struct symbol *sym, z_index_t zindex)
 162 {
 163   struct buffer_line *b = GARY_PUSH(buffer_line);
 164   b->line = (struct sym_line *) sym;
 165   b->zindex = zindex;
 166   sym_plan(sym, zindex);
 167 }
 168
 169 void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
 170 {
 171   struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
 172   ll->way = (struct osm_way *) o;
 173   ll->text = (struct sym_text *) sym;
 174   ll->zindex = zindex;
 175 }
 176
 177 void labeller_add_arealabel(struct symbol *sym UNUSED, struct osm_object *o, z_index_t zindex)
 178 {
 179   struct request_area *r = GARY_PUSH(requests_area);
 180
 181   r->request.type = REQUEST_AREALABEL;
 182   r->request.ind = num_requests++;
 183
 184   r->o = (struct osm_multipolygon *) o;
 185   r->zindex = zindex;
 186   r->sym = (struct sym_text *) sym;
 187
 188   GARY_INIT(r->text_variant, 0);
 189   struct point_variant *v = GARY_PUSH(r->text_variant);
 190   make_bitmap_label(v, r->sym);
 191 }
 192
 193 void make_graph(void)
 194 {
 195   hash_init();
 196   struct mempool *mp_edges = mp_new(BLOCK_SIZE);
 197
 198   printf("Extracting nodes, will iterate over %lld ways\n", GARY_SIZE(buffer_line));
 199   for (uns i=0; i<GARY_SIZE(buffer_line); i++)
 200   {
 201     struct osm_way *way = (struct osm_way *) buffer_line[i].line->s.o;
 202     struct graph_node *g_prev = NULL;
 203     struct osm_node *o_prev = NULL;
 204
 205     CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
 206     {
 207       // FIXME: Shall osm_object's type be checked here?
 208       struct osm_node *o_node = (struct osm_node *) ref->o;
 209
 210       struct graph_node *g_node = hash_find(ref->o->id);
 211       if (!g_node)
 212       {
 213         g_node = hash_new(ref->o->id);
 214         GARY_INIT(g_node->edges, 0);
 215         g_node->o = o_node;
 216         g_node->id = ref->o->id;
 217         g_node->num = num_nodes++;
 218       }
 219
 220       if (! g_prev)
 221       {
 222         g_prev = g_node;
 223         o_prev = o_node;
 224         continue;
 225       }
 226
 227       struct graph_edge *e = mp_alloc(mp_edges, sizeof(struct graph_edge)); num_edges_dbg++;
 228       e->num = num_edges++;
 229       e->id = buffer_line[i].line->s.o->id;
 230       e->color = buffer_line[i].line->color;
 231       e->length = hypot(abs(o_prev->x - o_node->x), abs(o_prev->y - o_node->y));
 232       e->visited = 0;
 233       e->prev = NULL;
 234       e->next = NULL;
 235       e->n1 = g_prev;
 236       e->n2 = g_node;
 237       e->longline = (uns) -1;
 238       e->text = NULL;
 239       e->sym = buffer_line[i].line;
 240       e->dir = 0;
 241
 242       struct graph_edge **edge = GARY_PUSH(g_prev->edges);
 243       *edge = e;
 244       edge = GARY_PUSH(g_node->edges);
 245       *edge = e;
 246
 247       g_prev = g_node;
 248       o_prev = o_node;
 249     }
 250   }
 251 }
 252
 253 void dump_graph(void)
 254 {
 255   HASH_FOR_ALL(hash, node)
 256   {
 257     printf("* Node: (%d) #%ju [%.2f; %.2f]\n", node->num, node->id, node->o->x, node->o->y);
 258     for (uns i=0; i<GARY_SIZE(node->edges); i++)
 259     {
 260       struct graph_edge *e = node->edges[i];
 261       printf("\t edge (%d) #%ju to ", e->num, e->id);
 262       if (node->edges[i]->n1->id == node->id)
 263         printf("(%d) #%ju [%.2f; %.2f]\n", e->n2->num, e->n2->id, e->n2->o->x, e->n2->o->y);
 264       else if (node->edges[i]->n2->id == node->id)
 265         printf("(%d) #%ju [%.2f; %.2f]\n", e->n1->num, e->n1->id, e->n1->o->x, e->n1->o->y);
 266       else
 267         printf("BEWARE! BEWARE! BEWARE!\n");
 268
 269       printf("\t\t");
 270       if (node->edges[i]->text) printf(" labelled %s;", osm_val_decode(node->edges[i]->text->text));
 271       printf(" colored %d;", node->edges[i]->color);
 272       printf("   length %.2f", node->edges[i]->length);
 273       printf("\n");
 274     }
 275   }
 276   HASH_END_FOR;
 277 }
 278
 279 void label_graph(void)
 280 {
 281 printf("There are %u line labels requested\n", GARY_SIZE(buffer_linelabel));
 282   for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
 283   {
 284     printf("Labelling nodes of way %s\n", osm_val_decode(buffer_linelabel[i].text->text));
 285     CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
 286     {
 287       printf("Looking for node %ju\n", ref->o->id);
 288       struct graph_node *n = hash_find(ref->o->id);
 289       if (n == NULL)
 290       {
 291         // FIXME: What shall be done?
 292       }
 293       else
 294       {
 295         printf("Searching among %u edges\n", GARY_SIZE(n->edges));
 296         for (uns j=0; j<GARY_SIZE(n->edges); j++)
 297         {
 298           if (n->edges[j]->id == buffer_linelabel[i].way->o.id)
 299           {
 300             printf("Labelling node %ju\n", n->id);
 301             n->edges[j]->text = buffer_linelabel[i].text;
 302             n->edges[j]->zindex = buffer_linelabel[i].zindex;
 303           }
 304         }
 305       }
 306     }
 307   }
 308 }
 309
 310 void join_edge(struct graph_edge *e, int dir)
 311 {
 312   struct graph_node *other_node = NULL;
 313   switch (dir)
 314   {
 315     case 1:
 316       other_node = e->n2;
 317       break;
 318     case 2:
 319       other_node = e->n1;
 320       break;
 321     // FIXME: default?
 322   }
 323
 324   struct graph_edge *candidate = NULL;
 325   for (uns i=0; i<GARY_SIZE(other_node->edges); i++)
 326   {
 327     struct graph_edge *other = other_node->edges[i];
 328     if (! other->visited)
 329     {
 330     struct graph_edge **new = GARY_PUSH(bfs_queue);
 331     *new = other_node->edges[i];
 332     }
 333
 334     if ((!other->visited) && (e->text) && (other->text) && (e->text->text == other->text->text))
 335     {
 336       if (e->color == other_node->edges[i]->color)
 337       {
 338         if ((!candidate) || (candidate->length < other->length))
 339         {
 340           candidate = other;
 341         }
 342       }
 343       else
 344       {
 345         // Beware: Name conflict here
 346       }
 347     }
 348   }
 349
 350   if (candidate)
 351   {
 352     candidate->longline = e->longline;
 353     if (dir == 1)
 354     {
 355       if (candidate->n2 != e->n1)
 356       {
 357         candidate->n1 = candidate->n2;
 358         candidate->n2 = e->n1;
 359       }
 360       e->prev = candidate;
 361       candidate->next = e;
 362
 363       longlines[e->longline].first = candidate;
 364     }
 365     else
 366     {
 367       if (candidate->n1 != e->n2)
 368       {
 369         candidate->n2 = candidate->n1;
 370         candidate->n1 = e->n2;
 371       }
 372       e->next = candidate;
 373       candidate->prev = e;
 374     }
 375   }
 376 }
 377
 378 void bfs2(void)
 379 {
 380   GARY_INIT(bfs_queue, 0);
 381   GARY_INIT(longlines, 0);
 382
 383   printf("Making longlines from %u causal lines, using %d graph edges\n", GARY_SIZE(buffer_line), num_edges_dbg);
 384
 385   HASH_FOR_ALL(hash, node)
 386   {
 387     for (uns i=0; i<GARY_SIZE(node->edges); i++)
 388     {
 389       struct graph_edge *e = node->edges[i];
 390
 391 //      printf("Examining edge from [%.2f; %.2f] to [%.2f; %.2f]\n",
 392 //              e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y);
 393
 394       // if (e->visited) HASH_CONTINUE; // FIXME: Is is correct?
 395       if (e->visited) continue;
 396 //      printf("Continuing\n");
 397       if (e->longline == (uns) -1)
 398       {
 399         GARY_PUSH(longlines);
 400         e->longline = num_longlines++;
 401         longlines[e->longline].first = e;
 402       }
 403 //      printf("Longline is %u\n", e->longline);
 404
 405       e->visited = 1;
 406
 407       if (! e->prev)
 408       {
 409         join_edge(e, 1);
 410       }
 411       if (! e->next)
 412       {
 413         join_edge(e, 2);
 414       }
 415     }
 416   }
 417   HASH_END_FOR;
 418
 419   GARY_FREE(bfs_queue);
 420 }
 421
 422 void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, int dir)
 423 {
 424   ASSERT(dir < 3);
 425   struct graph_edge *candidate = NULL;
 426
 427   if ((e->num > 31) && (e->num < 48)) printf("Searching for neighbours of %d, in longline %u, BFS dir is %d, edge's dir is %d\n", e->num, e->longline, dir, e->dir);
 428
 429
 430   for (uns i=0; i<GARY_SIZE(node->edges); i++)
 431   {
 432     struct graph_edge *other = node->edges[i];
 433 printf("Touching %d\n", other->num);
 434 if (other->num == 44) printf("Longline of 44 is %u\n", other->longline);
 435     if ((other->longline != (uns) -1) && (other->longline != e->longline)) continue;
 436
 437     if (! other->visited) {
 438     struct graph_edge **e_ptr = GARY_PUSH(bfs_queue);
 439     *e_ptr = other;
 440     other->visited = 1;
 441     }
 442
 443     if (((other->n1->id == node->id) && (other->n2->id == anode->id)) ||
 444         ((other->n2->id == node->id) && (other->n1->id == anode->id)))
 445         continue;
 446
 447     if (((other->n1->id == node->id) || (other->n2->id == node->id)) &&
 448         (e->text) && (other->text) && (e->text->text == other->text->text))
 449     {
 450       if (! candidate || (other->length > candidate->length))
 451       candidate = other;
 452     }
 453   }
 454
 455   if (candidate)
 456   {
 457     struct graph_edge *other = candidate;
 458 dbg_num_hits++;
 459       other->longline = e->longline;
 460       other->dir = dir;
 461       other->anode = (other->n1->id == node->id ? other->n2 : other->n1);
 462       other->bnode = (other->n1->id == node->id ? other->n1 : other->n2);
 463       switch (dir)
 464       {
 465         case 1:
 466           e->prev = other;
 467           other->next = e;
 468           longlines[other->longline].first = other;
 469           break;
 470         case 2:
 471           e->next = other;
 472           other->prev = e;
 473           break;
 474         default:
 475           printf("Oops\n");
 476           ASSERT(0);
 477       }
 478   }
 479 }
 480
 481 void bfs(void)
 482 {
 483   for (uns i=0; i<GARY_SIZE(bfs_queue); i++)
 484   {
 485     struct graph_edge *cur = bfs_queue[i];
 486     printf("Exploring new edge, %d\n", cur->num);
 487     //ASSERT(! cur->visited);
 488
 489     cur->visited = 1;
 490     if (cur->longline == (uns) -1)
 491     {
 492       GARY_PUSH(longlines);
 493       cur->longline = num_longlines++;
 494       longlines[cur->longline].first = cur;
 495     }
 496
 497     if (!cur->anode)
 498     {
 499       bfs_edge(cur, cur->n1, cur->n2, 1);
 500       bfs_edge(cur, cur->n2, cur->n1, 2);
 501     }
 502     else
 503     {
 504       bfs_edge(cur, cur->anode, cur->bnode, cur->dir);
 505     }
 506   }
 507 }
 508
 509 void bfs_wrapper(void)
 510 {
 511   GARY_INIT(bfs_queue, 0);
 512   GARY_INIT(longlines, 0);
 513
 514   HASH_FOR_ALL(hash, node)
 515   {
 516     for (uns i=0; i<GARY_SIZE(node->edges); i++)
 517     {
 518       if (! node->edges[i]->visited)
 519       {
 520         printf("Running new BFS\n");
 521         GARY_RESIZE(bfs_queue, 0);
 522         struct graph_edge **e = GARY_PUSH(bfs_queue);
 523         *e = node->edges[i];
 524         bfs();
 525         //dump_longlines();
 526         printf("Joined %d edges\n", dbg_num_hits); dbg_num_hits = 0;
 527         printf("Planned %u edges\n", GARY_SIZE(bfs_queue));
 528       }
 529     }
 530   }
 531   HASH_END_FOR;
 532
 533   GARY_FREE(bfs_queue);
 534 }
 535
 536 void oldbfs(void)
 537 {
 538   printf("Starting outer BFS\n");
 539   printf("There are %u buffered lines and %d eges\n", GARY_SIZE(buffer_line), num_edges_dbg);
 540
 541   GARY_INIT(bfs_queue, 0);
 542   GARY_INIT(longlines, 0);
 543
 544   int dbg_bfs_continues = 0;
 545
 546   HASH_FOR_ALL(hash, node)
 547   {
 548     // FIXME: Skip if visited node
 549
 550     for (uns i=0; i<GARY_SIZE(node->edges); i++)
 551     {
 552       struct graph_edge *e = node->edges[i];
 553
 554       if (e->visited) continue;
 555
 556       // BFS itself
 557       for (uns i1=0; i1<GARY_SIZE(e->n1->edges); i1++)
 558       {
 559         struct graph_edge *other = e->n1->edges[i1];
 560         if (other->visited) { dbg_bfs_continues++; continue; }
 561
 562         if (((other->n1->id == e->n1->id) || (other->n2->id == e->n1->id)) &&
 563             (e->text) && (other->text) && (e->text->text == other->text->text))
 564         {
 565 //          printf("Hit\n");
 566           other->visited = 1;
 567         }
 568       }
 569       for (uns i2=0; i2<GARY_SIZE(e->n2->edges); i2++)
 570       {
 571         struct graph_edge *other = e->n2->edges[i2];
 572         if (other->visited) {dbg_bfs_continues++; continue; }
 573
 574         if (((other->n1->id == e->n2->id) || (other->n2->id == e->n2->id)) &&
 575             (e->text) && (other->text) && (e->text->text == other->text->text))
 576         {
 577 //          printf("Hit\n");
 578           other->visited = 1;
 579         }
 580       }
 581     }
 582   }
 583
 584   HASH_END_FOR;
 585   printf("Total: %d hits, %d visited edges skipped\n", dbg_num_hits, dbg_bfs_continues);
 586
 587   GARY_FREE(bfs_queue);
 588 }
 589
 590 void dump_longlines(void)
 591 {
 592   for (uns i=0; i<GARY_SIZE(longlines); i++)
 593   {
 594     struct graph_edge *e = longlines[i].first;
 595
 596     printf("> Longline %u;", i);
 597     if (longlines[i].first->text) printf(" labelled %s", osm_val_decode(longlines[i].first->text->text));
 598     printf("\n");
 599     while (e)
 600     {
 601       printf("\t#%ju (%d)", e->id, e->num);
 602       switch (e->dir)
 603       {
 604       case 1:
 605         printf("[%.2f; %.2f] -- #%u [%.2f; %.2f] (dir %d)\n", e->anode->o->x, e->anode->o->y, e->bnode->o->o.id, e->bnode->o->x, e->bnode->o->y, e->dir);
 606         break;
 607       case 2:
 608         printf("[%.2f; %.2f] -- #%u [%.2f; %.2f] (dir %d)\n", e->bnode->o->x, e->bnode->o->y, e->anode->o->o.id, e->anode->o->x, e->anode->o->y, e->dir);
 609         break;
 610       case 0:
 611         printf("[%.2f; %.2f] -- #%u [%.2f; %.2f] (dir %d)\n", e->n1->o->x, e->n1->o->y, e->n2->o->o.id, e->n2->o->x, e->n2->o->y, e->dir);
 612         break;
 613       default:
 614         printf("%d\n", e->dir);
 615         ASSERT(0);
 616       }
 617       e = e->next;
 618     }
 619   }
 620 }
 621
 622 void make_segments(void)
 623 {
 624 printf("Analysing %u longlines\n", GARY_SIZE(longlines));
 625   for (uns i=0; i<GARY_SIZE(longlines); i++)
 626   {
 627     if (! longlines[i].first->text) continue;
 628 //    printf("Survived! %s\n", osm_val_decode(longlines[i].first->text->text));
 629 printf("New longline\n");
 630     struct request_line *request = GARY_PUSH(requests_line);
 631     request->request.ind = -1;
 632     request->request.type = REQUEST_LINELABEL;
 633
 634     GARY_INIT(request->segments, 0);
 635     request->num_segments = 0;
 636
 637     // ->num_variants FIXME
 638     // ->variants FIXME
 639
 640     struct graph_edge *e = longlines[i].first;
 641
 642     if (! e) printf("Oops\n");
 643     num_requests++;
 644     while (e)
 645     {
 646       if (! e->text) break;
 647       struct request_segment *r = GARY_PUSH(request->segments);
 648       request->num_segments++;
 649
 650       r->request.ind = num_requests++;
 651       r->request.type = REQUEST_SEGMENT;
 652
 653       struct osm_node *n = e->n1->o;
 654       r->x1 = n->x;
 655       r->y1 = n->y;
 656       n = e->n2->o;
 657       r->x2 = n->x;
 658       r->y2 = n->y;
 659       r->k = abs(r->x2 - r->x1) / (abs(r->y2 - r->y1) + 0.001); // FIXME: Hack to prevent floating point exception when y2 = y1
 660
 661 //printf("Segment [%.2f; %.2f] -- [%.2f; %.2f]\n", r->x1, r->y1, r->x2, r->y2);
 662
 663       r->sym = e->sym;
 664       r->zindex = e->zindex;
 665       r->text = malloc(sizeof(struct sym_text));
 666       *(r->text) = *(e->text);
 667       r->text->x = r->x1;
 668       r->text->y = r->y1;
 669
 670       r->variant = malloc(sizeof(struct point_variant)); // FIXME
 671       make_bitmap_label(r->variant, e->text);
 672
 673       e = e->next;
 674     }
 675   }
 676 }
 677
 678 void dump_linelabel_requests(void)
 679 {
 680   for (uns i=0; i<GARY_SIZE(requests_line); i++)
 681   {
 682     printf("Longline of %d segments, labelled %s\n", requests_line[i].num_segments, osm_val_decode(requests_line[i].segments[0].text->text));
 683   }
 684 }
 685
 686 void dump_individual(struct individual *individual)
 687 {
 688   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 689   {
 690     struct placement *p = &(individual->placements[i]);
 691
 692     switch (p->request->type)
 693     {
 694       case REQUEST_POINT:
 695         printf("Point at [%.2f; %.2f]\n", p->x, p->y);
 696         break;
 697       case REQUEST_LINELABEL: ;
 698         struct request_line *rl = (struct request_line *) p->request;
 699         printf("%d-segment longline %s\n", rl->num_segments, osm_val_decode(rl->segments[0].text->text));
 700         break;
 701       case REQUEST_AREALABEL: ;
 702         struct request_area *ra = (struct request_area *) p->request;
 703         printf("Area label %s at [%.2f; %.2f]\n", osm_val_decode(ra->sym->text), p->x, p->y);
 704     }
 705   }
 706   printf("\nTotal penalty: %d\n", individual->penalty);
 707 }
 708
 709 void labeller_label(void)
 710 {
 711   make_graph();
 712   label_graph();
 713 dump_graph();
 714   bfs_wrapper();
 715 dump_longlines();
 716   make_segments();
 717 dump_linelabel_requests();
 718
 719 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));
 720
 721   GARY_INIT(population1, conf_pop_size);
 722   GARY_INIT(population2, conf_pop_size);
 723   make_population();
 724
 725   printf("Dealing with %d requests\n", num_requests);
 726
 727 /*
 728   while (! shall_terminate())
 729   {
 730     iteration++;
 731
 732     struct individual **swp = population1;
 733     population1 = population2;
 734     population2 = swp;
 735     pop2_ind = 0;
 736   }
 737 */
 738
 739   dump_individual(population1[0]);
 740
 741   for (uns i=0; i<GARY_SIZE(population1[0]->placements); i++)
 742   {
 743     switch (population1[0]->placements[i].request->type)
 744     {
 745       case REQUEST_POINT: ;
 746         struct request_point *rp = (struct request_point *) population1[0]->placements[i].request;
 747         switch (rp->sym->type)
 748         {
 749           case SYMBOLIZER_POINT: ;
 750 //          printf("Moving point to final destination\n");
 751             struct sym_point *sp = (struct sym_point *) rp->sym;
 752             sp->x = population1[0]->placements[i].x;
 753             sp->y = population1[0]->placements[i].y;
 754             sym_plan((struct symbol *) sp, rp->zindex);
 755             break;
 756           case SYMBOLIZER_ICON: ;
 757 //          printf("Moving icon to final destination\n");
 758             struct sym_icon *si = (struct sym_icon *) rp->sym;
 759             si->sir.x = population1[0]->placements[i].x;
 760             si->sir.y = population1[0]->placements[i].y;
 761             sym_plan((struct symbol *) si, rp->zindex);
 762             break;
 763           default:
 764             ;
 765         }
 766         break;
 767       case REQUEST_AREALABEL: ;
 768         struct request_area *ra = (struct request_area *) population1[0]->placements[i].request;
 769         sym_plan((struct symbol *) ra->sym, ra->zindex);
 770         break;
 771
 772       case REQUEST_LINELABEL: ;
 773         struct request_line *rl = (struct request_line *) population1[0]->placements[i].request;
 774         for (uns j=0; j<GARY_SIZE(rl->segments); j++)
 775         {
 776 //          printf("Planning text %s to [%.2f; %.2f]\n", osm_val_decode(rl->segments[j].text->text), rl->segments[j].text->x, rl->segments[j].text->y);
 777           rl->segments[j].text->next_duplicate = NULL;
 778           rl->segments[j].text->next_in_tile = NULL;
 779           rl->segments[j].text->x = population1[0]->placements[i].x;
 780           rl->segments[j].text->y = population1[0]->placements[i].y;
 781           sym_plan((struct symbol *) rl->segments[j].text, rl->segments[j].zindex); // FIXME: z-index
 782         }
 783         break;
 784 /*
 785       case REQUEST_SEGMENT: ;
 786         struct request_segment *rs = (struct request_segment *) population1[0]->placements[i].request;
 787         printf("Segment!\n");
 788 */
 789     }
 790   }
 791
 792   return;
 793
 794   while (! shall_terminate())
 795   {
 796     iteration++;
 797
 798     breed();
 799     mutate();
 800     elite();
 801     rank_population();
 802     // sort population by fitness
 803
 804     struct individual **swp = population1;
 805     population1 = population2;
 806     printf("Swapped populations\n");
 807     population2 = swp;
 808     // GARY_RESIZE(population2, 0) -- is it needed?
 809     pop2_ind = 0;
 810   }
 811 }
 812
 813 void make_population(void)
 814 {
 815   for (int i=0; i<conf_pop_size; i++)
 816   {
 817     struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
 818     population1[i] = individual;
 819
 820     int p = 0;
 821     for (uns j=0; j<GARY_SIZE(requests_point); j++)
 822     {
 823       init_placement(&(individual->placements[p++]), (struct request *) &requests_point[j]);
 824     }
 825     for (uns j=0; j<GARY_SIZE(requests_line); j++)
 826     {
 827       init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j]);
 828       for (uns k=0; k<GARY_SIZE(requests_line[j].segments); k++)
 829       {
 830         init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j].segments[k]);
 831       }
 832     }
 833     for (uns j=0; j<GARY_SIZE(requests_area); j++)
 834     {
 835       init_placement(&(individual->placements[p++]), (struct request *) &requests_area[j]);
 836     }
 837
 838     ASSERT(p == num_requests);
 839   }
 840 }
 841
 842 bool shall_terminate(void)
 843 {
 844   switch (conf_term_cond)
 845   {
 846     case TERM_COND_PENALTY:
 847       return (population1[0]->penalty < conf_penalty_bound);
 848     case TERM_COND_STAGNATION:
 849       return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
 850     case TERM_COND_ITERATIONS:
 851       return (iteration >= conf_iteration_limit);
 852     default:
 853       // FIXME: Warn the user that no condition is set
 854       return 1;
 855   }
 856 }
 857
 858 void breed(void)
 859 {
 860   int acc = 0;
 861   int i=0;
 862   printf("%.2f\n", ((double) conf_breed_pop_size_perc/100));
 863   int conf_breed_pop_size = ((double) conf_breed_pop_size_perc/100) * conf_pop_size;
 864   struct individual **breed_buffer;
 865   while (i < conf_breed_pop_size)
 866   {
 867   printf("%d < %d, breeding\n", i, conf_breed_pop_size);
 868     int parent1 = randint(1, conf_breed_pop_size);
 869     int parent2 = randint(1, conf_breed_pop_size);
 870     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);
 871     breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
 872     population2[pop2_ind++] = breed_buffer[0];
 873     population2[pop2_ind++] = breed_buffer[1];
 874     free(breed_buffer);
 875     i++;
 876   }
 877
 878   acc += conf_breed_rbest_perc;
 879
 880   return; // FIXME: DEBUG HACK
 881
 882   int remaining = (1 - acc) * (conf_pop_size * conf_breed_perc);
 883   int step = remaining / conf_pop_size;
 884   for (; i<conf_pop_size; i += 2)
 885   {
 886     printf("Asking for %d and %d of %d\n", i*step, i*(step+1), conf_pop_size);
 887     breed_buffer = perform_crossover(population1[i*step], population1[i*step+1]);
 888     population2[pop2_ind++] = breed_buffer[0];
 889     population2[pop2_ind++] = breed_buffer[1];
 890   }
 891
 892   // FIXME: Could there be one missing individual?
 893 }
 894
 895 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
 896 {
 897   struct individual **buffer = malloc(2*sizeof(struct individual));
 898   struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
 899   struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
 900
 901   printf("Performing crossover\n");
 902
 903   for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
 904   {
 905     printf("%dth placement out of %d\n", i, num_requests);
 906     if (! parent1->placements[i].processed)
 907     {
 908       struct placement **clos_symbols = get_closure(&(parent1->placements[i]), parent1, parent2);
 909       int x = randint(1, 2);
 910
 911       if (x == 1)
 912       {
 913         copy_symbols(clos_symbols, parent1, child1);
 914         copy_symbols(clos_symbols, parent2, child2);
 915       }
 916       else
 917       {
 918         copy_symbols(clos_symbols, parent2, child1);
 919         copy_symbols(clos_symbols, parent1, child2);
 920       }
 921       printf("Symbols copied; %lld\n", GARY_SIZE(clos_symbols));
 922       GARY_FREE(clos_symbols);
 923     }
 924
 925     if (conf_mutate_children)
 926     {
 927       if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child1);
 928       if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child2);
 929     }
 930   }
 931
 932   buffer[0] = child1;
 933   buffer[1] = child2;
 934   return buffer;
 935 }
 936
 937 void mutate(void)
 938 {
 939   int i = 0;
 940   int conf_mutate_pop_size = conf_mutate_pop_size_perc * conf_pop_size;
 941   while (i < conf_mutate_rbest_perc * conf_pop_size)
 942   {
 943     int ind = randint(1, conf_mutate_pop_size);
 944     copy_individual(population2[pop2_ind], population1[ind]);
 945     perform_mutation(population2[pop2_ind]);
 946     pop2_ind++;
 947   }
 948 }
 949
 950 void perform_mutation(struct individual *individual)
 951 {
 952   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 953   {
 954     int x = randint(1, 1000);
 955     int acc = 0;
 956
 957     if (x <= acc + conf_mutate_move_bound)
 958     {
 959       move_symbol(&(individual->placements[i]));
 960       continue;
 961     }
 962     acc += conf_mutate_move_bound;
 963
 964     if (x <= acc + conf_mutate_regen_bound)
 965     {
 966       gen_coords(&(individual->placements[i]));
 967       continue;
 968     }
 969     acc += conf_mutate_regen_bound;
 970
 971     if (x <= acc + conf_mutate_chvar_bound)
 972     {
 973       if (0) // if num_variants > 1
 974       {
 975         // FIXME: assign new variant
 976       }
 977     }
 978   }
 979 }
 980
 981 void elite(void)
 982 {
 983   for (int i=0; i<conf_elite_perc * conf_pop_size; i++)
 984   {
 985     population2[pop2_ind++] = population1[0];
 986   }
 987 }
 988
 989 void rank_population(void)
 990 {
 991   // FIXME
 992 }
 993
 994 void gen_coords(struct placement *p)
 995 {
 996   switch(p->request->type)
 997   {
 998     case REQUEST_POINT:
 999       gen_coords_point(p);
1000   }
1001 }
1002
1003 void gen_coords_point(struct placement *p UNUSED)
1004 {
1005   // FIXME
1006 }
1007
1008 struct map_part **get_parts(struct placement *symbol, struct individual *individual)
1009 {
1010   struct map_part **buffer;
1011   GARY_INIT(buffer, 0);
1012   int x_min = symbol->x / conf_part_size;
1013   int x_max = (symbol->x /*+ symbol->bitmap->width*/ + conf_part_size - 1) / conf_part_size;
1014   int y_min = symbol->y / conf_part_size;
1015   int y_max = (symbol->y /*+ symbol->bitmap->height*/ + conf_part_size - 1) / conf_part_size;
1016
1017   for (int x=x_min; x < x_max; x++)
1018     for (int y=y_min; y < y_max; y++)
1019     {
1020       struct map_part *m = GARY_PUSH(buffer);
1021       *m = individual->map[x][y];
1022     }
1023
1024   return buffer;
1025 }
1026
1027 int randint(int min, int max)
1028 {
1029   int r = random();
1030   //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)));
1031   return min + (r % (max - min));
1032   return (r * (max - min));
1033 }
1034
1035 struct placement **get_closure(struct placement *placement, struct individual *parent1, struct individual *parent2 UNUSED)
1036 {
1037   printf("Getting closure\n");
1038   struct placement **closure;
1039   GARY_INIT(closure, 0);
1040   bool *chosen = malloc(GARY_SIZE(parent1->placements) * sizeof(bool));
1041   chosen[placement->request->ind] = 1;
1042
1043   struct placement **p = GARY_PUSH(closure); *p = placement;
1044
1045   uns first = 0;
1046   while (first < GARY_SIZE(closure))
1047   {
1048     printf("Iterating, first is %d\n", first);
1049     struct placement **overlapping = get_overlapping(placement);
1050     filter(overlapping, chosen);
1051     for (uns j=0; j<GARY_SIZE(overlapping); j++)
1052     {
1053       p = GARY_PUSH(closure); *p = overlapping[j];
1054       chosen[overlapping[j]->request->ind] = 1;
1055     }
1056     GARY_FREE(overlapping);
1057     first++;
1058   }
1059
1060   return closure;
1061 }
1062
1063 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child)
1064 {
1065   //printf("%d\n", child->penalty);
1066   //printf("Closure size: %lld\n", GARY_SIZE(closure));
1067   for (uns i=0; i<GARY_SIZE(closure); i++)
1068   {
1069     int ind = closure[i]->request->ind;
1070     child->placements[ind] = parent->placements[ind];
1071     child->placements[ind].processed = 0;
1072   }
1073 }
1074
1075 void move_symbol(struct placement *p)
1076 {
1077   switch (p->request->type)
1078   {
1079     case REQUEST_POINT:
1080       move_symbol_point(p);
1081   }
1082 }
1083
1084 void move_symbol_point(struct placement *p)
1085 {
1086   p->x += (double) (move_min + randdouble()) * flip(1, -1);
1087   p->y += (double) (move_min + randdouble()) * flip(1, -1);
1088 }
1089
1090 void init_placement(struct placement *p, struct request *r)
1091 {
1092   // FIXME
1093   p->request = r;
1094   p->processed = 0;
1095   switch (r->type)
1096   {
1097     case REQUEST_POINT: ;
1098       struct request_point *rp = (struct request_point *) r;
1099       p->x = rp->x;
1100       p->y = rp->y;
1101       break;
1102     case REQUEST_SEGMENT: ;
1103       struct request_segment *rs = (struct request_segment *) r;
1104       p->x = rs->x2;
1105       p->y = rs->y2;
1106       break;
1107     case REQUEST_AREALABEL: ;
1108       struct request_area *ra = (struct request_area *) r;
1109       struct sym_text *st = ra->sym;
1110       p->x = st->x;
1111       p->y = st->y;
1112   }
1113 }
1114
1115 void init_individual(struct individual *i)
1116 {
1117 //printf("Initing individual\n");
1118   GARY_INIT(i->placements, num_requests);
1119   GARY_INIT(i->map, 0);
1120   i->penalty = 0; // FIXME
1121 }
1122
1123 struct placement **get_overlapping(struct placement *p UNUSED)
1124 {
1125   struct placement **buffer;
1126   GARY_INIT(buffer, 0);
1127   return buffer;
1128 }
1129
1130 void filter(struct placement **list UNUSED, bool *pred UNUSED)
1131 {
1132   // FIXME
1133 }
1134
1135 int flip(int a, int b)
1136 {
1137   return (random() % 2 ? a : b);
1138 }
1139
1140 double randdouble(void)
1141 {
1142   // FIXME: How the hell shall double in range <0, 1> be generated? O:)
1143   return 0.5;
1144 }
1145
1146 void cleanup(void)
1147 {
1148   hash_cleanup();
1149   GARY_FREE(requests_point);
1150   GARY_FREE(requests_line);
1151   GARY_FREE(requests_area);
1152 }
1153
1154 void copy_individual(struct individual *src, struct individual *dest)
1155 {
1156   src->penalty = dest->penalty;
1157   GARY_INIT(dest->placements, GARY_SIZE(src->placements));
1158   for (uns i=0; i<GARY_SIZE(src->placements); i++)
1159   {
1160     dest->placements[i] = src->placements[i];
1161   }
1162 }