NCollection_UBTree< TheObjType, TheBndType > Class Template Reference

#include <NCollection_UBTree.hxx>

Inheritance diagram for NCollection_UBTree< TheObjType, TheBndType >:

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 TreeNode &	Root () const
virtual	~NCollection_UBTree ()
const Handle< NCollection_BaseAllocator > &	Allocator () const

Protected Member Functions
TreeNode &	ChangeLastNode ()
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

NCollection_UBTree()

template<class TheObjType, class TheBndType>

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

inline

Constructor.

~NCollection_UBTree()

template<class TheObjType, class TheBndType>

virtual NCollection_UBTree< TheObjType, TheBndType >::~NCollection_UBTree ( )

inlinevirtual

Desctructor.

Member Function Documentation

Add()

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

theObj	added object
theBnd	bounding box of the object.

Returns

always True

Reimplemented in NCollection_EBTree< TheObjType, TheBndType >.

Allocator()

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.

ChangeLastNode()

template<class TheObjType, class TheBndType>

TreeNode& NCollection_UBTree< TheObjType, TheBndType >::ChangeLastNode ( )

inlineprotected

Returns

the last added node

Clear()

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

aNewAlloc

Optional: 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 >.

IsEmpty()

template<class TheObjType, class TheBndType>

Standard_Boolean NCollection_UBTree< TheObjType, TheBndType >::IsEmpty ( ) const

inline

Root()

template<class TheObjType, class TheBndType>

const TreeNode& NCollection_UBTree< TheObjType, TheBndType >::Root ( ) const

inline

Returns

the root node of the tree

Select() [1/2]

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

Select() [2/2]

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:

• NCollection_UBTree.hxx