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);
            }
        };
    };
};
 
#endif