ecologylab.collections
Class FloatWeightSet<E extends FloatSetElement>

java.lang.Object
  ecologylab.generic.Debug
      ecologylab.collections.FloatWeightSet<E>

All Implemented Interfaces:

BasicFloatSet<E>, LinearAccess<E>

public class FloatWeightSet<E extends FloatSetElement>
extends Debug
implements BasicFloatSet<E>

Provides the facility of efficient weighted random selection from a set elements, each of whicn includes a characterizing floating point weight.

Works in cooperation w FloatSetElements; requiring that user object to keep an integer index slot, which only we should be accessing. This impure oo style is an adaption to Java's lack of multiple inheritance.

Gotta be careful to be thread safe. Seems no operations can safely occur concurrently. There are a bunch of synchronized methods to affect this.

Field Summary

static int	EXTRA_ALLOCATION Allocate this many extra slots, to avoid needing to alloc due to synch issues between insert & prune.
protected int	extraAllocation This many extra slots will be allocated in the set, to enable insertions() prior to a prune(), without reallocation.
protected float[]	incrementalSums Used to maintain a sequential set of areas by weight, in order to implement fast weighted randomSelect().
protected java.util.ArrayList<E>	maxArrayList When there is more than one maximum found by maxSelect(), this ArrayList holds the tied elements.
protected int	pruneSize Maximum size to let this grow to, before needPrune() will return true.
protected FloatSetElement	SENTINEL Used as a boundary condition for fast implementations of sort.
protected float	setSum
protected int	size size of last used element in array

Fields inherited from interface ecologylab.collections.BasicFloatSet

NO_RECOMPUTE, PARTIAL_RECOMPUTE, RECOMPUTE_ALL

Constructor Summary

FloatWeightSet(int initialSize)
Create a set, with data structures to support the stated initial size.

FloatWeightSet(int initialSize, boolean supportWeightedRandomSelect)

FloatWeightSet(int initialSize, int extraAllocation, ThreadMaster threadMaster, boolean supportWeightedRandomSelect)
Create a set, with data structures to support the stated initial size, and a threadMaster that may pause use before expensive operations.

FloatWeightSet(int initialSize, ThreadMaster threadMaster)
Create a set, with data structures to support the stated initial size, and a threadMaster that may pause use before expensive operations.

FloatWeightSet(int initialSize, ThreadMaster threadMaster, boolean supportWeightedRandomSelect)

Method Summary

void	clear(boolean doRecycleElements) Delete all the elements in the set, as fast as possible.
boolean	contains(E element)
void	decrement(E el)
void	delete(E el, int recompute) Delete an element from the set.
FloatSetElement[]	elements()
E	findElement(E element)
E	get(int i) Get the ith element in the set.
int	getPruneSize() Get the maximum size this should grow to before pruning.
float[]	incrementalSums()
int	indexOf(E element)
void	initializeStructure(int size)
void	insert(E el)
boolean	isEmpty() Check to see if the set has any elements.
protected boolean	isOversize(int sizeThreshold) Return true if the size of this is greater than the threshold passed in.
E	lastElement() Get the last element in the set, or null if the set is empty.
static void	main(java.lang.String[] a)
protected void	maxArrayListClear() Clear the ArrayList of tied elements from the last maxSelect().
E	maxSelect()
E	maxSelect(int desiredSize) Prune to the specified desired size, if necessary, then do a maxSelect().
float	mean()
float	meanByIteration()
int	numSlots()
void	prune(int numToKeep) Delete lowest-weighted elements, in case this collection has grown too big.
E	pruneAndMaxSelect() Prune to the set's specified maxSize, if necessary, then do a maxSelect().
E	pruneAndWeightedRandomSelect() Prune to the set's specified maxSize, if necessary, then do a weightedRandomSelect().
boolean	pruneIfNeeded()
void	setElements(FloatSetElement[] newElements)
void	setIncrementalSums(float[] newIncrementalSums)
void	setNumSlots(int newNumSlots)
void	setPruneSize(int maxSize) Set the maximum size this should grow to before pruning.
void	setSize(int newSize)
java.lang.String	shortString()
int	size()
boolean	syncRecompute()
java.util.ArrayList<E>	tiedForMax() If there was a tie in the last maxSelect() calculation, the others will be here.
java.lang.String	toString()
E	weightedRandomSelect() weighted randomSelect() with no recompute to update the data structure.
E	weightedRandomSelect(int desiredSize) Prune to the specified desired size, if necessary, then do a weightedRandomSelect().

Methods inherited from class ecologylab.generic.Debug

classSimpleName, closeLoggingFile, debug, debug, debug, debug, debugA, debugA, debugA, debugI, debugI, debugI, error, error, getClassName, getClassName, getInteractive, getPackageName, getPackageName, getPackageName, initialize, level, level, level, logToFile, print, print, println, println, println, println, println, println, printlnA, printlnA, printlnA, printlnI, printlnI, printlnI, printlnI, setLoggingFile, show, show, superString, toggleInteractive, toString, warning, warning, weird, weird

Methods inherited from class java.lang.Object

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

Field Detail

incrementalSums

protected float[] incrementalSums

Used to maintain a sequential set of areas by weight, in order to implement fast weighted randomSelect().

setSum

protected float setSum

SENTINEL

protected final FloatSetElement SENTINEL

Used as a boundary condition for fast implementations of sort.

extraAllocation

protected final int extraAllocation

This many extra slots will be allocated in the set, to enable insertions() prior to a prune(), without reallocation.

EXTRA_ALLOCATION

public static final int EXTRA_ALLOCATION

Allocate this many extra slots, to avoid needing to alloc due to synch issues between insert & prune.

See Also:

Constant Field Values

size

protected int size

size of last used element in array

pruneSize

protected int pruneSize

Maximum size to let this grow to, before needPrune() will return true. That is, when the set grows larger than this, it should be prune()ed.

maxArrayList

protected java.util.ArrayList<E extends FloatSetElement> maxArrayList

When there is more than one maximum found by maxSelect(), this ArrayList holds the tied elements. That this is not either a temporary, or passed back as the result of the sort operation, is hackish.

Constructor Detail

FloatWeightSet

public FloatWeightSet(int initialSize)

Create a set, with data structures to support the stated initial size. This set will not support weightedRandomSelect().

FloatWeightSet

public FloatWeightSet(int initialSize,
                      boolean supportWeightedRandomSelect)

FloatWeightSet

public FloatWeightSet(int initialSize,
                      ThreadMaster threadMaster)

Create a set, with data structures to support the stated initial size, and a threadMaster that may pause use before expensive operations. This set will not support weightedRandomSelect().

FloatWeightSet

public FloatWeightSet(int initialSize,
                      ThreadMaster threadMaster,
                      boolean supportWeightedRandomSelect)

FloatWeightSet

public FloatWeightSet(int initialSize,
                      int extraAllocation,
                      ThreadMaster threadMaster,
                      boolean supportWeightedRandomSelect)

Create a set, with data structures to support the stated initial size, and a threadMaster that may pause use before expensive operations. This set may support weightedRandomSelect().

Method Detail

clear

public void clear(boolean doRecycleElements)

Delete all the elements in the set, as fast as possible.

Parameters:

doRecycleElements - TODO

insert

public void insert(E el)

delete

public void delete(E el,
                   int recompute)

Delete an element from the set. Perhaps recompute incremental sums for randomSelect() integrity. Includes ensuring we cant pick el again.

This method MUST ONLY be called by FloatSetElement.delete()!

Specified by:

delete in interface BasicFloatSet<E extends FloatSetElement>

Parameters:

el - The FloatSetElement element to delete.

recompute - -1 for absolutely no recompute. 0 for recompute upwards from el. 1 for recompute all.

pruneIfNeeded

public boolean pruneIfNeeded()

isOversize

protected boolean isOversize(int sizeThreshold)

Return true if the size of this is greater than the threshold passed in.

Parameters:

sizeThreshold -

Returns:

pruneAndMaxSelect

public E pruneAndMaxSelect()

Prune to the set's specified maxSize, if necessary, then do a maxSelect(). The reason for doing these operations together is because both require sorting.

Returns:

element in the set with the highest weight, or in case of a tie, a random pick of those.

maxSelect

public E maxSelect(int desiredSize)

Prune to the specified desired size, if necessary, then do a maxSelect().

Parameters:

desiredSize -

Returns:

element in the set with the highest weight, or in case of a tie, a random pick of those.

maxArrayListClear

protected void maxArrayListClear()

Clear the ArrayList of tied elements from the last maxSelect(). This method can be overridden to provide post-process before the actual clear.

The clear() should be done as part of maxSelect() to avoid memory leaks.

maxSelect

public E maxSelect()

Returns:

the maximum in the set. If there are ties, pick randomly among them

tiedForMax

public java.util.ArrayList<E> tiedForMax()

If there was a tie in the last maxSelect() calculation, the others will be here.

Returns:

prune

public void prune(int numToKeep)

Delete lowest-weighted elements, in case this collection has grown too big. (After all, we can't have the INFINITELY LARGE collections we'd really like.)

Parameters:

numToKeep - -- size for the set after pruning is done.

mean

public float mean()

meanByIteration

public float meanByIteration()

size

public int size()

Specified by:

size in interface LinearAccess<E extends FloatSetElement>

toString

public java.lang.String toString()

Overrides:

toString in class Debug

shortString

public java.lang.String shortString()

isEmpty

public boolean isEmpty()

Check to see if the set has any elements.

Specified by:

isEmpty in interface BasicFloatSet<E extends FloatSetElement>

Specified by:

isEmpty in interface LinearAccess<E extends FloatSetElement>

Returns:

get

public E get(int i)

Get the ith element in the set.

Specified by:

get in interface BasicFloatSet<E extends FloatSetElement>

Specified by:

get in interface LinearAccess<E extends FloatSetElement>

Parameters:

i -

Returns:

lastElement

public E lastElement()

Get the last element in the set, or null if the set is empty.

Specified by:

lastElement in interface BasicFloatSet<E extends FloatSetElement>

Returns:

syncRecompute

public boolean syncRecompute()

Returns:

True if the set has elements to pick.

pruneAndWeightedRandomSelect

public E pruneAndWeightedRandomSelect()

Prune to the set's specified maxSize, if necessary, then do a weightedRandomSelect(). The reason for doing these operations together is because both require structural recomputation, specifically getting the current weights for all elements.

Returns:

element in the set with the highest weight, or in case of a tie, a random pick of those.

weightedRandomSelect

public E weightedRandomSelect(int desiredSize)

Prune to the specified desired size, if necessary, then do a weightedRandomSelect(). The reason for doing these operations together is because both require structural recomputation, specifically getting the current weights for all elements.

Parameters:

desiredSize -

Returns:

an element from the set.

weightedRandomSelect

public E weightedRandomSelect()

weighted randomSelect() with no recompute to update the data structure. Assumes caller is responsible for that updating via syncRecompute(...).

findElement

public E findElement(E element)

indexOf

public int indexOf(E element)

contains

public boolean contains(E element)

main

public static void main(java.lang.String[] a)

elements

public FloatSetElement[] elements()

setElements

public void setElements(FloatSetElement[] newElements)

incrementalSums

public float[] incrementalSums()

setIncrementalSums

public void setIncrementalSums(float[] newIncrementalSums)

numSlots

public int numSlots()

setNumSlots

public void setNumSlots(int newNumSlots)

setSize

public void setSize(int newSize)

initializeStructure

public void initializeStructure(int size)

setPruneSize

public void setPruneSize(int maxSize)

Set the maximum size this should grow to before pruning.

Parameters:

maxSize - The maxSize to set.

getPruneSize

public int getPruneSize()

Get the maximum size this should grow to before pruning.

decrement

public void decrement(E el)

Specified by:

decrement in interface BasicFloatSet<E extends FloatSetElement>