← Back to branch summary

~slub.team/goobi-indexserver/3.x

« back to all changes in this revision

Viewing changes to lucene/src/test/org/apache/lucene/util/TestArrayUtil.java

  • Committer: Sebastian Meyer
  • Date: 2012-08-03 09:12:40 UTC
  • Revision ID: sebastian.meyer@slub-dresden.de-20120803091240-x6861b0vabq1xror
https://launchpad.net/bugs/985487
Remove Lucene and Solr source code and add patches instead
Fix Bug #985487: Auto-suggestion for the search interface

Show diffs side-by-side

added added

removed removed

Lines of Context:
lucene/src/test/org/apache/lucene/util/TestArrayUtil.java
1
 
package org.apache.lucene.util;
2
 
 
3
 
/**
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
10
 
 *
11
 
 *     http://www.apache.org/licenses/LICENSE-2.0
12
 
 *
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.
18
 
 */
19
 
 
20
 
import java.util.Arrays;
21
 
import java.util.Collections;
22
 
 
23
 
public class TestArrayUtil extends LuceneTestCase {
24
 
 
25
 
  // Ensure ArrayUtil.getNextSize gives linear amortized cost of realloc/copy
26
 
  public void testGrowth() {
27
 
    int currentSize = 0;
28
 
    long copyCost = 0;
29
 
 
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);
38
 
      }
39
 
      currentSize = nextSize;
40
 
    }
41
 
  }
42
 
 
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));
48
 
    }
49
 
  }
50
 
 
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);
58
 
    }
59
 
  }
60
 
 
61
 
  public void testParseInt() throws Exception {
62
 
    int test;
63
 
    try {
64
 
      test = ArrayUtil.parseInt("".toCharArray());
65
 
      assertTrue(false);
66
 
    } catch (NumberFormatException e) {
67
 
      //expected
68
 
    }
69
 
    try {
70
 
      test = ArrayUtil.parseInt("foo".toCharArray());
71
 
      assertTrue(false);
72
 
    } catch (NumberFormatException e) {
73
 
      //expected
74
 
    }
75
 
    try {
76
 
      test = ArrayUtil.parseInt(String.valueOf(Long.MAX_VALUE).toCharArray());
77
 
      assertTrue(false);
78
 
    } catch (NumberFormatException e) {
79
 
      //expected
80
 
    }
81
 
    try {
82
 
      test = ArrayUtil.parseInt("0.34".toCharArray());
83
 
      assertTrue(false);
84
 
    } catch (NumberFormatException e) {
85
 
      //expected
86
 
    }
87
 
 
88
 
    try {
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) {
100
 
      e.printStackTrace();
101
 
      assertTrue(false);
102
 
    }
103
 
 
104
 
  }
105
 
 
106
 
  
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));
111
 
    }
112
 
    return a;
113
 
  }
114
 
  
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);
120
 
      Arrays.sort(a2);
121
 
      assertArrayEquals(a2, a1);
122
 
      
123
 
      a1 = createRandomArray(1000);
124
 
      a2 = a1.clone();
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);
130
 
      Arrays.sort(a2);
131
 
      assertArrayEquals(a2, a1);
132
 
    }
133
 
  }
134
 
  
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));
139
 
    }
140
 
    return a;
141
 
  }
142
 
  
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);
149
 
      Arrays.sort(a2);
150
 
      assertArrayEquals(a2, a1);
151
 
    }
152
 
  }
153
 
  
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);
159
 
      Arrays.sort(a2);
160
 
      assertArrayEquals(a2, a1);
161
 
      
162
 
      a1 = createRandomArray(1000);
163
 
      a2 = a1.clone();
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);
169
 
      Arrays.sort(a2);
170
 
      assertArrayEquals(a2, a1);
171
 
    }
172
 
  }
173
 
  
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);
178
 
      Arrays.sort(a2);
179
 
      assertArrayEquals(a2, a1);
180
 
      
181
 
      a1 = createRandomArray(30);
182
 
      a2 = a1.clone();
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);
188
 
      Arrays.sort(a2);
189
 
      assertArrayEquals(a2, a1);
190
 
    }
191
 
  }
192
 
  
193
 
  static class Item implements Comparable<Item> {
194
 
    final int val, order;
195
 
    
196
 
    Item(int val, int order) {
197
 
      this.val = val;
198
 
      this.order = order;
199
 
    }
200
 
    
201
 
    public int compareTo(Item other) {
202
 
      return this.order - other.order;
203
 
    }
204
 
    
205
 
    @Override
206
 
    public String toString() {
207
 
      return Integer.toString(val);
208
 
    }
209
 
  }
210
 
  
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));
220
 
    }
221
 
    
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));
226
 
    
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);
233
 
      }
234
 
      assertTrue(act.order >= last.order);
235
 
      last = act;
236
 
    }
237
 
  }
238
 
  
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());
248
 
  }
249
 
  
250
 
}