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.ArrayList;
22 import java.util.Collections;
23 import java.util.LinkedList;
24 import java.util.List;
26 public class TestCollectionUtil extends LuceneTestCase {
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));
33 return Arrays.asList(a);
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);
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);
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);
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);
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);
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);
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());
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());
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>();
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());