0029151: GCC 7.1 warnings "this statement may fall through" [-Wimplicit-fallthrough=]
[occt.git] / src / NCollection / NCollection_UBTreeFiller.hxx
CommitLineData
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 */
33template <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
88 /**
d11ab6c3
A
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 /**
7fd59977 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;
71c810df 133 opencascade::std::mt19937 myRandGen; //!< random number generator
7fd59977 134 Standard_Boolean myIsFullRandom;
135};
136
7fd59977 137//=======================================================================
138//function : Fill
139//purpose :
140//=======================================================================
141
142template <class TheObjType, class TheBndType>
143Standard_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
172template <class TheObjType, class TheBndType>
173Standard_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
193template <class TheObjType, class TheBndType>
194Standard_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