TrackerTraits.cxx

Go to the documentation of this file.

// Copyright 2019-2020 CERN and copyright holders of ALICE O2.
// See https://alice-o2.web.cern.ch/copyright for details of the copyright holders.
// All rights not expressly granted are reserved.
//
// This software is distributed under the terms of the GNU General Public
// License v3 (GPL Version 3), copied verbatim in the file "COPYING".
//
// In applying this license CERN does not waive the privileges and immunities
// granted to it by virtue of its status as an Intergovernmental Organization
// or submit itself to any jurisdiction.
 
#include <algorithm>
#include <iostream>
#include <iterator>
#include <ranges>
 
#ifdef OPTIMISATION_OUTPUT
#include <format>
#endif
 
#include <oneapi/tbb/combinable.h>
#include <oneapi/tbb/parallel_sort.h>
 
#include "CommonConstants/MathConstants.h"
#include "DetectorsBase/Propagator.h"
#include "GPUCommonMath.h"
#include "ITStracking/Cell.h"
#include "ITStracking/Constants.h"
#include "ITStracking/TrackerTraits.h"
#include "ITStracking/BoundedAllocator.h"
#include "ITStracking/IndexTableUtils.h"
#include "ITStracking/Tracklet.h"
#include "ReconstructionDataFormats/Track.h"
 
using o2::base::PropagatorF;
 
namespace
{
inline float Sq(float q)
{
  return q * q;
}
} // namespace
 
namespace o2::its
{
 
constexpr int debugLevel{0};
 
template <int nLayers>
void TrackerTraits<nLayers>::computeLayerTracklets(const int iteration, int iROFslice, int iVertex)
{
#ifdef OPTIMISATION_OUTPUT
  static int iter{0};
  std::ofstream off(std::format("tracklets{}.txt", iter++));
#endif
 
  for (int iLayer = 0; iLayer < mTrkParams[iteration].TrackletsPerRoad(); ++iLayer) {
    mTimeFrame->getTracklets()[iLayer].clear();
    mTimeFrame->getTrackletsLabel(iLayer).clear();
    if (iLayer > 0) {
      std::fill(mTimeFrame->getTrackletsLookupTable()[iLayer - 1].begin(),
                mTimeFrame->getTrackletsLookupTable()[iLayer - 1].end(), 0);
    }
  }
 
  const Vertex diamondVert({mTrkParams[iteration].Diamond[0], mTrkParams[iteration].Diamond[1], mTrkParams[iteration].Diamond[2]}, {25.e-6f, 0.f, 0.f, 25.e-6f, 0.f, 36.f}, 1, 1.f);
  gsl::span<const Vertex> diamondSpan(&diamondVert, 1);
  int startROF{mTrkParams[iteration].nROFsPerIterations > 0 ? iROFslice * mTrkParams[iteration].nROFsPerIterations : 0};
  int endROF{o2::gpu::GPUCommonMath::Min(mTrkParams[iteration].nROFsPerIterations > 0 ? (iROFslice + 1) * mTrkParams[iteration].nROFsPerIterations + mTrkParams[iteration].DeltaROF : mTimeFrame->getNrof(), mTimeFrame->getNrof())};
  for (int rof0{startROF}; rof0 < endROF; ++rof0) {
    gsl::span<const Vertex> primaryVertices = mTrkParams[iteration].UseDiamond ? diamondSpan : mTimeFrame->getPrimaryVertices(rof0);
    const int startVtx{iVertex >= 0 ? iVertex : 0};
    const int endVtx{iVertex >= 0 ? o2::gpu::CAMath::Min(iVertex + 1, static_cast<int>(primaryVertices.size())) : static_cast<int>(primaryVertices.size())};
    int minRof = o2::gpu::CAMath::Max(startROF, rof0 - mTrkParams[iteration].DeltaROF);
    int maxRof = o2::gpu::CAMath::Min(endROF - 1, rof0 + mTrkParams[iteration].DeltaROF);
 
    mTaskArena.execute([&] {
      tbb::parallel_for(
        tbb::blocked_range<int>(0, mTrkParams[iteration].TrackletsPerRoad()),
        [&](const tbb::blocked_range<int>& Layers) {
          for (int iLayer = Layers.begin(); iLayer < Layers.end(); ++iLayer) {
            gsl::span<const Cluster> layer0 = mTimeFrame->getClustersOnLayer(rof0, iLayer);
            if (layer0.empty()) {
              continue;
            }
            float meanDeltaR{mTrkParams[iteration].LayerRadii[iLayer + 1] - mTrkParams[iteration].LayerRadii[iLayer]};
 
            const int currentLayerClustersNum{static_cast<int>(layer0.size())};
            for (int iCluster{0}; iCluster < currentLayerClustersNum; ++iCluster) {
              const Cluster& currentCluster{layer0[iCluster]};
              const int currentSortedIndex{mTimeFrame->getSortedIndex(rof0, iLayer, iCluster)};
 
              if (mTimeFrame->isClusterUsed(iLayer, currentCluster.clusterId)) {
                continue;
              }
              const float inverseR0{1.f / currentCluster.radius};
 
              for (int iV{startVtx}; iV < endVtx; ++iV) {
                auto& primaryVertex{primaryVertices[iV]};
                if (primaryVertex.isFlagSet(2) && iteration != 3) {
                  continue;
                }
                const float resolution = o2::gpu::CAMath::Sqrt(Sq(mTrkParams[iteration].PVres) / primaryVertex.getNContributors() + Sq(mTimeFrame->getPositionResolution(iLayer)));
 
                const float tanLambda{(currentCluster.zCoordinate - primaryVertex.getZ()) * inverseR0};
 
                const float zAtRmin{tanLambda * (mTimeFrame->getMinR(iLayer + 1) - currentCluster.radius) + currentCluster.zCoordinate};
                const float zAtRmax{tanLambda * (mTimeFrame->getMaxR(iLayer + 1) - currentCluster.radius) + currentCluster.zCoordinate};
 
                const float sqInverseDeltaZ0{1.f / (Sq(currentCluster.zCoordinate - primaryVertex.getZ()) + 2.e-8f)}; 
                const float sigmaZ{o2::gpu::CAMath::Sqrt(Sq(resolution) * Sq(tanLambda) * ((Sq(inverseR0) + sqInverseDeltaZ0) * Sq(meanDeltaR) + 1.f) + Sq(meanDeltaR * mTimeFrame->getMSangle(iLayer)))};
 
                const int4 selectedBinsRect{getBinsRect(currentCluster, iLayer + 1, zAtRmin, zAtRmax, sigmaZ * mTrkParams[iteration].NSigmaCut, mTimeFrame->getPhiCut(iLayer))};
                if (selectedBinsRect.x == 0 && selectedBinsRect.y == 0 && selectedBinsRect.z == 0 && selectedBinsRect.w == 0) {
                  continue;
                }
 
                int phiBinsNum{selectedBinsRect.w - selectedBinsRect.y + 1};
 
                if (phiBinsNum < 0) {
                  phiBinsNum += mTrkParams[iteration].PhiBins;
                }
 
                for (int rof1{minRof}; rof1 <= maxRof; ++rof1) {
                  auto layer1 = mTimeFrame->getClustersOnLayer(rof1, iLayer + 1);
                  if (layer1.empty()) {
                    continue;
                  }
                  for (int iPhiCount{0}; iPhiCount < phiBinsNum; iPhiCount++) {
                    int iPhiBin = (selectedBinsRect.y + iPhiCount) % mTrkParams[iteration].PhiBins;
                    const int firstBinIndex{mTimeFrame->mIndexTableUtils.getBinIndex(selectedBinsRect.x, iPhiBin)};
                    const int maxBinIndex{firstBinIndex + selectedBinsRect.z - selectedBinsRect.x + 1};
                    if constexpr (debugLevel) {
                      if (firstBinIndex < 0 || firstBinIndex > mTimeFrame->getIndexTable(rof1, iLayer + 1).size() ||
                          maxBinIndex < 0 || maxBinIndex > mTimeFrame->getIndexTable(rof1, iLayer + 1).size()) {
                        std::cout << iLayer << "\t" << iCluster << "\t" << zAtRmin << "\t" << zAtRmax << "\t" << sigmaZ * mTrkParams[iteration].NSigmaCut << "\t" << mTimeFrame->getPhiCut(iLayer) << std::endl;
                        std::cout << currentCluster.zCoordinate << "\t" << primaryVertex.getZ() << "\t" << currentCluster.radius << std::endl;
                        std::cout << mTimeFrame->getMinR(iLayer + 1) << "\t" << currentCluster.radius << "\t" << currentCluster.zCoordinate << std::endl;
                        std::cout << "Illegal access to IndexTable " << firstBinIndex << "\t" << maxBinIndex << "\t" << selectedBinsRect.z << "\t" << selectedBinsRect.x << std::endl;
                        exit(1);
                      }
                    }
                    const int firstRowClusterIndex = mTimeFrame->getIndexTable(rof1, iLayer + 1)[firstBinIndex];
                    const int maxRowClusterIndex = mTimeFrame->getIndexTable(rof1, iLayer + 1)[maxBinIndex];
                    for (int iNextCluster{firstRowClusterIndex}; iNextCluster < maxRowClusterIndex; ++iNextCluster) {
                      if (iNextCluster >= (int)layer1.size()) {
                        break;
                      }
 
                      const Cluster& nextCluster{layer1[iNextCluster]};
                      if (mTimeFrame->isClusterUsed(iLayer + 1, nextCluster.clusterId)) {
                        continue;
                      }
 
                      const float deltaPhi{o2::gpu::GPUCommonMath::Abs(currentCluster.phi - nextCluster.phi)};
                      const float deltaZ{o2::gpu::GPUCommonMath::Abs(tanLambda * (nextCluster.radius - currentCluster.radius) +
                                                                     currentCluster.zCoordinate - nextCluster.zCoordinate)};
 
#ifdef OPTIMISATION_OUTPUT
                      MCCompLabel label;
                      int currentId{currentCluster.clusterId};
                      int nextId{nextCluster.clusterId};
                      for (auto& lab1 : mTimeFrame->getClusterLabels(iLayer, currentId)) {
                        for (auto& lab2 : mTimeFrame->getClusterLabels(iLayer + 1, nextId)) {
                          if (lab1 == lab2 && lab1.isValid()) {
                            label = lab1;
                            break;
                          }
                        }
                        if (label.isValid()) {
                          break;
                        }
                      }
                      off << std::format("{}\t{:d}\t{}\t{}\t{}\t{}", iLayer, label.isValid(), (tanLambda * (nextCluster.radius - currentCluster.radius) + currentCluster.zCoordinate - nextCluster.zCoordinate) / sigmaZ, tanLambda, resolution, sigmaZ) << std::endl;
#endif
 
                      if (deltaZ / sigmaZ < mTrkParams[iteration].NSigmaCut &&
                          (deltaPhi < mTimeFrame->getPhiCut(iLayer) ||
                           o2::gpu::GPUCommonMath::Abs(deltaPhi - constants::math::TwoPi) < mTimeFrame->getPhiCut(iLayer))) {
                        if (iLayer > 0) {
                          mTimeFrame->getTrackletsLookupTable()[iLayer - 1][currentSortedIndex]++;
                        }
                        const float phi{o2::gpu::GPUCommonMath::ATan2(currentCluster.yCoordinate - nextCluster.yCoordinate,
                                                                      currentCluster.xCoordinate - nextCluster.xCoordinate)};
                        const float tanL{(currentCluster.zCoordinate - nextCluster.zCoordinate) /
                                         (currentCluster.radius - nextCluster.radius)};
                        mTimeFrame->getTracklets()[iLayer].emplace_back(currentSortedIndex, mTimeFrame->getSortedIndex(rof1, iLayer + 1, iNextCluster), tanL, phi, rof0, rof1);
                      }
                    }
                  }
                }
              }
            }
          }
        });
    });
  }
 
  auto sortTracklets = [](const Tracklet& a, const Tracklet& b) -> bool {
    return a.firstClusterIndex < b.firstClusterIndex || (a.firstClusterIndex == b.firstClusterIndex && a.secondClusterIndex < b.secondClusterIndex);
  };
  auto equalTracklets = [](const Tracklet& a, const Tracklet& b) -> bool {
    return a.firstClusterIndex == b.firstClusterIndex && a.secondClusterIndex == b.secondClusterIndex;
  };
 
  mTaskArena.execute([&] {
    tbb::parallel_for(
      tbb::blocked_range<int>(0, mTrkParams[iteration].CellsPerRoad()),
      [&](const tbb::blocked_range<int>& Layers) {
        for (int iLayer = Layers.begin(); iLayer < Layers.end(); ++iLayer) {
          auto& trkl{mTimeFrame->getTracklets()[iLayer + 1]};
          tbb::parallel_sort(trkl.begin(), trkl.end(), sortTracklets);
          trkl.erase(std::unique(trkl.begin(), trkl.end(), equalTracklets), trkl.end());
          trkl.shrink_to_fit();
          auto& lut{mTimeFrame->getTrackletsLookupTable()[iLayer]};
          std::fill(lut.begin(), lut.end(), 0);
          if (trkl.empty()) {
            return;
          }
          for (const auto& tkl : trkl) {
            lut[tkl.firstClusterIndex]++;
          }
          std::exclusive_scan(lut.begin(), lut.end(), lut.begin(), 0);
          lut.push_back(trkl.size());
        }
      });
  });
 
  // in-place deduplication
  auto& trklt0 = mTimeFrame->getTracklets()[0];
  mTaskArena.execute([&] { tbb::parallel_sort(trklt0.begin(), trklt0.end(), sortTracklets); });
  trklt0.erase(std::unique(trklt0.begin(), trklt0.end(), equalTracklets), trklt0.end());
  trklt0.shrink_to_fit();
 
  if (mTimeFrame->hasMCinformation()) {
    for (int iLayer{0}; iLayer < mTrkParams[iteration].TrackletsPerRoad(); ++iLayer) {
      for (auto& trk : mTimeFrame->getTracklets()[iLayer]) {
        MCCompLabel label;
        int currentId{mTimeFrame->getClusters()[iLayer][trk.firstClusterIndex].clusterId};
        int nextId{mTimeFrame->getClusters()[iLayer + 1][trk.secondClusterIndex].clusterId};
        for (auto& lab1 : mTimeFrame->getClusterLabels(iLayer, currentId)) {
          for (auto& lab2 : mTimeFrame->getClusterLabels(iLayer + 1, nextId)) {
            if (lab1 == lab2 && lab1.isValid()) {
              label = lab1;
              break;
            }
          }
          if (label.isValid()) {
            break;
          }
        }
        mTimeFrame->getTrackletsLabel(iLayer).emplace_back(label);
      }
    }
  }
}
 
template <int nLayers>
void TrackerTraits<nLayers>::computeLayerCells(const int iteration)
{
#ifdef OPTIMISATION_OUTPUT
  static int iter{0};
  std::ofstream off(std::format("cells{}.txt", iter++));
#endif
 
  constexpr float radl = 9.36f; // Radiation length of Si [cm]
  constexpr float rho = 2.33f;  // Density of Si [g/cm^3]
 
  for (int iLayer = 0; iLayer < mTrkParams[iteration].CellsPerRoad(); ++iLayer) {
    deepVectorClear(mTimeFrame->getCells()[iLayer]);
    if (iLayer > 0) {
      deepVectorClear(mTimeFrame->getCellsLookupTable()[iLayer - 1]);
    }
    if (mTimeFrame->hasMCinformation()) {
      deepVectorClear(mTimeFrame->getCellsLabel(iLayer));
    }
  }
 
  mTaskArena.execute([&] {
    tbb::parallel_for(
      tbb::blocked_range<int>(0, mTrkParams[iteration].CellsPerRoad()),
      [&](const tbb::blocked_range<int>& Layers) {
        for (int iLayer = Layers.begin(); iLayer < Layers.end(); ++iLayer) {
 
          if (mTimeFrame->getTracklets()[iLayer + 1].empty() ||
              mTimeFrame->getTracklets()[iLayer].empty()) {
            continue;
          }
 
#ifdef OPTIMISATION_OUTPUT
          float resolution{o2::gpu::CAMath::Sqrt(0.5f * (mTrkParams[iteration].SystErrorZ2[iLayer] + mTrkParams[iteration].SystErrorZ2[iLayer + 1] + mTrkParams[iteration].SystErrorZ2[iLayer + 2] + mTrkParams[iteration].SystErrorY2[iLayer] + mTrkParams[iteration].SystErrorY2[iLayer + 1] + mTrkParams[iteration].SystErrorY2[iLayer + 2])) / mTrkParams[iteration].LayerResolution[iLayer]};
          resolution = resolution > 1.e-12 ? resolution : 1.f;
#endif
 
          // count number of cells found
          const int currentLayerTrackletsNum{static_cast<int>(mTimeFrame->getTracklets()[iLayer].size())};
          bounded_vector<int> perTrackletCount(currentLayerTrackletsNum + 1, 0, mMemoryPool.get());
          tbb::parallel_for(
            tbb::blocked_range<int>(0, currentLayerTrackletsNum),
            [&](const tbb::blocked_range<int>& Tracklets) {
              for (int iTracklet = Tracklets.begin(); iTracklet < Tracklets.end(); ++iTracklet) {
                const Tracklet& currentTracklet{mTimeFrame->getTracklets()[iLayer][iTracklet]};
                const int nextLayerClusterIndex{currentTracklet.secondClusterIndex};
                const int nextLayerFirstTrackletIndex{
                  mTimeFrame->getTrackletsLookupTable()[iLayer][nextLayerClusterIndex]};
                const int nextLayerLastTrackletIndex{
                  mTimeFrame->getTrackletsLookupTable()[iLayer][nextLayerClusterIndex + 1]};
 
                if (nextLayerFirstTrackletIndex == nextLayerLastTrackletIndex) {
                  continue;
                }
 
                int foundCells{0};
                for (int iNextTracklet{nextLayerFirstTrackletIndex}; iNextTracklet < nextLayerLastTrackletIndex; ++iNextTracklet) {
                  if (mTimeFrame->getTracklets()[iLayer + 1][iNextTracklet].firstClusterIndex != nextLayerClusterIndex) {
                    break;
                  }
                  const Tracklet& nextTracklet{mTimeFrame->getTracklets()[iLayer + 1][iNextTracklet]};
                  const float deltaTanLambda{std::abs(currentTracklet.tanLambda - nextTracklet.tanLambda)};
 
#ifdef OPTIMISATION_OUTPUT
                  bool good{mTimeFrame->getTrackletsLabel(iLayer)[iTracklet] == mTimeFrame->getTrackletsLabel(iLayer + 1)[iNextTracklet]};
                  float signedDelta{currentTracklet.tanLambda - nextTracklet.tanLambda};
                  off << std::format("{}\t{:d}\t{}\t{}\t{}\t{}", iLayer, good, signedDelta, signedDelta / (mTrkParams[iteration].CellDeltaTanLambdaSigma), tanLambda, resolution) << std::endl;
#endif
 
                  if (deltaTanLambda / mTrkParams[iteration].CellDeltaTanLambdaSigma < mTrkParams[iteration].NSigmaCut) {
 
                    const int clusId[3]{
                      mTimeFrame->getClusters()[iLayer][currentTracklet.firstClusterIndex].clusterId,
                      mTimeFrame->getClusters()[iLayer + 1][nextTracklet.firstClusterIndex].clusterId,
                      mTimeFrame->getClusters()[iLayer + 2][nextTracklet.secondClusterIndex].clusterId};
                    const auto& cluster1_glo = mTimeFrame->getUnsortedClusters()[iLayer][clusId[0]];
                    const auto& cluster2_glo = mTimeFrame->getUnsortedClusters()[iLayer + 1][clusId[1]];
                    const auto& cluster3_tf = mTimeFrame->getTrackingFrameInfoOnLayer(iLayer + 2)[clusId[2]];
                    auto track{buildTrackSeed(cluster1_glo, cluster2_glo, cluster3_tf)};
 
                    float chi2{0.f};
                    bool good{false};
                    for (int iC{2}; iC--;) {
                      const TrackingFrameInfo& trackingHit = mTimeFrame->getTrackingFrameInfoOnLayer(iLayer + iC)[clusId[iC]];
 
                      if (!track.rotate(trackingHit.alphaTrackingFrame)) {
                        break;
                      }
 
                      if (!track.propagateTo(trackingHit.xTrackingFrame, getBz())) {
                        break;
                      }
 
                      if (!track.correctForMaterial(mTrkParams[0].LayerxX0[iLayer + iC], mTrkParams[0].LayerxX0[iLayer] * radl * rho, true)) {
                        break;
                      }
 
                      const auto predChi2{track.getPredictedChi2Quiet(trackingHit.positionTrackingFrame, trackingHit.covarianceTrackingFrame)};
                      if (!iC && predChi2 > mTrkParams[iteration].MaxChi2ClusterAttachment) {
                        break;
                      }
 
                      if (!track.o2::track::TrackParCov::update(trackingHit.positionTrackingFrame, trackingHit.covarianceTrackingFrame)) {
                        break;
                      }
 
                      good = !iC;
                      chi2 += predChi2;
                    }
                    if (good) {
                      ++foundCells;
                    }
                  }
                }
                perTrackletCount[iTracklet] = foundCells;
              }
            });
 
          // calculate offset table and check if any cells where found
          std::exclusive_scan(perTrackletCount.begin(), perTrackletCount.end(), perTrackletCount.begin(), 0);
          auto totalCells{perTrackletCount.back()};
          if (totalCells == 0) {
            continue;
          }
          auto& layerCells = mTimeFrame->getCells()[iLayer];
          layerCells.resize(totalCells);
 
          tbb::parallel_for(
            tbb::blocked_range<int>(0, currentLayerTrackletsNum),
            [&](const tbb::blocked_range<int>& Tracklets) {
              for (int iTracklet = Tracklets.begin(); iTracklet < Tracklets.end(); ++iTracklet) {
                if (perTrackletCount[iTracklet] == perTrackletCount[iTracklet + 1]) {
                  continue;
                }
 
                const Tracklet& currentTracklet{mTimeFrame->getTracklets()[iLayer][iTracklet]};
                const int nextLayerClusterIndex{currentTracklet.secondClusterIndex};
                const int nextLayerFirstTrackletIndex{
                  mTimeFrame->getTrackletsLookupTable()[iLayer][nextLayerClusterIndex]};
                const int nextLayerLastTrackletIndex{
                  mTimeFrame->getTrackletsLookupTable()[iLayer][nextLayerClusterIndex + 1]};
 
                int position = perTrackletCount[iTracklet];
                for (int iNextTracklet{nextLayerFirstTrackletIndex}; iNextTracklet < nextLayerLastTrackletIndex; ++iNextTracklet) {
                  if (mTimeFrame->getTracklets()[iLayer + 1][iNextTracklet].firstClusterIndex != nextLayerClusterIndex) {
                    break;
                  }
                  const Tracklet& nextTracklet{mTimeFrame->getTracklets()[iLayer + 1][iNextTracklet]};
                  const float deltaTanLambda{std::abs(currentTracklet.tanLambda - nextTracklet.tanLambda)};
 
                  if (deltaTanLambda / mTrkParams[iteration].CellDeltaTanLambdaSigma < mTrkParams[iteration].NSigmaCut) {
 
                    const int clusId[3]{
                      mTimeFrame->getClusters()[iLayer][currentTracklet.firstClusterIndex].clusterId,
                      mTimeFrame->getClusters()[iLayer + 1][nextTracklet.firstClusterIndex].clusterId,
                      mTimeFrame->getClusters()[iLayer + 2][nextTracklet.secondClusterIndex].clusterId};
                    const auto& cluster1_glo = mTimeFrame->getUnsortedClusters()[iLayer][clusId[0]];
                    const auto& cluster2_glo = mTimeFrame->getUnsortedClusters()[iLayer + 1][clusId[1]];
                    const auto& cluster3_tf = mTimeFrame->getTrackingFrameInfoOnLayer(iLayer + 2)[clusId[2]];
                    auto track{buildTrackSeed(cluster1_glo, cluster2_glo, cluster3_tf)};
 
                    float chi2{0.f};
                    bool good{false};
                    for (int iC{2}; iC--;) {
                      const TrackingFrameInfo& trackingHit = mTimeFrame->getTrackingFrameInfoOnLayer(iLayer + iC)[clusId[iC]];
 
                      if (!track.rotate(trackingHit.alphaTrackingFrame)) {
                        break;
                      }
 
                      if (!track.propagateTo(trackingHit.xTrackingFrame, getBz())) {
                        break;
                      }
 
                      if (!track.correctForMaterial(mTrkParams[0].LayerxX0[iLayer + iC], mTrkParams[0].LayerxX0[iLayer] * radl * rho, true)) {
                        break;
                      }
 
                      const auto predChi2{track.getPredictedChi2Quiet(trackingHit.positionTrackingFrame, trackingHit.covarianceTrackingFrame)};
                      if (!iC && predChi2 > mTrkParams[iteration].MaxChi2ClusterAttachment) {
                        break;
                      }
 
                      if (!track.o2::track::TrackParCov::update(trackingHit.positionTrackingFrame, trackingHit.covarianceTrackingFrame)) {
                        break;
                      }
 
                      good = !iC;
                      chi2 += predChi2;
                    }
                    if (good) {
                      layerCells[position++] = CellSeed(iLayer, clusId[0], clusId[1], clusId[2], iTracklet, iNextTracklet, track, chi2);
                    }
                  }
                }
              }
            });
 
          if (iLayer > 0) {
            auto& lut = mTimeFrame->getCellsLookupTable()[iLayer - 1];
            lut.resize(currentLayerTrackletsNum + 1);
            std::copy_n(perTrackletCount.begin(), currentLayerTrackletsNum + 1, lut.begin());
          }
        }
      });
  });
 
  if (mTimeFrame->hasMCinformation()) {
    for (int iLayer{0}; iLayer < mTrkParams[iteration].CellsPerRoad(); ++iLayer) {
      for (auto& cell : mTimeFrame->getCells()[iLayer]) {
        MCCompLabel currentLab{mTimeFrame->getTrackletsLabel(iLayer)[cell.getFirstTrackletIndex()]};
        MCCompLabel nextLab{mTimeFrame->getTrackletsLabel(iLayer + 1)[cell.getSecondTrackletIndex()]};
        mTimeFrame->getCellsLabel(iLayer).emplace_back(currentLab == nextLab ? currentLab : MCCompLabel());
      }
    }
  }
 
  if constexpr (debugLevel) {
    for (int iLayer{0}; iLayer < mTrkParams[iteration].CellsPerRoad(); ++iLayer) {
      std::cout << "Cells on layer " << iLayer << " " << mTimeFrame->getCells()[iLayer].size() << std::endl;
    }
  }
}
 
template <int nLayers>
void TrackerTraits<nLayers>::findCellsNeighbours(const int iteration)
{
#ifdef OPTIMISATION_OUTPUT
  std::ofstream off(std::format("cellneighs{}.txt", iteration));
#endif
  for (int iLayer{0}; iLayer < mTrkParams[iteration].CellsPerRoad() - 1; ++iLayer) {
    const int nextLayerCellsNum{static_cast<int>(mTimeFrame->getCells()[iLayer + 1].size())};
    deepVectorClear(mTimeFrame->getCellsNeighbours()[iLayer]);
    deepVectorClear(mTimeFrame->getCellsNeighboursLUT()[iLayer]);
    if (mTimeFrame->getCells()[iLayer + 1].empty() ||
        mTimeFrame->getCellsLookupTable()[iLayer].empty()) {
      continue;
    }
 
    mTaskArena.execute([&] {
      int layerCellsNum{static_cast<int>(mTimeFrame->getCells()[iLayer].size())};
 
      bounded_vector<int> perCellCount(layerCellsNum + 1, 0, mMemoryPool.get());
      tbb::parallel_for(
        tbb::blocked_range<int>(0, layerCellsNum),
        [&](const tbb::blocked_range<int>& Cells) {
          for (int iCell = Cells.begin(); iCell < Cells.end(); ++iCell) {
            const auto& currentCellSeed{mTimeFrame->getCells()[iLayer][iCell]};
            const int nextLayerTrackletIndex{currentCellSeed.getSecondTrackletIndex()};
            const int nextLayerFirstCellIndex{mTimeFrame->getCellsLookupTable()[iLayer][nextLayerTrackletIndex]};
            const int nextLayerLastCellIndex{mTimeFrame->getCellsLookupTable()[iLayer][nextLayerTrackletIndex + 1]};
 
            int foundNextCells{0};
            for (int iNextCell{nextLayerFirstCellIndex}; iNextCell < nextLayerLastCellIndex; ++iNextCell) {
              auto nextCellSeed{mTimeFrame->getCells()[iLayer + 1][iNextCell]}; 
              if (nextCellSeed.getFirstTrackletIndex() != nextLayerTrackletIndex) {
                break;
              }
 
              if (!nextCellSeed.rotate(currentCellSeed.getAlpha()) ||
                  !nextCellSeed.propagateTo(currentCellSeed.getX(), getBz())) {
                continue;
              }
              float chi2 = currentCellSeed.getPredictedChi2(nextCellSeed); 
 
#ifdef OPTIMISATION_OUTPUT
              bool good{mTimeFrame->getCellsLabel(iLayer)[iCell] == mTimeFrame->getCellsLabel(iLayer + 1)[iNextCell]};
              off << std::format("{}\t{:d}\t{}", iLayer, good, chi2) << std::endl;
#endif
 
              if (chi2 > mTrkParams[0].MaxChi2ClusterAttachment) {
                continue;
              }
              ++foundNextCells;
            }
            perCellCount[iCell] = foundNextCells;
          }
        });
 
      std::exclusive_scan(perCellCount.begin(), perCellCount.end(), perCellCount.begin(), 0);
      int totalCellNeighbours = perCellCount.back();
      if (totalCellNeighbours == 0) {
        deepVectorClear(mTimeFrame->getCellsNeighbours()[iLayer]);
        return;
      }
 
      struct Neighbor {
        int cell{-1}, nextCell{-1}, level{-1};
      };
      bounded_vector<Neighbor> cellsNeighbours(mMemoryPool.get());
      cellsNeighbours.resize(totalCellNeighbours);
 
      tbb::parallel_for(
        tbb::blocked_range<int>(0, layerCellsNum),
        [&](const tbb::blocked_range<int>& Cells) {
          for (int iCell = Cells.begin(); iCell < Cells.end(); ++iCell) {
            if (perCellCount[iCell] == perCellCount[iCell + 1]) {
              continue;
            }
            const auto& currentCellSeed{mTimeFrame->getCells()[iLayer][iCell]};
            const int nextLayerTrackletIndex{currentCellSeed.getSecondTrackletIndex()};
            const int nextLayerFirstCellIndex{mTimeFrame->getCellsLookupTable()[iLayer][nextLayerTrackletIndex]};
            const int nextLayerLastCellIndex{mTimeFrame->getCellsLookupTable()[iLayer][nextLayerTrackletIndex + 1]};
 
            int position = perCellCount[iCell];
            for (int iNextCell{nextLayerFirstCellIndex}; iNextCell < nextLayerLastCellIndex; ++iNextCell) {
              auto nextCellSeed{mTimeFrame->getCells()[iLayer + 1][iNextCell]}; 
              if (nextCellSeed.getFirstTrackletIndex() != nextLayerTrackletIndex) {
                break;
              }
 
              if (!nextCellSeed.rotate(currentCellSeed.getAlpha()) ||
                  !nextCellSeed.propagateTo(currentCellSeed.getX(), getBz())) {
                continue;
              }
 
              float chi2 = currentCellSeed.getPredictedChi2(nextCellSeed); 
              if (chi2 > mTrkParams[0].MaxChi2ClusterAttachment) {
                continue;
              }
 
              cellsNeighbours[position++] = {iCell, iNextCell, currentCellSeed.getLevel() + 1};
            }
          }
        });
 
      tbb::parallel_sort(cellsNeighbours.begin(), cellsNeighbours.end(), [](const auto& a, const auto& b) {
        return a.nextCell < b.nextCell;
      });
 
      auto& cellsNeighbourLUT = mTimeFrame->getCellsNeighboursLUT()[iLayer];
      cellsNeighbourLUT.assign(nextLayerCellsNum, 0);
      for (const auto& neigh : cellsNeighbours) {
        ++cellsNeighbourLUT[neigh.nextCell];
      }
      std::inclusive_scan(cellsNeighbourLUT.begin(), cellsNeighbourLUT.end(), cellsNeighbourLUT.begin());
 
      mTimeFrame->getCellsNeighbours()[iLayer].reserve(totalCellNeighbours);
      std::ranges::transform(cellsNeighbours, std::back_inserter(mTimeFrame->getCellsNeighbours()[iLayer]), [](const auto& neigh) { return neigh.cell; });
 
      auto it = cellsNeighbours.begin();
      while (it != cellsNeighbours.end()) {
        const int current_nextCell = it->nextCell;
        auto group_end = std::find_if_not(it, cellsNeighbours.end(),
                                          [current_nextCell](const auto& nb) { return nb.nextCell == current_nextCell; });
        const auto max_level_it = std::max_element(it, group_end,
                                                   [](const auto& a, const auto& b) { return a.level < b.level; });
        mTimeFrame->getCells()[iLayer + 1][current_nextCell].setLevel(max_level_it->level);
        it = group_end;
      }
    });
  }
}
 
template <int nLayers>
void TrackerTraits<nLayers>::processNeighbours(int iLayer, int iLevel, const bounded_vector<CellSeed>& currentCellSeed, const bounded_vector<int>& currentCellId, bounded_vector<CellSeed>& updatedCellSeeds, bounded_vector<int>& updatedCellsIds)
{
  CA_DEBUGGER(std::cout << "Processing neighbours layer " << iLayer << " level " << iLevel << ", size of the cell seeds: " << currentCellSeed.size() << std::endl);
  auto propagator = o2::base::Propagator::Instance();
 
#ifdef CA_DEBUG
  int failed[5]{0, 0, 0, 0, 0}, attempts{0}, failedByMismatch{0};
#endif
 
  mTaskArena.execute([&] {
    bounded_vector<int> perCellCount(currentCellSeed.size() + 1, 0, mMemoryPool.get());
    tbb::parallel_for(
      tbb::blocked_range<int>(0, (int)currentCellSeed.size()),
      [&](const tbb::blocked_range<int>& Cells) {
        for (int iCell = Cells.begin(); iCell < Cells.end(); ++iCell) {
          const CellSeed& currentCell{currentCellSeed[iCell]};
          int foundSeeds{0};
          if (currentCell.getLevel() != iLevel) {
            continue;
          }
          if (currentCellId.empty() && (mTimeFrame->isClusterUsed(iLayer, currentCell.getFirstClusterIndex()) ||
                                        mTimeFrame->isClusterUsed(iLayer + 1, currentCell.getSecondClusterIndex()) ||
                                        mTimeFrame->isClusterUsed(iLayer + 2, currentCell.getThirdClusterIndex()))) {
            continue; 
          }
          const int cellId = currentCellId.empty() ? iCell : currentCellId[iCell];
          const int startNeighbourId{cellId ? mTimeFrame->getCellsNeighboursLUT()[iLayer - 1][cellId - 1] : 0};
          const int endNeighbourId{mTimeFrame->getCellsNeighboursLUT()[iLayer - 1][cellId]};
 
          for (int iNeighbourCell{startNeighbourId}; iNeighbourCell < endNeighbourId; ++iNeighbourCell) {
            CA_DEBUGGER(attempts++);
            const int neighbourCellId = mTimeFrame->getCellsNeighbours()[iLayer - 1][iNeighbourCell];
            const CellSeed& neighbourCell = mTimeFrame->getCells()[iLayer - 1][neighbourCellId];
            if (neighbourCell.getSecondTrackletIndex() != currentCell.getFirstTrackletIndex()) {
              CA_DEBUGGER(failedByMismatch++);
              continue;
            }
            if (mTimeFrame->isClusterUsed(iLayer - 1, neighbourCell.getFirstClusterIndex())) {
              continue;
            }
            if (currentCell.getLevel() - 1 != neighbourCell.getLevel()) {
              CA_DEBUGGER(failed[0]++);
              continue;
            }
            CellSeed seed{currentCell};
            auto& trHit = mTimeFrame->getTrackingFrameInfoOnLayer(iLayer - 1)[neighbourCell.getFirstClusterIndex()];
 
            if (!seed.rotate(trHit.alphaTrackingFrame)) {
              CA_DEBUGGER(failed[1]++);
              continue;
            }
 
            if (!propagator->propagateToX(seed, trHit.xTrackingFrame, getBz(), o2::base::PropagatorImpl<float>::MAX_SIN_PHI, o2::base::PropagatorImpl<float>::MAX_STEP, mCorrType)) {
              CA_DEBUGGER(failed[2]++);
              continue;
            }
 
            if (mCorrType == o2::base::PropagatorF::MatCorrType::USEMatCorrNONE) {
              float radl = 9.36f; // Radiation length of Si [cm]
              float rho = 2.33f;  // Density of Si [g/cm^3]
              if (!seed.correctForMaterial(mTrkParams[0].LayerxX0[iLayer - 1], mTrkParams[0].LayerxX0[iLayer - 1] * radl * rho, true)) {
                continue;
              }
            }
 
            auto predChi2{seed.getPredictedChi2Quiet(trHit.positionTrackingFrame, trHit.covarianceTrackingFrame)};
            if ((predChi2 > mTrkParams[0].MaxChi2ClusterAttachment) || predChi2 < 0.f) {
              CA_DEBUGGER(failed[3]++);
              continue;
            }
            seed.setChi2(seed.getChi2() + predChi2);
            if (!seed.o2::track::TrackParCov::update(trHit.positionTrackingFrame, trHit.covarianceTrackingFrame)) {
              CA_DEBUGGER(failed[4]++);
              continue;
            }
            ++foundSeeds;
          }
          perCellCount[iCell] = foundSeeds;
        }
      });
 
    std::exclusive_scan(perCellCount.begin(), perCellCount.end(), perCellCount.begin(), 0);
    auto totalNeighbours{perCellCount.back()};
    if (totalNeighbours == 0) {
      return;
    }
    updatedCellSeeds.resize(totalNeighbours);
    updatedCellsIds.resize(totalNeighbours);
 
    tbb::parallel_for(
      tbb::blocked_range<int>(0, (int)currentCellSeed.size()),
      [&](const tbb::blocked_range<int>& Cells) {
        for (int iCell = Cells.begin(); iCell < Cells.end(); ++iCell) {
          if (perCellCount[iCell] == perCellCount[iCell + 1]) {
            continue;
          }
          // no need for further checks on cell level
 
          const CellSeed& currentCell{currentCellSeed[iCell]};
          const int cellId = currentCellId.empty() ? iCell : currentCellId[iCell];
          const int startNeighbourId{cellId ? mTimeFrame->getCellsNeighboursLUT()[iLayer - 1][cellId - 1] : 0};
          const int endNeighbourId{mTimeFrame->getCellsNeighboursLUT()[iLayer - 1][cellId]};
 
          int offset = perCellCount[iCell];
          for (int iNeighbourCell{startNeighbourId}; iNeighbourCell < endNeighbourId; ++iNeighbourCell) {
            const int neighbourCellId = mTimeFrame->getCellsNeighbours()[iLayer - 1][iNeighbourCell];
            const CellSeed& neighbourCell = mTimeFrame->getCells()[iLayer - 1][neighbourCellId];
            if (neighbourCell.getSecondTrackletIndex() != currentCell.getFirstTrackletIndex() ||
                mTimeFrame->isClusterUsed(iLayer - 1, neighbourCell.getFirstClusterIndex()) ||
                currentCell.getLevel() - 1 != neighbourCell.getLevel()) {
              continue;
            }
 
            auto seed = currentCell;
 
            const auto& trHit = mTimeFrame->getTrackingFrameInfoOnLayer(iLayer - 1)[neighbourCell.getFirstClusterIndex()];
            if (!seed.rotate(trHit.alphaTrackingFrame) || !propagator->propagateToX(seed, trHit.xTrackingFrame, getBz(), o2::base::PropagatorImpl<float>::MAX_SIN_PHI, o2::base::PropagatorImpl<float>::MAX_STEP, mCorrType)) {
              continue;
            }
 
            if (mCorrType == o2::base::PropagatorF::MatCorrType::USEMatCorrNONE) {
              float radl = 9.36f; // Radiation length of Si [cm]
              float rho = 2.33f;  // Density of Si [g/cm^3]
              if (!seed.correctForMaterial(mTrkParams[0].LayerxX0[iLayer - 1], mTrkParams[0].LayerxX0[iLayer - 1] * radl * rho, true)) {
                continue;
              }
            }
 
            auto predChi2{seed.getPredictedChi2Quiet(trHit.positionTrackingFrame, trHit.covarianceTrackingFrame)};
            if ((predChi2 > mTrkParams[0].MaxChi2ClusterAttachment) || predChi2 < 0.f) {
              continue;
            }
            seed.setChi2(seed.getChi2() + predChi2);
            if (!seed.o2::track::TrackParCov::update(trHit.positionTrackingFrame, trHit.covarianceTrackingFrame)) {
              continue;
            }
 
            seed.getClusters()[iLayer - 1] = neighbourCell.getFirstClusterIndex();
            seed.setLevel(neighbourCell.getLevel());
            seed.setFirstTrackletIndex(neighbourCell.getFirstTrackletIndex());
            seed.setSecondTrackletIndex(neighbourCell.getSecondTrackletIndex());
 
            updatedCellSeeds[offset] = seed;
            updatedCellsIds[offset++] = neighbourCellId;
          }
        }
      });
  });
 
#ifdef CA_DEBUG
  std::cout << "\t\t- Found " << updatedCellSeeds.size() << " cell seeds out of " << attempts << " attempts" << std::endl;
  std::cout << "\t\t\t> " << failed[0] << " failed because of level" << std::endl;
  std::cout << "\t\t\t> " << failed[1] << " failed because of rotation" << std::endl;
  std::cout << "\t\t\t> " << failed[2] << " failed because of propagation" << std::endl;
  std::cout << "\t\t\t> " << failed[3] << " failed because of chi2 cut" << std::endl;
  std::cout << "\t\t\t> " << failed[4] << " failed because of update" << std::endl;
  std::cout << "\t\t\t> " << failedByMismatch << " failed because of mismatch" << std::endl;
#endif
}
 
template <int nLayers>
void TrackerTraits<nLayers>::findRoads(const int iteration)
{
  CA_DEBUGGER(std::cout << "Finding roads, iteration " << iteration << std::endl);
 
  for (int startLevel{mTrkParams[iteration].CellsPerRoad()}; startLevel >= mTrkParams[iteration].CellMinimumLevel(); --startLevel) {
    CA_DEBUGGER(std::cout << "\t > Processing level " << startLevel << std::endl);
    auto seedFilter = [&](const CellSeed& seed) {
      return seed.getQ2Pt() <= 1.e3 && seed.getChi2() <= mTrkParams[0].MaxChi2NDF * ((startLevel + 2) * 2 - 5);
    };
    bounded_vector<CellSeed> trackSeeds(mMemoryPool.get());
    for (int startLayer{mTrkParams[iteration].CellsPerRoad() - 1}; startLayer >= startLevel - 1; --startLayer) {
      if ((mTrkParams[iteration].StartLayerMask & (1 << (startLayer + 2))) == 0) {
        continue;
      }
      CA_DEBUGGER(std::cout << "\t\t > Starting processing layer " << startLayer << std::endl);
      bounded_vector<int> lastCellId(mMemoryPool.get()), updatedCellId(mMemoryPool.get());
      bounded_vector<CellSeed> lastCellSeed(mMemoryPool.get()), updatedCellSeed(mMemoryPool.get());
 
      processNeighbours(startLayer, startLevel, mTimeFrame->getCells()[startLayer], lastCellId, updatedCellSeed, updatedCellId);
 
      int level = startLevel;
      for (int iLayer{startLayer - 1}; iLayer > 0 && level > 2; --iLayer) {
        lastCellSeed.swap(updatedCellSeed);
        lastCellId.swap(updatedCellId);
        deepVectorClear(updatedCellSeed); 
        deepVectorClear(updatedCellId);   
        processNeighbours(iLayer, --level, lastCellSeed, lastCellId, updatedCellSeed, updatedCellId);
      }
      deepVectorClear(lastCellId);   
      deepVectorClear(lastCellSeed); 
 
      if (!updatedCellSeed.empty()) {
        trackSeeds.reserve(trackSeeds.size() + std::count_if(updatedCellSeed.begin(), updatedCellSeed.end(), seedFilter));
        std::copy_if(updatedCellSeed.begin(), updatedCellSeed.end(), std::back_inserter(trackSeeds), seedFilter);
      }
    }
 
    if (trackSeeds.empty()) {
      continue;
    }
 
    bounded_vector<TrackITSExt> tracks(mMemoryPool.get());
    mTaskArena.execute([&] {
      bounded_vector<int> perSeedCount(trackSeeds.size() + 1, 0, mMemoryPool.get());
      tbb::parallel_for(
        tbb::blocked_range<size_t>(size_t(0), trackSeeds.size()),
        [&](const tbb::blocked_range<size_t>& Seeds) {
          for (int iSeed = Seeds.begin(); iSeed < Seeds.end(); ++iSeed) {
            const CellSeed& seed{trackSeeds[iSeed]};
            TrackITSExt temporaryTrack{seed};
            temporaryTrack.resetCovariance();
            temporaryTrack.setChi2(0);
            for (int iL{0}; iL < 7; ++iL) {
              temporaryTrack.setExternalClusterIndex(iL, seed.getCluster(iL), seed.getCluster(iL) != constants::its::UnusedIndex);
            }
 
            bool fitSuccess = fitTrack(temporaryTrack, 0, mTrkParams[0].NLayers, 1, mTrkParams[0].MaxChi2ClusterAttachment, mTrkParams[0].MaxChi2NDF);
            if (!fitSuccess) {
              continue;
            }
            temporaryTrack.getParamOut() = temporaryTrack.getParamIn();
            temporaryTrack.resetCovariance();
            temporaryTrack.setChi2(0);
            fitSuccess = fitTrack(temporaryTrack, mTrkParams[0].NLayers - 1, -1, -1, mTrkParams[0].MaxChi2ClusterAttachment, mTrkParams[0].MaxChi2NDF, 50.f);
            if (!fitSuccess || temporaryTrack.getPt() < mTrkParams[iteration].MinPt[mTrkParams[iteration].NLayers - temporaryTrack.getNClusters()]) {
              continue;
            }
            ++perSeedCount[iSeed];
          }
        });
      std::exclusive_scan(perSeedCount.begin(), perSeedCount.end(), perSeedCount.begin(), 0);
      auto totalTracks{perSeedCount.back()};
      if (totalTracks == 0) {
        return;
      }
      tracks.resize(totalTracks);
 
      tbb::parallel_for(
        tbb::blocked_range<int>(0, (int)trackSeeds.size()),
        [&](const tbb::blocked_range<int>& Seeds) {
          for (int iSeed = Seeds.begin(); iSeed < Seeds.end(); ++iSeed) {
            if (perSeedCount[iSeed] == perSeedCount[iSeed + 1]) {
              continue;
            }
            const CellSeed& seed{trackSeeds[iSeed]};
            auto& trk = tracks[perSeedCount[iSeed]] = TrackITSExt(seed);
            trk.resetCovariance();
            trk.setChi2(0);
            for (int iL{0}; iL < 7; ++iL) {
              trk.setExternalClusterIndex(iL, seed.getCluster(iL), seed.getCluster(iL) != constants::its::UnusedIndex);
            }
 
            bool fitSuccess = fitTrack(trk, 0, mTrkParams[0].NLayers, 1, mTrkParams[0].MaxChi2ClusterAttachment, mTrkParams[0].MaxChi2NDF);
            if (!fitSuccess) {
              continue;
            }
            trk.getParamOut() = trk.getParamIn();
            trk.resetCovariance();
            trk.setChi2(0);
            fitTrack(trk, mTrkParams[0].NLayers - 1, -1, -1, mTrkParams[0].MaxChi2ClusterAttachment, mTrkParams[0].MaxChi2NDF, 50.f);
          }
        });
 
      deepVectorClear(trackSeeds);
      tbb::parallel_sort(tracks.begin(), tracks.end(), [](const auto& a, const auto& b) {
        return a.getChi2() < b.getChi2();
      });
    });
 
    for (auto& track : tracks) {
      int nShared = 0;
      bool isFirstShared{false};
      for (int iLayer{0}; iLayer < mTrkParams[0].NLayers; ++iLayer) {
        if (track.getClusterIndex(iLayer) == constants::its::UnusedIndex) {
          continue;
        }
        nShared += int(mTimeFrame->isClusterUsed(iLayer, track.getClusterIndex(iLayer)));
        isFirstShared |= !iLayer && mTimeFrame->isClusterUsed(iLayer, track.getClusterIndex(iLayer));
      }
 
      if (nShared > mTrkParams[0].ClusterSharing) {
        continue;
      }
 
      std::array<int, 3> rofs{INT_MAX, INT_MAX, INT_MAX};
      for (int iLayer{0}; iLayer < mTrkParams[0].NLayers; ++iLayer) {
        if (track.getClusterIndex(iLayer) == constants::its::UnusedIndex) {
          continue;
        }
        mTimeFrame->markUsedCluster(iLayer, track.getClusterIndex(iLayer));
        int currentROF = mTimeFrame->getClusterROF(iLayer, track.getClusterIndex(iLayer));
        for (int iR{0}; iR < 3; ++iR) {
          if (rofs[iR] == INT_MAX) {
            rofs[iR] = currentROF;
          }
          if (rofs[iR] == currentROF) {
            break;
          }
        }
      }
      if (rofs[2] != INT_MAX) {
        continue;
      }
      track.setUserField(0);
      track.getParamOut().setUserField(0);
      if (rofs[1] != INT_MAX) {
        track.setNextROFbit();
      }
      mTimeFrame->getTracks(o2::gpu::CAMath::Min(rofs[0], rofs[1])).emplace_back(track);
    }
  }
}
 
template <int nLayers>
void TrackerTraits<nLayers>::extendTracks(const int iteration)
{
  for (int rof{0}; rof < mTimeFrame->getNrof(); ++rof) {
    for (auto& track : mTimeFrame->getTracks(rof)) {
      auto backup{track};
      bool success{false};
      // the order here biases towards top extension, tracks should probably be fitted separately in the directions and then compared.
      if ((mTrkParams[iteration].UseTrackFollowerMix || mTrkParams[iteration].UseTrackFollowerTop) && track.getLastClusterLayer() != mTrkParams[iteration].NLayers - 1) {
        success = success || trackFollowing(&track, rof, true, iteration);
      }
      if ((mTrkParams[iteration].UseTrackFollowerMix || (mTrkParams[iteration].UseTrackFollowerBot && !success)) && track.getFirstClusterLayer() != 0) {
        success = success || trackFollowing(&track, rof, false, iteration);
      }
      if (success) {
        track.resetCovariance();
        track.setChi2(0);
        bool fitSuccess = fitTrack(track, 0, mTrkParams[iteration].NLayers, 1, mTrkParams[iteration].MaxChi2ClusterAttachment, mTrkParams[0].MaxChi2NDF);
        if (!fitSuccess) {
          track = backup;
          continue;
        }
        track.getParamOut() = track;
        track.resetCovariance();
        track.setChi2(0);
        fitSuccess = fitTrack(track, mTrkParams[iteration].NLayers - 1, -1, -1, mTrkParams[iteration].MaxChi2ClusterAttachment, mTrkParams[0].MaxChi2NDF, 50.);
        if (!fitSuccess) {
          track = backup;
          continue;
        }
        mTimeFrame->mNExtendedTracks++;
        mTimeFrame->mNExtendedUsedClusters += track.getNClusters() - backup.getNClusters();
        auto pattern = track.getPattern();
        auto diff = (pattern & ~backup.getPattern()) & 0xff;
        pattern |= (diff << 24);
        track.setPattern(pattern);
        for (int iLayer{0}; iLayer < mTrkParams[iteration].NLayers; ++iLayer) {
          if (track.getClusterIndex(iLayer) == constants::its::UnusedIndex) {
            continue;
          }
          mTimeFrame->markUsedCluster(iLayer, track.getClusterIndex(iLayer));
        }
      }
    }
  }
}
 
template <int nLayers>
void TrackerTraits<nLayers>::findShortPrimaries()
{
  const auto propagator = o2::base::Propagator::Instance();
  mTimeFrame->fillPrimaryVerticesXandAlpha();
 
  for (auto& cell : mTimeFrame->getCells()[0]) {
    auto& cluster3_glo = mTimeFrame->getClusters()[2][cell.getThirdClusterIndex()];
    auto& cluster2_glo = mTimeFrame->getClusters()[1][cell.getSecondClusterIndex()];
    auto& cluster1_glo = mTimeFrame->getClusters()[0][cell.getFirstClusterIndex()];
    if (mTimeFrame->isClusterUsed(2, cluster1_glo.clusterId) ||
        mTimeFrame->isClusterUsed(1, cluster2_glo.clusterId) ||
        mTimeFrame->isClusterUsed(0, cluster3_glo.clusterId)) {
      continue;
    }
 
    std::array<int, 3> rofs{
      mTimeFrame->getClusterROF(2, cluster3_glo.clusterId),
      mTimeFrame->getClusterROF(1, cluster2_glo.clusterId),
      mTimeFrame->getClusterROF(0, cluster1_glo.clusterId)};
    if (rofs[0] != rofs[1] && rofs[1] != rofs[2] && rofs[0] != rofs[2]) {
      continue;
    }
 
    int rof{rofs[0]};
    if (rofs[1] == rofs[2]) {
      rof = rofs[2];
    }
 
    auto pvs{mTimeFrame->getPrimaryVertices(rof)};
    auto pvsXAlpha{mTimeFrame->getPrimaryVerticesXAlpha(rof)};
 
    const auto& cluster3_tf = mTimeFrame->getTrackingFrameInfoOnLayer(2)[cluster3_glo.clusterId];
    TrackITSExt temporaryTrack{buildTrackSeed(cluster1_glo, cluster2_glo, cluster3_tf)};
    temporaryTrack.setExternalClusterIndex(0, cluster1_glo.clusterId, true);
    temporaryTrack.setExternalClusterIndex(1, cluster2_glo.clusterId, true);
    temporaryTrack.setExternalClusterIndex(2, cluster3_glo.clusterId, true);
 
    bool fitSuccess = fitTrack(temporaryTrack, 1, -1, -1);
    if (!fitSuccess) {
      continue;
    }
    fitSuccess = false;
 
    TrackITSExt bestTrack{temporaryTrack}, backup{temporaryTrack};
    float bestChi2{std::numeric_limits<float>::max()};
    for (int iV{0}; iV < (int)pvs.size(); ++iV) {
      temporaryTrack = backup;
      if (!temporaryTrack.rotate(pvsXAlpha[iV][1])) {
        continue;
      }
      if (!propagator->propagateTo(temporaryTrack, pvsXAlpha[iV][0], true)) {
        continue;
      }
 
      float pvRes{mTrkParams[0].PVres / o2::gpu::CAMath::Sqrt(float(pvs[iV].getNContributors()))};
      const float posVtx[2]{0.f, pvs[iV].getZ()};
      const float covVtx[3]{pvRes, 0.f, pvRes};
      float chi2 = temporaryTrack.getPredictedChi2Quiet(posVtx, covVtx);
      if (chi2 < bestChi2) {
        if (!temporaryTrack.track::TrackParCov::update(posVtx, covVtx)) {
          continue;
        }
        bestTrack = temporaryTrack;
        bestChi2 = chi2;
      }
    }
 
    bestTrack.resetCovariance();
    bestTrack.setChi2(0.f);
    fitSuccess = fitTrack(bestTrack, 0, mTrkParams[0].NLayers, 1, mTrkParams[0].MaxChi2ClusterAttachment, mTrkParams[0].MaxChi2NDF);
    if (!fitSuccess) {
      continue;
    }
    bestTrack.getParamOut() = bestTrack;
    bestTrack.resetCovariance();
    bestTrack.setChi2(0.f);
    fitSuccess = fitTrack(bestTrack, mTrkParams[0].NLayers - 1, -1, -1, mTrkParams[0].MaxChi2ClusterAttachment, mTrkParams[0].MaxChi2NDF, 50.);
    if (!fitSuccess) {
      continue;
    }
    mTimeFrame->markUsedCluster(0, bestTrack.getClusterIndex(0));
    mTimeFrame->markUsedCluster(1, bestTrack.getClusterIndex(1));
    mTimeFrame->markUsedCluster(2, bestTrack.getClusterIndex(2));
    mTimeFrame->getTracks(rof).emplace_back(bestTrack);
  }
}
 
template <int nLayers>
bool TrackerTraits<nLayers>::fitTrack(TrackITSExt& track, int start, int end, int step, float chi2clcut, float chi2ndfcut, float maxQoverPt, int nCl)
{
  auto propInstance = o2::base::Propagator::Instance();
 
  for (int iLayer{start}; iLayer != end; iLayer += step) {
    if (track.getClusterIndex(iLayer) == constants::its::UnusedIndex) {
      continue;
    }
    const TrackingFrameInfo& trackingHit = mTimeFrame->getTrackingFrameInfoOnLayer(iLayer)[track.getClusterIndex(iLayer)];
 
    if (!track.rotate(trackingHit.alphaTrackingFrame)) {
      return false;
    }
 
    if (!propInstance->propagateToX(track, trackingHit.xTrackingFrame, getBz(), o2::base::PropagatorImpl<float>::MAX_SIN_PHI, o2::base::PropagatorImpl<float>::MAX_STEP, mCorrType)) {
      return false;
    }
 
    if (mCorrType == o2::base::PropagatorF::MatCorrType::USEMatCorrNONE) {
      constexpr float radl = 9.36f; // Radiation length of Si [cm]
      constexpr float rho = 2.33f;  // Density of Si [g/cm^3]
      if (!track.correctForMaterial(mTrkParams[0].LayerxX0[iLayer], mTrkParams[0].LayerxX0[iLayer] * radl * rho, true)) {
        continue;
      }
    }
 
    auto predChi2{track.getPredictedChi2Quiet(trackingHit.positionTrackingFrame, trackingHit.covarianceTrackingFrame)};
    if ((nCl >= 3 && predChi2 > chi2clcut) || predChi2 < 0.f) {
      return false;
    }
    track.setChi2(track.getChi2() + predChi2);
    if (!track.o2::track::TrackParCov::update(trackingHit.positionTrackingFrame, trackingHit.covarianceTrackingFrame)) {
      return false;
    }
    nCl++;
  }
  return std::abs(track.getQ2Pt()) < maxQoverPt && track.getChi2() < chi2ndfcut * (nCl * 2 - 5);
}
 
template <int nLayers>
bool TrackerTraits<nLayers>::trackFollowing(TrackITSExt* track, int rof, bool outward, const int iteration)
{
  auto propInstance = o2::base::Propagator::Instance();
  const int step = -1 + outward * 2;
  const int end = outward ? mTrkParams[iteration].NLayers - 1 : 0;
  bounded_vector<TrackITSExt> hypotheses(1, *track, mMemoryPool.get()); // possibly avoid reallocation
  for (size_t iHypo{0}; iHypo < hypotheses.size(); ++iHypo) {
    auto hypo{hypotheses[iHypo]};
    int iLayer = static_cast<int>(outward ? hypo.getLastClusterLayer() : hypo.getFirstClusterLayer());
    // per layer we add new hypotheses
    while (iLayer != end) {
      iLayer += step; // step through all layers until we reach the end, this allows for skipping on empty layers
      const float r = mTrkParams[iteration].LayerRadii[iLayer];
      // get an estimate of the trackinf-frame x for the next step
      float x{-999};
      if (!hypo.getXatLabR(r, x, mTimeFrame->getBz(), o2::track::DirAuto) || x <= 0.f) {
        continue;
      }
      // estimate hypo's trk parameters at that x
      auto& hypoParam{outward ? hypo.getParamOut() : hypo.getParamIn()};
      if (!propInstance->propagateToX(hypoParam, x, mTimeFrame->getBz(), PropagatorF::MAX_SIN_PHI,
                                      PropagatorF::MAX_STEP, mTrkParams[iteration].CorrType)) {
        continue;
      }
 
      if (mTrkParams[iteration].CorrType == PropagatorF::MatCorrType::USEMatCorrNONE) { // account for material affects if propagator does not
        constexpr float radl = 9.36f;                                                   // Radiation length of Si [cm]
        constexpr float rho = 2.33f;                                                    // Density of Si [g/cm^3]
        if (!hypoParam.correctForMaterial(mTrkParams[iteration].LayerxX0[iLayer], mTrkParams[iteration].LayerxX0[iLayer] * radl * rho, true)) {
          continue;
        }
      }
 
      // calculate the search window on this layer
      const float phi{hypoParam.getPhi()};
      const float ePhi{o2::gpu::CAMath::Sqrt(hypoParam.getSigmaSnp2() / hypoParam.getCsp2())};
      const float z{hypoParam.getZ()};
      const float eZ{o2::gpu::CAMath::Sqrt(hypoParam.getSigmaZ2())};
      const int4 selectedBinsRect{getBinsRect(iLayer, phi, mTrkParams[iteration].TrackFollowerNSigmaCutPhi * ePhi, z, mTrkParams[iteration].TrackFollowerNSigmaCutZ * eZ)};
      if (selectedBinsRect.x == 0 && selectedBinsRect.y == 0 && selectedBinsRect.z == 0 && selectedBinsRect.w == 0) {
        continue;
      }
 
      int phiBinsNum{selectedBinsRect.w - selectedBinsRect.y + 1};
 
      if (phiBinsNum < 0) {
        phiBinsNum += mTrkParams[iteration].PhiBins;
      }
 
      gsl::span<const Cluster> layer1 = mTimeFrame->getClustersOnLayer(rof, iLayer);
      if (layer1.empty()) {
        continue;
      }
 
      // check all clusters in search windows for possible new hypotheses
      for (int iPhiCount = 0; iPhiCount < phiBinsNum; iPhiCount++) {
        int iPhiBin = (selectedBinsRect.y + iPhiCount) % mTrkParams[iteration].PhiBins;
        const int firstBinIndex{mTimeFrame->mIndexTableUtils.getBinIndex(selectedBinsRect.x, iPhiBin)};
        const int maxBinIndex{firstBinIndex + selectedBinsRect.z - selectedBinsRect.x + 1};
        const int firstRowClusterIndex = mTimeFrame->getIndexTable(rof, iLayer)[firstBinIndex];
        const int maxRowClusterIndex = mTimeFrame->getIndexTable(rof, iLayer)[maxBinIndex];
 
        for (int iNextCluster{firstRowClusterIndex}; iNextCluster < maxRowClusterIndex; ++iNextCluster) {
          if (iNextCluster >= (int)layer1.size()) {
            break;
          }
          const Cluster& nextCluster{layer1[iNextCluster]};
 
          if (mTimeFrame->isClusterUsed(iLayer, nextCluster.clusterId)) {
            continue;
          }
 
          const TrackingFrameInfo& trackingHit = mTimeFrame->getTrackingFrameInfoOnLayer(iLayer)[nextCluster.clusterId];
 
          auto tbupdated{hypo};
          auto& tbuParams = outward ? tbupdated.getParamOut() : tbupdated.getParamIn();
          if (!tbuParams.rotate(trackingHit.alphaTrackingFrame)) {
            continue;
          }
 
          if (!propInstance->propagateToX(tbuParams, trackingHit.xTrackingFrame, mTimeFrame->getBz(),
                                          PropagatorF::MAX_SIN_PHI, PropagatorF::MAX_STEP, PropagatorF::MatCorrType::USEMatCorrNONE)) {
            continue;
          }
 
          auto predChi2{tbuParams.getPredictedChi2Quiet(trackingHit.positionTrackingFrame, trackingHit.covarianceTrackingFrame)};
          if (predChi2 >= track->getChi2() * mTrkParams[iteration].NSigmaCut) {
            continue;
          }
 
          if (!tbuParams.o2::track::TrackParCov::update(trackingHit.positionTrackingFrame, trackingHit.covarianceTrackingFrame)) {
            continue;
          }
          tbupdated.setChi2(tbupdated.getChi2() + predChi2); 
          tbupdated.setExternalClusterIndex(iLayer, nextCluster.clusterId, true);
          hypotheses.emplace_back(tbupdated);
        }
      }
    }
  }
 
  TrackITSExt* bestHypo{track};
  bool swapped{false};
  for (auto& hypo : hypotheses) {
    if (hypo.isBetter(*bestHypo, track->getChi2() * mTrkParams[iteration].NSigmaCut)) {
      bestHypo = &hypo;
      swapped = true;
    }
  }
  *track = *bestHypo;
  return swapped;
}
 
template <int nLayers>
track::TrackParCov TrackerTraits<nLayers>::buildTrackSeed(const Cluster& cluster1, const Cluster& cluster2, const TrackingFrameInfo& tf3)
{
  float ca{-999.f}, sa{-999.f};
  o2::gpu::CAMath::SinCos(tf3.alphaTrackingFrame, sa, ca);
  const float x1 = cluster1.xCoordinate * ca + cluster1.yCoordinate * sa;
  const float y1 = -cluster1.xCoordinate * sa + cluster1.yCoordinate * ca;
  const float z1 = cluster1.zCoordinate;
  const float x2 = cluster2.xCoordinate * ca + cluster2.yCoordinate * sa;
  const float y2 = -cluster2.xCoordinate * sa + cluster2.yCoordinate * ca;
  const float z2 = cluster2.zCoordinate;
  const float x3 = tf3.xTrackingFrame;
  const float y3 = tf3.positionTrackingFrame[0];
  const float z3 = tf3.positionTrackingFrame[1];
  float tgp{1.f}, crv{1.f}, snp{-999.f}, tgl12{-999.f}, tgl23{-999.f}, q2pt{1.f / track::kMostProbablePt}, q2pt2{1.f}, sg2q2pt{-999.f};
  if (mIsZeroField) {
    tgp = o2::gpu::CAMath::ATan2(y3 - y1, x3 - x1);
    snp = tgp / o2::gpu::CAMath::Sqrt(1.f + tgp * tgp);
  } else {
    crv = math_utils::computeCurvature(x3, y3, x2, y2, x1, y1);
    snp = crv * (x3 - math_utils::computeCurvatureCentreX(x3, y3, x2, y2, x1, y1));
    q2pt = crv / (mBz * o2::constants::math::B2C);
    q2pt2 = crv * crv;
  }
  tgl12 = math_utils::computeTanDipAngle(x1, y1, x2, y2, z1, z2);
  tgl23 = math_utils::computeTanDipAngle(x2, y2, x3, y3, z2, z3);
  sg2q2pt = track::kC1Pt2max * (q2pt2 > 0.0005f ? (q2pt2 < 1.f ? q2pt2 : 1.f) : 0.0005f);
  return {tf3.xTrackingFrame, tf3.alphaTrackingFrame, {y3, z3, snp, 0.5f * (tgl12 + tgl23), q2pt}, {tf3.covarianceTrackingFrame[0], tf3.covarianceTrackingFrame[1], tf3.covarianceTrackingFrame[2], 0.f, 0.f, track::kCSnp2max, 0.f, 0.f, 0.f, track::kCTgl2max, 0.f, 0.f, 0.f, 0.f, sg2q2pt}};
}
 
template <int nLayers>
void TrackerTraits<nLayers>::setBz(float bz)
{
  mBz = bz;
  mIsZeroField = std::abs(mBz) < 0.01;
  mTimeFrame->setBz(bz);
}
 
template <int nLayers>
bool TrackerTraits<nLayers>::isMatLUT() const
{
  return o2::base::Propagator::Instance()->getMatLUT() && (mCorrType == o2::base::PropagatorImpl<float>::MatCorrType::USEMatCorrLUT);
}
 
template <int nLayers>
void TrackerTraits<nLayers>::setNThreads(int n)
{
  if (mNThreads == n && mTaskArena.is_active()) {
    return;
  }
  mNThreads = n > 0 ? n : 1;
#if defined(OPTIMISATION_OUTPUT) || defined(CA_DEBUG)
  mNThreads = 1; // only works while serial
#endif
  mTaskArena.initialize(mNThreads);
  LOGP(info, "Setting tracker with {} threads.", mNThreads);
}
 
template class TrackerTraits<7>;
 
} // namespace o2::its