OCC Main Page | FoundationClasses | Toolkits | Packages | Class Hierarchy | Data Structures | File List | Data Fields | Globals

FoundationClasses
TKernel
NCollection


NCollection_UBTree< TheObjType, TheBndType > Class Template Reference

#include <NCollection_UBTree.hxx>

Inheritance diagram for NCollection_UBTree< TheObjType, TheBndType >:

Inheritance graph
[legend]

Public Member Functions

 NCollection_UBTree (const Handle(NCollection_BaseAllocator)&theAllocator=0L)
virtual Standard_EXPORT Standard_Boolean Add (const TheObjType &theObj, const TheBndType &theBnd)
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_EXPORT Standard_Integer Select (const TreeNode &theBranch, Selector &theSelector) const

Private Member Functions

 NCollection_UBTree (const NCollection_UBTree &)
 Copy constructor (prohibited).
NCollection_UBTreeoperator= (const NCollection_UBTree &)
 Assignment operator (prohibited).
 Handle (NCollection_BaseAllocator) myAlloc
 Allocator for TreeNode.

Private Attributes

TreeNodemyRoot
 root of the tree
TreeNodemyLastNode
 the last added node

Data Structures

class  Selector
class  TreeNode

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  )  [inline, virtual]
 

Desctructor.

template<class TheObjType, class TheBndType>
NCollection_UBTree< TheObjType, TheBndType >::NCollection_UBTree const NCollection_UBTree< TheObjType, TheBndType > &   )  [private]
 


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:
theObj added object
theBnd bounding box of the object.
Returns:
always True

Reimplemented in NCollection_EBTree< TheObjType, TheBndType >.

template<class TheObjType, class TheBndType>
TreeNode& NCollection_UBTree< TheObjType, TheBndType >::ChangeLastNode  )  [inline, protected]
 

Returns:
the last added node

template<class TheObjType, class TheBndType>
virtual void NCollection_UBTree< TheObjType, TheBndType >::Clear const Handle(NCollection_BaseAllocator)&  aNewAlloc = 0L  )  [inline, virtual]
 

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

template<class TheObjType, class TheBndType>
NCollection_UBTree< TheObjType, TheBndType >::Handle NCollection_BaseAllocator   )  [private]
 

template<class TheObjType, class TheBndType>
const NCollection_UBTree< TheObjType, TheBndType >::Handle NCollection_BaseAllocator   )  const [inline]
 

Recommended to be used only in sub-classes.

Returns:
Allocator object used in this instance of UBTree.

template<class TheObjType, class TheBndType>
Standard_Boolean NCollection_UBTree< TheObjType, TheBndType >::IsEmpty  )  const [inline]
 

template<class TheObjType, class TheBndType>
NCollection_UBTree& NCollection_UBTree< TheObjType, TheBndType >::operator= const NCollection_UBTree< TheObjType, TheBndType > &   )  [private]
 

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>
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

template<class TheObjType, class TheBndType>
Standard_Integer NCollection_UBTree< TheObjType, TheBndType >::Select Selector theSelector  )  const [inline]
 

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


Field Documentation

template<class TheObjType, class TheBndType>
TreeNode* NCollection_UBTree< TheObjType, TheBndType >::myLastNode [private]
 

template<class TheObjType, class TheBndType>
TreeNode* NCollection_UBTree< TheObjType, TheBndType >::myRoot [private]
 


The documentation for this class was generated from the following file:
Generated on Mon Aug 25 13:13:02 2008 for OpenCASCADE by  doxygen 1.4.1