SheafSystem  0.0.0.0
Friends | List of all members
geometry::d_tree_point_locator_node< DC, DB > Class Template Reference

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

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

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.

References geometry::d_tree_point_locator_node< DC, DB >::_box_list, sheaf::ptr_linked_pool< T >::allocate(), geometry::d_tree_point_locator_path< DC, DB >::ascend(), geometry::d_tree_point_locator_path< DC, DB >::depth(), geometry::d_tree_point_locator_path< DC, DB >::descend(), geometry::d_tree_point_locator_node< DC, DB >::insert_box(), geometry::d_tree_point_locator_path< DC, DB >::intersects(), sheaf::singly_linked_list< T, A >::push_front(), geometry::d_tree_point_locator_path< DC, DB >::put_head(), geometry::d_tree_point_locator_node< DC, DB >::remove_box(), and geometry::d_tree_point_locator_path< DC, DB >::tree().

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

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
  • *this == xother

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

References geometry::d_tree_point_locator_node< DC, DB >::_box_list, geometry::d_tree_point_locator_node< DC, DB >::_branch_ct, geometry::d_tree_point_locator_node< DC, DB >::_branches, and geometry::d_tree_point_locator_node< DC, DB >::operator==().

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

◆ operator==()

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

Equality operator.

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

References geometry::d_tree_point_locator_node< DC, DB >::_box_list, geometry::d_tree_point_locator_node< DC, DB >::_branch_ct, geometry::d_tree_point_locator_node< DC, DB >::_branches, and geometry::d_tree_point_locator_node< DC, DB >::~d_tree_point_locator_node().

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

◆ put_next()

template<int DC, int DB>
void geometry::d_tree_point_locator_node< DC, DB >::put_next ( d_tree_point_locator_node< DC, DB > *  xnode)
protected

Sets the next node in the free list to xnode; intended for use only by class ptr_linked_pool.

Postcondition

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

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

◆ remove_box()

template<int DC, int DB>
void geometry::d_tree_point_locator_node< DC, DB >::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.

Precondition
  • xpath.intersects(xbox)
  • is_empty() ? xpath.depth() < xpath.tree()->depth() : true
Postcondition
  • -unexecutable( !contains_box(xbox, xpath) )
  • xpath.depth() == old_xpath_depth

Definition at line 367 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 >::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_node< DC, DB >::is_empty(), geometry::d_tree_point_locator_node< DC, DB >::is_leaf(), geometry::d_tree_point_locator_path< DC, DB >::put_head(), geometry::d_tree_point_locator_node< DC, DB >::remove_box(), and geometry::d_tree_point_locator_path< DC, DB >::tree().

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

◆ to_string()

template<int DC, int DB>
std::string * geometry::d_tree_point_locator_node< DC, DB >::to_string ( ) const

Get instance information as a string.

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

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

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

Member Data Documentation

◆ _box_list

template<int DC, int DB>
box_list_type geometry::d_tree_point_locator_node< DC, DB >::_box_list
protected

The list of bounding boxes associated with this.

Definition at line 182 of file d_tree_point_locator_node.h.

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

◆ _branch_ct

template<int DC, int DB>
size_type geometry::d_tree_point_locator_node< DC, DB >::_branch_ct
protected

The number of non-null branches.

Definition at line 197 of file d_tree_point_locator_node.h.

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

◆ _branches

template<int DC, int DB>
d_tree_point_locator_node<DC, DB>* geometry::d_tree_point_locator_node< DC, DB >::_branches[DEGREE]
protected

The branches of this node.

Definition at line 192 of file d_tree_point_locator_node.h.

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

◆ DEGREE

template<int DC, int DB>
const size_type geometry::d_tree_point_locator_node< DC, DB >::DEGREE = 1<<DC
staticprotected

The number of elements in the branches array.

Definition at line 187 of file d_tree_point_locator_node.h.

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