You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2013/05/03 16:15:18 UTC
svn commit: r1478802 [1/2] - in /lucene/dev/branches/branch_4x: ./ lucene/
lucene/core/ lucene/core/src/java/org/apache/lucene/index/
lucene/core/src/java/org/apache/lucene/search/
lucene/core/src/java/org/apache/lucene/search/spans/ lucene/core/src/ja...
Author: jpountz
Date: Fri May 3 14:15:17 2013
New Revision: 1478802
URL: http://svn.apache.org/r1478802
Log:
LUCENE-4946: Refactor SorterTemplate (now Sorter) (merged from r1478785 and r1478801).
Added:
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/ArrayInPlaceMergeSorter.java
- copied unchanged from r1478785, lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/ArrayInPlaceMergeSorter.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/ArrayIntroSorter.java
- copied unchanged from r1478785, lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/ArrayIntroSorter.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/ArrayTimSorter.java
- copied unchanged from r1478785, lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/ArrayTimSorter.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/InPlaceMergeSorter.java
- copied unchanged from r1478785, lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/InPlaceMergeSorter.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/IntroSorter.java
- copied unchanged from r1478785, lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/IntroSorter.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/Sorter.java
- copied unchanged from r1478785, lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/Sorter.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/TimSorter.java
- copied unchanged from r1478785, lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/TimSorter.java
lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/BaseSortTestCase.java
- copied unchanged from r1478785, lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/BaseSortTestCase.java
lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestInPlaceMergeSorter.java
- copied unchanged from r1478785, lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestInPlaceMergeSorter.java
lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestIntroSorter.java
- copied unchanged from r1478785, lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestIntroSorter.java
lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestTimSorter.java
- copied unchanged from r1478785, lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestTimSorter.java
Removed:
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/SorterTemplate.java
lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestSorterTemplate.java
Modified:
lucene/dev/branches/branch_4x/ (props changed)
lucene/dev/branches/branch_4x/lucene/ (props changed)
lucene/dev/branches/branch_4x/lucene/CHANGES.txt (contents, props changed)
lucene/dev/branches/branch_4x/lucene/NOTICE.txt (contents, props changed)
lucene/dev/branches/branch_4x/lucene/core/ (props changed)
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/ConcurrentMergeScheduler.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/DocFieldProcessor.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/FreqProxTermsWriter.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/FrozenBufferedDeletes.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/IndexFileDeleter.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/ConjunctionScorer.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/MinShouldMatchSumScorer.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/MultiPhraseQuery.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/PhraseQuery.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/TopTermsRewrite.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/BytesRefHash.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/automaton/BasicOperations.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/automaton/State.java
lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestArrayUtil.java
lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestCollectionUtil.java
lucene/dev/branches/branch_4x/lucene/facet/ (props changed)
lucene/dev/branches/branch_4x/lucene/facet/src/test/org/apache/lucene/facet/search/TestDrillSideways.java
lucene/dev/branches/branch_4x/lucene/highlighter/ (props changed)
lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java
lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenStreamFromTermPositionVector.java
lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/Passage.java
lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/PostingsHighlighter.java
lucene/dev/branches/branch_4x/lucene/memory/ (props changed)
lucene/dev/branches/branch_4x/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java
lucene/dev/branches/branch_4x/lucene/misc/ (props changed)
lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/CompoundFileExtractor.java
lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/sorter/Sorter.java
lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java
lucene/dev/branches/branch_4x/lucene/suggest/ (props changed)
lucene/dev/branches/branch_4x/lucene/suggest/src/java/org/apache/lucene/search/spell/DirectSpellChecker.java
lucene/dev/branches/branch_4x/lucene/suggest/src/java/org/apache/lucene/search/suggest/BytesRefArray.java
lucene/dev/branches/branch_4x/solr/ (props changed)
lucene/dev/branches/branch_4x/solr/core/ (props changed)
lucene/dev/branches/branch_4x/solr/core/src/java/org/apache/solr/handler/AnalysisRequestHandlerBase.java
Modified: lucene/dev/branches/branch_4x/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/CHANGES.txt?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/CHANGES.txt (original)
+++ lucene/dev/branches/branch_4x/lucene/CHANGES.txt Fri May 3 14:15:17 2013
@@ -23,6 +23,10 @@ Changes in backwards compatibility polic
* LUCENE-4973: SnapshotDeletionPolicy no longer requires a unique
String id (Mike McCandless, Shai Erera)
+* LUCENE-4946: The internal sorting API (SorterTemplate, now Sorter) has been
+ completely refactored to allow for a better implementation of TimSort.
+ (Adrien Grand, Uwe Schindler, Dawid Weiss)
+
Bug Fixes
* LUCENE-4935: CustomScoreQuery wrongly applied its query boost twice
Modified: lucene/dev/branches/branch_4x/lucene/NOTICE.txt
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/NOTICE.txt?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/NOTICE.txt (original)
+++ lucene/dev/branches/branch_4x/lucene/NOTICE.txt Fri May 3 14:15:17 2013
@@ -27,11 +27,6 @@ Jean-Philippe Barrette-LaPierre. This li
see http://sites.google.com/site/rrettesite/moman and
http://bitbucket.org/jpbarrette/moman/overview/
-The class org.apache.lucene.util.SorterTemplate was inspired by CGLIB's class
-with the same name. The implementation part is mainly done using pre-existing
-Lucene sorting code. In-place stable mergesort was borrowed from CGLIB,
-which is Apache-licensed.
-
The class org.apache.lucene.util.WeakIdentityMap was derived from
the Apache CXF project and is Apache License 2.0.
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/ConcurrentMergeScheduler.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/ConcurrentMergeScheduler.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/ConcurrentMergeScheduler.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/ConcurrentMergeScheduler.java Fri May 3 14:15:17 2013
@@ -184,7 +184,7 @@ public class ConcurrentMergeScheduler ex
}
// Sort the merge threads in descending order.
- CollectionUtil.mergeSort(activeMerges, compareByMergeDocCount);
+ CollectionUtil.timSort(activeMerges, compareByMergeDocCount);
int pri = mergeThreadPriority;
final int activeMergeCount = activeMerges.size();
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/DocFieldProcessor.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/DocFieldProcessor.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/DocFieldProcessor.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/DocFieldProcessor.java Fri May 3 14:15:17 2013
@@ -248,7 +248,7 @@ final class DocFieldProcessor extends Do
// sort the subset of fields that have vectors
// enabled; we could save [small amount of] CPU
// here.
- ArrayUtil.quickSort(fields, 0, fieldCount, fieldsComp);
+ ArrayUtil.introSort(fields, 0, fieldCount, fieldsComp);
for(int i=0;i<fieldCount;i++) {
final DocFieldProcessorPerField perField = fields[i];
perField.consumer.processFields(perField.fields, perField.fieldCount);
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/FreqProxTermsWriter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/FreqProxTermsWriter.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/FreqProxTermsWriter.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/FreqProxTermsWriter.java Fri May 3 14:15:17 2013
@@ -54,7 +54,7 @@ final class FreqProxTermsWriter extends
final int numAllFields = allFields.size();
// Sort by field name
- CollectionUtil.quickSort(allFields);
+ CollectionUtil.introSort(allFields);
final FieldsConsumer consumer = state.segmentInfo.getCodec().postingsFormat().fieldsConsumer(state);
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/FrozenBufferedDeletes.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/FrozenBufferedDeletes.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/FrozenBufferedDeletes.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/FrozenBufferedDeletes.java Fri May 3 14:15:17 2013
@@ -56,7 +56,7 @@ class FrozenBufferedDeletes {
assert !isSegmentPrivate || deletes.terms.size() == 0 : "segment private package should only have del queries";
Term termsArray[] = deletes.terms.keySet().toArray(new Term[deletes.terms.size()]);
termCount = termsArray.length;
- ArrayUtil.mergeSort(termsArray);
+ ArrayUtil.timSort(termsArray);
PrefixCodedTerms.Builder builder = new PrefixCodedTerms.Builder();
for (Term term : termsArray) {
builder.add(term);
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/IndexFileDeleter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/IndexFileDeleter.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/IndexFileDeleter.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/IndexFileDeleter.java Fri May 3 14:15:17 2013
@@ -232,7 +232,7 @@ final class IndexFileDeleter implements
}
// We keep commits list in sorted order (oldest to newest):
- CollectionUtil.mergeSort(commits);
+ CollectionUtil.timSort(commits);
// Now delete anything with ref count at 0. These are
// presumably abandoned files eg due to crash of
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/ConjunctionScorer.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/ConjunctionScorer.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/ConjunctionScorer.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/ConjunctionScorer.java Fri May 3 14:15:17 2013
@@ -44,7 +44,7 @@ class ConjunctionScorer extends Scorer {
}
// Sort the array the first time to allow the least frequent DocsEnum to
// lead the matching.
- ArrayUtil.mergeSort(docsAndFreqs, new Comparator<DocsAndFreqs>() {
+ ArrayUtil.timSort(docsAndFreqs, new Comparator<DocsAndFreqs>() {
@Override
public int compare(DocsAndFreqs o1, DocsAndFreqs o2) {
return Long.signum(o1.cost - o2.cost);
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/MinShouldMatchSumScorer.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/MinShouldMatchSumScorer.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/MinShouldMatchSumScorer.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/MinShouldMatchSumScorer.java Fri May 3 14:15:17 2013
@@ -87,7 +87,7 @@ class MinShouldMatchSumScorer extends Sc
this.sortedSubScorers = subScorers.toArray(new Scorer[this.numScorers]);
// sorting by decreasing subscorer cost should be inversely correlated with
// next docid (assuming costs are due to generating many postings)
- ArrayUtil.mergeSort(sortedSubScorers, new Comparator<Scorer>() {
+ ArrayUtil.timSort(sortedSubScorers, new Comparator<Scorer>() {
@Override
public int compare(Scorer o1, Scorer o2) {
return Long.signum(o2.cost() - o1.cost());
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/MultiPhraseQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/MultiPhraseQuery.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/MultiPhraseQuery.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/MultiPhraseQuery.java Fri May 3 14:15:17 2013
@@ -241,7 +241,7 @@ public class MultiPhraseQuery extends Qu
// sort by increasing docFreq order
if (slop == 0) {
- ArrayUtil.mergeSort(postingsFreqs);
+ ArrayUtil.timSort(postingsFreqs);
}
if (slop == 0) {
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/PhraseQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/PhraseQuery.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/PhraseQuery.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/PhraseQuery.java Fri May 3 14:15:17 2013
@@ -278,7 +278,7 @@ public class PhraseQuery extends Query {
// sort by increasing docFreq order
if (slop == 0) {
- ArrayUtil.mergeSort(postingsFreqs);
+ ArrayUtil.timSort(postingsFreqs);
}
if (slop == 0) { // optimize exact case
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/TopTermsRewrite.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/TopTermsRewrite.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/TopTermsRewrite.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/TopTermsRewrite.java Fri May 3 14:15:17 2013
@@ -156,7 +156,7 @@ public abstract class TopTermsRewrite<Q
final Q q = getTopLevelQuery();
final ScoreTerm[] scoreTerms = stQueue.toArray(new ScoreTerm[stQueue.size()]);
- ArrayUtil.mergeSort(scoreTerms, scoreTermSortByTermComp);
+ ArrayUtil.timSort(scoreTerms, scoreTermSortByTermComp);
for (final ScoreTerm st : scoreTerms) {
final Term term = new Term(query.field, st.bytes);
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java Fri May 3 14:15:17 2013
@@ -204,7 +204,7 @@ public class NearSpansOrdered extends Sp
/** Advance the subSpans to the same document */
private boolean toSameDoc() throws IOException {
- ArrayUtil.mergeSort(subSpansByDoc, spanDocComparator);
+ ArrayUtil.timSort(subSpansByDoc, spanDocComparator);
int firstIndex = 0;
int maxDoc = subSpansByDoc[subSpansByDoc.length - 1].doc();
while (subSpansByDoc[firstIndex].doc() != maxDoc) {
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java Fri May 3 14:15:17 2013
@@ -28,11 +28,6 @@ import java.util.Comparator;
public final class ArrayUtil {
- // affordable memory overhead to merge sorted arrays
- static final float MERGE_OVERHEAD_RATIO = 0.01f;
- // arrays below this size will always be sorted in-place
- static final int MERGE_EXTRA_MEMORY_THRESHOLD = (int) (15 / MERGE_OVERHEAD_RATIO);
-
private ArrayUtil() {} // no instance
/*
@@ -610,237 +605,86 @@ public final class ArrayUtil {
return result;
}
- private static abstract class ArraySorterTemplate<T> extends SorterTemplate {
-
- protected final T[] a;
-
- ArraySorterTemplate(T[] a) {
- this.a = a;
- }
-
- protected abstract int compare(T a, T b);
-
- @Override
- protected void swap(int i, int j) {
- final T o = a[i];
- a[i] = a[j];
- a[j] = o;
- }
-
- @Override
- protected int compare(int i, int j) {
- return compare(a[i], a[j]);
- }
-
+ private static class NaturalComparator<T extends Comparable<? super T>> implements Comparator<T> {
+ NaturalComparator() {}
@Override
- protected void setPivot(int i) {
- pivot = a[i];
- }
-
- @Override
- protected int comparePivot(int j) {
- return compare(pivot, a[j]);
- }
-
- private T pivot;
-
- }
-
- // a template for merge-based sorts which uses extra memory to speed up merging
- private static abstract class ArrayMergeSorterTemplate<T> extends ArraySorterTemplate<T> {
-
- private final int threshold; // maximum length of a merge that can be made using extra memory
- private final T[] tmp;
-
- ArrayMergeSorterTemplate(T[] a, float overheadRatio) {
- super(a);
- this.threshold = (int) (a.length * overheadRatio);
- @SuppressWarnings("unchecked")
- final T[] tmpBuf = (T[]) new Object[threshold];
- this.tmp = tmpBuf;
- }
-
- private void mergeWithExtraMemory(int lo, int pivot, int hi, int len1, int len2) {
- System.arraycopy(a, lo, tmp, 0, len1);
- int i = 0, j = pivot, dest = lo;
- while (i < len1 && j < hi) {
- if (compare(tmp[i], a[j]) <= 0) {
- a[dest++] = tmp[i++];
- } else {
- a[dest++] = a[j++];
- }
- }
- while (i < len1) {
- a[dest++] = tmp[i++];
- }
- assert j == dest;
- }
-
- @Override
- protected void merge(int lo, int pivot, int hi, int len1, int len2) {
- if (len1 <= threshold) {
- mergeWithExtraMemory(lo, pivot, hi, len1, len2);
- } else {
- // since this method recurses to run merge on smaller arrays, it will
- // end up using mergeWithExtraMemory
- super.merge(lo, pivot, hi, len1, len2);
- }
+ public int compare(T o1, T o2) {
+ return o1.compareTo(o2);
}
-
- }
-
- /** SorterTemplate with custom {@link Comparator} */
- private static <T> SorterTemplate getSorter(final T[] a, final Comparator<? super T> comp) {
- return new ArraySorterTemplate<T>(a) {
-
- @Override
- protected int compare(T a, T b) {
- return comp.compare(a, b);
- }
-
- };
}
- /** Natural SorterTemplate */
- private static <T extends Comparable<? super T>> SorterTemplate getSorter(final T[] a) {
- return new ArraySorterTemplate<T>(a) {
-
- @Override
- protected int compare(T a, T b) {
- return a.compareTo(b);
- }
+ @SuppressWarnings("rawtypes")
+ private static final Comparator<?> NATURAL_COMPARATOR = new NaturalComparator();
- };
+ /** Get the natural {@link Comparator} for the provided object class. */
+ @SuppressWarnings("unchecked")
+ public static <T extends Comparable<? super T>> Comparator<T> naturalComparator() {
+ return (Comparator<T>) NATURAL_COMPARATOR;
}
- /** SorterTemplate with custom {@link Comparator} for merge-based sorts. */
- private static <T> SorterTemplate getMergeSorter(final T[] a, final Comparator<? super T> comp) {
- if (a.length < MERGE_EXTRA_MEMORY_THRESHOLD) {
- return getSorter(a, comp);
- } else {
- return new ArrayMergeSorterTemplate<T>(a, MERGE_OVERHEAD_RATIO) {
-
- @Override
- protected int compare(T a, T b) {
- return comp.compare(a, b);
- }
-
- };
- }
+ /** Swap values stored in slots <code>i</code> and <code>j</code> */
+ public static <T> void swap(T[] arr, int i, int j) {
+ final T tmp = arr[i];
+ arr[i] = arr[j];
+ arr[j] = tmp;
}
- /** Natural SorterTemplate for merge-based sorts. */
- private static <T extends Comparable<? super T>> SorterTemplate getMergeSorter(final T[] a) {
- if (a.length < MERGE_EXTRA_MEMORY_THRESHOLD) {
- return getSorter(a);
- } else {
- return new ArrayMergeSorterTemplate<T>(a, MERGE_OVERHEAD_RATIO) {
-
- @Override
- protected int compare(T a, T b) {
- return a.compareTo(b);
- }
-
- };
- }
- }
-
- // quickSorts (endindex is exclusive!):
+ // intro-sorts
/**
- * Sorts the given array slice using the {@link Comparator}. This method uses the quick sort
+ * Sorts the given array slice using the {@link Comparator}. This method uses the intro sort
* algorithm, but falls back to insertion sort for small arrays.
* @param fromIndex start index (inclusive)
* @param toIndex end index (exclusive)
*/
- public static <T> void quickSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
+ public static <T> void introSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
if (toIndex-fromIndex <= 1) return;
- getSorter(a, comp).quickSort(fromIndex, toIndex-1);
+ new ArrayIntroSorter<T>(a, comp).sort(fromIndex, toIndex);
}
/**
- * Sorts the given array using the {@link Comparator}. This method uses the quick sort
+ * Sorts the given array using the {@link Comparator}. This method uses the intro sort
* algorithm, but falls back to insertion sort for small arrays.
*/
- public static <T> void quickSort(T[] a, Comparator<? super T> comp) {
- quickSort(a, 0, a.length, comp);
+ public static <T> void introSort(T[] a, Comparator<? super T> comp) {
+ introSort(a, 0, a.length, comp);
}
/**
- * Sorts the given array slice in natural order. This method uses the quick sort
+ * Sorts the given array slice in natural order. This method uses the intro sort
* algorithm, but falls back to insertion sort for small arrays.
* @param fromIndex start index (inclusive)
* @param toIndex end index (exclusive)
*/
- public static <T extends Comparable<? super T>> void quickSort(T[] a, int fromIndex, int toIndex) {
+ public static <T extends Comparable<? super T>> void introSort(T[] a, int fromIndex, int toIndex) {
if (toIndex-fromIndex <= 1) return;
- getSorter(a).quickSort(fromIndex, toIndex-1);
+ final Comparator<T> comp = naturalComparator();
+ introSort(a, fromIndex, toIndex, comp);
}
/**
- * Sorts the given array in natural order. This method uses the quick sort
+ * Sorts the given array in natural order. This method uses the intro sort
* algorithm, but falls back to insertion sort for small arrays.
*/
- public static <T extends Comparable<? super T>> void quickSort(T[] a) {
- quickSort(a, 0, a.length);
+ public static <T extends Comparable<? super T>> void introSort(T[] a) {
+ introSort(a, 0, a.length);
}
- // mergeSorts:
+ // tim sorts:
/**
- * Sorts the given array slice using the {@link Comparator}. This method uses the merge sort
- * algorithm, but falls back to insertion sort for small arrays.
- * @param fromIndex start index (inclusive)
- * @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;
- //System.out.println("SORT: " + (toIndex-fromIndex));
- getMergeSorter(a, comp).mergeSort(fromIndex, toIndex-1);
- }
-
- /**
- * Sorts the given array using the {@link Comparator}. This method uses the merge sort
- * algorithm, but falls back to insertion sort for small arrays.
- */
- public static <T> void mergeSort(T[] a, Comparator<? super T> comp) {
- mergeSort(a, 0, a.length, comp);
- }
-
- /**
- * Sorts the given array slice in natural order. This method uses the merge sort
- * algorithm, but falls back to insertion sort for small arrays.
- * @param fromIndex start index (inclusive)
- * @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;
- getMergeSorter(a).mergeSort(fromIndex, toIndex-1);
- }
-
- /**
- * Sorts the given array in natural order. This method uses the merge sort
- * algorithm, but falls back to insertion sort for small arrays.
- */
- public static <T extends Comparable<? super T>> void mergeSort(T[] a) {
- mergeSort(a, 0, a.length);
- }
-
- // timSorts:
-
- /**
- * Sorts the given array slice using the {@link Comparator}. This method uses the TimSort
+ * Sorts the given array slice using the {@link Comparator}. This method uses the Tim sort
* algorithm, but falls back to binary sort for small arrays.
* @param fromIndex start index (inclusive)
* @param toIndex end index (exclusive)
*/
public static <T> void timSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
if (toIndex-fromIndex <= 1) return;
- getMergeSorter(a, comp).timSort(fromIndex, toIndex-1);
+ new ArrayTimSorter<T>(a, comp, a.length / 64).sort(fromIndex, toIndex);
}
/**
- * Sorts the given array using the {@link Comparator}. This method uses the TimSort
+ * Sorts the given array using the {@link Comparator}. This method uses the Tim sort
* algorithm, but falls back to binary sort for small arrays.
*/
public static <T> void timSort(T[] a, Comparator<? super T> comp) {
@@ -848,102 +692,23 @@ public final class ArrayUtil {
}
/**
- * Sorts the given array slice in natural order. This method uses the TimSort
+ * Sorts the given array slice in natural order. This method uses the Tim sort
* algorithm, but falls back to binary sort for small arrays.
* @param fromIndex start index (inclusive)
* @param toIndex end index (exclusive)
*/
public static <T extends Comparable<? super T>> void timSort(T[] a, int fromIndex, int toIndex) {
if (toIndex-fromIndex <= 1) return;
- getMergeSorter(a).timSort(fromIndex, toIndex-1);
+ final Comparator<T> comp = naturalComparator();
+ timSort(a, fromIndex, toIndex, comp);
}
/**
- * Sorts the given array in natural order. This method uses the TimSort
+ * Sorts the given array in natural order. This method uses the Tim sort
* algorithm, but falls back to binary sort for small arrays.
*/
public static <T extends Comparable<? super T>> void timSort(T[] a) {
timSort(a, 0, a.length);
}
- // insertionSorts:
-
- /**
- * Sorts the given array slice using the {@link Comparator}. This method uses the insertion sort
- * algorithm. It is only recommended to use this algorithm for partially sorted small arrays!
- * @param fromIndex start index (inclusive)
- * @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);
- }
-
- /**
- * Sorts the given array using the {@link Comparator}. This method uses the insertion sort
- * algorithm. It is only recommended to use this algorithm for partially sorted small arrays!
- */
- public static <T> void insertionSort(T[] a, Comparator<? super T> comp) {
- insertionSort(a, 0, a.length, comp);
- }
-
- /**
- * Sorts the given array slice in natural order. This method uses the insertion sort
- * algorithm. It is only recommended to use this algorithm for partially sorted small arrays!
- * @param fromIndex start index (inclusive)
- * @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);
- }
-
- /**
- * Sorts the given array in natural order. This method uses the insertion sort
- * algorithm. It is only recommended to use this algorithm for partially sorted small arrays!
- */
- public static <T extends Comparable<? super T>> void insertionSort(T[] a) {
- insertionSort(a, 0, a.length);
- }
-
- // binarySorts:
-
- /**
- * Sorts the given array slice using the {@link Comparator}. This method uses the binary sort
- * algorithm. It is only recommended to use this algorithm for small arrays!
- * @param fromIndex start index (inclusive)
- * @param toIndex end index (exclusive)
- */
- public static <T> void binarySort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
- if (toIndex-fromIndex <= 1) return;
- getSorter(a, comp).binarySort(fromIndex, toIndex-1);
- }
-
- /**
- * Sorts the given array using the {@link Comparator}. This method uses the binary sort
- * algorithm. It is only recommended to use this algorithm for small arrays!
- */
- public static <T> void binarySort(T[] a, Comparator<? super T> comp) {
- binarySort(a, 0, a.length, comp);
- }
-
- /**
- * Sorts the given array slice in natural order. This method uses the binary sort
- * algorithm. It is only recommended to use this algorithm for small arrays!
- * @param fromIndex start index (inclusive)
- * @param toIndex end index (exclusive)
- */
- public static <T extends Comparable<? super T>> void binarySort(T[] a, int fromIndex, int toIndex) {
- if (toIndex-fromIndex <= 1) return;
- getSorter(a).binarySort(fromIndex, toIndex-1);
- }
-
- /**
- * Sorts the given array in natural order. This method uses the binary sort
- * algorithm. It is only recommended to use this algorithm for small arrays!
- */
- public static <T extends Comparable<? super T>> void binarySort(T[] a) {
- binarySort(a, 0, a.length);
- }
-
-}
\ No newline at end of file
+}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/BytesRefHash.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/BytesRefHash.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/BytesRefHash.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/BytesRefHash.java Fri May 3 14:15:17 2013
@@ -163,7 +163,7 @@ public final class BytesRefHash {
*/
public int[] sort(final Comparator<BytesRef> comp) {
final int[] compact = compact();
- new SorterTemplate() {
+ new IntroSorter() {
@Override
protected void swap(int i, int j) {
final int o = compact[i];
@@ -197,7 +197,7 @@ public final class BytesRefHash {
private final BytesRef pivot = new BytesRef(),
scratch1 = new BytesRef(), scratch2 = new BytesRef();
- }.quickSort(0, count - 1);
+ }.sort(0, count);
return compact;
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java Fri May 3 14:15:17 2013
@@ -17,9 +17,6 @@ package org.apache.lucene.util;
* limitations under the License.
*/
-import static org.apache.lucene.util.ArrayUtil.MERGE_EXTRA_MEMORY_THRESHOLD;
-import static org.apache.lucene.util.ArrayUtil.MERGE_OVERHEAD_RATIO;
-
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
@@ -37,16 +34,24 @@ import java.util.RandomAccess;
public final class CollectionUtil {
private CollectionUtil() {} // no instance
+ private static final class ListIntroSorter<T> extends IntroSorter {
- private static abstract class ListSorterTemplate<T> extends SorterTemplate {
-
- protected final List<T> list;
-
- ListSorterTemplate(List<T> list) {
+ T pivot;
+ final List<T> list;
+ final Comparator<? super T> comp;
+
+ ListIntroSorter(List<T> list, Comparator<? super T> comp) {
+ super();
+ if (!(list instanceof RandomAccess))
+ throw new IllegalArgumentException("CollectionUtil can only sort random access lists in-place.");
this.list = list;
+ this.comp = comp;
}
- protected abstract int compare(T a, T b);
+ @Override
+ protected void setPivot(int i) {
+ pivot = list.get(i);
+ }
@Override
protected void swap(int i, int j) {
@@ -55,257 +60,120 @@ public final class CollectionUtil {
@Override
protected int compare(int i, int j) {
- return compare(list.get(i), list.get(j));
- }
-
- @Override
- protected void setPivot(int i) {
- pivot = list.get(i);
+ return comp.compare(list.get(i), list.get(j));
}
@Override
protected int comparePivot(int j) {
- return compare(pivot, list.get(j));
+ return comp.compare(pivot, list.get(j));
}
- private T pivot;
-
}
- // a template for merge-based sorts which uses extra memory to speed up merging
- private static abstract class ListMergeSorterTemplate<T> extends ListSorterTemplate<T> {
+ private static final class ListTimSorter<T> extends TimSorter {
- private final int threshold; // maximum length of a merge that can be made using extra memory
- private final T[] tmp;
+ final List<T> list;
+ final Comparator<? super T> comp;
+ final T[] tmp;
- ListMergeSorterTemplate(List<T> list, float overheadRatio) {
- super(list);
- this.threshold = (int) (list.size() * overheadRatio);
- @SuppressWarnings("unchecked")
- final T[] tmpBuf = (T[]) new Object[threshold];
- this.tmp = tmpBuf;
- }
-
- private void mergeWithExtraMemory(int lo, int pivot, int hi, int len1, int len2) {
- for (int i = 0; i < len1; ++i) {
- tmp[i] = list.get(lo + i);
- }
- int i = 0, j = pivot, dest = lo;
- while (i < len1 && j < hi) {
- if (compare(tmp[i], list.get(j)) <= 0) {
- list.set(dest++, tmp[i++]);
- } else {
- list.set(dest++, list.get(j++));
- }
- }
- while (i < len1) {
- list.set(dest++, tmp[i++]);
+ @SuppressWarnings("unchecked")
+ ListTimSorter(List<T> list, Comparator<? super T> comp, int maxTempSlots) {
+ super(maxTempSlots);
+ if (!(list instanceof RandomAccess))
+ throw new IllegalArgumentException("CollectionUtil can only sort random access lists in-place.");
+ this.list = list;
+ this.comp = comp;
+ if (maxTempSlots > 0) {
+ this.tmp = (T[]) new Object[maxTempSlots];
+ } else {
+ this.tmp = null;
}
- assert j == dest;
}
@Override
- protected void merge(int lo, int pivot, int hi, int len1, int len2) {
- if (len1 <= threshold) {
- mergeWithExtraMemory(lo, pivot, hi, len1, len2);
- } else {
- // since this method recurses to run merge on smaller arrays, it will
- // end up using mergeWithExtraMemory
- super.merge(lo, pivot, hi, len1, len2);
- }
+ protected void swap(int i, int j) {
+ Collections.swap(list, i, j);
}
- }
-
- /** SorterTemplate with custom {@link Comparator} */
- private static <T> SorterTemplate getSorter(final List<T> list, final Comparator<? super T> comp) {
- if (!(list instanceof RandomAccess))
- throw new IllegalArgumentException("CollectionUtil can only sort random access lists in-place.");
- return new ListSorterTemplate<T>(list) {
-
- @Override
- protected int compare(T a, T b) {
- return comp.compare(a, b);
- }
+ @Override
+ protected void copy(int src, int dest) {
+ list.set(dest, list.get(src));
+ }
- };
- }
-
- /** Natural SorterTemplate */
- private static <T extends Comparable<? super T>> SorterTemplate getSorter(final List<T> list) {
- if (!(list instanceof RandomAccess))
- throw new IllegalArgumentException("CollectionUtil can only sort random access lists in-place.");
- return new ListSorterTemplate<T>(list) {
-
- @Override
- protected int compare(T a, T b) {
- return a.compareTo(b);
+ @Override
+ protected void save(int i, int len) {
+ for (int j = 0; j < len; ++j) {
+ tmp[j] = list.get(i + j);
}
+ }
- };
- }
-
- /** SorterTemplate with custom {@link Comparator} for merge-based sorts. */
- private static <T> SorterTemplate getMergeSorter(final List<T> list, final Comparator<? super T> comp) {
- if (!(list instanceof RandomAccess))
- throw new IllegalArgumentException("CollectionUtil can only sort random access lists in-place.");
- if (list.size() < MERGE_EXTRA_MEMORY_THRESHOLD) {
- return getSorter(list, comp);
- } else {
- return new ListMergeSorterTemplate<T>(list, MERGE_OVERHEAD_RATIO) {
-
- @Override
- protected int compare(T a, T b) {
- return comp.compare(a, b);
- }
+ @Override
+ protected void restore(int i, int j) {
+ list.set(j, tmp[i]);
+ }
- };
+ @Override
+ protected int compare(int i, int j) {
+ return comp.compare(list.get(i), list.get(j));
}
- }
-
- /** Natural SorterTemplate for merge-based sorts. */
- private static <T extends Comparable<? super T>> SorterTemplate getMergeSorter(final List<T> list) {
- if (!(list instanceof RandomAccess))
- throw new IllegalArgumentException("CollectionUtil can only sort random access lists in-place.");
- if (list.size() < MERGE_EXTRA_MEMORY_THRESHOLD) {
- return getSorter(list);
- } else {
- return new ListMergeSorterTemplate<T>(list, MERGE_OVERHEAD_RATIO) {
-
- @Override
- protected int compare(T a, T b) {
- return a.compareTo(b);
- }
- };
+ @Override
+ protected int compareSaved(int i, int j) {
+ return comp.compare(tmp[i], list.get(j));
}
- }
- /**
- * Sorts the given random access {@link List} using the {@link Comparator}.
- * The list must implement {@link 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.
- */
- public static <T> void quickSort(List<T> list, Comparator<? super T> comp) {
- final int size = list.size();
- if (size <= 1) return;
- getSorter(list, comp).quickSort(0, size-1);
- }
-
- /**
- * Sorts the given random access {@link List} in natural order.
- * The list must implement {@link 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.
- */
- public static <T extends Comparable<? super T>> void quickSort(List<T> list) {
- final int size = list.size();
- if (size <= 1) return;
- getSorter(list).quickSort(0, size-1);
}
- // mergeSorts:
-
/**
* Sorts the given random access {@link List} using the {@link Comparator}.
- * The list must implement {@link RandomAccess}. This method uses the merge sort
+ * The list must implement {@link RandomAccess}. This method uses the intro sort
* algorithm, but falls back to insertion sort for small lists.
* @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) {
+ public static <T> void introSort(List<T> list, Comparator<? super T> comp) {
final int size = list.size();
if (size <= 1) return;
- getMergeSorter(list, comp).mergeSort(0, size-1);
+ new ListIntroSorter<T>(list, comp).sort(0, size);
}
/**
* Sorts the given random access {@link List} in natural order.
- * The list must implement {@link RandomAccess}. This method uses the merge sort
+ * The list must implement {@link RandomAccess}. This method uses the intro sort
* algorithm, but falls back to insertion sort for small lists.
* @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) {
+ public static <T extends Comparable<? super T>> void introSort(List<T> list) {
final int size = list.size();
if (size <= 1) return;
- getMergeSorter(list).mergeSort(0, size-1);
+ final Comparator<T> comp = ArrayUtil.naturalComparator();
+ introSort(list, comp);
}
- // timSorts:
+ // Tim sorts:
/**
* Sorts the given random access {@link List} using the {@link Comparator}.
- * The list must implement {@link RandomAccess}. This method uses the TimSort
+ * The list must implement {@link RandomAccess}. This method uses the Tim sort
* algorithm, but falls back to binary sort for small lists.
* @throws IllegalArgumentException if list is e.g. a linked list without random access.
*/
public static <T> void timSort(List<T> list, Comparator<? super T> comp) {
final int size = list.size();
if (size <= 1) return;
- getMergeSorter(list, comp).timSort(0, size-1);
+ new ListTimSorter<T>(list, comp, list.size() / 64).sort(0, size);
}
/**
* Sorts the given random access {@link List} in natural order.
- * The list must implement {@link RandomAccess}. This method uses the TimSort
+ * The list must implement {@link RandomAccess}. This method uses the Tim sort
* algorithm, but falls back to binary sort for small lists.
* @throws IllegalArgumentException if list is e.g. a linked list without random access.
*/
public static <T extends Comparable<? super T>> void timSort(List<T> list) {
final int size = list.size();
if (size <= 1) return;
- getMergeSorter(list).timSort(0, size-1);
+ final Comparator<T> comp = ArrayUtil.naturalComparator();
+ timSort(list, comp);
}
- // insertionSorts:
-
- /**
- * Sorts the given random access {@link List} using the {@link Comparator}.
- * The list must implement {@link 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.
- */
- public static <T> void insertionSort(List<T> list, Comparator<? super T> comp) {
- final int size = list.size();
- if (size <= 1) return;
- getSorter(list, comp).insertionSort(0, size-1);
- }
-
- /**
- * Sorts the given random access {@link List} in natural order.
- * The list must implement {@link 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.
- */
- public static <T extends Comparable<? super T>> void insertionSort(List<T> list) {
- final int size = list.size();
- if (size <= 1) return;
- getSorter(list).insertionSort(0, size-1);
- }
-
- // binarySorts:
-
- /**
- * Sorts the given random access {@link List} using the {@link Comparator}.
- * The list must implement {@link RandomAccess}. This method uses the binary sort
- * algorithm. It is only recommended to use this algorithm for small lists!
- * @throws IllegalArgumentException if list is e.g. a linked list without random access.
- */
- public static <T> void binarySort(List<T> list, Comparator<? super T> comp) {
- final int size = list.size();
- if (size <= 1) return;
- getSorter(list, comp).binarySort(0, size-1);
- }
-
- /**
- * Sorts the given random access {@link List} in natural order.
- * The list must implement {@link RandomAccess}. This method uses the insertion sort
- * algorithm. It is only recommended to use this algorithm for small lists!
- * @throws IllegalArgumentException if list is e.g. a linked list without random access.
- */
- public static <T extends Comparable<? super T>> void binarySort(List<T> list) {
- final int size = list.size();
- if (size <= 1) return;
- getSorter(list).binarySort(0, size-1);
- }
-}
\ No newline at end of file
+}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/automaton/BasicOperations.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/automaton/BasicOperations.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/automaton/BasicOperations.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/automaton/BasicOperations.java Fri May 3 14:15:17 2013
@@ -557,8 +557,8 @@ final public class BasicOperations {
}
public void sort() {
- // mergesort seems to perform better on already sorted arrays:
- if (count > 1) ArrayUtil.mergeSort(points, 0, count);
+ // Tim sort performs well on already sorted arrays:
+ if (count > 1) ArrayUtil.timSort(points, 0, count);
}
public void add(Transition t) {
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/automaton/State.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/automaton/State.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/automaton/State.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/automaton/State.java Fri May 3 14:15:17 2013
@@ -239,7 +239,7 @@ public class State implements Comparable
/** Sorts transitions array in-place. */
public void sortTransitions(Comparator<Transition> comparator) {
// mergesort seems to perform better on already sorted arrays:
- if (numTransitions > 1) ArrayUtil.mergeSort(transitionsArray, 0, numTransitions, comparator);
+ if (numTransitions > 1) ArrayUtil.timSort(transitionsArray, 0, numTransitions, comparator);
}
/**
Modified: lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestArrayUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestArrayUtil.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestArrayUtil.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestArrayUtil.java Fri May 3 14:15:17 2013
@@ -128,21 +128,21 @@ public class TestArrayUtil extends Lucen
return a;
}
- public void testQuickSort() {
+ public void testIntroSort() {
int num = atLeast(50);
for (int i = 0; i < num; i++) {
Integer[] a1 = createRandomArray(2000), a2 = a1.clone();
- ArrayUtil.quickSort(a1);
+ ArrayUtil.introSort(a1);
Arrays.sort(a2);
assertArrayEquals(a2, a1);
a1 = createRandomArray(2000);
a2 = a1.clone();
- ArrayUtil.quickSort(a1, Collections.reverseOrder());
+ ArrayUtil.introSort(a1, Collections.reverseOrder());
Arrays.sort(a2, Collections.reverseOrder());
assertArrayEquals(a2, a1);
// reverse back, so we can test that completely backwards sorted array (worst case) is working:
- ArrayUtil.quickSort(a1);
+ ArrayUtil.introSort(a1);
Arrays.sort(a2);
assertArrayEquals(a2, a1);
}
@@ -158,38 +158,18 @@ public class TestArrayUtil extends Lucen
}
// This is a test for LUCENE-3054 (which fails without the merge sort fall back with stack overflow in most cases)
- public void testQuickToMergeSortFallback() {
+ public void testQuickToHeapSortFallback() {
int num = atLeast(50);
for (int i = 0; i < num; i++) {
Integer[] a1 = createSparseRandomArray(40000), a2 = a1.clone();
- ArrayUtil.quickSort(a1);
+ ArrayUtil.introSort(a1);
Arrays.sort(a2);
assertArrayEquals(a2, a1);
}
}
- public void testMergeSort() {
- int num = atLeast(50);
- for (int i = 0; i < num; i++) {
- Integer[] a1 = createRandomArray(2000), a2 = a1.clone();
- ArrayUtil.mergeSort(a1);
- Arrays.sort(a2);
- assertArrayEquals(a2, a1);
-
- a1 = createRandomArray(2000);
- a2 = a1.clone();
- ArrayUtil.mergeSort(a1, Collections.reverseOrder());
- Arrays.sort(a2, Collections.reverseOrder());
- assertArrayEquals(a2, a1);
- // reverse back, so we can test that completely backwards sorted array (worst case) is working:
- ArrayUtil.mergeSort(a1);
- Arrays.sort(a2);
- assertArrayEquals(a2, a1);
- }
- }
-
public void testTimSort() {
- int num = atLeast(65);
+ int num = atLeast(50);
for (int i = 0; i < num; i++) {
Integer[] a1 = createRandomArray(2000), a2 = a1.clone();
ArrayUtil.timSort(a1);
@@ -207,44 +187,6 @@ public class TestArrayUtil extends Lucen
assertArrayEquals(a2, a1);
}
}
-
- public void testInsertionSort() {
- for (int i = 0, c = atLeast(500); i < c; i++) {
- Integer[] a1 = createRandomArray(30), a2 = a1.clone();
- ArrayUtil.insertionSort(a1);
- Arrays.sort(a2);
- assertArrayEquals(a2, a1);
-
- a1 = createRandomArray(30);
- a2 = a1.clone();
- ArrayUtil.insertionSort(a1, Collections.reverseOrder());
- Arrays.sort(a2, Collections.reverseOrder());
- assertArrayEquals(a2, a1);
- // reverse back, so we can test that completely backwards sorted array (worst case) is working:
- ArrayUtil.insertionSort(a1);
- Arrays.sort(a2);
- assertArrayEquals(a2, a1);
- }
- }
-
- public void testBinarySort() {
- for (int i = 0, c = atLeast(500); i < c; i++) {
- Integer[] a1 = createRandomArray(30), a2 = a1.clone();
- ArrayUtil.binarySort(a1);
- Arrays.sort(a2);
- assertArrayEquals(a2, a1);
-
- a1 = createRandomArray(30);
- a2 = a1.clone();
- ArrayUtil.binarySort(a1, Collections.reverseOrder());
- Arrays.sort(a2, Collections.reverseOrder());
- assertArrayEquals(a2, a1);
- // reverse back, so we can test that completely backwards sorted array (worst case) is working:
- ArrayUtil.binarySort(a1);
- Arrays.sort(a2);
- assertArrayEquals(a2, a1);
- }
- }
static class Item implements Comparable<Item> {
final int val, order;
@@ -279,7 +221,7 @@ public class TestArrayUtil extends Lucen
if (VERBOSE) System.out.println("Before: " + Arrays.toString(items));
// if you replace this with ArrayUtil.quickSort(), test should fail:
- ArrayUtil.mergeSort(items);
+ ArrayUtil.timSort(items);
if (VERBOSE) System.out.println("Sorted: " + Arrays.toString(items));
Item last = items[0];
@@ -326,16 +268,10 @@ public class TestArrayUtil extends Lucen
// should produce no exceptions
public void testEmptyArraySort() {
Integer[] a = new Integer[0];
- ArrayUtil.quickSort(a);
- ArrayUtil.mergeSort(a);
- ArrayUtil.insertionSort(a);
- ArrayUtil.binarySort(a);
+ ArrayUtil.introSort(a);
ArrayUtil.timSort(a);
- ArrayUtil.quickSort(a, Collections.reverseOrder());
- ArrayUtil.mergeSort(a, Collections.reverseOrder());
+ ArrayUtil.introSort(a, Collections.reverseOrder());
ArrayUtil.timSort(a, Collections.reverseOrder());
- ArrayUtil.insertionSort(a, Collections.reverseOrder());
- ArrayUtil.binarySort(a, Collections.reverseOrder());
}
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestCollectionUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestCollectionUtil.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestCollectionUtil.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/TestCollectionUtil.java Fri May 3 14:15:17 2013
@@ -35,39 +35,20 @@ public class TestCollectionUtil extends
return Arrays.asList(a);
}
- public void testQuickSort() {
+ public void testIntroSort() {
for (int i = 0, c = atLeast(500); i < c; i++) {
List<Integer> list1 = createRandomList(2000), list2 = new ArrayList<Integer>(list1);
- CollectionUtil.quickSort(list1);
+ CollectionUtil.introSort(list1);
Collections.sort(list2);
assertEquals(list2, list1);
list1 = createRandomList(2000);
list2 = new ArrayList<Integer>(list1);
- CollectionUtil.quickSort(list1, Collections.reverseOrder());
+ CollectionUtil.introSort(list1, Collections.reverseOrder());
Collections.sort(list2, Collections.reverseOrder());
assertEquals(list2, list1);
// reverse back, so we can test that completely backwards sorted array (worst case) is working:
- CollectionUtil.quickSort(list1);
- Collections.sort(list2);
- assertEquals(list2, list1);
- }
- }
-
- public void testMergeSort() {
- for (int i = 0, c = atLeast(500); i < c; i++) {
- List<Integer> list1 = createRandomList(2000), list2 = new ArrayList<Integer>(list1);
- CollectionUtil.mergeSort(list1);
- Collections.sort(list2);
- assertEquals(list2, list1);
-
- list1 = createRandomList(2000);
- list2 = new ArrayList<Integer>(list1);
- CollectionUtil.mergeSort(list1, Collections.reverseOrder());
- Collections.sort(list2, Collections.reverseOrder());
- assertEquals(list2, list1);
- // reverse back, so we can test that completely backwards sorted array (worst case) is working:
- CollectionUtil.mergeSort(list1);
+ CollectionUtil.introSort(list1);
Collections.sort(list2);
assertEquals(list2, list1);
}
@@ -92,86 +73,30 @@ public class TestCollectionUtil extends
}
}
- public void testInsertionSort() {
- for (int i = 0, c = atLeast(500); i < c; i++) {
- List<Integer> list1 = createRandomList(30), list2 = new ArrayList<Integer>(list1);
- CollectionUtil.insertionSort(list1);
- Collections.sort(list2);
- assertEquals(list2, list1);
-
- list1 = createRandomList(30);
- list2 = new ArrayList<Integer>(list1);
- CollectionUtil.insertionSort(list1, Collections.reverseOrder());
- Collections.sort(list2, Collections.reverseOrder());
- assertEquals(list2, list1);
- // reverse back, so we can test that completely backwards sorted array (worst case) is working:
- CollectionUtil.insertionSort(list1);
- Collections.sort(list2);
- assertEquals(list2, list1);
- }
- }
-
- public void testBinarySort() {
- for (int i = 0, c = atLeast(500); i < c; i++) {
- List<Integer> list1 = createRandomList(30), list2 = new ArrayList<Integer>(list1);
- CollectionUtil.binarySort(list1);
- Collections.sort(list2);
- assertEquals(list2, list1);
-
- list1 = createRandomList(30);
- list2 = new ArrayList<Integer>(list1);
- CollectionUtil.binarySort(list1, Collections.reverseOrder());
- Collections.sort(list2, Collections.reverseOrder());
- assertEquals(list2, list1);
- // reverse back, so we can test that completely backwards sorted array (worst case) is working:
- CollectionUtil.binarySort(list1);
- Collections.sort(list2);
- assertEquals(list2, list1);
- }
- }
-
public void testEmptyListSort() {
// should produce no exceptions
List<Integer> list = Arrays.asList(new Integer[0]); // LUCENE-2989
- CollectionUtil.quickSort(list);
- CollectionUtil.mergeSort(list);
+ CollectionUtil.introSort(list);
CollectionUtil.timSort(list);
- CollectionUtil.insertionSort(list);
- CollectionUtil.binarySort(list);
- CollectionUtil.quickSort(list, Collections.reverseOrder());
- CollectionUtil.mergeSort(list, Collections.reverseOrder());
+ CollectionUtil.introSort(list, Collections.reverseOrder());
CollectionUtil.timSort(list, Collections.reverseOrder());
- CollectionUtil.insertionSort(list, Collections.reverseOrder());
- CollectionUtil.binarySort(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.introSort(list);
CollectionUtil.timSort(list);
- CollectionUtil.insertionSort(list);
- CollectionUtil.binarySort(list);
- CollectionUtil.quickSort(list, Collections.reverseOrder());
- CollectionUtil.mergeSort(list, Collections.reverseOrder());
+ CollectionUtil.introSort(list, Collections.reverseOrder());
CollectionUtil.timSort(list, Collections.reverseOrder());
- CollectionUtil.insertionSort(list, Collections.reverseOrder());
- CollectionUtil.binarySort(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.introSort(list);
CollectionUtil.timSort(list);
- CollectionUtil.insertionSort(list);
- CollectionUtil.binarySort(list);
- CollectionUtil.quickSort(list, Collections.reverseOrder());
- CollectionUtil.mergeSort(list, Collections.reverseOrder());
+ CollectionUtil.introSort(list, Collections.reverseOrder());
CollectionUtil.timSort(list, Collections.reverseOrder());
- CollectionUtil.insertionSort(list, Collections.reverseOrder());
- CollectionUtil.binarySort(list, Collections.reverseOrder());
}
}
Modified: lucene/dev/branches/branch_4x/lucene/facet/src/test/org/apache/lucene/facet/search/TestDrillSideways.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/facet/src/test/org/apache/lucene/facet/search/TestDrillSideways.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/facet/src/test/org/apache/lucene/facet/search/TestDrillSideways.java (original)
+++ lucene/dev/branches/branch_4x/lucene/facet/src/test/org/apache/lucene/facet/search/TestDrillSideways.java Fri May 3 14:15:17 2013
@@ -65,8 +65,8 @@ import org.apache.lucene.store.Directory
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.InPlaceMergeSorter;
import org.apache.lucene.util.InfoStream;
-import org.apache.lucene.util.SorterTemplate;
import org.apache.lucene.util._TestUtil;
public class TestDrillSideways extends FacetTestCase {
@@ -875,9 +875,7 @@ public class TestDrillSideways extends F
// Naive (on purpose, to reduce bug in tester/gold):
// sort all ids, then return top N slice:
- new SorterTemplate() {
-
- private int pivot;
+ new InPlaceMergeSorter() {
@Override
protected void swap(int i, int j) {
@@ -901,26 +899,7 @@ public class TestDrillSideways extends F
}
}
- @Override
- protected void setPivot(int i) {
- pivot = ids[i];
- }
-
- @Override
- protected int comparePivot(int j) {
- int counti = counts[pivot];
- int countj = counts[ids[j]];
- // Sort by count descending...
- if (counti > countj) {
- return -1;
- } else if (counti < countj) {
- return 1;
- } else {
- // ... then by ord ascending:
- return new BytesRef(values[pivot]).compareTo(new BytesRef(values[ids[j]]));
- }
- }
- }.mergeSort(0, ids.length-1);
+ }.sort(0, ids.length);
if (topN > ids.length) {
topN = ids.length;
Modified: lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java (original)
+++ lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java Fri May 3 14:15:17 2013
@@ -252,7 +252,7 @@ public class TokenSources {
if (unsortedTokens != null) {
tokensInOriginalOrder = unsortedTokens.toArray(new Token[unsortedTokens
.size()]);
- ArrayUtil.mergeSort(tokensInOriginalOrder, new Comparator<Token>() {
+ ArrayUtil.timSort(tokensInOriginalOrder, new Comparator<Token>() {
@Override
public int compare(Token t1, Token t2) {
if (t1.startOffset() == t2.startOffset()) return t1.endOffset()
Modified: lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenStreamFromTermPositionVector.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenStreamFromTermPositionVector.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenStreamFromTermPositionVector.java (original)
+++ lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenStreamFromTermPositionVector.java Fri May 3 14:15:17 2013
@@ -86,7 +86,7 @@ public final class TokenStreamFromTermPo
this.positionedTokens.add(token);
}
}
- CollectionUtil.mergeSort(this.positionedTokens, tokenComparator);
+ CollectionUtil.timSort(this.positionedTokens, tokenComparator);
int lastPosition = -1;
for (final Token token : this.positionedTokens) {
int thisPosition = token.getPositionIncrement();
Modified: lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/Passage.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/Passage.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/Passage.java (original)
+++ lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/Passage.java Fri May 3 14:15:17 2013
@@ -19,8 +19,8 @@ package org.apache.lucene.search.posting
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.InPlaceMergeSorter;
import org.apache.lucene.util.RamUsageEstimator;
-import org.apache.lucene.util.SorterTemplate;
/**
* Represents a passage (typically a sentence of the document).
@@ -64,7 +64,7 @@ public final class Passage {
final int starts[] = matchStarts;
final int ends[] = matchEnds;
final BytesRef terms[] = matchTerms;
- new SorterTemplate() {
+ new InPlaceMergeSorter() {
@Override
protected void swap(int i, int j) {
int temp = starts[i];
@@ -86,19 +86,7 @@ public final class Passage {
return Long.signum(((long)starts[i]) - starts[j]);
}
- @Override
- protected void setPivot(int i) {
- pivot = starts[i];
- }
-
- @Override
- protected int comparePivot(int j) {
- // TODO: java7 use Integer.compare(pivot, starts[j])
- return Long.signum(((long)pivot) - starts[j]);
- }
-
- int pivot;
- }.mergeSort(0, numMatches-1);
+ }.sort(0, numMatches);
}
void reset() {
Modified: lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/PostingsHighlighter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/PostingsHighlighter.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/PostingsHighlighter.java (original)
+++ lucene/dev/branches/branch_4x/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/PostingsHighlighter.java Fri May 3 14:15:17 2013
@@ -48,7 +48,7 @@ import org.apache.lucene.search.Query;
import org.apache.lucene.search.ScoreDoc;
import org.apache.lucene.search.TopDocs;
import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.SorterTemplate;
+import org.apache.lucene.util.InPlaceMergeSorter;
import org.apache.lucene.util.UnicodeUtil;
/**
@@ -313,9 +313,8 @@ public class PostingsHighlighter {
// sort for sequential io
Arrays.sort(docids);
- new SorterTemplate() {
- String pivot;
-
+ new InPlaceMergeSorter() {
+
@Override
protected void swap(int i, int j) {
String tmp = fields[i];
@@ -330,18 +329,8 @@ public class PostingsHighlighter {
protected int compare(int i, int j) {
return fields[i].compareTo(fields[j]);
}
-
- @Override
- protected void setPivot(int i) {
- pivot = fields[i];
- }
-
- @Override
- protected int comparePivot(int j) {
- return pivot.compareTo(fields[j]);
- }
- }.mergeSort(0, fields.length-1);
+ }.sort(0, fields.length);
// pull stored data:
String[][] contents = loadFieldValues(searcher, fields, docids, maxLength);
Modified: lucene/dev/branches/branch_4x/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java (original)
+++ lucene/dev/branches/branch_4x/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java Fri May 3 14:15:17 2013
@@ -572,7 +572,7 @@ public class MemoryIndex {
entries[i] = iter.next();
}
- if (size > 1) ArrayUtil.quickSort(entries, termComparator);
+ if (size > 1) ArrayUtil.introSort(entries, termComparator);
return entries;
}
Modified: lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/CompoundFileExtractor.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/CompoundFileExtractor.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/CompoundFileExtractor.java (original)
+++ lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/CompoundFileExtractor.java Fri May 3 14:15:17 2013
@@ -87,7 +87,7 @@ public class CompoundFileExtractor {
cfr = new CompoundFileDirectory(dir, filename, IOContext.DEFAULT, false);
String [] files = cfr.listAll();
- ArrayUtil.mergeSort(files); // sort the array of filename so that the output is more readable
+ ArrayUtil.timSort(files); // sort the array of filename so that the output is more readable
for (int i = 0; i < files.length; ++i) {
long len = cfr.fileLength(files[i]);
Modified: lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/sorter/Sorter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/sorter/Sorter.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/sorter/Sorter.java (original)
+++ lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/sorter/Sorter.java Fri May 3 14:15:17 2013
@@ -22,7 +22,7 @@ import java.util.Comparator;
import org.apache.lucene.index.AtomicReader;
import org.apache.lucene.index.IndexReader;
-import org.apache.lucene.util.SorterTemplate;
+import org.apache.lucene.util.TimSorter;
import org.apache.lucene.util.packed.MonotonicAppendingLongBuffer;
/**
@@ -113,16 +113,17 @@ public abstract class Sorter {
}
};
- private static final class DocValueSorterTemplate extends SorterTemplate {
+ private static final class DocValueSorter extends TimSorter {
private final int[] docs;
private final Sorter.DocComparator comparator;
+ private final int[] tmp;
- private int pivot;
-
- public DocValueSorterTemplate(int[] docs, Sorter.DocComparator comparator) {
+ public DocValueSorter(int[] docs, Sorter.DocComparator comparator) {
+ super(docs.length / 64);
this.docs = docs;
this.comparator = comparator;
+ tmp = new int[docs.length / 64];
}
@Override
@@ -131,21 +132,31 @@ public abstract class Sorter {
}
@Override
- protected int comparePivot(int j) {
- return comparator.compare(pivot, docs[j]);
- }
-
- @Override
- protected void setPivot(int i) {
- pivot = docs[i];
- }
-
- @Override
protected void swap(int i, int j) {
int tmpDoc = docs[i];
docs[i] = docs[j];
docs[j] = tmpDoc;
}
+
+ @Override
+ protected void copy(int src, int dest) {
+ docs[dest] = docs[src];
+ }
+
+ @Override
+ protected void save(int i, int len) {
+ System.arraycopy(docs, i, tmp, 0, len);
+ }
+
+ @Override
+ protected void restore(int i, int j) {
+ docs[j] = tmp[i];
+ }
+
+ @Override
+ protected int compareSaved(int i, int j) {
+ return comparator.compare(tmp[i], docs[j]);
+ }
}
/** Computes the old-to-new permutation over the given comparator. */
@@ -168,10 +179,10 @@ public abstract class Sorter {
docs[i] = i;
}
- SorterTemplate sorter = new DocValueSorterTemplate(docs, comparator);
+ DocValueSorter sorter = new DocValueSorter(docs, comparator);
// It can be common to sort a reader, add docs, sort it again, ... and in
// that case timSort can save a lot of time
- sorter.timSort(0, docs.length - 1); // docs is now the newToOld mapping
+ sorter.sort(0, docs.length); // docs is now the newToOld mapping
// The reason why we use MonotonicAppendingLongBuffer here is that it
// wastes very little memory if the index is in random order but can save
Modified: lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java (original)
+++ lucene/dev/branches/branch_4x/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java Fri May 3 14:15:17 2013
@@ -43,7 +43,7 @@ import org.apache.lucene.store.RAMOutput
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.SorterTemplate;
+import org.apache.lucene.util.TimSorter;
import org.apache.lucene.util.automaton.CompiledAutomaton;
/**
@@ -157,7 +157,7 @@ public class SortingAtomicReader extends
final DocsEnum inDocs = in.docs(newToOld(liveDocs), inReuse, flags);
final boolean withFreqs = indexOptions.compareTo(IndexOptions.DOCS_AND_FREQS) >=0 && (flags & DocsEnum.FLAG_FREQS) != 0;
- return new SortingDocsEnum(wrapReuse, inDocs, withFreqs, docMap);
+ return new SortingDocsEnum(docMap.size(), wrapReuse, inDocs, withFreqs, docMap);
}
@Override
@@ -184,7 +184,7 @@ public class SortingAtomicReader extends
// ask for everything. if that assumption changes in the future, we can
// factor in whether 'flags' says offsets are not required.
final boolean storeOffsets = indexOptions.compareTo(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS_AND_OFFSETS) >= 0;
- return new SortingDocsAndPositionsEnum(wrapReuse, inDocsAndPositions, docMap, storeOffsets);
+ return new SortingDocsAndPositionsEnum(docMap.size(), wrapReuse, inDocsAndPositions, docMap, storeOffsets);
}
}
@@ -295,34 +295,32 @@ public class SortingAtomicReader extends
static class SortingDocsEnum extends FilterDocsEnum {
- private static final class DocFreqSorterTemplate extends SorterTemplate {
+ private static final class DocFreqSorter extends TimSorter {
- private final int[] docs;
- private final int[] freqs;
+ private int[] docs;
+ private int[] freqs;
+ private final int[] tmpDocs;
+ private int[] tmpFreqs;
- private int pivot;
-
- public DocFreqSorterTemplate(int[] docs, int[] freqs) {
+ public DocFreqSorter(int maxDoc) {
+ super(maxDoc / 64);
+ this.tmpDocs = new int[maxDoc / 64];
+ }
+
+ public void reset(int[] docs, int[] freqs) {
this.docs = docs;
this.freqs = freqs;
+ if (freqs != null && tmpFreqs == null) {
+ tmpFreqs = new int[tmpDocs.length];
+ }
}
-
+
@Override
protected int compare(int i, int j) {
return docs[i] - docs[j];
}
@Override
- protected int comparePivot(int j) {
- return pivot - docs[j];
- }
-
- @Override
- protected void setPivot(int i) {
- pivot = docs[i];
- }
-
- @Override
protected void swap(int i, int j) {
int tmpDoc = docs[i];
docs[i] = docs[j];
@@ -334,22 +332,60 @@ public class SortingAtomicReader extends
freqs[j] = tmpFreq;
}
}
+
+ @Override
+ protected void copy(int src, int dest) {
+ docs[dest] = docs[src];
+ if (freqs != null) {
+ freqs[dest] = freqs[src];
+ }
+ }
+
+ @Override
+ protected void save(int i, int len) {
+ System.arraycopy(docs, i, tmpDocs, 0, len);
+ if (freqs != null) {
+ System.arraycopy(freqs, i, tmpFreqs, 0, len);
+ }
+ }
+
+ @Override
+ protected void restore(int i, int j) {
+ docs[j] = tmpDocs[i];
+ if (freqs != null) {
+ freqs[j] = tmpFreqs[i];
+ }
+ }
+
+ @Override
+ protected int compareSaved(int i, int j) {
+ return tmpDocs[i] - docs[j];
+ }
}
-
+
+ private final int maxDoc;
+ private final DocFreqSorter sorter;
private int[] docs;
private int[] freqs;
private int docIt = -1;
private final int upto;
private final boolean withFreqs;
- SortingDocsEnum(SortingDocsEnum reuse, final DocsEnum in, boolean withFreqs, final Sorter.DocMap docMap) throws IOException {
+ SortingDocsEnum(int maxDoc, SortingDocsEnum reuse, final DocsEnum in, boolean withFreqs, final Sorter.DocMap docMap) throws IOException {
super(in);
+ this.maxDoc = maxDoc;
this.withFreqs = withFreqs;
if (reuse != null) {
+ if (reuse.maxDoc == maxDoc) {
+ sorter = reuse.sorter;
+ } else {
+ sorter = new DocFreqSorter(maxDoc);
+ }
docs = reuse.docs;
freqs = reuse.freqs; // maybe null
} else {
docs = new int[64];
+ sorter = new DocFreqSorter(maxDoc);
}
docIt = -1;
int i = 0;
@@ -378,7 +414,8 @@ public class SortingAtomicReader extends
}
// TimSort can save much time compared to other sorts in case of
// reverse sorting, or when sorting a concatenation of sorted readers
- new DocFreqSorterTemplate(docs, freqs).timSort(0, i - 1);
+ sorter.reset(docs, freqs);
+ sorter.sort(0, i);
upto = i;
}
@@ -422,38 +459,34 @@ public class SortingAtomicReader extends
static class SortingDocsAndPositionsEnum extends FilterDocsAndPositionsEnum {
/**
- * A {@link SorterTemplate} which sorts two parallel arrays of doc IDs and
+ * A {@link Sorter} which sorts two parallel arrays of doc IDs and
* offsets in one go. Everytime a doc ID is 'swapped', its correponding offset
* is swapped too.
*/
- private static final class DocOffsetSorterTemplate extends SorterTemplate {
+ private static final class DocOffsetSorter extends TimSorter {
- private final int[] docs;
- private final long[] offsets;
+ private int[] docs;
+ private long[] offsets;
+ private final int[] tmpDocs;
+ private final long[] tmpOffsets;
- private int pivot;
-
- public DocOffsetSorterTemplate(int[] docs, long[] offsets) {
+ public DocOffsetSorter(int maxDoc) {
+ super(maxDoc / 64);
+ this.tmpDocs = new int[maxDoc / 64];
+ this.tmpOffsets = new long[maxDoc / 64];
+ }
+
+ public void reset(int[] docs, long[] offsets) {
this.docs = docs;
this.offsets = offsets;
}
-
+
@Override
protected int compare(int i, int j) {
return docs[i] - docs[j];
}
@Override
- protected int comparePivot(int j) {
- return pivot - docs[j];
- }
-
- @Override
- protected void setPivot(int i) {
- pivot = docs[i];
- }
-
- @Override
protected void swap(int i, int j) {
int tmpDoc = docs[i];
docs[i] = docs[j];
@@ -463,8 +496,33 @@ public class SortingAtomicReader extends
offsets[i] = offsets[j];
offsets[j] = tmpOffset;
}
+
+ @Override
+ protected void copy(int src, int dest) {
+ docs[dest] = docs[src];
+ offsets[dest] = offsets[src];
+ }
+
+ @Override
+ protected void save(int i, int len) {
+ System.arraycopy(docs, i, tmpDocs, 0, len);
+ System.arraycopy(offsets, i, tmpOffsets, 0, len);
+ }
+
+ @Override
+ protected void restore(int i, int j) {
+ docs[j] = tmpDocs[i];
+ offsets[j] = tmpOffsets[i];
+ }
+
+ @Override
+ protected int compareSaved(int i, int j) {
+ return tmpDocs[i] - docs[j];
+ }
}
+ private final int maxDoc;
+ private final DocOffsetSorter sorter;
private int[] docs;
private long[] offsets;
private final int upto;
@@ -481,19 +539,26 @@ public class SortingAtomicReader extends
private final RAMFile file;
- SortingDocsAndPositionsEnum(SortingDocsAndPositionsEnum reuse, final DocsAndPositionsEnum in, Sorter.DocMap docMap, boolean storeOffsets) throws IOException {
+ SortingDocsAndPositionsEnum(int maxDoc, SortingDocsAndPositionsEnum reuse, final DocsAndPositionsEnum in, Sorter.DocMap docMap, boolean storeOffsets) throws IOException {
super(in);
+ this.maxDoc = maxDoc;
this.storeOffsets = storeOffsets;
if (reuse != null) {
docs = reuse.docs;
offsets = reuse.offsets;
payload = reuse.payload;
file = reuse.file;
+ if (reuse.maxDoc == maxDoc) {
+ sorter = reuse.sorter;
+ } else {
+ sorter = new DocOffsetSorter(maxDoc);
+ }
} else {
docs = new int[32];
offsets = new long[32];
payload = new BytesRef(32);
file = new RAMFile();
+ sorter = new DocOffsetSorter(maxDoc);
}
final IndexOutput out = new RAMOutputStream(file);
int doc;
@@ -510,7 +575,8 @@ public class SortingAtomicReader extends
i++;
}
upto = i;
- new DocOffsetSorterTemplate(docs, offsets).timSort(0, upto - 1);
+ sorter.reset(docs, offsets);
+ sorter.sort(0, upto);
out.close();
this.postingInput = new RAMInputStream("", file);
}
Modified: lucene/dev/branches/branch_4x/lucene/suggest/src/java/org/apache/lucene/search/spell/DirectSpellChecker.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/suggest/src/java/org/apache/lucene/search/spell/DirectSpellChecker.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/suggest/src/java/org/apache/lucene/search/spell/DirectSpellChecker.java (original)
+++ lucene/dev/branches/branch_4x/lucene/suggest/src/java/org/apache/lucene/search/spell/DirectSpellChecker.java Fri May 3 14:15:17 2013
@@ -376,7 +376,7 @@ public class DirectSpellChecker {
suggestions[index--] = suggestion;
}
- ArrayUtil.mergeSort(suggestions, Collections.reverseOrder(comparator));
+ ArrayUtil.timSort(suggestions, Collections.reverseOrder(comparator));
if (numSug < suggestions.length) {
SuggestWord trimmed[] = new SuggestWord[numSug];
System.arraycopy(suggestions, 0, trimmed, 0, numSug);
Modified: lucene/dev/branches/branch_4x/lucene/suggest/src/java/org/apache/lucene/search/suggest/BytesRefArray.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/suggest/src/java/org/apache/lucene/search/suggest/BytesRefArray.java?rev=1478802&r1=1478801&r2=1478802&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/suggest/src/java/org/apache/lucene/search/suggest/BytesRefArray.java (original)
+++ lucene/dev/branches/branch_4x/lucene/suggest/src/java/org/apache/lucene/search/suggest/BytesRefArray.java Fri May 3 14:15:17 2013
@@ -21,12 +21,12 @@ import java.util.Arrays;
import java.util.Comparator;
import org.apache.lucene.util.ArrayUtil;
-import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.ByteBlockPool;
+import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.BytesRefIterator;
import org.apache.lucene.util.Counter;
+import org.apache.lucene.util.IntroSorter;
import org.apache.lucene.util.RamUsageEstimator;
-import org.apache.lucene.util.SorterTemplate;
/**
* A simple append only random-access {@link BytesRef} array that stores full
@@ -120,7 +120,7 @@ public final class BytesRefArray {
for (int i = 0; i < orderedEntries.length; i++) {
orderedEntries[i] = i;
}
- new SorterTemplate() {
+ new IntroSorter() {
@Override
protected void swap(int i, int j) {
final int o = orderedEntries[i];
@@ -148,7 +148,7 @@ public final class BytesRefArray {
private final BytesRef pivot = new BytesRef(), scratch1 = new BytesRef(),
scratch2 = new BytesRef();
- }.quickSort(0, size() - 1);
+ }.sort(0, size());
return orderedEntries;
}