moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer > Class Template Reference

#include <element_tree.hpp>

Collaboration diagram for moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >:

Public Types
typedef _Entity_handles	Entity_handles
typedef _Box	Box
typedef _Moab	Moab
typedef _Parametrizer	Parametrizer
typedef Entity_handles::value_type	Entity_handle

Public Member Functions
	Element_tree (Entity_handles &_entities, Moab &_moab, Box &_bounding_box, Parametrizer &_entity_contains)
	Element_tree (Self &s)
template<typename Vector , typename Result >
Result &	find (const Vector &point, Result &result) const

Private Types
typedef Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >	Self
typedef std::pair< Box, Entity_handle >	Leaf_element
typedef _element_tree::_Node< Entity_handles, std::vector< Leaf_element > >	Node
typedef common_tree::_Element_data< Box, std::bitset< NUM_DIM *MAX_ITERATIONS *2 > >	Element_data
typedef std::vector< Node >	Nodes
typedef std::tr1::unordered_map< Entity_handle, Element_data >	Element_map
typedef std::vector< typename Element_map::iterator >	Element_list
typedef _element_tree::_Partition_data< Box >	Partition_data

Private Member Functions
template<typename Iterator , typename Split_data >
void	compute_split (Iterator &begin, Iterator &end, Split_data &split_data, bool iteration=false)
template<typename Split_data >
bool	update_split_line (Split_data &data) const
template<typename Iterator , typename Split_data , typename Directions >
void	determine_split (Iterator &begin, Iterator &end, Split_data &data, const Directions &directions)
template<typename Iterator , typename Node_index , typename Directions , typename Partition_data >
void	build_tree (Iterator begin, Iterator end, const Node_index node, const Directions &directions, Partition_data &_data, int &depth, const bool is_middle=false)
template<typename Vector , typename Node_index , typename Result >
Result &	_find_point (const Vector &point, const Node_index &index, Result &result) const

Private Attributes
const Entity_handles &	entity_handles_
Nodes	tree_
Moab &	moab
Box	bounding_box
Parametrizer	entity_contains

Detailed Description

template<typename _Entity_handles, typename _Box, typename _Moab, typename _Parametrizer>
class moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >

Definition at line 231 of file element_tree.hpp.

Member Typedef Documentation

Box

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef _Box moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Box

Definition at line 237 of file element_tree.hpp.

Element_data

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef common_tree::_Element_data< Box, std::bitset< NUM_DIM * MAX_ITERATIONS * 2 > > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_data

private

Definition at line 249 of file element_tree.hpp.

Element_list

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef std::vector< typename Element_map::iterator > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_list

private

Definition at line 253 of file element_tree.hpp.

Element_map

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef std::tr1::unordered_map< Entity_handle, Element_data > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_map

private

Definition at line 252 of file element_tree.hpp.

Entity_handle

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef Entity_handles::value_type moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Entity_handle

Definition at line 240 of file element_tree.hpp.

Entity_handles

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef _Entity_handles moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Entity_handles

Definition at line 236 of file element_tree.hpp.

Leaf_element

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef std::pair< Box, Entity_handle > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Leaf_element

private

Definition at line 245 of file element_tree.hpp.

Moab

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef _Moab moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Moab

Definition at line 238 of file element_tree.hpp.

Node

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef _element_tree::_Node< Entity_handles, std::vector< Leaf_element > > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Node

private

Definition at line 246 of file element_tree.hpp.

Nodes

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef std::vector< Node > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Nodes

private

Definition at line 250 of file element_tree.hpp.

Parametrizer

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef _Parametrizer moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Parametrizer

Definition at line 239 of file element_tree.hpp.

Partition_data

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef _element_tree::_Partition_data< Box > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Partition_data

private

Definition at line 254 of file element_tree.hpp.

Self

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

typedef Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Self

private

Definition at line 244 of file element_tree.hpp.

Constructor & Destructor Documentation

Element_tree() [1/2]

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree ( Entity_handles &  _entities, Moab &  _moab, Box &  _bounding_box, Parametrizer &  _entity_contains  )

inline

Definition at line 258 of file element_tree.hpp.

 : entity_handles_( _entities ), tree_(), moab( _moab ), bounding_box( _bounding_box ),
 entity_contains( _entity_contains )
 {
 tree_.reserve( _entities.size() );
 Element_map element_map( _entities.size() );
 Partition_data _data;
 common_tree::construct_element_map( entity_handles_, element_map, _data.bounding_box, moab );
 bounding_box = _data.bounding_box;
 _bounding_box = bounding_box;
 Element_list element_ordering( element_map.size() );
 std::size_t index = 0;
 for( typename Element_map::iterator i = element_map.begin(); i != element_map.end(); ++i, ++index )
 {
 element_ordering[index] = i;
 }
 // We only build nonempty trees
 if( element_ordering.size() )
 {
 // initially all bits are set
 std::bitset< 3 > directions( 7 );
 tree_.push_back( Node() );
 int depth = 0;
 build_tree( element_ordering.begin(), element_ordering.end(), 0, directions, _data, depth );
 std::cout << "depth: " << depth << std::endl;
 }
 }

References moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::bounding_box, moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::build_tree(), moab::common_tree::construct_element_map(), moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::entity_handles_, and moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::tree_.

Element_tree() [2/2]

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree ( Self &  s )

inline

Definition at line 287 of file element_tree.hpp.

 : entity_handles_( s.entity_handles_ ), tree_( s.tree_ ), moab( s.moab ), bounding_box( s.bounding_box )
 {
 }

Member Function Documentation

_find_point()

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

template<typename Vector , typename Node_index , typename Result >

Result& moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::_find_point ( const Vector &  point, const Node_index &  index, Result &  result  ) const

inlineprivate

Definition at line 543 of file element_tree.hpp.

 {
 typedef typename Node::Entities::const_iterator Entity_iterator;
 typedef typename std::pair< bool, Vector > Return_type;
 const Node& node = tree_[index];
 if( node.leaf() )
 {
 // check each node
 for( Entity_iterator i = node.entities.begin(); i != node.entities.end(); ++i )
 {
 if( common_tree::box_contains_point( i->first, point ) )
 {
 Return_type r = entity_contains( moab, i->second, point );
 if( r.first )
 {
 result = std::make_pair( i->second, r.second );
 }
 return result;
 }
 }
 return Result( 0, point );
 }
 if( point[node.dim] < node.left_line )
 {
 return _find_point( point, node.left_, result );
 }
 else if( point[node.dim] > node.right_line )
 {
 return _find_point( point, node.right_, result );
 }
 else
 {
 Entity_handle middle = _find_point( point, node.middle_, result );
 if( middle != 0 )
 {
 return result;
 }
 if( point[node.dim] < node.split )
 {
 return _find_point( point, node.left_, result );
 }
 return _find_point( point, node.right_, result );
 }
 }

References moab::common_tree::box_contains_point(), moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::entity_contains, and moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::tree_.

Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::find().

build_tree()

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

template<typename Iterator , typename Node_index , typename Directions , typename Partition_data >

void moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::build_tree ( Iterator  begin, Iterator  end, const Node_index  node, const Directions &  directions, Partition_data &  _data, int &  depth, const bool  is_middle = false  )

inlineprivate

Definition at line 470 of file element_tree.hpp.

 {
 std::size_t number_elements = std::distance( begin, end );
 if( depth < MAX_DEPTH && number_elements > ELEMENTS_PER_LEAF && ( !is_middle || directions.any() ) )
 {
 determine_split( begin, end, _data, directions );
 // count_sort( begin, end, _data);
 std::sort( begin, end, _element_tree::Iterator_comparator< Iterator >() );
 // update the tree
 tree_[node] = _data;
 Iterator middle_begin( begin + _data.left() );
 Iterator middle_end( middle_begin + _data.middle() );
 std::vector< int > depths( 3, depth );
 // left subtree
 if( _data.left() > 0 )
 {
 Partition_data data( _data );
 tree_.push_back( Node() );
 tree_[node].children[0] = tree_.size() - 1;
 correct_bounding_box( _data, data.bounding_box, 0 );
 Directions new_directions( directions );
 const bool axis_is_very_small =
 ( data.bounding_box.max[_data.dim] - data.bounding_box.min[_data.dim] < EPSILON );
 new_directions.set( _data.dim, axis_is_very_small );
 build_tree( begin, middle_begin, tree_[node].children[0], new_directions, data, ++depths[0],
 is_middle );
 }
 // middle subtree
 if( _data.middle() > 0 )
 {
 Partition_data data( _data );
 tree_.push_back( Node() );
 tree_[node].children[1] = tree_.size() - 1;
 correct_bounding_box( _data, data.bounding_box, 1 );
 // force the middle subtree to split
 // in a different direction from this one
 Directions new_directions( directions );
 new_directions.flip( tree_[node].dim );
 bool axis_is_very_small =
 ( data.bounding_box.max[_data.dim] - data.bounding_box.min[_data.dim] < EPSILON );
 new_directions.set( _data.dim, axis_is_very_small );
 build_tree( middle_begin, middle_end, tree_[node].children[1], new_directions, data, ++depths[1],
 true );
 }
 // right subtree
 if( _data.right() > 0 )
 {
 Partition_data data( _data );
 tree_.push_back( Node() );
 tree_[node].children[2] = tree_.size() - 1;
 correct_bounding_box( _data, data.bounding_box, 2 );
 Directions new_directions( directions );
 const bool axis_is_very_small =
 ( data.bounding_box.max[_data.dim] - data.bounding_box.min[_data.dim] < EPSILON );
 new_directions.set( _data.dim, axis_is_very_small );
 
 build_tree( middle_end, end, tree_[node].children[2], directions, data, ++depths[2], is_middle );
 }
 depth = *std::max_element( depths.begin(), depths.end() );
 }
 if( tree_[node].leaf() )
 {
 common_tree::assign_entities( tree_[node].entities, begin, end );
 }
 }

References moab::common_tree::assign_entities(), children, moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::determine_split(), dim, ELEMENTS_PER_LEAF, entities, EPSILON, and moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::tree_.

Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree().

compute_split()

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

template<typename Iterator , typename Split_data >

void moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::compute_split ( Iterator &  begin, Iterator &  end, Split_data &  split_data, bool  iteration = false  )

inlineprivate

Definition at line 295 of file element_tree.hpp.

 {
 typedef typename Iterator::value_type::value_type Map_value_type;
 typedef typename Map_value_type::second_type::second_type Bitset;
 // we will update the left/right line
 double& left_line = split_data.left_line;
 double& right_line = split_data.right_line;
 double& split = split_data.split;
 const int& dim = split_data.dim;
#ifdef ELEMENT_TREE_DEBUG
 std::cout << std::endl;
 std::cout << "-------------------" << std::endl;
 std::cout << "dim: " << dim << " split: " << split << std::endl;
 std::cout << "bounding_box min: ";
 print_vector( split_data.bounding_box.min );
 std::cout << "bounding_box max: ";
 print_vector( split_data.bounding_box.max );
#endif
 // for each elt determine if left/middle/right
 for( Iterator i = begin; i != end; ++i )
 {
 const Box& box = ( *i )->second.first;
 Bitset& bits = ( *i )->second.second;
 // will be 0 if on left, will be 1 if in the middle
 // and 2 if on the right;
 const bool on_left = ( box.max[dim] < split );
 const bool on_right = ( box.min[dim] > split );
 const bool in_middle = !on_left && !on_right;
 // set the corresponding bits in the bit vector
 // looks like: [x_1 = 00 | x_2 = 00 | .. | z_1 = 00 | z_2 = 00]
 // two bits, left = 00, middle = 01, right = 10
 const int index = 4 * dim + 2 * iteration;
 if( on_left )
 {
 split_data.sizes[0]++;
 }
 else if( in_middle )
 {
 split_data.sizes[1]++;
 bits.set( index, 1 );
 left_line = std::min( left_line, box.min[dim] );
 right_line = std::max( right_line, box.max[dim] );
 }
 else if( on_right )
 {
 bits.set( index + 1, 1 );
 split_data.sizes[2]++;
 }
 }
#ifdef ELEMENT_TREE_DEBUG
 std::size_t _count = std::accumulate( split_data.sizes.begin(), split_data.sizes.end(), 0 );
 std::size_t total = std::distance( begin, end );
 if( total != _count )
 {
 std::cout << total << "vs. " << _count << std::endl;
 }
 std::cout << " left_line: " << left_line;
 std::cout << " right_line: " << right_line << std::endl;
 std::cout << "co/mputed partition size: ";
 print_vector( split_data.sizes );
 std::cout << "-------------------" << std::endl;
#endif
 }

References dim, left_line, moab::common_tree::print_vector(), right_line, and split.

Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::determine_split().

determine_split()

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

template<typename Iterator , typename Split_data , typename Directions >

void moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::determine_split ( Iterator &  begin, Iterator &  end, Split_data &  data, const Directions &  directions  )

inlineprivate

Definition at line 401 of file element_tree.hpp.

 {
 typedef typename Iterator::value_type Pair;
 typedef typename Pair::value_type Map_value_type;
 typedef typename Map_value_type::second_type::second_type Bitset;
 typedef typename Map_value_type::second_type::first_type Box;
 typedef typename std::map< std::size_t, Split_data > Splits;
 typedef typename Splits::value_type Split;
 typedef _element_tree::Split_comparator< Split > Comparator;
 Splits splits;
 for( std::size_t dir = 0; dir < directions.size(); ++dir )
 {
 if( directions.test( dir ) )
 {
 Split_data split_data( data.bounding_box, dir );
 compute_split( begin, end, split_data );
 splits.insert( std::make_pair( 2 * dir, split_data ) );
 if( update_split_line( split_data ) )
 {
 compute_split( begin, end, split_data, true );
 splits.insert( std::make_pair( 2 * dir + 1, split_data ) );
 }
 }
 }
 Split best = *std::min_element( splits.begin(), splits.end(), Comparator() );
#ifdef ELEMENT_TREE_DEBUG
 std::cout << "best: " << Comparator().split_objective( best ) << " ";
 print_vector( best.second.sizes );
#endif
 const int dir = best.first / 2;
 const int iter = best.first % 2;
 double& left_rightline = best.second.left_rightline = best.second.bounding_box.min[dir];
 double& right_leftline = best.second.right_leftline = best.second.bounding_box.max[dir];
 Bitset mask( 0 );
 mask.flip( 4 * dir + 2 * iter ).flip( 4 * dir + 2 * iter + 1 );
 for( Iterator i = begin; i != end; ++i )
 {
 Bitset& bits = ( *i )->second.second;
 const Box& box = ( *i )->second.first;
 // replace 12 bits with just two.
 bits &= mask;
 bits >>= 4 * dir + 2 * iter;
 // if box is labeled left/right but properly contained
 // in the middle, move the element into the middle.
 // we can shrink the size of left/right
 switch( bits.to_ulong() )
 {
 case 0:
 if( box.max[dir] > best.second.left_line )
 {
 left_rightline = std::max( left_rightline, box.max[dir] );
 }
 break;
 case 2:
 if( box.min[dir] < best.second.right_line )
 {
 right_leftline = std::min( right_leftline, box.max[dir] );
 }
 break;
 }
 }
 data = best.second;
 }

References moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::compute_split(), left_rightline, moab::common_tree::print_vector(), right_leftline, and moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::update_split_line().

Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::build_tree().

find()

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

template<typename Vector , typename Result >

Result& moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::find ( const Vector &  point, Result &  result  ) const

inline

Definition at line 591 of file element_tree.hpp.

 {
 typedef typename Vector::const_iterator Point_iterator;
 typedef typename Box::Pair Pair;
 typedef typename Pair::first_type Box_iterator;
 return _find_point( point, 0, result );
 }

References moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::_find_point().

update_split_line()

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

template<typename Split_data >

bool moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::update_split_line ( Split_data &  data ) const

inlineprivate

Definition at line 360 of file element_tree.hpp.

 {
 const int max = 2 * ( data.sizes[2] > data.sizes[0] );
 const int min = 2 * ( 1 - ( max == 2 ) );
 bool one_side_empty = data.sizes[max] == 0 || data.sizes[min] == 0;
 double balance_ratio = data.sizes[max] - data.sizes[min];
 // if ( !one_side_empty && balance_ratio < .05*total){ return false; }
 if( !one_side_empty )
 {
 // if we have some imbalance on left/right
 // try to fix the situation
 balance_ratio /= data.sizes[max];
 data.split += ( max - 1 ) * balance_ratio * ( data.split / 2.0 );
 }
 else
 {
 // if the (left) side is empty move the split line just past the
 // extent of the (left) line of the middle box.
 // if middle encompasses everything then wiggle
 // the split line a bit and hope for the best..
 const double left_distance = std::abs( data.left_line - data.split );
 const double right_distance = std::abs( data.right_line - data.split );
 if( ( data.sizes[0] == 0 ) && ( data.sizes[2] != 0 ) )
 {
 data.split += right_distance;
 }
 else if( data.sizes[2] == 0 && data.sizes[0] != 0 )
 {
 data.split -= left_distance;
 }
 else
 {
 data.split *= 1.05;
 }
 }
 data.left_line = data.right_line = data.split;
 data.sizes.assign( data.sizes.size(), 0 );
 return true;
 }

Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::determine_split().

Member Data Documentation

bounding_box

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

Box moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::bounding_box

private

Definition at line 606 of file element_tree.hpp.

Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree().

entity_contains

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

Parametrizer moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::entity_contains

private

Definition at line 607 of file element_tree.hpp.

Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::_find_point().

entity_handles_

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

const Entity_handles& moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::entity_handles_

private

Definition at line 603 of file element_tree.hpp.

Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree().

moab

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

Moab& moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::moab

private

Definition at line 605 of file element_tree.hpp.

tree_

template<typename _Entity_handles , typename _Box , typename _Moab , typename _Parametrizer >

Nodes moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::tree_

private

Definition at line 604 of file element_tree.hpp.

Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::_find_point(), moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::build_tree(), and moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree().

---

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

• element_tree.hpp