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