burlap.datastructures

Class StochasticTree<T>

java.lang.Object

burlap.datastructures.StochasticTree<T>

Type Parameters:

T - any Java object that will be sampled

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

A class for performing sampling of a set of objects at O(lg(n)) time. Elements can be added and removed dynamically. The "weights" of the objects should be positive values, but do not have to specify a probability distribution. The sampling will be performed according to the relative weight of all objects.

Author:

James MacGlashan

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	StochasticTree.STNode A class for storing a stochastic tree node.

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.Map<T,StochasticTree.STNode>	nodeMap A map from elements to the node that holds them.
protected java.util.Random	rand A random object used for sampling.
protected StochasticTree.STNode	root Root node of the stochastic tree

Constructor Summary

Constructors

Constructor and Description
StochasticTree() Initializes with an empty tree.
StochasticTree(java.util.List<java.lang.Double> weights, java.util.List<T> elements) Initializes a tree for objects with the given weights

Method Summary

Methods

Modifier and Type	Method and Description
void	changeWeight(T element, double w) Changes the weight of the given element.
T	getStoredEntry(T el) Returns the pointer to the stored entry in this tree for the given query element.
protected void	init() Initializes the three data structure
void	insert(double w, T el) Inserts the given element into the tree with the given weight
protected void	insertHelper(StochasticTree.STNode node, double w, T el) Helper recursive method for inserting an element
static void	main(java.lang.String[] args) Demos how to use this class
protected void	percolateWeightChange(StochasticTree.STNode node, double delta) A recursive method for percolating a weight change of a node
T	poll() Samples an element according to a probability defined by the relative weight of objects, removes it from the tree, and returns it.
void	remove(T element) Removes the given element from the tree.
protected void	removeHelper(StochasticTree.STNode node) A recursive method for removing a node
T	sample() Samples an element according to a probability defined by the relative weight of objects from the tree and returns it
protected StochasticTree.STNode	sampleHelper(StochasticTree.STNode node, double v) A recursive method for performing sampling
void	setRandom(java.util.Random r) Sets the tree to use a specific random object when performing sampling
int	size() Returns the number of objects in this tree
static void	test1() Another example usage
static void	test2() An example usage

Methods inherited from class java.lang.Object

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

Field Detail

root

protected StochasticTree.STNode root

Root node of the stochastic tree

nodeMap

protected java.util.Map<T,StochasticTree.STNode> nodeMap

A map from elements to the node that holds them.

rand

protected java.util.Random rand

A random object used for sampling.

Constructor Detail

StochasticTree

public StochasticTree()

Initializes with an empty tree.

StochasticTree

public StochasticTree(java.util.List<java.lang.Double> weights,
              java.util.List<T> elements)

Initializes a tree for objects with the given weights

Parameters:

weights - the weights of a set objects that determine how likely they are to be sampled

elements - the elements of the tree that will be sampled

Method Detail

init

protected void init()

Initializes the three data structure

setRandom

public void setRandom(java.util.Random r)

Sets the tree to use a specific random object when performing sampling

Parameters:

r -

size

public int size()

Returns the number of objects in this tree

Returns:

the number of objects in this tree

getStoredEntry

public T getStoredEntry(T el)

Returns the pointer to the stored entry in this tree for the given query element. This method requires T to be a hashable object.

Parameters:

el - the element whose stored object in the tree is to be returned

Returns:

the pointer to the stored entry in this tree for the given query element

insert

public void insert(double w,
          T el)

Inserts the given element into the tree with the given weight

Parameters:

w - the weight of the element

el - the element to insert

changeWeight

public void changeWeight(T element,
                double w)

Changes the weight of the given element. For this operation to be supported T must be hashable.

Parameters:

element - the element whose weight should be changed.

w - the new weight of the element.

remove

public void remove(T element)

Removes the given element from the tree. For this operation to be supported T must be hashable.

Parameters:

element -

sample

public T sample()

Samples an element according to a probability defined by the relative weight of objects from the tree and returns it

Returns:

a sampled element

poll

public T poll()

Samples an element according to a probability defined by the relative weight of objects, removes it from the tree, and returns it.

Returns:

a sampled element

insertHelper

protected void insertHelper(StochasticTree.STNode node,
                double w,
                T el)

Helper recursive method for inserting an element

Parameters:

node - the node from which to insert the element

w - the weight of the element

el - the element to be inserted

percolateWeightChange

protected void percolateWeightChange(StochasticTree.STNode node,
                         double delta)

A recursive method for percolating a weight change of a node

Parameters:

node - the node whose weight change should be percolated

delta -

removeHelper

protected void removeHelper(StochasticTree.STNode node)

A recursive method for removing a node

Parameters:

node - the node to be removed

sampleHelper

protected StochasticTree.STNode sampleHelper(StochasticTree.STNode node,
                                 double v)

A recursive method for performing sampling

Parameters:

node - the node from which to sample

v - the random value used to determine which direction to go

Returns:

a sampled node

main

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

Demos how to use this class

Parameters:

args - empty

test2

public static void test2()

An example usage

test1

public static void test1()

Another example usage