X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=labeller.c;h=d64c67a0c7143a90d6d05d64e4d88e765f005d30;hb=5ac436112370bca9a88fe9ed31f399197b6b08cf;hp=7f74bbf8efb6f579705999b3d9af4a56c84b1699;hpb=27a0c4be8375ad51adf0a55696f83859625b8d47;p=leo.git

diff --git a/labeller.c b/labeller.c
index 7f74bbf..d64c67a 100644
--- a/labeller.c
+++ b/labeller.c
@@ -12,6 +12,7 @@
 #define HASH_KEY_ATOMIC id
 #define HASH_WANT_FIND
 #define HASH_WANT_NEW
+#define HASH_WANT_CLEANUP
 #include <ucw/hashtable.h>
 
 #include <stdio.h>
@@ -26,7 +27,7 @@ static struct request_point *requests_point;
 static struct request_line *requests_line;
 static struct request_area *requests_area;
 
-static struct graph_edge *bfs_queue;
+static struct graph_edge **bfs_queue;
 static struct longline *longlines; int num_longlines;
 static struct buffer_line *buffer_line;
 static struct buffer_linelabel *buffer_linelabel;
@@ -36,17 +37,22 @@ struct eltpool *ep_individuals;
 struct individual **population1;
 struct individual **population2;
 
+int num_edges_dbg;
+int num_nodes;
+int num_edges = 0;
+int dbg_num_hits = 0;
+
 int conf_pop_size = 50;
 
 int conf_penalty_bound = 0;
 int conf_stagnation_bound = 0;
-int conf_iteration_limit = 5;
+int conf_iteration_limit = 4;
 
 int conf_term_cond = TERM_COND_ITERATIONS;
 
 int conf_breed_rbest_perc = 80;
 int conf_breed_pop_size_perc = 20;
-int conf_breed_perc = 50;
+int conf_breed_perc = 50;			// Percentage of new pop created by breeding
 
 bool conf_mutate_children = 1;
 int conf_mutate_children_prob = 0.3;
@@ -69,10 +75,13 @@ int conf_part_size = 50;
 int move_min = 0;
 int move_max = 1;
 
+int num_requests = 0;
+
 void labeller_init(void)
 {
 //  mpool_requests = mp_new(BLOCK_SIZE);
   GARY_INIT(requests_point, 0);
+  GARY_INIT(requests_line, 0);
   GARY_INIT(requests_area, 0);
   GARY_INIT(buffer_line, 0);
   GARY_INIT(buffer_linelabel, 0);
@@ -83,6 +92,8 @@ void make_bitmap_icon(struct point_variant *v, struct sym_icon *si)
 {
   v->width = si->sir.icon->width;
   v->height = si->sir.icon->height;
+  v->bitmap = malloc((int) ceil(v->width * v->height * sizeof(bool)));
+  for (int i=0; i<v->width*v->height; i++) v->bitmap[i] = 1;
 }
 
 void make_bitmap_point(struct point_variant *v, struct sym_point *sp)
@@ -109,14 +120,14 @@ void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t
 */
 
   struct request_point *r = GARY_PUSH(requests_point);
+
+  r->request.type = REQUEST_POINT;
+  r->request.ind = num_requests++;
+
   r->sym = sym;
   r->object = object;
   r->zindex = zindex;
 
-  struct osm_node *n = (struct osm_node *) object;
-  r->x = n->x;
-  r->y = n->y;
-
   r->offset_x = 0;
   r->offset_y = 0;
 
@@ -125,14 +136,18 @@ void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t
 
   struct point_variant *v = GARY_PUSH(r->variants);
 
-  if (sym->type == SYMBOLIZER_ICON)
   switch (sym->type)
   {
     case SYMBOLIZER_ICON:
       make_bitmap_icon(v, (struct sym_icon *) sym);
+      r->x = ((struct sym_icon *)sym)->sir.x;
+      r->y = ((struct sym_icon *)sym)->sir.y;
       break;
     case SYMBOLIZER_POINT:
       make_bitmap_point(v, (struct sym_point *) sym);
+      struct osm_node *n = (struct osm_node *) object;
+      r->x = n->x;
+      r->y = n->y;
       break;
     default:
       // Oops :)
@@ -140,7 +155,7 @@ void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t
       return;
   }
 
-  sym_plan(sym, zindex); // TEMPORARY
+  printf("Inited point to [%.2f; %.2f]\n", r->x, r->y);
 }
 
 void labeller_add_line(struct symbol *sym, z_index_t zindex)
@@ -151,11 +166,28 @@ void labeller_add_line(struct symbol *sym, z_index_t zindex)
   sym_plan(sym, zindex);
 }
 
+void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
+{
+  struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
+  ll->way = (struct osm_way *) o;
+  ll->text = (struct sym_text *) sym;
+  ll->zindex = zindex;
+}
+
 void labeller_add_arealabel(struct symbol *sym UNUSED, struct osm_object *o, z_index_t zindex)
 {
   struct request_area *r = GARY_PUSH(requests_area);
+
+  r->request.type = REQUEST_AREALABEL;
+  r->request.ind = num_requests++;
+
   r->o = (struct osm_multipolygon *) o;
   r->zindex = zindex;
+  r->sym = (struct sym_text *) sym;
+
+  GARY_INIT(r->text_variant, 0);
+  struct point_variant *v = GARY_PUSH(r->text_variant);
+  make_bitmap_label(v, r->sym);
 }
 
 void make_graph(void)
@@ -167,54 +199,92 @@ void make_graph(void)
   for (uns i=0; i<GARY_SIZE(buffer_line); i++)
   {
     struct osm_way *way = (struct osm_way *) buffer_line[i].line->s.o;
-    struct graph_node *prev = NULL;
-    struct osm_node *prev_node = NULL;
+    struct graph_node *g_prev = NULL;
+    struct osm_node *o_prev = NULL;
+
     CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
     {
       // FIXME: Shall osm_object's type be checked here?
-      struct osm_node *node = (struct osm_node *) ref->o;
+      struct osm_node *o_node = (struct osm_node *) ref->o;
 
-      struct graph_node *n = hash_find(ref->o->id);
-      if (!n)
+      struct graph_node *g_node = hash_find(ref->o->id);
+      if (!g_node)
       {
-        n = hash_new(ref->o->id);
-        GARY_INIT(n->edges, 0);
+        g_node = hash_new(ref->o->id);
+        GARY_INIT(g_node->edges, 0);
+        g_node->o = o_node;
+        g_node->id = ref->o->id;
+        g_node->num = num_nodes++;
       }
 
-      if (! prev)
+      if (! g_prev)
       {
-        prev = n;
-        prev_node = node;
+        g_prev = g_node;
+        o_prev = o_node;
         continue;
       }
 
-      struct graph_edge *e = (struct graph_edge *) mp_alloc(mp_edges, sizeof(struct graph_edge));
+      struct graph_edge *e = mp_alloc(mp_edges, sizeof(struct graph_edge)); num_edges_dbg++;
+      e->num = num_edges++;
       e->id = buffer_line[i].line->s.o->id;
       e->color = buffer_line[i].line->color;
-      e->length = hypot(abs(prev_node->x - node->x), abs(prev_node->y - node->y));
+      e->length = hypot(abs(o_prev->x - o_node->x), abs(o_prev->y - o_node->y));
       e->visited = 0;
       e->prev = NULL;
       e->next = NULL;
-      e->n1 = prev;
-      e->n2 = n;
-      e->longline = -1;
+      e->n1 = g_prev;
+      e->n2 = g_node;
+      e->longline = (uns) -1;
       e->text = NULL;
       e->sym = buffer_line[i].line;
+      e->dir = 0;
 
-      struct graph_edge **edge = GARY_PUSH(prev->edges);
+      struct graph_edge **edge = GARY_PUSH(g_prev->edges);
       *edge = e;
-      edge = GARY_PUSH(n->edges);
+      edge = GARY_PUSH(g_node->edges);
       *edge = e;
+
+      g_prev = g_node;
+      o_prev = o_node;
+    }
+  }
+}
+
+void dump_graph(void)
+{
+  HASH_FOR_ALL(hash, node)
+  {
+    printf("* Node: (%d) #%ju [%.2f; %.2f]\n", node->num, node->id, node->o->x, node->o->y);
+    for (uns i=0; i<GARY_SIZE(node->edges); i++)
+    {
+      struct graph_edge *e = node->edges[i];
+      printf("\t edge (%d) #%ju to ", e->num, e->id);
+      if (node->edges[i]->n1->id == node->id)
+        printf("(%d) #%ju [%.2f; %.2f]\n", e->n2->num, e->n2->id, e->n2->o->x, e->n2->o->y);
+      else if (node->edges[i]->n2->id == node->id)
+        printf("(%d) #%ju [%.2f; %.2f]\n", e->n1->num, e->n1->id, e->n1->o->x, e->n1->o->y);
+      else
+        printf("BEWARE! BEWARE! BEWARE!\n");
+
+      printf("\t\t");
+      if (node->edges[i]->text) printf(" labelled %s;", osm_val_decode(node->edges[i]->text->text));
+      printf(" colored %d;", node->edges[i]->color);
+      printf("   length %.2f", node->edges[i]->length);
+      printf("\n");
     }
   }
+  HASH_END_FOR;
 }
 
 void label_graph(void)
 {
+printf("There are %u line labels requested\n", GARY_SIZE(buffer_linelabel));
   for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
   {
+    printf("Labelling nodes of way %s\n", osm_val_decode(buffer_linelabel[i].text->text));
     CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
     {
+      printf("Looking for node %ju\n", ref->o->id);
       struct graph_node *n = hash_find(ref->o->id);
       if (n == NULL)
       {
@@ -222,11 +292,14 @@ void label_graph(void)
       }
       else
       {
+        printf("Searching among %u edges\n", GARY_SIZE(n->edges));
         for (uns j=0; j<GARY_SIZE(n->edges); j++)
         {
-          if (n->edges[j]->id == ((struct osm_object *) buffer_linelabel[i].way)->id)
+          if (n->edges[j]->id == buffer_linelabel[i].way->o.id)
           {
+            printf("Labelling node %ju\n", n->id);
             n->edges[j]->text = buffer_linelabel[i].text;
+            n->edges[j]->zindex = buffer_linelabel[i].zindex;
           }
         }
       }
@@ -254,12 +327,10 @@ void join_edge(struct graph_edge *e, int dir)
     struct graph_edge *other = other_node->edges[i];
     if (! other->visited)
     {
-    printf("Trying to add %dth edge\n", GARY_SIZE(bfs_queue)+1);
     struct graph_edge **new = GARY_PUSH(bfs_queue);
     *new = other_node->edges[i];
     }
 
-    //if (1) // FIXME: same labels but not the same edge
     if ((!other->visited) && (e->text) && (other->text) && (e->text->text == other->text->text))
     {
       if (e->color == other_node->edges[i]->color)
@@ -304,32 +375,32 @@ void join_edge(struct graph_edge *e, int dir)
   }
 }
 
-void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
-{
-  struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
-  ll->way = (struct osm_way *) o;
-  ll->text = (struct sym_text *) sym;
-  ll->zindex = zindex;
-}
-
-void bfs(void)
+void bfs2(void)
 {
   GARY_INIT(bfs_queue, 0);
   GARY_INIT(longlines, 0);
 
+  printf("Making longlines from %u causal lines, using %d graph edges\n", GARY_SIZE(buffer_line), num_edges_dbg);
+
   HASH_FOR_ALL(hash, node)
   {
     for (uns i=0; i<GARY_SIZE(node->edges); i++)
     {
       struct graph_edge *e = node->edges[i];
 
-      if (e->visited) HASH_CONTINUE;
+//      printf("Examining edge from [%.2f; %.2f] to [%.2f; %.2f]\n",
+//              e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y);
+
+      // if (e->visited) HASH_CONTINUE; // FIXME: Is is correct?
+      if (e->visited) continue;
+//      printf("Continuing\n");
       if (e->longline == (uns) -1)
       {
         GARY_PUSH(longlines);
         e->longline = num_longlines++;
-        longlines[num_longlines].first = e;
+        longlines[e->longline].first = e;
       }
+//      printf("Longline is %u\n", e->longline);
 
       e->visited = 1;
 
@@ -348,25 +419,254 @@ void bfs(void)
   GARY_FREE(bfs_queue);
 }
 
-void make_segments(void)
+void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, int dir)
 {
-  GARY_INIT(requests_line, 0);
+  ASSERT(dir < 3);
+  struct graph_edge *candidate = NULL;
+
+  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);
+
+
+  for (uns i=0; i<GARY_SIZE(node->edges); i++)
+  {
+    struct graph_edge *other = node->edges[i];
+printf("Touching %d\n", other->num);
+if (other->num == 44) printf("Longline of 44 is %u\n", other->longline);
+    if ((other->longline != (uns) -1) && (other->longline != e->longline)) continue;
+
+    if (! other->visited) {
+    struct graph_edge **e_ptr = GARY_PUSH(bfs_queue);
+    *e_ptr = other;
+    other->visited = 1;
+    }
+
+    if (((other->n1->id == node->id) && (other->n2->id == anode->id)) ||
+        ((other->n2->id == node->id) && (other->n1->id == anode->id)))
+        continue;
 
+    if (((other->n1->id == node->id) || (other->n2->id == node->id)) &&
+        (e->text) && (other->text) && (e->text->text == other->text->text))
+    {
+      if (! candidate || (other->length > candidate->length))
+      candidate = other;
+    }
+  }
+
+  if (candidate)
+  {
+    struct graph_edge *other = candidate;
+dbg_num_hits++;
+      other->longline = e->longline;
+      other->dir = dir;
+      other->anode = (other->n1->id == node->id ? other->n2 : other->n1);
+      other->bnode = (other->n1->id == node->id ? other->n1 : other->n2);
+      switch (dir)
+      {
+        case 1:
+          e->prev = other;
+          other->next = e;
+          longlines[other->longline].first = other;
+          break;
+        case 2:
+          e->next = other;
+          other->prev = e;
+          break;
+        default:
+          printf("Oops\n");
+          ASSERT(0);
+      }
+  }
+}
+
+void bfs(void)
+{
+  for (uns i=0; i<GARY_SIZE(bfs_queue); i++)
+  {
+    struct graph_edge *cur = bfs_queue[i];
+    printf("Exploring new edge, %d\n", cur->num);
+    //ASSERT(! cur->visited);
+
+    cur->visited = 1;
+    if (cur->longline == (uns) -1)
+    {
+      GARY_PUSH(longlines);
+      cur->longline = num_longlines++;
+      longlines[cur->longline].first = cur;
+    }
+
+    if (!cur->anode)
+    {
+      bfs_edge(cur, cur->n1, cur->n2, 1);
+      bfs_edge(cur, cur->n2, cur->n1, 2);
+    }
+    else
+    {
+      bfs_edge(cur, cur->anode, cur->bnode, cur->dir);
+    }
+  }
+}
+
+void bfs_wrapper(void)
+{
+  GARY_INIT(bfs_queue, 0);
+  GARY_INIT(longlines, 0);
+
+  HASH_FOR_ALL(hash, node)
+  {
+    for (uns i=0; i<GARY_SIZE(node->edges); i++)
+    {
+      if (! node->edges[i]->visited)
+      {
+        printf("Running new BFS\n");
+        GARY_RESIZE(bfs_queue, 0);
+        struct graph_edge **e = GARY_PUSH(bfs_queue);
+        *e = node->edges[i];
+        bfs();
+        //dump_longlines();
+        printf("Joined %d edges\n", dbg_num_hits); dbg_num_hits = 0;
+        printf("Planned %u edges\n", GARY_SIZE(bfs_queue));
+      }
+    }
+  }
+  HASH_END_FOR;
+
+  GARY_FREE(bfs_queue);
+}
+
+void oldbfs(void)
+{
+  printf("Starting outer BFS\n");
+  printf("There are %u buffered lines and %d eges\n", GARY_SIZE(buffer_line), num_edges_dbg);
+
+  GARY_INIT(bfs_queue, 0);
+  GARY_INIT(longlines, 0);
+
+  int dbg_bfs_continues = 0;
+
+  HASH_FOR_ALL(hash, node)
+  {
+    // FIXME: Skip if visited node
+
+    for (uns i=0; i<GARY_SIZE(node->edges); i++)
+    {
+      struct graph_edge *e = node->edges[i];
+
+      if (e->visited) continue;
+
+      // BFS itself
+      for (uns i1=0; i1<GARY_SIZE(e->n1->edges); i1++)
+      {
+        struct graph_edge *other = e->n1->edges[i1];
+        if (other->visited) { dbg_bfs_continues++; continue; }
+
+        if (((other->n1->id == e->n1->id) || (other->n2->id == e->n1->id)) &&
+            (e->text) && (other->text) && (e->text->text == other->text->text))
+        {
+//          printf("Hit\n");
+          other->visited = 1;
+        }
+      }
+      for (uns i2=0; i2<GARY_SIZE(e->n2->edges); i2++)
+      {
+        struct graph_edge *other = e->n2->edges[i2];
+        if (other->visited) {dbg_bfs_continues++; continue; }
+
+        if (((other->n1->id == e->n2->id) || (other->n2->id == e->n2->id)) &&
+            (e->text) && (other->text) && (e->text->text == other->text->text))
+        {
+//          printf("Hit\n");
+          other->visited = 1;
+        }
+      }
+    }
+  }
+
+  HASH_END_FOR;
+  printf("Total: %d hits, %d visited edges skipped\n", dbg_num_hits, dbg_bfs_continues);
+
+  GARY_FREE(bfs_queue);
+}
+
+void dump_longlines(void)
+{
+  for (uns i=0; i<GARY_SIZE(longlines); i++)
+  {
+    struct graph_edge *e = longlines[i].first;
+
+    printf("> Longline %u;", i);
+    if (longlines[i].first->text) printf(" labelled %s", osm_val_decode(longlines[i].first->text->text));
+    printf("\n");
+    while (e)
+    {
+      printf("\t#%ju (%d)", e->id, e->num);
+      switch (e->dir)
+      {
+      case 1:
+	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);
+	break;
+      case 2:
+	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);
+	break;
+      case 0:
+	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);
+	break;
+      default:
+        printf("%d\n", e->dir);
+        ASSERT(0);
+      }
+      e = e->next;
+    }
+  }
+}
+
+void make_segments(void)
+{
+printf("Analysing %u longlines\n", GARY_SIZE(longlines));
   for (uns i=0; i<GARY_SIZE(longlines); i++)
   {
+    if (! longlines[i].first->text) continue;
+//    printf("Survived! %s\n", osm_val_decode(longlines[i].first->text->text));
+printf("New longline\n");
     struct request_line *request = GARY_PUSH(requests_line);
+    request->request.ind = -1;
+    request->request.type = REQUEST_LINELABEL;
+
     GARY_INIT(request->segments, 0);
+    request->num_segments = 0;
+
+    // ->num_variants FIXME
+    // ->variants FIXME
+
     struct graph_edge *e = longlines[i].first;
+
+    if (! e) printf("Oops\n");
+    num_requests++;
     while (e)
     {
+      if (! e->text) break;
       struct request_segment *r = GARY_PUSH(request->segments);
       request->num_segments++;
-      r->x1 = ((struct osm_node *) e->n1)->x;
-      r->y1 = ((struct osm_node *) e->n1)->y;
-      r->x2 = ((struct osm_node *) e->n2)->x;
-      r->y2 = ((struct osm_node *) e->n2)->y;
+
+      r->request.ind = num_requests++;
+      r->request.type = REQUEST_SEGMENT;
+
+      struct osm_node *n = e->n1->o;
+      r->x1 = n->x;
+      r->y1 = n->y;
+      n = e->n2->o;
+      r->x2 = n->x;
+      r->y2 = n->y;
+      r->k = abs(r->x2 - r->x1) / (abs(r->y2 - r->y1) + 0.001); // FIXME: Hack to prevent floating point exception when y2 = y1
+
+//printf("Segment [%.2f; %.2f] -- [%.2f; %.2f]\n", r->x1, r->y1, r->x2, r->y2);
+
       r->sym = e->sym;
-      r->k = abs(r->x2 - r->x1) / abs(r->y2 - r->y1);
+      r->zindex = e->zindex;
+      r->text = malloc(sizeof(struct sym_text));
+      *(r->text) = *(e->text);
+      r->text->x = r->x1;
+      r->text->y = r->y1;
+
       r->variant = malloc(sizeof(struct point_variant)); // FIXME
       make_bitmap_label(r->variant, e->text);
 
@@ -375,52 +675,167 @@ void make_segments(void)
   }
 }
 
+void dump_linelabel_requests(void)
+{
+  for (uns i=0; i<GARY_SIZE(requests_line); i++)
+  {
+    printf("Longline of %d segments, labelled %s\n", requests_line[i].num_segments, osm_val_decode(requests_line[i].segments[0].text->text));
+  }
+}
+
+void dump_individual(struct individual *individual)
+{
+  for (uns i=0; i<GARY_SIZE(individual->placements); i++)
+  {
+    struct placement *p = &(individual->placements[i]);
+
+    switch (p->request->type)
+    {
+      case REQUEST_POINT:
+        printf("Point at [%.2f; %.2f]\n", p->x, p->y);
+        break;
+      case REQUEST_LINELABEL: ;
+        struct request_line *rl = (struct request_line *) p->request;
+        printf("%d-segment longline %s\n", rl->num_segments, osm_val_decode(rl->segments[0].text->text));
+        break;
+      case REQUEST_AREALABEL: ;
+        struct request_area *ra = (struct request_area *) p->request;
+        printf("Area label %s at [%.2f; %.2f]\n", osm_val_decode(ra->sym->text), p->x, p->y);
+    }
+  }
+  printf("\nTotal penalty: %d\n", individual->penalty);
+}
+
 void labeller_label(void)
 {
   make_graph();
   label_graph();
-  bfs();
+dump_graph();
+  bfs_wrapper();
+dump_longlines();
   make_segments();
+dump_linelabel_requests();
+
+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));
 
+  GARY_INIT(population1, conf_pop_size);
+  GARY_INIT(population2, conf_pop_size);
   make_population();
 
+  printf("Dealing with %d requests\n", num_requests);
+
+/*
   while (! shall_terminate())
   {
-    // sort population by fitness
-    // alloc new population
+    iteration++;
+
+    struct individual **swp = population1;
+    population1 = population2;
+    population2 = swp;
+    pop2_ind = 0;
+  }
+*/
+
+  dump_individual(population1[0]);
+
+  for (uns i=0; i<GARY_SIZE(population1[0]->placements); i++)
+  {
+    switch (population1[0]->placements[i].request->type)
+    {
+      case REQUEST_POINT: ;
+        struct request_point *rp = (struct request_point *) population1[0]->placements[i].request;
+        switch (rp->sym->type)
+        {
+          case SYMBOLIZER_POINT: ;
+//          printf("Moving point to final destination\n");
+	    struct sym_point *sp = (struct sym_point *) rp->sym;
+	    sp->x = population1[0]->placements[i].x;
+	    sp->y = population1[0]->placements[i].y;
+            sym_plan((struct symbol *) sp, rp->zindex);
+	    break;
+	  case SYMBOLIZER_ICON: ;
+//          printf("Moving icon to final destination\n");
+	    struct sym_icon *si = (struct sym_icon *) rp->sym;
+	    si->sir.x = population1[0]->placements[i].x;
+	    si->sir.y = population1[0]->placements[i].y;
+            sym_plan((struct symbol *) si, rp->zindex);
+	    break;
+	  default:
+	    ;
+        }
+        break;
+      case REQUEST_AREALABEL: ;
+        struct request_area *ra = (struct request_area *) population1[0]->placements[i].request;
+        sym_plan((struct symbol *) ra->sym, ra->zindex);
+        break;
+
+      case REQUEST_LINELABEL: ;
+        struct request_line *rl = (struct request_line *) population1[0]->placements[i].request;
+        for (uns j=0; j<GARY_SIZE(rl->segments); j++)
+        {
+//          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);
+          rl->segments[j].text->next_duplicate = NULL;
+          rl->segments[j].text->next_in_tile = NULL;
+          rl->segments[j].text->x = population1[0]->placements[i].x;
+          rl->segments[j].text->y = population1[0]->placements[i].y;
+          sym_plan((struct symbol *) rl->segments[j].text, rl->segments[j].zindex); // FIXME: z-index
+        }
+        break;
+/*
+      case REQUEST_SEGMENT: ;
+        struct request_segment *rs = (struct request_segment *) population1[0]->placements[i].request;
+        printf("Segment!\n");
+*/
+    }
+  }
+
+  return;
+
+  while (! shall_terminate())
+  {
+    iteration++;
+
     breed();
     mutate();
     elite();
     rank_population();
+    // sort population by fitness
+
+    struct individual **swp = population1;
+    population1 = population2;
+    printf("Swapped populations\n");
+    population2 = swp;
+    // GARY_RESIZE(population2, 0) -- is it needed?
+    pop2_ind = 0;
   }
 }
 
 void make_population(void)
 {
-  GARY_INIT(population1, 0);
   for (int i=0; i<conf_pop_size; i++)
   {
-    struct individual *individual = ep_alloc(ep_individuals);
-    struct individual **ind = GARY_PUSH(population1);
-    *ind = individual;
-    GARY_INIT(individual->map, 0);
-    GARY_INIT(individual->placements, 0);
+    struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
+    population1[i] = individual;
 
+    int p = 0;
     for (uns j=0; j<GARY_SIZE(requests_point); j++)
     {
-      struct placement *p = GARY_PUSH(individual->placements);
-      init_placement(p, (struct request *) &requests_point[i]);
+      init_placement(&(individual->placements[p++]), (struct request *) &requests_point[j]);
     }
     for (uns j=0; j<GARY_SIZE(requests_line); j++)
     {
-      struct placement *p = GARY_PUSH(individual->placements);
-      init_placement(p, (struct request *) &requests_line[i]);
+      init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j]);
+      for (uns k=0; k<GARY_SIZE(requests_line[j].segments); k++)
+      {
+	init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j].segments[k]);
+      }
     }
     for (uns j=0; j<GARY_SIZE(requests_area); j++)
     {
-      struct placement *p = GARY_PUSH(individual->placements);
-      init_placement(p, (struct request *) &requests_area[i]);
+      init_placement(&(individual->placements[p++]), (struct request *) &requests_area[j]);
     }
+
+    ASSERT(p == num_requests);
   }
 }
 
@@ -444,27 +859,34 @@ void breed(void)
 {
   int acc = 0;
   int i=0;
-  int conf_breed_pop_size = conf_breed_pop_size_perc * conf_pop_size;
+  printf("%.2f\n", ((double) conf_breed_pop_size_perc/100));
+  int conf_breed_pop_size = ((double) conf_breed_pop_size_perc/100) * conf_pop_size;
   struct individual **breed_buffer;
-  while (i < conf_breed_rbest_perc * conf_pop_size)
+  while (i < conf_breed_pop_size)
   {
+  printf("%d < %d, breeding\n", i, conf_breed_pop_size);
     int parent1 = randint(1, conf_breed_pop_size);
     int parent2 = randint(1, conf_breed_pop_size);
+    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);
     breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
-    population2[2*i] = breed_buffer[0];
-    population2[2*i+1] = breed_buffer[1];
+    population2[pop2_ind++] = breed_buffer[0];
+    population2[pop2_ind++] = breed_buffer[1];
     free(breed_buffer);
+    i++;
   }
 
   acc += conf_breed_rbest_perc;
 
+  return; // FIXME: DEBUG HACK
+
   int remaining = (1 - acc) * (conf_pop_size * conf_breed_perc);
   int step = remaining / conf_pop_size;
   for (; i<conf_pop_size; i += 2)
   {
-    breed_buffer = perform_crossover(population1[i*step], population1[i*(step+1)]);
-    population2[2*i] = breed_buffer[0];
-    population2[2*i+1] = breed_buffer[1];
+    printf("Asking for %d and %d of %d\n", i*step, i*(step+1), conf_pop_size);
+    breed_buffer = perform_crossover(population1[i*step], population1[i*step+1]);
+    population2[pop2_ind++] = breed_buffer[0];
+    population2[pop2_ind++] = breed_buffer[1];
   }
 
   // FIXME: Could there be one missing individual?
@@ -473,16 +895,17 @@ void breed(void)
 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
 {
   struct individual **buffer = malloc(2*sizeof(struct individual));
-  struct individual *child1 = ep_alloc(ep_individuals);
-  struct individual *child2 = ep_alloc(ep_individuals);
+  struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
+  struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
+
+  printf("Performing crossover\n");
 
   for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
   {
+    printf("%dth placement out of %d\n", i, num_requests);
     if (! parent1->placements[i].processed)
     {
-      struct placement **clos_symbols;
-      GARY_INIT(clos_symbols, 0);
-      get_closure(clos_symbols, &(parent1->placements[i]), parent1, parent2);
+      struct placement **clos_symbols = get_closure(&(parent1->placements[i]), parent1, parent2);
       int x = randint(1, 2);
 
       if (x == 1)
@@ -495,6 +918,7 @@ struct individual **perform_crossover(struct individual *parent1, struct individ
         copy_symbols(clos_symbols, parent2, child1);
         copy_symbols(clos_symbols, parent1, child2);
       }
+      printf("Symbols copied; %lld\n", GARY_SIZE(clos_symbols));
       GARY_FREE(clos_symbols);
     }
 
@@ -517,8 +941,9 @@ void mutate(void)
   while (i < conf_mutate_rbest_perc * conf_pop_size)
   {
     int ind = randint(1, conf_mutate_pop_size);
-    population2[pop2_ind] = population1[ind];
+    copy_individual(population2[pop2_ind], population1[ind]);
     perform_mutation(population2[pop2_ind]);
+    pop2_ind++;
   }
 }
 
@@ -557,7 +982,7 @@ void elite(void)
 {
   for (int i=0; i<conf_elite_perc * conf_pop_size; i++)
   {
-    population2[pop2_ind] = population1[0];
+    population2[pop2_ind++] = population1[0];
   }
 }
 
@@ -602,11 +1027,16 @@ struct map_part **get_parts(struct placement *symbol, struct individual *individ
 int randint(int min, int max)
 {
   int r = random();
+  //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)));
+  return min + (r % (max - min));
   return (r * (max - min));
 }
 
-void get_closure(struct placement **closure UNUSED, struct placement *placement UNUSED, struct individual *parent1 UNUSED, struct individual *parent2 UNUSED)
+struct placement **get_closure(struct placement *placement, struct individual *parent1, struct individual *parent2 UNUSED)
 {
+  printf("Getting closure\n");
+  struct placement **closure;
+  GARY_INIT(closure, 0);
   bool *chosen = malloc(GARY_SIZE(parent1->placements) * sizeof(bool));
   chosen[placement->request->ind] = 1;
 
@@ -615,6 +1045,7 @@ void get_closure(struct placement **closure UNUSED, struct placement *placement
   uns first = 0;
   while (first < GARY_SIZE(closure))
   {
+    printf("Iterating, first is %d\n", first);
     struct placement **overlapping = get_overlapping(placement);
     filter(overlapping, chosen);
     for (uns j=0; j<GARY_SIZE(overlapping); j++)
@@ -623,15 +1054,21 @@ void get_closure(struct placement **closure UNUSED, struct placement *placement
       chosen[overlapping[j]->request->ind] = 1;
     }
     GARY_FREE(overlapping);
+    first++;
   }
+
+  return closure;
 }
 
 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child)
 {
+  //printf("%d\n", child->penalty);
+  //printf("Closure size: %lld\n", GARY_SIZE(closure));
   for (uns i=0; i<GARY_SIZE(closure); i++)
   {
     int ind = closure[i]->request->ind;
     child->placements[ind] = parent->placements[ind];
+    child->placements[ind].processed = 0;
   }
 }
 
@@ -650,16 +1087,45 @@ void move_symbol_point(struct placement *p)
   p->y += (double) (move_min + randdouble()) * flip(1, -1);
 }
 
-void init_placement(struct placement *p UNUSED, struct request *r UNUSED)
+void init_placement(struct placement *p, struct request *r)
 {
   // FIXME
+  p->request = r;
+  p->processed = 0;
+  switch (r->type)
+  {
+    case REQUEST_POINT: ;
+      struct request_point *rp = (struct request_point *) r;
+      p->x = rp->x;
+      p->y = rp->y;
+      break;
+    case REQUEST_SEGMENT: ;
+      struct request_segment *rs = (struct request_segment *) r;
+      p->x = rs->x2;
+      p->y = rs->y2;
+      break;
+    case REQUEST_AREALABEL: ;
+      struct request_area *ra = (struct request_area *) r;
+      struct sym_text *st = ra->sym;
+      p->x = st->x;
+      p->y = st->y;
+  }
+}
+
+void init_individual(struct individual *i)
+{
+//printf("Initing individual\n");
+  GARY_INIT(i->placements, num_requests);
+  GARY_INIT(i->map, 0);
+  i->penalty = 0; // FIXME
 }
 
 struct placement **get_overlapping(struct placement *p UNUSED)
 {
   struct placement **buffer;
   GARY_INIT(buffer, 0);
-return buffer; }
+  return buffer;
+}
 
 void filter(struct placement **list UNUSED, bool *pred UNUSED)
 {
@@ -676,3 +1142,21 @@ double randdouble(void)
   // FIXME: How the hell shall double in range <0, 1> be generated? O:)
   return 0.5;
 }
+
+void cleanup(void)
+{
+  hash_cleanup();
+  GARY_FREE(requests_point);
+  GARY_FREE(requests_line);
+  GARY_FREE(requests_area);
+}
+
+void copy_individual(struct individual *src, struct individual *dest)
+{
+  src->penalty = dest->penalty;
+  GARY_INIT(dest->placements, GARY_SIZE(src->placements));
+  for (uns i=0; i<GARY_SIZE(src->placements); i++)
+  {
+    dest->placements[i] = src->placements[i];
+  }
+}