Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2021-02-14 13:26:50

0001 #ifndef FastSimulation_Tracking_SeedingTree_h
0002 #define FastSimulation_Tracking_SeedingTree_h
0003 
0004 #include <vector>
0005 #include <iostream>
0006 #include <algorithm>
0007 #include <unordered_set>
0008 
0009 template <class DATA>
0010 class SeedingNode {
0011 protected:
0012   const DATA _data;
0013   const std::vector<SeedingNode<DATA>*>& _allNodes;
0014   unsigned int _index;  //the index in allNodes
0015   int _parentIndex;     //the parent's index in allNodes
0016   int _childIndex;      //the index of this Node in its parent's children vector
0017   unsigned int _depth;  //the depth within the tree (for root: depth=0 && parentIndex=-1
0018   std::vector<unsigned int> _children;
0019 
0020 public:
0021   SeedingNode(const DATA& data, std::vector<SeedingNode*>& allNodes, int parentIndex = -1)
0022       : _data(data), _allNodes(allNodes), _index(allNodes.size()), _parentIndex(parentIndex) {
0023     allNodes.push_back(this);
0024 
0025     if (_parentIndex >= 0) {
0026       SeedingNode* parent = allNodes[_parentIndex];
0027       _depth = parent->_depth + 1;
0028       _childIndex = parent->_children.size();
0029       parent->_children.push_back(_index);
0030 
0031     } else {
0032       _depth = 0;
0033       _childIndex = -1;
0034     }
0035   }
0036 
0037   void sort(std::vector<SeedingNode<DATA>*>& allNodes, unsigned int parentIndex) {
0038     _parentIndex = parentIndex;
0039     _index = allNodes.size();
0040     if (_parentIndex >= 0) {
0041       allNodes[_parentIndex]->_children[_childIndex] = _index;
0042     }
0043     allNodes.push_back(this);
0044     for (unsigned int ichild = 0; ichild < _children.size(); ++ichild) {
0045       _allNodes[_children[ichild]]->sort(allNodes, _index);
0046     }
0047   }
0048 
0049   bool insert(const std::vector<DATA>& dataList, std::vector<SeedingNode<DATA>*>& allNodes) {
0050     if (_depth + 1 >= dataList.size()) {
0051       return false;
0052     }
0053     for (unsigned int ichild = 0; ichild < _children.size(); ++ichild) {
0054       if (allNodes[_children[ichild]]->getData() == dataList[_depth + 1]) {
0055         return allNodes[_children[ichild]]->insert(dataList, allNodes);
0056       }
0057     }
0058     SeedingNode<DATA>* node = new SeedingNode<DATA>(dataList[_depth + 1], allNodes, _index);
0059     if (node->getDepth() + 1 >= dataList.size()) {
0060       return true;
0061     }
0062     return node->insert(dataList, allNodes);
0063   }
0064 
0065   inline unsigned int getDepth() const { return _depth; }
0066 
0067   inline const SeedingNode<DATA>* next() const {
0068     if (_index + 1 < _allNodes.size()) {
0069       return _allNodes[_index + 1];
0070     }
0071     return nullptr;
0072   }
0073 
0074   inline const SeedingNode<DATA>* firstChild() const {
0075     if (!_children.empty()) {
0076       return _allNodes[_children[0]];
0077     }
0078     return nullptr;
0079   }
0080 
0081   inline unsigned int getIndex() const { return _index; }
0082 
0083   inline const SeedingNode* getParent() const {
0084     if (_parentIndex >= 0) {
0085       return _allNodes[_parentIndex];
0086     }
0087     return nullptr;
0088   }
0089 
0090   inline unsigned int getChildrenSize() const { return _children.size(); }
0091 
0092   inline const SeedingNode<DATA>* getChild(unsigned int ichild) const { return _allNodes[_children[ichild]]; }
0093 
0094   inline unsigned int getChildIndex() const { return _childIndex; }
0095 
0096   inline const DATA& getData() const { return _data; }
0097 
0098   void print() const {
0099     printf("index=%3i, depth=%2i, childIndex=%2i:  ", _index, _depth, _childIndex);
0100     for (unsigned int i = 0; i < _depth; ++i) {
0101       std::cout << " -- ";
0102     }
0103     printf("[%s, %s] \r\n", _data.toString().c_str(), _data.toIdString().c_str());
0104   }
0105   void printRecursive() const {
0106     print();
0107     for (unsigned int ichild = 0; ichild < _children.size(); ++ichild) {
0108       _allNodes[_children[ichild]]->printRecursive();
0109     }
0110   }
0111 };
0112 
0113 template <class DATA>
0114 class SeedingTree {
0115 public:
0116   typedef std::unordered_set<DATA, typename DATA::hashfct, typename DATA::eqfct> SingleSet;
0117 
0118 protected:
0119   std::vector<SeedingNode<DATA>*> _roots;
0120   std::vector<SeedingNode<DATA>*> _allNodes;
0121 
0122   SingleSet _singleSet;
0123 
0124 public:
0125   //returns true if successfully inserted into tree
0126   bool insert(const std::vector<DATA>& dataList) {
0127     for (unsigned int i = 0; i < dataList.size(); ++i) {
0128       _singleSet.insert(dataList[i]);
0129     }
0130 
0131     if (dataList.empty()) {
0132       return false;
0133     }
0134     for (unsigned int iroot = 0; iroot < _roots.size(); ++iroot) {
0135       if (_roots[iroot]->getData() == dataList[0]) {
0136         return _roots[iroot]->insert(dataList, _allNodes);
0137       }
0138     }
0139     SeedingNode<DATA>* node = new SeedingNode<DATA>(dataList[0], _allNodes);
0140     _roots.push_back(node);
0141     return node->insert(dataList, _allNodes);
0142   }
0143 
0144   inline const SingleSet& getSingleSet() const { return _singleSet; }
0145 
0146   void sort() {
0147     //this setups depth first ordered indexes.
0148     std::vector<SeedingNode<DATA>*> allNodes;
0149     for (unsigned int iroot = 0; iroot < _roots.size(); ++iroot) {
0150       _roots[iroot]->sort(allNodes, -1);
0151     }
0152     _allNodes = allNodes;
0153   }
0154 
0155   inline unsigned int numberOfRoots() const { return _roots.size(); }
0156 
0157   inline unsigned int numberOfNodes() const { return _allNodes.size(); }
0158 
0159   inline const SeedingNode<DATA>* getRoot(unsigned int i) const {
0160     if (i < _roots.size()) {
0161       return _roots[i];
0162     }
0163     return nullptr;
0164   }
0165 
0166   void printRecursive() const {
0167     std::cout << "SeedingTree: n=" << _allNodes.size() << " [recursive]" << std::endl;
0168     for (unsigned int iroot = 0; iroot < _roots.size(); ++iroot) {
0169       _roots[iroot]->printRecursive();
0170     }
0171   }
0172   void printOrdered() const {
0173     std::cout << "SeedingTree: n=" << _allNodes.size() << " [ordered]" << std::endl;
0174     for (unsigned int inode = 0; inode < _allNodes.size(); ++inode) {
0175       _allNodes[inode]->print();
0176     }
0177   }
0178 
0179   void print() const {
0180     std::cout << "SeedingTree: n=" << _allNodes.size() << std::endl;
0181     for (unsigned int inode = 0; inode < _allNodes.size(); ++inode) {
0182       _allNodes[inode]->print();
0183     }
0184   }
0185 
0186   ~SeedingTree() {
0187     for (unsigned int iroot = 0; iroot < _roots.size(); ++iroot) {
0188       delete _roots[iroot];
0189     }
0190     _roots.clear();
0191   }
0192 };
0193 
0194 #endif