A node in a d_tree_point_locator search structure. More...

#include <d_tree_point_locator_node.h>

Friends
class	ptr_linked_pool< d_tree_point_locator_node< DC, DB > >

D_TREE_POINT_LOCATOR_NODE FACET
typedef sheaf::size_type	size_type
	An unsigned integral type used to represent sizes and capacities. More...

typedef singly_linked_list< const d_bounding_box< DC, DB > * >	box_list_type
	The type of box list. More...

box_list_type	_box_list
	The list of bounding boxes associated with this. More...

d_tree_point_locator_node< DC, DB > *	_branches [DEGREE]
	The branches of this node. More...

size_type	_branch_ct
	The number of non-null branches. More...

static const size_type	DEGREE = 1<<DC
	The number of elements in the branches array. More...

	d_tree_point_locator_node ()
	Default constructor. More...

	d_tree_point_locator_node (const d_tree_point_locator_node< DC, DB > &xother)
	Copy constructor. More...

d_tree_point_locator_node< DC, DB > &	operator= (const d_tree_point_locator_node< DC, DB > &xother)
	Assignment operator. More...

bool	operator== (const d_tree_point_locator_node< DC, DB > &xother)
	Equality operator. More...

	~d_tree_point_locator_node ()
	Destructor. More...

bool	invariant () const
	Class invariant. More...

d_tree_point_locator_node< DC, DB > *	branch (int xindex) const
	The xindex-th branch. More...

bool	is_leaf () const
	True if this node is a leaf node. More...

bool	is_empty () const
	True if box_list() is empty. More...

void	insert_box (const d_bounding_box< DC, DB > *xbox, d_tree_point_locator_path< DC, DB > &xpath)
	Inserts xbox in this or somewhere on one of its branches. More...

void	remove_box (const d_bounding_box< DC, DB > *xbox, d_tree_point_locator_path< DC, DB > &xpath)
	Removes xbox from this and its branches, recursively. More...

bool	contains_box (const d_bounding_box< DC, DB > *xbox, d_tree_point_locator_path< DC, DB > &xpath) const
	True if xbox is in the box list of this or its branches, recursively. More...

void	clear ()
	Clears all branches and all boxes from this. Warning: this function does not deallocate the branches and hence can leave allocated but unreachable branches. More...

const box_list_type &	box_list (d_tree_point_locator_path< DC, DB > &xpath) const
	The bounding boxes which intersect xpath. More...

const box_list_type &	box_list () const
	The bounding boxes which intersect this. More...

std::string *	to_string () const
	Get instance information as a string. More...

size_type	branch_ct () const
	The number of non-null branches. More...

static size_type	degree ()
	The maximum number of branches a node may have. More...

d_tree_point_locator_node< DC, DB > *	next () const
	The next node in the free list; intended for use only by class ptr_linked_pool. More...

void	put_next (d_tree_point_locator_node< DC, DB > *xnode)
	Sets the next node in the free list to xnode; intended for use only by class ptr_linked_pool. More...

Detailed Description

template<int DC, int DB>
class geometry::d_tree_point_locator_node< DC, DB >

A node in a d_tree_point_locator search structure.

Definition at line 60 of file d_tree_point_locator_node.h.

Member Typedef Documentation

◆ box_list_type

template<int DC, int DB>

typedef singly_linked_list<const d_bounding_box<DC, DB>*> geometry::d_tree_point_locator_node< DC, DB >::box_list_type

The type of box list.

Definition at line 150 of file d_tree_point_locator_node.h.

◆ size_type

template<int DC, int DB>

typedef sheaf::size_type geometry::d_tree_point_locator_node< DC, DB >::size_type

An unsigned integral type used to represent sizes and capacities.

Definition at line 74 of file d_tree_point_locator_node.h.

Constructor & Destructor Documentation

◆ d_tree_point_locator_node() [1/2]

template<int DC, int DB>

geometry::d_tree_point_locator_node< DC, DB >::d_tree_point_locator_node ( )

Default constructor.

Definition at line 62 of file d_tree_point_locator_node.impl.h.

◆ d_tree_point_locator_node() [2/2]

template<int DC, int DB>

geometry::d_tree_point_locator_node< DC, DB >::d_tree_point_locator_node ( const d_tree_point_locator_node< DC, DB > & xother )

Copy constructor.

Postcondition

*this == xother

Definition at line 84 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_node< DC, DB >::operator=().

◆ ~d_tree_point_locator_node()

template<int DC, int DB>

geometry::d_tree_point_locator_node< DC, DB >::~d_tree_point_locator_node ( )

Destructor.

Definition at line 157 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_node< DC, DB >::invariant().

Referenced by geometry::d_tree_point_locator_node< DC, DB >::operator==().

Member Function Documentation

◆ box_list() [1/2]

template<int DC, int DB>

const d_tree_point_locator_node< DC, DB >::box_list_type & geometry::d_tree_point_locator_node< DC, DB >::box_list ( d_tree_point_locator_path< DC, DB > & xpath ) const

The bounding boxes which intersect xpath.

Precondition

xpath.depth() == xpath.tree()->depth() ? is_leaf() : true

Postcondition

xpath.depth() == old_xpath_depth

Definition at line 538 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_path< DC, DB >::ascend(), geometry::d_tree_point_locator_node< DC, DB >::box_list(), geometry::d_tree_point_locator_path< DC, DB >::depth(), geometry::d_tree_point_locator_path< DC, DB >::descend(), geometry::d_tree_point_locator_path< DC, DB >::head(), and geometry::d_tree_point_locator_path< DC, DB >::tree().

◆ box_list() [2/2]

template<int DC, int DB>

const d_tree_point_locator_node< DC, DB >::box_list_type & geometry::d_tree_point_locator_node< DC, DB >::box_list ( ) const

The bounding boxes which intersect this.

Definition at line 575 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_node< DC, DB >::to_string().

Referenced by geometry::d_tree_point_locator_node< DC, DB >::box_list(), and geometry::d_tree_point_locator_node< DC, DB >::clear().

◆ branch()

template<int DC, int DB>

d_tree_point_locator_node< DC, DB > * geometry::d_tree_point_locator_node< DC, DB >::branch ( int xindex ) const

The xindex-th branch.

Precondition

(0 <= xindex) && (xindex < degree())

Definition at line 188 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_node< DC, DB >::is_leaf().

Referenced by geometry::d_tree_point_locator_node< DC, DB >::invariant().

◆ branch_ct()

template<int DC, int DB>

size_type geometry::d_tree_point_locator_node< DC, DB >::branch_ct ( ) const

The number of non-null branches.

Definition at line 675 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_node< DC, DB >::next().

Referenced by geometry::d_tree_point_locator_node< DC, DB >::degree().

◆ clear()

template<int DC, int DB>

void geometry::d_tree_point_locator_node< DC, DB >::clear ( )

Clears all branches and all boxes from this. Warning: this function does not deallocate the branches and hence can leave allocated but unreachable branches.

Postcondition

is_empty()

is_leaf()

Definition at line 508 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_node< DC, DB >::box_list().

Referenced by geometry::d_tree_point_locator_node< DC, DB >::contains_box().

◆ contains_box()

template<int DC, int DB>

bool geometry::d_tree_point_locator_node< DC, DB >::contains_box	(	const d_bounding_box< DC, DB > *	xbox,
		d_tree_point_locator_path< DC, DB > &	xpath
	)		const

True if xbox is in the box list of this or its branches, recursively.

Precondition

is_empty() ? xpath.depth() < xpath.tree()->depth() : true

Postcondition

xpath.depth() == old_xpath_depth

Definition at line 452 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_path< DC, DB >::ascend(), geometry::d_tree_point_locator_node< DC, DB >::clear(), geometry::d_tree_point_locator_node< DC, DB >::contains_box(), geometry::d_tree_point_locator_path< DC, DB >::depth(), geometry::d_tree_point_locator_path< DC, DB >::descend(), geometry::d_tree_point_locator_path< DC, DB >::intersects(), geometry::d_tree_point_locator_path< DC, DB >::put_head(), and geometry::d_tree_point_locator_path< DC, DB >::tree().

Referenced by geometry::d_tree_point_locator_node< DC, DB >::contains_box(), and geometry::d_tree_point_locator_node< DC, DB >::remove_box().

◆ degree()

template<int DC, int DB>

size_type geometry::d_tree_point_locator_node< DC, DB >::degree ( )

static

The maximum number of branches a node may have.

Postcondition

result == DEGREE

Definition at line 652 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_node< DC, DB >::branch_ct().

Referenced by geometry::d_tree_point_locator_node< DC, DB >::to_string().

◆ insert_box()

template<int DC, int DB>

void geometry::d_tree_point_locator_node< DC, DB >::insert_box	(	const d_bounding_box< DC, DB > *	xbox,
		d_tree_point_locator_path< DC, DB > &	xpath
	)

Inserts xbox in this or somewhere on one of its branches.

Precondition

xpath.intersects(xbox)

Postcondition

-unexecutable( contains_box(xbox, xpath) )

xpath.depth() == old_xpath_depth

Definition at line 255 of file d_tree_point_locator_node.impl.h.

Referenced by geometry::d_tree_point_locator_node< DC, DB >::insert_box(), and geometry::d_tree_point_locator_node< DC, DB >::is_empty().

◆ invariant()

template<int DC, int DB>

bool geometry::d_tree_point_locator_node< DC, DB >::invariant ( ) const

Class invariant.

Invariant

branch_ct() <= degree()

for(int i = ( 0 ); i < ( degree() ); ++ i ) (is_leaf() ? branch(i) == 0 : true)

Definition at line 175 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_node< DC, DB >::branch().

Referenced by geometry::d_tree_point_locator_node< DC, DB >::~d_tree_point_locator_node().

◆ is_empty()

template<int DC, int DB>

bool geometry::d_tree_point_locator_node< DC, DB >::is_empty ( ) const

True if box_list() is empty.

Definition at line 232 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_node< DC, DB >::insert_box().

Referenced by geometry::d_tree_point_locator_node< DC, DB >::is_leaf(), and geometry::d_tree_point_locator_node< DC, DB >::remove_box().

◆ is_leaf()

template<int DC, int DB>

bool geometry::d_tree_point_locator_node< DC, DB >::is_leaf ( ) const

True if this node is a leaf node.

Definition at line 211 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_node< DC, DB >::is_empty().

Referenced by geometry::d_tree_point_locator_node< DC, DB >::branch(), and geometry::d_tree_point_locator_node< DC, DB >::remove_box().

◆ next()

template<int DC, int DB>

d_tree_point_locator_node< DC, DB > * geometry::d_tree_point_locator_node< DC, DB >::next ( ) const

protected

The next node in the free list; intended for use only by class ptr_linked_pool.

Definition at line 700 of file d_tree_point_locator_node.impl.h.

References geometry::d_tree_point_locator_node< DC, DB >::put_next().

Referenced by geometry::d_tree_point_locator_node< DC, DB >::branch_ct().

◆ operator=()

template<int DC, int DB>

d_tree_point_locator_node< DC, DB > & geometry::d_tree_point_locator_node< DC, DB >::operator= ( const d_tree_point_locator_node< DC, DB > & xother )

Assignment operator.

Postcondition