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

    1   package org.apache.lucene.search.spans;
    2   
    3   /**
    4    * Copyright 2004 The Apache Software Foundation
    5    *
    6    * Licensed under the Apache License, Version 2.0 (the "License");
    7    * you may not use this file except in compliance with the License.
    8    * You may obtain a copy of the License at
    9    *
   10    *     http://www.apache.org/licenses/LICENSE-2.0
   11    *
   12    * Unless required by applicable law or agreed to in writing, software
   13    * distributed under the License is distributed on an "AS IS" BASIS,
   14    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   15    * See the License for the specific language governing permissions and
   16    * limitations under the License.
   17    */
   18   
   19   import java.io.IOException;
   20   
   21   import java.util.List;
   22   import java.util.ArrayList;
   23   
   24   import org.apache.lucene.index.IndexReader;
   25   import org.apache.lucene.util.PriorityQueue;
   26   
   27   class NearSpans implements Spans {
   28     private SpanNearQuery query;
   29   
   30     private List ordered = new ArrayList();         // spans in query order
   31     private int slop;                               // from query
   32     private boolean inOrder;                        // from query
   33   
   34     private SpansCell first;                        // linked list of spans
   35     private SpansCell last;                         // sorted by doc only
   36   
   37     private int totalLength;                        // sum of current lengths
   38   
   39     private CellQueue queue;                        // sorted queue of spans
   40     private SpansCell max;                          // max element in queue
   41   
   42     private boolean more = true;                    // true iff not done
   43     private boolean firstTime = true;               // true before first next()
   44   
   45     private class CellQueue extends PriorityQueue {
   46       public CellQueue(int size) {
   47         initialize(size);
   48       }
   49       
   50       protected final boolean lessThan(Object o1, Object o2) {
   51         SpansCell spans1 = (SpansCell)o1;
   52         SpansCell spans2 = (SpansCell)o2;
   53         if (spans1.doc() == spans2.doc()) {
   54           if (spans1.start() == spans2.start()) {
   55             if (spans1.end() == spans2.end()) {
   56               return spans1.index > spans2.index;
   57             } else {
   58               return spans1.end() < spans2.end();
   59             }
   60           } else {
   61             return spans1.start() < spans2.start();
   62           }
   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 implements 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       public boolean next() throws IOException {
   83         if (length != -1)                           // subtract old length
   84           totalLength -= length;
   85   
   86         boolean more = spans.next();                // move to next
   87   
   88         if (more) {
   89           length = end() - start();                 // compute new length
   90           totalLength += length;                    // add new length to total
   91   
   92           if (max == null || doc() > max.doc() ||   // maintain max
   93               (doc() == max.doc() && end() > max.end()))
   94             max = this;
   95         }
   96   
   97         return more;
   98       }
   99   
  100       public boolean skipTo(int target) throws IOException {
  101         if (length != -1)                           // subtract old length
  102           totalLength -= length;
  103   
  104         boolean more = spans.skipTo(target);        // skip
  105   
  106         if (more) {
  107           length = end() - start();                 // compute new length
  108           totalLength += length;                    // add new length to total
  109   
  110           if (max == null || doc() > max.doc() ||   // maintain max
  111               (doc() == max.doc() && end() > max.end()))
  112             max = this;
  113         }
  114   
  115         return more;
  116       }
  117   
  118       public int doc() { return spans.doc(); }
  119       public int start() { return spans.start(); }
  120       public int end() { return spans.end(); }
  121   
  122       public String toString() { return spans.toString() + "#" + index; }
  123     }
  124   
  125     public NearSpans(SpanNearQuery query, IndexReader reader)
  126       throws IOException {
  127       this.query = query;
  128       this.slop = query.getSlop();
  129       this.inOrder = query.isInOrder();
  130   
  131       SpanQuery[] clauses = query.getClauses();     // initialize spans & list
  132       queue = new CellQueue(clauses.length);
  133       for (int i = 0; i < clauses.length; i++) {
  134         SpansCell cell =                            // construct clause spans
  135           new SpansCell(clauses[i].getSpans(reader), i);
  136         ordered.add(cell);                          // add to ordered
  137       }
  138     }
  139   
  140     public boolean next() throws IOException {
  141       if (firstTime) {
  142         initList(true);
  143         listToQueue();                              // initialize queue
  144         firstTime = false;
  145       } else if (more) {
  146         more = min().next();                        // trigger further scanning
  147         if (more)
  148           queue.adjustTop();                        // maintain queue
  149       }
  150   
  151       while (more) {
  152   
  153         boolean queueStale = false;
  154   
  155         if (min().doc() != max.doc()) {             // maintain list
  156           queueToList();
  157           queueStale = true;
  158         }
  159   
  160         // skip to doc w/ all clauses
  161   
  162         while (more && first.doc() < last.doc()) {
  163           more = first.skipTo(last.doc());          // skip first upto last
  164           firstToLast();                            // and move it to the end
  165           queueStale = true;
  166         }
  167   
  168         if (!more) return false;
  169   
  170         // found doc w/ all clauses
  171   
  172         if (queueStale) {                           // maintain the queue
  173           listToQueue();
  174           queueStale = false;
  175         }
  176   
  177         if (atMatch())
  178           return true;
  179         
  180         // trigger further scanning
  181         if (inOrder && checkSlop()) {
  182           /* There is a non ordered match within slop and an ordered match is needed. */
  183           more = firstNonOrderedNextToPartialList();
  184           if (more) {
  185             partialListToQueue();                            
  186           }
  187         } else {
  188           more = min().next();
  189           if (more) {
  190             queue.adjustTop();                      // maintain queue
  191           }
  192         }
  193       }
  194       return false;                                 // no more matches
  195     }
  196   
  197     public boolean skipTo(int target) throws IOException {
  198       if (firstTime) {                              // initialize
  199         initList(false);
  200         for (SpansCell cell = first; more && cell!=null; cell=cell.next) {
  201           more = cell.skipTo(target);               // skip all
  202         }
  203         if (more) {
  204           listToQueue();
  205         }
  206         firstTime = false;
  207       } else {                                      // normal case
  208         while (more && min().doc() < target) {      // skip as needed
  209           more = min().skipTo(target);
  210           if (more)
  211             queue.adjustTop();
  212         }
  213       }
  214       if (more) {
  215   
  216         if (atMatch())                              // at a match?
  217           return true;
  218   
  219         return next();                              // no, scan
  220       }
  221   
  222       return false;
  223     }
  224   
  225     private SpansCell min() { return (SpansCell)queue.top(); }
  226   
  227     public int doc() { return min().doc(); }
  228     public int start() { return min().start(); }
  229     public int end() { return max.end(); }
  230   
  231   
  232     public String toString() {
  233       return "spans("+query.toString()+")@"+
  234         (firstTime?"START":(more?(doc()+":"+start()+"-"+end()):"END"));
  235     }
  236   
  237     private void initList(boolean next) throws IOException {
  238       for (int i = 0; more && i < ordered.size(); i++) {
  239         SpansCell cell = (SpansCell)ordered.get(i);
  240         if (next)
  241           more = cell.next();                       // move to first entry
  242         if (more) {
  243           addToList(cell);                          // add to list
  244         }
  245       }
  246     }
  247   
  248     private void addToList(SpansCell cell) {
  249       if (last != null) {			  // add next to end of list
  250         last.next = cell;
  251       } else
  252         first = cell;
  253       last = cell;
  254       cell.next = null;
  255     }
  256   
  257     private void firstToLast() {
  258       last.next = first;			  // move first to end of list
  259       last = first;
  260       first = first.next;
  261       last.next = null;
  262     }
  263   
  264     private void queueToList() {
  265       last = first = null;
  266       while (queue.top() != null) {
  267         addToList((SpansCell)queue.pop());
  268       }
  269     }
  270     
  271     private boolean firstNonOrderedNextToPartialList() throws IOException {
  272       /* Creates a partial list consisting of first non ordered and earlier.
  273        * Returns first non ordered .next().
  274        */
  275       last = first = null;
  276       int orderedIndex = 0;
  277       while (queue.top() != null) {
  278         SpansCell cell = (SpansCell)queue.pop();
  279         addToList(cell);
  280         if (cell.index == orderedIndex) {
  281           orderedIndex++;
  282         } else {
  283           return cell.next();
  284           // FIXME: continue here, rename to eg. checkOrderedMatch():
  285           // when checkSlop() and not ordered, repeat cell.next().
  286           // when checkSlop() and ordered, add to list and repeat queue.pop()
  287           // without checkSlop(): no match, rebuild the queue from the partial list.
  288           // When queue is empty and checkSlop() and ordered there is a match.
  289         }
  290       }
  291       throw new RuntimeException("Unexpected: ordered");
  292     }
  293   
  294     private void listToQueue() {
  295       queue.clear(); // rebuild queue
  296       partialListToQueue();
  297     }
  298   
  299     private void partialListToQueue() {
  300       for (SpansCell cell = first; cell != null; cell = cell.next) {
  301         queue.put(cell);                      // add to queue from list
  302       }
  303     }
  304   
  305     private boolean atMatch() {
  306       return (min().doc() == max.doc())
  307             && checkSlop()
  308             && (!inOrder || matchIsOrdered());
  309     }
  310     
  311     private boolean checkSlop() {
  312       int matchLength = max.end() - min().start();
  313       return (matchLength - totalLength) <= slop;
  314     }
  315   
  316     private boolean matchIsOrdered() {
  317       int lastStart = -1;
  318       for (int i = 0; i < ordered.size(); i++) {
  319         int start = ((SpansCell)ordered.get(i)).start();
  320         if (!(start > lastStart))
  321           return false;
  322         lastStart = start;
  323       }
  324       return true;
  325     }
  326   }

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