BaseTree.h

Go to the documentation of this file.

#ifndef GfxTL_BASETREE_HEADER__
#define GfxTL_BASETREE_HEADER__
#include <utility>
#include <vector>
 
namespace GfxTL
{
    template <class Cell>
    class BaseTree
    {
    public:
        typedef Cell CellType;
 
        BaseTree();
        BaseTree(const BaseTree<Cell>& bt);
        virtual ~BaseTree();
        virtual void Clear();
        virtual void Init();
 
        CellType*&
        Root()
        {
            return m_root;
        }
 
        const CellType*
        Root() const
        {
            return m_root;
        }
 
        inline bool IsLeaf(const CellType& cell) const;
        inline bool ExistChild(const CellType& cell, unsigned int i) const;
        BaseTree<Cell>& operator=(const BaseTree<Cell>& bt);
        size_t NumberOfLeaves() const;
        size_t NumberOfNodesOnLevel(size_t level) const;
        size_t MaxDepth() const;
        double AvgDepth() const;
        template <class ScalarT>
        void LeafDepthVariance(size_t* numLeaves, ScalarT* variance) const;
 
    protected:
        CellType*
        InnerNodeMarker() const
        {
            return (CellType*)1;
        }
 
    private:
        CellType* m_root;
    };
 
    template <class Cell>
    inline bool
    BaseTree<Cell>::IsLeaf(const CellType& cell) const
    {
        return &(cell[0]) == NULL;
    }
 
    template <class Cell>
    inline bool
    BaseTree<Cell>::ExistChild(const CellType& cell, unsigned int i) const
    {
        return &(cell[i]) > (CellType*)1;
    }
 
    template <class Cell>
    BaseTree<Cell>::BaseTree() : m_root(NULL)
    {
    }
 
    template <class Cell>
    BaseTree<Cell>::BaseTree(const BaseTree<Cell>& bt) : m_root(NULL)
    {
        if (bt.m_root)
        {
            m_root = new Cell(*bt.m_root);
        }
    }
 
    template <class Cell>
    BaseTree<Cell>::~BaseTree()
    {
        Clear();
    }
 
    template <class Cell>
    void
    BaseTree<Cell>::Clear()
    {
        if (m_root)
        {
            delete m_root;
            m_root = NULL;
        }
    }
 
    template <class Cell>
    void
    BaseTree<Cell>::Init()
    {
    }
 
    template <class Cell>
    BaseTree<Cell>&
    BaseTree<Cell>::operator=(const BaseTree<Cell>& bt)
    {
        Clear();
        if (bt.m_root)
        {
            m_root = new Cell(*bt.m_root);
        }
        return *this;
    }
 
    template <class Cell>
    size_t
    BaseTree<Cell>::NumberOfLeaves() const
    {
        if (!Root())
        {
            return 0;
        }
        size_t numLeaves = 0;
        std::vector<const CellType*> stack;
        stack.push_back(Root());
        while (stack.size())
        {
            const CellType* c = stack.back();
            stack.pop_back();
            if (IsLeaf(*c))
            {
                ++numLeaves;
            }
            else
                for (unsigned int i = 0; i < CellType::NChildren; ++i)
                    if (ExistChild(*c, i))
                    {
                        stack.push_back(&((*c)[i]));
                    }
        }
        return numLeaves;
    }
 
    template <class Cell>
    size_t
    BaseTree<Cell>::NumberOfNodesOnLevel(size_t level) const
    {
        if (!Root())
        {
            return 0;
        }
        typedef std::pair<const CellType*, size_t> Pair;
        size_t numNodes = 0;
        std::vector<Pair> stack;
        stack.push_back(Pair(Root(), 0));
        while (stack.size())
        {
            Pair p = stack.back();
            stack.pop_back();
            if (p.second == level)
            {
                ++numNodes;
                continue;
            }
            else if (IsLeaf(*p.first))
            {
                continue;
            }
            else
                for (unsigned int i = 0; i < CellType::NChildren; ++i)
                    if (ExistChild(*p.first, i))
                    {
                        stack.push_back(Pair(&((*p.first)[i]), p.second + 1));
                    }
        }
        return numNodes;
    }
 
    template <class Cell>
    size_t
    BaseTree<Cell>::MaxDepth() const
    {
        size_t maxLevel = 0;
        if (!Root())
        {
            return maxLevel;
        }
        typedef std::pair<const CellType*, size_t> Pair;
        std::vector<Pair> stack;
        stack.push_back(Pair(Root(), 0));
        while (stack.size())
        {
            Pair p = stack.back();
            stack.pop_back();
            if (p.second > maxLevel)
            {
                maxLevel = p.second;
            }
            if (IsLeaf(*p.first))
            {
                continue;
            }
            else
                for (unsigned int i = 0; i < CellType::NChildren; ++i)
                    if (ExistChild(*p.first, i))
                    {
                        stack.push_back(Pair(&((*p.first)[i]), p.second + 1));
                    }
        }
        return maxLevel;
    }
 
    template <class Cell>
    double
    BaseTree<Cell>::AvgDepth() const
    {
        if (!Root())
        {
            return 0.0;
        }
        size_t levelSum = 0;
        size_t leaveCount = 0;
        typedef std::pair<const CellType*, size_t> Pair;
        std::vector<Pair> stack;
        stack.push_back(Pair(Root(), 0));
        while (stack.size())
        {
            Pair p = stack.back();
            stack.pop_back();
            if (IsLeaf(*p.first))
            {
                levelSum += p.second;
                ++leaveCount;
                continue;
            }
            else
                for (unsigned int i = 0; i < CellType::NChildren; ++i)
                    if (ExistChild(*p.first, i))
                    {
                        stack.push_back(Pair(&((*p.first)[i]), p.second + 1));
                    }
        }
        return double(levelSum) / double(leaveCount);
    }
 
    template <class Cell>
    template <class ScalarT>
    void
    BaseTree<Cell>::LeafDepthVariance(size_t* numLeaves, ScalarT* variance) const
    {
        typedef ScalarT ScalarType;
        *numLeaves = 0;
        *variance = 0;
        if (!Root())
        {
            return;
        }
        ScalarType avgDepth = 0;
        std::vector<std::pair<const CellType*, size_t>> stack;
        stack.push_back(std::make_pair(Root(), size_t(0)));
        while (stack.size())
        {
            std::pair<const CellType*, size_t> c = stack.back();
            stack.pop_back();
            if (IsLeaf(*c.first))
            {
                ++(*numLeaves);
                avgDepth += (ScalarType)c.second;
            }
            else
                for (unsigned int i = 0; i < Cell::NChildren; ++i)
                    if (ExistChild(*c.first, i))
                    {
                        stack.push_back(std::make_pair(&((*c.first)[i]), c.second + 1));
                    }
        }
        avgDepth /= ScalarType(*numLeaves);
        *variance = 0;
        stack.push_back(std::make_pair(Root(), size_t(0)));
        while (stack.size())
        {
            std::pair<const CellType*, size_t> c = stack.back();
            stack.pop_back();
            if (IsLeaf(*c.first))
            {
                ScalarType t = ScalarType(c.second) - avgDepth;
                *variance += t * t;
            }
            else
                for (unsigned int i = 0; i < Cell::NChildren; ++i)
                    if (ExistChild(*c.first, i))
                    {
                        stack.push_back(std::make_pair(&((*c.first)[i]), c.second + 1));
                    }
        }
        *variance /= ScalarType(*numLeaves);
    }
}; // namespace GfxTL
 
#endif