File indexing completed on 2024-04-06 12:11:22
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;
0015 int _parentIndex;
0016 int _childIndex;
0017 unsigned int _depth;
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
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
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