3171200389b385a22e30cc9a9d2002a6bf75d828
[occt.git] / src / NCollection / NCollection_UBTreeFiller.hxx
1 // Created on: 2002-10-18
2 // Created by: Michael SAZONOV
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
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.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #ifndef NCollection_UBTreeFiller_HeaderFile
17 #define NCollection_UBTreeFiller_HeaderFile
18
19 #include <NCollection_UBTree.hxx>
20 #include <NCollection_Vector.hxx>
21
22 #include <random>
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.
60    * @param theAlloc
61    *   Allocator for the Filler data.
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,
69                             const Handle(NCollection_BaseAllocator)& theAlloc=0L,
70                             const Standard_Boolean isFullRandom = Standard_True)
71     : myTree(theTree), mySeqPtr(256, theAlloc),
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) {}
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    */
86   Standard_Integer Fill ();
87
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
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    */ 
100   Standard_Integer CheckTree (Standard_OStream& theStream);
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)
109 #ifdef OCCT_DEBUG_UBTREE
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;
133   opencascade::std::mt19937             myRandGen;      //!< random number generator
134   Standard_Boolean                      myIsFullRandom;
135 };
136
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--) { 
149       unsigned int ind = myRandGen();
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--) { 
157       unsigned int ind = myRandGen();
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