1 // Created on: 2002-10-18
2 // Created by: Michael SAZONOV
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
7 // This library is free software; you can redistribute it and/or modify it under
8 // the terms of the GNU Lesser General Public License version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #ifndef NCollection_UBTreeFiller_HeaderFile
17 #define NCollection_UBTreeFiller_HeaderFile
19 #include <NCollection_UBTree.hxx>
20 #include <NCollection_Vector.hxx>
25 * This class is used to fill an UBTree in a random order.
26 * The quality of a tree is much better (from the point of view of
27 * the search time) if objects are added to it in a random order to
28 * avoid adding a chain of neerby objects one following each other.
30 * This class collects objects to be added, and then add them to the tree
33 template <class TheObjType, class TheBndType> class NCollection_UBTreeFiller
36 // ---------- PUBLIC TYPES ----------
38 //! Structure of pair (object, bnd box)
43 ObjBnd (const TheObjType& theObj, const TheBndType& theBnd)
44 : myObj(theObj), myBnd(theBnd) {}
46 : myObj(TheObjType()), myBnd(TheBndType()) {}
50 typedef NCollection_UBTree<TheObjType, TheBndType> UBTree;
51 typedef TYPENAME UBTree::TreeNode UBTreeNode;
54 // ---------- PUBLIC METHODS ----------
59 * Tree instance that is to be filled.
61 * Allocator for the Filler data.
63 * Takes effect when the number of items is large (order of 50,000). When
64 * it is True, the code uses the maximal randomization allowing a better
65 * balanced tree. If False, the randomization/tree balance are worse but
66 * the tree filling is faster due to better utilisation of CPU L1/L2 cache.
68 NCollection_UBTreeFiller (UBTree& theTree,
69 const Handle(NCollection_BaseAllocator)& theAlloc=0L,
70 const Standard_Boolean isFullRandom = Standard_True)
71 : myTree(theTree), mySeqPtr(1000, theAlloc),
72 mySeed(1), myIsFullRandom (isFullRandom)
75 // We use srand/rand for a single threaded application
76 // and rand_r for a multi threaded one.
77 // _REENTRANT must be defined for a multi threaded application.
82 //! Adds a pair (theObj, theBnd) to my sequence
83 void Add (const TheObjType& theObj, const TheBndType& theBnd)
84 { mySeqPtr.Append (ObjBnd (theObj, theBnd)); }
87 * Fills the tree with the objects from my sequence. This method clears
88 * the internal buffer of added items making sure that no item would be added
91 * the number of objects added to the tree.
93 Standard_EXPORT Standard_Integer Fill ();
96 * Remove all data from Filler, partculary if the Tree no more needed
97 * so the destructor of this Filler should not populate the useless Tree.
99 void Reset() { mySeqPtr.Clear(); }
102 * Check the filled tree for the total number of items and the balance
103 * outputting these results to ostream.
105 * the tree size (the same value is returned by method Fill()).
107 Standard_EXPORT Standard_Integer CheckTree (Standard_OStream& theStream);
110 * Destructor. Fills the tree with accumulated items if they have not been
111 * passed by a previous call of method Fill().
113 ~NCollection_UBTreeFiller ()
115 if (mySeqPtr.Length() > 0)
116 #ifdef OCCT_DEBUG_UBTREE
117 cout << "~NCollection_UBTreeFiller: " << Fill()
118 << " objects added to the tree" << endl;
126 // Assignment operator is made empty and private in order to
127 // avoid warning on MSVC (C4512)
128 void operator = (const NCollection_UBTreeFiller&) {}
130 static Standard_Real checkNode (const UBTreeNode& theNode,
131 const Standard_Integer theLength,
132 Standard_Integer& theNumber);
136 // ---------- PRIVATE FIELDS ----------
139 NCollection_Vector<ObjBnd> mySeqPtr;
140 int mySeed; //!< seed for rand
141 Standard_Boolean myIsFullRandom;
145 inline int take_random (int * theSeed)
147 return rand_r ((unsigned *) theSeed);
150 inline int take_random (int *)
156 //=======================================================================
159 //=======================================================================
161 template <class TheObjType, class TheBndType>
162 Standard_Integer NCollection_UBTreeFiller<TheObjType,TheBndType>::Fill ()
164 Standard_Integer i, nbAdd = mySeqPtr.Length();
165 // Fisher-Yates randomization
167 for (i = nbAdd; i > 0; i--) {
168 unsigned int ind = take_random(&mySeed);
170 const unsigned int ind1 = take_random(&mySeed);
174 const ObjBnd& aObjBnd = mySeqPtr(ind);
175 myTree.Add (aObjBnd.myObj, aObjBnd.myBnd);
176 mySeqPtr(ind) = mySeqPtr(i-1);
179 for (i = nbAdd; i > 0; i--) {
180 unsigned int ind = take_random(&mySeed);
181 ind = i - (ind % i) - 1;
182 const ObjBnd& aObjBnd = mySeqPtr(ind);
183 myTree.Add (aObjBnd.myObj, aObjBnd.myBnd);
184 mySeqPtr(ind) = mySeqPtr(i-1);
190 //=======================================================================
191 //function : CheckTree
193 //=======================================================================
195 template <class TheObjType, class TheBndType>
196 Standard_Integer NCollection_UBTreeFiller<TheObjType,TheBndType>::CheckTree
197 (Standard_OStream& theStream)
199 Standard_Integer aNumber(0);
200 const Standard_Real aLen = checkNode (myTree.Root(), 0, aNumber);
201 const Standard_Real num = (double) aNumber;
202 const Standard_Real aLen1 = sqrt (aLen / num);
203 const Standard_Real aLen0 = log(num) / log(2.);
205 sprintf (buf, "Checking UBTree:%8d leaves, balance =%7.2f",
206 aNumber, aLen1 / aLen0);
207 theStream << buf << endl;
211 //=======================================================================
212 //function : checkNode
214 //=======================================================================
216 template <class TheObjType, class TheBndType>
217 Standard_Real NCollection_UBTreeFiller<TheObjType,TheBndType>::checkNode
218 (const TYPENAME NCollection_UBTree<TheObjType, TheBndType>::TreeNode& theNode,
219 const Standard_Integer theLength,
220 Standard_Integer& theNumber)
222 Standard_Real aLength;
223 if (!theNode.IsLeaf())
224 aLength = (checkNode (theNode.Child(0), theLength+1, theNumber) +
225 checkNode (theNode.Child(1), theLength+1, theNumber));
228 aLength = theLength * theLength;