CellRangeDataTreeStrategy.h

Go to the documentation of this file.

#ifndef GfxTL__CELLRANGEDATATREESTRATEGY_HEADER__
#define GfxTL__CELLRANGEDATATREESTRATEGY_HEADER__
#include <vector>
 
namespace GfxTL
{
    template <class InheritedStrategyT, class KernelT>
    struct CellRangeDataTreeStrategy
    {
        typedef typename KernelT::value_type value_type;
 
        class CellData : public InheritedStrategyT::CellData
        {
        public:
            typedef typename KernelT::value_type value_type;
            typedef typename KernelT::HandleType HandleType;
            typedef std::pair<HandleType, HandleType> CellRange;
 
            size_t
            Size() const
            {
                return m_range.second - m_range.first;
            }
 
            const CellRange&
            Range() const
            {
                return m_range;
            }
 
            CellRange&
            Range()
            {
                return m_range;
            }
 
            CellRange m_range;
        };
 
        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
            {
            };
 
            template <class BaseTraversalT>
            class CellRangeTraversalInformation : public BaseTraversalT
            {
            };
 
            template <class BuildInformationT>
            void
            InitRootBuildInformation(BuildInformationT* bi) const
            {
                bi->Range() = CellRange(KernelT::BeginHandle(), KernelT::EndHandle());
            }
 
            template <class BuildInformationT>
            void
            InitBuildInformation(const CellType& parent,
                                 const BuildInformationT& parentInfo,
                                 unsigned int childIdx,
                                 BuildInformationT* bi) const
            {
                bi->Range() = parent[childIdx].Range();
            }
 
            template <class BuildInformationT>
            void
            InitRoot(const BuildInformationT& bi, CellType* cell)
            {
                cell->m_range.first = KernelT::BeginHandle();
                cell->m_range.second = KernelT::EndHandle();
            }
 
            template <class BuildInformationT>
            void
            InitCell(const CellType& parent,
                     const BuildInformationT& parentInfo,
                     unsigned int childIdx,
                     const BuildInformationT& bi,
                     CellType* cell)
            {
                cell->Range() = bi.Range();
            }
 
            template <class TraversalInformationT>
            void
            InitRootTraversalInformation(const CellType& root, TraversalInformationT* ti) const
            {
            }
 
            template <class TraversalInformationT>
            void
            GetCellRange(const CellType& cell,
                         const TraversalInformationT& ti,
                         CellRange* range) const
            {
                *range = cell.Range();
            }
 
            template <class TraversalInformationT>
            void
            InitTraversalInformation(const CellType& parent,
                                     const TraversalInformationT& pTi,
                                     unsigned int childIdx,
                                     TraversalInformationT* ti) const
            {
            }
 
            template <class SplitterT, class BuildInformationT>
            void
            SplitData(const SplitterT& split,
                      const CellType& parent,
                      const BuildInformationT&,
                      CellType* left,
                      CellType* right)
            {
                size_t sizes[2];
                SplitData(split, parent.Range(), &sizes[0], &sizes[1]);
                left->m_range.first = parent.m_range.first;
                left->m_range.second = parent.m_range.first + sizes[0];
                right->m_range.first = left->m_range.second;
                right->m_range.second = right->m_range.first + sizes[1];
            }
 
            template <class SplitterT, class BuildInformationT>
            void
            SplitData(const SplitterT& split,
                      const CellType& parent,
                      const BuildInformationT&,
                      CellType* left,
                      BuildInformationT* leftBi,
                      CellType* right,
                      BuildInformationT* rightBi)
            {
                size_t sizes[2];
                SplitData(split, parent.Range(), &sizes[0], &sizes[1]);
                left->m_range.first = parent.m_range.first;
                left->m_range.second = parent.m_range.first + sizes[0];
                right->m_range.first = left->m_range.second;
                right->m_range.second = right->m_range.first + sizes[1];
            }
 
            template <class SplitterT, class BuildInformationT>
            void
            SplitData(const SplitterT* splitters,
                      const unsigned int numSplitters,
                      const CellType& parent,
                      const BuildInformationT& parentInfo,
                      CellType** cells)
            {
                size_t* sizes = new size_t[size_t(1u) << numSplitters];
                SplitData(splitters, numSplitters, parentInfo.Range(), sizes);
                unsigned int childCount = 0;
                HandleType begin = parent.m_range.first;
                for (unsigned int i = 0; i < (1u << numSplitters); ++i)
                    if (sizes[i])
                    {
                        cells[i] = new CellType;
                        cells[i]->m_range.first = begin;
                        cells[i]->m_range.second = begin + sizes[i];
                        begin = cells[i]->m_range.second;
                        ++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,
                      size_t* 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, size_t* left, size_t* 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(this->at(this->Dereference(j))))
                    {
                        ++j;
                    }
                    while (j < k && !split(this->at(this->Dereference(k))))
                    {
                        --k;
                    }
                    if (j < k)
                    {
                        this->SwapHandles(k, j);
                        ++j;
                        --k;
                    }
                    else
                    {
                        break;
                    }
                }
                *left = j - range.first;
                *right = (range.second - range.first) - *left;
            }
 
            void
            PartitionDataRange(const CellRange& range,
                               const std::vector<size_t>& clusterid,
                               const std::vector<size_t>& clusterCount,
                               CellType** bis)
            {
                std::vector<size_t> clusterPositions(clusterCount.size());
                clusterPositions[0] = 0;
                bis[0]->Range() = CellRange(range.first, range.first + clusterCount[0]);
                for (size_t i = 1; i < clusterCount.size(); ++i)
                {
                    clusterPositions[i] = clusterPositions[i - 1] + clusterCount[i - 1];
                    bis[i]->Range() =
                        CellRange(range.first + clusterPositions[i],
                                  range.first + clusterPositions[i] + clusterCount[i]);
                }
                std::vector<size_t> partitioning(clusterid.size());
                for (size_t i = 0; i < clusterid.size(); ++i)
                {
                    partitioning[i] = clusterPositions[clusterid[i]]++;
                }
                for (size_t i = 0; i < partitioning.size(); ++i)
                    while (i != partitioning[i])
                    {
                        KernelT::SwapHandles(range.first + i, range.first + partitioning[i]);
                        std::swap(partitioning[i], partitioning[partitioning[i]]);
                    }
            }
        };
    };
}; // namespace GfxTL
 
#endif