/usr/include/oce/NCollection_EBTree.hxx is in liboce-foundation-dev 0.17.2-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 | // Created on: 2002-07-30
// Created by: Michael SAZONOV
// Copyright (c) 2002-2014 OPEN CASCADE SAS
//
// This file is part of Open CASCADE Technology software library.
//
// This library is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License version 2.1 as published
// by the Free Software Foundation, with special exception defined in the file
// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
// distribution for complete text of the license and disclaimer of any warranty.
//
// Alternatively, this file may be used under the terms of Open CASCADE
// commercial license or contractual agreement.
#ifndef NCollection_EBTree_HeaderFile
#define NCollection_EBTree_HeaderFile
#include <NCollection_UBTree.hxx>
#include <Standard_DefineHandle.hxx>
#include <MMgt_TShared.hxx>
#include <NCollection_List.hxx>
#include <TColStd_SequenceOfInteger.hxx>
#include <NCollection_DataMap.hxx>
/**
* The algorithm of unbalanced binary tree of overlapped bounding boxes with
* the possibility of deleting objects from the tree.
*
* In addition to the requirements to the object type defined in the parent
* class this class requires that the object can be hashed and compared to
* another object (functions HashCode and IsEqual are defined for it), since
* the class NCollection_DataMap is used where the object plays the role of
* the key.
*/
template <class TheObjType, class TheBndType> class NCollection_EBTree
: public NCollection_UBTree <TheObjType, TheBndType>
{
public:
typedef NCollection_UBTree <TheObjType, TheBndType> UBTree;
typedef TYPENAME UBTree::TreeNode TreeNode;
// ---------- PUBLIC METHODS ----------
/**
* Constructor.
*/
NCollection_EBTree (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
: UBTree (theAllocator) {}
/**
* Extends the functionality of the parent method by maintaining
* the map myObjNodeMap. Redefined virtual method
* @return
* False if the tree already contains theObj.
*/
Standard_EXPORT Standard_Boolean Add (const TheObjType& theObj,
const TheBndType& theBnd);
/**
* Removes the given object and updates the tree.
* @return
* False if the tree does not contain theObj
*/
Standard_EXPORT Standard_Boolean Remove (const TheObjType& theObj);
/**
* @return
* True if the tree contains the object.
*/
Standard_Boolean Contains (const TheObjType& theObj) const
{ return myObjNodeMap.IsBound (theObj); }
/**
* @return
* The leaf node containing the object.
*/
const TreeNode& FindNode (const TheObjType& theObj) const
{ return *myObjNodeMap.Find (theObj); }
/**
* Clears the contents of the tree. Redefined virtual method
*/
void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L)
{ myObjNodeMap.Clear(); UBTree::Clear(aNewAlloc); }
private:
// ---------- PRIVATE METHODS ----------
/// Copy constructor (prohibited).
NCollection_EBTree (const NCollection_EBTree&);
/// Assignment operator (prohibited).
NCollection_EBTree& operator = (const NCollection_EBTree&);
// ---------- PRIVATE FIELDS ----------
NCollection_DataMap <TheObjType, TreeNode*>
myObjNodeMap; ///< map of object to node pointer
};
// ================== METHODS TEMPLATES =====================
//=======================================================================
//function : Add
//purpose : Updates the tree with a new object and its bounding box.
// Returns false if the tree already contains theObj.
//=======================================================================
template <class TheObjType, class TheBndType>
Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Add
(const TheObjType& theObj,
const TheBndType& theBnd)
{
Standard_Boolean result = Standard_False;
if (!Contains (theObj)) {
// Add object in the tree using parent method
UBTree::Add (theObj, theBnd);
// Update the map
TreeNode& aNewNode = this->ChangeLastNode();
myObjNodeMap.Bind (theObj, &aNewNode);
// If the new node is not the root (has a parent) check the neighbour node
if (!aNewNode.IsRoot()) {
TreeNode& aNeiNode = aNewNode.ChangeParent().ChangeChild(0);
if (aNeiNode.IsLeaf()) {
myObjNodeMap.UnBind (aNeiNode.Object());
myObjNodeMap.Bind (aNeiNode.Object(), &aNeiNode);
}
}
result = Standard_True;
}
return result;
}
//=======================================================================
//function : Remove
//purpose : Removes the given object and updates the tree.
// Returns false if the tree does not contain theObj.
//=======================================================================
template <class TheObjType, class TheBndType>
Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Remove
(const TheObjType& theObj)
{
Standard_Boolean result = Standard_False;
if (Contains (theObj)) {
TreeNode* pNode = myObjNodeMap (theObj);
if (pNode->IsRoot()) {
// it is the root, so clear all the tree
Clear();
}
else {
// it is a child of some parent,
// so kill the child that contains theObj
// and update bounding boxes of all ancestors
myObjNodeMap.UnBind (theObj);
TreeNode* pParent = &pNode->ChangeParent();
pParent->Kill ((pNode == &pParent->Child(0) ? 0 : 1),
this->Allocator());
if (pParent->IsLeaf()) {
// the parent node became a leaf, so update the map
myObjNodeMap.UnBind (pParent->Object());
myObjNodeMap.Bind (pParent->Object(), pParent);
}
while (!pParent->IsRoot()) {
pParent = &pParent->ChangeParent();
pParent->ChangeBnd() = pParent->Child(0).Bnd();
pParent->ChangeBnd().Add (pParent->Child(1).Bnd());
}
}
result = Standard_True;
}
return result;
}
// ======================================================================
// Declaration of handled version of NCollection_EBTree.
// In the macros below the arguments are:
// _HEBTREE - the desired name of handled class
// _OBJTYPE - the name of the object type
// _BNDTYPE - the name of the bounding box type
// _HUBTREE - the name of parent class
// (defined using macro DEFINE_HUBTREE)
#define DEFINE_HEBTREE(_HEBTREE, _OBJTYPE, _BNDTYPE, _HUBTREE) \
class _HEBTREE : public _HUBTREE \
{ \
public: \
typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree; \
typedef NCollection_EBTree <_OBJTYPE, _BNDTYPE> EBTree; \
\
_HEBTREE () : _HUBTREE(new EBTree) {} \
/* Empty constructor */ \
\
/* Access to the methods of EBTree */ \
\
Standard_Boolean Remove (const _OBJTYPE& theObj) \
{ return ChangeETree().Remove (theObj); } \
\
Standard_Boolean Contains (const _OBJTYPE& theObj) const \
{ return ETree().Contains (theObj); } \
\
const UBTree::TreeNode& FindNode (const _OBJTYPE& theObj) const \
{ return ETree().FindNode (theObj); } \
\
/* Access to the extended tree algorithm */ \
\
const EBTree& ETree () const { return (const EBTree&) Tree(); } \
EBTree& ChangeETree () { return (EBTree&) ChangeTree(); } \
\
DEFINE_STANDARD_RTTI (_HEBTREE) \
/* Type management */ \
}; \
DEFINE_STANDARD_HANDLE (_HEBTREE, _HUBTREE)
#define IMPLEMENT_HEBTREE(_HEBTREE, _HUBTREE) \
IMPLEMENT_STANDARD_HANDLE (_HEBTREE, _HUBTREE) \
IMPLEMENT_STANDARD_RTTIEXT(_HEBTREE, _HUBTREE)
#endif
|