lucene-java-3.4.0/lucene/backwards/src/test/org/apache/lucene/util/TestCollectionUtil.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.ArrayList;
  22 import java.util.Collections;
  23 import java.util.LinkedList;
  24 import java.util.List;
  25
  26 public class TestCollectionUtil extends LuceneTestCase {
  27
  28   private List<Integer> createRandomList(int maxSize) {
  29     final Integer[] a = new Integer[random.nextInt(maxSize) + 1];
  30     for (int i = 0; i < a.length; i++) {
  31       a[i] = Integer.valueOf(random.nextInt(a.length));
  32     }
  33     return Arrays.asList(a);
  34   }
  35
  36   public void testQuickSort() {
  37     for (int i = 0, c = atLeast(500); i < c; i++) {
  38       List<Integer> list1 = createRandomList(1000), list2 = new ArrayList<Integer>(list1);
  39       CollectionUtil.quickSort(list1);
  40       Collections.sort(list2);
  41       assertEquals(list2, list1);
  42
  43       list1 = createRandomList(1000);
  44       list2 = new ArrayList<Integer>(list1);
  45       CollectionUtil.quickSort(list1, Collections.reverseOrder());
  46       Collections.sort(list2, Collections.reverseOrder());
  47       assertEquals(list2, list1);
  48       // reverse back, so we can test that completely backwards sorted array (worst case) is working:
  49       CollectionUtil.quickSort(list1);
  50       Collections.sort(list2);
  51       assertEquals(list2, list1);
  52     }
  53   }
  54
  55   public void testMergeSort() {
  56     for (int i = 0, c = atLeast(500); i < c; i++) {
  57       List<Integer> list1 = createRandomList(1000), list2 = new ArrayList<Integer>(list1);
  58       CollectionUtil.mergeSort(list1);
  59       Collections.sort(list2);
  60       assertEquals(list2, list1);
  61
  62       list1 = createRandomList(1000);
  63       list2 = new ArrayList<Integer>(list1);
  64       CollectionUtil.mergeSort(list1, Collections.reverseOrder());
  65       Collections.sort(list2, Collections.reverseOrder());
  66       assertEquals(list2, list1);
  67       // reverse back, so we can test that completely backwards sorted array (worst case) is working:
  68       CollectionUtil.mergeSort(list1);
  69       Collections.sort(list2);
  70       assertEquals(list2, list1);
  71     }
  72   }
  73
  74   public void testInsertionSort() {
  75     for (int i = 0, c = atLeast(500); i < c; i++) {
  76       List<Integer> list1 = createRandomList(30), list2 = new ArrayList<Integer>(list1);
  77       CollectionUtil.insertionSort(list1);
  78       Collections.sort(list2);
  79       assertEquals(list2, list1);
  80
  81       list1 = createRandomList(30);
  82       list2 = new ArrayList<Integer>(list1);
  83       CollectionUtil.insertionSort(list1, Collections.reverseOrder());
  84       Collections.sort(list2, Collections.reverseOrder());
  85       assertEquals(list2, list1);
  86       // reverse back, so we can test that completely backwards sorted array (worst case) is working:
  87       CollectionUtil.insertionSort(list1);
  88       Collections.sort(list2);
  89       assertEquals(list2, list1);
  90     }
  91   }
  92
  93   public void testEmptyListSort() {
  94     // should produce no exceptions
  95     List<Integer> list = Arrays.asList(new Integer[0]);
  96     CollectionUtil.quickSort(list);
  97     CollectionUtil.mergeSort(list);
  98     CollectionUtil.insertionSort(list);
  99     CollectionUtil.quickSort(list, Collections.reverseOrder());
 100     CollectionUtil.mergeSort(list, Collections.reverseOrder());
 101     CollectionUtil.insertionSort(list, Collections.reverseOrder());
 102
 103     // check that empty non-random access lists pass sorting without ex (as sorting is not needed)
 104     list = new LinkedList<Integer>();
 105     CollectionUtil.quickSort(list);
 106     CollectionUtil.mergeSort(list);
 107     CollectionUtil.insertionSort(list);
 108     CollectionUtil.quickSort(list, Collections.reverseOrder());
 109     CollectionUtil.mergeSort(list, Collections.reverseOrder());
 110     CollectionUtil.insertionSort(list, Collections.reverseOrder());
 111   }
 112
 113   public void testOneElementListSort() {
 114     // check that one-element non-random access lists pass sorting without ex (as sorting is not needed)
 115     List<Integer> list = new LinkedList<Integer>();
 116     list.add(1);
 117     CollectionUtil.quickSort(list);
 118     CollectionUtil.mergeSort(list);
 119     CollectionUtil.insertionSort(list);
 120     CollectionUtil.quickSort(list, Collections.reverseOrder());
 121     CollectionUtil.mergeSort(list, Collections.reverseOrder());
 122     CollectionUtil.insertionSort(list, Collections.reverseOrder());
 123   }
 124
 125 }