[occt.git] / src / NCollection / NCollection_UBTree.hxx

// File:      NCollection_UBTree.hxx
// Created:   30.07.02 09:51:33
// Author:    Michael SAZONOV
// Copyright: Open CASCADE 2002

#ifndef NCollection_UBTree_HeaderFile
#define NCollection_UBTree_HeaderFile

#include <NCollection_BaseAllocator.hxx>
#include <NCollection_DefineAlloc.hxx>

/**
 * 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:
 * @code
 *   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)
 *   };
 * @endcode
 * 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.
 */

template <class TheObjType, class TheBndType> class NCollection_UBTree
{
 public:
  // ---------- PUBLIC TYPES ----------

  /**
   * Class defining the minimal interface of selector.
   */
  class Selector
  {
  public:
    /**
     * Constructor
     */
    Selector () : myStop(Standard_False) {}

    /**
     * Rejection base on the bounding type.
     * @return
     *   True if the bounding box does not conform to some selection conditions
     */
    virtual Standard_Boolean Reject (const TheBndType&) const = 0;

    /**
     * Confirm the object while making necessary tests on it. This method is
     * called when the bounding box of the object conforms to the conditions
     * (see Reject()). It is also supposed to keep record of accepted objects.
     * @return
     *   True if the object is accepted
     */
    virtual Standard_Boolean Accept (const TheObjType&) = 0;

    /**
     * This condition is checked after each call to Accept().
     * @return
     *   True signals that the selection process is stopped
     */
    Standard_Boolean Stop () const { return myStop; }

    /**
     * Destructor
     */
    virtual ~Selector () {}

  protected:
    /**
     * The method Accept() should set this flag if the selection process
     * is to be stopped
     */
    Standard_Boolean myStop;
  };

  /**
   * Class describing the node of the tree.
   * Initially the tree consists of one leaf. A node can grow to a branch
   * holding two childs:
   * - one correspondent to initial node
   * - the new one with a new object and bounding box
   */
  class TreeNode
  {
  public:
    DEFINE_STANDARD_ALLOC
    DEFINE_NCOLLECTION_ALLOC

  public:
    TreeNode (const TheObjType& theObj, const TheBndType& theBnd)
      : myBnd(theBnd), myObject(theObj), myChildren(0), myParent(0) {}

    Standard_Boolean       IsLeaf       () const { return !myChildren; }
    Standard_Boolean       IsRoot       () const { return !myParent; }
    const TheBndType&      Bnd          () const { return myBnd; }
    TheBndType&            ChangeBnd    ()       { return myBnd; }
    const TheObjType&      Object       () const { return myObject; }
    const TreeNode&        Child        (const Standard_Integer i) const
                                                 { return myChildren[i]; }
    TreeNode&              ChangeChild  (const Standard_Integer i)
                                                 { return myChildren[i]; }
    const TreeNode&        Parent       () const { return *myParent; }
    TreeNode&              ChangeParent ()       { return *myParent; }

    /**
     * Forces *this node being gemmated such a way that it becomes
     * a branch holding the previous content of *this node at the 
     * first child and theObj at the second child.
     * @param TheNewBnd
     *   new bounding box comprizing both child nodes.
     * @param theObj
     *   added object.
     * @param theBnd
     *   bounding box of theObj.
     * @theAlloc
     *   allocator providing memory to the new child nodes, provided by the
     *   calling Tree instance.
     */
    void Gemmate            (const TheBndType& theNewBnd,
                             const TheObjType& theObj,
                             const TheBndType& theBnd,
                             const Handle(NCollection_BaseAllocator)& theAlloc)
    {
      //TreeNode *children = new TreeNode [2];
      TreeNode *children = (TreeNode *) theAlloc->Allocate (2*sizeof(TreeNode));
      new (&children[0]) TreeNode;
      new (&children[1]) TreeNode;
      children[0] = *this;
      children[1].myObject = theObj;
      children[1].myBnd = theBnd;
      children[0].myParent = children[1].myParent = this;
      if (!IsLeaf()) {
        myChildren[0].myParent = children;
        myChildren[1].myParent = children;
      }
      myChildren = children;
      myBnd = theNewBnd;
      myObject = TheObjType();      // nullify myObject
    }

    /**
     * Kills the i-th child, and *this accepts the content of another child
     */
    void Kill               (const Standard_Integer i,
                             const Handle(NCollection_BaseAllocator)& theAlloc)
    {
      if (!IsLeaf()) {
        TreeNode *oldChildren = myChildren;
        const Standard_Integer iopp = 1 - i;
        myBnd      = oldChildren[iopp].myBnd;
        myObject   = oldChildren[iopp].myObject;
        myChildren = oldChildren[iopp].myChildren;
        if (!IsLeaf()) {
          myChildren[0].myParent = this;
          myChildren[1].myParent = this;
        }
        // oldChildren[0].myChildren = oldChildren[1].myChildren = 0L;
        // delete [] oldChildren;
        oldChildren[iopp].~TreeNode();
        delNode(&oldChildren[i], theAlloc); // remove the whole branch
        theAlloc->Free(oldChildren);
      }
    }

//  ~TreeNode () { if (myChildren) delete [] myChildren; }
    ~TreeNode () { myChildren = 0L; }

    /**
     * Deleter of tree node. The whole hierarchy of its children also deleted.
     * This method should be used instead of operator delete.
     */ 
    static void delNode (TreeNode * theNode,
                         Handle(NCollection_BaseAllocator)& theAlloc)
    {
      if (theNode) {
        if (theNode -> myChildren) {
          delNode (&theNode -> myChildren[0], theAlloc);
          delNode (&theNode -> myChildren[1], theAlloc);
          theAlloc->Free(theNode -> myChildren);
        }
        theNode->~TreeNode();
      }
    }

  private:
    TreeNode () : myChildren(0L), myParent(0L) {}

    TheBndType  myBnd;          ///< bounding geometry
    TheObjType  myObject;       ///< the object
    TreeNode   *myChildren;     ///< 2 children forming a b-tree
    TreeNode   *myParent;       ///< the pointer to a parent node
  };

  // ---------- PUBLIC METHODS ----------

  /**
   * Constructor.
   */
  NCollection_UBTree
    (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
      : myRoot(0L), myLastNode(0L)
  {
    if (theAllocator.IsNull())
      myAlloc = NCollection_BaseAllocator::CommonBaseAllocator();
    else
      myAlloc = theAllocator;
  }

  /**
   * Update the tree with a new object and its bounding box.
   * @param theObj
   *   added object
   * @param theBnd
   *   bounding box of the object.
   * @return
   *   always True
   */
  Standard_EXPORT virtual Standard_Boolean Add (const TheObjType& theObj,
                                                const TheBndType& theBnd);

  /**
   * Searches in the tree all objects conforming to the given selector.
   * return
   *   Number of objects accepted
   */
  virtual Standard_Integer Select (Selector& theSelector) const
        { return (IsEmpty() ? 0 : Select (Root(), theSelector)); }

  /**
   * Clears the contents of the tree.
   * @param 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.
   */
  virtual void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L)
//      { if (myRoot) delete myRoot; myRoot = 0L; }
  {
    if (myRoot) {
      TreeNode::delNode (myRoot, this->myAlloc);
      this->myAlloc->Free (myRoot);
      myRoot = 0L;
    }
    if (aNewAlloc.IsNull() == Standard_False)
      myAlloc = aNewAlloc;
  }

  Standard_Boolean IsEmpty () const { return !myRoot; }

  /**
   * @return
   *   the root node of the tree
   */
  const TreeNode& Root () const { return *myRoot; }

  /**
   * Desctructor.
   */
  virtual ~NCollection_UBTree () { Clear(); }

  /**
   * Recommended to be used only in sub-classes.
   * @return
   *   Allocator object used in this instance of UBTree.
   */
  const Handle(NCollection_BaseAllocator)& Allocator () const
  { return myAlloc; }

 protected:
  // ---------- PROTECTED METHODS ----------

  /**
   * @return
   *   the last added node
   */
  TreeNode& ChangeLastNode () { return *myLastNode; }

  /**
   * Searches in the branch all objects conforming to the given selector.
   * @return
   *   the number of objects accepted
   */
  Standard_EXPORT Standard_Integer Select (const TreeNode& theBranch,
                                           Selector& theSelector) const;

 private:
  // ---------- PRIVATE METHODS ----------

  /// Copy constructor (prohibited).
  NCollection_UBTree (const NCollection_UBTree&);

  /// Assignment operator (prohibited).
  NCollection_UBTree& operator = (const NCollection_UBTree&);

  // ---------- PRIVATE FIELDS ----------

  TreeNode                            *myRoot;    ///< root of the tree
  TreeNode                            *myLastNode;///< the last added node
  Handle(NCollection_BaseAllocator)    myAlloc;   ///< Allocator for TreeNode
};

// ================== METHODS TEMPLATES =====================
//=======================================================================
//function : Add
//purpose  : Updates the tree with a new object and its bounding box
//=======================================================================

template <class TheObjType, class TheBndType>
Standard_Boolean NCollection_UBTree<TheObjType,TheBndType>::Add
                        (const TheObjType& theObj,
                         const TheBndType& theBnd)
{
  if (IsEmpty()) {
    // Accepting first object
    myRoot = new (this->myAlloc) TreeNode (theObj, theBnd);
    myLastNode = myRoot;
    return Standard_True;
  }

  TreeNode *pBranch = myRoot;
  Standard_Boolean isOutOfBranch = pBranch->Bnd().IsOut (theBnd);

  for(;;) {
    // condition of stopping the search
    if (isOutOfBranch || pBranch->IsLeaf()) {
      TheBndType aNewBnd = theBnd;
      aNewBnd.Add (pBranch->Bnd());
      // put the new leaf aside on the level of pBranch
      pBranch->Gemmate (aNewBnd, theObj, theBnd, this->myAlloc);
      myLastNode = &pBranch->ChangeChild(1);
      break;
    }

    // Update the bounding box of the branch
    pBranch->ChangeBnd().Add (theBnd);

    // Select the best child branch to accept the object:
    // 1. First check if one branch is out and another one is not.
    // 2. Else select the child having the least union with theBnd
    Standard_Integer iBest = 0;
    Standard_Boolean isOut[] = { pBranch->Child(0).Bnd().IsOut (theBnd),
                                 pBranch->Child(1).Bnd().IsOut (theBnd) };
    if (isOut[0] != isOut[1])
      iBest = (isOut[0] ? 1 : 0);
    else {
      TheBndType aUnion[] = { theBnd, theBnd };
      aUnion[0].Add (pBranch->Child(0).Bnd());
      aUnion[1].Add (pBranch->Child(1).Bnd());
      const Standard_Real d1 = aUnion[0].SquareExtent();
      const Standard_Real d2 = aUnion[1].SquareExtent();
      if (d1 > d2)
        iBest = 1;
    }

    // Continue with the selected branch
    isOutOfBranch = isOut[iBest];
    pBranch = &pBranch->ChangeChild(iBest);
  }
  return Standard_True;
}

//=======================================================================
//function : Select
//purpose  : Recursively searches in the branch all objects conforming 
//           to the given selector.
//           Returns the number of objects found.
//=======================================================================

template <class TheObjType, class TheBndType>
Standard_Integer NCollection_UBTree<TheObjType,TheBndType>::Select
                                 (const TreeNode& theBranch,
                                  Selector&       theSelector) const
{
  // Try to reject the branch by bounding box
  if (theSelector.Reject (theBranch.Bnd()))
    return 0;

  Standard_Integer nSel = 0;

  if (theBranch.IsLeaf()) {
    // It is a leaf => try to accept the object
    if (theSelector.Accept (theBranch.Object()))
      nSel++;
  }
  else {
    // It is a branch => select from its children
    nSel += Select (theBranch.Child(0), theSelector);
    if (!theSelector.Stop())
      nSel += Select (theBranch.Child(1), theSelector);
  }

  return nSel;
}

// ======================================================================
/**
 * Declaration of handled version of NCollection_UBTree.
 * In the macros below the arguments are:
 * _HUBTREE      - the desired name of handled class
 * _OBJTYPE      - the name of the object type
 * _BNDTYPE      - the name of the bounding box type
 * _HPARENT      - the name of parent class (usually MMgt_TShared)
 */
#define DEFINE_HUBTREE(_HUBTREE, _OBJTYPE, _BNDTYPE, _HPARENT)          \
class _HUBTREE : public _HPARENT                                        \
{                                                                       \
 public:                                                                \
  typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree;               \
                                                                        \
  _HUBTREE () : myTree(new UBTree) {}                                   \
  /* Empty constructor */                                               \
  _HUBTREE (const Handle_NCollection_BaseAllocator& theAlloc)           \
     : myTree(new UBTree(theAlloc)) {}                                  \
  /* Constructor */                                                     \
                                                                        \
  /* Access to the methods of UBTree */                                 \
                                                                        \
  Standard_Boolean Add (const _OBJTYPE& theObj,                         \
                        const _BNDTYPE& theBnd)                         \
        { return ChangeTree().Add (theObj, theBnd); }                   \
                                                                        \
  Standard_Integer Select (UBTree::Selector& theSelector) const         \
        { return Tree().Select (theSelector); }                         \
                                                                        \
  void Clear () { ChangeTree().Clear (); }                              \
                                                                        \
  Standard_Boolean IsEmpty () const { return Tree().IsEmpty(); }        \
                                                                        \
  const UBTree::TreeNode& Root () const { return Tree().Root(); }       \
                                                                        \
                                                                        \
  /* Access to the tree algorithm */                                    \
                                                                        \
  const UBTree& Tree () const { return *myTree; }                       \
  UBTree&       ChangeTree () { return *myTree; }                       \
                                                                        \
  ~_HUBTREE () { delete myTree; }                                       \
  /* Destructor */                                                      \
                                                                        \
  DEFINE_STANDARD_RTTI (_HUBTREE)                                       \
  /* Type management */                                                 \
                                                                        \
 private:                                                               \
  /* Copying and assignment are prohibited  */                          \
  _HUBTREE (UBTree*);                                                   \
  _HUBTREE (const _HUBTREE&);                                           \
  void operator = (const _HUBTREE&);                                    \
                                                                        \
 private:                                                               \
  UBTree       *myTree;        /* pointer to the tree algorithm */      \
};                                                                      \
DEFINE_STANDARD_HANDLE (_HUBTREE, _HPARENT)

#define IMPLEMENT_HUBTREE(_HUBTREE, _HPARENT)                           \
IMPLEMENT_STANDARD_HANDLE (_HUBTREE, _HPARENT)                          \
IMPLEMENT_STANDARD_RTTIEXT(_HUBTREE, _HPARENT)

#endif
Commit	Line	Data
7fd59977	1	// File: NCollection_UBTree.hxx
	2	// Created: 30.07.02 09:51:33
	3	// Author: Michael SAZONOV
	4	// Copyright: Open CASCADE 2002
	5
	6	#ifndef NCollection_UBTree_HeaderFile
	7	#define NCollection_UBTree_HeaderFile
	8
	9	#include <NCollection_BaseAllocator.hxx>
1c35b92f	10	#include <NCollection_DefineAlloc.hxx>
7fd59977	11
	12	/**
	13	* The algorithm of unbalanced binary tree of overlapped bounding boxes.
	14	*
	15	* Once the tree of boxes of geometric objects is constructed, the algorithm
	16	* is capable of fast geometric selection of objects. The tree can be easily
	17	* updated by adding to it a new object with bounding box.
	18	*
	19	* The time of adding to the tree of one object is O(log(N)), where N is the
	20	* total number of objects, so the time of building a tree of N objects is
	21	* O(N(log(N)). The search time of one object is O(log(N)).
	22	*
	23	* Defining various classes inheriting NCollection_UBTree::Selector we can
	24	* perform various kinds of selection over the same b-tree object
	25	*
	26	* The object may be of any type allowing copying. Among the best suitable
	27	* solutions there can be a pointer to an object, handled object or integer
	28	* index of object inside some collection. The bounding object may have any
	29	* dimension and geometry. The minimal interface of TheBndType (besides
	30	* public empty and copy constructor and operator =) used in UBTree algorithm
	31	* is as the following:
	32	* @code
	33	* class MyBndType
	34	* {
	35	* public:
	36	* inline void Add (const MyBndType& other);
	37	* // Updates me with other bounding
	38	*
	39	* inline Standard_Boolean IsOut (const MyBndType& other) const;
	40	* // Classifies other bounding relatively me
	41	*
	42	* inline Standard_Real SquareExtent() const;
	43	* // Computes the squared maximal linear extent of me.
	44	* // (For box it is the squared diagonal of box)
	45	* };
	46	* @endcode
	47	* To select objects you need to define a class derived from UBTree::Selector
	48	* that should redefine the necessary virtual methods to maintain the
	49	* selection condition. The object of this class is also used to retrieve
	50	* selected objects after search.
	51	*/
	52
	53	template <class TheObjType, class TheBndType> class NCollection_UBTree
	54	{
	55	public:
	56	// ---------- PUBLIC TYPES ----------
	57
	58	/**
	59	* Class defining the minimal interface of selector.
	60	*/
	61	class Selector
	62	{
	63	public:
	64	/**
	65	* Constructor
	66	*/
	67	Selector () : myStop(Standard_False) {}
	68
	69	/**
	70	* Rejection base on the bounding type.
	71	* @return
	72	* True if the bounding box does not conform to some selection conditions
	73	*/
	74	virtual Standard_Boolean Reject (const TheBndType&) const = 0;
75
76	/**
77	* Confirm the object while making necessary tests on it. This method is
78	* called when the bounding box of the object conforms to the conditions
79	* (see Reject()). It is also supposed to keep record of accepted objects.
80	* @return
81	* True if the object is accepted
82	*/
83	virtual Standard_Boolean Accept (const TheObjType&) = 0;
84
85	/**
86	* This condition is checked after each call to Accept().
87	* @return
88	* True signals that the selection process is stopped
89	*/
90	Standard_Boolean Stop () const { return myStop; }
91
92	/**
93	* Destructor
94	*/
95	virtual ~Selector () {}
96
97	protected:
98	/**
99	* The method Accept() should set this flag if the selection process
100	* is to be stopped
101	*/
102	Standard_Boolean myStop;
103	};
104
105	/**
106	* Class describing the node of the tree.
107	* Initially the tree consists of one leaf. A node can grow to a branch
108	* holding two childs:
109	* - one correspondent to initial node
110	* - the new one with a new object and bounding box
111	*/
112	class TreeNode
113	{
1c35b92f	114	public:
	115	DEFINE_STANDARD_ALLOC
	116	DEFINE_NCOLLECTION_ALLOC
	117
7fd59977	118	public:
	119	TreeNode (const TheObjType& theObj, const TheBndType& theBnd)
	120	: myBnd(theBnd), myObject(theObj), myChildren(0), myParent(0) {}
	121
	122	Standard_Boolean IsLeaf () const { return !myChildren; }
	123	Standard_Boolean IsRoot () const { return !myParent; }
	124	const TheBndType& Bnd () const { return myBnd; }
	125	TheBndType& ChangeBnd () { return myBnd; }
	126	const TheObjType& Object () const { return myObject; }
	127	const TreeNode& Child (const Standard_Integer i) const
	128	{ return myChildren[i]; }
	129	TreeNode& ChangeChild (const Standard_Integer i)
	130	{ return myChildren[i]; }
	131	const TreeNode& Parent () const { return *myParent; }
	132	TreeNode& ChangeParent () { return *myParent; }
	133
	134	/**
	135	* Forces *this node being gemmated such a way that it becomes
	136	* a branch holding the previous content of *this node at the
	137	* first child and theObj at the second child.
	138	* @param TheNewBnd
	139	* new bounding box comprizing both child nodes.
	140	* @param theObj
	141	* added object.
	142	* @param theBnd
	143	* bounding box of theObj.
	144	* @theAlloc
	145	* allocator providing memory to the new child nodes, provided by the
	146	* calling Tree instance.
	147	*/
	148	void Gemmate (const TheBndType& theNewBnd,
	149	const TheObjType& theObj,
	150	const TheBndType& theBnd,
	151	const Handle(NCollection_BaseAllocator)& theAlloc)
	152	{
	153	//TreeNode *children = new TreeNode [2];
	154	TreeNode children = (TreeNode ) theAlloc->Allocate (2*sizeof(TreeNode));
	155	new (&children[0]) TreeNode;
	156	new (&children[1]) TreeNode;
	157	children[0] = *this;
	158	children[1].myObject = theObj;
	159	children[1].myBnd = theBnd;
	160	children[0].myParent = children[1].myParent = this;
	161	if (!IsLeaf()) {
	162	myChildren[0].myParent = children;
	163	myChildren[1].myParent = children;
	164	}
	165	myChildren = children;
	166	myBnd = theNewBnd;
	167	myObject = TheObjType(); // nullify myObject
	168	}
	169
	170	/**
	171	* Kills the i-th child, and *this accepts the content of another child
	172	*/
	173	void Kill (const Standard_Integer i,
	174	const Handle(NCollection_BaseAllocator)& theAlloc)
	175	{
	176	if (!IsLeaf()) {
	177	TreeNode *oldChildren = myChildren;
	178	const Standard_Integer iopp = 1 - i;
	179	myBnd = oldChildren[iopp].myBnd;
	180	myObject = oldChildren[iopp].myObject;
	181	myChildren = oldChildren[iopp].myChildren;
182	if (!IsLeaf()) {
183	myChildren[0].myParent = this;
184	myChildren[1].myParent = this;
185	}
186	// oldChildren[0].myChildren = oldChildren[1].myChildren = 0L;
187	// delete [] oldChildren;
188	oldChildren[iopp].~TreeNode();
189	delNode(&oldChildren[i], theAlloc); // remove the whole branch
190	theAlloc->Free(oldChildren);
191	}
192	}
193
194	// ~TreeNode () { if (myChildren) delete [] myChildren; }
195	~TreeNode () { myChildren = 0L; }
196
7fd59977	197	/**
	198	* Deleter of tree node. The whole hierarchy of its children also deleted.
	199	* This method should be used instead of operator delete.
	200	*/
	201	static void delNode (TreeNode * theNode,
	202	Handle(NCollection_BaseAllocator)& theAlloc)
	203	{
	204	if (theNode) {
	205	if (theNode -> myChildren) {
	206	delNode (&theNode -> myChildren[0], theAlloc);
	207	delNode (&theNode -> myChildren[1], theAlloc);
	208	theAlloc->Free(theNode -> myChildren);
	209	}
	210	theNode->~TreeNode();
	211	}
	212	}
	213
	214	private:
	215	TreeNode () : myChildren(0L), myParent(0L) {}
	216
	217	TheBndType myBnd; ///< bounding geometry
	218	TheObjType myObject; ///< the object
	219	TreeNode *myChildren; ///< 2 children forming a b-tree
	220	TreeNode *myParent; ///< the pointer to a parent node
	221	};
	222
	223	// ---------- PUBLIC METHODS ----------
	224
	225	/**
	226	* Constructor.
	227	*/
	228	NCollection_UBTree
	229	(const Handle(NCollection_BaseAllocator)& theAllocator=0L)
	230	: myRoot(0L), myLastNode(0L)
	231	{
	232	if (theAllocator.IsNull())
	233	myAlloc = NCollection_BaseAllocator::CommonBaseAllocator();
	234	else
	235	myAlloc = theAllocator;
	236	}
	237
	238	/**
	239	* Update the tree with a new object and its bounding box.
	240	* @param theObj
	241	* added object
	242	* @param theBnd
	243	* bounding box of the object.
	244	* @return
	245	* always True
	246	*/
	247	Standard_EXPORT virtual Standard_Boolean Add (const TheObjType& theObj,
	248	const TheBndType& theBnd);
	249
	250	/**
	251	* Searches in the tree all objects conforming to the given selector.
	252	* return
	253	* Number of objects accepted
	254	*/
23be7421	255	virtual Standard_Integer Select (Selector& theSelector) const
7fd59977	256	{ return (IsEmpty() ? 0 : Select (Root(), theSelector)); }
	257
	258	/**
	259	* Clears the contents of the tree.
	260	* @param aNewAlloc
	261	* Optional: a new allocator that will be used when the tree is rebuilt
	262	* anew. This makes sense if the memory allocator needs re-initialisation
	263	* (like NCollection_IncAllocator). By default the previous allocator is
	264	* kept.
	265	*/
	266	virtual void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L)
	267	// { if (myRoot) delete myRoot; myRoot = 0L; }
	268	{
	269	if (myRoot) {
	270	TreeNode::delNode (myRoot, this->myAlloc);
	271	this->myAlloc->Free (myRoot);
	272	myRoot = 0L;
	273	}
	274	if (aNewAlloc.IsNull() == Standard_False)
	275	myAlloc = aNewAlloc;
	276	}
	277
	278	Standard_Boolean IsEmpty () const { return !myRoot; }
	279
	280	/**
	281	* @return
	282	* the root node of the tree
	283	*/
	284	const TreeNode& Root () const { return *myRoot; }
	285
	286	/**
	287	* Desctructor.
	288	*/
	289	virtual ~NCollection_UBTree () { Clear(); }
	290
	291	/**
	292	* Recommended to be used only in sub-classes.
	293	* @return
	294	* Allocator object used in this instance of UBTree.
	295	*/
	296	const Handle(NCollection_BaseAllocator)& Allocator () const
	297	{ return myAlloc; }
	298
	299	protected:
	300	// ---------- PROTECTED METHODS ----------
	301
	302	/**
	303	* @return
	304	* the last added node
	305	*/
	306	TreeNode& ChangeLastNode () { return *myLastNode; }
	307
	308	/**
	309	* Searches in the branch all objects conforming to the given selector.
	310	* @return
	311	* the number of objects accepted
	312	*/
	313	Standard_EXPORT Standard_Integer Select (const TreeNode& theBranch,
	314	Selector& theSelector) const;
	315
	316	private:
	317	// ---------- PRIVATE METHODS ----------
	318
	319	/// Copy constructor (prohibited).
320	NCollection_UBTree (const NCollection_UBTree&);
321
322	/// Assignment operator (prohibited).
323	NCollection_UBTree& operator = (const NCollection_UBTree&);
324
325	// ---------- PRIVATE FIELDS ----------
326
327	TreeNode *myRoot; ///< root of the tree
328	TreeNode *myLastNode;///< the last added node
329	Handle(NCollection_BaseAllocator) myAlloc; ///< Allocator for TreeNode
330	};
331
332	// ================== METHODS TEMPLATES =====================
333	//=======================================================================
334	//function : Add
335	//purpose : Updates the tree with a new object and its bounding box
336	//=======================================================================
337
338	template <class TheObjType, class TheBndType>
339	Standard_Boolean NCollection_UBTree<TheObjType,TheBndType>::Add
340	(const TheObjType& theObj,
341	const TheBndType& theBnd)
342	{
343	if (IsEmpty()) {
344	// Accepting first object
345	myRoot = new (this->myAlloc) TreeNode (theObj, theBnd);
346	myLastNode = myRoot;
347	return Standard_True;
348	}
349
350	TreeNode *pBranch = myRoot;
351	Standard_Boolean isOutOfBranch = pBranch->Bnd().IsOut (theBnd);
352
353	for(;;) {
354	// condition of stopping the search
355	if (isOutOfBranch \|\| pBranch->IsLeaf()) {
356	TheBndType aNewBnd = theBnd;
357	aNewBnd.Add (pBranch->Bnd());
358	// put the new leaf aside on the level of pBranch
359	pBranch->Gemmate (aNewBnd, theObj, theBnd, this->myAlloc);
360	myLastNode = &pBranch->ChangeChild(1);
361	break;
362	}
363
364	// Update the bounding box of the branch
365	pBranch->ChangeBnd().Add (theBnd);
366
367	// Select the best child branch to accept the object:
368	// 1. First check if one branch is out and another one is not.
369	// 2. Else select the child having the least union with theBnd
370	Standard_Integer iBest = 0;
371	Standard_Boolean isOut[] = { pBranch->Child(0).Bnd().IsOut (theBnd),
372	pBranch->Child(1).Bnd().IsOut (theBnd) };
373	if (isOut[0] != isOut[1])
374	iBest = (isOut[0] ? 1 : 0);
375	else {
376	TheBndType aUnion[] = { theBnd, theBnd };
377	aUnion[0].Add (pBranch->Child(0).Bnd());
378	aUnion[1].Add (pBranch->Child(1).Bnd());
379	const Standard_Real d1 = aUnion[0].SquareExtent();
380	const Standard_Real d2 = aUnion[1].SquareExtent();
381	if (d1 > d2)
382	iBest = 1;
383	}
384
385	// Continue with the selected branch
386	isOutOfBranch = isOut[iBest];
387	pBranch = &pBranch->ChangeChild(iBest);
388	}
389	return Standard_True;
390	}
391
392	//=======================================================================
393	//function : Select
394	//purpose : Recursively searches in the branch all objects conforming
395	// to the given selector.
396	// Returns the number of objects found.
397	//=======================================================================
398
399	template <class TheObjType, class TheBndType>
400	Standard_Integer NCollection_UBTree<TheObjType,TheBndType>::Select
401	(const TreeNode& theBranch,
402	Selector& theSelector) const
403	{
404	// Try to reject the branch by bounding box
405	if (theSelector.Reject (theBranch.Bnd()))
406	return 0;
407
408	Standard_Integer nSel = 0;
409
410	if (theBranch.IsLeaf()) {
411	// It is a leaf => try to accept the object
412	if (theSelector.Accept (theBranch.Object()))
413	nSel++;
414	}
415	else {
416	// It is a branch => select from its children
417	nSel += Select (theBranch.Child(0), theSelector);
418	if (!theSelector.Stop())
419	nSel += Select (theBranch.Child(1), theSelector);
420	}
421
422	return nSel;
423	}
424
425	// ======================================================================
426	/**
427	* Declaration of handled version of NCollection_UBTree.
428	* In the macros below the arguments are:
429	* _HUBTREE - the desired name of handled class
430	* _OBJTYPE - the name of the object type
431	* _BNDTYPE - the name of the bounding box type
432	* _HPARENT - the name of parent class (usually MMgt_TShared)
433	*/
434	#define DEFINE_HUBTREE(_HUBTREE, _OBJTYPE, _BNDTYPE, _HPARENT) \
435	class _HUBTREE : public _HPARENT \
436	{ \
437	public: \
438	typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree; \
439	\
440	_HUBTREE () : myTree(new UBTree) {} \
441	/* Empty constructor */ \
23be7421 M	442	_HUBTREE (const Handle_NCollection_BaseAllocator& theAlloc) \
	443	: myTree(new UBTree(theAlloc)) {} \
	444	/* Constructor */ \
7fd59977	445	\
	446	/* Access to the methods of UBTree */ \
	447	\
	448	Standard_Boolean Add (const _OBJTYPE& theObj, \
	449	const _BNDTYPE& theBnd) \
	450	{ return ChangeTree().Add (theObj, theBnd); } \
	451	\
	452	Standard_Integer Select (UBTree::Selector& theSelector) const \
	453	{ return Tree().Select (theSelector); } \
	454	\
	455	void Clear () { ChangeTree().Clear (); } \
	456	\
	457	Standard_Boolean IsEmpty () const { return Tree().IsEmpty(); } \
	458	\
	459	const UBTree::TreeNode& Root () const { return Tree().Root(); } \
	460	\
	461	\
	462	/* Access to the tree algorithm */ \
	463	\
	464	const UBTree& Tree () const { return *myTree; } \
	465	UBTree& ChangeTree () { return *myTree; } \
	466	\
	467	~_HUBTREE () { delete myTree; } \
	468	/* Destructor */ \
	469	\
	470	DEFINE_STANDARD_RTTI (_HUBTREE) \
	471	/* Type management */ \
	472	\
82469411 A	473	private: \
	474	/* Copying and assignment are prohibited */ \
	475	_HUBTREE (UBTree*); \
	476	_HUBTREE (const _HUBTREE&); \
	477	void operator = (const _HUBTREE&); \
7fd59977	478	\
	479	private: \
	480	UBTree myTree; / pointer to the tree algorithm */ \
	481	}; \
	482	DEFINE_STANDARD_HANDLE (_HUBTREE, _HPARENT)
	483
	484	#define IMPLEMENT_HUBTREE(_HUBTREE, _HPARENT) \
	485	IMPLEMENT_STANDARD_HANDLE (_HUBTREE, _HPARENT) \
	486	IMPLEMENT_STANDARD_RTTIEXT(_HUBTREE, _HPARENT)
	487
7fd59977	488	#endif