Open CASCADE Technology  6.9.0
Data Structures | Public Member Functions | Protected Member Functions

NCollection_UBTree< TheObjType, TheBndType > Class Template Reference

#include <NCollection_UBTree.hxx>

Inheritance diagram for NCollection_UBTree< TheObjType, TheBndType >:
Inheritance graph
[legend]

Data Structures

class  Selector
 Memory allocation. More...
 
class  TreeNode
 

Public Member Functions

 NCollection_UBTree (const Handle< NCollection_BaseAllocator > &theAllocator=0L)
 
virtual Standard_Boolean Add (const TheObjType &theObj, const TheBndType &theBnd)
 
virtual Standard_Integer Select (Selector &theSelector) const
 
virtual void Clear (const Handle< NCollection_BaseAllocator > &aNewAlloc=0L)
 
Standard_Boolean IsEmpty () const
 
const TreeNodeRoot () const
 
virtual ~NCollection_UBTree ()
 
const Handle
< NCollection_BaseAllocator > & 
Allocator () const
 

Protected Member Functions

TreeNodeChangeLastNode ()
 
Standard_Integer Select (const TreeNode &theBranch, Selector &theSelector) const
 

Detailed Description

template<class TheObjType, class TheBndType>
class NCollection_UBTree< TheObjType, TheBndType >

The algorithm of unbalanced binary tree of overlapped bounding boxes.

Once the tree of boxes of geometric objects is constructed, the algorithm is capable of fast geometric selection of objects. The tree can be easily updated by adding to it a new object with bounding box.

The time of adding to the tree of one object is O(log(N)), where N is the total number of objects, so the time of building a tree of N objects is O(N(log(N)). The search time of one object is O(log(N)).

Defining various classes inheriting NCollection_UBTree::Selector we can perform various kinds of selection over the same b-tree object

The object may be of any type allowing copying. Among the best suitable solutions there can be a pointer to an object, handled object or integer index of object inside some collection. The bounding object may have any dimension and geometry. The minimal interface of TheBndType (besides public empty and copy constructor and operator =) used in UBTree algorithm is as the following:

* class MyBndType
* {
* public:
* inline void Add (const MyBndType& other);
* // Updates me with other bounding
*
* inline Standard_Boolean IsOut (const MyBndType& other) const;
* // Classifies other bounding relatively me
*
* inline Standard_Real SquareExtent() const;
* // Computes the squared maximal linear extent of me.
* // (For box it is the squared diagonal of box)
* };
*

To select objects you need to define a class derived from UBTree::Selector that should redefine the necessary virtual methods to maintain the selection condition. The object of this class is also used to retrieve selected objects after search.

Constructor & Destructor Documentation

template<class TheObjType , class TheBndType >
NCollection_UBTree< TheObjType, TheBndType >::NCollection_UBTree ( const Handle< NCollection_BaseAllocator > &  theAllocator = 0L)
inline

Constructor.

template<class TheObjType , class TheBndType >
virtual NCollection_UBTree< TheObjType, TheBndType >::~NCollection_UBTree ( )
inlinevirtual

Desctructor.

Member Function Documentation

template<class TheObjType , class TheBndType >
Standard_Boolean NCollection_UBTree< TheObjType, TheBndType >::Add ( const TheObjType &  theObj,
const TheBndType &  theBnd 
)
virtual

Update the tree with a new object and its bounding box.

Parameters
theObjadded object
theBndbounding box of the object.
Returns
always True
template<class TheObjType , class TheBndType >
const Handle< NCollection_BaseAllocator >& NCollection_UBTree< TheObjType, TheBndType >::Allocator ( ) const
inline

Recommended to be used only in sub-classes.

Returns
Allocator object used in this instance of UBTree.
template<class TheObjType , class TheBndType >
TreeNode& NCollection_UBTree< TheObjType, TheBndType >::ChangeLastNode ( )
inlineprotected
Returns
the last added node
template<class TheObjType , class TheBndType >
virtual void NCollection_UBTree< TheObjType, TheBndType >::Clear ( const Handle< NCollection_BaseAllocator > &  aNewAlloc = 0L)
inlinevirtual

Clears the contents of the tree.

Parameters
aNewAllocOptional: a new allocator that will be used when the tree is rebuilt anew. This makes sense if the memory allocator needs re-initialisation (like NCollection_IncAllocator). By default the previous allocator is kept.

Reimplemented in NCollection_EBTree< TheObjType, TheBndType >.

template<class TheObjType , class TheBndType >
Standard_Boolean NCollection_UBTree< TheObjType, TheBndType >::IsEmpty ( ) const
inline
template<class TheObjType , class TheBndType >
const TreeNode& NCollection_UBTree< TheObjType, TheBndType >::Root ( ) const
inline
Returns
the root node of the tree
template<class TheObjType , class TheBndType >
virtual Standard_Integer NCollection_UBTree< TheObjType, TheBndType >::Select ( Selector theSelector) const
inlinevirtual

Searches in the tree all objects conforming to the given selector. return Number of objects accepted

template<class TheObjType , class TheBndType >
Standard_Integer NCollection_UBTree< TheObjType, TheBndType >::Select ( const TreeNode theBranch,
Selector theSelector 
) const
protected

Searches in the branch all objects conforming to the given selector.

Returns
the number of objects accepted

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