SBDTree Class Reference

Models a Separated Block Diagonal tree structure. More...

#include <SBDTree.hpp>

Inheritance diagram for SBDTree:

Public Member Functions
	SBDTree (std::vector< unsigned long int > &r_hierarchy, std::vector< unsigned long int > &c_hierarchy, std::vector< unsigned long int > &r_bounds, std::vector< unsigned long int > &c_bounds)
	Base constructor.
	SBDTree (std::vector< unsigned long int > &hierarchy, std::vector< unsigned long int > &r_bounds, std::vector< unsigned long int > &c_bounds)
	Base constructor. More...
	~SBDTree ()
	Base deconstructor. More...
void	getSeparatorBB (const unsigned long int index, unsigned long int &r_lo, unsigned long int &r_hi, unsigned long int &c_lo, unsigned long int &c_hi)
	Gets, from a separator node, the bounding box of the nonzeroes contained in the separator. More...
unsigned long int	up (const unsigned long int index)
	Returns the parent of a given node. More...
unsigned long int	left (const unsigned long int index)
	Returns the left child of a given node. More...
unsigned long int	right (const unsigned long int index)
	Returns the right child of a given node. More...
void	rowBounds (const unsigned long int index, unsigned long int &r_lo, unsigned long int &r_hi)
	Returns the row bounds corresponding to a given node. More...
void	columnBounds (const unsigned long int index, unsigned long int &c_lo, unsigned long int &c_hi)
	Returns the column bounds corresponding to a given node. More...
char	isLeaf (const unsigned long int index)
	Whether the given node is a leaf node.
unsigned long int	size ()
	Gets the number of nodes.
unsigned long int	getRoot ()
	Gets the root index.

Protected Member Functions
void	build (std::vector< unsigned long int > &hierarchy, std::vector< unsigned long int > &r_bounds, std::vector< unsigned long int > &c_bounds)
	Builds the SBD tree using three input vectors. More...

Protected Attributes
unsigned long int *	parent
	Array s.t. More...
unsigned long int *	left_child
	Array s.t. More...
unsigned long int *	right_child
	Array s.t. More...
unsigned long int *	r_lo
	Array s.t. More...
unsigned long int *	r_hi
	Array s.t. More...
unsigned long int *	c_lo
	Array s.t. More...
unsigned long int *	c_hi
	Array s.t. More...
unsigned long int	root
	Which node ID corresponds to the root. More...
unsigned long int	nodes
	The total number of tree nodes. More...
char	root_is_set
	Whether the root node is set. More...

Static Protected Attributes
static const unsigned long int	NO_SUCH_NODE = ULONG_MAX
	Integer corresponding to non-existing nodes. More...

Detailed Description

Models a Separated Block Diagonal tree structure.

Constructor & Destructor Documentation

SBDTree::SBDTree	(	std::vector< unsigned long int > &	hierarchy,
		std::vector< unsigned long int > &	r_bounds,
		std::vector< unsigned long int > &	c_bounds
	)

Base constructor.

Warning: avoids some assertions!

References build().

SBDTree::~SBDTree

(

)

Base deconstructor.

References c_hi, c_lo, left_child, parent, r_hi, r_lo, and right_child.

Member Function Documentation

void SBDTree::build ( std::vector< unsigned long int > &  hierarchy, std::vector< unsigned long int > &  r_bounds, std::vector< unsigned long int > &  c_bounds  )

protected

Builds the SBD tree using three input vectors.

Parameters

hierarchy	The SBD hierarchy vector.
r_bounds	The row bounds of each SBD block.
c_bounds	The column bounds of each SBD block.

References c_hi, c_lo, left_child, NO_SUCH_NODE, nodes, parent, r_hi, r_lo, right_child, root, and root_is_set.

Referenced by SBDTree().

void SBDTree::columnBounds	(	const unsigned long int	index,
		unsigned long int &	c_lo,
		unsigned long int &	c_hi
	)

Returns the column bounds corresponding to a given node.

Referenced by BlockOrderer< T >::induce(), BlockOrderer< T >::left_horizontal(), BlockOrderer< T >::lower_vertical(), BlockOrderer< T >::middle(), BlockOrderer< T >::right_horizontal(), and BlockOrderer< T >::upper_vertical().

void SBDTree::getSeparatorBB	(	const unsigned long int	index,
		unsigned long int &	r_lo,
		unsigned long int &	r_hi,
		unsigned long int &	c_lo,
		unsigned long int &	c_hi
	)

Gets, from a separator node, the bounding box of the nonzeroes contained in the separator.

Note that this is not the r_lo/hi,c_lo/hi of the node itself; those are the bounds of the row-wise and column-wise separators.

This is a logarithmic operation.

Parameters

index	The separator node ID.
r_lo	Where to store the lower row bound.
r_hi	Where to store the upper row bound.
c_lo	Where to store the lower column bound.
c_hi	Where to store the upper column bound.

Note that this is not the r_lo/hi,c_lo/hi of the node itself; those are the bounds of the row-wise and column-wise separators.

This is a logarithmic operation.

References left_child, NO_SUCH_NODE, and right_child.

Referenced by BlockOrderer< T >::left_horizontal(), BlockOrderer< T >::lower_vertical(), BlockOrderer< T >::middle(), BlockOrderer< T >::right_horizontal(), and BlockOrderer< T >::upper_vertical().

unsigned long int SBDTree::left

(

const unsigned long int

index

)

Returns the left child of a given node.

References left_child, and NO_SUCH_NODE.

Referenced by BlockOrderer< T >::traverse().

unsigned long int SBDTree::right

(

const unsigned long int

index

)

Returns the right child of a given node.

References NO_SUCH_NODE, and right_child.

Referenced by BlockOrderer< T >::traverse().

void SBDTree::rowBounds	(	const unsigned long int	index,
		unsigned long int &	r_lo,
		unsigned long int &	r_hi
	)

Returns the row bounds corresponding to a given node.

Referenced by BlockOrderer< T >::induce(), BlockOrderer< T >::left_horizontal(), BlockOrderer< T >::lower_vertical(), BlockOrderer< T >::middle(), BlockOrderer< T >::right_horizontal(), and BlockOrderer< T >::upper_vertical().

unsigned long int SBDTree::up

(

const unsigned long int

index

)

Returns the parent of a given node.

References NO_SUCH_NODE, and parent.

Referenced by BlockOrderer< T >::traverse().

Member Data Documentation

unsigned long int* SBDTree::c_hi

protected

Array s.t.

c_hi[i] returns the upper column bound of block i.

Referenced by build(), Upscaler< T >::getSubTree(), Upscaler< T >::Upscaler(), and ~SBDTree().

unsigned long int* SBDTree::c_lo

protected

Array s.t.

c_lo[i] returns the lower column bound of block i.

Referenced by build(), Upscaler< T >::getSubTree(), Upscaler< T >::Upscaler(), and ~SBDTree().

unsigned long int* SBDTree::left_child

protected

Array s.t.

left_child[i] returns the left child ID of block i.

Referenced by build(), getSeparatorBB(), Upscaler< T >::getSubTree(), isLeaf(), left(), Upscaler< T >::readout(), and ~SBDTree().

const unsigned long int SBDTree::NO_SUCH_NODE = ULONG_MAX

staticprotected

Integer corresponding to non-existing nodes.

Referenced by build(), Upscaler< T >::determineMinMax(), getSeparatorBB(), Upscaler< T >::getSubTree(), isLeaf(), left(), Upscaler< T >::treeIterator::next(), Upscaler< T >::treeInOrderIterator::next(), Upscaler< T >::treePostOrderIterator::next(), Upscaler< T >::readout(), right(), and up().

unsigned long int SBDTree::nodes

protected

The total number of tree nodes.

Referenced by build(), and size().

unsigned long int* SBDTree::parent

protected

Array s.t.

parent[i] returns the parent ID of block i.

Referenced by build(), Upscaler< T >::determineMinMax(), Upscaler< T >::getSubTree(), Upscaler< T >::readout(), up(), Upscaler< T >::Upscaler(), and ~SBDTree().

unsigned long int* SBDTree::r_hi

protected

Array s.t.

r_hi[i] returns the upper row bound of block i.

Referenced by build(), Upscaler< T >::getSubTree(), Upscaler< T >::Upscaler(), and ~SBDTree().

unsigned long int* SBDTree::r_lo

protected

Array s.t.

r_lo[i] returns the lower row bound of block i.

Referenced by build(), Upscaler< T >::getSubTree(), Upscaler< T >::Upscaler(), and ~SBDTree().

unsigned long int* SBDTree::right_child

protected

Array s.t.

right_child[i] returns the right child ID of block i.

Referenced by build(), getSeparatorBB(), Upscaler< T >::getSubTree(), isLeaf(), Upscaler< T >::readout(), right(), and ~SBDTree().

unsigned long int SBDTree::root

protected

Which node ID corresponds to the root.

Referenced by build(), getRoot(), Upscaler< T >::getSubTree(), and Upscaler< T >::Upscaler().

char SBDTree::root_is_set

protected

Whether the root node is set.

Referenced by build().

---

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

• SBDTree.hpp
• SBDTree.cpp