DtNTree.h

Go to the documentation of this file.

/****************************************************************************** 
** Copyright (c) 2016 MAK Technologies, Inc. 
** All rights reserved. 
******************************************************************************/ 


#include <boost/shared_ptr.hpp>
#include <boost/weak_ptr.hpp>
#include <boost/enable_shared_from_this.hpp>

#include <cassert>

namespace makVrv
{
   class DtNTreeNullMutexPolicy
   {
   public:
      class scoped_lock
      {
      public:
         explicit scoped_lock(DtNTreeNullMutexPolicy&, bool=true) { }

         bool upgrade_to_writer()   { return true; }
         void downgrade_to_reader() { }
         void release()             { }
      };
   };

   template <typename Tree>
   struct DtNTreeSharedPointerTraits
   {
      typedef boost::shared_ptr<Tree> Ptr;
      typedef boost::weak_ptr<Tree>   ParentPtr;
   };

   template <typename Tree>
   struct DtNTreeWeakPointerTraits
   {
      typedef boost::weak_ptr<Tree>   Ptr;
      typedef boost::shared_ptr<Tree> ParentPtr;
   };

   template <
      typename T,
      unsigned int Dimensions = 3,
      typename Mutex = DtNTreeNullMutexPolicy,
      template <typename> class SubcellTraits = DtNTreeSharedPointerTraits,
      typename BoundsType = double
   >
   class DtNTree
      : public boost::enable_shared_from_this< DtNTree<T,Dimensions,Mutex,SubcellTraits,BoundsType> >
   {

      template <unsigned int A, unsigned int B>
      struct Power
      {
         static const unsigned int value = A * Power<A, B - 1>::value;
      };
      template <unsigned int A>
      struct Power<A, 0>
      {
         static const unsigned int value = 1;
      };


      template <typename Z>
      static boost::shared_ptr<Z> Get(const boost::shared_ptr<Z>& p) { return p ;}

      template <typename Z>
      static boost::shared_ptr<Z> Get(const boost::weak_ptr<Z>& p)   { return p.lock(); }

      template <typename Z>
      static void Set(boost::shared_ptr<Z>& p, const boost::shared_ptr<Z>& to) { p = to; }

      template <typename Z>
      static void Set(boost::shared_ptr<Z>& p, const boost::weak_ptr<Z>& to)   { p = to.lock(); }

      template <typename Z>
      static void Set(boost::weak_ptr<Z>& p, const boost::shared_ptr<Z>& to)   { p = to; }

      template <typename Z>
      static void Set(boost::weak_ptr<Z>& p, const boost::weak_ptr<Z>& to)     { p = to; }

      typedef typename SubcellTraits<DtNTree>::Ptr       Ptr;
      typedef typename SubcellTraits<DtNTree>::ParentPtr ParentPtr;

   public:
      class Query;
      friend class Query;

      static const unsigned int NumberOfIndices = Power<2, Dimensions>::value;

      struct Range
      {
         Range()
            : minimum(std::numeric_limits<BoundsType>::min())
            , maximum(std::numeric_limits<BoundsType>::max()) { }

         Range(BoundsType min, BoundsType max)
            : minimum(min), maximum(max) { }

         double size() const
         {
            return maximum - minimum;
         }

         bool intersects(const Range& other) const
         {
            if (maximum < other.minimum) return false;

            if (other.maximum < minimum) return false;

            return true;
         }

         BoundsType minimum, maximum;
      };

      class Bounds
      {
      public:
         Bounds makeSubBounds(unsigned int index) const
         {
            Bounds newBounds(*this);

            for (unsigned int bit=1, d=0; d < Dimensions; ++d, bit=bit<<1)
            {
               // compute center point of range for this dimension
               Range r = range(d);
               BoundsType middle = ((r.maximum - r.minimum)/2) + r.minimum;

               // if the bit for this dimension is 1 then it will be from
               // the center to the max, otherwise from the min to the center
               // min and max are set when myRanges is initialized
               if (index & bit)
               {
                  newBounds.range(d).minimum = middle;
               }
               else
               {
                  newBounds.range(d).maximum = middle;
               }
            }

            return newBounds;
         }

         double size() const
         {
            double value = 1;

            for (unsigned int d=0; d < Dimensions; ++d)
            {
               value *= range(d).size();
            }

            return value;
         }

         bool intersects(const Bounds& other) const
         {
            for (unsigned int d=0; d < Dimensions; ++d)
            {
               // if any of the dimensions don't overlap then the entire thing doesn't
               if (!range(d).intersects(other.range(d)))
               {
                  return false;
               }
            }

            return true;
         }


         Range&       range(unsigned int i)       { assert(i < Dimensions); return myRanges[i]; }
         const Range& range(unsigned int i) const { assert(i < Dimensions); return myRanges[i]; }

      private:
         Range myRanges[Dimensions];
      };

      class Subcell
      {
      public:
         const Bounds& bounds() const { return myBounds; }

         boost::shared_ptr<DtNTree> getPtr(DtNTree& tree, Query& query)
         {
            boost::shared_ptr<DtNTree> child;

            // see if there's already a child there
            typename Mutex::scoped_lock lock(myMutex, false);
            Set(child, myTree);

            // if not then we'll see if we need to create it
            if (!child)
            {
               // if we're not going to create a subcell then return null
               // the caller will have to deal with this case
               if (!query.shouldCreateSubcell(*this))
               {
                  return boost::shared_ptr<DtNTree>();
               }

               // if this returns false then another lock got the write lock and might
               // have created the child, have to check again
               if (!lock.upgrade_to_writer())
               {
                  Set(child, myTree);
               }

               // now we have the write lock and we know there's no child
               // create it and store it
               // we have a shared pointer to it on the stack, don't need the mutex anymore
               if (!child)
               {
                  child = query.createSubcell(tree, *this);
                  Set(myTree, child);
               }
            }

            return child;
         }

      private:
         friend class DtNTree;

         void init(const Bounds& b) { myBounds = b; }

         Bounds myBounds;

         mutable Mutex myMutex;

         Ptr myTree;
      };

      static boost::shared_ptr<DtNTree> Create(const Bounds& bounds)
      {
         return boost::shared_ptr<DtNTree>(new DtNTree(bounds, 0));
      }

      int getLevel() const { return myLevel; }

      const Bounds& getBounds() const { return myBounds; }

      boost::shared_ptr<DtNTree> getParent() const { return Get(myParent); }


      T&       getData()       { return myData; }
      const T& getData() const { return myData; }

   protected:
      explicit DtNTree(DtNTree& parent, const Bounds& bounds)
         : myParent(parent.shared_from_this())
         , myLevel(parent.myLevel + 1)
         , myBounds(bounds)
      {
         for (unsigned int i=0; i < NumberOfIndices; ++i)
         {
            mySubcells[i].init(bounds.makeSubBounds(i));
         }
      }

      explicit DtNTree(const Bounds& bounds, unsigned int level)
         : myParent()
         , myLevel(level)
         , myBounds(bounds)
      {
         for (unsigned int i=0; i < NumberOfIndices; ++i)
         {
            mySubcells[i].init(bounds.makeSubBounds(i));
         }
      }

      virtual boost::shared_ptr<DtNTree> createSubcell(Subcell& cell)
      {
         return boost::shared_ptr<DtNTree>(new DtNTree(*this, cell.bounds()));
      }

      virtual void visit(Query& query)
      {
         // search is split up into two phases so that the match function can see
         // the entire set of subareas before any recursing is done

         // holds the results of the intersection checks
         bool intersected[NumberOfIndices];

         // iterate over each subarea and check for matching
         for (unsigned int i=0; i < NumberOfIndices; ++i)
         {
            intersected[i] = query.matches(mySubcells[i]);
         }

         // iterate again over the subcells that were matched
         for (unsigned int i=0; i < NumberOfIndices; ++i)
         {
            // skip any cells that didn't match
            if (!intersected[i])
            {
               continue;
            }

            // shared pointer to child on the stack guarantees it stays alive
            boost::shared_ptr<DtNTree> child = mySubcells[i].getPtr(*this, query);

            // if we got through all the at and actually have a child, time to recurse
            if (child)
            {
               query.visit(*child);
            }
         }
      }

      const ParentPtr myParent;

      const int myLevel;

      const Bounds myBounds;

      Subcell mySubcells[NumberOfIndices];

      T myData;
   };

   template <
      typename T,
      unsigned int Dimensions,
      typename Mutex,
      template <typename> class SubcellPolicy,
      typename BoundsType
   >
   class DtNTree<T,Dimensions,Mutex,SubcellPolicy,BoundsType>::Query
   {
   public:
      virtual ~Query() { }

      virtual bool matches(const Subcell& cell) = 0;

      virtual bool shouldCreateSubcell(const Subcell& cell) = 0;

      virtual boost::shared_ptr<DtNTree> createSubcell(DtNTree& tree, Subcell& cell)
      {
         return tree.createSubcell(cell);
      }

      virtual void visit(DtNTree& tree)
      {
         tree.visit(*this);
      }

   protected:
      Subcell& getSubcell(DtNTree& tree, unsigned int i)
      {
         assert(i < sizeof(tree.mySubcells));
         return tree.mySubcells[i];
      }
   };
}