lucene-java-3.4.0/lucene/src/java/org/apache/lucene/util/CollectionUtil.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.Comparator;
  21 import java.util.Collections;
  22 import java.util.List;
  23 import java.util.RandomAccess;
  24
  25 /**
  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.
  30  *
  31  * @lucene.internal
  32  */
  33
  34 public final class CollectionUtil {
  35
  36   private CollectionUtil() {} // no instance
  37
  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() {
  43       @Override
  44       protected void swap(int i, int j) {
  45         Collections.swap(list, i, j);
  46       }
  47
  48       @Override
  49       protected int compare(int i, int j) {
  50         return comp.compare(list.get(i), list.get(j));
  51       }
  52
  53       @Override
  54       protected void setPivot(int i) {
  55         pivot = list.get(i);
  56       }
  57
  58       @Override
  59       protected int comparePivot(int j) {
  60         return comp.compare(pivot, list.get(j));
  61       }
  62
  63       private T pivot;
  64     };
  65   }
  66
  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() {
  72       @Override
  73       protected void swap(int i, int j) {
  74         Collections.swap(list, i, j);
  75       }
  76
  77       @Override
  78       protected int compare(int i, int j) {
  79         return list.get(i).compareTo(list.get(j));
  80       }
  81
  82       @Override
  83       protected void setPivot(int i) {
  84         pivot = list.get(i);
  85       }
  86
  87       @Override
  88       protected int comparePivot(int j) {
  89         return pivot.compareTo(list.get(j));
  90       }
  91
  92       private T pivot;
  93     };
  94   }
  95
  96   /**
  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.
 101    */
 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);
 106   }
 107
 108   /**
 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.
 113    */
 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);
 118   }
 119
 120   // mergeSorts:
 121
 122   /**
 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.
 127    */
 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);
 132   }
 133
 134   /**
 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.
 139    */
 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);
 144   }
 145
 146   // insertionSorts:
 147
 148   /**
 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.
 153    */
 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);
 158   }
 159
 160   /**
 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.
 165    */
 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);
 170   }
 171
 172 }