1 files changed, 122 insertions, 0 deletions
diff --git a/predicate-search/src/test/java/com/yahoo/search/predicate/utils/PrimitiveArraySorterTest.java b/predicate-search/src/test/java/com/yahoo/search/predicate/utils/PrimitiveArraySorterTest.java
new file mode 100644
index 00000000000..950268d5ecf
--- /dev/null
+++ b/predicate-search/src/test/java/com/yahoo/search/predicate/utils/PrimitiveArraySorterTest.java
@@ -0,0 +1,122 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.search.predicate.utils;
+
+import org.junit.Test;
+
+import java.util.Arrays;
+import java.util.Random;
+
+import static org.junit.Assert.assertArrayEquals;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+public class PrimitiveArraySorterTest {
+
+    @Test
+    public void sorting_empty_array_should_not_throw_exception() {
+        short[] array = {};
+        PrimitiveArraySorter.sort(array, Short::compare);
+    }
+
+    @Test
+    public void test_sorting_single_item_array() {
+        short[] array = {42};
+        PrimitiveArraySorter.sort(array, Short::compare);
+        assertEquals(42, array[0]);
+    }
+
+    @Test
+    public void test_sorting_custom_comparator() {
+        short[] array = {4, 2, 5};
+        PrimitiveArraySorter.sort(array, (a, b) -> Short.compare(b, a)); // Sort using inverse ordering.
+        short[] expected = {5, 4, 2};
+        assertArrayEquals(expected, array);
+    }
+
+    @Test
+    public void test_complicated_array() {
+        short[] array = {20381, -28785, -19398, 17307, -12612, 11459, -30164, -16597, -4267, 30838, 8918, 9014, -26444,
+                -1232, -14620, 12636, -12389, -4931, 32108, 19854, -12681, 14933, 319, 27348, -4907, 19196, 14209,
+                -32694, 2579, 9771, -1157, -13717, 28506, -8016, 21423, 23697, 23755, 29650, 25644, -14660, -18952,
+                25272, -19933, -11375, -32363, -11766, -29509, -23898, 12398, -2600, -20703, -23812, -8292, -1605,
+                28642, 12748, 2547, -14535, 4476, -7802};
+        short[] expected = Arrays.copyOf(array, array.length);
+        Arrays.sort(expected);
+        PrimitiveArraySorter.sort(array, Short::compare);
+        assertArrayEquals(expected, array);
+    }
+
+    @Test
+    public void sorting_random_arrays_should_produce_identical_result_as_java_sort() {
+        Random r = new Random(4234);
+        for (int i = 0; i < 10000; i++) {
+            short[] original = makeRandomArray(r);
+            short[] javaSorted = Arrays.copyOf(original, original.length);
+            short[] customSorted = Arrays.copyOf(original, original.length);
+            PrimitiveArraySorter.sort(customSorted, Short::compare);
+            Arrays.sort(javaSorted);
+            String errorMsg = String.format("%s != %s (before sorting: %s)", Arrays.toString(customSorted), Arrays.toString(javaSorted), Arrays.toString(original));
+            assertArrayEquals(errorMsg, customSorted, javaSorted);
+        }
+    }
+
+    @Test
+    public void test_merging_simple_array() {
+        short[] array = {-20, -12, 2, -22, -11, 33, 44};
+        short[] expected = {-22, -20, -12, -11, 2, 33, 44};
+        short[] result = new short[array.length];
+        PrimitiveArraySorter.merge(array, result, 3, Short::compare);
+        assertArrayEquals(expected, result);
+    }
+
+    @Test
+    public void test_merging_of_random_generated_arrays() {
+        Random r = new Random(4234);
+        for (int i = 0; i < 10000; i++) {
+            short[] array = makeRandomArray(r);
+            int length = array.length;
+            short[] mergeArray = new short[length];
+            short[] expected = Arrays.copyOf(array, length);
+            Arrays.sort(expected);
+
+            int pivot = length > 0 ? r.nextInt(length) : 0;
+            Arrays.sort(array, 0, pivot);
+            Arrays.sort(array, pivot, length);
+            PrimitiveArraySorter.merge(array, mergeArray, pivot, Short::compare);
+            assertArrayEquals(expected, mergeArray);
+        }
+    }
+
+    @Test
+    public void test_sortandmerge_returns_false_when_sort_is_in_place() {
+        short[] array = {3, 2, 1, 0, 4, 5, 6};
+        short[] mergeArray = new short[array.length];
+        assertFalse(PrimitiveArraySorter.sortAndMerge(array, mergeArray, 4, 7, Short::compare));
+        assertIsSorted(array);
+
+        array = new short[]{3, 2, 1, 0, 4, 5, 6};
+        assertTrue(PrimitiveArraySorter.sortAndMerge(array, mergeArray, 3, 7, Short::compare));
+        assertIsSorted(mergeArray);
+    }
+
+    // Create random array with size [0, 99] filled with random values.
+    private short[] makeRandomArray(Random r) {
+        short[] array = new short[r.nextInt(100)];
+        for (int j = 0; j < array.length; j++) {
+            array[j] = (short) r.nextInt();
+        }
+        return array;
+    }
+
+    private static void assertIsSorted(short[] array) {
+        if (array.length == 0) return;
+        int prev = array[0];
+        for (int i = 1; i < array.length; i++) {
+            int next = array[i];
+            assertTrue(prev <= next);
+            prev = next;
+        }
+    }
+
+}