From ce0c74158bbd91c1ca6443816f51b603d557e376 Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Mon, 13 Jan 2025 16:55:25 -0800
Subject: MergeSort to its own file

Allow self-recursive forward refs.
Missing progress.
---
 .../java/com/seaofnodes/simple/BrainFuckTest.java  |  4 +-
 .../java/com/seaofnodes/simple/MergeSortTest.java  | 65 ++++++++++++++++++++++
 2 files changed, 66 insertions(+), 3 deletions(-)
 create mode 100644 chapter18/src/test/java/com/seaofnodes/simple/MergeSortTest.java

(limited to 'chapter18/src/test/java/com')

diff --git a/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
index 2995e89c..37ecde1c 100644
--- a/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
+++ b/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
@@ -1,10 +1,8 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.evaluator.Evaluator;
-import org.junit.Test;
-
 import java.nio.charset.StandardCharsets;
-
+import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
diff --git a/chapter18/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/chapter18/src/test/java/com/seaofnodes/simple/MergeSortTest.java
new file mode 100644
index 00000000..d48449d5
--- /dev/null
+++ b/chapter18/src/test/java/com/seaofnodes/simple/MergeSortTest.java
@@ -0,0 +1,65 @@
+package com.seaofnodes.simple;
+
+import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+public class MergeSortTest {
+
+    @Test
+    public void testMergeSort() {
+        CodeGen code = new CodeGen(
+"""
+// based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort
+
+val merge_sort = { int[] a, int[] b, int n ->
+    copy_array(a, 0, n, b);
+    split_merge(a, 0, n, b);
+};
+
+val split_merge = { int[] b, int begin, int end, int[] a ->
+    if (end - begin <= 1)
+        return 0;
+    int middle = (end + begin) / 2;
+    split_merge(a, begin, middle, b);
+    split_merge(a, middle, end, b);
+    merge(b, begin, middle, end, a);
+    return 0;
+};
+
+val merge = { int[] b, int begin, int middle, int end, int[] a ->
+    int i = begin, j = middle;
+
+    for (int k = begin; k < end; k++) {
+        // && and ||
+        bool cond = false;
+        if (i < middle) {
+            if (j >= end)          cond = true;
+            else if (a[i] <= a[j]) cond = true;
+        }
+        if (cond) b[k] = a[i++];
+        else      b[k] = a[j++];
+    }
+};
+
+val copy_array = { int[] a, int begin, int end, int[] b ->
+    for (int k = begin; k < end; k++)
+        b[k] = a[k];
+};
+
+int[] !a = new int[arg];
+int[] !b = new int[a#];
+
+for (int i = 0; i < a#; i++)
+    a[i] = a# - i;
+
+merge_sort(a, b, a#);
+
+return a;
+""");
+        code.parse().opto();
+        assertEquals("Stop[ return [int]; return 0; ]", code._stop.toString());
+        assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11));
+    }
+
+}
-- 
cgit v1.2.3