cs2.introml

Class TieBreaker<T>

java.lang.Object

cs2.introml.TieBreaker<T>

Type Parameters:

T - type of object

public class TieBreaker<T>
extends java.lang.Object

A general mechanism by which to fairly choose the "winner" in a stream of objects of unknown size (Related: http://en.wikipedia.org/wiki/Reservoir_sampling). Each candidate object is supplied with a "cost" and the candidate with the smallest cost is returned as the winner (where ties are broken randomly). The implementation requires O(1) time/space (i.e. does not depend upon how many candidate objects are supplied).

Constructor Summary

Constructors

Constructor and Description
TieBreaker(long rngSeed) Initialize the random seed

Method Summary

Modifier and Type	Method and Description
void	candidate(T obj, double cost) Supply a candidate with a cost
T	getWinner() Based upon stream of candidates since the last reset (or construction), returns the winning candidate (lowest cost; selected randomly from any ties).
void	reset() Resets the object to a state in which it hasn't encountered any candidate objects.

Methods inherited from class java.lang.Object

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

Constructor Detail

TieBreaker

public TieBreaker(long rngSeed)

Initialize the random seed

Parameters:

rngSeed - random number generator seed

Method Detail

reset

public void reset()

Resets the object to a state in which it hasn't encountered any candidate objects.

candidate

public void candidate(T obj,
                      double cost)

Supply a candidate with a cost

Parameters:

obj - candidate

cost - cost (lower is cheaper)

getWinner

public T getWinner()

Based upon stream of candidates since the last reset (or construction), returns the winning candidate (lowest cost; selected randomly from any ties).

Returns:

object with lowest cost, randomly selected from amongst ties