implements a binary tree of partial sums for sampling from discrete distributions with arbitrary weight More...

#include <mpblocks/btps/tree.h>

Public Types
typedef Traits::NodeOps	NodeOps

typedef Traits::NodeRef	NodeRef

Public Member Functions
void	clear ()
	clear out the tree (does not free nodes) More...

template<typename T >
NodeRef	findInterval (T val)
	given `$` val [0,1] $, sample a node from the weighted distribution More...

void	generateDepthProfile (std::map< int, std::list< NodeRef > > &depthMap)
	fill `depthMap` with a list of nodes at each depth More...

void	insert (NodeRef x)
	insert a single node into the tree, `weight(x)` must be set, all other fields are initialized by the tree More...

void	remove (NodeRef x)
	remove node from the tree and maintain balance More...

NodeRef	root ()
	return the root node in the tree More...

size_t	size ()
	return the count of nodes in the tree More...

auto	sum () -> decltype(ops_.CumulativeWeight(root_))
	return the total weight of all nodes in the tree More...

	Tree (NodeRef Nil)
	initialize a tree using Nil as the sentinal object More...

double	validateTree ()
	return the largest difference between `cum(x)` and the computed value over all nodes in the tree More...

Private Member Functions
auto	count (NodeRef N) -> decltype(ops_.Count(N))

auto	cum (NodeRef N) -> decltype(ops_.CumulativeWeight(N))

NodeRef	deepestLeaf (NodeRef p)
	find the deepest leaf in a subtree More...

template<typename T >
NodeRef	findInterval (NodeRef x, T val)
	given `$` val [0,1] $, sample a node from the weighted distribution over the subtree rooted at `x` More...

void	insert (NodeRef p, NodeRef x)
	recursively insert `x` in the subtree rooted at `p` More...

bool	isLeaf (NodeRef x)
	true if `x` is a leaf node (i.e. both children are Nil) More...

NodeRef &	left (NodeRef N)

NodeRef &	parent (NodeRef N)

void	removeLeaf (NodeRef x)
	remove a leaf node from the tree More...

NodeRef &	right (NodeRef N)

void	swap (NodeRef a, NodeRef b)
	swaps everything but the weight and cumulative weight More...

void	update (NodeRef x)
	update a node's count and cumulative weight by summing the count/weight of itself with the cumulative count/weight of it's children More...

void	updateAncestry (NodeRef p)
	walk the tree along the parent path from p to the root and update all nodes on that path More...

double	validateNode (NodeRef x)
	return the larger of the error of `cum(x)` or the error of it's children More...

auto	weight (NodeRef N) -> decltype(ops_.Weight(N))

Private Attributes
NodeRef	nil_

NodeOps	ops_

NodeRef	root_

Detailed Description

template<class Traits>
class mpblocks::btps::Tree< Traits >

implements a binary tree of partial sums for sampling from discrete distributions with arbitrary weight

Definition at line 44 of file tree.h.

Member Typedef Documentation

template<class Traits >

typedef Traits::NodeOps mpblocks::btps::Tree< Traits >::NodeOps

Definition at line 47 of file tree.h.

template<class Traits >

typedef Traits::NodeRef mpblocks::btps::Tree< Traits >::NodeRef

Definition at line 46 of file tree.h.

Constructor & Destructor Documentation

template<class Traits >

mpblocks::btps::Tree< Traits >::Tree ( NodeRef Nil )

inline

initialize a tree using Nil as the sentinal object

Nil and NodeOps must be such that the following are true

op	condition
weight(Nil)	= 0
cum(Nil)	= 0
count(Nil)	= 0
left(Nil)	= Nil
right(Nil)	= Nil
parent(Nil)	= Nil

Definition at line 85 of file tree.h.

Member Function Documentation

template<class Traits >

void mpblocks::btps::Tree< Traits >::clear ( )

inline

clear out the tree (does not free nodes)

Definition at line 102 of file tree.h.

template<class Traits >

auto mpblocks::btps::Tree< Traits >::count ( NodeRef N ) -> decltype(ops_.Count(N))

inlineprivate

Definition at line 58 of file tree.h.

template<class Traits >

auto mpblocks::btps::Tree< Traits >::cum ( NodeRef N ) -> decltype(ops_.CumulativeWeight(N))

inlineprivate

Definition at line 62 of file tree.h.

template<class Traits >

NodeRef mpblocks::btps::Tree< Traits >::deepestLeaf ( NodeRef p )

inlineprivate

find the deepest leaf in a subtree

Definition at line 155 of file tree.h.

template<class Traits >

template<typename T >

NodeRef mpblocks::btps::Tree< Traits >::findInterval	(	NodeRef	x,
		T	val
	)

inlineprivate

given $ val [0,1] $, sample a node from the weighted distribution over the subtree rooted at x

Definition at line 242 of file tree.h.

template<class Traits >

template<typename T >

NodeRef mpblocks::btps::Tree< Traits >::findInterval ( T val )

inline

given $ val [0,1] $, sample a node from the weighted distribution

Definition at line 345 of file tree.h.

template<class Traits >

void mpblocks::btps::Tree< Traits >::generateDepthProfile ( std::map< int, std::list< NodeRef > > & depthMap )

inline

fill depthMap with a list of nodes at each depth

Definition at line 329 of file tree.h.

template<class Traits >

void mpblocks::btps::Tree< Traits >::insert	(	NodeRef	p,
		NodeRef	x
	)

inlineprivate

recursively insert x in the subtree rooted at p

Definition at line 117 of file tree.h.

template<class Traits >

void mpblocks::btps::Tree< Traits >::insert ( NodeRef x )

inline

insert a single node into the tree, weight(x) must be set, all other fields are initialized by the tree

Definition at line 281 of file tree.h.

template<class Traits >

bool mpblocks::btps::Tree< Traits >::isLeaf ( NodeRef x )

inlineprivate

true if x is a leaf node (i.e. both children are Nil)

Definition at line 164 of file tree.h.

template<class Traits >

NodeRef& mpblocks::btps::Tree< Traits >::left ( NodeRef N )

inlineprivate

Definition at line 55 of file tree.h.

template<class Traits >

NodeRef& mpblocks::btps::Tree< Traits >::parent ( NodeRef N )

inlineprivate

Definition at line 54 of file tree.h.

template<class Traits >

void mpblocks::btps::Tree< Traits >::remove ( NodeRef x )

inline

remove node from the tree and maintain balance

Definition at line 295 of file tree.h.

template<class Traits >

void mpblocks::btps::Tree< Traits >::removeLeaf ( NodeRef x )

inlineprivate

remove a leaf node from the tree

Definition at line 213 of file tree.h.

template<class Traits >

NodeRef& mpblocks::btps::Tree< Traits >::right ( NodeRef N )

inlineprivate

Definition at line 56 of file tree.h.

template<class Traits >

NodeRef mpblocks::btps::Tree< Traits >::root ( )

inline

return the root node in the tree

Definition at line 94 of file tree.h.

template<class Traits >

size_t mpblocks::btps::Tree< Traits >::size ( )

inline

return the count of nodes in the tree

Definition at line 105 of file tree.h.

template<class Traits >

auto mpblocks::btps::Tree< Traits >::sum ( ) -> decltype(ops_.CumulativeWeight(root_))

inline

return the total weight of all nodes in the tree

Definition at line 97 of file tree.h.

template<class Traits >

void mpblocks::btps::Tree< Traits >::swap	(	NodeRef	a,
		NodeRef	b
	)

inlineprivate

swaps everything but the weight and cumulative weight

Definition at line 167 of file tree.h.

template<class Traits >

void mpblocks::btps::Tree< Traits >::update ( NodeRef x )

inlineprivate

update a node's count and cumulative weight by summing the count/weight of itself with the cumulative count/weight of it's children

Definition at line 111 of file tree.h.

template<class Traits >

void mpblocks::btps::Tree< Traits >::updateAncestry ( NodeRef p )

inlineprivate

walk the tree along the parent path from p to the root and update all nodes on that path

Definition at line 142 of file tree.h.

template<class Traits >

double mpblocks::btps::Tree< Traits >::validateNode ( NodeRef x )

inlineprivate

return the larger of the error of cum(x) or the error of it's children

Definition at line 267 of file tree.h.

template<class Traits >

double mpblocks::btps::Tree< Traits >::validateTree ( )

inline

return the largest difference between cum(x) and the computed value over all nodes in the tree

Definition at line 321 of file tree.h.

template<class Traits >

auto mpblocks::btps::Tree< Traits >::weight ( NodeRef N ) -> decltype(ops_.Weight(N))

inlineprivate

Definition at line 66 of file tree.h.

Member Data Documentation

template<class Traits >

NodeRef mpblocks::btps::Tree< Traits >::nil_

private

Definition at line 50 of file tree.h.

template<class Traits >

NodeOps mpblocks::btps::Tree< Traits >::ops_

private

Definition at line 52 of file tree.h.

template<class Traits >

NodeRef mpblocks::btps::Tree< Traits >::root_

private

Definition at line 51 of file tree.h.

The documentation for this class was generated from the following file:

include/mpblocks/btps/tree.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<class Traits> class mpblocks::btps::Tree< Traits >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class Traits>
class mpblocks::btps::Tree< Traits >