include/Geant4/G4KDNode.hh

0001 //
0002 // ********************************************************************
0003 // * License and Disclaimer                                           *
0004 // *                                                                  *
0005 // * The  Geant4 software  is  copyright of the Copyright Holders  of *
0006 // * the Geant4 Collaboration.  It is provided  under  the terms  and *
0007 // * conditions of the Geant4 Software License,  included in the file *
0008 // * LICENSE and available at  http://cern.ch/geant4/license .  These *
0009 // * include a list of copyright holders.                             *
0010 // *                                                                  *
0011 // * Neither the authors of this software system, nor their employing *
0012 // * institutes,nor the agencies providing financial support for this *
0013 // * work  make  any representation or  warranty, express or implied, *
0014 // * regarding  this  software system or assume any liability for its *
0015 // * use.  Please see the license in the file  LICENSE  and URL above *
0016 // * for the full disclaimer and the limitation of liability.         *
0017 // *                                                                  *
0018 // * This  code  implementation is the result of  the  scientific and *
0019 // * technical work of the GEANT4 collaboration.                      *
0020 // * By using,  copying,  modifying or  distributing the software (or *
0021 // * any work based  on the software)  you  agree  to acknowledge its *
0022 // * use  in  resulting  scientific  publications,  and indicate your *
0023 // * acceptance of all terms of the Geant4 Software license.          *
0024 // ********************************************************************
0025 //
0026 //
0027 // Author: Mathieu Karamitros
0028
0029 // The code is developed in the framework of the ESA AO7146
0030 //
0031 // We would be very happy hearing from you, send us your feedback! :)
0032 //
0033 // In order for Geant4-DNA to be maintained and still open-source,
0034 // article citations are crucial.
0035 // If you use Geant4-DNA chemistry and you publish papers about your software,
0036 // in addition to the general paper on Geant4-DNA:
0037 //
0038 // Int. J. Model. Simul. Sci. Comput. 1 (2010) 157–178
0039 //
0040 // we would be very happy if you could please also cite the following
0041 // reference papers on chemistry:
0042 //
0043 // J. Comput. Phys. 274 (2014) 841-882
0044 // Prog. Nucl. Sci. Tec. 2 (2011) 503-508
0045
0046 #ifndef G4KDNODE_HH
0047 #define G4KDNODE_HH
0048
0049 #include <list>
0050 #include <vector>
0051 #include <deque>
0052 #include <ostream>
0053
0054 // geant4
0055 #include "G4Types.hh"
0056 #include "G4Allocator.hh"
0057
0058 class G4KDTree;
0059 class G4KDMap;
0060
0061 class G4KDNode_Base
0062 {
0063 public:
0064   //----------------------------
0065   // For root node :
0066   // parent = 0, axis = 0, side = 0
0067   G4KDNode_Base(G4KDTree*, G4KDNode_Base* /*parent*/);
0068   virtual ~G4KDNode_Base();
0069   virtual double operator[](std::size_t) const = 0;
0070   virtual void InactiveNode();
0071   virtual bool IsValid() const{ return true; }
0072
0073   //----------------------------
0074   inline G4KDTree* GetTree() const {return fTree;}
0075   inline void SetTree(G4KDTree* tree) {fTree = tree;}
0076
0077   //----------------------------
0078   G4int GetDim() const;
0079   inline G4int GetAxis() const{return (G4int)fAxis;}
0080   inline G4KDNode_Base* GetParent(){return fParent;}
0081   inline G4KDNode_Base* GetLeft(){return fLeft;}
0082   inline G4KDNode_Base* GetRight(){return fRight;}
0083
0084   //----------------------------
0085   template<typename Position>
0086     G4KDNode_Base* FindParent(const Position& x0);
0087
0088   template<typename PointT>
0089     G4KDNode_Base* Insert(PointT* point);
0090   template<typename PointT>
0091     G4KDNode_Base* Insert(const PointT& point);
0092   G4int Insert(G4KDNode_Base* newNode);
0093
0094   void PullSubTree();
0095   void RetrieveNodeList(std::list<G4KDNode_Base*>& node_list);
0096
0097   void Print(std::ostream& out, G4int level = 0) const;
0098
0099 // std::vector<std::deque<G4KDNode_Base*>::iterator>*
0100 //   GetIteratorsForSortingAlgo(G4KDMap*);
0101 // std::map<G4KDMap*, std::vector<std::deque<G4KDNode_Base*>::iterator>>*
0102 //   fpIteratorInSortingAlgo;
0103
0104 protected:
0105   //°°°°°°°°°°°
0106   // Members
0107   //°°°°°°°°°°°
0108   std::size_t fAxis; // axis : x, y, z ...
0109   G4int fSide; // left/right
0110   /* fSide == 0  : Is the root node
0111    * fSide == -1 : It is the left of the parent node
0112    * fSide == 1  : It is the right of the parent node
0113    */
0114
0115   G4KDTree* fTree{nullptr};
0116   G4KDNode_Base *fLeft{nullptr}, *fRight{nullptr}, *fParent{nullptr};
0117   /* Left : fLeft->fPosition[axis] < this->fPosition[axis]
0118    * Right : fRight->fPosition[axis] > this->fPosition[axis]
0119    * Root node : fParent = 0
0120    */
0121 private:
0122   G4KDNode_Base(const G4KDNode_Base& right);
0123   G4KDNode_Base& operator=(const G4KDNode_Base& right);
0124 };
0125
0126 /**
0127  * G4KDNode stores one entity in G4KDTree
0128  * This class is for internal use only
0129  */
0130
0131 template<typename PointT>
0132   class G4KDNode : public G4KDNode_Base
0133   {
0134   public:
0135     //----------------------------
0136     // For root node :
0137     // parent = 0, axis = 0, side = 0
0138     G4KDNode(G4KDTree*, PointT* /*point*/, G4KDNode_Base* /*parent*/);
0139     ~G4KDNode() override;
0140
0141     void *operator new(std::size_t);
0142     void operator delete(void *);
0143
0144     inline PointT* GetPoint()
0145     {
0146       return fPoint;
0147     }
0148
0149     G4double operator[](std::size_t i) const override
0150     {
0151       if(fPoint == nullptr) abort();
0152       return (*fPoint)[(G4int)i];
0153     }
0154
0155     void InactiveNode() override
0156     {
0157       fValid = false;
0158       G4KDNode_Base::InactiveNode();
0159     }
0160
0161     G4bool IsValid() const override
0162     {
0163       return fValid;
0164     }
0165
0166   protected:
0167     PointT* fPoint;
0168     G4bool fValid;
0169
0170   private:
0171     G4KDNode(const G4KDNode<PointT>& right);
0172     G4KDNode& operator=(const G4KDNode<PointT>& right);
0173
0174     static G4ThreadLocal G4Allocator<G4KDNode<PointT>>* fgAllocator;
0175   };
0176
0177 template<typename PointT>
0178   G4ThreadLocal G4Allocator<G4KDNode<PointT>>*
0179     G4KDNode<PointT>::fgAllocator = nullptr;
0180
0181 template<typename PointT>
0182   void* G4KDNode<PointT>::operator new(std::size_t)
0183   {
0184     if(!fgAllocator) fgAllocator = new G4Allocator<G4KDNode<PointT> >;
0185     return (void *) fgAllocator->MallocSingle();
0186   }
0187
0188 template<typename PointT>
0189   void G4KDNode<PointT>::operator delete(void *aNode)
0190   {
0191     fgAllocator->FreeSingle((G4KDNode<PointT> *) aNode);
0192   }
0193
0194 /**
0195  * G4KDNode stores one entity in G4KDTree
0196  * This class is for internal use only
0197  */
0198
0199 template<typename PointCopyT>
0200   class G4KDNodeCopy: public G4KDNode_Base
0201   {
0202   public:
0203     //----------------------------
0204     // For root node :
0205     // parent = 0, axis = 0, side = 0
0206     G4KDNodeCopy(G4KDTree* tree,
0207                  const PointCopyT& point,
0208                  G4KDNode_Base* parent) :
0209      G4KDNode_Base(tree, parent)
0210     {
0211       fPoint = point;
0212       fValid = true;
0213     }
0214
0215     ~G4KDNodeCopy() override= default;
0216
0217     void *operator new(std::size_t)
0218     {
0219       if(!fgAllocator) fgAllocator = new G4Allocator<G4KDNodeCopy<PointCopyT>>;
0220       return (void *) fgAllocator->MallocSingle();
0221     }
0222
0223     void operator delete(void* aNode)
0224     {
0225       fgAllocator->FreeSingle((G4KDNodeCopy<PointCopyT>*) aNode);
0226     }
0227
0228     inline const PointCopyT& GetPoint()
0229     {
0230       return fPoint;
0231     }
0232
0233     double operator[](std::size_t i) const override
0234     {
0235       return fPoint[i];
0236     }
0237
0238     void InactiveNode() override
0239     {
0240       fValid = false;
0241       G4KDNode_Base::InactiveNode();
0242     }
0243
0244     bool IsValid() const override
0245     {
0246       return fValid;
0247     }
0248
0249   protected:
0250     PointCopyT fPoint;
0251     G4bool fValid;
0252
0253   private:
0254     G4KDNodeCopy(const G4KDNodeCopy<PointCopyT>& right) :
0255           G4KDNode_Base(right), fPoint(0)
0256     {
0257       fValid = false;
0258     }
0259
0260     G4KDNodeCopy<PointCopyT>&
0261     operator=(const G4KDNodeCopy<PointCopyT>& right)
0262     {
0263       if(this == &right) return *this;
0264       fPoint = right.fPoint;
0265       fTree = right.fTree;
0266       fLeft = right.fLeft;
0267       fRight = right.fRight;
0268       fParent = right.fParent;
0269       fSide = right.fSide;
0270       fAxis = right.fAxis;
0271       return *this;
0272     }
0273
0274     static G4ThreadLocal G4Allocator<G4KDNodeCopy<PointCopyT>>* fgAllocator;
0275   };
0276
0277 template<typename PointT>
0278   G4ThreadLocal G4Allocator<G4KDNodeCopy<PointT>>*
0279     G4KDNodeCopy<PointT>::fgAllocator = nullptr;
0280
0281 #include "G4KDNode.icc"
0282
0283 #endif // G4KDNODE_HH