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> | |
2674244c | 21 | |
22 | #include <random> | |
7fd59977 | 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) |
e1c1b6b9 | 71 | : myTree(theTree), mySeqPtr(256, theAlloc), |
2674244c | 72 | myRandGen (5489u /* == std::mt19937::default_seed, not defined in older environments, e.g, on Debian 6.0 with GCC 4.4.5 */), |
73 | myIsFullRandom (isFullRandom) {} | |
7fd59977 | 74 | |
75 | //! Adds a pair (theObj, theBnd) to my sequence | |
76 | void Add (const TheObjType& theObj, const TheBndType& theBnd) | |
77 | { mySeqPtr.Append (ObjBnd (theObj, theBnd)); } | |
78 | ||
79 | /** | |
80 | * Fills the tree with the objects from my sequence. This method clears | |
81 | * the internal buffer of added items making sure that no item would be added | |
82 | * twice. | |
83 | * @return | |
84 | * the number of objects added to the tree. | |
85 | */ | |
be5c3602 | 86 | Standard_Integer Fill (); |
7fd59977 | 87 | |
d11ab6c3 A |
88 | /** |
89 | * Remove all data from Filler, partculary if the Tree no more needed | |
90 | * so the destructor of this Filler should not populate the useless Tree. | |
91 | */ | |
92 | void Reset() { mySeqPtr.Clear(); } | |
93 | ||
7fd59977 | 94 | /** |
95 | * Check the filled tree for the total number of items and the balance | |
96 | * outputting these results to ostream. | |
97 | * @return | |
98 | * the tree size (the same value is returned by method Fill()). | |
99 | */ | |
be5c3602 | 100 | Standard_Integer CheckTree (Standard_OStream& theStream); |
7fd59977 | 101 | |
102 | /** | |
103 | * Destructor. Fills the tree with accumulated items if they have not been | |
104 | * passed by a previous call of method Fill(). | |
105 | */ | |
106 | ~NCollection_UBTreeFiller () | |
107 | { | |
108 | if (mySeqPtr.Length() > 0) | |
0797d9d3 | 109 | #ifdef OCCT_DEBUG_UBTREE |
7fd59977 | 110 | cout << "~NCollection_UBTreeFiller: " << Fill() |
111 | << " objects added to the tree" << endl; | |
112 | #else | |
113 | Fill(); | |
114 | #endif | |
115 | } | |
116 | ||
117 | private: | |
118 | ||
119 | // Assignment operator is made empty and private in order to | |
120 | // avoid warning on MSVC (C4512) | |
121 | void operator = (const NCollection_UBTreeFiller&) {} | |
122 | ||
123 | static Standard_Real checkNode (const UBTreeNode& theNode, | |
124 | const Standard_Integer theLength, | |
125 | Standard_Integer& theNumber); | |
126 | ||
127 | ||
128 | private: | |
129 | // ---------- PRIVATE FIELDS ---------- | |
130 | ||
131 | UBTree& myTree; | |
132 | NCollection_Vector<ObjBnd> mySeqPtr; | |
2674244c | 133 | std::mt19937 myRandGen; //!< random number generator |
7fd59977 | 134 | Standard_Boolean myIsFullRandom; |
135 | }; | |
136 | ||
7fd59977 | 137 | //======================================================================= |
138 | //function : Fill | |
139 | //purpose : | |
140 | //======================================================================= | |
141 | ||
142 | template <class TheObjType, class TheBndType> | |
143 | Standard_Integer NCollection_UBTreeFiller<TheObjType,TheBndType>::Fill () | |
144 | { | |
145 | Standard_Integer i, nbAdd = mySeqPtr.Length(); | |
146 | // Fisher-Yates randomization | |
147 | if (myIsFullRandom) | |
148 | for (i = nbAdd; i > 0; i--) { | |
2674244c | 149 | unsigned int ind = myRandGen(); |
7fd59977 | 150 | ind = ind % i; |
151 | const ObjBnd& aObjBnd = mySeqPtr(ind); | |
152 | myTree.Add (aObjBnd.myObj, aObjBnd.myBnd); | |
153 | mySeqPtr(ind) = mySeqPtr(i-1); | |
154 | } | |
155 | else | |
156 | for (i = nbAdd; i > 0; i--) { | |
2674244c | 157 | unsigned int ind = myRandGen(); |
7fd59977 | 158 | ind = i - (ind % i) - 1; |
159 | const ObjBnd& aObjBnd = mySeqPtr(ind); | |
160 | myTree.Add (aObjBnd.myObj, aObjBnd.myBnd); | |
161 | mySeqPtr(ind) = mySeqPtr(i-1); | |
162 | } | |
163 | mySeqPtr.Clear(); | |
164 | return nbAdd; | |
165 | } | |
166 | ||
167 | //======================================================================= | |
168 | //function : CheckTree | |
169 | //purpose : | |
170 | //======================================================================= | |
171 | ||
172 | template <class TheObjType, class TheBndType> | |
173 | Standard_Integer NCollection_UBTreeFiller<TheObjType,TheBndType>::CheckTree | |
174 | (Standard_OStream& theStream) | |
175 | { | |
176 | Standard_Integer aNumber(0); | |
177 | const Standard_Real aLen = checkNode (myTree.Root(), 0, aNumber); | |
178 | const Standard_Real num = (double) aNumber; | |
179 | const Standard_Real aLen1 = sqrt (aLen / num); | |
180 | const Standard_Real aLen0 = log(num) / log(2.); | |
181 | char buf[128]; | |
182 | sprintf (buf, "Checking UBTree:%8d leaves, balance =%7.2f", | |
183 | aNumber, aLen1 / aLen0); | |
184 | theStream << buf << endl; | |
185 | return aNumber; | |
186 | } | |
187 | ||
188 | //======================================================================= | |
189 | //function : checkNode | |
190 | //purpose : | |
191 | //======================================================================= | |
192 | ||
193 | template <class TheObjType, class TheBndType> | |
194 | Standard_Real NCollection_UBTreeFiller<TheObjType,TheBndType>::checkNode | |
195 | (const TYPENAME NCollection_UBTree<TheObjType, TheBndType>::TreeNode& theNode, | |
196 | const Standard_Integer theLength, | |
197 | Standard_Integer& theNumber) | |
198 | { | |
199 | Standard_Real aLength; | |
200 | if (!theNode.IsLeaf()) | |
201 | aLength = (checkNode (theNode.Child(0), theLength+1, theNumber) + | |
202 | checkNode (theNode.Child(1), theLength+1, theNumber)); | |
203 | else { | |
204 | theNumber++; | |
205 | aLength = theLength * theLength; | |
206 | } | |
207 | return aLength; | |
208 | } | |
209 | ||
210 | #endif |