lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Christoph Goller <>
Subject PATCH: PriorityQueue
Date Thu, 04 Sep 2003 15:34:20 GMT
Hi folks,

This is a suggestion how to make code with PriorityQueue more consistent
and easier to understand. I am not talking about a bug. The current code
seems to work fine.

Currently there are two different kinds of applications of PriorityQueue.
In SegmentMergeQueue, PhraseQueue, and TermPositionsQueue one knows
in advance the maximum number of elements in the queue and the queue is
only used to order the elements. One is never tempted to add more elements
than the specified number to the queue. With HitQueue one wants to find the
n best hits within an a priori unknown number of hits.

My problem:

1) PriorityQueue currently is initialized with a maximum size, however it
actually can hold twice the number of elements. This feature is only used
by HitQueue which currently must be able to hold one element more than
maxSize. This is required by the code in IndexSearcher and MultiSearcher.

2) I find the code in IndexSearcher and MultiSearcher for controlling the
size of the queue a little bit confusing. Furthermore, if the queue is already
full and a new element has a higher score than top(), it is more efficient
to change the top-element and call adjustTop() than to add the new element
and call pop() afterwards (what is currently done).


I´d like to introduce a clearer contract about the maxSize in PriorityQueue.
PriorityQueue should be able to hold exactly maxSize elements and put()
should throw an exception if one accidently tries to add more elements.
Furthermore I´d like to add a method insert() to PriorityQueue that only adds
a new element if either the queue is not full or !lessThan(element, top()).
This new method can then be used in IndexSearcher and MultiSearcher.

Patch files for PriorityQueue, IndexSearcher, MultiSearcher, and
TestPriorityQueue (one additional test) are attached.

kind regards,

* Dr. Christoph Goller       Tel.:   +49 89 203 45734           *
* Detego Software GmbH       Mobile: +49 179 1128469            *
* Keuslinstr. 13             Fax.:   +49 721 151516176          *
* 80798 München, Germany     Email:  *

View raw message