X-Git-Url: https://git.mdrn.pl/pylucene.git/blobdiff_plain/a2e61f0c04805cfcb8706176758d1283c7e3a55c..aaeed5504b982cf3545252ab528713250aa33eed:/lucene-java-3.4.0/lucene/backwards/src/test/org/apache/lucene/util/TestArrayUtil.java diff --git a/lucene-java-3.4.0/lucene/backwards/src/test/org/apache/lucene/util/TestArrayUtil.java b/lucene-java-3.4.0/lucene/backwards/src/test/org/apache/lucene/util/TestArrayUtil.java deleted file mode 100644 index 93f583c..0000000 --- a/lucene-java-3.4.0/lucene/backwards/src/test/org/apache/lucene/util/TestArrayUtil.java +++ /dev/null @@ -1,250 +0,0 @@ -package org.apache.lucene.util; - -/** - * 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; - -public class TestArrayUtil extends LuceneTestCase { - - // Ensure ArrayUtil.getNextSize gives linear amortized cost of realloc/copy - public void testGrowth() { - int currentSize = 0; - long copyCost = 0; - - // Make sure ArrayUtil hits Integer.MAX_VALUE, if we insist: - while(currentSize != Integer.MAX_VALUE) { - int nextSize = ArrayUtil.oversize(1+currentSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF); - assertTrue(nextSize > currentSize); - if (currentSize > 0) { - copyCost += currentSize; - double copyCostPerElement = ((double) copyCost)/currentSize; - assertTrue("cost " + copyCostPerElement, copyCostPerElement < 10.0); - } - currentSize = nextSize; - } - } - - public void testMaxSize() { - // intentionally pass invalid elemSizes: - for(int elemSize=0;elemSize<10;elemSize++) { - assertEquals(Integer.MAX_VALUE, ArrayUtil.oversize(Integer.MAX_VALUE, elemSize)); - assertEquals(Integer.MAX_VALUE, ArrayUtil.oversize(Integer.MAX_VALUE-1, elemSize)); - } - } - - public void testInvalidElementSizes() { - int num = atLeast(10000); - for (int iter = 0; iter < num; iter++) { - final int minTargetSize = random.nextInt(Integer.MAX_VALUE); - final int elemSize = random.nextInt(11); - final int v = ArrayUtil.oversize(minTargetSize, elemSize); - assertTrue(v >= minTargetSize); - } - } - - public void testParseInt() throws Exception { - int test; - try { - test = ArrayUtil.parseInt("".toCharArray()); - assertTrue(false); - } catch (NumberFormatException e) { - //expected - } - try { - test = ArrayUtil.parseInt("foo".toCharArray()); - assertTrue(false); - } catch (NumberFormatException e) { - //expected - } - try { - test = ArrayUtil.parseInt(String.valueOf(Long.MAX_VALUE).toCharArray()); - assertTrue(false); - } catch (NumberFormatException e) { - //expected - } - try { - test = ArrayUtil.parseInt("0.34".toCharArray()); - assertTrue(false); - } catch (NumberFormatException e) { - //expected - } - - try { - test = ArrayUtil.parseInt("1".toCharArray()); - assertTrue(test + " does not equal: " + 1, test == 1); - test = ArrayUtil.parseInt("-10000".toCharArray()); - assertTrue(test + " does not equal: " + -10000, test == -10000); - test = ArrayUtil.parseInt("1923".toCharArray()); - assertTrue(test + " does not equal: " + 1923, test == 1923); - test = ArrayUtil.parseInt("-1".toCharArray()); - assertTrue(test + " does not equal: " + -1, test == -1); - test = ArrayUtil.parseInt("foo 1923 bar".toCharArray(), 4, 4); - assertTrue(test + " does not equal: " + 1923, test == 1923); - } catch (NumberFormatException e) { - e.printStackTrace(); - assertTrue(false); - } - - } - - - private Integer[] createRandomArray(int maxSize) { - final Integer[] a = new Integer[random.nextInt(maxSize) + 1]; - for (int i = 0; i < a.length; i++) { - a[i] = Integer.valueOf(random.nextInt(a.length)); - } - return a; - } - - public void testQuickSort() { - int num = atLeast(50); - for (int i = 0; i < num; i++) { - Integer[] a1 = createRandomArray(1000), a2 = a1.clone(); - ArrayUtil.quickSort(a1); - Arrays.sort(a2); - assertArrayEquals(a2, a1); - - a1 = createRandomArray(1000); - a2 = a1.clone(); - ArrayUtil.quickSort(a1, Collections.reverseOrder()); - Arrays.sort(a2, Collections.reverseOrder()); - assertArrayEquals(a2, a1); - // reverse back, so we can test that completely backwards sorted array (worst case) is working: - ArrayUtil.quickSort(a1); - Arrays.sort(a2); - assertArrayEquals(a2, a1); - } - } - - private Integer[] createSparseRandomArray(int maxSize) { - final Integer[] a = new Integer[random.nextInt(maxSize) + 1]; - for (int i = 0; i < a.length; i++) { - a[i] = Integer.valueOf(random.nextInt(2)); - } - return a; - } - - // This is a test for LUCENE-3054 (which fails without the merge sort fall back with stack overflow in most cases) - public void testQuickToMergeSortFallback() { - int num = atLeast(50); - for (int i = 0; i < num; i++) { - Integer[] a1 = createSparseRandomArray(40000), a2 = a1.clone(); - ArrayUtil.quickSort(a1); - Arrays.sort(a2); - assertArrayEquals(a2, a1); - } - } - - public void testMergeSort() { - int num = atLeast(50); - for (int i = 0; i < num; i++) { - Integer[] a1 = createRandomArray(1000), a2 = a1.clone(); - ArrayUtil.mergeSort(a1); - Arrays.sort(a2); - assertArrayEquals(a2, a1); - - a1 = createRandomArray(1000); - a2 = a1.clone(); - ArrayUtil.mergeSort(a1, Collections.reverseOrder()); - Arrays.sort(a2, Collections.reverseOrder()); - assertArrayEquals(a2, a1); - // reverse back, so we can test that completely backwards sorted array (worst case) is working: - ArrayUtil.mergeSort(a1); - Arrays.sort(a2); - assertArrayEquals(a2, a1); - } - } - - public void testInsertionSort() { - for (int i = 0, c = atLeast(500); i < c; i++) { - Integer[] a1 = createRandomArray(30), a2 = a1.clone(); - ArrayUtil.insertionSort(a1); - Arrays.sort(a2); - assertArrayEquals(a2, a1); - - a1 = createRandomArray(30); - a2 = a1.clone(); - ArrayUtil.insertionSort(a1, Collections.reverseOrder()); - Arrays.sort(a2, Collections.reverseOrder()); - assertArrayEquals(a2, a1); - // reverse back, so we can test that completely backwards sorted array (worst case) is working: - ArrayUtil.insertionSort(a1); - Arrays.sort(a2); - assertArrayEquals(a2, a1); - } - } - - static class Item implements Comparable { - final int val, order; - - Item(int val, int order) { - this.val = val; - this.order = order; - } - - public int compareTo(Item other) { - return this.order - other.order; - } - - @Override - public String toString() { - return Integer.toString(val); - } - } - - public void testMergeSortStability() { - Item[] items = new Item[100]; - for (int i = 0; i < items.length; i++) { - // half of the items have value but same order. The value of this items is sorted, - // so they should always be in order after sorting. - // The other half has defined order, but no (-1) value (they should appear after - // all above, when sorted). - final boolean equal = random.nextBoolean(); - items[i] = new Item(equal ? (i+1) : -1, equal ? 0 : (random.nextInt(1000)+1)); - } - - if (VERBOSE) System.out.println("Before: " + Arrays.toString(items)); - // if you replace this with ArrayUtil.quickSort(), test should fail: - ArrayUtil.mergeSort(items); - if (VERBOSE) System.out.println("Sorted: " + Arrays.toString(items)); - - Item last = items[0]; - for (int i = 1; i < items.length; i++) { - final Item act = items[i]; - if (act.order == 0) { - // order of "equal" items should be not mixed up - assertTrue(act.val > last.val); - } - assertTrue(act.order >= last.order); - last = act; - } - } - - // should produce no exceptions - public void testEmptyArraySort() { - Integer[] a = new Integer[0]; - ArrayUtil.quickSort(a); - ArrayUtil.mergeSort(a); - ArrayUtil.insertionSort(a); - ArrayUtil.quickSort(a, Collections.reverseOrder()); - ArrayUtil.mergeSort(a, Collections.reverseOrder()); - ArrayUtil.insertionSort(a, Collections.reverseOrder()); - } - -}