+++ /dev/null
-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<Item> {
- 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());
- }
-
-}
fnp / pylucene.git / blobdiff