test/fannkuch.cpp

/*
 * The Computer Language Benchmarks Game
 * http://shootout.alioth.debian.org/
 *
 * Contributed by Eckehard Berns
 * Based on code by Heiner Marxen
 * and the ATS version by Hongwei Xi
 *
 * Modified for emscripten by azakai
 */

#include <stdio.h>
#include <stdlib.h>

struct worker_args {
  int i, n;
  struct worker_args* next;
};

int fannkuch_worker(void* _arg) {
  struct worker_args* args = (worker_args*)_arg;
  int *perm1, *count, *perm;
  int maxflips, flips, i, n, r, j, k, tmp;

  maxflips = 0;
  n = args->n;
  perm1 = (int*)malloc(n * sizeof(int));
  perm = (int*)malloc(n * sizeof(int));
  count = (int*)malloc(n * sizeof(int));
  for (i = 0; i < n; i++)
    perm1[i] = i;
  perm1[args->i] = n - 1;
  perm1[n - 1] = args->i;
  r = n;

  for (;;) {
    for (; r > 1; r--)
      count[r - 1] = r;
    if (perm1[0] != 0 && perm1[n - 1] != n - 1) {
      for (i = 0; i < n; i++)
        perm[i] = perm1[i];
      flips = 0;
      k = perm[0];
      do {
        for (i = 1, j = k - 1; i < j; i++, j--) {
          tmp = perm[i];
          perm[i] = perm[j];
          perm[j] = tmp;
        }
        flips++;
        tmp = perm[k];
        perm[k] = k;
        k = tmp;
      } while (k);
      if (maxflips < flips)
        maxflips = flips;
    }
    for (;;) {
      if (r >= n - 1) {
        free(perm1);
        free(perm);
        free(count);
        return maxflips;
      }

      {
        int p0 = perm1[0];
        for (i = 0; i < r; i++)
          perm1[i] = perm1[i + 1];
        perm1[i] = p0;
      }
      if (--count[r] > 0)
        break;
      r++;
    }
  }
}

static int fannkuch(int n) {
  struct worker_args *args, *targs;
  int showmax = 30;
  int *perm1, *count, i, r, maxflips, flips;

  args = NULL;
  for (i = 0; i < n - 1; i++) {
    targs = (worker_args*)malloc(sizeof(struct worker_args));
    targs->i = i;
    targs->n = n;
    targs->next = args;
    args = targs;
  }

  perm1 = (int*)malloc(n * sizeof(int));
  count = (int*)malloc(n * sizeof(int));

  for (i = 0; i < n; i++)
    perm1[i] = i;

  r = n;
  for (;;) {
    if (showmax) {
      for (i = 0; i < n; i++)
        printf("%d", perm1[i] + 1);
      printf("\n");
      showmax--;
    } else
      goto cleanup;

    for (; r > 1; r--)
      count[r - 1] = r;

    for (;;) {
      if (r == n)
        goto cleanup;
      {
        int p0 = perm1[0];
        for (i = 0; i < r; i++)
          perm1[i] = perm1[i + 1];
        perm1[i] = p0;
      }
      if (--count[r] > 0)
        break;

      r++;
    }
  }

cleanup:
  free(perm1);
  free(count);
  maxflips = 0;
  while (args != NULL) {
    flips = (int)fannkuch_worker(args);
    if (maxflips < flips)
      maxflips = flips;
    targs = args;
    args = args->next;
    free(targs);
  }
  return maxflips;
}

int main(int argc, char** argv) {
  int n = argc > 1 ? atoi(argv[1]) : 0;

  if (n < 1) {
    printf("Wrong argument.\n");
    return 1;
  }
  printf("Pfannkuchen(%d) = %d.\n", n, fannkuch(n));
  return 0;
}