X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=labeller.c;h=1db25fca59721a57be2199c4e79154de98772460;hb=3232a51a5fed20b6d3f0d6b9df0b8c66fdc75ca4;hp=0089fc4c0bc934a6e8b52babadd186f2c1293647;hpb=570ed05bd065baa7020d445b6c71c2faba72a863;p=leo.git

diff --git a/labeller.c b/labeller.c
index 0089fc4..1db25fc 100644
--- a/labeller.c
+++ b/labeller.c
@@ -49,6 +49,8 @@ int dbg_bfs = 0;
 int dbg_map_parts = 0;
 int dbg_movement = 0;
 int dbg_init = 0;
+int dbg_overlaps = 0;
+int dbg_rank = 0;
 
 int page_width_int;
 int page_height_int;
@@ -108,6 +110,10 @@ void join_edge(struct graph_edge *e, int dir);
 void bfs(uns longline);
 void make_segments(void);
 
+int overlaps(struct placement *p1, struct placement *p2);
+int get_overlap(struct placement *p);
+int individual_overlap(struct individual *individual);
+
 void make_population(void);
 bool shall_terminate(void);
 void breed(void);
@@ -116,6 +122,8 @@ void elite(void);
 void rank_population(void);
 void plan_individual(struct individual *individual);
 
+int cmp_individual(const void *a, const void *b);
+
 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);
@@ -1066,6 +1074,10 @@ void make_population(void)
 {
   for (int i=0; i<conf_pop_size; i++)
   {
+    struct individual *i2 = ep_alloc(ep_individuals);
+    init_individual(i2);
+    population2[i] = i2;
+
     if (dbg_init)
       printf("Making individual %d\n", i);
     struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
@@ -1250,9 +1262,121 @@ void elite(void)
   }
 }
 
+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]);
+
+  int p1x = p1->x; int p1y = p1->y;
+  int p2x = p2->x; int p2y = p2->y;
+
+  int overlap = 0;
+  for (int y=max2(p1y, p2y); y<=min2(p1y+v1->height, p2y+v2->height); y++)
+    for (int x=max2(p1x, p2x); x<=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)
+{
+  struct map_part **parts = get_map_parts(p);
+  if (! parts)
+  {
+    if (dbg_overlaps)
+      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;
+    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;
+    }
+  }
+
+  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);
+
+  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;
+}
+
+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)
 {
-  // FIXME
+  int penalty;
+
+  for (int i=0; i<conf_pop_size; i++)
+  {
+    if (dbg_rank)
+      printf("Individual %d\n", i);
+    population1[i]->penalty = 0;
+
+    penalty = individual_overlap(population1[i]);
+    if (dbg_rank)
+      printf("Increasing penalty by %d for overlap\n", penalty);
+    population1[i]->penalty += penalty;
+  }
 }
 
 struct map_part **get_map_parts(struct placement *p)
@@ -1590,8 +1714,7 @@ int flip(int a, int b)
 
 double randdouble(void)
 {
-  // FIXME: How the hell shall double in range <0, 1> be generated? O:)
-  return 0.5;
+  return ((double) rand() / (double) RAND_MAX);
 }
 
 void cleanup(void)
@@ -1604,10 +1727,19 @@ void cleanup(void)
 
 void copy_individual(struct individual *src, struct individual *dest)
 {
-  src->penalty = dest->penalty;
+  dest->penalty = src->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];
+    dest->placements[i].map_links = NULL;
+  }
+  for (uns j=0; j<num_map_parts; j++)
+  {
+    struct map_part *part = GARY_PUSH(dest->map);
+    GARY_INIT(part->placement, 0);
+    struct map_placement *mp = GARY_PUSH(part->placement);
+    mp->placement = &dummy_placement;
+    mp->next = mp->prev = NULL;
   }
 }