21 #ifndef D_TREE_POINT_LOCATOR_NODE_IMPL_H 22 #define D_TREE_POINT_LOCATOR_NODE_IMPL_H 24 #ifndef SHEAF_DLL_SPEC_H 25 #include "SheafSystem/sheaf_dll_spec.h" 28 #ifndef ASSERT_CONTRACT_H 29 #include "SheafSystem/assert_contract.h" 32 #ifndef ERROR_MESSAGE_H 33 #include "SheafSystem/error_message.h" 36 #ifndef D_TREE_POINT_LOCATOR_H 37 #include "SheafSystem/d_tree_point_locator.h" 40 #ifndef D_TREE_POINT_LOCATOR_PATH_H 41 #include "SheafSystem/d_tree_point_locator_path.h" 45 #include "SheafSystem/std_sstream.h" 60 template <
int DC,
int DB>
71 for(
int i=0; i<DEGREE; ++i)
82 template <
int DC,
int DB>
94 ensure(*
this == xother);
101 template <
int DC,
int DB>
115 for(
int i=0; i<DEGREE; ++i)
122 ensure(*
this == xother);
127 template <
int DC,
int DB>
139 bool result = (_box_list == xother.
_box_list);
141 for(
int i=0; i<DEGREE; ++i)
143 result = result && ( _branches[i] == xother.
_branches[i]);
146 result == result && (_branch_ct == xother.
_branch_ct);
155 template <
int DC,
int DB>
172 template <
int DC,
int DB>
179 invariance(branch_ct() <= degree());
180 invariance_for_all(i, 0, degree(), (is_leaf() ? branch(i) == 0 :
true));
185 template <
int DC,
int DB>
194 require((0 <= xindex) && (xindex < degree()));
198 result = _branches[xindex];
208 template <
int DC,
int DB>
219 result = (_branch_ct == 0);
229 template <
int DC,
int DB>
241 result = _box_list.empty();
252 template <
int DC,
int DB>
266 if(xpath.
depth() == xpath.
tree()->depth())
270 _box_list.push_front(xbox);
277 xpath.
tree()->node_pool();
283 assertion(++(_box_list.begin()) == _box_list.end());
297 assertion(lbranch == 0);
305 _branches[i] = lnode_pool.
allocate();
312 _box_list.pop_front();
317 assertion(_box_list.empty());
336 _branches[i] = lnode_pool.
allocate();
356 ensure(unexecutable(contains_box(xbox, xpath)));
357 ensure(xpath.
depth() == old_xpath_depth);
364 template <
int DC,
int DB>
375 require(is_empty() ? xpath.
depth() < xpath.
tree()->depth() :
true);
382 xpath.
tree()->node_pool();
400 lnode_pool.deallocate(lbranch);
414 if(xbox == _box_list.front())
416 _box_list.pop_front();
420 typename box_list_type::iterator lprev = _box_list.begin();
421 typename box_list_type::iterator lcur = ++lprev;
422 while(lcur != _box_list.end())
426 _box_list.erase_after(lprev);
440 ensure(unexecutable(!contains_box(xbox, xpath)));
441 ensure(xpath.
depth() == old_xpath_depth);
449 template <
int DC,
int DB>
459 require(is_empty() ? xpath.
depth() < xpath.
tree()->depth() :
true);
470 for(
size_type i=0; !result && (i<DEGREE); i++)
488 typename box_list_type::const_iterator litr = _box_list.begin();
489 while(!result && (litr != _box_list.end()))
491 result = (*litr == xbox);
498 ensure(xpath.
depth() == old_xpath_depth);
505 template <
int DC,
int DB>
515 for(
int i=0; i<DEGREE; i++)
535 template <
int DC,
int DB>
542 require(xpath.
depth() == xpath.
tree()->depth() ? is_leaf() :
true);
552 lresult_ptr = &_box_list;
559 lresult_ptr = &(_branches[xpath.
head()]->box_list(xpath));
565 ensure(xpath.
depth() == old_xpath_depth);
572 template <
int DC,
int DB>
591 template <
int DC,
int DB>
600 ostr <<
"d_tree_point_locator_node:" << endl;
602 ostr <<
"this = " <<
this << endl;
622 for(
int i=0; i<DEGREE; ++i)
624 ostr <<
"_branches[i] = " << _branches[i] << endl;
628 for(
int i=0; i<DEGREE; ++i)
630 if(_branches[i] != 0)
633 string* s = _branches[i]->to_string();
641 string* result =
new string(ostr.str());
649 template <
int DC,
int DB>
665 ensure(result == DEGREE);
672 template <
int DC,
int DB>
697 template <
int DC,
int DB>
709 result = _branches[0];
719 template <
int DC,
int DB>
729 _branches[0] = xnode;
733 ensure(next() == xnode);
746 #ifndef DOXYGEN_SHOULD_SKIP_THIS 748 template <
int DC,
int DB>
750 geometry::operator<<(std::ostream& xos, const geometry::d_tree_point_locator_node<DC, DB>& xnode)
752 std::string* s = xnode.to_string();
759 #endif // ifndef DOXYGEN_SHOULD_SKIP_THIS 761 #endif // D_TREE_POINT_LOCATOR_NODE_IMPL_H bool invariant() const
Class invariant.
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.
T * allocate()
Allocate next available object from the free list.
d_tree_point_locator_node< DC, DB > & operator=(const d_tree_point_locator_node< DC, DB > &xother)
Assignment operator.
~d_tree_point_locator_node()
Destructor.
d_tree_point_locator_node< DC, DB > * branch(int xindex) const
The xindex-th branch.
std::string * to_string() const
Get instance information as a string.
size_type depth() const
The current depth.
static size_type degree()
The maximum number of branches a node may have.
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.
void ascend()
Ascend one level in the path.
size_type head() const
The branch index of the head of the path.
A reallocatable pool of objects of type T. Objects in the pool are either "allocated" or linked toget...
bool is_empty() const
True if box_list() is empty.
box_list_type _box_list
The list of bounding boxes associated with this.
void clear()
Clears all branches and all boxes from this. Warning: this function does not deallocate the branches ...
size_type _branch_ct
The number of non-null branches.
bool operator==(const d_tree_point_locator_node< DC, DB > &xother)
Equality operator.
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.
const box_list_type & box_list() const
The bounding boxes which intersect this.
size_type branch_ct() const
The number of non-null branches.
d_tree_point_locator_node()
Default constructor.
bool intersects(const d_bounding_box< DC, DB > *xbox) const
True if the tree box represented by the current head intersects the box with lower bound xlb and uppe...
sheaf::size_type size_type
An unsigned integral type used to represent sizes and capacities.
A bounding box that can be strung together into a list.
A path in an d_tree_point_locator search structure.
void push_front(const T &value)
Prepends the given element value to the beginning of the container.
void descend()
Descend one level in the path.
void put_head(size_type xhead)
Set the current head to xhead.
d_tree_point_locator< DC, DB > * tree() const
The tree this is a path in.
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.
d_tree_point_locator_node< DC, DB > * _branches[DEGREE]
The branches of this node.
A node in a d_tree_point_locator search structure.
Namespace for geometry component of sheaf system.
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.
Wrapper class for forward_list or slist depending on compiler. The class replicates the minimum subse...
bool is_leaf() const
True if this node is a leaf node.