1 package org.apache.lucene.util;
4 * Licensed to the Apache Software Foundation (ASF) under one or more
5 * contributor license agreements. See the NOTICE file distributed with
6 * this work for additional information regarding copyright ownership.
7 * The ASF licenses this file to You under the Apache License, Version 2.0
8 * (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
11 * http://www.apache.org/licenses/LICENSE-2.0
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
20 import java.util.Arrays;
21 import java.util.Collections;
23 public class TestArrayUtil extends LuceneTestCase {
25 // Ensure ArrayUtil.getNextSize gives linear amortized cost of realloc/copy
26 public void testGrowth() {
30 // Make sure ArrayUtil hits Integer.MAX_VALUE, if we insist:
31 while(currentSize != Integer.MAX_VALUE) {
32 int nextSize = ArrayUtil.oversize(1+currentSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF);
33 assertTrue(nextSize > currentSize);
34 if (currentSize > 0) {
35 copyCost += currentSize;
36 double copyCostPerElement = ((double) copyCost)/currentSize;
37 assertTrue("cost " + copyCostPerElement, copyCostPerElement < 10.0);
39 currentSize = nextSize;
43 public void testMaxSize() {
44 // intentionally pass invalid elemSizes:
45 for(int elemSize=0;elemSize<10;elemSize++) {
46 assertEquals(Integer.MAX_VALUE, ArrayUtil.oversize(Integer.MAX_VALUE, elemSize));
47 assertEquals(Integer.MAX_VALUE, ArrayUtil.oversize(Integer.MAX_VALUE-1, elemSize));
51 public void testInvalidElementSizes() {
52 int num = atLeast(10000);
53 for (int iter = 0; iter < num; iter++) {
54 final int minTargetSize = random.nextInt(Integer.MAX_VALUE);
55 final int elemSize = random.nextInt(11);
56 final int v = ArrayUtil.oversize(minTargetSize, elemSize);
57 assertTrue(v >= minTargetSize);
61 public void testParseInt() throws Exception {
64 test = ArrayUtil.parseInt("".toCharArray());
66 } catch (NumberFormatException e) {
70 test = ArrayUtil.parseInt("foo".toCharArray());
72 } catch (NumberFormatException e) {
76 test = ArrayUtil.parseInt(String.valueOf(Long.MAX_VALUE).toCharArray());
78 } catch (NumberFormatException e) {
82 test = ArrayUtil.parseInt("0.34".toCharArray());
84 } catch (NumberFormatException e) {
89 test = ArrayUtil.parseInt("1".toCharArray());
90 assertTrue(test + " does not equal: " + 1, test == 1);
91 test = ArrayUtil.parseInt("-10000".toCharArray());
92 assertTrue(test + " does not equal: " + -10000, test == -10000);
93 test = ArrayUtil.parseInt("1923".toCharArray());
94 assertTrue(test + " does not equal: " + 1923, test == 1923);
95 test = ArrayUtil.parseInt("-1".toCharArray());
96 assertTrue(test + " does not equal: " + -1, test == -1);
97 test = ArrayUtil.parseInt("foo 1923 bar".toCharArray(), 4, 4);
98 assertTrue(test + " does not equal: " + 1923, test == 1923);
99 } catch (NumberFormatException e) {
107 private Integer[] createRandomArray(int maxSize) {
108 final Integer[] a = new Integer[random.nextInt(maxSize) + 1];
109 for (int i = 0; i < a.length; i++) {
110 a[i] = Integer.valueOf(random.nextInt(a.length));
115 public void testQuickSort() {
116 int num = atLeast(50);
117 for (int i = 0; i < num; i++) {
118 Integer[] a1 = createRandomArray(1000), a2 = a1.clone();
119 ArrayUtil.quickSort(a1);
121 assertArrayEquals(a2, a1);
123 a1 = createRandomArray(1000);
125 ArrayUtil.quickSort(a1, Collections.reverseOrder());
126 Arrays.sort(a2, Collections.reverseOrder());
127 assertArrayEquals(a2, a1);
128 // reverse back, so we can test that completely backwards sorted array (worst case) is working:
129 ArrayUtil.quickSort(a1);
131 assertArrayEquals(a2, a1);
135 private Integer[] createSparseRandomArray(int maxSize) {
136 final Integer[] a = new Integer[random.nextInt(maxSize) + 1];
137 for (int i = 0; i < a.length; i++) {
138 a[i] = Integer.valueOf(random.nextInt(2));
143 // This is a test for LUCENE-3054 (which fails without the merge sort fall back with stack overflow in most cases)
144 public void testQuickToMergeSortFallback() {
145 int num = atLeast(50);
146 for (int i = 0; i < num; i++) {
147 Integer[] a1 = createSparseRandomArray(40000), a2 = a1.clone();
148 ArrayUtil.quickSort(a1);
150 assertArrayEquals(a2, a1);
154 public void testMergeSort() {
155 int num = atLeast(50);
156 for (int i = 0; i < num; i++) {
157 Integer[] a1 = createRandomArray(1000), a2 = a1.clone();
158 ArrayUtil.mergeSort(a1);
160 assertArrayEquals(a2, a1);
162 a1 = createRandomArray(1000);
164 ArrayUtil.mergeSort(a1, Collections.reverseOrder());
165 Arrays.sort(a2, Collections.reverseOrder());
166 assertArrayEquals(a2, a1);
167 // reverse back, so we can test that completely backwards sorted array (worst case) is working:
168 ArrayUtil.mergeSort(a1);
170 assertArrayEquals(a2, a1);
174 public void testInsertionSort() {
175 for (int i = 0, c = atLeast(500); i < c; i++) {
176 Integer[] a1 = createRandomArray(30), a2 = a1.clone();
177 ArrayUtil.insertionSort(a1);
179 assertArrayEquals(a2, a1);
181 a1 = createRandomArray(30);
183 ArrayUtil.insertionSort(a1, Collections.reverseOrder());
184 Arrays.sort(a2, Collections.reverseOrder());
185 assertArrayEquals(a2, a1);
186 // reverse back, so we can test that completely backwards sorted array (worst case) is working:
187 ArrayUtil.insertionSort(a1);
189 assertArrayEquals(a2, a1);
193 static class Item implements Comparable<Item> {
194 final int val, order;
196 Item(int val, int order) {
201 public int compareTo(Item other) {
202 return this.order - other.order;
206 public String toString() {
207 return Integer.toString(val);
211 public void testMergeSortStability() {
212 Item[] items = new Item[100];
213 for (int i = 0; i < items.length; i++) {
214 // half of the items have value but same order. The value of this items is sorted,
215 // so they should always be in order after sorting.
216 // The other half has defined order, but no (-1) value (they should appear after
217 // all above, when sorted).
218 final boolean equal = random.nextBoolean();
219 items[i] = new Item(equal ? (i+1) : -1, equal ? 0 : (random.nextInt(1000)+1));
222 if (VERBOSE) System.out.println("Before: " + Arrays.toString(items));
223 // if you replace this with ArrayUtil.quickSort(), test should fail:
224 ArrayUtil.mergeSort(items);
225 if (VERBOSE) System.out.println("Sorted: " + Arrays.toString(items));
227 Item last = items[0];
228 for (int i = 1; i < items.length; i++) {
229 final Item act = items[i];
230 if (act.order == 0) {
231 // order of "equal" items should be not mixed up
232 assertTrue(act.val > last.val);
234 assertTrue(act.order >= last.order);
239 // should produce no exceptions
240 public void testEmptyArraySort() {
241 Integer[] a = new Integer[0];
242 ArrayUtil.quickSort(a);
243 ArrayUtil.mergeSort(a);
244 ArrayUtil.insertionSort(a);
245 ArrayUtil.quickSort(a, Collections.reverseOrder());
246 ArrayUtil.mergeSort(a, Collections.reverseOrder());
247 ArrayUtil.insertionSort(a, Collections.reverseOrder());