CellSizeDataTreeStrategy.h

Go to the documentation of this file.

#ifndef GfxTL__CELLSIZEDATATREESTRATEGY_HEADER__
#define GfxTL__CELLSIZEDATATREESTRATEGY_HEADER__
 
namespace GfxTL
{
    template <class InheritedStrategyT, class KernelT>
    struct CellSizeDataTreeStrategy
    {
        typedef typename KernelT::value_type value_type;
 
        class CellData : public InheritedStrategyT::CellData
        {
        public:
            typedef typename KernelT::value_type value_type;
            typedef unsigned int size_type;
 
            size_type
            Size() const
            {
                return m_size;
            }
 
            void
            Size(unsigned int s)
            {
                m_size = s;
            }
 
            size_type m_size;
        };
 
        template <class BaseT>
        class StrategyBase : public InheritedStrategyT::template StrategyBase<BaseT>, public KernelT
        {
        public:
            typedef typename InheritedStrategyT::template StrategyBase<BaseT> BaseType;
            typedef typename BaseT::CellType CellType;
            typedef typename KernelT::HandleType HandleType;
            typedef typename KernelT::DereferencedType DereferencedType;
            typedef std::pair<HandleType, HandleType> CellRange;
            typedef typename KernelT::value_type value_type;
            typedef StrategyBase<BaseT> ThisType;
 
        protected:
            class BuildInformation
            {
            public:
                CellRange&
                Range()
                {
                    return m_range;
                }
 
                const CellRange&
                Range() const
                {
                    return m_range;
                }
 
            private:
                CellRange m_range;
            };
 
            template <class BaseTraversalT>
            class GlobalTraversalInformation : public BaseTraversalT
            {
            };
 
            template <class BaseTraversalT>
            class TraversalInformation : public BaseTraversalT
            {
            public:
                CellRange&
                Range()
                {
                    return m_range;
                }
 
                const CellRange&
                Range() const
                {
                    return m_range;
                }
 
            private:
                CellRange m_range;
            };
 
            template <class BuildInformationT>
            void
            InitRootBuildInformation(BuildInformationT* bi) const
            {
                RootRange(&bi->Range());
            }
 
            template <class BuildInformationT>
            void
            InitBuildInformation(const CellType& parent,
                                 const BuildInformationT& parentInfo,
                                 unsigned int childIdx,
                                 BuildInformationT* bi) const
            {
                Range(parent, parentInfo.Range(), childIdx, &bi->Range());
            }
 
            template <class BuildInformationT>
            void
            InitRoot(const BuildInformationT& bi, CellType* cell)
            {
                cell->m_size = bi.Range().second - bi.Range().first;
            }
 
            template <class BuildInformationT>
            void
            InitCell(const CellType& parent,
                     const BuildInformationT& parentInfo,
                     unsigned int childIdx,
                     const BuildInformationT& bi,
                     CellType* cell)
            {
                cell->m_size = bi.Range().second - bi.Range().first;
            }
 
            template <class TraversalInformationT>
            void
            InitRootTraversalInformation(const CellType& root, TraversalInformationT* ti) const
            {
                RootRange(&ti->Range());
            }
 
            template <class TraversalInformationT>
            void
            InitTraversalInformation(const CellType& parent,
                                     const TraversalInformationT& pTi,
                                     unsigned int childIdx,
                                     TraversalInformationT* ti) const
            {
                Range(parent, pTi.Range(), childIdx, &ti->Range());
            }
 
            void
            RootRange(CellRange* r) const
            {
                r->first = KernelT::BeginHandle();
                r->second = KernelT::EndHandle();
            }
 
            void
            Range(const CellType& parent,
                  const CellRange& parentRange,
                  unsigned int child,
                  CellRange* r) const
            {
                r->first = parentRange.first;
                for (unsigned int i = 0; i < child; ++i)
                    if (&(parent[i]) > (CellType*)1)
                    {
                        r->first += parent[i].m_size;
                    }
                r->second = r->first + parent[child].m_size;
            }
 
            template <class TraversalInformationT>
            void
            GetCellRange(const CellType& cell,
                         const TraversalInformationT& ti,
                         CellRange* range) const
            {
                *range = ti.Range();
            }
 
            template <class SplitterT, class BuildInformationT>
            void
            SplitData(const SplitterT& split,
                      const CellType&,
                      const BuildInformationT& parentInfo,
                      CellType* left,
                      CellType* right)
            {
                unsigned int sizes[2];
                SplitData(split, parentInfo.Range(), &sizes[0], &sizes[1]);
                left->m_size = sizes[0];
                right->m_size = sizes[1];
            }
 
            template <class SplitterT, class BuildInformationT>
            void
            SplitData(const SplitterT* splitters,
                      const unsigned int numSplitters,
                      const CellType&,
                      const BuildInformationT& parentInfo,
                      CellType** cells)
            {
                unsigned int* sizes = new unsigned int[1 << numSplitters];
                SplitData(splitters, numSplitters, parentInfo.Range(), sizes);
                unsigned int childCount = 0;
                for (unsigned int i = 0; i < (unsigned)(1 << numSplitters); ++i)
                    if (sizes[i])
                    {
                        cells[i] = new CellType;
                        cells[i]->m_size = sizes[i];
                        ++childCount;
                    }
                    else
                    {
                        cells[i] = NULL;
                    }
                if (!cells[0] && childCount)
                {
                    cells[0] = (CellType*)0x1;
                }
                delete sizes;
            }
 
            template <class SplitterT>
            void
            SplitData(const SplitterT* splitters,
                      const unsigned int numSplitters,
                      const CellRange& range,
                      unsigned int* sizes)
            {
                const unsigned int numChildren = 1 << numSplitters;
                SplitData(splitters[0], range, &(sizes[0]), &(sizes[numChildren >> 1]));
                if (numSplitters == 1)
                {
                    return;
                }
                CellRange leftRange(range.first, range.first + sizes[0]),
                    rightRange(leftRange.second, range.second);
                SplitData(splitters + 1, numSplitters - 1, leftRange, sizes);
                SplitData(splitters + 1, numSplitters - 1, rightRange, sizes + (numChildren >> 1));
            }
 
            template <class SplitterT>
            void
            SplitData(const SplitterT& split,
                      const CellRange& range,
                      unsigned int* left,
                      unsigned int* right)
            {
                if (range.second - range.first == 0)
                {
                    *left = 0;
                    *right = 0;
                    return;
                }
                HandleType j = range.first;
                HandleType k = range.second - 1;
                while (1)
                {
                    while (j <= k && split(at(Dereference(j))))
                    {
                        ++j;
                    }
                    while (j < k && !split(at(Dereference(k))))
                    {
                        --k;
                    }
                    if (j < k)
                    {
                        SwapHandles(k, j);
                        ++j;
                        --k;
                    }
                    else
                    {
                        break;
                    }
                }
                *left = j - range.first;
                *right = (range.second - range.first) - *left;
            }
 
            template <class SplitterT>
            bool
            SplitAndInsert(const SplitterT& split,
                           CellRange parentRange,
                           CellType* left,
                           CellType* right)
            {
                if (split(KernelT::back()))
                {
                    ++(left->m_size);
                    return true;
                }
                else
                {
                    ++(right->m_size);
                    return false;
                }
            }
 
            void
            InsertBack(const CellRange& range, CellType*)
            {
                KernelT::InsertBack(range.second - 1);
            }
 
            bool
            Remove(CellType& cell, DereferencedType s)
            {
                if (cell(at(s)))
                {
                    --cell[0].m_size;
                    return true;
                }
                else
                {
                    --cell[1].m_size;
                    return false;
                }
            }
 
            void
            Remove(DereferencedType s, CellType*)
            {
                KernelT::Remove(s);
            }
        };
    };
}; // namespace GfxTL
 
#endif