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