Lucene.Net  3.0.3
Lucene.Net is a port of the Lucene search engine library, written in C# and targeted at .NET runtime users.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Pages
ScorerDocQueue.cs
Go to the documentation of this file.
1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements. See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 
18 
19 /* Derived from Lucene.Net.Util.PriorityQueue of March 2005 */
20 using System;
21 using Lucene.Net.Support;
22 using DocIdSetIterator = Lucene.Net.Search.DocIdSetIterator;
23 using Scorer = Lucene.Net.Search.Scorer;
24 
25 namespace Lucene.Net.Util
26 {
27 
28  /// <summary>A ScorerDocQueue maintains a partial ordering of its Scorers such that the
29  /// least Scorer can always be found in constant time. Put()'s and pop()'s
30  /// require log(size) time. The ordering is by Scorer.doc().
31  /// </summary>
32  public class ScorerDocQueue
33  {
34  // later: SpansQueue for spans with doc and term positions
35  private HeapedScorerDoc[] heap;
36  private int maxSize;
37  private int size;
38 
39  private class HeapedScorerDoc
40  {
41  private void InitBlock(ScorerDocQueue enclosingInstance)
42  {
43  this.enclosingInstance = enclosingInstance;
44  }
45  private ScorerDocQueue enclosingInstance;
46  public ScorerDocQueue Enclosing_Instance
47  {
48  get
49  {
50  return enclosingInstance;
51  }
52 
53  }
54  internal Scorer scorer;
55  internal int doc;
56 
57  internal HeapedScorerDoc(ScorerDocQueue enclosingInstance, Scorer s):this(enclosingInstance, s, s.DocID())
58  {
59  }
60 
61  internal HeapedScorerDoc(ScorerDocQueue enclosingInstance, Scorer scorer, int doc)
62  {
63  InitBlock(enclosingInstance);
64  this.scorer = scorer;
65  this.doc = doc;
66  }
67 
68  internal virtual void Adjust()
69  {
70  doc = scorer.DocID();
71  }
72  }
73 
74  private HeapedScorerDoc topHSD; // same as heap[1], only for speed
75 
76  /// <summary>Create a ScorerDocQueue with a maximum size. </summary>
77  public ScorerDocQueue(int maxSize)
78  {
79  // assert maxSize >= 0;
80  size = 0;
81  int heapSize = maxSize + 1;
82  heap = new HeapedScorerDoc[heapSize];
83  this.maxSize = maxSize;
84  topHSD = heap[1]; // initially null
85  }
86 
87  /// <summary> Adds a Scorer to a ScorerDocQueue in log(size) time.
88  /// If one tries to add more Scorers than maxSize
89  /// a RuntimeException (ArrayIndexOutOfBound) is thrown.
90  /// </summary>
91  public void Put(Scorer scorer)
92  {
93  size++;
94  heap[size] = new HeapedScorerDoc(this, scorer);
95  UpHeap();
96  }
97 
98  /// <summary> Adds a Scorer to the ScorerDocQueue in log(size) time if either
99  /// the ScorerDocQueue is not full, or not lessThan(scorer, top()).
100  /// </summary>
101  /// <param name="scorer">
102  /// </param>
103  /// <returns> true if scorer is added, false otherwise.
104  /// </returns>
105  public virtual bool Insert(Scorer scorer)
106  {
107  if (size < maxSize)
108  {
109  Put(scorer);
110  return true;
111  }
112  else
113  {
114  int docNr = scorer.DocID();
115  if ((size > 0) && (!(docNr < topHSD.doc)))
116  {
117  // heap[1] is top()
118  heap[1] = new HeapedScorerDoc(this, scorer, docNr);
119  DownHeap();
120  return true;
121  }
122  else
123  {
124  return false;
125  }
126  }
127  }
128 
129  /// <summary>Returns the least Scorer of the ScorerDocQueue in constant time.
130  /// Should not be used when the queue is empty.
131  /// </summary>
132  public Scorer Top()
133  {
134  // assert size > 0;
135  return topHSD.scorer;
136  }
137 
138  /// <summary>Returns document number of the least Scorer of the ScorerDocQueue
139  /// in constant time.
140  /// Should not be used when the queue is empty.
141  /// </summary>
142  public int TopDoc()
143  {
144  // assert size > 0;
145  return topHSD.doc;
146  }
147 
148  public float TopScore()
149  {
150  // assert size > 0;
151  return topHSD.scorer.Score();
152  }
153 
154  public bool TopNextAndAdjustElsePop()
155  {
156  return CheckAdjustElsePop(topHSD.scorer.NextDoc() != DocIdSetIterator.NO_MORE_DOCS);
157  }
158 
159  public bool TopSkipToAndAdjustElsePop(int target)
160  {
161  return CheckAdjustElsePop(topHSD.scorer.Advance(target) != DocIdSetIterator.NO_MORE_DOCS);
162  }
163 
164  private bool CheckAdjustElsePop(bool cond)
165  {
166  if (cond)
167  {
168  // see also adjustTop
169  topHSD.doc = topHSD.scorer.DocID();
170  }
171  else
172  {
173  // see also popNoResult
174  heap[1] = heap[size]; // move last to first
175  heap[size] = null;
176  size--;
177  }
178  DownHeap();
179  return cond;
180  }
181 
182  /// <summary>Removes and returns the least scorer of the ScorerDocQueue in log(size)
183  /// time.
184  /// Should not be used when the queue is empty.
185  /// </summary>
186  public Scorer Pop()
187  {
188  // assert size > 0;
189  Scorer result = topHSD.scorer;
190  PopNoResult();
191  return result;
192  }
193 
194  /// <summary>Removes the least scorer of the ScorerDocQueue in log(size) time.
195  /// Should not be used when the queue is empty.
196  /// </summary>
197  private void PopNoResult()
198  {
199  heap[1] = heap[size]; // move last to first
200  heap[size] = null;
201  size--;
202  DownHeap(); // adjust heap
203  }
204 
205  /// <summary>Should be called when the scorer at top changes doc() value.
206  /// Still log(n) worst case, but it's at least twice as fast to <c>
207  /// { pq.top().change(); pq.adjustTop(); }
208  /// </c> instead of <c>
209  /// { o = pq.pop(); o.change(); pq.push(o); }
210  /// </c>
211  /// </summary>
212  public void AdjustTop()
213  {
214  // assert size > 0;
215  topHSD.Adjust();
216  DownHeap();
217  }
218 
219  /// <summary>Returns the number of scorers currently stored in the ScorerDocQueue. </summary>
220  public int Size()
221  {
222  return size;
223  }
224 
225  /// <summary>Removes all entries from the ScorerDocQueue. </summary>
226  public void Clear()
227  {
228  for (int i = 0; i <= size; i++)
229  {
230  heap[i] = null;
231  }
232  size = 0;
233  }
234 
235  private void UpHeap()
236  {
237  int i = size;
238  HeapedScorerDoc node = heap[i]; // save bottom node
239  int j = Number.URShift(i, 1);
240  while ((j > 0) && (node.doc < heap[j].doc))
241  {
242  heap[i] = heap[j]; // shift parents down
243  i = j;
244  j = Number.URShift(j, 1);
245  }
246  heap[i] = node; // install saved node
247  topHSD = heap[1];
248  }
249 
250  private void DownHeap()
251  {
252  int i = 1;
253  HeapedScorerDoc node = heap[i]; // save top node
254  int j = i << 1; // find smaller child
255  int k = j + 1;
256  if ((k <= size) && (heap[k].doc < heap[j].doc))
257  {
258  j = k;
259  }
260  while ((j <= size) && (heap[j].doc < node.doc))
261  {
262  heap[i] = heap[j]; // shift up child
263  i = j;
264  j = i << 1;
265  k = j + 1;
266  if (k <= size && (heap[k].doc < heap[j].doc))
267  {
268  j = k;
269  }
270  }
271  heap[i] = node; // install saved node
272  topHSD = heap[1];
273  }
274  }
275 }