lti::kdTree< T, D, U >::node Class Reference

Class of nodes of the kd-tree. More...

#include <ltiKdTree.h>

Inheritance diagram for lti::kdTree< T, D, U >::node:

[legend]

Collaboration diagram for lti::kdTree< T, D, U >::node:

[legend]

List of all members.

Public Types
typedef std::vector< element * >	points_type
Public Member Functions
	node ()
	node (const node &other)
	~node ()
void	add (element *f)
bool	isLeaf () const
node &	copy (const node &other)
node &	operator= (const node &other)
node *	clone () const
virtual bool	read (ioHandler &handler, const bool complete=true)
virtual bool	write (ioHandler &handler, const bool complete=true) const
Public Attributes
Attributes

points_type	points
node *	left
node *	right
int	splitDim
value_type	partition
Protected Member Functions
void	clearPoints ()
void	subdivide (const int maxCount, int &levels, int &leaves)
int	getDimWithHighestVariance () const
value_type	getMedianVal (const int searchDim) const
bool	getPoint (const T &key, element &elem) const
bool	getPoint (const T &key, std::list< element > &elems) const
void	add (std::list< element * > &pts)

Detailed Description

template<class T, class D = int, class U = l2SquareDistantor<T>>
class lti::kdTree< T, D, U >::node

Class of nodes of the kd-tree.

Implementation must be here due to MS VC++ bug

Member Typedef Documentation

template<class T, class D = int, class U = l2SquareDistantor<T>>

typedef std::vector<element*> lti::kdTree< T, D, U >::node::points_type

type used for the container of elements.

A std::vector is for the search much more appropriate because the access through iterators is about a factor 5 faster than the std::list type.

Constructor & Destructor Documentation

template<class T, class D = int, class U = l2SquareDistantor<T>>

lti::kdTree< T, D, U >::node::node ( ) [inline]

constructor

Referenced by lti::kdTree< T, D, U >::node::clone(), lti::kdTree< T, D, U >::node::read(), and lti::kdTree< T, D, U >::node::subdivide().

template<class T, class D = int, class U = l2SquareDistantor<T>>

lti::kdTree< T, D, U >::node::node ( const node & other ) [inline]

copy constructor.

Makes a deep copy, i.e. the pointers will be different

References lti::kdTree< T, D, U >::node::copy().

template<class T, class D = int, class U = l2SquareDistantor<T>>

lti::kdTree< T, D, U >::node::~node ( ) [inline]

destructor

References lti::kdTree< T, D, U >::node::clearPoints(), lti::kdTree< T, D, U >::node::left, and lti::kdTree< T, D, U >::node::right.

Member Function Documentation

template<class T, class D = int, class U = l2SquareDistantor<T>>

void lti::kdTree< T, D, U >::node::add ( std::list< element * > & pts ) [inline, protected]

insert all elements in the given list into the internal elements vector.

The pointed elements will be inserted as they are (without copying), and the memory managment is controled by this node itself.

The dimensionality of each element MUST be equal than the one of the first added element.

References lti::kdTree< T, D, U >::node::points.

template<class T, class D = int, class U = l2SquareDistantor<T>>

void lti::kdTree< T, D, U >::node::add ( element * f ) [inline]

insert a pointer to an element into the points list.

The pointed element will be inserted as is (without copying), and the memory managment is controled by the node itself.

The dimensionality of each element MUST be equal than the one of the first element added.

References lti::kdTree< T, D, U >::node::points.

Referenced by lti::kdTree< T, D, U >::node::subdivide().

template<class T, class D = int, class U = l2SquareDistantor<T>>

void lti::kdTree< T, D, U >::node::clearPoints ( ) [inline, protected]

deep clear points

References lti::kdTree< T, D, U >::node::points.

Referenced by lti::kdTree< T, D, U >::node::copy(), lti::kdTree< T, D, U >::node::read(), and lti::kdTree< T, D, U >::node::~node().

template<class T, class D = int, class U = l2SquareDistantor<T>>

node* lti::kdTree< T, D, U >::node::clone ( ) const [inline]

clone method

References lti::kdTree< T, D, U >::node::node().

Referenced by lti::kdTree< T, D, U >::node::copy().

template<class T, class D = int, class U = l2SquareDistantor<T>>

node& lti::kdTree< T, D, U >::node::copy ( const node & other ) [inline]

copy method

Reimplemented from lti::ioObject.

References lti::kdTree< T, D, U >::node::clearPoints(), lti::kdTree< T, D, U >::node::clone(), lti::kdTree< T, D, U >::node::left, lti::kdTree< T, D, U >::node::partition, lti::kdTree< T, D, U >::node::points, lti::kdTree< T, D, U >::node::right, and lti::kdTree< T, D, U >::node::splitDim.

Referenced by lti::kdTree< T, D, U >::node::node(), and lti::kdTree< T, D, U >::node::operator=().

template<class T, class D = int, class U = l2SquareDistantor<T>>

int lti::kdTree< T, D, U >::node::getDimWithHighestVariance ( ) const [inline, protected]

get the dimension of the data with the highest variance.

We assume the whole data set to be considered is located at the points vector.

References lti::kdTree< T, D, U >::node::points.

Referenced by lti::kdTree< T, D, U >::node::subdivide().

template<class T, class D = int, class U = l2SquareDistantor<T>>

value_type lti::kdTree< T, D, U >::node::getMedianVal ( const int searchDim ) const [inline, protected]

get the median value at the given search dimension

Parameters:

searchDim

search dimension

Returns:: the median of the given dimension

References lti::quickMedian< T >::apply(), and lti::kdTree< T, D, U >::node::points.

Referenced by lti::kdTree< T, D, U >::node::subdivide().

template<class T, class D = int, class U = l2SquareDistantor<T>>

bool lti::kdTree< T, D, U >::node::getPoint	(	const T &	key,
		std::list< element > &	elems
	)			const `[inline, protected]`

search for exactly the given key in the list of elements.

If found, return true, otherwise return false and leave the element instance untouched.

For floating types this method usually returns false, because the exact match of the key is very unprobable. This method is therefore used mostly for integer value_types

References lti::kdTree< T, D, U >::node::points.

template<class T, class D = int, class U = l2SquareDistantor<T>>

bool lti::kdTree< T, D, U >::node::getPoint	(	const T &	key,
		element &	elem
	)			const `[inline, protected]`

search for exactly the given key in the list of elements.

If found, return true, otherwise return false and leave the element instance untouched.

For floating types this method usually returns false, because the exact match of the key is very unprobable. This method is therefore used mostly for integer value_types

References lti::kdTree< T, D, U >::node::points.

template<class T, class D = int, class U = l2SquareDistantor<T>>

bool lti::kdTree< T, D, U >::node::isLeaf ( ) const [inline]

return true if this node is a leaf.

References lti::kdTree< T, D, U >::node::points.

template<class T, class D = int, class U = l2SquareDistantor<T>>

node& lti::kdTree< T, D, U >::node::operator= ( const node & other ) [inline]

copy method

Reimplemented from lti::ioObject.

References lti::kdTree< T, D, U >::node::copy().

template<class T, class D = int, class U = l2SquareDistantor<T>>

virtual bool lti::kdTree< T, D, U >::node::read	(	ioHandler &	handler,
		const bool	complete = `true`
	)			`[inline, virtual]`

read the parameters from the given ioHandler

Parameters:

	handler	the ioHandler to be used
	complete	if true (the default) the enclosing begin/end will be also read, otherwise only the data block will be read.

Returns:: true if write was successful

Reimplemented from lti::ioObject.

Referenced by lti::kdTree< T, D, U >::node::read().

template<class T, class D = int, class U = l2SquareDistantor<T>>

void lti::kdTree< T, D, U >::node::subdivide	(	const int	maxCount,
		int &	levels,
		int &	leaves
	)			`[inline, protected]`

split the data stored at this node considering the axis with the highest variance.

Parameters:

	maxCount	maximum bucket size (how many elements are allowed to be in a leaf node)
	levels	number of levels required until now for this tree.
	leaves	at the end this variable (which should be initialized with zero externally) contains the number of leaves in the tree

References lti::kdTree< T, D, U >::node::add(), lti::kdTree< T, D, U >::node::getDimWithHighestVariance(), lti::kdTree< T, D, U >::node::getMedianVal(), lti::kdTree< T, D, U >::node::left, lti::max(), lti::kdTree< T, D, U >::node::node(), lti::kdTree< T, D, U >::node::partition, lti::kdTree< T, D, U >::node::points, lti::kdTree< T, D, U >::node::right, lti::kdTree< T, D, U >::node::splitDim, and lti::kdTree< T, D, U >::node::subdivide().

Referenced by lti::kdTree< T, D, U >::node::subdivide().

template<class T, class D = int, class U = l2SquareDistantor<T>>

virtual bool lti::kdTree< T, D, U >::node::write	(	ioHandler &	handler,
		const bool	complete = `true`
	)			const `[inline, virtual]`

write the parameters in the given ioHandler

Parameters:

	handler	the ioHandler to be used
	complete	if true (the default) the enclosing begin/end will be also written, otherwise only the data block will be written.

Returns:: true if write was successful

Reimplemented from lti::ioObject.

References lti::kdTree< T, D, U >::node::left, lti::kdTree< T, D, U >::node::partition, lti::kdTree< T, D, U >::node::points, lti::kdTree< T, D, U >::node::right, lti::kdTree< T, D, U >::node::splitDim, lti::kdTree< T, D, U >::node::write(), lti::ioHandler::write(), lti::ioHandler::writeBegin(), lti::ioHandler::writeDataSeparator(), lti::ioHandler::writeEnd(), lti::ioHandler::writeEOL(), lti::ioHandler::writeKeyValueSeparator(), and lti::ioHandler::writeSymbol().

Referenced by lti::kdTree< T, D, U >::node::write().

Member Data Documentation

template<class T, class D = int, class U = l2SquareDistantor<T>>

node* lti::kdTree< T, D, U >::node::left

the left subtree (lower coordinate) from the split plane

Referenced by lti::kdTree< T, D, U >::node::copy(), lti::kdTree< T, D, U >::node::read(), lti::kdTree< T, D, U >::node::subdivide(), lti::kdTree< T, D, U >::node::write(), and lti::kdTree< T, D, U >::node::~node().

template<class T, class D = int, class U = l2SquareDistantor<T>>

value_type lti::kdTree< T, D, U >::node::partition

Value at the split dimension where the splitting takes place.

Usually this value corresponds to the median at the given split dimension.

Referenced by lti::kdTree< T, D, U >::node::copy(), lti::kdTree< T, D, U >::node::read(), lti::kdTree< T, D, U >::node::subdivide(), and lti::kdTree< T, D, U >::node::write().

template<class T, class D = int, class U = l2SquareDistantor<T>>

points_type lti::kdTree< T, D, U >::node::points

Points stored in this node.

These are pointers to the data allocated in the kdTree class, this way the data can be "transfered" more efficiently between different nodes. The memory managment is done by this node.

Referenced by lti::kdTree< T, D, U >::node::add(), lti::kdTree< T, D, U >::node::clearPoints(), lti::kdTree< T, D, U >::node::copy(), lti::kdTree< T, D, U >::node::getDimWithHighestVariance(), lti::kdTree< T, D, U >::node::getMedianVal(), lti::kdTree< T, D, U >::node::getPoint(), lti::kdTree< T, D, U >::node::isLeaf(), lti::kdTree< T, D, U >::node::read(), lti::kdTree< T, D, U >::node::subdivide(), and lti::kdTree< T, D, U >::node::write().