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 #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.
  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(1000, theAlloc),
  72       mySeed(1), myIsFullRandom (isFullRandom)
  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
  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
 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 OCCT_DEBUG_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