SeedingTree.h

Go to the documentation of this file.

#ifndef FastSimulation_Tracking_SeedingTree_h
#define FastSimulation_Tracking_SeedingTree_h

#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_set>

template<class DATA>
class SeedingNode
{
    protected:
        const DATA _data;
        const std::vector<SeedingNode<DATA>*>& _allNodes;
        unsigned int _index; //the index in allNodes
        int _parentIndex; //the parent's index in allNodes
        int _childIndex; //the index of this Node in its parent's children vector
        unsigned int _depth; //the depth within the tree (for root: depth=0 && parentIndex=-1
        std::vector<unsigned int> _children;

    public:
        SeedingNode(const DATA& data, std::vector<SeedingNode*>& allNodes, int parentIndex=-1):
            _data(data),
            _allNodes(allNodes),
            _index(allNodes.size()),
            _parentIndex(parentIndex)
        {
            allNodes.push_back(this);
        
            if (_parentIndex>=0)
            {
                SeedingNode* parent = allNodes[_parentIndex];
                _depth=parent->_depth+1;
                _childIndex=parent->_children.size();
                parent->_children.push_back(_index);
                
            }
            else
            {
                _depth=0;
                _childIndex=-1;
            }
        }
        
        void sort(std::vector<SeedingNode<DATA>*>& allNodes,unsigned int parentIndex)
        {
            _parentIndex=parentIndex;
            _index=allNodes.size();
            if (_parentIndex>=0)
            {
                allNodes[_parentIndex]->_children[_childIndex]=_index;
            }
            allNodes.push_back(this);
            for (unsigned int ichild=0; ichild<_children.size();++ichild)
            {
                _allNodes[_children[ichild]]->sort(allNodes,_index);
            }
        }
        
        bool insert(const std::vector<DATA>& dataList, std::vector<SeedingNode<DATA>*>& allNodes)
        {
            if (_depth+1>=dataList.size())
            {
                //std::cout<<"\tSeedingNode::insert: return"<<std::endl;
                return false;
            }
            for (unsigned int ichild=0; ichild<_children.size();++ichild)
            {
                if (allNodes[_children[ichild]]->getData()==dataList[_depth+1])
                {
                    //std::cout<<"\tSeedingNode::insert: has child "<<dataList[_depth+1].print()<<std::endl;
                    return allNodes[_children[ichild]]->insert(dataList,allNodes);
                }
            }
            //std::cout<<"\tSeedingNode::insert: create child "<<dataList[_depth+1].print()<<std::endl;
            SeedingNode<DATA>* node = new SeedingNode<DATA>(dataList[_depth+1],allNodes,_index);
            if (node->getDepth()+1>=dataList.size())
            {
                return true;
            }
            return node->insert(dataList,allNodes);
        }
        
        inline unsigned int getDepth() const
        {
            return _depth;
        }
        
        inline const SeedingNode<DATA>* next() const
        {
            if (_index+1<_allNodes.size())
            {
                return _allNodes[_index+1];
            }
            return nullptr;
        }
       
        inline const SeedingNode<DATA>* firstChild() const
        {
            if (_children.size()>0)
            {
                return _allNodes[_children[0]];
            }
            return nullptr;
        }
        
        inline unsigned int getIndex() const
        {
            return _index;
        }
        
        inline const SeedingNode* getParent() const
        {
            if (_parentIndex>=0)
            {
                return _allNodes[_parentIndex];
            }
            return nullptr;
        }
        
        inline unsigned int getChildrenSize() const
        {
            return _children.size();
        }
        
        inline const SeedingNode<DATA>* getChild(unsigned int ichild) const
        {
            return _allNodes[_children[ichild]];
        }
        
        inline unsigned int getChildIndex() const
        {
            return _childIndex;
        }
        
        inline const DATA& getData() const
        {
            return _data;
        }
        
        void print() const
        {
            
            printf("index=%3i, depth=%2i, childIndex=%2i:  ",_index,_depth,_childIndex);
            for (unsigned int i=0;i<_depth;++i)
            {
                std::cout<<" -- ";
            }
            printf("[%s, %s] \r\n",_data.toString().c_str(),_data.toIdString().c_str());
            
        }
        void printRecursive() const
        {
            print();
            for (unsigned int ichild=0; ichild<_children.size(); ++ichild)
            {
                _allNodes[_children[ichild]]->printRecursive();
            }
        }
};

template<class DATA>
class SeedingTree
{
    public:
        typedef std::unordered_set<DATA,typename DATA:: hashfct, typename DATA:: eqfct> SingleSet;
    protected:
        std::vector<SeedingNode<DATA>*> _roots;
        std::vector<SeedingNode<DATA>*> _allNodes;
        
        SingleSet _singleSet;
    public:
        SeedingTree()
        {
        }
        
        //returns true if successfully inserted into tree
        bool insert(const std::vector<DATA>& dataList)
        {
            for (unsigned int i = 0; i< dataList.size(); ++i)
            {
                _singleSet.insert(dataList[i]);
            }

            if (dataList.size()==0)
            {
                return false;
            }
            for (unsigned int iroot=0; iroot<_roots.size();++iroot)
            {
                if (_roots[iroot]->getData()==dataList[0])
                {
                    //std::cout<<"\tfound root: "<<dataList[0].print()<<std::endl;
                    return _roots[iroot]->insert(dataList,_allNodes);
                }
            }
            //std::cout<<"\tnew root: "<<dataList[0].print()<<std::endl;
            SeedingNode<DATA>* node = new SeedingNode<DATA>(dataList[0],_allNodes);
            _roots.push_back(node);
            return node->insert(dataList,_allNodes);
        }
        
        inline const SingleSet& getSingleSet() const
        {
            return _singleSet;
        }
        
        void sort()
        {
            //this setups depth first ordered indexes.
            std::vector<SeedingNode<DATA>*> allNodes;
            for (unsigned int iroot=0; iroot<_roots.size();++iroot)
            {
                _roots[iroot]->sort(allNodes,-1);
            }
            _allNodes=allNodes;
        }
        
        
        
        inline unsigned int numberOfRoots() const
        {
            return _roots.size();
        }
        
        inline unsigned int numberOfNodes() const
        {
            return _allNodes.size();
        }
        
        inline const SeedingNode<DATA>* getRoot(unsigned int i) const
        {
            if (i<_roots.size())
            {
                return _roots[i];
            }
            return nullptr;
        }
        
        void printRecursive() const
        {
            std::cout<<"SeedingTree: n="<<_allNodes.size()<<" [recursive]"<<std::endl;
            for (unsigned int iroot=0; iroot<_roots.size();++iroot)
            {
                _roots[iroot]->printRecursive();
            }
        }
        void printOrdered() const
        {
            std::cout<<"SeedingTree: n="<<_allNodes.size()<<" [ordered]"<<std::endl;
            for (unsigned int inode=0; inode<_allNodes.size();++inode)
            {
                _allNodes[inode]->print();
            }
        }
        
        void print() const
        {
            std::cout<<"SeedingTree: n="<<_allNodes.size()<<std::endl;
            for (unsigned int inode=0; inode<_allNodes.size();++inode)
            {
                _allNodes[inode]->print();
            }
        }
        
        ~SeedingTree()
        {
            for (unsigned int iroot=0; iroot<_roots.size();++iroot)
            {
                delete _roots[iroot];
            }
            _roots.clear();
        }
};

#endif