[leo.git] / labeller.c

#include <ucw/lib.h>
#include <ucw/gary.h>
#include <ucw/mempool.h>
#include <ucw/eltpool.h>

#include "leo.h"
#include "sym.h"
#include "map.h"
#include "labeller.h"

#define HASH_NODE struct graph_node
#define HASH_PREFIX(x) hash_##x
#define HASH_KEY_ATOMIC id
#define HASH_WANT_FIND
#define HASH_WANT_NEW
#define HASH_WANT_CLEANUP
#include <ucw/hashtable.h>

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <fcntl.h>
#include <limits.h>

#define BLOCK_SIZE 4096

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 longline *longlines; int num_longlines;
static struct buffer_line *buffer_line;
static struct buffer_linelabel *buffer_linelabel;

struct eltpool *ep_individuals;

struct individual **population1;
struct individual **population2;

int dbg_segments = VERBOSITY_NONE;
int dbg_plan = VERBOSITY_NONE;
int dbg_requests = VERBOSITY_NONE;
int dbg_graph = VERBOSITY_NONE;
int dbg_bfs = VERBOSITY_NONE;
int dbg_map_parts = VERBOSITY_NONE;
int dbg_movement = VERBOSITY_NONE;
int dbg_init = VERBOSITY_NONE;
int dbg_overlaps = VERBOSITY_NONE;
int dbg_rank = VERBOSITY_NONE;
int dbg_evolution = VERBOSITY_INDIVIDUAL;
int dbg_mutation = VERBOSITY_NONE;
int dbg_breeding = VERBOSITY_NONE;

int page_width_int;
int page_height_int;

int num_nodes;
int num_edges = 0;
int dbg_num_hits = 0;

int conf_pop_size = 50;
int conf_fit_size = 1;

int conf_penalty_bound = 0;
int conf_stagnation_bound = 0;
int conf_iteration_limit = 100;

int conf_term_cond = TERM_COND_ITERATIONS;

double conf_breed_pop_size = 0.4;
double conf_breed_rbest = 0.2;

int breed_pop_size;
int breed_rbest_size;

bool conf_mutate_children = 1;
double conf_mutate_children_prob = 1.0;

double conf_mutate_pop_size = 0.4;
double conf_mutate_rbest = 0.2;

double conf_mutate_move_bound = 0.1;
double conf_mutate_regen_bound = 0.0;
double conf_mutate_chvar_bound = 0.0;

int mutate_pop_size;
int mutate_rbest_size;

double conf_elite_pop_size = 0.2;
int elite_pop_size;

double conf_max_section_length = 100;
double conf_max_section_overlay = 10;

int old_best = INT_MAX;
int iteration = 0;
int pop2_ind;

// In milimeters
int move_min = 0;
int move_max = 5;

int num_requests = 0;
int num_placements = 0;

// In milimeters
int conf_map_part_width = 5;
int conf_map_part_height = 5;

uns num_map_parts_row;
uns num_map_parts_col;
uns num_map_parts;

void compute_sizes(void);

void make_population(void);
bool shall_terminate(void);
void breed(void);
void mutate(void);
void elite(void);
void rank_population(void);
void plan_individual(struct individual *individual);

int overlaps(struct placement *p1, struct placement *p2);
int get_overlap(struct placement *p);
int individual_overlap(struct individual *individual);

double get_distance(struct placement *p);
double individual_distances(struct individual *individual);

double get_omittment(struct placement *p);
double individual_omittment(struct individual *individual);

struct individual **perform_crossover(struct individual *parent1, struct individual *parent2);
void perform_mutation(struct individual *individual);
void init_placement(struct placement *p, struct individual *individual, struct request *r);
void init_individual(struct individual *i);
void copy_individual(struct individual *src, struct individual *dest);
int cmp_individual(const void *a, const void *b);

void clear_individual(struct individual *individual);
void clear_population(struct individual **pop);

void make_bitmap(struct variant *v, struct symbol *sym);
void make_bitmap_icon(struct variant *v, struct sym_icon *si);
void make_bitmap_point(struct variant *v, struct sym_point *sp);
void make_bitmap_label(struct variant *v, struct sym_text *text);

double gen_movement(void);
double gen_movement_uniform(void);
void move_symbol(struct placement *p);
void move_symbol_point(struct placement *p);
void move_symbol_segment(struct placement *p);
void hide_segment_labels(struct individual *individual);

void gen_coords(struct placement *p);
void gen_coords_point(struct placement *p);
void gen_coords_segment(struct placement *p);
void gen_coords_area(struct placement *p);

struct map_part **get_map_parts(struct placement *p);
void update_map_parts(struct placement *p);
void update_map_parts_delete(struct placement *p);
void update_map_parts_create(struct placement *p);
struct placement **get_closure(struct placement *placement);
void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child, bool **processed_ptr);
struct placement **get_overlapping(struct placement *p);
struct placement **filter(struct placement **list, bool **pred_ptr);


void make_graph(void);
void label_graph(void);
void bfs_wrapper(void);
void bfs(uns longline);
void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir);
void make_segments(void);

void cut_edge(struct graph_edge *e, double dist);
struct request_line *make_new_line(void);
struct request_section *make_new_section(struct request_line *rl);
struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym);

void dump_bitmaps(struct individual *individual);
void dump_graph(void);
void dump_longlines(void);
void dump_linelabel_requests(void);
void dump_individual(struct individual *individual);
void dump_label(struct symbol *sym);
void dump_penalties(struct individual **population);

int randint(int min, int max);
int flip(int a, int b);
double randdouble(void);

int max2(int a, int b);
int min2(int a, int b);
int max4(int a, int b, int c, int d);
int min4(int a, int b, int c, int d);

struct placement dummy_placement;

int max2(int a, int b)
{
  return (a > b ? a : b);
}

int min2(int a, int b)
{
  return (a < b ? a : b);
}

int max4(int a, int b, int c, int d)
{
  return max2(max2(a, b), max2(c, d));
}

int min4(int a, int b, int c, int d)
{
  return min2(min2(a, b), min2(c, d));
}

void dump_label(struct symbol *sym)
{
  switch (sym->type)
  {
    case SYMBOLIZER_TEXT: ;
      struct sym_text *st = (struct sym_text *) sym;
      printf("%s\n", osm_val_decode(st->text));
    default:
      // FIXME
      ;
  }
}

void labeller_init(void)
{
  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);
  ep_individuals = ep_new(sizeof(struct individual), 1);

  compute_sizes();
}

void make_bitmap(struct variant *v, struct symbol *sym)
{
  v->offset_x = v->offset_y = 0;

  switch (sym->type)
  {
    case SYMBOLIZER_POINT:
      make_bitmap_point(v, (struct sym_point *) sym);
      break;
    case SYMBOLIZER_ICON:
      make_bitmap_icon(v, (struct sym_icon *) sym);
      break;
    case SYMBOLIZER_TEXT:
      make_bitmap_label(v, (struct sym_text *) sym);
      break;
    default:
      ASSERT(sym->type != SYMBOLIZER_INVALID);
  }
}

void make_bitmap_icon(struct variant *v, struct sym_icon *si)
{
  v->width = si->sir.width + 1;
  v->height = si->sir.height + 1;
  v->bitmap = malloc(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 variant *v, struct sym_point *sp)
{
  v->width = v->height = sp->size + 1;
  v->bitmap = malloc(v->width * v->height * sizeof(bool));
  // FIXME: Okay, memset would be much nicer here
  for (int i=0; i<sp->size*sp->size; i++) v->bitmap[i] = 1;
}

void make_bitmap_label(struct variant *v, struct sym_text *text)
{
  int tw = ceil(text->tw);
  int th = ceil(text->th);

  double rotate_rad = text->rotate / (-180 / M_PI);

  // Initially, ll = [0; 0], lr = [tw, 0], ul = [0, th], ur = [tw, th]
  // They could be declared before but should not be initialized in code
  // as reassigning x-coordinate affects computation of y-cordinate
  int llx = 0;
  int lly = 0;

  int lrx = tw * cos(rotate_rad);
  int lry = tw * sin(rotate_rad);

  int ulx = th * sin(rotate_rad);
  int uly = th * cos(rotate_rad);

  int urx = tw * cos(rotate_rad) + th * sin(rotate_rad);
  int ury = tw * sin(rotate_rad) + th * cos(rotate_rad);

  int min_x = min4(llx, lrx, ulx, urx);
  int min_y = min4(lly, lry, uly, ury);
  int max_x = max4(llx, lrx, ulx, urx);
  int max_y = max4(lly, lry, uly, ury);

  v->width = max_x - min_x + 1;
  v->height = max_y - min_y + 1;
  v->bitmap = malloc(v->width * v->height * sizeof(bool));
  memset(v->bitmap, 0, v->width * v->height * sizeof(bool));

  for (int i=0; i<th; i++)
  {
    for (int j=0; j<tw; j++)
    {
      int nx = j*cos(rotate_rad) + i*sin(rotate_rad);
      int ny = j*sin(rotate_rad) + i*cos(rotate_rad);
      v->bitmap[(ny-min_y)*v->width + (nx-min_x)] = 1;
    }
  }
}

void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex)
{
  if (dbg_requests >= VERBOSITY_PLACEMENT)
    printf("Adding point\n");
  if (object->type != OSM_TYPE_NODE)
  {
    printf("Warning: Point label requested on non-point object\n");
    return;
  }

  struct request_point *r = GARY_PUSH(requests_point);

  r->request.type = REQUEST_POINT;
  r->request.ind = num_requests++;

  r->sym = sym;
  r->zindex = zindex;

  r->offset_x = 0;
  r->offset_y = 0;

  r->num_variants = 1;
  GARY_INIT(r->request.variants, 0);

  struct variant *v = GARY_PUSH(r->request.variants);

  struct osm_node *n = (struct osm_node *) object; // FIXME: Compiler warning
  r->x = n->x;
  r->y = n->y;
  make_bitmap(v, sym);
  switch (sym->type)
  {
    case SYMBOLIZER_ICON:
      // FIXME: Really?
      r->x = ((struct sym_icon *)sym)->sir.x;
      r->y = ((struct sym_icon *)sym)->sir.y;
      break;
    default:
      // FIXME
      return;
  }

  if (dbg_requests >= VERBOSITY_PLACEMENT)
    printf("Inited point to [%.2f; %.2f] on %u\n", r->x, r->y, r->zindex);
}

void labeller_add_line(struct symbol *sym, z_index_t zindex)
{
  if (dbg_requests >= VERBOSITY_PLACEMENT)
    printf("Adding line on %u\n", zindex);
  struct buffer_line *b = GARY_PUSH(buffer_line);
  b->line = (struct sym_line *) sym;
  b->zindex = zindex;
  sym_plan(sym, zindex);
}

void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
{
  if (o->type != OSM_TYPE_WAY)
  {
    printf("Linelabel request on object which is not way\n");
    return;
  }

  if (dbg_requests >= VERBOSITY_PLACEMENT)
    printf("Labelling way %ju on %u\n", o->id, zindex);
  struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
  ll->way = (struct osm_way *) o;
  ll->label = sym;
  ll->zindex = zindex;
}

void labeller_add_arealabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
{
  if (dbg_requests >= VERBOSITY_PLACEMENT)
    printf("Adding area on %u\n", zindex);
  struct request_area *r = GARY_PUSH(requests_area);

  r->request.type = REQUEST_AREA;
  r->request.ind = num_requests++;

  r->o = (struct osm_multipolygon *) o;
  r->zindex = zindex;
  r->label = sym;

  osm_obj_center(o, &(r->cx), &(r->cy));

  GARY_INIT(r->request.variants, 0);
  struct variant *v = GARY_PUSH(r->request.variants);
  make_bitmap(v, sym);
}

void make_graph(void)
{
  hash_init();
  struct mempool *mp_edges = mp_new(BLOCK_SIZE);

  if (dbg_graph >= VERBOSITY_GENERAL)
    printf("Extracting nodes, will iterate over %lld ways\n", GARY_SIZE(buffer_line));
  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 *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 *o_node = (struct osm_node *) ref->o;

      struct graph_node *g_node = hash_find(ref->o->id);
      if (!g_node)
      {
        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 (! g_prev)
      {
        g_prev = g_node;
        o_prev = o_node;
        continue;
      }

      struct graph_edge *e = mp_alloc(mp_edges, sizeof(struct graph_edge));
      e->num = num_edges++;
      e->id = buffer_line[i].line->s.o->id;
      e->color = buffer_line[i].line->color;
      e->length = hypot(abs(o_prev->x - o_node->x), abs(o_prev->y - o_node->y));
      e->visited = -1;
      e->prev = NULL;
      e->next = NULL;
      e->n1 = g_prev;
      e->n2 = g_node;
      e->longline = (uns) -1;
      e->line = buffer_line[i].line;
      e->dir = DIR_UNSET;
      e->label = NULL;

      struct graph_edge **edge = GARY_PUSH(g_prev->edges);
      *edge = e;
      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
      {
        // This shouldn't ever happen
        printf("BEWARE! Edge is associated with a node it doesn't belongs to!\n");
      }

      printf("\t\t");

      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));
      else if ((node->edges[i]->label)) printf("Labelled\n");

      printf(" colored %d;", node->edges[i]->color);
      printf("   length %.2f", node->edges[i]->length);
      printf("\n");
    }
  }
  HASH_END_FOR;
}

void label_graph(void)
{
  if (dbg_graph >= VERBOSITY_GENERAL)
    printf("There are %u line labels requested\n", GARY_SIZE(buffer_linelabel));
  for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
  {
    if (buffer_linelabel[i].label->type == SYMBOLIZER_TEXT)
    if (dbg_graph >= VERBOSITY_INDIVIDUAL)
      printf("Labelling nodes of way %s\n", osm_val_decode(((struct sym_text *) buffer_linelabel[i].label)->text));
    CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
    {
      if (dbg_graph >= VERBOSITY_PLACEMENT)
        printf("Looking for node %ju\n", ref->o->id);
      struct graph_node *n = hash_find(ref->o->id);
      if (n == NULL)
      {
        printf("BEWARE! Requested node couldn't be found.\n");
      }
      else
      {
        if (dbg_graph >= VERBOSITY_ALL)
          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 == buffer_linelabel[i].way->o.id)
          {
            if (dbg_graph >= VERBOSITY_ALL)
              printf("Labelling node %ju\n", n->id);
            n->edges[j]->label = buffer_linelabel[i].label;
            n->edges[j]->zindex = buffer_linelabel[i].zindex;
          }
        }
      }
    }
  }
}

void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir)
{
  if (dbg_bfs >= VERBOSITY_PLACEMENT)
    printf("BFS edge called for edge %d (going %d) in direction %d\n", e->num, e->dir, dir);
  struct graph_edge *candidate = NULL;

  for (uns i=0; i<GARY_SIZE(node->edges); i++)
  {
    struct graph_edge *other = node->edges[i];
    if ((other->longline != (uns) -1) && (other->longline != e->longline)) continue;

    if ((uns) other->visited != e->longline) {
    if (dbg_bfs >= VERBOSITY_PLACEMENT)
      printf("Pushing new edge %d / %ju\n", other->num, other->id);
    struct graph_edge **e_ptr = GARY_PUSH(bfs_queue);
    *e_ptr = other;
    other->visited = e->longline;
    }

    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->label) && (other->label) &&
        (e->label->type == SYMBOLIZER_TEXT) && (other->label->type == SYMBOLIZER_TEXT) &&
        (((struct sym_text *) e->label)->text == ((struct sym_text *) other->label)->text))
    {
      if (! candidate || (other->length > candidate->length))
      candidate = other;
    }
  }

  if (candidate)
  {
    if (dbg_bfs >= VERBOSITY_PLACEMENT)
      printf("New line in longline %u\n", e->longline);
    struct graph_edge *other = candidate;
      other->longline = e->longline;
      other->dir = dir;
      if (((dir == DIR_BWD) && (other->n1->id == node->id)) ||
          ((dir == DIR_FWD) && (other->n2->id == node->id)))
      {
        struct graph_node *swp = other->n2;
        other->n2 = other->n1;
        other->n1 = swp;
      }

      switch (dir)
      {
        case DIR_BWD:
          e->prev = other;
          other->next = e;
          longlines[other->longline].first = other;
          break;
        case DIR_FWD:
          e->next = other;
          other->prev = e;
          break;
        default:
          printf("Oops\n");
          ASSERT(0);
      }
  }
}

void bfs(uns longline)
{
  if (dbg_bfs >= VERBOSITY_INDIVIDUAL)
  {
    printf("BFS called for longline %u\n", longline);
    printf("%d longlines are believed to exist, %d exist\n", num_longlines, GARY_SIZE(longlines));
  }

  for (uns i=0; i<GARY_SIZE(bfs_queue); i++)
  {
    struct graph_edge *cur = bfs_queue[i];
    if (dbg_bfs >= VERBOSITY_PLACEMENT)
      printf("Exploring new edge %d; %d remaining\n", cur->num, GARY_SIZE(bfs_queue));

    cur->visited = longline;

    if (cur->longline == (uns) -1)
      continue;

    if (cur->dir == DIR_UNSET)
    {
      cur->dir = DIR_CENTER;
      bfs_edge(cur, cur->n1, cur->n2, DIR_BWD);
      bfs_edge(cur, cur->n2, cur->n1, DIR_FWD);
    }
    else
    {
      switch (cur->dir)
      {
        case DIR_BWD:
          bfs_edge(cur, cur->n1, cur->n2, cur->dir);
          break;
        case DIR_FWD:
          bfs_edge(cur, cur->n2, cur->n1, cur->dir);
          break;
        default:
          // FIXME
          ;
      }
    }
  }
}

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]->label) && (node->edges[i]->longline == (uns) -1))
      {
        GARY_PUSH(longlines);
        longlines[num_longlines].first = node->edges[i];

        if (dbg_bfs >= VERBOSITY_INDIVIDUAL)
        {
          printf("Running new BFS\n");
          printf("Creating longline %u\n", num_longlines);
        }

        GARY_RESIZE(bfs_queue, 0);
        struct graph_edge **e = GARY_PUSH(bfs_queue);
        *e = node->edges[i];
        node->edges[i]->longline = num_longlines;
        bfs(node->edges[i]->longline);

        if (dbg_bfs >= VERBOSITY_INDIVIDUAL)
        {
          printf("Joined %d edges\n", dbg_num_hits); dbg_num_hits = 0;
          printf("Planned %u edges\n", GARY_SIZE(bfs_queue));
        }
        num_longlines++;
      }
    }
  }
  HASH_END_FOR;

  GARY_FREE(bfs_queue);
}

void dump_longlines(void)
{
  printf("*** Longlines dump\n");
  for (uns i=0; i<GARY_SIZE(longlines); i++)
  {
    printf("Longline %u:", i);
    struct graph_edge *e = longlines[i].first;
    if ((e->label) && (e->label->type == SYMBOLIZER_TEXT))
      printf(" labelled %s", osm_val_decode(((struct sym_text *) e->label)->text));
    printf("\n");

    while (e)
    {
      printf("\t#%ju (%d): [%.2f; %.2f] -- [%.2f; %.2f] (dir %d)\n",
             e->id, e->num, e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y, e->dir);

      e = e->next;
    }
  }
}

struct request_line *make_new_line(void)
{
  struct request_line *rl = GARY_PUSH(requests_line);
  rl->request.ind = num_requests++;
  rl->request.type = REQUEST_LINE;
  GARY_INIT(rl->sections, 0);
  GARY_INIT(rl->request.variants, 0);

  return rl;
}

struct request_section *make_new_section(struct request_line *rl)
{
  struct request_section *rls = GARY_PUSH(rl->sections);
  rls->request.ind = num_requests++;
  rls->request.type = REQUEST_SECTION;
  rls->num_segments = 0;
  GARY_INIT(rls->segments, 0);
  GARY_INIT(rls->request.variants, 0);

  return rls;
}

struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym)
{
  struct request_segment *rs = GARY_PUSH(rls->segments);
  rls->num_segments++;

  rs->request.ind = num_requests++;
  rs->request.type = REQUEST_SEGMENT;

  GARY_INIT(rs->request.variants, 0);
  if (sym)
  {
    struct variant *v = GARY_PUSH(rs->request.variants);
    make_bitmap(v, sym);
  }

  return rs;
}

void cut_edge(struct graph_edge *e, double dist)
{
  if (dbg_segments >= VERBOSITY_PLACEMENT)
    printf("Cutting [%.2f; %.2f] -- [%.2f; %.2f] to dist %.2f\n", e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y, dist);

  struct graph_edge *new = malloc(sizeof(struct graph_edge));
  *new = *e;
  e->next = new;

  switch (e->label->type)
  {
    case SYMBOLIZER_TEXT:
      new->label = malloc(sizeof(struct sym_text));
      *((struct sym_text *) new->label) = *((struct sym_text *) e->label);
      break;
    default:
      ;
  }

  struct osm_node *n1 = e->n1->o;
  struct osm_node *n2 = e->n2->o;

  if ((n1->x == n2->x) && (n1->y == n2->y))
  {
    printf("[%.2f; %.2f] -- [%.2f; %.2f]\n", n1->x, n1->y, n2->x, n2->y);
    if (dbg_segments >= VERBOSITY_PLACEMENT)
      printf("Won't cut point\n");
    return;
  }

  struct osm_node *n11 = malloc(sizeof(struct osm_node));
  struct graph_node *gn = malloc(sizeof(struct graph_node));
  gn->o = n11;
  double vsize = sqrt(pow(n1->x - n2->x, 2) + pow(n1->y - n2->y, 2));
  n11->x = n1->x + (n2->x - n1->x) / vsize * dist;
  n11->y = n1->y + (n2->y - n1->y) / vsize * dist;

  e->n2 = new->n1 = gn;

  e->length = hypot(abs(n1->x - n11->x), abs(n1->y - n11->y));
  new->length = hypot(abs(n11->x - n2->x), abs(n11->y - n2->y));
  new->visited = 0;
}

void make_segments(void)
{
  for (uns i=0; i<GARY_SIZE(longlines); i++)
  {
    // Skip lines which are not labelled
    if (! (longlines[i].first && longlines[i].first->label))
      continue;

    struct request_line *request = make_new_line();
    struct request_section *rls = make_new_section(request);
    struct request_segment *rs = NULL;

    struct graph_edge *e = longlines[i].first;
    double cur_length = 0;

    struct sym_text *st = NULL;
    if (e->label->type == SYMBOLIZER_TEXT)
    {
      st = (struct sym_text *) e->label;
    }
    else
    {
      // FIXME: Should other label types be supported in future?
      if (dbg_segments >= VERBOSITY_PLACEMENT)
        printf("Warning: Skipping line\n");
      continue;
    }

    if (dbg_segments >= VERBOSITY_INDIVIDUAL)
      printf("New longline\n");

    while (e)
    {
      if (e->visited < 0)
      {
        if (dbg_segments >= VERBOSITY_PLACEMENT)
          printf("BEWARE: Edge cycle\n");
        break;
      }
      e->visited = -1;

      if (dbg_segments >= VERBOSITY_PLACEMENT)
        printf("Taking edge from [%.2f; %.2f] to [%.2f; %.2f] of length %.2f\n", e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y, e->length);

      if (st && (e->length < st->tw))
      {
        e = e->next;
        if (dbg_segments >= VERBOSITY_PLACEMENT)
          printf("Warning: Skipping segment\n");
        continue;
      }

      if (cur_length + e->length > conf_max_section_length + conf_max_section_overlay)
      {
        if (dbg_segments >= VERBOSITY_PLACEMENT)
          printf("Edge too long, length is %.2f; %.2f - %.2f = %.2f\n", e->length, conf_max_section_length, cur_length, conf_max_section_length - cur_length);
        // HACK to prevent cutting to 0 lenght
        cut_edge(e, max2(conf_max_section_length - cur_length, 2));
      }

      rs = make_new_segment(rls, NULL);
      rs->label = malloc(sizeof(struct sym_text));
      *((struct sym_text *) rs->label) = *((struct sym_text *) e->label);

      rs->x1 = e->n1->o->x;
      rs->y1 = e->n1->o->y;
      rs->x2 = e->n2->o->x;
      rs->y2 = e->n2->o->y;

      rs->slope = (rs->y2 - rs->y1) / (rs->x2 - rs->x1);
      ((struct sym_text *) rs->label)->rotate = atan(rs->slope) * (-180 / M_PI);
      struct variant *v = GARY_PUSH(rs->request.variants);
      make_bitmap(v, rs->label);

      rs->zindex = e->zindex;

      cur_length += e->length;
      if (cur_length > conf_max_section_length)
      {
        if (dbg_segments >= VERBOSITY_PLACEMENT)
          printf("Making new section, new length would be %f, allowed is %.2f / %.2f\n", cur_length + e->length, conf_max_section_length, conf_max_section_overlay);

        rls = make_new_section(request);
        cur_length = 0;
      }

      e = e->next;
    }

    if (request->sections[0].num_segments == 0)
    {
      if (dbg_segments >= VERBOSITY_INDIVIDUAL)
        printf("WARNING: Longline without any segment, skipped\n");

      struct request_section *rls = &request->sections[0];
      GARY_FREE(rls->segments);
      GARY_FREE(rls->request.variants);

      struct request_line *rl = &requests_line[GARY_SIZE(requests_line)-1];
      GARY_FREE(rl->sections);
      GARY_FREE(rl->request.variants);

      GARY_POP(requests_line);
      num_requests -= 2;
    }
  }
}

void dump_linelabel_requests(void)
{
  for (uns i=0; i<GARY_SIZE(requests_line); i++)
  {
    if (requests_line[i].sections[0].num_segments == 0)
    {
      if (dbg_segments >= VERBOSITY_INDIVIDUAL)
        printf("Beware: Longline without any segment\n");
      continue;
    }

    printf("Request for linelabel, %d sections\n", GARY_SIZE(requests_line[i].sections));
    dump_label(requests_line[i].sections[0].segments[0].label);
    for (uns j=0; j<GARY_SIZE(requests_line[i].sections); j++)
    {
      printf("%d section, %d segments\n", j, GARY_SIZE(requests_line[i].sections[j].segments));
      for (uns k=0; k<GARY_SIZE(requests_line[i].sections[j].segments); k++)
      {
        struct request_segment *rs = &requests_line[i].sections[j].segments[k];
        printf("[%.2f; %.2f] -- [%.2f; %.2f]\n", rs->x1, rs->y1, rs->x2, rs->y2);
      }
    }
    printf("\n");
  }
}

void dump_bitmaps(struct individual *individual)
{
  bool *bitmap = malloc(page_width_int * page_height_int * sizeof(bool));
  printf("Bitmap size is %d\n", page_width_int * page_height_int);
  for (int i=0; i<page_height_int; i++)
    for (int j=0; j<page_width_int; j++)
      bitmap[i*page_width_int + j] = 0;

  int total = 0;
  for (uns i=0; i<GARY_SIZE(individual->placements); i++)
  {
    if (individual->placements[i].variant_used == -1) continue;

    struct placement *p = &(individual->placements[i]);
    struct variant *v = NULL;

    switch (p->request->type)
    {
      case REQUEST_SEGMENT: ;
      case REQUEST_POINT: ;
      case REQUEST_AREA: ;
        v = &(p->request->variants[p->variant_used]);
        break;
      default:
        ASSERT(p->request->type != REQUEST_INVALID);
        continue;
    }

    int base_x = p->x; int base_y = p->y;
    for (int dr = max2(0, 0-p->y); dr < v->height; dr++)
    {
      for (int dc = max2(0, 0-p->x); dc < v->width; dc++)
      {
        if (v->bitmap[dr * v->width + dc])
        {
          if (bitmap[(base_y + dr) * page_width_int + (base_x + dc)]) total += 1;
          bitmap[(base_y + dr) * page_width_int + (base_x + dc)] = 1;
        }
      }
    }
  }
  if (dbg_overlaps >= VERBOSITY_GENERAL)
    printf("There were %d collisions during bitmap dump\n", total);

  FILE *fd_dump = fopen("dump.pbm", "w");
  fprintf(fd_dump, "P1\n");
  fprintf(fd_dump, "%d %d\n", page_width_int, page_height_int);
  for (int i=0; i<page_height_int; i++)
  {
    for (int j=0; j<page_width_int; j++)
    {
      fprintf(fd_dump, "%d", bitmap[(int) (i*page_width_int + j)] ? 1 : 0);
    }
    fprintf(fd_dump, "\n");
  }
  fclose(fd_dump);

  free(bitmap);
}

void dump_individual(struct individual *individual)
{
  printf("*** Individual dump\n");
  printf("(There are %d requests)\n", num_requests);

  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] on %u\n", p->x, p->y, ((struct request_point *) p->request)->zindex);
        break;
      case REQUEST_LINE: ;
        struct request_line *rl = (struct request_line *) p->request;
        printf("Line: ");
        dump_label(rl->sections[0].segments[0].label);
        break;
      case REQUEST_SECTION: ;
        printf("*");
        break;
      case REQUEST_SEGMENT: ;
        if (p->variant_used >= 0)
          printf("Segment placed at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_segment *) p->request)->zindex);
        else
          printf("Segment not placed\n");
        break;
      case REQUEST_AREA: ;
        struct request_area *ra = (struct request_area *) p->request;
        printf("Area label ");
        dump_label(ra->label);
        printf(" at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_area *) p->request)->zindex);
        break;
      default:
        ASSERT(p->request->type != 0);
    }
  }
  printf("\nTotal penalty: %d\n", individual->penalty);
}

void plan_individual(struct individual *individual)
{
  for (uns i=0; i<GARY_SIZE(individual->placements); i++)
  {
    struct symbol *s = NULL;
    z_index_t zindex = 0;
    if (individual->placements[i].variant_used < 0) continue;
    switch (individual->placements[i].request->type)
    {
      case REQUEST_POINT: ;
        struct request_point *rp = (struct request_point *) individual->placements[i].request;
        s = rp->sym;
        zindex = rp->zindex;
        break;
      case REQUEST_SEGMENT: ;
        struct request_segment *rs = (struct request_segment *) individual->placements[i].request;
        s = rs->label;
        zindex = rs->zindex;
        break;
      case REQUEST_LINE: ;
        break;
      case REQUEST_AREA: ;
        struct request_area *ra = (struct request_area *) individual->placements[i].request;
        s = ra->label;
        zindex = ra->zindex;
        break;
      default:
        ASSERT(individual->placements[i].request != REQUEST_INVALID);
        continue;
    }

  if (dbg_plan >= VERBOSITY_PLACEMENT)
    printf("Will plan symbol at [%.2f; %.2f] on %u\n", individual->placements[i].x, individual->placements[i].y, zindex);

    if (s) switch (s->type)
    {
      case SYMBOLIZER_POINT: ;
        struct sym_point *sp = (struct sym_point *) s;
        sp->x = individual->placements[i].x;
        sp->y = individual->placements[i].y;
        sym_plan((struct symbol *) sp, zindex);
        break;
      case SYMBOLIZER_ICON: ;
        struct sym_icon *si = (struct sym_icon *) s;
        si->sir.x = individual->placements[i].x;
        si->sir.y = individual->placements[i].y;
        sym_plan((struct symbol *) si, zindex);
        break;
      case SYMBOLIZER_TEXT: ;
        struct sym_text *st = (struct sym_text *) s;
        st->x = individual->placements[i].x;
        st->y = individual->placements[i].y;
        st->next_duplicate = NULL;
        if (dbg_plan >= VERBOSITY_PLACEMENT)
          printf("Planning text %s at [%.2f; %.2f] on %u, with rotation %.2f\n", osm_val_decode(st->text), st->x, st->y, zindex, st->rotate);
        sym_plan((struct symbol *) st, zindex);
        break;
      default:
        ASSERT(s->type != SYMBOLIZER_INVALID);
    }
  }
}

void dump_penalties(struct individual **population)
{
  for (int i=0; i<conf_pop_size; i++)
  {
    printf("Individual %d has penalty %d\n", i, population[i]->penalty);
  }
}

void compute_sizes(void)
{
  page_width_int = floor(page_width);
  page_height_int = floor(page_height);

  num_map_parts_row = (page_width_int + conf_map_part_width) / conf_map_part_width;
  num_map_parts_col = (page_height_int + conf_map_part_height) / conf_map_part_height;
  num_map_parts = num_map_parts_row * num_map_parts_col;

  breed_pop_size = conf_breed_pop_size * conf_pop_size;
  breed_rbest_size = conf_breed_rbest * conf_pop_size;
  if (dbg_evolution >= VERBOSITY_GENERAL)
  {
    printf("Breeding parameters:\n");
    printf(" %d individuals are created\n", breed_pop_size);
    printf(" %d best individuals in old population are considered\n", breed_rbest_size);
  }

  mutate_pop_size = conf_mutate_pop_size * conf_pop_size;
  mutate_rbest_size = conf_mutate_rbest * conf_pop_size;
  if (dbg_evolution >= VERBOSITY_GENERAL)
  {
    printf("Mutation parameters:\n");
    printf(" %d individuals are created\n", mutate_pop_size);
    printf(" %d best individuals in old population are considered\n", mutate_rbest_size);
  }

  elite_pop_size = conf_elite_pop_size * conf_pop_size;
  if (dbg_evolution >= VERBOSITY_GENERAL)
  {
    printf("Elitism parameters:\n");
    printf(" %d best individuals are copied\n", elite_pop_size);
  }

  if (breed_pop_size + mutate_pop_size + elite_pop_size != conf_pop_size)
  {
    if (conf_fit_size)
    {
      elite_pop_size += conf_pop_size - (breed_pop_size + mutate_pop_size + elite_pop_size);
    }
    else
    {
      fprintf(stderr, "Breeding + mutation + elitism won't create correct number of individuals\n");
      fprintf(stderr, "Please fix conf_breed_pop_size, conf_mutate_pop_size and conf_elite_pop_size parameters\n");
      exit(2);
    }
  }
}

void labeller_label(void)
{
  make_graph();
  label_graph();
  bfs_wrapper();
  make_segments();

  GARY_INIT(population1, conf_pop_size);
  GARY_INIT(population2, conf_pop_size);
  make_population();
  rank_population();
  qsort(population1, conf_pop_size, sizeof(struct individual *), cmp_individual);

  if (dbg_evolution >= VERBOSITY_GENERAL)
  {
    printf("Penalties after initialization\n");
    dump_penalties(population1);
  }

  while (! shall_terminate())
  {
    iteration++;
    if (dbg_evolution)
      printf("\n*** Iteration %d ***\n", iteration);

    breed();
    mutate();
    elite();

    struct individual **swp = population1;
    population1 = population2;
    population2 = swp;
    pop2_ind = 0;
    clear_population(population2);

    rank_population();

    if (dbg_evolution >= VERBOSITY_GENERAL)
      printf("Sorting population\n");
    qsort(population1, conf_pop_size, sizeof(struct individual *), cmp_individual);

    if (dbg_evolution >= VERBOSITY_GENERAL)
    {
      printf("Penalties after sort\n");
      dump_penalties(population1);
    }

    old_best = population1[0]->penalty;
  }

  if (dbg_overlaps >= VERBOSITY_GENERAL)
    dump_bitmaps(population1[0]);

  plan_individual(population1[0]);

  labeller_cleanup();

  return;
}

void labeller_cleanup(void)
{
  hash_cleanup();
  GARY_FREE(requests_point);
  GARY_FREE(requests_line);
  GARY_FREE(requests_area);
}

void make_population(void)
{
  for (int i=0; i<conf_pop_size; i++)
  {
    num_placements = 0; // FIXME: This IS a terrible HACK
    struct individual *i2 = ep_alloc(ep_individuals);
    init_individual(i2);
    population2[i] = i2;

    if (dbg_init >= VERBOSITY_INDIVIDUAL)
      printf("Making individual %d\n", i);
    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++)
    {
      init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_point[j]);
    }

    for (uns j=0; j<GARY_SIZE(requests_line); j++)
    {
      init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j]);

      for (uns k=0; k<GARY_SIZE(requests_line[j].sections); k++)
      {
        init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k]);

        for (uns l=0; l<GARY_SIZE(requests_line[j].sections[k].segments); l++)
        {
          init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k].segments[l]);
        }
      }
    }

    for (uns j=0; j<GARY_SIZE(requests_area); j++)
    {
      init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_area[j]);
    }

    hide_segment_labels(individual);

    ASSERT(p == num_requests);
  }
}

bool shall_terminate(void)
{
  switch (conf_term_cond)
  {
    case TERM_COND_PENALTY:
      return (population1[0]->penalty < conf_penalty_bound);
    case TERM_COND_STAGNATION:
      return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
    case TERM_COND_ITERATIONS:
      return (iteration >= conf_iteration_limit);
    default:
      fprintf(stderr, "Warning: No termination condition is set, terminating\n");
      return 1;
  }
}

void breed(void)
{
  int i=0;

  struct individual **breed_buffer;
  while (i < breed_pop_size)
  {
    int parent1 = randint(0, breed_rbest_size);
    int parent2 = randint(0, breed_rbest_size);
    if (dbg_breeding >= VERBOSITY_INDIVIDUAL)
      printf("Will breed %d and %d\n", parent1, parent2);

    breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
    population2[pop2_ind++] = breed_buffer[0];
    population2[pop2_ind++] = breed_buffer[1];
    free(breed_buffer);
    i += 2;
  }

  return;
}

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); init_individual(child1);
  struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);

  bool *processed;
  GARY_INIT_ZERO(processed, GARY_SIZE(parent1->placements));

  for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
  {
    if (! processed[parent1->placements[i].ind])
    {
      if (dbg_breeding >= VERBOSITY_PLACEMENT)
        printf("Creating symbol closure for placement %u\n", i);

      struct placement **clos_symbols = get_closure(&(parent1->placements[i]));
      int x = randint(0, 2);

      if (x == 0)
      {
        if (dbg_breeding >= VERBOSITY_PLACEMENT)
          printf("Copying parent->child 1->1 and 2->2\n");
        copy_symbols(clos_symbols, parent1, child1, &processed);
        copy_symbols(clos_symbols, parent2, child2, &processed);
      }
      else
      {
        if (dbg_breeding >= VERBOSITY_PLACEMENT)
          printf("Copying parent->child 2->1 and 1->2\n");
        copy_symbols(clos_symbols, parent2, child1, &processed);
        copy_symbols(clos_symbols, parent1, child2, &processed);
      }

      GARY_FREE(clos_symbols);
    }
  }

  GARY_FREE(processed);

  if (conf_mutate_children)
  {
    if (randdouble() < conf_mutate_children_prob) perform_mutation(child1);
    else hide_segment_labels(child1);

    if (randdouble() < conf_mutate_children_prob) perform_mutation(child2);
    else hide_segment_labels(child2);
  }

  buffer[0] = child1;
  buffer[1] = child2;
  return buffer;
}

void mutate(void)
{
  for (int i=0; i < mutate_pop_size; i++)
  {
    if (dbg_mutation >= VERBOSITY_INDIVIDUAL)
      printf("Creating %d-th individual by mutation\n", i);
    int ind = randint(0, mutate_rbest_size);
    if (dbg_mutation >= VERBOSITY_INDIVIDUAL)
      printf("Mutating %d-th individual of original population\n", ind);
    population2[pop2_ind] = ep_alloc(ep_individuals);
    copy_individual(population1[ind], population2[pop2_ind]);
    if (dbg_mutation >= VERBOSITY_INDIVIDUAL)
      printf("Individual %d in pop2 inited from individual %d in pop1\n", pop2_ind, ind);
    perform_mutation(population2[pop2_ind]);
    pop2_ind++;
  }
}

void perform_mutation(struct individual *individual)
{
  for (uns i=0; i<GARY_SIZE(individual->placements); i++)
  {
    double x = randdouble();
    double acc = 0;

    if (x <= acc + conf_mutate_move_bound)
    {
      if (dbg_mutation >= VERBOSITY_PLACEMENT)
        printf("Mutation: Moving symbol in placement %u\n", i);
      move_symbol(&(individual->placements[i]));
      continue;
    }
    acc += conf_mutate_move_bound;

    if (x <= acc + conf_mutate_regen_bound)
    {
      gen_coords(&(individual->placements[i]));
      continue;
    }
    acc += conf_mutate_regen_bound;

    if (x <= acc + conf_mutate_chvar_bound)
    {
      struct placement *p = &(individual->placements[i]);
      switch (p->request->type)
      {
        case REQUEST_POINT:
        case REQUEST_AREA:
          // Does nothing when there are 0 variants... does it mind?
          p->variant_used = randint(-1, GARY_SIZE(p->request->variants));
          break;
        case REQUEST_SEGMENT:
          p->variant_used = randint(0, GARY_SIZE(p->request->variants));
          break;
        case REQUEST_SECTION:
          p->variant_used = randint(0, GARY_SIZE(((struct request_section *) p->request)->segments));
          break;
        default:
          ;
      }
    }
  }

  hide_segment_labels(individual);
}

void elite(void)
{
  for (int i=0; i<elite_pop_size; i++)
  {
    population2[pop2_ind] = ep_alloc(ep_individuals);
    copy_individual(population1[i], population2[pop2_ind++]);
  }
}

int overlaps(struct placement *p1, struct placement *p2)
{
  if (p1->request->type != REQUEST_POINT &&
      p1->request->type != REQUEST_SEGMENT &&
      p1->request->type != REQUEST_AREA)
    return 0;

  if (p2->request->type != REQUEST_POINT &&
      p2->request->type != REQUEST_SEGMENT &&
      p2->request->type != REQUEST_AREA)
    return 0;

  if (p1->variant_used == -1 || p2->variant_used == -1)
    return 0;

  struct variant *v1, *v2;

  v1 = &(p1->request->variants[p1->variant_used]);
  v2 = &(p2->request->variants[p2->variant_used]);

  // FIXME: This doesn't fully respect offset which it probably should
  int p1x = p1->x; int p1y = p1->y;
  int p2x = p2->x; int p2y = p2->y;

  int overlap = 0;
  for (int y=max2(0, max2(p1y, p2y)); y<min2(page_height_int, min2(p1y+v1->height, p2y+v2->height)); y++)
    for (int x=max2(0, max2(p1x, p2x)); x<min2(page_width_int, min2(p1x+v1->width, p2x+v2->width)); x++)
    {
      if (v1->bitmap[(y-p1y)*v1->width + (x-p1x)] &&
          v2->bitmap[(y-p2y)*v2->width + (x-p2x)])
        overlap++;
    }

  return overlap;
}

int get_overlap(struct placement *p)
{
  if (p->variant_used == -1) return 0;

  struct map_part **parts = get_map_parts(p);
  if (! parts)
  {
    if (dbg_overlaps >= VERBOSITY_PLACEMENT)
      printf("Placement of request %d seems not to be placed\n", p->request->ind);
    return 0;
  }

  struct placement **others;
  bool *planned;

  GARY_INIT_ZERO(planned, num_requests);
  planned[p->request->ind] = 1;
  GARY_INIT(others, 0);

  for (uns i=0; i<GARY_SIZE(parts); i++)
  {
    struct map_placement *mp = parts[i]->placement->next_in_map;
    while (mp)
    {
      if (! planned[mp->placement->request->ind])
      {
        struct placement **p = GARY_PUSH(others);
        *p = mp->placement;
        planned[mp->placement->request->ind] = true;
      }
      mp = mp->next_in_map;
    }
  }

  int overlap = 0;
  for (uns i=0; i<GARY_SIZE(others); i++)
  {
    overlap += overlaps(p, others[i]);
  }

  GARY_FREE(planned);
  GARY_FREE(parts);
  GARY_FREE(others);

  if (dbg_overlaps >= VERBOSITY_PLACEMENT)
    printf("Placement of request %d add %d to overlaps\n", p->request->ind, overlap);

  if (p->x < 0) overlap += 0 - p->x;
  if (p->x + p->request->variants[p->variant_used].width > page_width_int)
    overlap += p->x + p->request->variants[p->variant_used].width - page_width_int;

  if (p->y < 0) overlap += 0 - p->y;
  if (p->y + p->request->variants[p->variant_used].height > page_height_int)
    overlap += p->y + p->request->variants[p->variant_used].height - page_height_int;

  return overlap;
}

int individual_overlap(struct individual *individual)
{
  int overlap = 0;

  for (uns i=0; i<GARY_SIZE(individual->placements); i++)
  {
    overlap += get_overlap(&individual->placements[i]);
  }

  return overlap;
}

double get_distance(struct placement *p)
{
  if (p->variant_used < 0) return 0;
  struct variant *v = &p->request->variants[p->variant_used];

  double dx, dy, distance;
  switch (p->request->type)
  {
    case REQUEST_POINT: ;
      struct request_point *rp = (struct request_point *) p->request;
      dx = rp->x + v->offset_x - p->x;
      dy = rp->y + v->offset_y - p->y;
      distance = sqrt(dx*dx + dy*dy);
      if (dbg_rank >= VERBOSITY_PLACEMENT)
        printf("Point placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, rp->x, rp->y);
      break;
    case REQUEST_SEGMENT: ;
      struct request_segment *rs = (struct request_segment *) p->request;
      struct sym_text *st = (struct sym_text *) rs->label;

      double width = p->request->variants[p->variant_used].width;
      double rotated_x = p->x + width * sin(st->rotate / (-180 / M_PI));
      double rotated_y = p->y + width * cos(st->rotate / (-180 / M_PI));

      if (rs->x1 < rs->x2)
      {
        if (p->x < rs->x1)
        {
          dx = rs->x1 - p->x;
          dy = rs->y1 - p->y;
        }
        else if (rotated_x > rs->x2)
        {
          dx = rotated_x - rs->x2;
          dy = rotated_y - rs->y2;
        }
        else
        {
          dx = dy = 0;
        }
      }
      else
      {
        if (p->x < rs->x2)
        {
          dx = rs->x2 - p->x;
          dy = rs->y2 - p->y;
        }
        else if (rotated_x > rs->x1)
        {
          dx = rotated_x - rs->x1;
          dy = rotated_y - rs->y1;
        }
        else
        {
          dx = dy = 0;
        }
      }

      distance = sqrt(dx*dx + dy*dy);
      break;
    case REQUEST_AREA: ;
      struct request_area *ra = (struct request_area *) p->request;
      dx = ra->cx + v->offset_x - p->x;
      dy = ra->cy + v->offset_y - p->y;
      distance = sqrt(dx*dx + dy*dy);
      if (dbg_rank >= VERBOSITY_PLACEMENT)
        printf("Area placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
      break;
    default:
      return 0;
  }

  if (dbg_rank >= VERBOSITY_PLACEMENT)
    printf("Placement %d has distance %.2f\n", p->ind, distance);
  return distance;
}

double individual_distances(struct individual *individual)
{
  int distances = 0;

  for (uns i=0; i<GARY_SIZE(individual->placements); i++)
  {
    distances += get_distance(&individual->placements[i]);
  }

  return distances;
}

double get_omittment(struct placement *p)
{
  if (p->variant_used >= 0) return 0;

  // FIX ME :)
  switch (p->request->type)
  {
    case REQUEST_POINT:
    case REQUEST_AREA:
      return 10;
      break;
    default:
      return 0;
  }
}

double individual_omittment(struct individual *individual)
{
  int omittment = 0;

  for (uns i=0; i<GARY_SIZE(individual->placements); i++)
  {
    omittment += get_omittment(&individual->placements[i]);
  }

  return omittment;
}

int cmp_individual(const void *a, const void *b)
{
  struct individual **ia = (struct individual **) a;
  struct individual **ib = (struct individual **) b;

  return (*ia)->penalty - (*ib)->penalty;
}

void rank_population(void)
{
  int penalty;

  for (int i=0; i<conf_pop_size; i++)
  {
    if (dbg_rank >= VERBOSITY_INDIVIDUAL)
      printf("Individual %d\n", i);
    population1[i]->penalty = 0;

    penalty = individual_omittment(population1[i]);
    if (dbg_rank >= VERBOSITY_INDIVIDUAL)
      printf("Increasing penalty by %d for omittment\n", penalty);
    population1[i]->penalty += penalty;

    penalty = individual_overlap(population1[i]);
    if (dbg_rank >= VERBOSITY_INDIVIDUAL)
      printf("Increasing penalty by %d for overlap\n", penalty);
    population1[i]->penalty += penalty;

    penalty = individual_distances(population1[i]);
    if (dbg_rank >= VERBOSITY_INDIVIDUAL)
      printf("Increasing penalty by %d for distances\n", penalty);
    population1[i]->penalty += penalty;
  }
}

struct map_part **get_map_parts(struct placement *p)
{
  if (p->variant_used < 0) return NULL;

  struct map_part **buffer;
  GARY_INIT(buffer, 0);

  if (dbg_map_parts >= VERBOSITY_PLACEMENT)
    printf("Looking for map parts containing placement of request %d, placed at [%.2f; %.2f]\n", p->request->ind, p->x, p->y);

  struct variant v;
  switch (p->request->type)
  {
    case REQUEST_POINT:
    case REQUEST_SEGMENT:
    case REQUEST_AREA:
      v = p->request->variants[p->variant_used];
      break;
    default:
      if (dbg_map_parts >= VERBOSITY_ALL)
        printf("Skipping unsupported request type (%d)\n", p->request->type);
      return NULL;
  }

  if (dbg_map_parts >= VERBOSITY_PLACEMENT)
    printf("Bitmap is %d x %d\n", v.width, v.height);

  int x_min = max2(0, p->x) / conf_map_part_width;
  // CHECK ME: Is rounding needed?
  int x_max = min2(page_width_int, (p->x + v.width)) / conf_map_part_width;
  int y_min = max2(0, p->y) / conf_map_part_height;
  // CHECK ME: Is rounding needed?
  int y_max = min2(page_height_int, (p->y + v.height)) / conf_map_part_height;

  if (dbg_map_parts >= VERBOSITY_PLACEMENT)
    printf("Cells between [%d; %d] and [%d; %d] generated\n", x_min, y_min, x_max, y_max);

  for (int y=y_min; y<=y_max; y++)
    for (int x=x_min; x<=x_max; x++)
    {
      struct map_part **m = GARY_PUSH(buffer);
      if (dbg_map_parts >= VERBOSITY_ALL)
        printf("Asking for %d of %u\n", y * num_map_parts_row + x, GARY_SIZE(p->individual->map));
      *m = p->individual->map[y * num_map_parts_row + x];
    }

  if (dbg_map_parts >= VERBOSITY_PLACEMENT)
    printf("Returning %u map parts potentially containing the symbol\n", GARY_SIZE(buffer));

  return buffer;
}

void update_map_parts_delete(struct placement *p)
{
  struct map_placement *mp = p->map_links;
  while (mp)
  {
    mp->prev_in_map->next_in_map = mp->next_in_map;
    if (mp->next_in_map)
      mp->next_in_map->prev_in_map = mp->prev_in_map;

    struct map_placement *tmp = mp;
    mp = mp->next_in_placement;
    free(tmp);
  }
  p->map_links = NULL;
}

void update_map_parts_create(struct placement *p)
{
  struct map_part **parts = get_map_parts(p);
  if (parts == NULL) return;

  for (uns i=0; i<GARY_SIZE(parts); i++)
  {
    struct map_placement *mp = malloc(sizeof(struct map_placement));
    mp->placement = p;
    mp->part = parts[i];

    mp->next_in_map = parts[i]->placement->next_in_map;
    mp->prev_in_map = parts[i]->placement;
    parts[i]->placement->next_in_map = mp;
    if (mp->next_in_map) mp->next_in_map->prev_in_map = mp;

    mp->next_in_placement = p->map_links;
    mp->prev_in_placement = NULL;
    p->map_links = mp;
  }

  GARY_FREE(parts);
}

void update_map_parts(struct placement *p)
{
  update_map_parts_delete(p);
  update_map_parts_create(p);
}

void gen_coords(struct placement *p)
{
  switch(p->request->type)
  {
    case REQUEST_POINT:
      gen_coords_point(p);
      break;
    case REQUEST_AREA:
      gen_coords_area(p);
      break;
    case REQUEST_SEGMENT:
      gen_coords_segment(p);
      break;
    case REQUEST_LINE:
      if (dbg_movement)
        printf("Not yet implemented\n");
      break;
    default:
      if (dbg_movement >= VERBOSITY_ALL)
        printf("Testing request type\n");
      ASSERT(p->request->type != REQUEST_INVALID);
  }

  update_map_parts(p);
}

double gen_movement(void)
{
  double m = (random() % 100000) / 10000;
  m = pow(m, 1.0/3) * flip(1, -1);
  if (dbg_movement >= VERBOSITY_ALL)
    printf("Movement %.2f\n", m);
  return m;
}

double gen_movement_uniform(void)
{
  return (move_max - move_min) * randdouble() * flip(1, -1);
}

void gen_coords_point(struct placement *p)
{
  p->x = p->x + gen_movement();
}

void gen_coords_segment(struct placement *p)
{
  struct request_segment *rs = (struct request_segment *) p->request;
  p->x = (rs->x1 + rs->x2) / 2;
  p->y = (rs->y1 + rs->y2) / 2;
}

void gen_coords_area(struct placement *p)
{
  struct request_area *ra = (struct request_area *) p->request;

  p->x = p->x + gen_movement();
  p->y = p->y + gen_movement();

  if (dbg_movement >= VERBOSITY_PLACEMENT)
    printf("Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
}

int randint(int min, int max)
{
  if (min == max) return min;
  int r = random();
  return min + (r % (max - min));
}

struct placement **get_closure(struct placement *placement)
{
  struct placement **closure;
  GARY_INIT(closure, 0);
  bool *chosen = malloc(GARY_SIZE(placement->individual->placements) * sizeof(bool));
  for (uns i=0; i<GARY_SIZE(placement->individual->placements); i++) { chosen[i] = 0; }
  chosen[placement->request->ind] = 1;

  struct placement **p = GARY_PUSH(closure); *p = placement;

  uns first = 0;
  while (first < GARY_SIZE(closure))
  {
    if (dbg_breeding >= VERBOSITY_ALL)
      printf("Iterating, first is %d of current %u\n", first, GARY_SIZE(closure));
    struct placement **overlapping = get_overlapping(placement);
    if (! overlapping) { first++; continue; }

    struct placement **filtered = filter(overlapping, &chosen);
    if (dbg_breeding >= VERBOSITY_ALL)
      printf("There are %u new overlapping symbols\n", GARY_SIZE(filtered));
    GARY_FREE(overlapping);
    overlapping = filtered;
    for (uns j=0; j<GARY_SIZE(overlapping); j++)
    {
      if (! chosen[overlapping[j]->request->ind])
      {
        if (overlaps(*p, overlapping[j]))
        {
          p = GARY_PUSH(closure); *p = overlapping[j];
          if (dbg_breeding >= VERBOSITY_ALL)
            printf("Adding placement of request %d (in fact at [%.2f; %.2f] of size %d x %d)\n", overlapping[j]->request->ind, overlapping[j]->x, overlapping[j]->y, overlapping[j]->request->variants[overlapping[j]->variant_used].width, overlapping[j]->request->variants[overlapping[j]->variant_used].height);
          chosen[overlapping[j]->request->ind] = 1;
        }
      }
    }
    GARY_FREE(overlapping);
    first++;
  }

  free(chosen);

  return closure;
}

void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child, bool **processed_ptr)
{
  bool *processed = *processed_ptr;
  if (dbg_breeding >= VERBOSITY_ALL)
    printf("Will copy %u symbols\n", GARY_SIZE(closure));

  for (uns i=0; i<GARY_SIZE(closure); i++)
  {
    processed[closure[i]->ind] = 1;
    int ind = closure[i]->ind;
    child->placements[ind] = parent->placements[ind];
    child->placements[ind].individual = child;
    child->placements[ind].processed = 0;
    child->placements[ind].map_links = NULL;
    update_map_parts(&child->placements[ind]);
  }
}

void move_symbol(struct placement *p)
{
  switch (p->request->type)
  {
    case REQUEST_POINT:
    case REQUEST_AREA:
      move_symbol_point(p);
      break;
    case REQUEST_SEGMENT:
      move_symbol_segment(p);
      break;
    default:
      ASSERT(p->request->type != REQUEST_INVALID);
  }
}

void move_symbol_point(struct placement *p)
{
  p->x += gen_movement_uniform();
  p->y += gen_movement_uniform();
}

void move_symbol_segment(struct placement *p)
{
  double m = gen_movement_uniform();
  // CHECK ME
  p->x += m;
  p->y += m * ((struct request_segment *) p->request)->slope;
}

void hide_segment_labels(struct individual *individual)
{
  // BEWARE: This fully depends on current genetic encoding

  int used = -1, num = -1;
  for (uns i=0; i<GARY_SIZE(individual->placements); i++)
  {
    switch (individual->placements[i].request->type)
    {
      case REQUEST_SECTION:
        used = individual->placements[i].variant_used;
        num = 0;
        break;
      case REQUEST_SEGMENT:
        if (num == used)
          individual->placements[i].variant_used = 0;
        else
          individual->placements[i].variant_used = -1;
        num++;
        break;
      default:
        ;
    }
  }
}

void init_placement(struct placement *p, struct individual *individual, struct request *r)
{
  p->ind = num_placements++;
  p->request = r;
  p->processed = 0;
  p->x = p->y = 0; // To prevent valgrind from complaining
  p->variant_used = 0;
  p->map_links = NULL;
  p->individual = individual;
  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_LINE: ;
      break;
    case REQUEST_SECTION: ;
      struct request_section *rls = (struct request_section *) r;
      p->variant_used = randint(0, rls->num_segments);
      break;
    case REQUEST_SEGMENT: ;
      struct request_segment *rs = (struct request_segment *) r;
      p->x = rs->x2;
      p->y = rs->y2;
      break;
    case REQUEST_AREA: ;
      struct request_area *ra = (struct request_area *) r;
      p->x = ra->cx;
      p->y = ra->cy;
      p->variant_used = 0;
      break;
    default:
      ASSERT(p->request->type != REQUEST_INVALID);
  }

  gen_coords(p);
  if (dbg_init >= VERBOSITY_PLACEMENT)
    printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y);
}

void reset_individual_map(struct individual *i)
{
  for (uns j=0; j<num_map_parts; j++)
  {
    struct map_placement *mp = i->map[j]->placement;
    while (mp)
    {
      struct map_placement *tmp = mp;
      mp = mp->next_in_map;
      free(tmp);
    }

    free(i->map[j]);
    struct map_part *part = malloc(sizeof(struct map_part));
    part->ind = j;

    mp = malloc(sizeof(struct map_placement));
    part->placement = mp;
    mp->placement = &dummy_placement;
    mp->next_in_map = mp->prev_in_map = NULL;
    mp->next_in_placement = mp->prev_in_placement = NULL;
    i->map[j] = part;
  }
}

void update_individual(struct individual *individual)
{
  for (uns i=0; i<GARY_SIZE(individual->placements); i++)
  {
    update_map_parts_delete(&individual->placements[i]);
  }
}

void clear_individual(struct individual *individual)
{
  for (uns j=0; j<num_map_parts; j++)
  {
    struct map_placement *mp = individual->map[j]->placement;
    while (mp)
    {
      struct map_placement *tmp = mp;
      mp = mp->next_in_map;
      free(tmp);
    }

    free(individual->map[j]);
  }

  GARY_FREE(individual->map);
  GARY_FREE(individual->placements);
  ep_free(ep_individuals, individual);
}

void clear_population(struct individual **pop)
{
  for (uns i=0; i<GARY_SIZE(pop); i++)
  {
    clear_individual(pop[i]);
  }
}

struct placement **get_overlapping(struct placement *p)
{
  struct placement **buffer;
  GARY_INIT(buffer, 0);

  struct map_part **parts = get_map_parts(p);
  if (! parts) return NULL;

  for (uns i=0; i<GARY_SIZE(parts); i++)
  {
    struct map_placement *mp = parts[i]->placement->next_in_map;
    while (mp)
    {
      if (p->variant_used >= 0)
      {
        struct placement **p = GARY_PUSH(buffer);
        *p = mp->placement;
      }
      mp = mp->next_in_map;
    }
  }
  GARY_FREE(parts);

  if (dbg_map_parts >= VERBOSITY_PLACEMENT)
    printf("Returning %u potentially overlapping placements\n", GARY_SIZE(buffer));

  return buffer;
}

struct placement **filter(struct placement **list, bool **pred_ptr)
{
  bool *pred = *pred_ptr; // As GARY can't be passed directly
  struct placement **filtered;
  GARY_INIT(filtered, 0);

  for (uns i=0; i<GARY_SIZE(list); i++)
  {
    if (pred[list[i]->request->ind])
      continue;

    struct placement **p = GARY_PUSH(filtered);
    *p = list[i];
  }

  return filtered;
}

int flip(int a, int b)
{
  return (random() % 2 ? a : b);
}

double randdouble(void)
{
  return ((double) rand() / (double) RAND_MAX);
}

void init_individual(struct individual *individual)
{
  GARY_INIT(individual->placements, num_requests);
  GARY_INIT(individual->map, 0);
  for (uns j=0; j<num_map_parts; j++)
  {
    GARY_PUSH(individual->map);
    struct map_part *part = malloc(sizeof(struct map_part));
    struct map_placement *mp = malloc(sizeof(struct map_placement));
    part->placement = mp;
    part->ind = j;
    mp->placement = &dummy_placement;
    mp->next_in_map = mp->prev_in_map = NULL;
    mp->next_in_placement = mp->prev_in_placement = NULL;
    individual->map[j] = part;
  }
  individual->penalty = 0;
}

void copy_individual(struct individual *src, struct individual *dest)
{
  init_individual(dest);
  dest->penalty = src->penalty;

  for (uns i=0; i<GARY_SIZE(src->placements); i++)
  {
    dest->placements[i] = src->placements[i];
    dest->placements[i].map_links = NULL;
    dest->placements[i].individual = dest;

    update_map_parts_create(&dest->placements[i]);
  }
}