StochasticTree

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.

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

All Methods Static Methods Instance Methods Concrete 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 - the random generator to use
  - 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 - the element to remove
  - 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 - the change in weight
  - 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

Class StochasticTree<T>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

root

nodeMap

rand

Constructor Detail

StochasticTree

StochasticTree

Method Detail

init

setRandom

size

getStoredEntry

insert

changeWeight

remove

sample

poll

insertHelper

percolateWeightChange

removeHelper

sampleHelper

main

test2

test1