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.Comparator;
21 import java.util.Collections;
22 import java.util.List;
23 import java.util.RandomAccess;
26 * Methods for manipulating (sorting) collections.
27 * Sort methods work directly on the supplied lists and don't copy to/from arrays
28 * before/after. For medium size collections as used in the Lucene indexer that is
29 * much more efficient.
34 public final class CollectionUtil {
36 private CollectionUtil() {} // no instance
38 /** SorterTemplate with custom {@link Comparator} */
39 private static <T> SorterTemplate getSorter(final List<T> list, final Comparator<? super T> comp) {
40 if (!(list instanceof RandomAccess))
41 throw new IllegalArgumentException("CollectionUtil can only sort random access lists in-place.");
42 return new SorterTemplate() {
44 protected void swap(int i, int j) {
45 Collections.swap(list, i, j);
49 protected int compare(int i, int j) {
50 return comp.compare(list.get(i), list.get(j));
54 protected void setPivot(int i) {
59 protected int comparePivot(int j) {
60 return comp.compare(pivot, list.get(j));
67 /** Natural SorterTemplate */
68 private static <T extends Comparable<? super T>> SorterTemplate getSorter(final List<T> list) {
69 if (!(list instanceof RandomAccess))
70 throw new IllegalArgumentException("CollectionUtil can only sort random access lists in-place.");
71 return new SorterTemplate() {
73 protected void swap(int i, int j) {
74 Collections.swap(list, i, j);
78 protected int compare(int i, int j) {
79 return list.get(i).compareTo(list.get(j));
83 protected void setPivot(int i) {
88 protected int comparePivot(int j) {
89 return pivot.compareTo(list.get(j));
97 * Sorts the given random access {@link List} using the {@link Comparator}.
98 * The list must implement {@link RandomAccess}. This method uses the quick sort
99 * algorithm, but falls back to insertion sort for small lists.
100 * @throws IllegalArgumentException if list is e.g. a linked list without random access.
102 public static <T> void quickSort(List<T> list, Comparator<? super T> comp) {
103 final int size = list.size();
104 if (size <= 1) return;
105 getSorter(list, comp).quickSort(0, size-1);
109 * Sorts the given random access {@link List} in natural order.
110 * The list must implement {@link RandomAccess}. This method uses the quick sort
111 * algorithm, but falls back to insertion sort for small lists.
112 * @throws IllegalArgumentException if list is e.g. a linked list without random access.
114 public static <T extends Comparable<? super T>> void quickSort(List<T> list) {
115 final int size = list.size();
116 if (size <= 1) return;
117 getSorter(list).quickSort(0, size-1);
123 * Sorts the given random access {@link List} using the {@link Comparator}.
124 * The list must implement {@link RandomAccess}. This method uses the merge sort
125 * algorithm, but falls back to insertion sort for small lists.
126 * @throws IllegalArgumentException if list is e.g. a linked list without random access.
128 public static <T> void mergeSort(List<T> list, Comparator<? super T> comp) {
129 final int size = list.size();
130 if (size <= 1) return;
131 getSorter(list, comp).mergeSort(0, size-1);
135 * Sorts the given random access {@link List} in natural order.
136 * The list must implement {@link RandomAccess}. This method uses the merge sort
137 * algorithm, but falls back to insertion sort for small lists.
138 * @throws IllegalArgumentException if list is e.g. a linked list without random access.
140 public static <T extends Comparable<? super T>> void mergeSort(List<T> list) {
141 final int size = list.size();
142 if (size <= 1) return;
143 getSorter(list).mergeSort(0, size-1);
149 * Sorts the given random access {@link List} using the {@link Comparator}.
150 * The list must implement {@link RandomAccess}. This method uses the insertion sort
151 * algorithm. It is only recommended to use this algorithm for partially sorted small lists!
152 * @throws IllegalArgumentException if list is e.g. a linked list without random access.
154 public static <T> void insertionSort(List<T> list, Comparator<? super T> comp) {
155 final int size = list.size();
156 if (size <= 1) return;
157 getSorter(list, comp).insertionSort(0, size-1);
161 * Sorts the given random access {@link List} in natural order.
162 * The list must implement {@link RandomAccess}. This method uses the insertion sort
163 * algorithm. It is only recommended to use this algorithm for partially sorted small lists!
164 * @throws IllegalArgumentException if list is e.g. a linked list without random access.
166 public static <T extends Comparable<? super T>> void insertionSort(List<T> list) {
167 final int size = list.size();
168 if (size <= 1) return;
169 getSorter(list).insertionSort(0, size-1);