You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by jp...@apache.org on 2013/05/04 15:55:18 UTC
svn commit: r1479109 [2/2] - in /commons/sandbox/sorting/trunk: ./ src/
src/main/ src/main/java/ src/main/java/org/ src/main/java/org/apache/
src/main/java/org/apache/commons/ src/main/java/org/apache/commons/sorting/
src/test/ src/test/java/ src/test/...
Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/Benchmark.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/Benchmark.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/Benchmark.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/Benchmark.java Sat May 4 13:55:17 2013
@@ -0,0 +1,162 @@
+package org.apache.commons.sorting;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.Random;
+
+public class Benchmark {
+
+ static final Random R = new Random();
+ static Integer[] CACHE = new Integer[1 << 24];
+ static {
+ for (int i = 0; i < CACHE.length; ++i) {
+ CACHE[i] = i;
+ }
+ }
+
+ private static enum Order {
+ RANDOM {
+ @Override
+ void prepare(Integer[] arr) {
+ for (int i = 0; i < arr.length; ++i) {
+ arr[i] = CACHE[R.nextInt(CACHE.length)];
+ }
+ }
+ },
+ RANDOM_LOW_CARDINALITY {
+ @Override
+ void prepare(Integer[] arr) {
+ for (int i = 0; i < arr.length; ++i) {
+ arr[i] = CACHE[R.nextInt(100)];
+ }
+ }
+ },
+ ASCENDING {
+ @Override
+ void prepare(Integer[] arr) {
+ RANDOM.prepare(arr);
+ Arrays.sort(arr);
+ }
+ },
+ ASCENDING_SEQUENCES {
+ @Override
+ void prepare(Integer[] arr) {
+ arr[0] = CACHE[R.nextInt(100)];
+ for (int i = 1; i < arr.length; ++i) {
+ if (R.nextInt(200) == 0) {
+ arr[i] = CACHE[R.nextInt(100)];
+ } else {
+ final int slot = arr[i-1] + R.nextInt(100);
+ arr[i] = CACHE[slot & (CACHE.length - 1)];
+ }
+ }
+ }
+ },
+ MOSTLY_ASCENDING {
+ @Override
+ void prepare(Integer[] arr) {
+ arr[0] = CACHE[R.nextInt(CACHE.length)];
+ for (int i = 1; i < arr.length; ++i) {
+ final int slot = arr[i-1] - 4 + R.nextInt(10);
+ arr[i] = CACHE[slot & (CACHE.length - 1)];
+ }
+ }
+ },
+ DESCENDING {
+ @Override
+ void prepare(Integer[] arr) {
+ ASCENDING.prepare(arr);
+ Collections.reverse(Arrays.asList(arr));
+ }
+ },
+ STRICTLY_DESCENDING {
+ @Override
+ void prepare(Integer[] arr) {
+ arr[0] = CACHE[CACHE.length - 1 - R.nextInt(10)];
+ for (int i = 1; i < arr.length; ++i) {
+ arr[i] = arr[i - 1] - 1 - R.nextInt(5);
+ }
+ }
+ };
+ abstract void prepare(Integer[] arr);
+ }
+
+ public static void main(String[] args) {
+ final Integer[] array = new Integer[2000000];
+ final Random random = new Random();
+ for (int i = 0; i < array.length; ++i) {
+ array[i] = random.nextInt(100);
+ }
+
+ final Map<String, Sorter> sorters = new LinkedHashMap<String, Sorter>();
+ sorters.put("Arrays.sort", new Sorter() {
+ @Override
+ protected int compare(int i, int j) { throw new UnsupportedOperationException(); }
+ @Override
+ protected void swap(int i, int j) { throw new UnsupportedOperationException(); }
+ @Override
+ public void sort(int from, int to) {
+ if (from == 0 && to == array.length) {
+ Arrays.sort(array);
+ } else {
+ throw new Error();
+ }
+ }
+ });
+ sorters.put("IntroSorter", new ArrayIntroSorter<Integer>(array));
+ sorters.put("HeapSorter", new ArrayHeapSorter<Integer>(array));
+ sorters.put("TernaryHeapSorter", new ArrayTernaryHeapSorter<Integer>(array));
+ sorters.put("MergeSorter", new ArrayMergeSorter<Integer>(array, array.length));
+ sorters.put("InPlaceMergeSorter", new ArrayInPlaceMergeSorter<Integer>(array));
+ sorters.put("TimSorter", new ArrayTimSorter<Integer>(array, array.length/2));
+
+ long start = System.nanoTime();
+ // JVM warming
+ while (System.nanoTime() - start < 10L * 1000 * 1000 * 1000) {
+ for (Sorter sorter : sorters.values()) {
+ Order.RANDOM.prepare(array);
+ sorter.sort(0, array.length);
+ }
+ }
+ for (Order order : Order.values()) {
+ System.out.print('\t');
+ System.out.print(order);
+ }
+ System.out.println();
+ for (int i = 0; i < 10; ++i) {
+ for (Map.Entry<String, Sorter> entry : sorters.entrySet()) {
+ final Sorter sorter = entry.getValue();
+ System.out.print(entry.getKey());
+ for (Order order : Order.values()) {
+ order.prepare(array);
+ start = System.nanoTime();
+ sorter.sort(0, array.length);
+ final long time = (System.nanoTime() - start) / 1000 / 1000;
+ System.out.print('\t');
+ System.out.print(time); // ms
+ }
+ System.out.println();
+ }
+ }
+ }
+
+}
Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/Benchmark.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/BinarySorterTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/BinarySorterTest.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/BinarySorterTest.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/BinarySorterTest.java Sat May 4 13:55:17 2013
@@ -0,0 +1,36 @@
+package org.apache.commons.sorting;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import org.junit.runner.RunWith;
+
+import com.carrotsearch.randomizedtesting.RandomizedRunner;
+
+@RunWith(RandomizedRunner.class)
+public class BinarySorterTest extends SortTestBase {
+
+ public BinarySorterTest() {
+ super(true);
+ }
+
+ @Override
+ public Sorter newSorter(Entry[] arr) {
+ return new ArrayBinarySorter<Entry>(arr);
+ }
+
+}
Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/BinarySorterTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/Entry.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/Entry.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/Entry.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/Entry.java Sat May 4 13:55:17 2013
@@ -0,0 +1,34 @@
+package org.apache.commons.sorting;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class Entry implements java.lang.Comparable<Entry> {
+
+ public final int value;
+ public final int ord;
+
+ public Entry(int value, int ord) {
+ this.value = value;
+ this.ord = ord;
+ }
+
+ public int compareTo(Entry other) {
+ return value < other.value ? -1 : value == other.value ? 0 : 1;
+ }
+
+}
Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/Entry.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/HeapSorterTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/HeapSorterTest.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/HeapSorterTest.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/HeapSorterTest.java Sat May 4 13:55:17 2013
@@ -0,0 +1,36 @@
+package org.apache.commons.sorting;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import org.junit.runner.RunWith;
+
+import com.carrotsearch.randomizedtesting.RandomizedRunner;
+
+@RunWith(RandomizedRunner.class)
+public class HeapSorterTest extends SortTestBase {
+
+ public HeapSorterTest() {
+ super(false);
+ }
+
+ @Override
+ public Sorter newSorter(Entry[] arr) {
+ return new ArrayHeapSorter<Entry>(arr);
+ }
+
+}
Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/HeapSorterTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/InPlaceMergeSorterTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/InPlaceMergeSorterTest.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/InPlaceMergeSorterTest.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/InPlaceMergeSorterTest.java Sat May 4 13:55:17 2013
@@ -0,0 +1,36 @@
+package org.apache.commons.sorting;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import org.junit.runner.RunWith;
+
+import com.carrotsearch.randomizedtesting.RandomizedRunner;
+
+@RunWith(RandomizedRunner.class)
+public class InPlaceMergeSorterTest extends SortTestBase {
+
+ public InPlaceMergeSorterTest() {
+ super(true);
+ }
+
+ @Override
+ public Sorter newSorter(Entry[] arr) {
+ return new ArrayInPlaceMergeSorter<Entry>(arr);
+ }
+
+}
Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/InPlaceMergeSorterTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/InsertionSorterTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/InsertionSorterTest.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/InsertionSorterTest.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/InsertionSorterTest.java Sat May 4 13:55:17 2013
@@ -0,0 +1,36 @@
+package org.apache.commons.sorting;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import org.junit.runner.RunWith;
+
+import com.carrotsearch.randomizedtesting.RandomizedRunner;
+
+@RunWith(RandomizedRunner.class)
+public class InsertionSorterTest extends SortTestBase {
+
+ public InsertionSorterTest() {
+ super(true);
+ }
+
+ @Override
+ public Sorter newSorter(Entry[] arr) {
+ return new ArrayInsertionSorter<Entry>(arr);
+ }
+
+}
Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/InsertionSorterTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/IntroSorterTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/IntroSorterTest.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/IntroSorterTest.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/IntroSorterTest.java Sat May 4 13:55:17 2013
@@ -0,0 +1,36 @@
+package org.apache.commons.sorting;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import org.junit.runner.RunWith;
+
+import com.carrotsearch.randomizedtesting.RandomizedRunner;
+
+@RunWith(RandomizedRunner.class)
+public class IntroSorterTest extends SortTestBase {
+
+ public IntroSorterTest() {
+ super(false);
+ }
+
+ @Override
+ public Sorter newSorter(Entry[] arr) {
+ return new ArrayIntroSorter<Entry>(arr);
+ }
+
+}
Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/IntroSorterTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/MergeSorterTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/MergeSorterTest.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/MergeSorterTest.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/MergeSorterTest.java Sat May 4 13:55:17 2013
@@ -0,0 +1,36 @@
+package org.apache.commons.sorting;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import org.junit.runner.RunWith;
+
+import com.carrotsearch.randomizedtesting.RandomizedRunner;
+
+@RunWith(RandomizedRunner.class)
+public class MergeSorterTest extends SortTestBase {
+
+ public MergeSorterTest() {
+ super(true);
+ }
+
+ @Override
+ public Sorter newSorter(Entry[] arr) {
+ return new ArrayMergeSorter<Entry>(arr, randomInt(arr.length));
+ }
+
+}
Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/MergeSorterTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/SortTestBase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/SortTestBase.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/SortTestBase.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/SortTestBase.java Sat May 4 13:55:17 2013
@@ -0,0 +1,170 @@
+package org.apache.commons.sorting;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.util.Arrays;
+
+import org.junit.Test;
+
+import com.carrotsearch.randomizedtesting.RandomizedTest;
+
+public abstract class SortTestBase extends RandomizedTest {
+
+ private final boolean stable;
+
+ public SortTestBase(boolean stable) {
+ this.stable = stable;
+ }
+
+ public abstract Sorter newSorter(Entry[] arr);
+
+ public void assertSorted(Entry[] original, Entry[] sorted) {
+ assertEquals(original.length, sorted.length);
+ Entry[] actuallySorted = Arrays.copyOf(original, original.length);
+ Arrays.sort(actuallySorted);
+ for (int i = 0; i < original.length; ++i) {
+ assertEquals(actuallySorted[i].value, sorted[i].value);
+ if (stable) {
+ assertEquals(actuallySorted[i].ord, sorted[i].ord);
+ }
+ }
+ }
+
+ public void test(Entry[] arr) {
+ final int o = randomInt(1000);
+ final Entry[] toSort = new Entry[o + arr.length + randomInt(2)];
+ System.arraycopy(arr, 0, toSort, o, arr.length);
+ final Sorter sorter = newSorter(toSort);
+ assert getClass().getSimpleName().indexOf(sorter.getClass().getSimpleName().substring("Array".length())) == 0;
+ sorter.sort(o, o + arr.length);
+ assertSorted(arr, Arrays.copyOfRange(toSort, o, o + arr.length));
+ }
+
+ enum Strategy {
+ RANDOM {
+ @Override
+ public void set(Entry[] arr, int i) {
+ arr[i] = new Entry(randomInt(), i);
+ }
+ },
+ RANDOM_LOW_CARDINALITY {
+ @Override
+ public void set(Entry[] arr, int i) {
+ arr[i] = new Entry(randomInt(5), i);
+ }
+ },
+ ASCENDING {
+ @Override
+ public void set(Entry[] arr, int i) {
+ arr[i] = i == 0
+ ? new Entry(randomInt(5), 0)
+ : new Entry(arr[i - 1].value + randomInt(5), i);
+ }
+ },
+ DESCENDING {
+ @Override
+ public void set(Entry[] arr, int i) {
+ arr[i] = i == 0
+ ? new Entry(randomInt(5), 0)
+ : new Entry(arr[i - 1].value - randomInt(5), i);
+ }
+ },
+ STRICTLY_DESCENDING {
+ @Override
+ public void set(Entry[] arr, int i) {
+ arr[i] = i == 0
+ ? new Entry(randomInt(5), 0)
+ : new Entry(arr[i - 1].value - randomIntBetween(1, 5), i);
+ }
+ },
+ ASCENDING_SEQUENCES {
+ @Override
+ public void set(Entry[] arr, int i) {
+ arr[i] = i == 0
+ ? new Entry(randomInt(5), 0)
+ : new Entry(rarely() ? randomInt(1000) : arr[i - 1].value + randomInt(5), i);
+ }
+ },
+ MOSTLY_ASCENDING {
+ @Override
+ public void set(Entry[] arr, int i) {
+ arr[i] = i == 0
+ ? new Entry(randomInt(5), 0)
+ : new Entry(arr[i - 1].value + randomIntBetween(-8, 10), i);
+ }
+ };
+ public abstract void set(Entry[] arr, int i);
+ }
+
+ public void test(Strategy strategy, int length) {
+ final Entry[] arr = new Entry[length];
+ for (int i = 0; i < arr.length; ++i) {
+ strategy.set(arr, i);
+ }
+ test(arr);
+ }
+
+ public void test(Strategy strategy) {
+ test(strategy, randomInt(20000));
+ }
+
+ @Test
+ public void testEmpty() {
+ test(new Entry[0]);
+ }
+
+ @Test
+ public void testOne() {
+ test(Strategy.RANDOM, 1);
+ }
+
+ @Test
+ public void testTwo() {
+ test(Strategy.RANDOM_LOW_CARDINALITY, 2);
+ }
+
+ @Test
+ public void testRandom() {
+ test(Strategy.RANDOM);
+ }
+
+ @Test
+ public void testRandomLowCardinality() {
+ test(Strategy.RANDOM_LOW_CARDINALITY);
+ }
+
+ @Test
+ public void testAscending() {
+ test(Strategy.ASCENDING);
+ }
+
+ @Test
+ public void testAscendingSequences() {
+ test(Strategy.ASCENDING_SEQUENCES);
+ }
+
+ @Test
+ public void testDescending() {
+ test(Strategy.DESCENDING);
+ }
+
+ @Test
+ public void testStrictlyDescending() {
+ test(Strategy.STRICTLY_DESCENDING);
+ }
+}
Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/SortTestBase.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/SorterTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/SorterTest.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/SorterTest.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/SorterTest.java Sat May 4 13:55:17 2013
@@ -0,0 +1,68 @@
+package org.apache.commons.sorting;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.util.Arrays;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+import com.carrotsearch.randomizedtesting.RandomizedRunner;
+import com.carrotsearch.randomizedtesting.RandomizedTest;
+import com.carrotsearch.randomizedtesting.annotations.Repeat;
+
+@RunWith(RandomizedRunner.class)
+public class SorterTest extends RandomizedTest {
+
+ @Test
+ @Repeat(iterations=10)
+ public void testLowerUpper() {
+ final Integer[] arr = new Integer[randomIntBetween(10, 100)];
+ for (int i = 0; i < arr.length; ++i) {
+ arr[i] = randomInt(20);
+ }
+ Arrays.sort(arr);
+ final Sorter sorter = new ArrayHeapSorter<Integer>(arr);
+ final int off = randomInt(arr.length - 1);
+ final int from = randomInt(arr.length / 2);
+ final int to = randomIntBetween(arr.length / 2, arr.length);
+
+ int dest = sorter.lower(from, to, off);
+ if (dest > from) {
+ assertTrue(arr[off] > arr[dest - 1]);
+ }
+ if (dest < to) {
+ assertTrue(arr[off] <= arr[dest]);
+ }
+
+ int dest2 = sorter.lower2(from, to, off);
+ assertEquals(dest, dest2);
+
+ dest = sorter.upper(from, to, off);
+ if (dest > from) {
+ assertTrue(arr[off] >= arr[dest - 1]);
+ }
+ if (dest < to) {
+ assertTrue(arr[off] < arr[dest]);
+ }
+
+ dest2 = sorter.upper2(from, to, off);
+ assertEquals(dest, dest2);
+ }
+
+}
Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/SorterTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/TernaryHeapSorterTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/TernaryHeapSorterTest.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/TernaryHeapSorterTest.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/TernaryHeapSorterTest.java Sat May 4 13:55:17 2013
@@ -0,0 +1,36 @@
+package org.apache.commons.sorting;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import org.junit.runner.RunWith;
+
+import com.carrotsearch.randomizedtesting.RandomizedRunner;
+
+@RunWith(RandomizedRunner.class)
+public class TernaryHeapSorterTest extends SortTestBase {
+
+ public TernaryHeapSorterTest() {
+ super(false);
+ }
+
+ @Override
+ public Sorter newSorter(Entry[] arr) {
+ return new ArrayTernaryHeapSorter<Entry>(arr);
+ }
+
+}
Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/TernaryHeapSorterTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/TimSorterTest.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/TimSorterTest.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/TimSorterTest.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/TimSorterTest.java Sat May 4 13:55:17 2013
@@ -0,0 +1,64 @@
+package org.apache.commons.sorting;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.util.Arrays;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+import com.carrotsearch.randomizedtesting.RandomizedRunner;
+import com.carrotsearch.randomizedtesting.annotations.Repeat;
+
+@RunWith(RandomizedRunner.class)
+public class TimSorterTest extends SortTestBase {
+
+ public TimSorterTest() {
+ super(true);
+ }
+
+ @Override
+ public Sorter newSorter(Entry[] arr) {
+ return new ArrayTimSorter<Entry>(arr, randomInt(arr.length));
+ }
+
+ @Test
+ @Repeat(iterations=10)
+ public void testLowerUpper() {
+ final Integer[] arr = new Integer[randomIntBetween(10, 100)];
+ final int max = randomInt(20);
+ for (int i = 0; i < arr.length; ++i) {
+ arr[i] = randomInt(max);
+ }
+ Arrays.sort(arr);
+ final TimSorter sorter = new ArrayTimSorter<Integer>(arr, arr.length);
+ final int savedStart = randomInt(arr.length / 2);
+ final int savedLength = randomIntBetween(1, arr.length - savedStart);
+ sorter.saveAll(savedStart, savedLength);
+ final int savedOff = randomInt(savedLength - 1);
+ final int off = savedStart + savedOff;
+ final int from = randomInt(arr.length / 2);
+ final int to = randomIntBetween(arr.length / 2, arr.length);
+
+ assertEquals(sorter.lower(from, to, off), sorter.lowerSaved(from, to, savedOff));
+ assertEquals(sorter.lower(from, to, off), sorter.lowerSaved3(from, to, savedOff));
+ assertEquals(sorter.upper(from, to, off), sorter.upperSaved(from, to, savedOff));
+ assertEquals(sorter.upper(from, to, off), sorter.upperSaved3(from, to, savedOff));
+ }
+
+}
Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/TimSorterTest.java
------------------------------------------------------------------------------
svn:eol-style = native