Home » lucene-3.0.1-src » org.apache » lucene » search » spans » [javadoc | source]

    1   package org.apache.lucene.search.spans;
    2   
    3   /**
    4    * Licensed to the Apache Software Foundation (ASF) under one or more
    5    * contributor license agreements.  See the NOTICE file distributed with
    6    * this work for additional information regarding copyright ownership.
    7    * The ASF licenses this file to You under the Apache License, Version 2.0
    8    * (the "License"); you may not use this file except in compliance with
    9    * the License.  You may obtain a copy of the License at
   10    *
   11    *     http://www.apache.org/licenses/LICENSE-2.0
   12    *
   13    * Unless required by applicable law or agreed to in writing, software
   14    * distributed under the License is distributed on an "AS IS" BASIS,
   15    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   16    * See the License for the specific language governing permissions and
   17    * limitations under the License.
   18    */
   19   
   20   import org.apache.lucene.index.IndexReader;
   21   import org.apache.lucene.util.PriorityQueue;
   22   
   23   import java.io.IOException;
   24   import java.util.ArrayList;
   25   import java.util.Collection;
   26   import java.util.List;
   27   import java.util.Set;
   28   import java.util.HashSet;
   29   
   30   /**
   31    * Similar to {@link NearSpansOrdered}, but for the unordered case.
   32    * 
   33    * Expert:
   34    * Only public for subclassing.  Most implementations should not need this class
   35    */
   36   public class NearSpansUnordered extends Spans {
   37     private SpanNearQuery query;
   38   
   39     private List<SpansCell> ordered = new ArrayList<SpansCell>();         // spans in query order
   40     private Spans[] subSpans;  
   41     private int slop;                               // from query
   42   
   43     private SpansCell first;                        // linked list of spans
   44     private SpansCell last;                         // sorted by doc only
   45   
   46     private int totalLength;                        // sum of current lengths
   47   
   48     private CellQueue queue;                        // sorted queue of spans
   49     private SpansCell max;                          // max element in queue
   50   
   51     private boolean more = true;                    // true iff not done
   52     private boolean firstTime = true;               // true before first next()
   53   
   54     private class CellQueue extends PriorityQueue<SpansCell> {
   55       public CellQueue(int size) {
   56         initialize(size);
   57       }
   58       
   59       @Override
   60       protected final boolean lessThan(SpansCell spans1, SpansCell spans2) {
   61         if (spans1.doc() == spans2.doc()) {
   62           return NearSpansOrdered.docSpansOrdered(spans1, spans2);
   63         } else {
   64           return spans1.doc() < spans2.doc();
   65         }
   66       }
   67     }
   68   
   69   
   70     /** Wraps a Spans, and can be used to form a linked list. */
   71     private class SpansCell extends Spans {
   72       private Spans spans;
   73       private SpansCell next;
   74       private int length = -1;
   75       private int index;
   76   
   77       public SpansCell(Spans spans, int index) {
   78         this.spans = spans;
   79         this.index = index;
   80       }
   81   
   82       @Override
   83       public boolean next() throws IOException {
   84         return adjust(spans.next());
   85       }
   86   
   87       @Override
   88       public boolean skipTo(int target) throws IOException {
   89         return adjust(spans.skipTo(target));
   90       }
   91       
   92       private boolean adjust(boolean condition) {
   93         if (length != -1) {
   94           totalLength -= length;  // subtract old length
   95         }
   96         if (condition) {
   97           length = end() - start(); 
   98           totalLength += length; // add new length
   99   
  100           if (max == null || doc() > max.doc()
  101               || (doc() == max.doc()) && (end() > max.end())) {
  102             max = this;
  103           }
  104         }
  105         more = condition;
  106         return condition;
  107       }
  108   
  109       @Override
  110       public int doc() { return spans.doc(); }
  111       
  112       @Override
  113       public int start() { return spans.start(); }
  114       
  115       @Override
  116       public int end() { return spans.end(); }
  117                       // TODO: Remove warning after API has been finalized
  118       @Override
  119       public Collection<byte[]> getPayload() throws IOException {
  120         return new ArrayList<byte[]>(spans.getPayload());
  121       }
  122   
  123       // TODO: Remove warning after API has been finalized
  124       @Override
  125       public boolean isPayloadAvailable() {
  126         return spans.isPayloadAvailable();
  127       }
  128   
  129       @Override
  130       public String toString() { return spans.toString() + "#" + index; }
  131     }
  132   
  133   
  134     public NearSpansUnordered(SpanNearQuery query, IndexReader reader)
  135       throws IOException {
  136       this.query = query;
  137       this.slop = query.getSlop();
  138   
  139       SpanQuery[] clauses = query.getClauses();
  140       queue = new CellQueue(clauses.length);
  141       subSpans = new Spans[clauses.length];    
  142       for (int i = 0; i < clauses.length; i++) {
  143         SpansCell cell =
  144           new SpansCell(clauses[i].getSpans(reader), i);
  145         ordered.add(cell);
  146         subSpans[i] = cell.spans;
  147       }
  148     }
  149     public Spans[] getSubSpans() {
  150   	  return subSpans;
  151     }
  152     @Override
  153     public boolean next() throws IOException {
  154       if (firstTime) {
  155         initList(true);
  156         listToQueue(); // initialize queue
  157         firstTime = false;
  158       } else if (more) {
  159         if (min().next()) { // trigger further scanning
  160           queue.updateTop(); // maintain queue
  161         } else {
  162           more = false;
  163         }
  164       }
  165   
  166       while (more) {
  167   
  168         boolean queueStale = false;
  169   
  170         if (min().doc() != max.doc()) {             // maintain list
  171           queueToList();
  172           queueStale = true;
  173         }
  174   
  175         // skip to doc w/ all clauses
  176   
  177         while (more && first.doc() < last.doc()) {
  178           more = first.skipTo(last.doc());          // skip first upto last
  179           firstToLast();                            // and move it to the end
  180           queueStale = true;
  181         }
  182   
  183         if (!more) return false;
  184   
  185         // found doc w/ all clauses
  186   
  187         if (queueStale) {                           // maintain the queue
  188           listToQueue();
  189           queueStale = false;
  190         }
  191   
  192         if (atMatch()) {
  193           return true;
  194         }
  195         
  196         more = min().next();
  197         if (more) {
  198           queue.updateTop();                      // maintain queue
  199         }
  200       }
  201       return false;                                 // no more matches
  202     }
  203   
  204     @Override
  205     public boolean skipTo(int target) throws IOException {
  206       if (firstTime) {                              // initialize
  207         initList(false);
  208         for (SpansCell cell = first; more && cell!=null; cell=cell.next) {
  209           more = cell.skipTo(target);               // skip all
  210         }
  211         if (more) {
  212           listToQueue();
  213         }
  214         firstTime = false;
  215       } else {                                      // normal case
  216         while (more && min().doc() < target) {      // skip as needed
  217           if (min().skipTo(target)) {
  218             queue.updateTop();
  219           } else {
  220             more = false;
  221           }
  222         }
  223       }
  224       return more && (atMatch() ||  next());
  225     }
  226   
  227     private SpansCell min() { return queue.top(); }
  228   
  229     @Override
  230     public int doc() { return min().doc(); }
  231     @Override
  232     public int start() { return min().start(); }
  233     @Override
  234     public int end() { return max.end(); }
  235   
  236     // TODO: Remove warning after API has been finalized
  237     /**
  238      * WARNING: The List is not necessarily in order of the the positions
  239      * @return Collection of <code>byte[]</code> payloads
  240      * @throws IOException
  241      */
  242     @Override
  243     public Collection<byte[]> getPayload() throws IOException {
  244       Set<byte[]> matchPayload = new HashSet<byte[]>();
  245       for (SpansCell cell = first; cell != null; cell = cell.next) {
  246         if (cell.isPayloadAvailable()) {
  247           matchPayload.addAll(cell.getPayload());
  248         }
  249       }
  250       return matchPayload;
  251     }
  252   
  253     // TODO: Remove warning after API has been finalized
  254     @Override
  255     public boolean isPayloadAvailable() {
  256       SpansCell pointer = min();
  257       while (pointer != null) {
  258         if (pointer.isPayloadAvailable()) {
  259           return true;
  260         }
  261         pointer = pointer.next;
  262       }
  263   
  264       return false;
  265     }
  266   
  267     @Override
  268     public String toString() {
  269       return getClass().getName() + "("+query.toString()+")@"+
  270         (firstTime?"START":(more?(doc()+":"+start()+"-"+end()):"END"));
  271     }
  272   
  273     private void initList(boolean next) throws IOException {
  274       for (int i = 0; more && i < ordered.size(); i++) {
  275         SpansCell cell = ordered.get(i);
  276         if (next)
  277           more = cell.next();                       // move to first entry
  278         if (more) {
  279           addToList(cell);                          // add to list
  280         }
  281       }
  282     }
  283   
  284     private void addToList(SpansCell cell) throws IOException {
  285       if (last != null) {			  // add next to end of list
  286         last.next = cell;
  287       } else
  288         first = cell;
  289       last = cell;
  290       cell.next = null;
  291     }
  292   
  293     private void firstToLast() {
  294       last.next = first;			  // move first to end of list
  295       last = first;
  296       first = first.next;
  297       last.next = null;
  298     }
  299   
  300     private void queueToList() throws IOException {
  301       last = first = null;
  302       while (queue.top() != null) {
  303         addToList(queue.pop());
  304       }
  305     }
  306     
  307     private void listToQueue() {
  308       queue.clear(); // rebuild queue
  309       for (SpansCell cell = first; cell != null; cell = cell.next) {
  310         queue.add(cell);                      // add to queue from list
  311       }
  312     }
  313   
  314     private boolean atMatch() {
  315       return (min().doc() == max.doc())
  316           && ((max.end() - min().start() - totalLength) <= slop);
  317     }
  318   }

Home » lucene-3.0.1-src » org.apache » lucene » search » spans » [javadoc | source]