You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by ot...@apache.org on 2003/09/11 14:15:30 UTC
cvs commit: jakarta-lucene/src/java/org/apache/lucene/util PriorityQueue.java
otis 2003/09/11 05:15:30
Modified: src/test/org/apache/lucene/util TestPriorityQueue.java
src/java/org/apache/lucene/search IndexSearcher.java
MultiSearcher.java
src/java/org/apache/lucene/util PriorityQueue.java
Log:
- Added insert(Object) method to PriorityQueue class.
Submitted by: Christoph Goller
Reviewed by: Otis
Revision Changes Path
1.4 +12 -0 jakarta-lucene/src/test/org/apache/lucene/util/TestPriorityQueue.java
Index: TestPriorityQueue.java
===================================================================
RCS file: /home/cvs/jakarta-lucene/src/test/org/apache/lucene/util/TestPriorityQueue.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- TestPriorityQueue.java 5 Jun 2002 01:50:54 -0000 1.3
+++ TestPriorityQueue.java 11 Sep 2003 12:15:30 -0000 1.4
@@ -135,4 +135,16 @@
pq.clear();
assertEquals(0, pq.size());
}
+
+ public void testFixedSize(){
+ PriorityQueue pq = new IntegerQueue(3);
+ pq.insert(new Integer(2));
+ pq.insert(new Integer(3));
+ pq.insert(new Integer(1));
+ pq.insert(new Integer(5));
+ pq.insert(new Integer(7));
+ pq.insert(new Integer(1));
+ assertEquals(3, pq.size());
+ assertEquals(3, ((Integer) pq.top()).intValue());
+ }
}
1.10 +1 -8 jakarta-lucene/src/java/org/apache/lucene/search/IndexSearcher.java
Index: IndexSearcher.java
===================================================================
RCS file: /home/cvs/jakarta-lucene/src/java/org/apache/lucene/search/IndexSearcher.java,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -r1.9 -r1.10
--- IndexSearcher.java 24 May 2003 15:24:26 -0000 1.9
+++ IndexSearcher.java 11 Sep 2003 12:15:30 -0000 1.10
@@ -133,18 +133,11 @@
final HitQueue hq = new HitQueue(nDocs);
final int[] totalHits = new int[1];
scorer.score(new HitCollector() {
- private float minScore = 0.0f;
public final void collect(int doc, float score) {
if (score > 0.0f && // ignore zeroed buckets
(bits==null || bits.get(doc))) { // skip docs not in bits
totalHits[0]++;
- if (score >= minScore) {
- hq.put(new ScoreDoc(doc, score)); // update hit queue
- if (hq.size() > nDocs) { // if hit queue overfull
- hq.pop(); // remove lowest in hit queue
- minScore = ((ScoreDoc)hq.top()).score; // reset minScore
- }
- }
+ hq.insert(new ScoreDoc(doc, score));
}
}
}, reader.maxDoc());
1.11 +3 -10 jakarta-lucene/src/java/org/apache/lucene/search/MultiSearcher.java
Index: MultiSearcher.java
===================================================================
RCS file: /home/cvs/jakarta-lucene/src/java/org/apache/lucene/search/MultiSearcher.java,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -r1.10 -r1.11
--- MultiSearcher.java 29 Jan 2003 17:18:54 -0000 1.10
+++ MultiSearcher.java 11 Sep 2003 12:15:30 -0000 1.11
@@ -144,7 +144,6 @@
public TopDocs search(Query query, Filter filter, int nDocs)
throws IOException {
HitQueue hq = new HitQueue(nDocs);
- float minScore = 0.0f;
int totalHits = 0;
for (int i = 0; i < searchables.length; i++) { // search each searcher
@@ -153,15 +152,9 @@
ScoreDoc[] scoreDocs = docs.scoreDocs;
for (int j = 0; j < scoreDocs.length; j++) { // merge scoreDocs into hq
ScoreDoc scoreDoc = scoreDocs[j];
- if (scoreDoc.score >= minScore) {
- scoreDoc.doc += starts[i]; // convert doc
- hq.put(scoreDoc); // update hit queue
- if (hq.size() > nDocs) { // if hit queue overfull
- hq.pop(); // remove lowest in hit queue
- minScore = ((ScoreDoc)hq.top()).score; // reset minScore
- }
- } else
- break; // no more scores > minScore
+ scoreDoc.doc += starts[i]; // convert doc
+ if(!hq.insert(scoreDoc))
+ break; // no more scores > minScore
}
}
1.4 +28 -2 jakarta-lucene/src/java/org/apache/lucene/util/PriorityQueue.java
Index: PriorityQueue.java
===================================================================
RCS file: /home/cvs/jakarta-lucene/src/java/org/apache/lucene/util/PriorityQueue.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- PriorityQueue.java 7 Nov 2002 05:55:40 -0000 1.3
+++ PriorityQueue.java 11 Sep 2003 12:15:30 -0000 1.4
@@ -60,6 +60,7 @@
public abstract class PriorityQueue {
private Object[] heap;
private int size;
+ private int maxSize;
/** Determines the ordering of objects in this priority queue. Subclasses
must define this one method. */
@@ -68,16 +69,41 @@
/** Subclass constructors must call this. */
protected final void initialize(int maxSize) {
size = 0;
- int heapSize = (maxSize * 2) + 1;
+ int heapSize = maxSize + 1;
heap = new Object[heapSize];
+ this.maxSize = maxSize;
}
- /** Adds an Object to a PriorityQueue in log(size) time. */
+ /**
+ * Adds an Object to a PriorityQueue in log(size) time.
+ * If one tries to add more objects than maxSize from initialize
+ * a RuntimeException (ArrayIndexOutOfBound) is thrown.
+ */
public final void put(Object element) {
size++;
heap[size] = element;
upHeap();
}
+
+ /**
+ * Adds element to the PriorityQueue in log(size) time if either
+ * the PriorityQueue is not full, or !lessThan(element, top()).
+ * @param element
+ * @return true if element is added, false otherwise.
+ */
+ public boolean insert(Object element){
+ if(size < maxSize){
+ put(element);
+ return true;
+ }
+ else if(size > 0 && !lessThan(element, top())){
+ heap[1] = element;
+ adjustTop();
+ return true;
+ }
+ else
+ return false;
+ }
/** Returns the least element of the PriorityQueue in constant time. */
public final Object top() {