A class that represents a two dimensional K-d Tree (2-d Tree). More...

#include <Index.h>

Public Types
typedef KdTreeNode::kdData	kdData
	Export data type. More...

typedef KdTreeNode::kdDataItem	kdDataItem
	Export data item type. More...

typedef KdTreeNode::kdDataTag	kdDataTag
	Export data type. More...

typedef KdTreeNode::kdKey	kdKey
	Export key type. More...

Public Member Functions
void	buildOptimized (std::vector< std::pair< kdKey, kdDataItem > > &dataSet)
	It inserts the data in the tree and and keeps it balanced: the kdsort algorithm must be called before. More...

void	clear ()
	It clears all tree nodes. More...

const te::gm::Envelope &	getMBR () const
	It gets the minimum bounding box of all elements in the tree. More...

	Index (const te::gm::Envelope &mbr)
	Constructor. More...

void	insert (const kdKey &key, const kdDataItem &item)
	It inserts the data with a given key in tree. More...

bool	isEmpty () const
	It returns true if the tree is empty and false otherwise. More...

void	search (const te::gm::Envelope &e, std::vector< KdTreeNode * > &report) const
	Range search query. More...

void	setMBR (const te::gm::Envelope &mbr)
	It sets the minimum bounding box of all elements in the tree. More...

const std::size_t &	size () const
	It returns the number of tree nodes. More...

	~Index ()
	Destructor. More...

Private Member Functions
KdTreeNode *	buildOptimized (std::vector< std::pair< kdKey, kdDataItem > > &dataSet, const std::size_t &first, const std::size_t &last)
	It builds the tree recursively. More...

void	erase (KdTreeNode *node)
	It Erases a node from the tree and all nodes below it. More...

	Index (const Index &rhs)
	No copy constructor allowed. More...

void	insertData (KdTreeNode *&node, const kdDataItem &data, const kd_node_m_datasingle_tag &)
	It inserts data for single nodes, i.e. nodes that stores only one element. More...

Index &	operator= (const Index &rhs)
	No assignment operator allowed. More...

void	search (const te::gm::Envelope &e, KdTreeNode node, const char &level, std::vector< KdTreeNode > &report) const
	It inserts data for set nodes, i.e., nodes that may stores many element. More...

Private Attributes
te::gm::Envelope	m_mbr
	Minimum bounding box of all nodes. More...

KdTreeNode *	m_root
	Pointer to the root node. More...

std::size_t	m_size
	The size of the K-d Tree (number of nodes). More...

Detailed Description

template<class KdTreeNode>
class te::sam::kdtree::Index< KdTreeNode >

A class that represents a two dimensional K-d Tree (2-d Tree).

Note: This type of tree stores the data into nodes (not only in the leafs node).; This tree may be built by two ways: 1) Inserting each element in the tree. In this case the tree can becomes unbalanced, but in practical cases this is not the expected, and is the best way to construct the tree (faster way). 2) Passing a container with pairs (key/data-item) and using the method buildOptimized after calling kdsort. The tree built this way is almost balanced but will be construct in time O(N log N). Warning: In this case items with the same key will be stores in different nodes!; This type of tree may be of special interest of EXTENT SEARCH QUERIES.; If the node type is kd_node_data_single_tag than NodeData and NodeDataItem are the same types. And if one entry with the same key already exist, so they will be overwrite.; If the node type is kd_node_data_set_tag than NodeData mus have a method called push_back(NodeDataItem) that permits to store elements with the same key in the node.

Definition at line 68 of file Index.h.

Member Typedef Documentation

template<class KdTreeNode >

typedef KdTreeNode::kdData te::sam::kdtree::Index< KdTreeNode >::kdData

Export data type.

Definition at line 76 of file Index.h.

template<class KdTreeNode >

typedef KdTreeNode::kdDataItem te::sam::kdtree::Index< KdTreeNode >::kdDataItem

Export data item type.

Definition at line 79 of file Index.h.

template<class KdTreeNode >

typedef KdTreeNode::kdDataTag te::sam::kdtree::Index< KdTreeNode >::kdDataTag

Export data type.

Definition at line 82 of file Index.h.

template<class KdTreeNode >

typedef KdTreeNode::kdKey te::sam::kdtree::Index< KdTreeNode >::kdKey

Export key type.

Definition at line 73 of file Index.h.

Constructor & Destructor Documentation

template<class KdTreeNode >

te::sam::kdtree::Index< KdTreeNode >::Index ( const te::gm::Envelope & mbr )

inline

Constructor.

Definition at line 85 of file Index.h.

Referenced by te::sam::kdtree::Index< KdTreeNode >::buildOptimized().

template<class KdTreeNode >

te::sam::kdtree::Index< KdTreeNode >::~Index ( )

inline

Destructor.

Definition at line 93 of file Index.h.

References te::sam::kdtree::Index< KdTreeNode >::clear().

template<class KdTreeNode >

te::sam::kdtree::Index< KdTreeNode >::Index ( const Index< KdTreeNode > & rhs )

private

No copy constructor allowed.

Parameters

rhs	The other index.

Member Function Documentation

template<class KdTreeNode >

void te::sam::kdtree::Index< KdTreeNode >::buildOptimized ( std::vector< std::pair< kdKey, kdDataItem > > & dataSet )

inline

It inserts the data in the tree and and keeps it balanced: the kdsort algorithm must be called before.

Definition at line 137 of file Index.h.

References te::sam::kdtree::Index< KdTreeNode >::m_root.

Referenced by te::sam::kdtree::Index< KdTreeNode >::buildOptimized().

template<class KdTreeNode >

KdTreeNode* te::sam::kdtree::Index< KdTreeNode >::buildOptimized	(	std::vector< std::pair< kdKey, kdDataItem > > &	dataSet,
		const std::size_t &	first,
		const std::size_t &	last
	)

inlineprivate

It builds the tree recursively.

Definition at line 181 of file Index.h.

References te::sam::kdtree::Index< KdTreeNode >::buildOptimized(), te::sam::kdtree::Index< KdTreeNode >::Index(), te::sam::kdtree::Index< KdTreeNode >::m_size, and te::sam::kdtree::Index< KdTreeNode >::operator=().

template<class KdTreeNode >

void te::sam::kdtree::Index< KdTreeNode >::clear ( )

inline

It clears all tree nodes.

Definition at line 99 of file Index.h.

References te::sam::kdtree::Index< KdTreeNode >::erase(), te::sam::kdtree::Index< KdTreeNode >::m_root, and te::sam::kdtree::Index< KdTreeNode >::m_size.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::~AdaptativeIndex(), and te::sam::kdtree::Index< KdTreeNode >::~Index().

template<class KdTreeNode >

void te::sam::kdtree::Index< KdTreeNode >::erase ( KdTreeNode * node )

inlineprivate

It Erases a node from the tree and all nodes below it.

Definition at line 153 of file Index.h.

Referenced by te::sam::kdtree::Index< KdTreeNode >::clear(), te::sam::kdtree::AdaptativeIndex< KdTreeNode >::clear(), and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::erase().

template<class KdTreeNode >

const te::gm::Envelope& te::sam::kdtree::Index< KdTreeNode >::getMBR ( ) const

inline

It gets the minimum bounding box of all elements in the tree.

Definition at line 128 of file Index.h.

References te::sam::kdtree::Index< KdTreeNode >::insert(), and te::sam::kdtree::Index< KdTreeNode >::m_mbr.

template<class KdTreeNode >

void te::sam::kdtree::Index< KdTreeNode >::insert	(	const kdKey &	key,
		const kdDataItem &	item
	)

inline

It inserts the data with a given key in tree.

Definition at line 224 of file Index.h.

References te::sam::kdtree::Index< KdTreeNode >::insertData(), te::sam::kdtree::Index< KdTreeNode >::m_root, and te::sam::kdtree::Index< KdTreeNode >::m_size.

Referenced by te::sam::kdtree::Index< KdTreeNode >::getMBR().

template<class KdTreeNode >

void te::sam::kdtree::Index< KdTreeNode >::insertData	(	KdTreeNode *&	node,
		const kdDataItem &	data,
		const kd_node_m_datasingle_tag &
	)

inlineprivate

It inserts data for single nodes, i.e. nodes that stores only one element.

Definition at line 165 of file Index.h.

References te::sam::kdtree::Index< KdTreeNode >::search().

Referenced by te::sam::kdtree::Index< KdTreeNode >::insert().

template<class KdTreeNode >

bool te::sam::kdtree::Index< KdTreeNode >::isEmpty ( ) const

inline

It returns true if the tree is empty and false otherwise.

Definition at line 116 of file Index.h.

References te::sam::kdtree::Index< KdTreeNode >::m_root.

template<class KdTreeNode >

Index& te::sam::kdtree::Index< KdTreeNode >::operator= ( const Index< KdTreeNode > & rhs )

private

No assignment operator allowed.

Parameters

rhs	The other index.

Returns: A reference for this.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::average(), and te::sam::kdtree::Index< KdTreeNode >::buildOptimized().

template<class KdTreeNode >

void te::sam::kdtree::Index< KdTreeNode >::search	(	const te::gm::Envelope &	e,
		std::vector< KdTreeNode * > &	report
	)		const

inline

Range search query.

Definition at line 144 of file Index.h.

References te::sam::kdtree::Index< KdTreeNode >::m_root.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::erase(), te::sam::kdtree::Index< KdTreeNode >::insertData(), te::sam::kdtree::Index< KdTreeNode >::search(), and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::search().

template<class KdTreeNode >

void te::sam::kdtree::Index< KdTreeNode >::search	(	const te::gm::Envelope &	e,
		KdTreeNode *	node,
		const char &	level,
		std::vector< KdTreeNode * > &	report
	)		const

inlineprivate

It inserts data for set nodes, i.e., nodes that may stores many element.

Recursive range query.

Definition at line 310 of file Index.h.

References te::gm::Envelope::m_llx, te::gm::Envelope::m_lly, te::gm::Envelope::m_urx, te::gm::Envelope::m_ury, and te::sam::kdtree::Index< KdTreeNode >::search().

template<class KdTreeNode >

void te::sam::kdtree::Index< KdTreeNode >::setMBR ( const te::gm::Envelope & mbr )

inline

It sets the minimum bounding box of all elements in the tree.

Definition at line 122 of file Index.h.

References te::sam::kdtree::Index< KdTreeNode >::m_mbr.

template<class KdTreeNode >

const std::size_t& te::sam::kdtree::Index< KdTreeNode >::size ( ) const

inline

It returns the number of tree nodes.

Definition at line 110 of file Index.h.

References te::sam::kdtree::Index< KdTreeNode >::m_size.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::average(), te::sam::kdtree::AdaptativeIndex< KdTreeNode >::build(), te::sam::kdtree::AdaptativeIndex< KdTreeNode >::setBucketSize(), and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::update().

Member Data Documentation

template<class KdTreeNode >

te::gm::Envelope te::sam::kdtree::Index< KdTreeNode >::m_mbr

private

Minimum bounding box of all nodes.

Definition at line 219 of file Index.h.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::build(), te::sam::kdtree::Index< KdTreeNode >::getMBR(), te::sam::kdtree::AdaptativeIndex< KdTreeNode >::getMBR(), te::sam::kdtree::Index< KdTreeNode >::setMBR(), and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::setMBR().

template<class KdTreeNode >

KdTreeNode* te::sam::kdtree::Index< KdTreeNode >::m_root

private

Pointer to the root node.

Definition at line 218 of file Index.h.

template<class KdTreeNode >

std::size_t te::sam::kdtree::Index< KdTreeNode >::m_size

private

The size of the K-d Tree (number of nodes).

Definition at line 220 of file Index.h.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::build(), te::sam::kdtree::Index< KdTreeNode >::buildOptimized(), te::sam::kdtree::Index< KdTreeNode >::clear(), te::sam::kdtree::AdaptativeIndex< KdTreeNode >::clear(), te::sam::kdtree::Index< KdTreeNode >::insert(), te::sam::kdtree::Index< KdTreeNode >::size(), and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::size().

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

/home/castejon/castejon_files/develop/terralib5/git_master/src/terralib/sam/kdtree/Index.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<class KdTreeNode> class te::sam::kdtree::Index< KdTreeNode >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class KdTreeNode>
class te::sam::kdtree::Index< KdTreeNode >