// @(#) $Id: AliHLTTPCCAStartHitsFinder.cxx,v 1.5 2010/08/26 15:05:51 ikulakov Exp $
// **************************************************************************
// This file is property of and copyright by the ALICE HLT Project          *
// ALICE Experiment at CERN, All rights reserved.                           *
//                                                                          *
// Primary Authors: Sergey Gorbunov <sergey.gorbunov@kip.uni-heidelberg.de> *
//                  Ivan Kisel <kisel@kip.uni-heidelberg.de>                *
//                  for The ALICE HLT Project.                              *
//                                                                          *
// Developed by:   Igor Kulakov <I.Kulakov@gsi.de>                          *
//                 Maksym Zyzak <M.Zyzak@gsi.de>                            *
//                                                                          *
// Permission to use, copy, modify and distribute this software and its     *
// documentation strictly for non-commercial purposes is hereby granted     *
// without fee, provided that the above copyright notice appears in all     *
// copies and that both the copyright notice and this permission notice     *
// appear in the supporting documentation. The authors make no claims       *
// about the suitability of this software for any purpose. It is            *
// provided "as is" without express or implied warranty.                    *
//                                                                          *
//***************************************************************************

#define USE_ARBB
//#define USE_CALL

#include "AliHLTTPCCAStartHitsFinder.h"
#include "AliHLTTPCCATracker.h"
#include "AliHLTArray.h"
#include "AliHLTTPCCAMath.h"

#ifdef USE_TBB
#include <tbb/parallel_sort.h>
#endif //USE_TBB

#ifdef USE_ARBB
#include <arbb.hpp>
using namespace arbb;
#endif // USE_ARBB


//////////////////////////////////////////////////////////////////////////////
// depends on:
// - linkUp/linkDown data for the rows above and below the row to process
//
// changes atomically:
// - number of tracklets
//
// writes
// - tracklet start-hit ids
//
// only when all rows are done, is NTracklets known
//////////////////////////////////////////////////////////////////////////////

//X template<typename Int, typename Float>
//X struct SeedRowData {
//X   Int fRow;
//X   Int fHitIndex;
//X };
//X 
//X typedef std::vector<SeedRowData<ushort_v, sfloat_v> > SeedDataVector; // contains ushort_v::Size complete seeds
//X typedef std::vector<SeedRowData<unsigned short, float> > SeedDataScalar; // contains one complete seed
//X 
//X void AliHLTTPCCAStartHitsFinder::run( AliHLTTPCCATracker &tracker, const SliceData &data )
//X {
//X   SeedDataVector seed;
//X   const int lastRow = Parameters::NumberOfRows - 4;
//X   for ( int rowIndex = 2; rowIndex <= lastRow; ++rowIndex ) {
//X     // inside the row we're looking for hits that are linked upwards but not downwards, those start
//X     // a seed
//X     const int maxStorageSize = ( row.NHits() + short_v::Size - 1 ) / short_v::Size;
//X     short_v linkUpCompressedStorage[maxStorageSize];
//X     ushort_v hitIndexesCompressedStorage[maxStorageSize];
//X     short *linkUpCompressed = &linkUpCompressedStorage[0];
//X     unsigned short *hitIndexesCompressed = &hitIndexesCompressedStorage[0];
//X     for ( int hitIndex = 0; hitIndex < row.NHits(); hitIndex += short_v::Size ) {
//X       const short_v linkUp = data.HitLinkUpData( row, hitIndex );
//X       foreach_bit( int i, linkUp != -1 ) {
//X         *linkUpCompressed++ = linkUp[i];
//X         *hitIndexesCompressed++ = hitIndex + i;
//X       }
//X     }
//X   }
//X }
void AliHLTTPCCAStartHitsFinder::FindStartHits(AliHLTTPCCAStartHitId_ArBB::TDense<1>& startHits, nested_my<AliHLTTPCCARowHit>& rowsData, const FindStartHitsParam& param) {
  
  const TRowI_ArBB NRows = AliHLTTPCCAParameters::NumberOfRows;
  const TRowI_ArBB rowStep = AliHLTTPCCAParameters::RowStep;
  const TRowI_ArBB lastRow = NRows - rowStep*2;

  _for ( TRowI_ArBB iRow = 0, iRow <= lastRow, ++iRow ) {
    _if (rowsData.lengths()[iRow] <= 0) { _continue; } _end_if; // 0 hits on row
    AliHLTTPCCARowHit::TDense<1> row = rowsData.segment(iRow);
    
    dense<arbb::boolean> validHitsMask = ( row.IsUsed() == 0 ); // not-used hits can be connected only with not-used, so only one check is needed

    const THitI_ArBB taskSize = row.length();
      
    const dense<THitI_ArBB> &middleHitIndexes = row.LinkUp();
    validHitsMask = validHitsMask && ( row.LinkDn() < 0 ) && ( middleHitIndexes >= 0 ); // start hits are those which have a link up but none down
    _if ( any(validHitsMask) ) { // start hit has been found
      
      {   // find chains with an appropriate length
        TRowI_ArBB iCurRow = iRow + 1*rowStep;
        TRowI_ArBB nRows = 2; // number of rows in chain
        dense<THitI_ArBB> upperHitIndexes = middleHitIndexes;
        _for (,any(validHitsMask) && nRows < param.neighboursChainMinLength,) {
          AliHLTTPCCARowHit::TDense<1> curRow = rowsData.segment(iCurRow);
          upperHitIndexes = gather( curRow.LinkUp(), upperHitIndexes, static_cast<i16>(-10000), fill<i16>(-10000, taskSize), validHitsMask );
          validHitsMask = validHitsMask && upperHitIndexes >= 0;
          nRows++;
          iCurRow += rowStep;
        } _end_for;
      }

        // set all hits in the chains as used
      _if ( any(validHitsMask) ) {
        dense<arbb::boolean> goodChains = validHitsMask;
          
        row.SetIsUsed( select( goodChains, 1, row.IsUsed() ) );

        TRowI_ArBB iCurRow = iRow + 1*rowStep;
        dense<i16> nHits = fill(0, taskSize);
        nHits = select(goodChains, 2, nHits);
        dense<THitI_ArBB> upperHitIndexes = middleHitIndexes;
        _for (,any(goodChains),) {
          const usize curTaskSize = goodChains.length();
          _if ( rowsData.lengths()[iCurRow] <= 0 ) {
            goodChains = fill(false, curTaskSize);
            _continue;
          } _end_if;
          AliHLTTPCCARowHit::TDense<1> curRow = rowsData.segment(iCurRow);


          curRow.SetIsUsed( scatter( fill<i16>(1,curTaskSize), upperHitIndexes, curRow.IsUsed(), goodChains ) );
          upperHitIndexes = gather( curRow.LinkUp(), upperHitIndexes, static_cast<THitI_ArBB>(-1), fill<THitI_ArBB>(-1,curTaskSize), goodChains );

          goodChains = goodChains && upperHitIndexes >= 0;
          nHits = select(goodChains, nHits + 1, nHits);
          rowsData = replace_segment( rowsData, iCurRow, curRow );
                    
          iCurRow += rowStep;
        } _end_for;

          // save start hits
        _for( usize i = 0, i < validHitsMask.length(), ++i ) {
          _if ( validHitsMask[i] ) {
            startHits = cat_my( startHits, fill(AliHLTTPCCAStartHitId_ArBB(iRow, i, nHits[i]), 1) );
          } _end_if;
        } _end_for;

          //   // check free space
          // if ( ISUNLIKELY( startHitsCount >= kMaxStartHits ) ) { // TODO take in account stages kMax for one stage should be smaller
          //   break;
          // }
      } _end_if; // if good Chains
        
    } _end_if;

    rowsData = replace_segment( rowsData, iRow, row );
  } _end_for; // iRow
}


void AliHLTTPCCAStartHitsFinder::run( int iter )
{

  FindStartHitsParam param;
  param.neighboursChainMinLength = AliHLTTPCCAParameters::NeighboursChainMinLength[iter];
  FindStartHits(fStartHits_ArBB, fRows_ArBB, param);
}