lucene-java-3.4.0/lucene/src/java/org/apache/lucene/search/spans/NearSpansUnordered.java

   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 }