NearSpans


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 }
327
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags