lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sh...@apache.org
Subject svn commit: r1458924 [9/13] - in /lucene/dev/branches/lucene4258: ./ dev-tools/ dev-tools/eclipse/dot.settings/ dev-tools/maven/ dev-tools/maven/solr/solrj/src/java/ dev-tools/scripts/ lucene/ lucene/analysis/ lucene/analysis/common/ lucene/analysis/co...
Date Wed, 20 Mar 2013 16:27:23 GMT
Modified: lucene/dev/branches/lucene4258/lucene/misc/src/java/org/apache/lucene/index/sorter/Sorter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/misc/src/java/org/apache/lucene/index/sorter/Sorter.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/misc/src/java/org/apache/lucene/index/sorter/Sorter.java (original)
+++ lucene/dev/branches/lucene4258/lucene/misc/src/java/org/apache/lucene/index/sorter/Sorter.java Wed Mar 20 16:27:13 2013
@@ -18,58 +18,104 @@ package org.apache.lucene.index.sorter;
  */
 
 import java.io.IOException;
-import java.util.List;
+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.packed.MonotonicAppendingLongBuffer;
 
 /**
  * Sorts documents in a given index by returning a permutation on the docs.
- * Implementations can call {@link #compute(int[], List)} to compute the
+ * Implementations can call {@link #sort(int, DocComparator)} to compute the
  * old-to-new permutation over the given documents and values.
  * 
  * @lucene.experimental
  */
 public abstract class Sorter {
-  
+
+  /**
+   * A permutation of doc IDs. For every document ID between <tt>0</tt> and
+   * {@link IndexReader#maxDoc()}, <code>oldToNew(newToOld(docID))</code> must
+   * return <code>docID</code>.
+   */
+  public static abstract class DocMap {
+
+    /** Given a doc ID from the original index, return its ordinal in the
+     *  sorted index. */
+    public abstract int oldToNew(int docID);
+
+    /** Given the ordinal of a doc ID, return its doc ID in the original index. */
+    public abstract int newToOld(int docID);
+
+  }
+
+  /** Check consistency of a {@link DocMap}, useful for assertions. */
+  static boolean isConsistent(DocMap docMap, int maxDoc) {
+    for (int i = 0; i < maxDoc; ++i) {
+      final int newID = docMap.oldToNew(i);
+      final int oldID = docMap.newToOld(newID);
+      assert newID >= 0 && newID < maxDoc : "doc IDs must be in [0-" + maxDoc + "[, got " + newID;
+      assert i == oldID : "mapping is inconsistent: " + i + " --oldToNew--> " + newID + " --newToOld--> " + oldID;
+      if (i != oldID || newID < 0 || newID >= maxDoc) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  /** A comparator of doc IDs. */
+  public static abstract class DocComparator {
+
+    /** Compare docID1 against docID2. The contract for the return value is the
+     *  same as {@link Comparator#compare(Object, Object)}. */
+    public abstract int compare(int docID1, int docID2);
+
+  }
+
   /** Sorts documents in reverse order. */
   public static final Sorter REVERSE_DOCS = new Sorter() {
     @Override
-    public int[] oldToNew(final AtomicReader reader) throws IOException {
+    public DocMap sort(final AtomicReader reader) throws IOException {
       final int maxDoc = reader.maxDoc();
-      int[] reverseDocs = new int[maxDoc];
-      for (int i = 0; i < maxDoc; i++) {
-        reverseDocs[i] = maxDoc - (i + 1);
-      }
-      return reverseDocs;
+      return new DocMap() {
+        @Override
+        public int oldToNew(int docID) {
+          return maxDoc - docID - 1;
+        }
+        @Override
+        public int newToOld(int docID) {
+          return maxDoc - docID - 1;
+        }
+      };
     }
   };
 
-  private static final class DocValueSorterTemplate<T extends Comparable<? super T>> extends SorterTemplate {
+  private static final class DocValueSorterTemplate extends SorterTemplate {
     
     private final int[] docs;
-    private final List<T> values;
+    private final Sorter.DocComparator comparator;
     
-    private T pivot;
+    private int pivot;
     
-    public DocValueSorterTemplate(int[] docs, List<T> values) {
+    public DocValueSorterTemplate(int[] docs, Sorter.DocComparator comparator) {
       this.docs = docs;
-      this.values = values;
+      this.comparator = comparator;
     }
     
     @Override
     protected int compare(int i, int j) {
-      return values.get(docs[i]).compareTo(values.get(docs[j]));
+      return comparator.compare(docs[i], docs[j]);
     }
     
     @Override
     protected int comparePivot(int j) {
-      return pivot.compareTo(values.get(docs[j]));
+      return comparator.compare(pivot, docs[j]);
     }
     
     @Override
     protected void setPivot(int i) {
-      pivot = values.get(docs[i]);
+      pivot = docs[i];
     }
     
     @Override
@@ -80,27 +126,74 @@ public abstract class Sorter {
     }
   }
 
-  /** Computes the old-to-new permutation over the given documents and values. */
-  protected static <T extends Comparable<? super T>> int[] compute(int[] docs, List<T> values) {
-    SorterTemplate sorter = new DocValueSorterTemplate<T>(docs, values);
-    sorter.quickSort(0, docs.length - 1);
-    
-    final int[] oldToNew = new int[docs.length];
-    for (int i = 0; i < docs.length; i++) {
-      oldToNew[docs[i]] = i;
+  /** Computes the old-to-new permutation over the given comparator. */
+  protected static Sorter.DocMap sort(final int maxDoc, DocComparator comparator) {
+    // check if the index is sorted
+    boolean sorted = true;
+    for (int i = 1; i < maxDoc; ++i) {
+      if (comparator.compare(i-1, i) > 0) {
+        sorted = false;
+        break;
+      }
+    }
+    if (sorted) {
+      return null;
+    }
+
+    // sort doc IDs
+    final int[] docs = new int[maxDoc];
+    for (int i = 0; i < maxDoc; i++) {
+      docs[i] = i;
     }
-    return oldToNew;
+    
+    SorterTemplate sorter = new DocValueSorterTemplate(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
+
+    // The reason why we use MonotonicAppendingLongBuffer here is that it
+    // wastes very little memory if the index is in random order but can save
+    // a lot of memory if the index is already "almost" sorted
+    final MonotonicAppendingLongBuffer newToOld = new MonotonicAppendingLongBuffer();
+    for (int i = 0; i < maxDoc; ++i) {
+      newToOld.add(docs[i]);
+    }
+
+    for (int i = 0; i < maxDoc; ++i) {
+      docs[(int) newToOld.get(i)] = i;
+    } // docs is now the oldToNew mapping
+
+    final MonotonicAppendingLongBuffer oldToNew = new MonotonicAppendingLongBuffer();
+    for (int i = 0; i < maxDoc; ++i) {
+      oldToNew.add(docs[i]);
+    }
+    
+    return new Sorter.DocMap() {
+
+      @Override
+      public int oldToNew(int docID) {
+        return (int) oldToNew.get(docID);
+      }
+
+      @Override
+      public int newToOld(int docID) {
+        return (int) newToOld.get(docID);
+      }
+    };
   }
   
   /**
    * Returns a mapping from the old document ID to its new location in the
    * sorted index. Implementations can use the auxiliary
-   * {@link #compute(int[], List)} to compute the old-to-new permutation
-   * given an array of documents and their corresponding values.
+   * {@link #sort(int, DocComparator)} to compute the old-to-new permutation
+   * given a list of documents and their corresponding values.
+   * <p>
+   * A return value of <tt>null</tt> is allowed and means that
+   * <code>reader</code> is already sorted.
    * <p>
    * <b>NOTE:</b> deleted documents are expected to appear in the mapping as
    * well, they will however be dropped when the index is actually sorted.
    */
-  public abstract int[] oldToNew(AtomicReader reader) throws IOException;
+  public abstract DocMap sort(AtomicReader reader) throws IOException;
   
 }

Modified: lucene/dev/branches/lucene4258/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java (original)
+++ lucene/dev/branches/lucene4258/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java Wed Mar 20 16:27:13 2013
@@ -43,7 +43,6 @@ 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.FixedBitSet;
 import org.apache.lucene.util.SorterTemplate;
 
 /**
@@ -66,14 +65,12 @@ public class SortingAtomicReader extends
 
   private static class SortingFields extends FilterFields {
 
-    private final int[] old2new;
-    private final Bits inLiveDocs;
+    private final Sorter.DocMap docMap;
     private final FieldInfos infos;
 
-    public SortingFields(final Fields in, final Bits inLiveDocs, FieldInfos infos, final int[] old2new) {
+    public SortingFields(final Fields in, FieldInfos infos, Sorter.DocMap docMap) {
       super(in);
-      this.old2new = old2new;
-      this.inLiveDocs = inLiveDocs;
+      this.docMap = docMap;
       this.infos = infos;
     }
 
@@ -83,7 +80,7 @@ public class SortingAtomicReader extends
       if (terms == null) {
         return null;
       } else {
-        return new SortingTerms(terms, inLiveDocs, infos.fieldInfo(field).getIndexOptions(), old2new);
+        return new SortingTerms(terms, infos.fieldInfo(field).getIndexOptions(), docMap);
       }
     }
 
@@ -91,75 +88,96 @@ public class SortingAtomicReader extends
 
   private static class SortingTerms extends FilterTerms {
 
-    private final int[] old2new;
-    private final Bits inLiveDocs;
+    private final Sorter.DocMap docMap;
     private final IndexOptions indexOptions;
     
-    public SortingTerms(final Terms in, final Bits inLiveDocs, IndexOptions indexOptions, final int[] old2new) {
+    public SortingTerms(final Terms in, IndexOptions indexOptions, final Sorter.DocMap docMap) {
       super(in);
-      this.old2new = old2new;
-      this.inLiveDocs = inLiveDocs;
+      this.docMap = docMap;
       this.indexOptions = indexOptions;
     }
 
     @Override
     public TermsEnum iterator(final TermsEnum reuse) throws IOException {
-      return new SortingTermsEnum(in.iterator(reuse), inLiveDocs, old2new, indexOptions);
+      return new SortingTermsEnum(in.iterator(reuse), docMap, indexOptions);
     }
 
   }
 
   private static class SortingTermsEnum extends FilterTermsEnum {
 
-    private final int[] old2new;
-    private final Bits inLiveDocs;
+    private final Sorter.DocMap docMap;
     private final IndexOptions indexOptions;
     
-    public SortingTermsEnum(final TermsEnum in, final Bits inLiveDocs, final int[] old2new, IndexOptions indexOptions) {
+    public SortingTermsEnum(final TermsEnum in, Sorter.DocMap docMap, IndexOptions indexOptions) {
       super(in);
-      this.old2new = old2new;
-      this.inLiveDocs = inLiveDocs;
+      this.docMap = docMap;
       this.indexOptions = indexOptions;
     }
 
+    Bits newToOld(final Bits liveDocs) {
+      if (liveDocs == null) {
+        return null;
+      }
+      return new Bits() {
+
+        @Override
+        public boolean get(int index) {
+          return liveDocs.get(docMap.oldToNew(index));
+        }
+
+        @Override
+        public int length() {
+          return liveDocs.length();
+        }
+
+      };
+    }
+
     @Override
     public DocsEnum docs(Bits liveDocs, DocsEnum reuse, final int flags) throws IOException {
-      if (liveDocs != null) {
-        liveDocs = inLiveDocs;
-      }
-      
-      // if we're asked to reuse the given DocsEnum and it is Sorting, return
-      // the wrapped one, since some Codecs expect it.
+      final DocsEnum inReuse;
+      final SortingDocsEnum wrapReuse;
       if (reuse != null && reuse instanceof SortingDocsEnum) {
-        reuse = ((SortingDocsEnum) reuse).getWrapped();
+        // if we're asked to reuse the given DocsEnum and it is Sorting, return
+        // the wrapped one, since some Codecs expect it.
+        wrapReuse = (SortingDocsEnum) reuse;
+        inReuse = wrapReuse.getWrapped();
+      } else {
+        wrapReuse = null;
+        inReuse = reuse;
       }
-      boolean withFreqs = indexOptions.compareTo(IndexOptions.DOCS_AND_FREQS) >=0 && (flags & DocsEnum.FLAG_FREQS) != 0;
-      return new SortingDocsEnum(in.docs(liveDocs, reuse, flags), withFreqs, old2new);
+
+      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);
     }
 
     @Override
     public DocsAndPositionsEnum docsAndPositions(Bits liveDocs, DocsAndPositionsEnum reuse, final int flags) throws IOException {
-      if (liveDocs != null) {
-        liveDocs = inLiveDocs;
-      }
-      
-      // if we're asked to reuse the given DocsAndPositionsEnum and it is
-      // Sorting, return the wrapped one, since some Codecs expect it.
+      final DocsAndPositionsEnum inReuse;
+      final SortingDocsAndPositionsEnum wrapReuse;
       if (reuse != null && reuse instanceof SortingDocsAndPositionsEnum) {
-        reuse = ((SortingDocsAndPositionsEnum) reuse).getWrapped();
+        // if we're asked to reuse the given DocsEnum and it is Sorting, return
+        // the wrapped one, since some Codecs expect it.
+        wrapReuse = (SortingDocsAndPositionsEnum) reuse;
+        inReuse = wrapReuse.getWrapped();
+      } else {
+        wrapReuse = null;
+        inReuse = reuse;
       }
-      
-      final DocsAndPositionsEnum positions = in.docsAndPositions(liveDocs, reuse, flags);
-      if (positions == null) {
+
+      final DocsAndPositionsEnum inDocsAndPositions = in.docsAndPositions(newToOld(liveDocs), inReuse, flags);
+      if (inDocsAndPositions == null) {
         return null;
-      } else {
-        // we ignore the fact that offsets may be stored but not asked for,
-        // since this code is expected to be used during addIndexes which will
-        // ask for everything. if that assumption changes in the future, we can
-        // factor in whether 'flags' says offsets are not required.
-        boolean storeOffsets = indexOptions.compareTo(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS_AND_OFFSETS) >= 0;
-        return new SortingDocsAndPositionsEnum(positions, old2new, storeOffsets);
       }
+
+      // we ignore the fact that offsets may be stored but not asked for,
+      // since this code is expected to be used during addIndexes which will
+      // 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);
     }
 
   }
@@ -167,48 +185,48 @@ public class SortingAtomicReader extends
   private static class SortingBinaryDocValues extends BinaryDocValues {
     
     private final BinaryDocValues in;
-    private final int[] new2old;
+    private final Sorter.DocMap docMap;
     
-    SortingBinaryDocValues(BinaryDocValues in, int[] new2old) {
+    SortingBinaryDocValues(BinaryDocValues in, Sorter.DocMap docMap) {
       this.in = in;
-      this.new2old = new2old;
+      this.docMap = docMap;
     }
 
     @Override
     public void get(int docID, BytesRef result) {
-      in.get(new2old[docID], result);
+      in.get(docMap.newToOld(docID), result);
     }
   }
   
   private static class SortingNumericDocValues extends NumericDocValues {
 
     private final NumericDocValues in;
-    private final int[] new2old;
+    private final Sorter.DocMap docMap;
 
-    public SortingNumericDocValues(final NumericDocValues in, final int[] new2old) {
+    public SortingNumericDocValues(final NumericDocValues in, Sorter.DocMap docMap) {
       this.in = in;
-      this.new2old = new2old;
+      this.docMap = docMap;
     }
 
     @Override
     public long get(int docID) {
-      return in.get(new2old[docID]);
+      return in.get(docMap.newToOld(docID));
     }
   }
   
   private static class SortingSortedDocValues extends SortedDocValues {
     
     private final SortedDocValues in;
-    private final int[] new2old;
+    private final Sorter.DocMap docMap;
     
-    SortingSortedDocValues(SortedDocValues in, int[] new2old) {
+    SortingSortedDocValues(SortedDocValues in, Sorter.DocMap docMap) {
       this.in = in;
-      this.new2old = new2old;
+      this.docMap = docMap;
     }
 
     @Override
     public int getOrd(int docID) {
-      return in.getOrd(new2old[docID]);
+      return in.getOrd(docMap.newToOld(docID));
     }
 
     @Override
@@ -223,7 +241,7 @@ public class SortingAtomicReader extends
 
     @Override
     public void get(int docID, BytesRef result) {
-      in.get(new2old[docID], result);
+      in.get(docMap.newToOld(docID), result);
     }
 
     @Override
@@ -235,11 +253,11 @@ public class SortingAtomicReader extends
   private static class SortingSortedSetDocValues extends SortedSetDocValues {
     
     private final SortedSetDocValues in;
-    private final int[] new2old;
+    private final Sorter.DocMap docMap;
     
-    SortingSortedSetDocValues(SortedSetDocValues in, int[] new2old) {
+    SortingSortedSetDocValues(SortedSetDocValues in, Sorter.DocMap docMap) {
       this.in = in;
-      this.new2old = new2old;
+      this.docMap = docMap;
     }
 
     @Override
@@ -249,7 +267,7 @@ public class SortingAtomicReader extends
 
     @Override
     public void setDocument(int docID) {
-      in.setDocument(new2old[docID]);
+      in.setDocument(docMap.newToOld(docID));
     }
 
     @Override
@@ -268,7 +286,7 @@ public class SortingAtomicReader extends
     }
   }
 
-  private static class SortingDocsEnum extends FilterDocsEnum {
+  static class SortingDocsEnum extends FilterDocsEnum {
     
     private static final class DocFreqSorterTemplate extends SorterTemplate {
       
@@ -303,49 +321,68 @@ public class SortingAtomicReader extends
         docs[i] = docs[j];
         docs[j] = tmpDoc;
         
-        int tmpFreq = freqs[i];
-        freqs[i] = freqs[j];
-        freqs[j] = tmpFreq;
+        if (freqs != null) {
+          int tmpFreq = freqs[i];
+          freqs[i] = freqs[j];
+          freqs[j] = tmpFreq;
+        }
       }
     }
     
-    private int[] docs = new int[64];
+    private int[] docs;
     private int[] freqs;
     private int docIt = -1;
     private final int upto;
     private final boolean withFreqs;
-    
-    public SortingDocsEnum(final DocsEnum in, boolean withFreqs, final int[] old2new) throws IOException {
+
+    SortingDocsEnum(SortingDocsEnum reuse, final DocsEnum in, boolean withFreqs, final Sorter.DocMap docMap) throws IOException {
       super(in);
       this.withFreqs = withFreqs;
+      if (reuse != null) {
+        docs = reuse.docs;
+        freqs = reuse.freqs; // maybe null
+      } else {
+        docs = new int[64];
+      }
+      docIt = -1;
       int i = 0;
       int doc;
       if (withFreqs) {
-        freqs = new int[docs.length];
+        if (freqs == null || freqs.length < docs.length) {
+          freqs = new int[docs.length];
+        }
         while ((doc = in.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS){
           if (i >= docs.length) {
             docs = ArrayUtil.grow(docs, docs.length + 1);
             freqs = ArrayUtil.grow(freqs, freqs.length + 1);
           }
-          docs[i] = old2new[doc];
+          docs[i] = docMap.oldToNew(doc);
           freqs[i] = in.freq();
           ++i;
         }
-        SorterTemplate sorter = new DocFreqSorterTemplate(docs, freqs);
-        sorter.quickSort(0, i - 1);
       } else {
         freqs = null;
         while ((doc = in.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS){
           if (i >= docs.length) {
             docs = ArrayUtil.grow(docs, docs.length + 1);
           }
-          docs[i++] = old2new[doc];
+          docs[i++] = docMap.oldToNew(doc);
         }
-        Arrays.sort(docs, 0, i);
       }
+      // 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);
       upto = i;
     }
-    
+
+    // for testing
+    boolean reused(DocsEnum other) {
+      if (other == null || !(other instanceof SortingDocsEnum)) {
+        return false;
+      }
+      return docs == ((SortingDocsEnum) other).docs;
+    }
+
     @Override
     public int advance(final int target) throws IOException {
       // need to support it for checkIndex, but in practice it won't be called, so
@@ -376,7 +413,7 @@ public class SortingAtomicReader extends
     }
   }
   
-  private static class SortingDocsAndPositionsEnum extends FilterDocsAndPositionsEnum {
+  static class SortingDocsAndPositionsEnum extends FilterDocsAndPositionsEnum {
     
     /**
      * A {@link SorterTemplate} which sorts two parallel arrays of doc IDs and
@@ -433,35 +470,53 @@ public class SortingAtomicReader extends
     private int pos;
     private int startOffset = -1;
     private int endOffset = -1;
-    private final BytesRef payload = new BytesRef(32);
+    private final BytesRef payload;
     private int currFreq;
-    
-    public SortingDocsAndPositionsEnum(final DocsAndPositionsEnum in, final int[] old2new, boolean storeOffsets) throws IOException {
+
+    private final RAMFile file;
+
+    SortingDocsAndPositionsEnum(SortingDocsAndPositionsEnum reuse, final DocsAndPositionsEnum in, Sorter.DocMap docMap, boolean storeOffsets) throws IOException {
       super(in);
       this.storeOffsets = storeOffsets;
-      final RAMFile file = new RAMFile();
+      if (reuse != null) {
+        docs = reuse.docs;
+        offsets = reuse.offsets;
+        payload = reuse.payload;
+        file = reuse.file;
+      } else {
+        docs = new int[32];
+        offsets = new long[32];
+        payload = new BytesRef(32);
+        file = new RAMFile();
+      }
       final IndexOutput out = new RAMOutputStream(file);
-      docs = new int[32];
-      offsets = new long[32];
       int doc;
       int i = 0;
       while ((doc = in.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
         if (i == docs.length) {
-          docs = ArrayUtil.grow(docs, docs.length + 1);
-          offsets = ArrayUtil.grow(offsets, offsets.length + 1);
+          final int newLength = ArrayUtil.oversize(i + 1, 4);
+          docs = Arrays.copyOf(docs, newLength);
+          offsets = Arrays.copyOf(offsets, newLength);
         }
-        docs[i] = old2new[doc];
+        docs[i] = docMap.oldToNew(doc);
         offsets[i] = out.getFilePointer();
         addPositions(in, out);
         i++;
       }
       upto = i;
-      SorterTemplate sorter = new DocOffsetSorterTemplate(docs, offsets);
-      sorter.quickSort(0, upto - 1);
+      new DocOffsetSorterTemplate(docs, offsets).timSort(0, upto - 1);
       out.close();
       this.postingInput = new RAMInputStream("", file);
     }
-    
+
+    // for testing
+    boolean reused(DocsAndPositionsEnum other) {
+      if (other == null || !(other instanceof SortingDocsAndPositionsEnum)) {
+        return false;
+      }
+      return docs == ((SortingDocsAndPositionsEnum) other).docs;
+    }
+
     private void addPositions(final DocsAndPositionsEnum in, final IndexOutput out) throws IOException {
       int freq = in.freq();
       out.writeVInt(freq);
@@ -547,38 +602,29 @@ public class SortingAtomicReader extends
     }
   }
 
-  private final int[] old2new, new2old;
-  private final FixedBitSet mappedLiveDocs;
+  /** Return a sorted view of <code>reader</code> according to the order
+   *  defined by <code>sorter</code>. If the reader is already sorted, this
+   *  method might return the reader as-is. */
+  public static AtomicReader sort(AtomicReader reader, Sorter sorter) throws IOException {
+    final Sorter.DocMap docMap = sorter.sort(reader);
+    if (docMap == null) {
+      // the reader is already sorter
+      return reader;
+    }
+    assert Sorter.isConsistent(docMap, reader.maxDoc());
+    return new SortingAtomicReader(reader, docMap);
+  }
+
+  private final Sorter.DocMap docMap;
 
-  public SortingAtomicReader(final AtomicReader in, final Sorter sorter) throws IOException {
+  private SortingAtomicReader(final AtomicReader in, final Sorter.DocMap docMap) {
     super(in);
-    old2new = sorter.oldToNew(in);
-    if (old2new.length != in.maxDoc()) {
-      throw new IllegalArgumentException("sorter should provide mapping for every document in the index, including deleted ones");
-    }
-    new2old = new int[old2new.length];
-    for (int i = 0; i < new2old.length; i++) {
-      new2old[old2new[i]] = i;
-    }
-    
-    if (!in.hasDeletions()) {
-      mappedLiveDocs = null;
-    } else {
-      mappedLiveDocs = new FixedBitSet(in.maxDoc());
-      mappedLiveDocs.set(0, in.maxDoc());
-      Bits liveDocs = in.getLiveDocs();
-      int len = liveDocs.length();
-      for (int i = 0; i < len; i++) {
-        if (!liveDocs.get(i)) {
-          mappedLiveDocs.clear(old2new[i]);
-        }
-      }
-    }
+    this.docMap = docMap;
   }
 
   @Override
   public void document(final int docID, final StoredFieldVisitor visitor) throws IOException {
-    in.document(new2old[docID], visitor);
+    in.document(docMap.newToOld(docID), visitor);
   }
   
   @Override
@@ -587,7 +633,7 @@ public class SortingAtomicReader extends
     if (fields == null) {
       return null;
     } else {
-      return new SortingFields(fields, in.getLiveDocs(), in.getFieldInfos(), old2new);
+      return new SortingFields(fields, in.getFieldInfos(), docMap);
     }
   }
   
@@ -597,14 +643,29 @@ public class SortingAtomicReader extends
     if (oldDocValues == null) {
       return null;
     } else {
-      return new SortingBinaryDocValues(oldDocValues, new2old);
+      return new SortingBinaryDocValues(oldDocValues, docMap);
     }
   }
   
   @Override
   public Bits getLiveDocs() {
-    ensureOpen();
-    return mappedLiveDocs;
+    final Bits inLiveDocs = in.getLiveDocs();
+    if (inLiveDocs == null) {
+      return null;
+    }
+    return new Bits() {
+
+      @Override
+      public boolean get(int index) {
+        return inLiveDocs.get(docMap.newToOld(index));
+      }
+
+      @Override
+      public int length() {
+        return inLiveDocs.length();
+      }
+
+    };
   }
   
   @Override
@@ -613,7 +674,7 @@ public class SortingAtomicReader extends
     if (norm == null) {
       return null;
     } else {
-      return new SortingNumericDocValues(norm, new2old);
+      return new SortingNumericDocValues(norm, docMap);
     }
   }
 
@@ -621,7 +682,7 @@ public class SortingAtomicReader extends
   public NumericDocValues getNumericDocValues(String field) throws IOException {
     final NumericDocValues oldDocValues = in.getNumericDocValues(field);
     if (oldDocValues == null) return null;
-    return new SortingNumericDocValues(oldDocValues, new2old);
+    return new SortingNumericDocValues(oldDocValues, docMap);
   }
 
   @Override
@@ -630,7 +691,7 @@ public class SortingAtomicReader extends
     if (sortedDV == null) {
       return null;
     } else {
-      return new SortingSortedDocValues(sortedDV, new2old);
+      return new SortingSortedDocValues(sortedDV, docMap);
     }
   }
   
@@ -640,13 +701,13 @@ public class SortingAtomicReader extends
     if (sortedSetDV == null) {
       return null;
     } else {
-      return new SortingSortedSetDocValues(sortedSetDV, new2old);
+      return new SortingSortedSetDocValues(sortedSetDV, docMap);
     }  
   }
 
   @Override
   public Fields getTermVectors(final int docID) throws IOException {
-    return in.getTermVectors(new2old[docID]);
+    return in.getTermVectors(docMap.newToOld(docID));
   }
   
 }

Modified: lucene/dev/branches/lucene4258/lucene/misc/src/java/org/apache/lucene/misc/HighFreqTerms.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/misc/src/java/org/apache/lucene/misc/HighFreqTerms.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/misc/src/java/org/apache/lucene/misc/HighFreqTerms.java (original)
+++ lucene/dev/branches/lucene4258/lucene/misc/src/java/org/apache/lucene/misc/HighFreqTerms.java Wed Mar 20 16:27:13 2013
@@ -211,13 +211,7 @@ final class TotalTermFreqComparatorSortD
   
   @Override
   public int compare(TermStats a, TermStats b) {
-    if (a.totalTermFreq < b.totalTermFreq) {
-      return 1;
-    } else if (a.totalTermFreq > b.totalTermFreq) {
-      return -1;
-    } else {
-      return 0;
-    }
+    return Long.compare(b.totalTermFreq, a.totalTermFreq);
   }
 }
 

Modified: lucene/dev/branches/lucene4258/lucene/misc/src/test/org/apache/lucene/index/sorter/IndexSortingTest.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/misc/src/test/org/apache/lucene/index/sorter/IndexSortingTest.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/misc/src/test/org/apache/lucene/index/sorter/IndexSortingTest.java (original)
+++ lucene/dev/branches/lucene4258/lucene/misc/src/test/org/apache/lucene/index/sorter/IndexSortingTest.java Wed Mar 20 16:27:13 2013
@@ -61,7 +61,7 @@ public class IndexSortingTest extends So
 
     Directory target = newDirectory();
     IndexWriter writer = new IndexWriter(target, newIndexWriterConfig(TEST_VERSION_CURRENT, null));
-    reader = new SortingAtomicReader(reader, sorter);
+    reader = SortingAtomicReader.sort(reader, sorter);
     writer.addIndexes(reader);
     writer.close();
     reader.close();

Modified: lucene/dev/branches/lucene4258/lucene/misc/src/test/org/apache/lucene/index/sorter/SorterTestBase.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/misc/src/test/org/apache/lucene/index/sorter/SorterTestBase.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/misc/src/test/org/apache/lucene/index/sorter/SorterTestBase.java (original)
+++ lucene/dev/branches/lucene4258/lucene/misc/src/test/org/apache/lucene/index/sorter/SorterTestBase.java Wed Mar 20 16:27:13 2013
@@ -1,5 +1,22 @@
 package org.apache.lucene.index.sorter;
 
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Arrays;
@@ -30,6 +47,7 @@ import org.apache.lucene.index.DocsAndPo
 import org.apache.lucene.index.DocsEnum;
 import org.apache.lucene.index.FieldInfo.IndexOptions;
 import org.apache.lucene.index.FieldInvertState;
+import org.apache.lucene.index.IndexReader;
 import org.apache.lucene.index.IndexWriterConfig;
 import org.apache.lucene.index.NumericDocValues;
 import org.apache.lucene.index.RandomIndexWriter;
@@ -38,6 +56,10 @@ import org.apache.lucene.index.SortedDoc
 import org.apache.lucene.index.SortedSetDocValues;
 import org.apache.lucene.index.Term;
 import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.index.TermsEnum.SeekStatus;
+import org.apache.lucene.index.sorter.SortingAtomicReader.SortingDocsAndPositionsEnum;
+import org.apache.lucene.index.sorter.SortingAtomicReader.SortingDocsEnum;
 import org.apache.lucene.search.CollectionStatistics;
 import org.apache.lucene.search.DocIdSetIterator;
 import org.apache.lucene.search.TermStatistics;
@@ -45,29 +67,13 @@ import org.apache.lucene.search.similari
 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.LuceneTestCase;
 import org.apache.lucene.util._TestUtil;
 import org.junit.AfterClass;
 import org.junit.BeforeClass;
 import org.junit.Test;
 
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
 public abstract class SorterTestBase extends LuceneTestCase {
 
   static final class NormsSimilarity extends Similarity {
@@ -231,7 +237,7 @@ public abstract class SorterTestBase ext
     int numDocs = atLeast(20);
     createIndex(dir, numDocs, random());
     
-    reader = new SlowCompositeReaderWrapper(DirectoryReader.open(dir));
+    reader = SlowCompositeReaderWrapper.wrap(DirectoryReader.open(dir));
   }
   
   @AfterClass
@@ -252,8 +258,9 @@ public abstract class SorterTestBase ext
   
   @Test
   public void testDocsAndPositionsEnum() throws Exception {
-    Term term = new Term(DOC_POSITIONS_FIELD, DOC_POSITIONS_TERM);
-    DocsAndPositionsEnum sortedPositions = reader.termPositionsEnum(term);
+    TermsEnum termsEnum = reader.terms(DOC_POSITIONS_FIELD).iterator(null);
+    assertEquals(SeekStatus.FOUND, termsEnum.seekCeil(new BytesRef(DOC_POSITIONS_TERM)));
+    DocsAndPositionsEnum sortedPositions = termsEnum.docsAndPositions(null, null);
     int doc;
     
     // test nextDoc()
@@ -271,7 +278,11 @@ public abstract class SorterTestBase ext
     }
     
     // test advance()
-    sortedPositions = reader.termPositionsEnum(term);
+    final DocsAndPositionsEnum reuse = sortedPositions;
+    sortedPositions = termsEnum.docsAndPositions(null, reuse);
+    if (sortedPositions instanceof SortingDocsAndPositionsEnum) {
+      assertTrue(((SortingDocsAndPositionsEnum) sortedPositions).reused(reuse)); // make sure reuse worked
+    }
     doc = 0;
     while ((doc = sortedPositions.advance(doc)) != DocIdSetIterator.NO_MORE_DOCS) {
       int freq = sortedPositions.freq();
@@ -286,36 +297,66 @@ public abstract class SorterTestBase ext
       }
     }
   }
-  
+
+  Bits randomLiveDocs(int maxDoc) {
+    if (rarely()) {
+      if (random().nextBoolean()) {
+        return null;
+      } else {
+        return new Bits.MatchNoBits(maxDoc);
+      }
+    }
+    final FixedBitSet bits = new FixedBitSet(maxDoc);
+    final int bitsSet = _TestUtil.nextInt(random(), 1, maxDoc - 1);
+    for (int i = 0; i < bitsSet; ++i) {
+      while (true) {
+        final int index = random().nextInt(maxDoc);
+        if (!bits.get(index)) {
+          bits.set(index);
+          break;
+        }
+      }
+    }
+    return bits;
+  }
+
   @Test
   public void testDocsEnum() throws Exception {
-    Term term = new Term(DOCS_ENUM_FIELD, DOCS_ENUM_TERM);
-    DocsEnum docs = reader.termDocsEnum(term);
-    Bits mappedLiveDocs = reader.getLiveDocs();
+    Bits mappedLiveDocs = randomLiveDocs(reader.maxDoc());
+    TermsEnum termsEnum = reader.terms(DOCS_ENUM_FIELD).iterator(null);
+    assertEquals(SeekStatus.FOUND, termsEnum.seekCeil(new BytesRef(DOCS_ENUM_TERM)));
+    DocsEnum docs = termsEnum.docs(mappedLiveDocs, null);
+
     int doc;
     int prev = -1;
     while ((doc = docs.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
-      if (mappedLiveDocs != null) {
-        assertTrue("document " + doc + " marked as deleted", mappedLiveDocs.get(doc));
-      }
+      assertTrue("document " + doc + " marked as deleted", mappedLiveDocs == null || mappedLiveDocs.get(doc));
       assertEquals("incorrect value; doc " + doc, sortedValues[doc].intValue(), Integer.parseInt(reader.document(doc).get(ID_FIELD)));
       while (++prev < doc) {
-        assertFalse("document " + prev + " not marked as deleted", mappedLiveDocs.get(prev));
+        assertFalse("document " + prev + " not marked as deleted", mappedLiveDocs == null || mappedLiveDocs.get(prev));
       }
     }
-    
-    docs = reader.termDocsEnum(term);
-    doc = 0;
+    while (++prev < reader.maxDoc()) {
+      assertFalse("document " + prev + " not marked as deleted", mappedLiveDocs == null || mappedLiveDocs.get(prev));
+    }
+
+    DocsEnum reuse = docs;
+    docs = termsEnum.docs(mappedLiveDocs, reuse);
+    if (docs instanceof SortingDocsEnum) {
+      assertTrue(((SortingDocsEnum) docs).reused(reuse)); // make sure reuse worked
+    }
+    doc = -1;
     prev = -1;
-    while ((doc = docs.advance(doc)) != DocIdSetIterator.NO_MORE_DOCS) {
-      if (mappedLiveDocs != null) {
-        assertTrue("document " + doc + " marked as deleted", mappedLiveDocs.get(doc));
-      }
+    while ((doc = docs.advance(doc + 1)) != DocIdSetIterator.NO_MORE_DOCS) {
+      assertTrue("document " + doc + " marked as deleted", mappedLiveDocs == null || mappedLiveDocs.get(doc));
       assertEquals("incorrect value; doc " + doc, sortedValues[doc].intValue(), Integer.parseInt(reader.document(doc).get(ID_FIELD)));
       while (++prev < doc) {
-        assertFalse("document " + prev + " not marked as deleted", mappedLiveDocs.get(prev));
+        assertFalse("document " + prev + " not marked as deleted", mappedLiveDocs == null || mappedLiveDocs.get(prev));
       }
     }
+    while (++prev < reader.maxDoc()) {
+      assertFalse("document " + prev + " not marked as deleted", mappedLiveDocs == null || mappedLiveDocs.get(prev));
+    }
   }
   
   @Test

Modified: lucene/dev/branches/lucene4258/lucene/misc/src/test/org/apache/lucene/index/sorter/SortingAtomicReaderTest.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/misc/src/test/org/apache/lucene/index/sorter/SortingAtomicReaderTest.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/misc/src/test/org/apache/lucene/index/sorter/SortingAtomicReaderTest.java (original)
+++ lucene/dev/branches/lucene4258/lucene/misc/src/test/org/apache/lucene/index/sorter/SortingAtomicReaderTest.java Wed Mar 20 16:27:13 2013
@@ -19,7 +19,6 @@ package org.apache.lucene.index.sorter;
 
 import java.io.IOException;
 import java.util.Arrays;
-import java.util.Collections;
 
 import org.apache.lucene.index.AtomicReader;
 import org.apache.lucene.util.Bits;
@@ -33,28 +32,34 @@ public class SortingAtomicReaderTest ext
     // build the mapping from the reader, since we deleted documents, some of
     // them might have disappeared from the index (e.g. if an entire segment is
     // dropped b/c all its docs are deleted)
-    Integer[] values = new Integer[reader.maxDoc()];
-    int[] docs = new int[reader.maxDoc()];
+    final int[] values = new int[reader.maxDoc()];
     for (int i = 0; i < reader.maxDoc(); i++) {
-      docs[i] = i;
       values[i] = Integer.valueOf(reader.document(i).get(ID_FIELD));
     }
+    final Sorter.DocComparator comparator = new Sorter.DocComparator() {
+      @Override
+      public int compare(int docID1, int docID2) {
+        final int v1 = values[docID1];
+        final int v2 = values[docID2];
+        return v1 < v2 ? -1 : v1 == v2 ? 0 : 1;
+      }
+    };
 
-    final int[] oldToNew = Sorter.compute(docs, Collections.unmodifiableList(Arrays.asList(values)));
+    final Sorter.DocMap docMap = Sorter.sort(reader.maxDoc(), comparator);
     // Sorter.compute also sorts the values
     sortedValues = new Integer[reader.maxDoc()];
     for (int i = 0; i < reader.maxDoc(); ++i) {
-      sortedValues[oldToNew[i]] = values[i];
+      sortedValues[docMap.oldToNew(i)] = values[i];
     }
     if (VERBOSE) {
-      System.out.println("oldToNew: " + Arrays.toString(oldToNew));
+      System.out.println("docMap: " + docMap);
       System.out.println("sortedValues: " + Arrays.toString(sortedValues));
     }
     
-    reader = new SortingAtomicReader(reader, new Sorter() {
+    reader = SortingAtomicReader.sort(reader, new Sorter() {
       @Override
-      public int[] oldToNew(AtomicReader reader) throws IOException {
-        return oldToNew;
+      public Sorter.DocMap sort(AtomicReader reader) throws IOException {
+        return docMap;
       }
     });
     

Modified: lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/CustomScoreQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/CustomScoreQuery.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/CustomScoreQuery.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/CustomScoreQuery.java Wed Mar 20 16:27:13 2013
@@ -348,6 +348,11 @@ public class CustomScoreQuery extends Qu
       }
       return doc;
     }
+
+    @Override
+    public long cost() {
+      return subQueryScorer.cost();
+    }
   }
 
   @Override

Modified: lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/BoostedQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/BoostedQuery.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/BoostedQuery.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/BoostedQuery.java Wed Mar 20 16:27:13 2013
@@ -188,6 +188,11 @@ public class BoostedQuery extends Query 
       res.addDetail(vals.explain(doc));
       return res;
     }
+
+    @Override
+    public long cost() {
+      return scorer.cost();
+    }
   }
 
 

Modified: lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/FunctionQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/FunctionQuery.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/FunctionQuery.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/FunctionQuery.java Wed Mar 20 16:27:13 2013
@@ -159,6 +159,11 @@ public class FunctionQuery extends Query
     }
 
     @Override
+    public long cost() {
+      return maxDoc;
+    }
+
+    @Override
     public int freq() throws IOException {
       return 1;
     }

Modified: lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/ValueSource.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/ValueSource.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/ValueSource.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/ValueSource.java Wed Mar 20 16:27:13 2013
@@ -139,28 +139,12 @@ public abstract class ValueSource {
 
     @Override
     public int compare(int slot1, int slot2) {
-      final double v1 = values[slot1];
-      final double v2 = values[slot2];
-      if (v1 > v2) {
-        return 1;
-      } else if (v1 < v2) {
-        return -1;
-      } else {
-        return 0;
-      }
-
+      return Double.compare(values[slot1], values[slot2]);
     }
 
     @Override
     public int compareBottom(int doc) {
-      final double v2 = docVals.doubleVal(doc);
-      if (bottom > v2) {
-        return 1;
-      } else if (bottom < v2) {
-        return -1;
-      } else {
-        return 0;
-      }
+      return Double.compare(bottom, docVals.doubleVal(doc));
     }
 
     @Override
@@ -188,13 +172,7 @@ public abstract class ValueSource {
     public int compareDocToValue(int doc, Double valueObj) {
       final double value = valueObj;
       final double docValue = docVals.doubleVal(doc);
-      if (docValue < value) {
-        return -1;
-      } else if (docValue > value) {
-        return 1;
-      } else {
-        return 0;
-      }
+      return Double.compare(docValue, value);
     }
   }
 }

Modified: lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/ValueSourceScorer.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/ValueSourceScorer.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/ValueSourceScorer.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/ValueSourceScorer.java Wed Mar 20 16:27:13 2013
@@ -91,4 +91,9 @@ public class ValueSourceScorer extends S
   public int freq() throws IOException {
     return 1;
   }
+
+  @Override
+  public long cost() {
+    return maxDoc;
+  }
 }

Modified: lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/valuesource/TFValueSource.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/valuesource/TFValueSource.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/valuesource/TFValueSource.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/valuesource/TFValueSource.java Wed Mar 20 16:27:13 2013
@@ -97,6 +97,11 @@ public class TFValueSource extends TermF
             public int advance(int target) {
               return DocIdSetIterator.NO_MORE_DOCS;
             }
+
+            @Override
+            public long cost() {
+              return 0;
+            }
           };
         }
         atDoc = -1;

Modified: lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/valuesource/TermFreqValueSource.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/valuesource/TermFreqValueSource.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/valuesource/TermFreqValueSource.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queries/src/java/org/apache/lucene/queries/function/valuesource/TermFreqValueSource.java Wed Mar 20 16:27:13 2013
@@ -90,6 +90,11 @@ public class TermFreqValueSource extends
             public int advance(int target) {
               return DocIdSetIterator.NO_MORE_DOCS;
             }
+
+            @Override
+            public long cost() {
+              return 0;
+            }
           };
         }
         atDoc = -1;

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/CharStream.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/CharStream.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/CharStream.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/CharStream.java Wed Mar 20 16:27:13 2013
@@ -112,4 +112,4 @@ interface CharStream {
   void Done();
 
 }
-/* JavaCC - OriginalChecksum=30b94cad7b10d0d81e3a59a1083939d0 (do not edit this line) */
+/* JavaCC - OriginalChecksum=c847dd1920bf7901125a7244125682ad (do not edit this line) */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/ParseException.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/ParseException.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/ParseException.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/ParseException.java Wed Mar 20 16:27:13 2013
@@ -184,4 +184,4 @@ public class ParseException extends Exce
    }
 
 }
-/* JavaCC - OriginalChecksum=b187d97d5bb75c3fc63d642c1c26ac6e (do not edit this line) */
+/* JavaCC - OriginalChecksum=61602edcb3a15810cbc58f5593eba40d (do not edit this line) */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/QueryParser.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/QueryParser.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/QueryParser.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/QueryParser.java Wed Mar 20 16:27:13 2013
@@ -165,7 +165,6 @@ public class QueryParser extends QueryPa
   }
 
 // This makes sure that there is no garbage after the query string
-  @Override
   final public Query TopLevelQuery(String field) throws ParseException {
   Query q;
     q = Query(field);
@@ -538,7 +537,6 @@ public class QueryParser extends QueryPa
   }
 
   /** Reinitialise. */
-  @Override
   public void ReInit(CharStream stream) {
     token_source.ReInit(stream);
     token = new Token();

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/Token.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/Token.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/Token.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/Token.java Wed Mar 20 16:27:13 2013
@@ -97,7 +97,6 @@ public class Token implements java.io.Se
   /**
    * Returns the image.
    */
-  @Override
   public String toString()
   {
     return image;
@@ -129,4 +128,4 @@ public class Token implements java.io.Se
   }
 
 }
-/* JavaCC - OriginalChecksum=405bb5d2fcd84e94ac1c8f0b12c1f914 (do not edit this line) */
+/* JavaCC - OriginalChecksum=c1e1418b35aa9e47ef8dc98b87423d70 (do not edit this line) */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/TokenMgrError.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/TokenMgrError.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/TokenMgrError.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/TokenMgrError.java Wed Mar 20 16:27:13 2013
@@ -121,7 +121,6 @@ public class TokenMgrError extends Error
    *
    * from this method for such cases in the release version of your parser.
    */
-  @Override
   public String getMessage() {
     return super.getMessage();
   }
@@ -145,4 +144,4 @@ public class TokenMgrError extends Error
     this(LexicalError(EOFSeen, lexState, errorLine, errorColumn, errorAfter, curChar), reason);
   }
 }
-/* JavaCC - OriginalChecksum=f433e1a52b8eadbf12f3fbbbf87fd140 (do not edit this line) */
+/* JavaCC - OriginalChecksum=0c275864a1972d9a01601ab81426872d (do not edit this line) */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/CharStream.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/CharStream.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/CharStream.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/CharStream.java Wed Mar 20 16:27:13 2013
@@ -112,4 +112,4 @@ interface CharStream {
   void Done();
 
 }
-/* JavaCC - OriginalChecksum=53b2ec7502d50e2290e86187a6c01270 (do not edit this line) */
+/* JavaCC - OriginalChecksum=c95f1720d9b38046dc5d294b741c44cb (do not edit this line) */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/ParseException.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/ParseException.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/ParseException.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/ParseException.java Wed Mar 20 16:27:13 2013
@@ -187,4 +187,4 @@ public class ParseException extends Quer
    }
 
 }
-/* JavaCC - OriginalChecksum=4263a02db9988d7a863aa97ad2f6dc67 (do not edit this line) */
+/* JavaCC - OriginalChecksum=81401c29cf6f9909761c636b4778ccc0 (do not edit this line) */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/StandardSyntaxParser.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/StandardSyntaxParser.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/StandardSyntaxParser.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/StandardSyntaxParser.java Wed Mar 20 16:27:13 2013
@@ -58,7 +58,6 @@ public class StandardSyntaxParser implem
      *  @param query  the query string to be parsed.
      *  @throws ParseException if the parsing fails
      */
-    @Override
     public QueryNode parse(CharSequence query, CharSequence field) throws QueryNodeParseException {
       ReInit(new FastCharStream(new StringReader(query.toString())));
       try {

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/Token.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/Token.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/Token.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/Token.java Wed Mar 20 16:27:13 2013
@@ -97,7 +97,6 @@ public class Token implements java.io.Se
   /**
    * Returns the image.
    */
-  @Override
   public String toString()
   {
     return image;
@@ -129,4 +128,4 @@ public class Token implements java.io.Se
   }
 
 }
-/* JavaCC - OriginalChecksum=ea8b1e55950603be28e2f63dcd544ab4 (do not edit this line) */
+/* JavaCC - OriginalChecksum=30bbd23e0dec26f141130dc62a4f6e9d (do not edit this line) */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/TokenMgrError.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/TokenMgrError.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/TokenMgrError.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/flexible/standard/parser/TokenMgrError.java Wed Mar 20 16:27:13 2013
@@ -121,7 +121,6 @@ public class TokenMgrError extends Error
    *
    * from this method for such cases in the release version of your parser.
    */
-  @Override
   public String getMessage() {
     return super.getMessage();
   }
@@ -145,4 +144,4 @@ public class TokenMgrError extends Error
     this(LexicalError(EOFSeen, lexState, errorLine, errorColumn, errorAfter, curChar), reason);
   }
 }
-/* JavaCC - OriginalChecksum=be88283d82a985d82a34dda46bcf42d5 (do not edit this line) */
+/* JavaCC - OriginalChecksum=3ca7fbf7de9f2424b131a5499b0a78d0 (do not edit this line) */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/CharStream.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/CharStream.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/CharStream.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/CharStream.java Wed Mar 20 16:27:13 2013
@@ -112,4 +112,4 @@ interface CharStream {
   void Done();
 
 }
-/* JavaCC - OriginalChecksum=242ae59b965491e225a44534cbc73b42 (do not edit this line) */
+/* JavaCC - OriginalChecksum=5ca20c9145f29a0f8909470a7f949fe4 (do not edit this line) */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/ParseException.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/ParseException.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/ParseException.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/ParseException.java Wed Mar 20 16:27:13 2013
@@ -184,4 +184,4 @@ public class ParseException extends Exce
    }
 
 }
-/* JavaCC - OriginalChecksum=bd8163f41bf2fd1bb00f025fce3dcaaf (do not edit this line) */
+/* JavaCC - OriginalChecksum=be6f55e3bf157e8c96b4c06cca5ec81b (do not edit this line) */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/QueryParser.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/QueryParser.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/QueryParser.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/QueryParser.java Wed Mar 20 16:27:13 2013
@@ -52,7 +52,7 @@ public class QueryParser implements Quer
   /* CHECKME: These should be the same as for the tokenizer. How? */
   final char truncator = '*';
   final char anyChar = '?';
-  final char quote = '\u005c"';
+  final char quote = '"';
   final char fieldOperator = ':';
   final char comma = ','; /* prefix list separator */
   final char carat = '^'; /* weight operator */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/QueryParser.jj
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/QueryParser.jj?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/QueryParser.jj (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/QueryParser.jj Wed Mar 20 16:27:13 2013
@@ -81,7 +81,7 @@ public class QueryParser {
   /* CHECKME: These should be the same as for the tokenizer. How? */
   final char truncator = '*';
   final char anyChar = '?';
-  final char quote = '\"';
+  final char quote = '"';
   final char fieldOperator = ':';
   final char comma = ','; /* prefix list separator */
   final char carat = '^'; /* weight operator */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/Token.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/Token.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/Token.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/Token.java Wed Mar 20 16:27:13 2013
@@ -97,7 +97,6 @@ public class Token implements java.io.Se
   /**
    * Returns the image.
    */
-  @Override
   public String toString()
   {
     return image;
@@ -129,4 +128,4 @@ public class Token implements java.io.Se
   }
 
 }
-/* JavaCC - OriginalChecksum=f2df701e24da1cf2d025118ce6efdd2f (do not edit this line) */
+/* JavaCC - OriginalChecksum=db38f23b3674db52ff034369707a0ac3 (do not edit this line) */

Modified: lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/TokenMgrError.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/TokenMgrError.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/TokenMgrError.java (original)
+++ lucene/dev/branches/lucene4258/lucene/queryparser/src/java/org/apache/lucene/queryparser/surround/parser/TokenMgrError.java Wed Mar 20 16:27:13 2013
@@ -121,7 +121,6 @@ public class TokenMgrError extends Error
    *
    * from this method for such cases in the release version of your parser.
    */
-  @Override
   public String getMessage() {
     return super.getMessage();
   }
@@ -145,4 +144,4 @@ public class TokenMgrError extends Error
     this(LexicalError(EOFSeen, lexState, errorLine, errorColumn, errorAfter, curChar), reason);
   }
 }
-/* JavaCC - OriginalChecksum=8c69a370d9a9893140562c8bb911678c (do not edit this line) */
+/* JavaCC - OriginalChecksum=dcdd5ccde13b91bcd8f76a86ca618852 (do not edit this line) */

Modified: lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/Lookup.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/Lookup.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/Lookup.java (original)
+++ lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/Lookup.java Wed Mar 20 16:27:13 2013
@@ -25,6 +25,7 @@ import java.util.List;
 
 import org.apache.lucene.search.spell.Dictionary;
 import org.apache.lucene.search.spell.TermFreqIterator;
+import org.apache.lucene.util.BytesRef;
 import org.apache.lucene.util.BytesRefIterator;
 import org.apache.lucene.util.PriorityQueue;
 
@@ -39,17 +40,29 @@ public abstract class Lookup {
   public static final class LookupResult implements Comparable<LookupResult> {
     /** the key's text */
     public final CharSequence key;
+
     /** the key's weight */
     public final long value;
+
+    /** the key's payload (null if not present) */
+    public final BytesRef payload;
     
     /**
      * Create a new result from a key+weight pair.
      */
     public LookupResult(CharSequence key, long value) {
+      this(key, value, null);
+    }
+
+    /**
+     * Create a new result from a key+weight+payload triple.
+     */
+    public LookupResult(CharSequence key, long value, BytesRef payload) {
       this.key = key;
       this.value = value;
+      this.payload = payload;
     }
-    
+
     @Override
     public String toString() {
       return key + "/" + value;

Modified: lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/SortedTermFreqIteratorWrapper.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/SortedTermFreqIteratorWrapper.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/SortedTermFreqIteratorWrapper.java (original)
+++ lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/SortedTermFreqIteratorWrapper.java Wed Mar 20 16:27:13 2013
@@ -120,13 +120,7 @@ public class SortedTermFreqIteratorWrapp
       if (cmp != 0) {
         return cmp;
       }
-      if (leftCost < rightCost) {
-        return -1;
-      } else if (rightCost < leftCost) {
-        return 1;
-      } else {
-        return 0;
-      }
+      return Long.compare(leftCost, rightCost);
     }
   };
   

Modified: lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java (original)
+++ lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java Wed Mar 20 16:27:13 2013
@@ -33,6 +33,7 @@ import org.apache.lucene.analysis.Analyz
 import org.apache.lucene.analysis.TokenStream;
 import org.apache.lucene.analysis.TokenStreamToAutomaton;
 import org.apache.lucene.search.spell.TermFreqIterator;
+import org.apache.lucene.search.spell.TermFreqPayloadIterator;
 import org.apache.lucene.search.suggest.Lookup;
 import org.apache.lucene.search.suggest.Sort;
 import org.apache.lucene.store.ByteArrayDataInput;
@@ -180,6 +181,10 @@ public class AnalyzingSuggester extends 
    *  graphs this will always be 1. */
   private int maxAnalyzedPathsForOneInput;
 
+  private boolean hasPayloads;
+
+  private static final int PAYLOAD_SEP = '\u001f';
+
   /**
    * Calls {@link #AnalyzingSuggester(Analyzer,Analyzer,int,int,int)
    * AnalyzingSuggester(analyzer, analyzer, EXACT_FIRST |
@@ -330,8 +335,15 @@ public class AnalyzingSuggester extends 
       return new TokenStreamToAutomaton();
     }
   }
+  
+  private static class AnalyzingComparator implements Comparator<BytesRef> {
+
+    private final boolean hasPayloads;
+
+    public AnalyzingComparator(boolean hasPayloads) {
+      this.hasPayloads = hasPayloads;
+    }
 
-  private  Comparator<BytesRef> sortComparator = new Comparator<BytesRef>() {
     private final ByteArrayDataInput readerA = new ByteArrayDataInput();
     private final ByteArrayDataInput readerB = new ByteArrayDataInput();
     private final BytesRef scratchA = new BytesRef();
@@ -367,10 +379,19 @@ public class AnalyzingSuggester extends 
       }
 
       // Finally by surface form:
-      scratchA.offset = readerA.getPosition();
-      scratchA.length = a.length - scratchA.offset;
-      scratchB.offset = readerB.getPosition();
-      scratchB.length = b.length - scratchB.offset;
+      if (hasPayloads) {
+        readerA.setPosition(readerA.getPosition() + scratchA.length);
+        scratchA.length = readerA.readShort();
+        scratchA.offset = readerA.getPosition();
+        readerB.setPosition(readerB.getPosition() + scratchB.length);
+        scratchB.length = readerB.readShort();
+        scratchB.offset = readerB.getPosition();
+      } else {
+        scratchA.offset = readerA.getPosition();
+        scratchA.length = a.length - scratchA.offset;
+        scratchB.offset = readerB.getPosition();
+        scratchB.length = b.length - scratchB.offset;
+      }
 
       cmp = scratchA.compareTo(scratchB);
       if (cmp != 0) {
@@ -380,21 +401,28 @@ public class AnalyzingSuggester extends 
       return 0;
     }
   };
-  
+
   @Override
   public void build(TermFreqIterator iterator) throws IOException {
     String prefix = getClass().getSimpleName();
     File directory = Sort.defaultTempDir();
     File tempInput = File.createTempFile(prefix, ".input", directory);
     File tempSorted = File.createTempFile(prefix, ".sorted", directory);
-    
+
+    TermFreqPayloadIterator payloads;
+    if (iterator instanceof TermFreqPayloadIterator) {
+      payloads = (TermFreqPayloadIterator) iterator;
+    } else {
+      payloads = null;
+    }
+    hasPayloads = payloads != null;
+
     Sort.ByteSequencesWriter writer = new Sort.ByteSequencesWriter(tempInput);
     Sort.ByteSequencesReader reader = null;
     BytesRef scratch = new BytesRef();
 
     TokenStreamToAutomaton ts2a = getTokenStreamToAutomaton();
 
-    // analyzed sequence + 0(byte) + weight(int) + surface + analyzedLength(short) 
     boolean success = false;
     byte buffer[] = new byte[8];
     try {
@@ -419,6 +447,19 @@ public class AnalyzingSuggester extends 
           // compute the required length:
           // analyzed sequence + weight (4) + surface + analyzedLength (short)
           int requiredLength = analyzedLength + 4 + surfaceForm.length + 2;
+
+          BytesRef payload;
+
+          if (hasPayloads) {
+            if (surfaceForm.length > (Short.MAX_VALUE-2)) {
+              throw new IllegalArgumentException("cannot handle surface form > " + (Short.MAX_VALUE-2) + " in length (got " + surfaceForm.length + ")");
+            }
+            payload = payloads.payload();
+            // payload + surfaceLength (short)
+            requiredLength += payload.length + 2;
+          } else {
+            payload = null;
+          }
           
           buffer = ArrayUtil.grow(buffer, requiredLength);
           
@@ -430,7 +471,18 @@ public class AnalyzingSuggester extends 
 
           output.writeInt(encodeWeight(iterator.weight()));
 
-          output.writeBytes(surfaceForm.bytes, surfaceForm.offset, surfaceForm.length);
+          if (hasPayloads) {
+            for(int i=0;i<surfaceForm.length;i++) {
+              if (surfaceForm.bytes[i] == PAYLOAD_SEP) {
+                throw new IllegalArgumentException("surface form cannot contain unit separator character U+001F; this character is reserved");
+              }
+            }
+            output.writeShort((short) surfaceForm.length);
+            output.writeBytes(surfaceForm.bytes, surfaceForm.offset, surfaceForm.length);
+            output.writeBytes(payload.bytes, payload.offset, payload.length);
+          } else {
+            output.writeBytes(surfaceForm.bytes, surfaceForm.offset, surfaceForm.length);
+          }
 
           assert output.getPosition() == requiredLength: output.getPosition() + " vs " + requiredLength;
 
@@ -440,7 +492,7 @@ public class AnalyzingSuggester extends 
       writer.close();
 
       // Sort all input/output pairs (required by FST.Builder):
-      new Sort(sortComparator).sort(tempInput, tempSorted);
+      new Sort(new AnalyzingComparator(payloads != null)).sort(tempInput, tempSorted);
 
       // Free disk space:
       tempInput.delete();
@@ -474,8 +526,13 @@ public class AnalyzingSuggester extends 
         long cost = input.readInt();
 
         surface.bytes = scratch.bytes;
-        surface.offset = input.getPosition();
-        surface.length = scratch.length - surface.offset;
+        if (hasPayloads) {
+          surface.length = input.readShort();
+          surface.offset = input.getPosition();
+        } else {
+          surface.offset = input.getPosition();
+          surface.length = scratch.length - surface.offset;
+        }
         
         if (previousAnalyzed == null) {
           previousAnalyzed = new BytesRef();
@@ -513,7 +570,18 @@ public class AnalyzingSuggester extends 
 
         Util.toIntsRef(analyzed, scratchInts);
         //System.out.println("ADD: " + scratchInts + " -> " + cost + ": " + surface.utf8ToString());
-        builder.add(scratchInts, outputs.newPair(cost, BytesRef.deepCopyOf(surface)));
+        if (!hasPayloads) {
+          builder.add(scratchInts, outputs.newPair(cost, BytesRef.deepCopyOf(surface)));
+        } else {
+          int payloadOffset = input.getPosition() + surface.length;
+          int payloadLength = scratch.length - payloadOffset;
+          BytesRef br = new BytesRef(surface.length + 1 + payloadLength);
+          System.arraycopy(surface.bytes, surface.offset, br.bytes, 0, surface.length);
+          br.bytes[surface.length] = PAYLOAD_SEP;
+          System.arraycopy(scratch.bytes, payloadOffset, br.bytes, surface.length+1, payloadLength);
+          br.length = br.bytes.length;
+          builder.add(scratchInts, outputs.newPair(cost, br));
+        }
       }
       fst = builder.finish();
 
@@ -542,6 +610,7 @@ public class AnalyzingSuggester extends 
 
       fst.save(dataOut);
       dataOut.writeVInt(maxAnalyzedPathsForOneInput);
+      dataOut.writeByte((byte) (hasPayloads ? 1 : 0));
     } finally {
       IOUtils.close(output);
     }
@@ -554,12 +623,58 @@ public class AnalyzingSuggester extends 
     try {
       this.fst = new FST<Pair<Long,BytesRef>>(dataIn, new PairOutputs<Long,BytesRef>(PositiveIntOutputs.getSingleton(true), ByteSequenceOutputs.getSingleton()));
       maxAnalyzedPathsForOneInput = dataIn.readVInt();
+      hasPayloads = dataIn.readByte() == 1;
     } finally {
       IOUtils.close(input);
     }
     return true;
   }
 
+  private LookupResult getLookupResult(Long output1, BytesRef output2, CharsRef spare) {
+    LookupResult result;
+    if (hasPayloads) {
+      int sepIndex = -1;
+      for(int i=0;i<output2.length;i++) {
+        if (output2.bytes[output2.offset+i] == PAYLOAD_SEP) {
+          sepIndex = i;
+          break;
+        }
+      }
+      assert sepIndex != -1;
+      spare.grow(sepIndex);
+      int payloadLen = output2.length - sepIndex - 1;
+      output2.length = sepIndex;
+      UnicodeUtil.UTF8toUTF16(output2, spare);
+      BytesRef payload = new BytesRef(payloadLen);
+      System.arraycopy(output2.bytes, sepIndex+1, payload.bytes, 0, payloadLen);
+      payload.length = payloadLen;
+      result = new LookupResult(spare.toString(), decodeWeight(output1), payload);
+    } else {
+      spare.grow(output2.length);
+      UnicodeUtil.UTF8toUTF16(output2, spare);
+      result = new LookupResult(spare.toString(), decodeWeight(output1));
+    }
+
+    return result;
+  }
+
+  private boolean sameSurfaceForm(BytesRef key, BytesRef output2) {
+    if (hasPayloads) {
+      // output2 has at least PAYLOAD_SEP byte:
+      if (key.length >= output2.length) {
+        return false;
+      }
+      for(int i=0;i<key.length;i++) {
+        if (key.bytes[key.offset+i] != output2.bytes[output2.offset+i]) {
+          return false;
+        }
+      }
+      return output2.bytes[output2.offset + key.length] == PAYLOAD_SEP;
+    } else {
+      return key.bytesEquals(output2);
+    }
+  }
+
   @Override
   public List<LookupResult> lookup(final CharSequence key, boolean onlyMorePopular, int num) {
     assert num > 0;
@@ -639,10 +754,9 @@ public class AnalyzingSuggester extends 
         // nodes we have and the
         // maxSurfaceFormsPerAnalyzedForm:
         for(MinResult<Pair<Long,BytesRef>> completion : completions) {
-          if (utf8Key.bytesEquals(completion.output.output2)) {
-            spare.grow(completion.output.output2.length);
-            UnicodeUtil.UTF8toUTF16(completion.output.output2, spare);
-            results.add(new LookupResult(spare.toString(), decodeWeight(completion.output.output1)));
+          BytesRef output2 = completion.output.output2;
+          if (sameSurfaceForm(utf8Key, output2)) {
+            results.add(getLookupResult(completion.output.output1, output2, spare));
             break;
           }
         }
@@ -676,7 +790,7 @@ public class AnalyzingSuggester extends 
             // In exactFirst mode, don't accept any paths
             // matching the surface form since that will
             // create duplicate results:
-            if (utf8Key.bytesEquals(output.output2)) {
+            if (sameSurfaceForm(utf8Key, output.output2)) {
               // We found exact match, which means we should
               // have already found it in the first search:
               assert results.size() == 1;
@@ -697,9 +811,8 @@ public class AnalyzingSuggester extends 
       MinResult<Pair<Long,BytesRef>> completions[] = searcher.search();
 
       for(MinResult<Pair<Long,BytesRef>> completion : completions) {
-        spare.grow(completion.output.output2.length);
-        UnicodeUtil.UTF8toUTF16(completion.output.output2, spare);
-        LookupResult result = new LookupResult(spare.toString(), decodeWeight(completion.output.output1));
+
+        LookupResult result = getLookupResult(completion.output.output1, completion.output.output2, spare);
 
         // TODO: for fuzzy case would be nice to return
         // how many edits were required
@@ -736,7 +849,6 @@ public class AnalyzingSuggester extends 
     // from each analyzed token, with byte 0 used as
     // separator between tokens:
     Automaton automaton = ts2a.toAutomaton(ts);
-    ts.end();
     ts.close();
 
     replaceSep(automaton);
@@ -758,7 +870,6 @@ public class AnalyzingSuggester extends 
     // Turn tokenstream into automaton:
     TokenStream ts = queryAnalyzer.tokenStream("", new StringReader(key.toString()));
     Automaton automaton = (getTokenStreamToAutomaton()).toAutomaton(ts);
-    ts.end();
     ts.close();
 
     // TODO: we could use the end offset to "guess"

Modified: lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/fst/FSTCompletionLookup.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/fst/FSTCompletionLookup.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/fst/FSTCompletionLookup.java (original)
+++ lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/fst/FSTCompletionLookup.java Wed Mar 20 16:27:13 2013
@@ -25,9 +25,10 @@ import java.util.ArrayList;
 import java.util.List;
 
 import org.apache.lucene.search.spell.TermFreqIterator;
+import org.apache.lucene.search.spell.TermFreqPayloadIterator;
 import org.apache.lucene.search.suggest.Lookup;
-import org.apache.lucene.search.suggest.Sort;
 import org.apache.lucene.search.suggest.Sort.SortInfo;
+import org.apache.lucene.search.suggest.Sort;
 import org.apache.lucene.search.suggest.fst.FSTCompletion.Completion;
 import org.apache.lucene.search.suggest.tst.TSTLookup;
 import org.apache.lucene.store.ByteArrayDataInput;
@@ -141,6 +142,9 @@ public class FSTCompletionLookup extends
 
   @Override
   public void build(TermFreqIterator tfit) throws IOException {
+    if (tfit instanceof TermFreqPayloadIterator) {
+      throw new IllegalArgumentException("this suggester doesn't support payloads");
+    }
     File tempInput = File.createTempFile(
         FSTCompletionLookup.class.getSimpleName(), ".input", Sort.defaultTempDir());
     File tempSorted = File.createTempFile(

Modified: lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/fst/WFSTCompletionLookup.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/fst/WFSTCompletionLookup.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/fst/WFSTCompletionLookup.java (original)
+++ lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/fst/WFSTCompletionLookup.java Wed Mar 20 16:27:13 2013
@@ -26,9 +26,10 @@ import java.util.Comparator;
 import java.util.List;
 
 import org.apache.lucene.search.spell.TermFreqIterator;
+import org.apache.lucene.search.spell.TermFreqPayloadIterator;
 import org.apache.lucene.search.suggest.Lookup;
-import org.apache.lucene.search.suggest.SortedTermFreqIteratorWrapper;
 import org.apache.lucene.search.suggest.Sort.ByteSequencesWriter;
+import org.apache.lucene.search.suggest.SortedTermFreqIteratorWrapper;
 import org.apache.lucene.store.ByteArrayDataInput;
 import org.apache.lucene.store.ByteArrayDataOutput;
 import org.apache.lucene.store.InputStreamDataInput;
@@ -40,12 +41,12 @@ import org.apache.lucene.util.IOUtils;
 import org.apache.lucene.util.IntsRef;
 import org.apache.lucene.util.UnicodeUtil;
 import org.apache.lucene.util.fst.Builder;
-import org.apache.lucene.util.fst.FST;
 import org.apache.lucene.util.fst.FST.Arc;
 import org.apache.lucene.util.fst.FST.BytesReader;
+import org.apache.lucene.util.fst.FST;
 import org.apache.lucene.util.fst.PositiveIntOutputs;
-import org.apache.lucene.util.fst.Util;
 import org.apache.lucene.util.fst.Util.MinResult;
+import org.apache.lucene.util.fst.Util;
 
 /**
  * Suggester based on a weighted FST: it first traverses the prefix, 
@@ -93,6 +94,9 @@ public class WFSTCompletionLookup extend
   
   @Override
   public void build(TermFreqIterator iterator) throws IOException {
+    if (iterator instanceof TermFreqPayloadIterator) {
+      throw new IllegalArgumentException("this suggester doesn't support payloads");
+    }
     BytesRef scratch = new BytesRef();
     TermFreqIterator iter = new WFSTTermFreqIteratorWrapper(iterator);
     IntsRef scratchInts = new IntsRef();

Modified: lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/jaspell/JaspellLookup.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/jaspell/JaspellLookup.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/jaspell/JaspellLookup.java (original)
+++ lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/jaspell/JaspellLookup.java Wed Mar 20 16:27:13 2013
@@ -26,6 +26,7 @@ import java.util.ArrayList;
 import java.util.List;
 
 import org.apache.lucene.search.spell.TermFreqIterator;
+import org.apache.lucene.search.spell.TermFreqPayloadIterator;
 import org.apache.lucene.search.suggest.Lookup;
 import org.apache.lucene.search.suggest.UnsortedTermFreqIteratorWrapper;
 import org.apache.lucene.search.suggest.jaspell.JaspellTernarySearchTrie.TSTNode;
@@ -53,6 +54,9 @@ public class JaspellLookup extends Looku
 
   @Override
   public void build(TermFreqIterator tfit) throws IOException {
+    if (tfit instanceof TermFreqPayloadIterator) {
+      throw new IllegalArgumentException("this suggester doesn't support payloads");
+    }
     if (tfit.getComparator() != null) {
       // make sure it's unsorted
       // WTF - this could result in yet another sorted iteration....

Modified: lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TSTLookup.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TSTLookup.java?rev=1458924&r1=1458923&r2=1458924&view=diff
==============================================================================
--- lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TSTLookup.java (original)
+++ lucene/dev/branches/lucene4258/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TSTLookup.java Wed Mar 20 16:27:13 2013
@@ -25,9 +25,10 @@ import java.io.OutputStream;
 import java.util.ArrayList;
 import java.util.List;
 
+import org.apache.lucene.search.spell.TermFreqIterator;
+import org.apache.lucene.search.spell.TermFreqPayloadIterator;
 import org.apache.lucene.search.suggest.Lookup;
 import org.apache.lucene.search.suggest.SortedTermFreqIteratorWrapper;
-import org.apache.lucene.search.spell.TermFreqIterator;
 import org.apache.lucene.util.BytesRef;
 import org.apache.lucene.util.CharsRef;
 import org.apache.lucene.util.IOUtils;
@@ -51,6 +52,9 @@ public class TSTLookup extends Lookup {
 
   @Override
   public void build(TermFreqIterator tfit) throws IOException {
+    if (tfit instanceof TermFreqPayloadIterator) {
+      throw new IllegalArgumentException("this suggester doesn't support payloads");
+    }
     root = new TernaryTreeNode();
     // buffer first
     if (tfit.getComparator() != BytesRef.getUTF8SortedAsUTF16Comparator()) {



Mime
View raw message