svn commit: r1085691 - in /lucene/dev/branches/branch_3x: ./ lucene/ lucene/src/java/org/apache/lucene/util/ lucene/src/test/org/apache/lucene/util/ solr/

[us...@apache.org]

Author: uschindler
Date: Sat Mar 26 11:11:27 2011
New Revision: 1085691

URL: http://svn.apache.org/viewvc?rev=1085691&view=rev
Log:
LUCENE-2990: ArrayUtil/CollectionUtil.*Sort() methods now exit early on empty or one-element lists/arrays

Modified:
    lucene/dev/branches/branch_3x/   (props changed)
    lucene/dev/branches/branch_3x/lucene/   (props changed)
    lucene/dev/branches/branch_3x/lucene/CHANGES.txt
    lucene/dev/branches/branch_3x/lucene/src/java/org/apache/lucene/util/ArrayUtil.java
    lucene/dev/branches/branch_3x/lucene/src/java/org/apache/lucene/util/CollectionUtil.java
    lucene/dev/branches/branch_3x/lucene/src/test/org/apache/lucene/util/TestCollectionUtil.java
    lucene/dev/branches/branch_3x/solr/   (props changed)

Modified: lucene/dev/branches/branch_3x/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/CHANGES.txt?rev=1085691&r1=1085690&r2=1085691&view=diff
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/CHANGES.txt (original)
+++ lucene/dev/branches/branch_3x/lucene/CHANGES.txt Sat Mar 26 11:11:27 2011
@@ -9,6 +9,11 @@ Changes in backwards compatibility polic
   a method getHeapArray() was added to retrieve the internal heap array as a
   non-generic Object[].  (Uwe Schindler, Yonik Seeley)
 
+Optimizations
+
+* LUCENE-2990: ArrayUtil/CollectionUtil.*Sort() methods now exit early
+  on empty or one-element lists/arrays.  (Uwe Schindler)
+
 ======================= Lucene 3.1 (not yet released) =======================
 
 Changes in backwards compatibility policy

Modified: lucene/dev/branches/branch_3x/lucene/src/java/org/apache/lucene/util/ArrayUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/src/java/org/apache/lucene/util/ArrayUtil.java?rev=1085691&r1=1085690&r2=1085691&view=diff
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/src/java/org/apache/lucene/util/ArrayUtil.java (original)
+++ lucene/dev/branches/branch_3x/lucene/src/java/org/apache/lucene/util/ArrayUtil.java Sat Mar 26 11:11:27 2011
@@ -542,6 +542,7 @@ public final class ArrayUtil {
    * @param toIndex end index (exclusive)
    */
   public static <T> void quickSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
+    if (toIndex-fromIndex <= 1) return;
     getSorter(a, comp).quickSort(fromIndex, toIndex-1);
   }
   
@@ -560,6 +561,7 @@ public final class ArrayUtil {
    * @param toIndex end index (exclusive)
    */
   public static <T extends Comparable<? super T>> void quickSort(T[] a, int fromIndex, int toIndex) {
+    if (toIndex-fromIndex <= 1) return;
     getSorter(a).quickSort(fromIndex, toIndex-1);
   }
   
@@ -580,6 +582,7 @@ public final class ArrayUtil {
    * @param toIndex end index (exclusive)
    */
   public static <T> void mergeSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
+    if (toIndex-fromIndex <= 1) return;
     getSorter(a, comp).mergeSort(fromIndex, toIndex-1);
   }
   
@@ -598,6 +601,7 @@ public final class ArrayUtil {
    * @param toIndex end index (exclusive)
    */
   public static <T extends Comparable<? super T>> void mergeSort(T[] a, int fromIndex, int toIndex) {
+    if (toIndex-fromIndex <= 1) return;
     getSorter(a).mergeSort(fromIndex, toIndex-1);
   }
   
@@ -618,6 +622,7 @@ public final class ArrayUtil {
    * @param toIndex end index (exclusive)
    */
   public static <T> void insertionSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
+    if (toIndex-fromIndex <= 1) return;
     getSorter(a, comp).insertionSort(fromIndex, toIndex-1);
   }
   
@@ -636,6 +641,7 @@ public final class ArrayUtil {
    * @param toIndex end index (exclusive)
    */
   public static <T extends Comparable<? super T>> void insertionSort(T[] a, int fromIndex, int toIndex) {
+    if (toIndex-fromIndex <= 1) return;
     getSorter(a).insertionSort(fromIndex, toIndex-1);
   }
   

Modified: lucene/dev/branches/branch_3x/lucene/src/java/org/apache/lucene/util/CollectionUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/src/java/org/apache/lucene/util/CollectionUtil.java?rev=1085691&r1=1085690&r2=1085691&view=diff
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/src/java/org/apache/lucene/util/CollectionUtil.java (original)
+++ lucene/dev/branches/branch_3x/lucene/src/java/org/apache/lucene/util/CollectionUtil.java Sat Mar 26 11:11:27 2011
@@ -100,7 +100,9 @@ public final class CollectionUtil {
    * @throws IllegalArgumentException if list is e.g. a linked list without random access.
    */
   public static <T> void quickSort(List<T> list, Comparator<? super T> comp) {
-    getSorter(list, comp).quickSort(0, list.size()-1);
+    final int size = list.size();
+    if (size <= 1) return;
+    getSorter(list, comp).quickSort(0, size-1);
   }
   
   /**
@@ -110,7 +112,9 @@ public final class CollectionUtil {
    * @throws IllegalArgumentException if list is e.g. a linked list without random access.
    */
   public static <T extends Comparable<? super T>> void quickSort(List<T> list) {
-    getSorter(list).quickSort(0, list.size()-1);
+    final int size = list.size();
+    if (size <= 1) return;
+    getSorter(list).quickSort(0, size-1);
   }
 
   // mergeSorts:
@@ -122,7 +126,9 @@ public final class CollectionUtil {
    * @throws IllegalArgumentException if list is e.g. a linked list without random access.
    */
   public static <T> void mergeSort(List<T> list, Comparator<? super T> comp) {
-    getSorter(list, comp).mergeSort(0, list.size()-1);
+    final int size = list.size();
+    if (size <= 1) return;
+    getSorter(list, comp).mergeSort(0, size-1);
   }
   
   /**
@@ -132,7 +138,9 @@ public final class CollectionUtil {
    * @throws IllegalArgumentException if list is e.g. a linked list without random access.
    */
   public static <T extends Comparable<? super T>> void mergeSort(List<T> list) {
-    getSorter(list).mergeSort(0, list.size()-1);
+    final int size = list.size();
+    if (size <= 1) return;
+    getSorter(list).mergeSort(0, size-1);
   }
 
   // insertionSorts:
@@ -144,7 +152,9 @@ public final class CollectionUtil {
    * @throws IllegalArgumentException if list is e.g. a linked list without random access.
    */
   public static <T> void insertionSort(List<T> list, Comparator<? super T> comp) {
-    getSorter(list, comp).insertionSort(0, list.size()-1);
+    final int size = list.size();
+    if (size <= 1) return;
+    getSorter(list, comp).insertionSort(0, size-1);
   }
   
   /**
@@ -154,7 +164,9 @@ public final class CollectionUtil {
    * @throws IllegalArgumentException if list is e.g. a linked list without random access.
    */
   public static <T extends Comparable<? super T>> void insertionSort(List<T> list) {
-    getSorter(list).insertionSort(0, list.size()-1);
+    final int size = list.size();
+    if (size <= 1) return;
+    getSorter(list).insertionSort(0, size-1);
   }
   
 }
\ No newline at end of file

Modified: lucene/dev/branches/branch_3x/lucene/src/test/org/apache/lucene/util/TestCollectionUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_3x/lucene/src/test/org/apache/lucene/util/TestCollectionUtil.java?rev=1085691&r1=1085690&r2=1085691&view=diff
==============================================================================
--- lucene/dev/branches/branch_3x/lucene/src/test/org/apache/lucene/util/TestCollectionUtil.java (original)
+++ lucene/dev/branches/branch_3x/lucene/src/test/org/apache/lucene/util/TestCollectionUtil.java Sat Mar 26 11:11:27 2011
@@ -20,6 +20,7 @@ package org.apache.lucene.util;
 import java.util.Arrays;
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.LinkedList;
 import java.util.List;
 
 public class TestCollectionUtil extends LuceneTestCase {
@@ -89,8 +90,8 @@ public class TestCollectionUtil extends 
     }
   }
   
-  // should produce no exceptions
-  public void testEmptyArraySort() {
+  public void testEmptyListSort() {
+    // should produce no exceptions
     List<Integer> list = Arrays.asList(new Integer[0]);
     CollectionUtil.quickSort(list);
     CollectionUtil.mergeSort(list);
@@ -98,6 +99,27 @@ public class TestCollectionUtil extends 
     CollectionUtil.quickSort(list, Collections.reverseOrder());
     CollectionUtil.mergeSort(list, Collections.reverseOrder());
     CollectionUtil.insertionSort(list, Collections.reverseOrder());
+    
+    // check that empty non-random access lists pass sorting without ex (as sorting is not needed)
+    list = new LinkedList<Integer>();
+    CollectionUtil.quickSort(list);
+    CollectionUtil.mergeSort(list);
+    CollectionUtil.insertionSort(list);
+    CollectionUtil.quickSort(list, Collections.reverseOrder());
+    CollectionUtil.mergeSort(list, Collections.reverseOrder());
+    CollectionUtil.insertionSort(list, Collections.reverseOrder());
+  }
+  
+  public void testOneElementListSort() {
+    // check that one-element non-random access lists pass sorting without ex (as sorting is not needed)
+    List<Integer> list = new LinkedList<Integer>();
+    list.add(1);
+    CollectionUtil.quickSort(list);
+    CollectionUtil.mergeSort(list);
+    CollectionUtil.insertionSort(list);
+    CollectionUtil.quickSort(list, Collections.reverseOrder());
+    CollectionUtil.mergeSort(list, Collections.reverseOrder());
+    CollectionUtil.insertionSort(list, Collections.reverseOrder());
   }
   
 }