sn-markov: Implement counting of comparators.

diff --git a/src/Makefile.am b/src/Makefile.am
index 6d579fd..09a9959 100644 (file)
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -49,7 +49,8 @@ sn_cut_LDADD = libsortnetwork.la
 sn_info_SOURCES = sn-info.c
 sn_info_LDADD = libsortnetwork.la
 
-sn_markov_SOURCES = sn-markov.c
+sn_markov_SOURCES = sn-markov.c \
+                   histogram.c histogram.h
 sn_markov_LDADD = libsortnetwork.la
 
 sn_merge_SOURCES = sn-merge.c

diff --git a/src/histogram.c b/src/histogram.c
new file mode 100644 (file)
index 0000000..db6a4d9
--- /dev/null
+++ b/src/histogram.c
@@ -0,0 +1,168 @@
+/**
+ * libsortnetwork - src/histrogram.c
+ * Copyright (C) 2011  Florian octo Forster
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; only version 2 of the License is applicable.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
+ *
+ * Authors:
+ *   Florian octo Forster <ff at octo.it>
+ **/
+
+#ifndef _ISOC99_SOURCE
+# define _ISOC99_SOURCE
+#endif
+#ifndef _POSIX_C_SOURCE
+# define _POSIX_C_SOURCE 200809L
+#endif
+#ifndef _XOPEN_SOURCE
+# define _XOPEN_SOURCE 700
+#endif
+
+#include <stdlib.h>
+#include <stdint.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+#include <errno.h>
+
+#include "histogram.h"
+
+#define BAR_WIDTH 64
+
+struct histogram_s
+{
+  uint64_t *data;
+  int index_min;
+  int index_max;
+};
+
+static int hist_resize (histogram_t *h, int rating) /* {{{ */
+{
+  int min_new;
+  int max_new;
+  size_t nelem_new;
+  size_t nelem_old;
+  uint64_t *tmp;
+
+  if ((h->index_min == 0) && (h->index_max == 0))
+  {
+    min_new = rating;
+    max_new = rating;
+  }
+  else
+  {
+    min_new = ((h->index_min < rating) ? h->index_min : rating);
+    max_new = ((h->index_max > rating) ? h->index_max : rating);
+  }
+
+  nelem_new = (size_t) ((max_new - min_new) + 1);
+  nelem_old = (size_t) ((h->index_max - h->index_min) + 1);
+
+  assert (nelem_new >= nelem_old);
+
+  tmp = realloc (h->data, nelem_new * sizeof (*h->data));
+  if (tmp == NULL)
+    return (ENOMEM);
+  h->data = tmp;
+
+  if ((h->index_min == 0) && (h->index_max == 0))
+  {
+    h->index_min = min_new;
+    h->index_max = max_new;
+    h->data[0] = 0;
+    return (0);
+  }
+
+  if (min_new < h->index_min)
+  {
+    size_t diff = (size_t) (h->index_min - min_new);
+
+    memmove (h->data + diff, h->data, nelem_old * sizeof (*h->data));
+    memset (h->data, 0, diff * sizeof (*h->data));
+
+    h->index_min = min_new;
+  }
+  else if (max_new > h->index_max)
+  {
+    size_t diff = (size_t) (max_new - h->index_max);
+    memset (h->data + nelem_old, 0, diff * sizeof (*h->data));
+
+    h->index_max = max_new;
+  }
+
+  return (0);
+} /* }}} int hist_resize */
+
+histogram_t *hist_create (void) /* {{{ */
+{
+  histogram_t *h = malloc (sizeof (*h));
+  if (h == NULL)
+    return (NULL);
+  memset (h, 0, sizeof (*h));
+  h->data = NULL;
+
+  return (h);
+} /* }}} hist_create */
+
+void hist_destroy (histogram_t *h) /* {{{ */
+{
+  if (h != NULL)
+    free (h->data);
+  free (h);
+} /* }}} hist_destroy */
+
+int hist_account (histogram_t *h, int rating) /* {{{ */
+{
+  if ((h == NULL) || (rating < 0))
+    return (EINVAL);
+
+  if ((rating < h->index_min) || (rating > h->index_max))
+    hist_resize (h, rating);
+
+  h->data[rating - h->index_min]++;
+
+  return (0);
+} /* }}} int hist_account */
+
+int hist_print (histogram_t *h) /* {{{ */
+{
+  char bar[BAR_WIDTH + 1];
+  uint64_t max;
+  int i;
+
+  if (h == NULL)
+    return (EINVAL);
+
+  max = 1;
+  for (i = h->index_min; i <= h->index_max; i++)
+    if (max < h->data[i - h->index_min])
+      max = h->data[i - h->index_min];
+
+  for (i = h->index_min; i <= h->index_max; i++)
+  {
+    uint64_t num = h->data[i - h->index_min];
+    uint64_t points = (BAR_WIDTH * num) / max;
+    uint64_t j;
+
+    for (j = 0; j < (BAR_WIDTH + 1); j++)
+      bar[j] = (j < points) ? '#' : 0;
+
+    printf ("%4i: %8"PRIu64" %s\n", i, num, bar);
+  }
+
+  return (0);
+} /* }}} int hist_print */
+
+/* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */

diff --git a/src/histogram.h b/src/histogram.h
new file mode 100644 (file)
index 0000000..c52b35c
--- /dev/null
+++ b/src/histogram.h
@@ -0,0 +1,34 @@
+/**
+ * libsortnetwork - src/histrogram.h
+ * Copyright (C) 2011  Florian octo Forster
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; only version 2 of the License is applicable.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
+ *
+ * Authors:
+ *   Florian octo Forster <ff at octo.it>
+ **/
+
+#ifndef HISTOGRAM_H
+#define HISTOGRAM_H 1
+
+struct histogram_s;
+typedef struct histogram_s histogram_t;
+
+histogram_t *hist_create (void);
+void hist_destroy (histogram_t *h);
+
+int hist_account (histogram_t *h, int rating);
+int hist_print (histogram_t *h);
+
+#endif /* HISTOGRAM_H */

diff --git a/src/sn-markov.c b/src/sn-markov.c
index 1fcc41d..5de4284 100644 (file)
--- a/src/sn-markov.c
+++ b/src/sn-markov.c
@@ -43,6 +43,7 @@
 
 #include "sn_network.h"
 #include "sn_random.h"
+#include "histogram.h"
 
 #if !defined(__GNUC__) || !__GNUC__
 # define __attribute__(x) /**/
@@ -59,6 +60,8 @@ static int best_rating = INT_MAX;
 static _Bool do_loop = 1;
 static uint64_t max_iterations = 0;
 
+static histogram_t *histogram;
+
 static void sigint_handler (int signal __attribute__((unused)))
 {
   do_loop = 0;
@@ -204,6 +207,8 @@ static void random_walk (sn_network_t *n)
       best_solution = sn_network_clone (next);
     }
 
+    hist_account (histogram, sn_network_get_comparator_num (next));
+
     sn_network_destroy (n);
     n = next;
     iteration_counter++;
@@ -224,6 +229,8 @@ int main (int argc, char **argv)
   struct sigaction sigint_action;
   struct sigaction sigterm_action;
 
+  histogram = hist_create ();
+
   read_options (argc, argv);
   if (initial_input_file == NULL)
     exit_usage (argv[0], EXIT_FAILURE);
@@ -254,6 +261,10 @@ int main (int argc, char **argv)
   random_walk (start_network);
   start_network = NULL;
 
+  hist_print (histogram);
+  hist_destroy (histogram);
+  histogram = NULL;
+
   if (best_solution != NULL)
   {
     if (best_output_file != NULL)