lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From o...@apache.org
Subject cvs commit: jakarta-lucene/src/java/org/apache/lucene/util PriorityQueue.java
Date Thu, 11 Sep 2003 12:15:30 GMT
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() {
  
  
  

Mime
View raw message