From c5721759bbc6677be3f401d0f54dd53c9063d305 Mon Sep 17 00:00:00 2001
From: Brian Anderson <andersrb@gmail.com>
Date: Sun, 13 Mar 2011 21:22:27 -0400
Subject: Add fannkuchredux shootout benchmark

---
 src/Makefile                             |  1 +
 src/test/bench/shootout/fannkuchredux.rs | 99 ++++++++++++++++++++++++++++++++
 2 files changed, 100 insertions(+)
 create mode 100644 src/test/bench/shootout/fannkuchredux.rs

(limited to 'src')

diff --git a/src/Makefile b/src/Makefile
index edf9ceb2..74359c00 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -575,6 +575,7 @@ TEST_XFAILS_RUSTC := $(addprefix test/run-pass/, \
                         wrong-ret-type.rs \
                         ), \
                       $(wildcard test/*fail/*.rs test/*fail/*.rc)) \
+                     test/bench/shootout/fannkuchredux.rs \
                      test/bench/shootout/fasta.rs \
                      test/bench/shootout/binarytrees.rs \
                      $(wildcard test/bench/99-bottles/*rs)
diff --git a/src/test/bench/shootout/fannkuchredux.rs b/src/test/bench/shootout/fannkuchredux.rs
new file mode 100644
index 00000000..2d44067b
--- /dev/null
+++ b/src/test/bench/shootout/fannkuchredux.rs
@@ -0,0 +1,99 @@
+// Based on Isaac Gouy's fannkuchredux.csharp
+
+use std;
+
+import std._int;
+import std._vec;
+
+impure fn fannkuch(int n) -> int {
+
+  fn perm1init(uint i) -> mutable int {
+    ret i as int;
+  }
+  auto perm1init_ = perm1init; // Rustboot workaround
+
+  auto perm = _vec.init_elt[mutable int](0, n as uint);
+  auto perm1 = _vec.init_fn[mutable int](perm1init_, n as uint);
+  auto count = _vec.init_elt[mutable int](0, n as uint);
+
+  auto f = 0;
+  auto i = 0;
+  auto k = 0;
+  auto r = 0;
+  auto flips = 0;
+  auto nperm = 0;
+  auto checksum = 0;
+
+  r = n;
+  while (r > 0) {
+    i = 0;
+
+    while (r != 1) {
+      count.(r - 1) = r;
+      r -=1;
+    }
+
+    while (i < n) {
+      perm.(i) = perm1.(i);
+      i += 1;
+    }
+
+    // Count flips and update max and checksum
+    f = 0;
+    k = perm.(0);
+    while (k != 0) {
+      i = 0;
+      while (2 * i < k) {
+        auto t = perm.(i);
+        perm.(i) = perm.(k - i);
+        perm.(k - i) = t;
+        i += 1;
+      }
+      k = perm.(0);
+      f += 1;
+    }
+
+    if (f > flips) {
+      flips = f;
+    }
+
+    if ((nperm & 0x1) == 0) {
+      checksum += f;
+    } else {
+      checksum -= f;
+    }
+
+    // Use incremental change to generate another permutation
+    auto go = true;
+    while (go) {
+      if (r == n) {
+        log checksum;
+        ret flips;
+      }
+      auto p0 = perm1.(0);
+      i = 0;
+      while (i < r) {
+        auto j = i + 1;
+        perm1.(i) = perm1.(j);
+        i = j;
+      }
+      perm1.(r) = p0;
+
+      count.(r) -= 1;
+      if (count.(r) > 0) {
+        go = false;
+      } else {
+        r += 1;
+      }
+    }
+
+    nperm += 1;
+  }
+
+  ret flips;
+}
+
+impure fn main(vec[str] args) {
+  auto n = 7;
+  log #fmt("Pfannkuchen(%d) = %d", n, fannkuch(n));
+}
\ No newline at end of file
-- 
cgit v1.2.3