Commit | Line | Data |
---|---|---|
b311480e | 1 | // Created on: 2002-10-18 |
2 | // Created by: Michael SAZONOV | |
973c2be1 | 3 | // Copyright (c) 2002-2014 OPEN CASCADE SAS |
b311480e | 4 | // |
973c2be1 | 5 | // This file is part of Open CASCADE Technology software library. |
b311480e | 6 | // |
d5f74e42 | 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 | |
973c2be1 | 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. | |
b311480e | 12 | // |
973c2be1 | 13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement. | |
7fd59977 | 15 | |
16 | #ifndef NCollection_UBTreeFiller_HeaderFile | |
17 | #define NCollection_UBTreeFiller_HeaderFile | |
18 | ||
19 | #include <NCollection_UBTree.hxx> | |
20 | #include <NCollection_Vector.hxx> | |
21 | #include <stdlib.h> | |
22 | #include <stdio.h> | |
23 | ||
24 | /** | |
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. | |
29 | * | |
30 | * This class collects objects to be added, and then add them to the tree | |
31 | * in a random order. | |
32 | */ | |
33 | template <class TheObjType, class TheBndType> class NCollection_UBTreeFiller | |
34 | { | |
35 | public: | |
36 | // ---------- PUBLIC TYPES ---------- | |
37 | ||
38 | //! Structure of pair (object, bnd box) | |
39 | struct ObjBnd | |
40 | { | |
41 | TheObjType myObj; | |
42 | TheBndType myBnd; | |
43 | ObjBnd (const TheObjType& theObj, const TheBndType& theBnd) | |
44 | : myObj(theObj), myBnd(theBnd) {} | |
45 | ObjBnd () | |
46 | : myObj(TheObjType()), myBnd(TheBndType()) {} | |
47 | }; | |
48 | ||
49 | //! UBTree algorithm | |
50 | typedef NCollection_UBTree<TheObjType, TheBndType> UBTree; | |
51 | typedef TYPENAME UBTree::TreeNode UBTreeNode; | |
52 | ||
53 | ||
54 | // ---------- PUBLIC METHODS ---------- | |
55 | ||
56 | /** | |
57 | * Constructor. | |
58 | * @param theTree | |
59 | * Tree instance that is to be filled. | |
d11ab6c3 A |
60 | * @param theAlloc |
61 | * Allocator for the Filler data. | |
7fd59977 | 62 | * @param isFullRandom |
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. | |
67 | */ | |
68 | NCollection_UBTreeFiller (UBTree& theTree, | |
857ffd5e | 69 | const Handle(NCollection_BaseAllocator)& theAlloc=0L, |
7fd59977 | 70 | const Standard_Boolean isFullRandom = Standard_True) |
d11ab6c3 A |
71 | : myTree(theTree), mySeqPtr(1000, theAlloc), |
72 | mySeed(1), myIsFullRandom (isFullRandom) | |
7fd59977 | 73 | { |
74 | #ifndef _REENTRANT | |
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. | |
78 | srand (mySeed); | |
79 | #endif | |
80 | } | |
81 | ||
82 | //! Adds a pair (theObj, theBnd) to my sequence | |
83 | void Add (const TheObjType& theObj, const TheBndType& theBnd) | |
84 | { mySeqPtr.Append (ObjBnd (theObj, theBnd)); } | |
85 | ||
86 | /** | |
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 | |
89 | * twice. | |
90 | * @return | |
91 | * the number of objects added to the tree. | |
92 | */ | |
93 | Standard_EXPORT Standard_Integer Fill (); | |
94 | ||
d11ab6c3 A |
95 | /** |
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. | |
98 | */ | |
99 | void Reset() { mySeqPtr.Clear(); } | |
100 | ||
7fd59977 | 101 | /** |
102 | * Check the filled tree for the total number of items and the balance | |
103 | * outputting these results to ostream. | |
104 | * @return | |
105 | * the tree size (the same value is returned by method Fill()). | |
106 | */ | |
107 | Standard_EXPORT Standard_Integer CheckTree (Standard_OStream& theStream); | |
108 | ||
109 | /** | |
110 | * Destructor. Fills the tree with accumulated items if they have not been | |
111 | * passed by a previous call of method Fill(). | |
112 | */ | |
113 | ~NCollection_UBTreeFiller () | |
114 | { | |
115 | if (mySeqPtr.Length() > 0) | |
116 | #ifdef DEB_UBTREE | |
117 | cout << "~NCollection_UBTreeFiller: " << Fill() | |
118 | << " objects added to the tree" << endl; | |
119 | #else | |
120 | Fill(); | |
121 | #endif | |
122 | } | |
123 | ||
124 | private: | |
125 | ||
126 | // Assignment operator is made empty and private in order to | |
127 | // avoid warning on MSVC (C4512) | |
128 | void operator = (const NCollection_UBTreeFiller&) {} | |
129 | ||
130 | static Standard_Real checkNode (const UBTreeNode& theNode, | |
131 | const Standard_Integer theLength, | |
132 | Standard_Integer& theNumber); | |
133 | ||
134 | ||
135 | private: | |
136 | // ---------- PRIVATE FIELDS ---------- | |
137 | ||
138 | UBTree& myTree; | |
139 | NCollection_Vector<ObjBnd> mySeqPtr; | |
140 | int mySeed; //!< seed for rand | |
141 | Standard_Boolean myIsFullRandom; | |
142 | }; | |
143 | ||
144 | #ifdef _REENTRANT | |
145 | inline int take_random (int * theSeed) | |
146 | { | |
147 | return rand_r ((unsigned *) theSeed); | |
148 | } | |
149 | #else | |
150 | inline int take_random (int *) | |
151 | { | |
152 | return rand(); | |
153 | } | |
154 | #endif | |
155 | ||
156 | //======================================================================= | |
157 | //function : Fill | |
158 | //purpose : | |
159 | //======================================================================= | |
160 | ||
161 | template <class TheObjType, class TheBndType> | |
162 | Standard_Integer NCollection_UBTreeFiller<TheObjType,TheBndType>::Fill () | |
163 | { | |
164 | Standard_Integer i, nbAdd = mySeqPtr.Length(); | |
165 | // Fisher-Yates randomization | |
166 | if (myIsFullRandom) | |
167 | for (i = nbAdd; i > 0; i--) { | |
168 | unsigned int ind = take_random(&mySeed); | |
169 | if (i > RAND_MAX) { | |
170 | const unsigned int ind1 = take_random(&mySeed); | |
171 | ind += (ind1 << 15); | |
172 | } | |
173 | ind = ind % i; | |
174 | const ObjBnd& aObjBnd = mySeqPtr(ind); | |
175 | myTree.Add (aObjBnd.myObj, aObjBnd.myBnd); | |
176 | mySeqPtr(ind) = mySeqPtr(i-1); | |
177 | } | |
178 | else | |
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); | |
185 | } | |
186 | mySeqPtr.Clear(); | |
187 | return nbAdd; | |
188 | } | |
189 | ||
190 | //======================================================================= | |
191 | //function : CheckTree | |
192 | //purpose : | |
193 | //======================================================================= | |
194 | ||
195 | template <class TheObjType, class TheBndType> | |
196 | Standard_Integer NCollection_UBTreeFiller<TheObjType,TheBndType>::CheckTree | |
197 | (Standard_OStream& theStream) | |
198 | { | |
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.); | |
204 | char buf[128]; | |
205 | sprintf (buf, "Checking UBTree:%8d leaves, balance =%7.2f", | |
206 | aNumber, aLen1 / aLen0); | |
207 | theStream << buf << endl; | |
208 | return aNumber; | |
209 | } | |
210 | ||
211 | //======================================================================= | |
212 | //function : checkNode | |
213 | //purpose : | |
214 | //======================================================================= | |
215 | ||
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) | |
221 | { | |
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)); | |
226 | else { | |
227 | theNumber++; | |
228 | aLength = theLength * theLength; | |
229 | } | |
230 | return aLength; | |
231 | } | |
232 | ||
233 | #endif |