it.unimi.di.mg4j.search.score
Class ScoredDocumentBoundedSizeQueue<T>

java.lang.Object
  it.unimi.di.mg4j.search.score.ScoredDocumentBoundedSizeQueue<T>

public class ScoredDocumentBoundedSizeQueue<T>
extends Object

A queue of scored documents with fixed maximum capacity.

Instances of this class contain a queue in which it possible to enqueue a document with given score. The capacity of the queue is fixed at creation time: once the queue is filled, new elements are enqueued by dequeueing those in the queue or discarded, depending on their score; the return value of enqueue(int, double, Object) can be used to check whether the argument has been actually enqueued or not. In particular, using the standard constructor will give a queue that remembers just the documents with highest score. As a commodity, document can be enqueued together with additional information that can be retrieved later.

The standard constructor orders document by score first, and then by document index. This trick guarantees that the queue is stable (because the order is an actual order, not a preorder), and makes it possible to consistently retrieve documents from the k-th to the (k+j)-th using a queue of capacity k+j from which j elements are extracted.

Warning: documents are dequeued in score order, which means documents with smaller score are dequeued first.

The queue returns its results as instances of DocumentScoreInfo.

Constructor Summary

ScoredDocumentBoundedSizeQueue(int capacity)
Creates a new empty bounded-size queue with a given capacity and natural order as comparator.

Method Summary

DocumentScoreInfo<T>	dequeue() Dequeues a document from the queue, returning an instance of DocumentScoreInfo.
boolean	enqueue(int d, double s) Enqueues a document with given score.
boolean	enqueue(int d, double s, T i) Enqueues a document with given score and info.
boolean	isEmpty()
int	size()
boolean	wouldEnqueue(int d, double s) Checks whether a document with given score would be enqueued.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ScoredDocumentBoundedSizeQueue

public ScoredDocumentBoundedSizeQueue(int capacity)

Creates a new empty bounded-size queue with a given capacity and natural order as comparator.

Documents with equal scores will be compared using their document index.

Parameters:

capacity - the initial capacity of this queue.

Method Detail

wouldEnqueue

public boolean wouldEnqueue(int d,
                            double s)

Checks whether a document with given score would be enqueued.

If this methods returns true, an immediately following call to enqueue(int, double, Object) with the same score would case the document to be enqueued.

Parameters:

d - the document to test.

s - its score.

Returns:

true if the document would have been enqueued by enqueue(int, double, Object).

enqueue

public boolean enqueue(int d,
                       double s,
                       T i)

Enqueues a document with given score and info.

Parameters:

d - the document to enqueue.

s - its score.

i - additional information about this document.

Returns:

true if the document has been actually enqueued.

enqueue

public boolean enqueue(int d,
                       double s)

Enqueues a document with given score.

Parameters:

d - the document to enqueue.

s - its score.

Returns:

true if the document has been actually enqueued.

isEmpty

public boolean isEmpty()

size

public int size()

dequeue

public DocumentScoreInfo<T> dequeue()

Dequeues a document from the queue, returning an instance of DocumentScoreInfo.

Documents are dequeued in inverse score order.

Returns:

the next DocumentScoreInfo.