?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Thumbnail file hits. Based on a patch from D Bera
[beagle.git] / beagled / Lucene.Net / Search / Spans / NearSpans.cs
blob796bc4654e5bf775e2dc988f6c0a97ced446812e
1 /*
2 * Copyright 2004 The Apache Software Foundation
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 using System;
17 using IndexReader = Lucene.Net.Index.IndexReader;
18 using PriorityQueue = Lucene.Net.Util.PriorityQueue;
19 namespace Lucene.Net.Search.Spans
20 {
21
22 class NearSpans : Spans
23 {
24 private SpanNearQuery query;
25
26 private System.Collections.IList ordered = new System.Collections.ArrayList(); // spans in query order
27 private int slop; // from query
28 private bool inOrder; // from query
29
30 private SpansCell first; // linked list of spans
31 private SpansCell last; // sorted by doc only
32
33 private int totalLength; // sum of current lengths
34
35 private CellQueue queue; // sorted queue of spans
36 private SpansCell max; // max element in queue
37
38 private bool more = true; // true iff not done
39 private bool firstTime = true; // true before first next()
40
41 private class CellQueue : PriorityQueue
42 {
43 private void InitBlock(NearSpans enclosingInstance)
44 {
45 this.enclosingInstance = enclosingInstance;
46 }
47 private NearSpans enclosingInstance;
48 public NearSpans Enclosing_Instance
49 {
50 get
51 {
52 return enclosingInstance;
53 }
54
55 }
56 public CellQueue(NearSpans enclosingInstance, int size)
57 {
58 InitBlock(enclosingInstance);
59 Initialize(size);
60 }
61
62 public override bool LessThan(System.Object o1, System.Object o2)
63 {
64 SpansCell spans1 = (SpansCell) o1;
65 SpansCell spans2 = (SpansCell) o2;
66 if (spans1.Doc() == spans2.Doc())
67 {
68 if (spans1.Start() == spans2.Start())
69 {
70 if (spans1.End() == spans2.End())
71 {
72 return spans1.index > spans2.index;
73 }
74 else
75 {
76 return spans1.End() < spans2.End();
77 }
78 }
79 else
80 {
81 return spans1.Start() < spans2.Start();
82 }
83 }
84 else
85 {
86 return spans1.Doc() < spans2.Doc();
87 }
88 }
89 }
90
91
92 /// <summary>Wraps a Spans, and can be used to form a linked list. </summary>
93 private class SpansCell : Spans
94 {
95 private void InitBlock(NearSpans enclosingInstance)
96 {
97 this.enclosingInstance = enclosingInstance;
98 }
99 private NearSpans enclosingInstance;
100 public NearSpans Enclosing_Instance
101 {
102 get
103 {
104 return enclosingInstance;
105 }
106
107 }
108
109 private Spans spans;
110 public SpansCell next;
111 private int length = - 1;
112 public int index;
113
114 public SpansCell(NearSpans enclosingInstance, Spans spans, int index)
115 {
116 InitBlock(enclosingInstance);
117 this.spans = spans;
118 this.index = index;
119 }
120
121 public virtual bool Next()
122 {
123 if (length != - 1)
124 // subtract old length
125 Enclosing_Instance.totalLength -= length;
126
127 bool more = spans.Next(); // move to next
128
129 if (more)
130 {
131 length = End() - Start(); // compute new length
132 Enclosing_Instance.totalLength += length; // add new length to total
133
134 if (Enclosing_Instance.max == null || Doc() > Enclosing_Instance.max.Doc() || (Doc() == Enclosing_Instance.max.Doc() && End() > Enclosing_Instance.max.End()))
135 Enclosing_Instance.max = this;
136 }
137
138 return more;
139 }
140
141 public virtual bool SkipTo(int target)
142 {
143 if (length != - 1)
144 // subtract old length
145 Enclosing_Instance.totalLength -= length;
146
147 bool more = spans.SkipTo(target); // skip
148
149 if (more)
150 {
151 length = End() - Start(); // compute new length
152 Enclosing_Instance.totalLength += length; // add new length to total
153
154 if (Enclosing_Instance.max == null || Doc() > Enclosing_Instance.max.Doc() || (Doc() == Enclosing_Instance.max.Doc() && End() > Enclosing_Instance.max.End()))
155 Enclosing_Instance.max = this;
156 }
157
158 return more;
159 }
160
161 public virtual int Doc()
162 {
163 return spans.Doc();
164 }
165 public virtual int Start()
166 {
167 return spans.Start();
168 }
169 public virtual int End()
170 {
171 return spans.End();
172 }
173
174 public override System.String ToString()
175 {
176 return spans.ToString() + "#" + index;
177 }
178 }
179
180 public NearSpans(SpanNearQuery query, IndexReader reader)
181 {
182 this.query = query;
183 this.slop = query.GetSlop();
184 this.inOrder = query.IsInOrder();
185
186 SpanQuery[] clauses = query.GetClauses(); // initialize spans & list
187 queue = new CellQueue(this, clauses.Length);
188 for (int i = 0; i < clauses.Length; i++)
189 {
190 SpansCell cell = new SpansCell(this, clauses[i].GetSpans(reader), i);
191 ordered.Add(cell); // add to ordered
192 }
193 }
194
195 public virtual bool Next()
196 {
197 if (firstTime)
198 {
199 InitList(true);
200 ListToQueue(); // initialize queue
201 firstTime = false;
202 }
203 else if (more)
204 {
205 more = Min().Next(); // trigger further scanning
206 if (more)
207 queue.AdjustTop(); // maintain queue
208 }
209
210 while (more)
211 {
212
213 bool queueStale = false;
214
215 if (Min().Doc() != max.Doc())
216 {
217 // maintain list
218 QueueToList();
219 queueStale = true;
220 }
221
222 // skip to doc w/ all clauses
223
224 while (more && first.Doc() < last.Doc())
225 {
226 more = first.SkipTo(last.Doc()); // skip first upto last
227 FirstToLast(); // and move it to the end
228 queueStale = true;
229 }
230
231 if (!more)
232 return false;
233
234 // found doc w/ all clauses
235
236 if (queueStale)
237 {
238 // maintain the queue
239 ListToQueue();
240 queueStale = false;
241 }
242
243 if (AtMatch())
244 return true;
245
246 // trigger further scanning
247 if (inOrder && CheckSlop())
248 {
249 /* There is a non ordered match within slop and an ordered match is needed. */
250 more = FirstNonOrderedNextToPartialList();
251 if (more)
252 {
253 PartialListToQueue();
254 }
255 }
256 else
257 {
258 more = Min().Next();
259 if (more)
260 {
261 queue.AdjustTop(); // maintain queue
262 }
263 }
264 }
265 return false; // no more matches
266 }
267
268 public virtual bool SkipTo(int target)
269 {
270 if (firstTime)
271 {
272 // initialize
273 InitList(false);
274 for (SpansCell cell = first; more && cell != null; cell = cell.next)
275 {
276 more = cell.SkipTo(target); // skip all
277 }
278 if (more)
279 {
280 ListToQueue();
281 }
282 firstTime = false;
283 }
284 else
285 {
286 // normal case
287 while (more && Min().Doc() < target)
288 {
289 // skip as needed
290 more = Min().SkipTo(target);
291 if (more)
292 queue.AdjustTop();
293 }
294 }
295 if (more)
296 {
297
298 if (AtMatch())
299 // at a match?
300 return true;
301
302 return Next(); // no, scan
303 }
304
305 return false;
306 }
307
308 private SpansCell Min()
309 {
310 return (SpansCell) queue.Top();
311 }
312
313 public virtual int Doc()
314 {
315 return Min().Doc();
316 }
317 public virtual int Start()
318 {
319 return Min().Start();
320 }
321 public virtual int End()
322 {
323 return max.End();
324 }
325
326
327 public override System.String ToString()
328 {
329 return "spans(" + query.ToString() + ")@" + (firstTime?"START":(more?(Doc() + ":" + Start() + "-" + End()):"END"));
330 }
331
332 private void InitList(bool next)
333 {
334 for (int i = 0; more && i < ordered.Count; i++)
335 {
336 SpansCell cell = (SpansCell) ordered[i];
337 if (next)
338 more = cell.Next(); // move to first entry
339 if (more)
340 {
341 AddToList(cell); // add to list
342 }
343 }
344 }
345
346 private void AddToList(SpansCell cell)
347 {
348 if (last != null)
349 {
350 // add next to end of list
351 last.next = cell;
352 }
353 else
354 first = cell;
355 last = cell;
356 cell.next = null;
357 }
358
359 private void FirstToLast()
360 {
361 last.next = first; // move first to end of list
362 last = first;
363 first = first.next;
364 last.next = null;
365 }
366
367 private void QueueToList()
368 {
369 last = first = null;
370 while (queue.Top() != null)
371 {
372 AddToList((SpansCell) queue.Pop());
373 }
374 }
375
376 private bool FirstNonOrderedNextToPartialList()
377 {
378 /* Creates a partial list consisting of first non ordered and earlier.
379 * Returns first non ordered .next().
380 */
381 last = first = null;
382 int orderedIndex = 0;
383 while (queue.Top() != null)
384 {
385 SpansCell cell = (SpansCell) queue.Pop();
386 AddToList(cell);
387 if (cell.index == orderedIndex)
388 {
389 orderedIndex++;
390 }
391 else
392 {
393 return cell.Next();
394 // FIXME: continue here, rename to eg. checkOrderedMatch():
395 // when checkSlop() and not ordered, repeat cell.next().
396 // when checkSlop() and ordered, add to list and repeat queue.pop()
397 // without checkSlop(): no match, rebuild the queue from the partial list.
398 // When queue is empty and checkSlop() and ordered there is a match.
399 }
400 }
401 throw new System.SystemException("Unexpected: ordered");
402 }
403
404 private void ListToQueue()
405 {
406 queue.Clear(); // rebuild queue
407 PartialListToQueue();
408 }
409
410 private void PartialListToQueue()
411 {
412 for (SpansCell cell = first; cell != null; cell = cell.next)
413 {
414 queue.Put(cell); // add to queue from list
415 }
416 }
417
418 private bool AtMatch()
419 {
420 return (Min().Doc() == max.Doc()) && CheckSlop() && (!inOrder || MatchIsOrdered());
421 }
422
423 private bool CheckSlop()
424 {
425 int matchLength = max.End() - Min().Start();
426 return (matchLength - totalLength) <= slop;
427 }
428
429 private bool MatchIsOrdered()
430 {
431 int lastStart = - 1;
432 for (int i = 0; i < ordered.Count; i++)
433 {
434 int start = ((SpansCell) ordered[i]).Start();
435 if (!(start > lastStart))
436 return false;
437 lastStart = start;
438 }
439 return true;
440 }
441 }
442 }
A Beagle Git Repo