org.apache.lucene.util
Class CollectionUtil

java.lang.Object
  org.apache.lucene.util.CollectionUtil

public final class CollectionUtil
extends Object

Methods for manipulating (sorting) collections. Sort methods work directly on the supplied lists and don't copy to/from arrays before/after. For medium size collections as used in the Lucene indexer that is much more efficient.

NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

Method Summary

static <T extends Comparable<? super T>> void	insertionSort(List<T> list) Sorts the given random access List in natural order.
static <T> void	insertionSort(List<T> list, Comparator<? super T> comp) Sorts the given random access List using the Comparator.
static <T extends Comparable<? super T>> void	mergeSort(List<T> list) Sorts the given random access List in natural order.
static <T> void	mergeSort(List<T> list, Comparator<? super T> comp) Sorts the given random access List using the Comparator.
static <T extends Comparable<? super T>> void	quickSort(List<T> list) Sorts the given random access List in natural order.
static <T> void	quickSort(List<T> list, Comparator<? super T> comp) Sorts the given random access List using the Comparator.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

quickSort

public static <T> void quickSort(List<T> list,
                                 Comparator<? super T> comp)

Sorts the given random access List using the Comparator. The list must implement RandomAccess. This method uses the quick sort algorithm, but falls back to insertion sort for small lists.

Throws:

IllegalArgumentException - if list is e.g. a linked list without random access.

quickSort

public static <T extends Comparable<? super T>> void quickSort(List<T> list)

Sorts the given random access List in natural order. The list must implement RandomAccess. This method uses the quick sort algorithm, but falls back to insertion sort for small lists.

Throws:

IllegalArgumentException - if list is e.g. a linked list without random access.

mergeSort

public static <T> void mergeSort(List<T> list,
                                 Comparator<? super T> comp)

Sorts the given random access List using the Comparator. The list must implement RandomAccess. This method uses the merge sort algorithm, but falls back to insertion sort for small lists.

Throws:

IllegalArgumentException - if list is e.g. a linked list without random access.

mergeSort

public static <T extends Comparable<? super T>> void mergeSort(List<T> list)

Sorts the given random access List in natural order. The list must implement RandomAccess. This method uses the merge sort algorithm, but falls back to insertion sort for small lists.

Throws:

IllegalArgumentException - if list is e.g. a linked list without random access.

insertionSort

public static <T> void insertionSort(List<T> list,
                                     Comparator<? super T> comp)

Sorts the given random access List using the Comparator. The list must implement RandomAccess. This method uses the insertion sort algorithm. It is only recommended to use this algorithm for partially sorted small lists!

Throws:

IllegalArgumentException - if list is e.g. a linked list without random access.

insertionSort

public static <T extends Comparable<? super T>> void insertionSort(List<T> list)

Sorts the given random access List in natural order. The list must implement RandomAccess. This method uses the insertion sort algorithm. It is only recommended to use this algorithm for partially sorted small lists!

Throws:

IllegalArgumentException - if list is e.g. a linked list without random access.