nvbio::SumTree< Iterator > Struct Template Reference

Detailed description

template< typename Iterator>
struct nvbio::SumTree< Iterator >

Given an array of length N, it's possible to build a binary tree on top of it with 2*N-1 nodes, where each internal node encodes the sum of the values associated with its leaves. The original N cells will be the leaves of such a tree. This class encodes such a tree, allowing incremental modifications of the values associated with the leaves. If N is not a power of 2, the base array is conceptually padded with zeros.

An example usage of this class is to sample CDFs that are continuously updated over time.

Definition at line 108 of file sum_tree.h.

#include <sum_tree.h>

Public Types
typedef Iterator	iterator_type
typedef std::iterator_traits < Iterator >::value_type	value_type

Public Methods
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE	SumTree (const uint32 size, iterator_type cells)
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32	size () const
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32	padded_size () const
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32	nodes () const
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	setup (const value_type zero=value_type(0))
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	add (const uint32 i, const value_type v)
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	set (const uint32 i, const value_type v)
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE value_type	sum () const
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE value_type	cell (const uint32 i) const

Static Public Methods
NVBIO_FORCEINLINE static NVBIO_HOST_DEVICE uint32	node_count (const uint32 size)

Member Typedef Documentation

template<typename Iterator>

typedef Iterator nvbio::SumTree< Iterator >::iterator_type

Definition at line 110 of file sum_tree.h.

template<typename Iterator>

typedef std::iterator_traits<Iterator>::value_type nvbio::SumTree< Iterator >::value_type

Definition at line 111 of file sum_tree.h.

Constructor & Destructor Documentation

template<typename Iterator >

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE nvbio::SumTree< Iterator >::SumTree	(	const uint32	size,
		iterator_type	cells
	)

constructor

Definition at line 51 of file sum_tree_inl.h.

Member Function Documentation

template<typename Iterator >

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void nvbio::SumTree< Iterator >::add	(	const uint32	i,
		const value_type	v
	)

increment a cell's value

Definition at line 88 of file sum_tree_inl.h.

template<typename Iterator>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE value_type nvbio::SumTree< Iterator >::cell ( const uint32  i) const

inline

return a cell's value

Definition at line 161 of file sum_tree.h.

template<typename Iterator >

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 nvbio::SumTree< Iterator >::node_count ( const uint32  size)

static

return the number of nodes corresponding to a given number of leaves

Definition at line 36 of file sum_tree_inl.h.

template<typename Iterator>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 nvbio::SumTree< Iterator >::nodes ( ) const

inline

return the total node count

Definition at line 136 of file sum_tree.h.

template<typename Iterator>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 nvbio::SumTree< Iterator >::padded_size ( ) const

inline

return the number of leaves, padded to the nearest power of 2

Definition at line 131 of file sum_tree.h.

template<typename Iterator >

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void nvbio::SumTree< Iterator >::set	(	const uint32	i,
		const value_type	v
	)

reset a cell's value

Definition at line 104 of file sum_tree_inl.h.

template<typename Iterator >

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void nvbio::SumTree< Iterator >::setup

(

const value_type

zero = value_type(0))

setup the tree structure

Definition at line 64 of file sum_tree_inl.h.

template<typename Iterator>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 nvbio::SumTree< Iterator >::size ( void  ) const

inline

return the number of leaves

Definition at line 126 of file sum_tree.h.

template<typename Iterator>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE value_type nvbio::SumTree< Iterator >::sum ( ) const

inline

return the total tree sum

Definition at line 156 of file sum_tree.h.

---

The documentation for this struct was generated from the following files:

• E:/git/nvbio/nvbio/basic/sum_tree.h
• E:/git/nvbio/nvbio/basic/sum_tree_inl.h