edu.vt.marian.search
Class PriQueueSequencer

java.lang.Object
  |
  +--edu.vt.marian.search.PriQueueSequencer

public class PriQueueSequencer

extends java.lang.Object

implements SetCollectionSequencer

A PriQueueSequencer is a Sequencer designed for large numbers of component sets. It is presumed that the sets are all proper WtdObjSets (that they all have varying weights among their elements) and that they are added with similar scaling weights, so that we are unlikely to be able to ignore any one set for long. (If this consequence is violated, we should be using a WtdObjSetSequencer (q.v.)).

Since the number of sets is large, we need an O(k) search for the next highest element. Back in the old days, somebody would build a heap and use it to implement a priority queue of component sets where the key is the (optinally weighted) top unused element in the set. But this is Java. Is there a PirorityQueue class in the library?

By the way, the reasoning below indicates that we want to keep all the sets but the current one on the PriQueue until elements from the current set fall below the top weight in thePriQueue.

We expect the weights in any WtdObjSet to drop off, not smoothly, but as a stairstep function. Thus instead of searching for the top element among the (scaled) component sets, we begin be searching for the top two sets, and search only when the top weight in the second set exceeds that in the top set.

See Also:

Sequencer, Enumeration

Constructor Summary

PriQueueSequencer(int ExpectedNumSets, long classSize, edu.vt.marian.common.Debug d)
Create a merging sequencer for an expected number of sets.

PriQueueSequencer(long classSize, edu.vt.marian.common.Debug d)
Create a merging sequencer for an unknown number of sets.

Method Summary

int	addSet(WtdObjSet set) Add a new component set to the Sequencer with no scaling constant.
int	expectedNumElts() Return the expected number of unique elements in the result sequence.
boolean	hasMoreElements()
int	maxNumElts() Return the maximum number of unique elements in the result sequence.
java.lang.Object	nextElement()
java.lang.String	profile()
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Constructor Detail

PriQueueSequencer

public PriQueueSequencer(long classSize,
                         edu.vt.marian.common.Debug d)

Create a merging sequencer for an unknown number of sets.

PriQueueSequencer

public PriQueueSequencer(int ExpectedNumSets,
                         long classSize,
                         edu.vt.marian.common.Debug d)

Create a merging sequencer for an expected number of sets.

Parameters:

expectedNumSets - As many sets as we expect to add. Does not need to be perfectly accurate.

Method Detail

addSet

public int addSet(WtdObjSet set)

Add a new component set to the Sequencer with no scaling constant.

Specified by:

addSet in interface SetCollectionSequencer

Parameters:

set - a component weighted object set.

Returns:

ReturnValues.OK -- set was added without problems.
anything else -- problems.

expectedNumElts

public int expectedNumElts()

Return the expected number of unique elements in the result sequence. NOTE: The statistics here are drawn from the hypergeometric distribution. Follow code and documentation in the C++ file "search/woset_coll.cc."

maxNumElts

public int maxNumElts()

Return the maximum number of unique elements in the result sequence. (This is just the sum of all the elements in each component set,)

nextElement

public java.lang.Object nextElement()

hasMoreElements

public boolean hasMoreElements()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

profile

public java.lang.String profile()