lucene-java-3.5.0/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 }