/* ======================================================================== *\
!
! *
! * This file is part of MARS, the MAGIC Analysis and Reconstruction
! * Software. It is distributed to you in the hope that it can be a useful
! * and timesaving tool in analyzing Data of imaging Cerenkov telescopes.
! * It is distributed WITHOUT ANY WARRANTY.
! *
! * Permission to use, copy, modify and distribute this software and its
! * documentation for any purpose is hereby granted without fee,
! * provided that the above copyright notice appear in all copies and
! * that both that copyright notice and this permission notice appear
! * in supporting documentation. It is provided "as is" without express
! * or implied warranty.
! *
!
!   Author(s): Markus Gaug       09/2004 <mailto:markus@ifae.es> 
!
!   Copyright: MAGIC Software Development, 2002-2004
!
!
\* ======================================================================== */
//////////////////////////////////////////////////////////////////////////////
//
//   MExtractTimeAndChargeSpline
//
//   Fast Spline extractor using a cubic spline algorithm, adapted from 
//   Numerical Recipes in C++, 2nd edition, pp. 116-119.
//   
//   The coefficients "ya" are here denoted as "fHiGainSignal" and "fLoGainSignal"
//   which means the FADC value subtracted by the clock-noise corrected pedestal.
//
//   The coefficients "y2a" get immediately divided 6. and are called here 
//   "fHiGainSecondDeriv" and "fLoGainSecondDeriv" although they are now not exactly 
//   the second derivative coefficients any more. 
// 
//   The calculation of the cubic-spline interpolated value "y" on a point 
//   "x" along the FADC-slices axis becomes:
// 
//   y =    a*fHiGainSignal[klo] + b*fHiGainSignal[khi] 
//       + (a*a*a-a)*fHiGainSecondDeriv[klo] + (b*b*b-b)*fHiGainSecondDeriv[khi]
//
//   with:
//   a = (khi - x)
//   b = (x - klo)
//
//   and "klo" being the lower bin edge FADC index and "khi" the upper bin edge FADC index.
//   fHiGainSignal[klo] and fHiGainSignal[khi] are the FADC values at "klo" and "khi".
//
//   An analogues formula is used for the low-gain values.
//
//   The coefficients fHiGainSecondDeriv and fLoGainSecondDeriv are calculated with the 
//   following simplified algorithm:
//
//   for (Int_t i=1;i<range-1;i++) {
//       pp                   = fHiGainSecondDeriv[i-1] + 4.;
//       fHiGainFirstDeriv[i] = fHiGainSignal[i+1] - 2.*fHiGainSignal[i] + fHiGainSignal[i-1]
//       fHiGainFirstDeriv[i] = (6.0*fHiGainFirstDeriv[i]-fHiGainFirstDeriv[i-1])/pp;
//   }
// 
//   for (Int_t k=range-2;k>=0;k--)
//       fHiGainSecondDeriv[k] = (fHiGainSecondDeriv[k]*fHiGainSecondDeriv[k+1] + fHiGainFirstDeriv[k])/6.;
// 
//
//   This algorithm takes advantage of the fact that the x-values are all separated by exactly 1
//   which simplifies the Numerical Recipes algorithm.
//   (Note that the variables "fHiGainFirstDeriv" are not real first derivative coefficients.)
//
//
//   The algorithm to search the time proceeds as follows:
//
//   1) Calculate all fHiGainSignal from fHiGainFirst to fHiGainLast 
//      (note that an "overlap" to the low-gain arrays is possible: i.e. fHiGainLast>14 in the case of 
//      the MAGIC FADCs).
//   2) Remember the position of the slice with the highest content "fAbMax" at "fAbMaxPos".
//   3) If one or more slices are saturated or fAbMaxPos is less than 2 slices from fHiGainFirst, 
//      return fAbMaxPos as time and fAbMax as charge (note that the pedestal is subtracted here).
//   4) Calculate all fHiGainSecondDeriv from the fHiGainSignal array
//   5) Search for the maximum, starting in interval fAbMaxPos-1 in steps of 0.2 till fAbMaxPos-0.2.
//      If no maximum is found, go to interval fAbMaxPos+1. 
//      --> 4 function evaluations
//   6) Search for the absolute maximum from fAbMaxPos to fAbMaxPos+1 in steps of 0.2 
//      --> 4 function  evaluations
//   7) Try a better precision searching from new max. position fAbMaxPos-0.2 to fAbMaxPos+0.2
//      in steps of 0.025 (83 psec. in the case of the MAGIC FADCs).
//      --> 14 function evaluations
//   8) If Time Extraction Type kMaximum has been chosen, the position of the found maximum is 
//      returned, else:
//   9) The Half Maximum is calculated. 
//  10) fHiGainSignal is called beginning from fAbMaxPos-1 backwards until a value smaller than fHalfMax
//      is found at "klo". 
//  11) Then, the spline value between "klo" and "klo"+1 is halfed by means of bisection as long as 
//      the difference between fHalfMax and spline evaluation is less than fResolution (default: 0.01).
//      --> maximum 12 interations.
//   
//  The algorithm to search the charge proceeds as follows:
//
//  1) If Charge Type: kAmplitude was chosen, return the Maximum of the spline, found during the 
//     time search.
//  2) If Charge Type: kIntegral was chosen, sum the fHiGainSignal between:
//     (Int_t)(fAbMaxPos - fRiseTime) and 
//     (Int_t)(fAbMaxPos + fFallTime)
//     (default: fRiseTime: 1.5, fFallTime: 4.5)
//  3) Sum only half the values of the edge slices
//  4) Sum 1.5*fHiGainSecondDeriv of the not-edge slices using the "natural cubic 
//     spline with second derivatives set to 0. at the edges.
//     (Remember that fHiGainSecondDeriv had been divided by 6.)
//   
//  The values: fNumHiGainSamples and fNumLoGainSamples are set to:
//  1) If Charge Type: kAmplitude was chosen: 1.
//  2) If Charge Type: kIntegral was chosen: TMath::Floor(fRiseTime + fFallTime)
//                 or: TMath::Floor(fRiseTime + fFallTime + 1.) in the case of the low-gain
//
//  Call: SetRange(fHiGainFirst, fHiGainLast, fLoGainFirst, fLoGainLast) 
//        to modify the ranges.
// 
//        Defaults: 
//        fHiGainFirst =  2 
//        fHiGainLast  =  14
//        fLoGainFirst =  2 
//        fLoGainLast  =  14
//
//  Call: SetResolution() to define the resolution of the half-maximum search.
//        Default: 0.01
//
//  Call: SetRiseTime() and SetFallTime() to define the integration ranges 
//        for the case, the extraction type kIntegral has been chosen.
//
//  Call: - SetTimeType(MExtractTimeAndChargeSpline::kMaximum) for extraction 
//          the position of the maximum (default)
//          --> needs 22 function evaluations
//        - SetTimeType(MExtractTimeAndChargeSpline::kHalfMaximum) for extraction 
//          the position of the half maximum at the rising edge.
//          --> needs max. 34 function evaluations
//        - SetChargeType(MExtractTimeAndChargeSpline::kAmplitude) for the 
//          computation of the amplitude at the maximum (default)
//          --> no further function evaluation needed
//        - SetChargeType(MExtractTimeAndChargeSpline::kIntegral) for the 
//          computation of the integral beneith the spline between fRiseTime 
//          from the position of the maximum to fFallTime after the position of 
//          the maximum. The Low Gain is computed with one more slice at the falling
//          edge.
//          --> needs one more simple summation loop over 7 slices.
//        
//////////////////////////////////////////////////////////////////////////////
#include "MExtractTimeAndChargeSpline.h"

#include "MPedestalPix.h"

#include "MLog.h"
#include "MLogManip.h"

ClassImp(MExtractTimeAndChargeSpline);

using namespace std;

const Byte_t  MExtractTimeAndChargeSpline::fgHiGainFirst  = 2;
const Byte_t  MExtractTimeAndChargeSpline::fgHiGainLast   = 14;
const Byte_t  MExtractTimeAndChargeSpline::fgLoGainFirst  = 2;
const Byte_t  MExtractTimeAndChargeSpline::fgLoGainLast   = 14;
const Float_t MExtractTimeAndChargeSpline::fgResolution   = 0.01;
const Float_t MExtractTimeAndChargeSpline::fgRiseTime     = 1.5;
const Float_t MExtractTimeAndChargeSpline::fgFallTime     = 4.5;
// --------------------------------------------------------------------------
//
// Default constructor.
//
// Calls: 
// - SetRange(fgHiGainFirst, fgHiGainLast, fgLoGainFirst, fgLoGainLast)
// 
// Initializes:
// - fResolution    to fgResolution
// - fRiseTime      to fgRiseTime
// - fFallTime      to fgFallTime
// - Time Extraction Type to kMaximum
// - Charge Extraction Type to kAmplitude
//
MExtractTimeAndChargeSpline::MExtractTimeAndChargeSpline(const char *name, const char *title) 
    : fAbMax(0.), fAbMaxPos(0.), fHalfMax(0.)
{

  fName  = name  ? name  : "MExtractTimeAndChargeSpline";
  fTitle = title ? title : "Calculate photons arrival time using a fast spline";

  SetResolution();
  SetRiseTime();
  SetFallTime();
  
  SetRange(fgHiGainFirst, fgHiGainLast, fgLoGainFirst, fgLoGainLast);

  SetTimeType();
  SetChargeType();

}


//-------------------------------------------------------------------
//
// Set the ranges
// In order to set the fNum...Samples variables correctly for the case, 
// the integral is computed, have to overwrite this function and make an 
// explicit call to SetChargeType().
//
void MExtractTimeAndChargeSpline::SetRange(Byte_t hifirst, Byte_t hilast, Byte_t lofirst, Byte_t lolast)
{

  MExtractor::SetRange(hifirst, hilast, lofirst, lolast);

  if (IsExtractionType(kIntegral))
    SetChargeType(kIntegral);
  if (IsExtractionType(kAmplitude))
    SetChargeType(kAmplitude);
  
}


//-------------------------------------------------------------------
//
// Set the Time Extraction type. Possible are:
// - kMaximum:     Search the maximum of the spline and return its position
// - kHalfMaximum: Search the half maximum left from the maximum and return
//                 its position
//
void MExtractTimeAndChargeSpline::SetTimeType( ExtractionType_t typ )
{

  CLRBIT(fFlags,kMaximum);
  CLRBIT(fFlags,kHalfMaximum);
  SETBIT(fFlags,typ);

}

//-------------------------------------------------------------------
//
// Set the Charge Extraction type. Possible are:
// - kAmplitude: Search the value of the spline at the maximum
// - kIntegral:  Integral the spline from fHiGainFirst to fHiGainLast,   
//               by counting the edge bins only half and setting the 
//               second derivative to zero, there.
//
void MExtractTimeAndChargeSpline::SetChargeType( ExtractionType_t typ )
{

  CLRBIT(fFlags,kAmplitude);
  CLRBIT(fFlags,kIntegral );

  SETBIT(fFlags,typ);

}

// --------------------------------------------------------------------------
//
// ReInit
//
// Calls:
// - MExtractTimeAndCharge::ReInit(pList);
// - Deletes all arrays, if not NULL
// - Creates new arrays according to the extraction range
//
Bool_t MExtractTimeAndChargeSpline::ReInit(MParList *pList)
{

  if (IsExtractionType(kAmplitude))
    {
      fNumHiGainSamples = 1.;
      fNumLoGainSamples = fLoGainLast ? 1. : 0.; 
      fSqrtHiGainSamples = 1.;
      fSqrtLoGainSamples = 1.;
      fWindowSizeHiGain  = 1;
      fWindowSizeLoGain  = 1;
    }

  if (IsExtractionType(kIntegral))
    {
      fNumHiGainSamples  = fRiseTime + fFallTime;
      fNumLoGainSamples  = fLoGainLast ? fNumHiGainSamples + 1. : 0.;
      fSqrtHiGainSamples = TMath::Sqrt(fNumHiGainSamples);
      fSqrtLoGainSamples = TMath::Sqrt(fNumLoGainSamples);
      fWindowSizeHiGain  = (Int_t)(fRiseTime + fFallTime);
      fWindowSizeLoGain  = (Int_t)(fRiseTime + fFallTime+1);
    }

  if (!MExtractTimeAndCharge::ReInit(pList))
    return kFALSE;

  return kTRUE;
}

// --------------------------------------------------------------------------
//
// InitArrays
//
// Gets called in the ReInit() and initialized the arrays
//
Bool_t MExtractTimeAndChargeSpline::InitArrays()
{

  Int_t range = fHiGainLast - fHiGainFirst + 1 + fHiLoLast;

  fHiGainSignal     .Set(range);
  fHiGainFirstDeriv .Set(range);
  fHiGainSecondDeriv.Set(range);

  range = fLoGainLast - fLoGainFirst + 1;

  fLoGainSignal     .Set(range);
  fLoGainFirstDeriv .Set(range);
  fLoGainSecondDeriv.Set(range);

  fHiGainSignal     .Reset();
  fHiGainFirstDeriv .Reset();
  fHiGainSecondDeriv.Reset();

  fLoGainSignal     .Reset();
  fLoGainFirstDeriv .Reset();
  fLoGainSecondDeriv.Reset();

  return kTRUE;

}

// --------------------------------------------------------------------------
//
// Calculates the arrival time and charge for each pixel 
//
void MExtractTimeAndChargeSpline::FindTimeAndChargeHiGain(Byte_t *first, Byte_t *logain, Float_t &sum, Float_t &dsum, 
                                                          Float_t &time, Float_t &dtime, 
                                                          Byte_t &sat, const MPedestalPix &ped, const Bool_t abflag)
{
  
  Int_t range = fHiGainLast - fHiGainFirst + 1;
  const Byte_t *end = first + range;
  Byte_t       *p  = first;
  Int_t  count     = 0;

  const Float_t pedes  = ped.GetPedestal();
  const Float_t ABoffs = ped.GetPedestalABoffset();

  Float_t pedmean[2];
  pedmean[0] = pedes + ABoffs;
  pedmean[1] = pedes - ABoffs;

  fAbMax        = 0.;
  fAbMaxPos     = 0.;
  Byte_t maxpos = 0;

  //
  // Check for saturation in all other slices
  //
  while (p<end)
    {

      const Int_t ids      = fHiGainFirst + count ;
      const Float_t signal = (Float_t)*p - pedmean[(ids+abflag) & 0x1];
      fHiGainSignal[count] = signal;

      if (signal > fAbMax + 0.1) /* the 0.1 is necessary for the ultra-high enery events saturating many slices */
        {
          fAbMax = signal;
          maxpos =  p-first;
        }

      if (*p++ >= fSaturationLimit)
        sat++;
            
      count++;                                                    
    }
  
  if (fHiLoLast != 0)
    {

      end = logain + fHiLoLast;

      while (logain<end)
        {

          const Int_t ids      = fHiGainFirst + range ;
          const Float_t signal = (Float_t)*logain - pedmean[(ids+abflag) & 0x1];
          fHiGainSignal[range] = signal;
          range++;
          
          if (signal > fAbMax)
            { 
              fAbMax = signal;
              maxpos =  logain-first;
            }
          
          if (*logain >= fSaturationLimit)
            sat++;

          logain++;
        }
    }
  
  Float_t pp;

  fHiGainSecondDeriv[0] = 0.;
  fHiGainFirstDeriv[0]  = 0.;

  for (Int_t i=1;i<range-1;i++)
    {
      pp = fHiGainSecondDeriv[i-1] + 4.;
      fHiGainSecondDeriv[i] = -1.0/pp;
      fHiGainFirstDeriv [i] = fHiGainSignal[i+1] - fHiGainSignal[i] - fHiGainSignal[i] + fHiGainSignal[i-1];
      fHiGainFirstDeriv [i] = (6.0*fHiGainFirstDeriv[i]-fHiGainFirstDeriv[i-1])/pp;
    }

  fHiGainSecondDeriv[range-1] = 0.;

  for (Int_t k=range-2;k>=0;k--)
    fHiGainSecondDeriv[k] = fHiGainSecondDeriv[k]*fHiGainSecondDeriv[k+1] + fHiGainFirstDeriv[k];
  for (Int_t k=range-2;k>=0;k--)
    fHiGainSecondDeriv[k] /= 6.;
  
  if (IsNoiseCalculation() && IsExtractionType(kAmplitude))
    {
      //
      // Take the spline value at the middle of the third slice (to avoid egde effects)
      // 
      sum = 0.5*fHiGainSignal[2]
          + 0.5*fHiGainSignal[3]
          + (-0.375)*fHiGainSecondDeriv[2] 
          + (-0.375)*fHiGainSecondDeriv[3];
      return;
    }

  if (IsNoiseCalculation() && IsExtractionType(kIntegral))
    {
      //
      // Take the spline value at the middle of the third slice (to avoid egde effects)
      // 
      Int_t first = 2;
      Int_t last  = first + (Int_t)(fRiseTime+fFallTime);
      CalcIntegralHiGain(sum,first,last);
      return;
    }

  //
  // Allow no saturated slice 
  // and 
  // Don't start if the maxpos is too close to the left limit.
  //
  if ((sat || maxpos < 2))
    {
      time =  IsExtractionType(kMaximum) 
        ? (Float_t)(fHiGainFirst + maxpos) 
        : (Float_t)(fHiGainFirst + maxpos - 1);
      sum  =  IsExtractionType(kAmplitude) 
        ? fAbMax : 0.;
      return;
    }
      
  //
  // Now find the maximum  
  //
  Float_t step    = 0.2; // start with step size of 1ns and loop again with the smaller one
  Float_t lower   = (Float_t)maxpos-1.;
  Float_t upper   = (Float_t)maxpos;
  fAbMaxPos       = upper;
  Float_t x       = lower;
  Float_t y       = 0.;
  Float_t a       = 1.;
  Float_t b       = 0.;
  Int_t   klo     = maxpos-1;
  Int_t   khi     = maxpos;

  //
  // Search for the maximum, starting in interval maxpos-1 in steps of 0.2 till maxpos-0.2.
  // If no maximum is found, go to interval maxpos+1.
  //
  while ( x < upper - 0.3 )
    {

      x += step;
      a -= step;
      b += step;

      y = a*fHiGainSignal[klo]
        + b*fHiGainSignal[khi]
        + (a*a*a-a)*fHiGainSecondDeriv[klo] 
        + (b*b*b-b)*fHiGainSecondDeriv[khi];

      if (y > fAbMax)
        {
          fAbMax    = y;
          fAbMaxPos = x;
        }

      //      *fLog << err << x << "  " << y << " " << fAbMaxPos<< endl;
    }

  //
  // Search for the absolute maximum from maxpos to maxpos+1 in steps of 0.2
  //
  if (fAbMaxPos > upper-0.1)
    {

      upper   = (Float_t)maxpos+1.;
      lower   = (Float_t)maxpos;
      x       = lower;
      a       = 1.;
      b       = 0.;
      khi     = maxpos+1;
      klo     = maxpos;

      while (x<upper-0.3)
        {

          x += step;
          a -= step;
          b += step;
          
          y = a*fHiGainSignal[klo]
            + b*fHiGainSignal[khi]
            + (a*a*a-a)*fHiGainSecondDeriv[klo] 
            + (b*b*b-b)*fHiGainSecondDeriv[khi];

          if (y > fAbMax)
            {
              fAbMax    = y;
              fAbMaxPos = x;
            }
          //          *fLog << inf << x << "  " << y << " " << fAbMaxPos << endl;

        }
  }


  //
  // Now, the time, abmax and khicont and klocont are set correctly within the previous precision.
  // Try a better precision. 
  //
  const Float_t up = fAbMaxPos+step-0.035;
  const Float_t lo = fAbMaxPos-step+0.035;
  const Float_t maxpossave = fAbMaxPos;
  
  x     = fAbMaxPos;
  a     = upper - x;
  b     = x - lower;
 
  step  = 0.025; // step size of 83 ps 
 
  while (x<up)
    {

      x += step;
      a -= step;
      b += step;
      
      y = a*fHiGainSignal[klo]
        + b*fHiGainSignal[khi]
        + (a*a*a-a)*fHiGainSecondDeriv[klo] 
        + (b*b*b-b)*fHiGainSecondDeriv[khi];
      
      if (y > fAbMax)
        {
          fAbMax    = y;
          fAbMaxPos = x;
        }
      //      *fLog << inf << x << "  " << y << " " << fAbMaxPos << endl;      
    }

  //
  // Second, try from time down to time-0.2 in steps of 0.025.
  //
  x     = maxpossave;

  //
  // Test the possibility that the absolute maximum has not been found between
  // maxpos and maxpos+0.025, then we have to look between maxpos-0.025 and maxpos
  // which requires new setting of klocont and khicont
  //
  if (x < klo + 0.02)
    {
      klo--;
      khi--;
      upper--;
      lower--;
    }

  a     = upper - x;
  b     = x - lower;
  
  while (x>lo)
    {

      x -= step;
      a += step;
      b -= step;
      
      y = a*fHiGainSignal[klo]
        + b*fHiGainSignal[khi]
        + (a*a*a-a)*fHiGainSecondDeriv[klo] 
        + (b*b*b-b)*fHiGainSecondDeriv[khi];
      
      if (y > fAbMax)
        {
          fAbMax    = y;
          fAbMaxPos = x;
        }
      //      *fLog << warn << x << "  " << y << "  " << fAbMaxPos << endl;
    }

  if (IsExtractionType(kMaximum))
    {
      time = (Float_t)fHiGainFirst + fAbMaxPos;
      dtime = 0.025;
    }
  else
    {
      fHalfMax = fAbMax/2.;
      
      //
      // Now, loop from the maximum bin leftward down in order to find the position of the half maximum.
      // First, find the right FADC slice:
      // 
      klo  = maxpos - 1;
      while (klo >= 0)
        {
          if (fHiGainSignal[klo] < fHalfMax)
            break;
          klo--;
        }
      
      //
      // Loop from the beginning of the slice upwards to reach the fHalfMax:
      // With means of bisection:
      // 
      x     = (Float_t)klo;
      a     = 1.;
      b     = 0.;
      
      step = 0.5;
      Bool_t back = kFALSE;
      
      Int_t maxcnt = 50;
      Int_t cnt    = 0;

      while (TMath::Abs(y-fHalfMax) > fResolution)
        {
          
          if (back)
            {
              x -= step;
              a += step;
              b -= step;
            }
          else
            {
              x += step;
              a -= step;
              b += step;
            }
          
          y = a*fHiGainSignal[klo]
            + b*fHiGainSignal[khi]
            + (a*a*a-a)*fHiGainSecondDeriv[klo] 
            + (b*b*b-b)*fHiGainSecondDeriv[khi];
          
          if (y > fHalfMax)
            back = kTRUE;
          else
            back = kFALSE;

          if (++cnt > maxcnt)
            {
              //              *fLog << inf << x << "  " << y << " " << fHalfMax << endl;
              break;
            }
          
          step /= 2.;
        }

      time  = (Float_t)fHiGainFirst + x;
      dtime = fResolution;
    }
  
  if (IsExtractionType(kAmplitude))
    {
      sum = fAbMax;
      return;
    }

  if (IsExtractionType(kIntegral))
    {
      //
      // Now integrate the whole thing!
      // 
      Int_t startslice = (Int_t)(fAbMaxPos - fRiseTime);
      Int_t lastslice  = (Int_t)(fAbMaxPos + fFallTime);
      
      if (lastslice > range)
        {
          lastslice = range;
          startslice += (lastslice - range);
        }
      
      CalcIntegralHiGain(sum, startslice, lastslice);
    }
  
}


// --------------------------------------------------------------------------
//
// Calculates the arrival time and charge for each pixel 
//
void MExtractTimeAndChargeSpline::FindTimeAndChargeLoGain(Byte_t *first, Float_t &sum, Float_t &dsum, 
                                                          Float_t &time, Float_t &dtime, 
                                                          Byte_t &sat, const MPedestalPix &ped, const Bool_t abflag) 
{
  
  Int_t range = fLoGainLast - fLoGainFirst + 1;
  const Byte_t *end = first + range;
  Byte_t       *p  = first;
  Int_t  count     = 0;

  Float_t pedes        = ped.GetPedestal();
  const Float_t ABoffs = ped.GetPedestalABoffset();

  Float_t pedmean[2];
  pedmean[0] = pedes + ABoffs;
  pedmean[1] = pedes - ABoffs;

  fAbMax        = 0.;
  fAbMaxPos     = 0.;
  Byte_t maxpos = 0;

  //
  // Check for saturation in all other slices
  //
  while (p<end)
    {

      const Int_t ids      = fLoGainFirst + count ;
      const Float_t signal = (Float_t)*p - pedmean[(ids+abflag) & 0x1];
      fLoGainSignal[count] = signal;

      if (signal > fAbMax)
        {
          fAbMax = signal;
          maxpos =  p-first;
        }

      if (*p >= fSaturationLimit)
        sat++;
            
      p++;
      count++;                                                    
    }
  
  Float_t pp;

  fLoGainSecondDeriv[0] = 0.;
  fLoGainFirstDeriv[0]  = 0.;

  for (Int_t i=1;i<range-1;i++)
    {
      pp = fLoGainSecondDeriv[i-1] + 4.;
      fLoGainSecondDeriv[i] = -1.0/pp;
      fLoGainFirstDeriv [i] = fLoGainSignal[i+1] - fLoGainSignal[i] - fLoGainSignal[i] + fLoGainSignal[i-1];
      fLoGainFirstDeriv [i] = (6.0*fLoGainFirstDeriv[i]-fLoGainFirstDeriv[i-1])/pp;
    }

  fLoGainSecondDeriv[range-1] = 0.;
  for (Int_t k=range-2;k>=0;k--)
    fLoGainSecondDeriv[k] = fLoGainSecondDeriv[k]*fLoGainSecondDeriv[k+1] + fLoGainFirstDeriv[k];
  for (Int_t k=range-2;k>=0;k--)
    fLoGainSecondDeriv[k] /= 6.;
  
  if (IsNoiseCalculation() && IsExtractionType(kAmplitude))
    {
      //
      // Take the spline value at the middle of the third slice (to avoid egde effects)
      // 
      sum = 0.5*fLoGainSignal[2]
          + 0.5*fLoGainSignal[3]
          + (-0.375)*fLoGainSecondDeriv[2] 
          + (-0.375)*fLoGainSecondDeriv[3];
      return;
    }

  if (IsNoiseCalculation() && IsExtractionType(kIntegral))
    {
      //
      // Take the spline value at the middle of the third slice (to avoid egde effects)
      // 
      Int_t first = 2;
      Int_t last  = first + (Int_t)(fRiseTime+fFallTime);
      CalcIntegralLoGain(sum,first,last);
      return;
    }

  //
  // Allow no saturated slice 
  // and 
  // Don't start if the maxpos is too close to the left limit.
  //
  if (sat || maxpos < 1)
    {
      time =  IsExtractionType(kMaximum) 
        ? (Float_t)(fLoGainFirst + maxpos) 
        : (Float_t)(fLoGainFirst + maxpos - 1);
      return;
    }
      
  if (maxpos < 2 && IsExtractionType(kHalfMaximum))
    {
      time = (Float_t)(fLoGainFirst + maxpos - 1);
      return;
    }

  //
  // Now find the maximum  
  //
  Float_t step    = 0.2; // start with step size of 1ns and loop again with the smaller one
  Float_t lower   = (Float_t)maxpos-1.;
  Float_t upper   = (Float_t)maxpos;
  fAbMaxPos       = upper;
  Float_t x       = lower;
  Float_t y       = 0.;
  Float_t a       = 1.;
  Float_t b       = 0.;
  Int_t   klo     = maxpos-1;
  Int_t   khi     = maxpos;

  //
  // Search for the maximum, starting in interval maxpos-1 in steps of 0.2 till maxpos-0.2.
  // If no maximum is found, go to interval maxpos+1.
  //
  while ( x < upper - 0.3 )
    {

      x += step;
      a -= step;
      b += step;

      y = a*fLoGainSignal[klo]
        + b*fLoGainSignal[khi]
        + (a*a*a-a)*fLoGainSecondDeriv[klo] 
        + (b*b*b-b)*fLoGainSecondDeriv[khi];

      if (y > fAbMax)
        {
          fAbMax    = y;
          fAbMaxPos = x;
        }

      //      *fLog << err << x << "  " << y << " " << fAbMaxPos<< endl;
    }

  //
  // Test the possibility that the absolute maximum has not been found before the 
  // maxpos and search from maxpos to maxpos+1 in steps of 0.2
  //
  if (fAbMaxPos > upper-0.1)
    {

      upper   = (Float_t)maxpos+1.;
      lower   = (Float_t)maxpos;
      x       = lower;
      a       = 1.;
      b       = 0.;
      khi     = maxpos+1;
      klo     = maxpos;

      while (x<upper-0.3)
        {

          x += step;
          a -= step;
          b += step;
          
          y = a*fLoGainSignal[klo]
            + b*fLoGainSignal[khi]
            + (a*a*a-a)*fLoGainSecondDeriv[klo] 
            + (b*b*b-b)*fLoGainSecondDeriv[khi];

          if (y > fAbMax)
            {
              fAbMax    = y;
              fAbMaxPos = x;
            }
          //          *fLog << inf << x << "  " << y << " " << fAbMaxPos << endl;

        }
  }


  //
  // Now, the time, abmax and khicont and klocont are set correctly within the previous precision.
  // Try a better precision. 
  //
  const Float_t up = fAbMaxPos+step-0.035;
  const Float_t lo = fAbMaxPos-step+0.035;
  const Float_t maxpossave = fAbMaxPos;
  
  x     = fAbMaxPos;
  a     = upper - x;
  b     = x - lower;
 
  step  = 0.025; // step size of 83 ps 
 
  while (x<up)
    {

      x += step;
      a -= step;
      b += step;
      
      y = a*fLoGainSignal[klo]
        + b*fLoGainSignal[khi]
        + (a*a*a-a)*fLoGainSecondDeriv[klo] 
        + (b*b*b-b)*fLoGainSecondDeriv[khi];
      
      if (y > fAbMax)
        {
          fAbMax    = y;
          fAbMaxPos = x;
        }
      //      *fLog << inf << x << "  " << y << " " << fAbMaxPos << endl;      
    }

  //
  // Second, try from time down to time-0.2 in steps of 0.025.
  //
  x     = maxpossave;

  //
  // Test the possibility that the absolute maximum has not been found between
  // maxpos and maxpos+0.02, then we have to look between maxpos-0.02 and maxpos
  // which requires new setting of klocont and khicont
  //
  if (x < klo + 0.02)
    {
      klo--;
      khi--;
      upper--;
      lower--;
    }

  a     = upper - x;
  b     = x - lower;
  
  while (x>lo)
    {

      x -= step;
      a += step;
      b -= step;
      
      y = a*fLoGainSignal[klo]
        + b*fLoGainSignal[khi]
        + (a*a*a-a)*fLoGainSecondDeriv[klo] 
        + (b*b*b-b)*fLoGainSecondDeriv[khi];
      
      if (y > fAbMax)
        {
          fAbMax    = y;
          fAbMaxPos = x;
        }
      //      *fLog << warn << x << "  " << y << "  " << fAbMaxPos << endl;
    }

  if (IsExtractionType(kMaximum))
    {
      time = (Float_t)fLoGainFirst + fAbMaxPos;
      dtime = 0.02;
    }
  else
    {
      fHalfMax = fAbMax/2.;
      
      //
      // Now, loop from the maximum bin leftward down in order to find the position of the half maximum.
      // First, find the right FADC slice:
      // 
      klo  = maxpos - 1;
      while (klo >= 0)
        {
          if (fLoGainSignal[klo] < fHalfMax)
            break;
          klo--;
        }
      
      //
      // Loop from the beginning of the slice upwards to reach the fHalfMax:
      // With means of bisection:
      // 
      x     = (Float_t)klo;
      a     = 1.;
      b     = 0.;
      
      step = 0.5;
      Bool_t back = kFALSE;
      
      Int_t maxcnt = 50;
      Int_t cnt    = 0;

      while (TMath::Abs(y-fHalfMax) > fResolution)
        {
          
          if (back)
            {
              x -= step;
              a += step;
              b -= step;
            }
          else
            {
              x += step;
              a -= step;
              b += step;
            }
          
          y = a*fLoGainSignal[klo]
            + b*fLoGainSignal[khi]
            + (a*a*a-a)*fLoGainSecondDeriv[klo] 
            + (b*b*b-b)*fLoGainSecondDeriv[khi];
          
          if (y > fHalfMax)
            back = kTRUE;
          else
            back = kFALSE;

          if (++cnt > maxcnt)
            {
              //              *fLog << inf << x << "  " << y << " " << fHalfMax << endl;
              break;
            }
          
          step /= 2.;
        }

      time  = (Float_t)fLoGainFirst + x;
      dtime = fResolution;
    }
  
  if (IsExtractionType(kAmplitude))
    {
      sum = fAbMax;
      return;
    }

  if (IsExtractionType(kIntegral))
    {
      //
      // Now integrate the whole thing!
      // 
      Int_t startslice = (Int_t)(fAbMaxPos - fRiseTime);
      Int_t lastslice  = (Int_t)(fAbMaxPos + fFallTime + 1);
      
      if (lastslice > range)
        {
          lastslice = range;
          startslice += (lastslice - range);
        }
      CalcIntegralLoGain(sum, startslice, lastslice);
    }
}

void MExtractTimeAndChargeSpline::CalcIntegralHiGain(Float_t &sum, Int_t startslice, Int_t lastslice)
{

  if (startslice < 0)
    {
      lastslice -= startslice;
      startslice = 0;
    }
  
  Int_t i = startslice;
  sum = 0.5*fHiGainSignal[i];
  
  //
  // We sum 1.5 times the second deriv. coefficients because these had been 
  // divided by 6. already. Usually, 0.25*fHiGainSecondDeriv should be added.
  //
  for (i=startslice+1; i<lastslice; i++)
    sum += fHiGainSignal[i] + 1.5*fHiGainSecondDeriv[i];
  
  sum += 0.5*fHiGainSignal[lastslice];

}

void MExtractTimeAndChargeSpline::CalcIntegralLoGain(Float_t &sum, Int_t startslice, Int_t lastslice)
{

  if (startslice < 0)
    {
      lastslice -= startslice;
      startslice = 0;
    }
  
  Int_t i = startslice;
  sum = 0.5*fLoGainSignal[i];
  
  //
  // We sum 1.5 times the second deriv. coefficients because these had been 
  // divided by 6. already. Usually, 0.25*fLoGainSecondDeriv should be added.
  //
  for (i=startslice+1; i<lastslice; i++)
    sum += fLoGainSignal[i] + 1.5*fLoGainSecondDeriv[i];
  
  sum += 0.5*fLoGainSignal[lastslice];

}



// --------------------------------------------------------------------------
//
// In addition to the resources of the base-class MExtractor:
//   MJPedestal.MExtractor.WindowSizeHiGain: 6
//   MJPedestal.MExtractor.WindowSizeLoGain: 6
//
Int_t MExtractTimeAndChargeSpline::ReadEnv(const TEnv &env, TString prefix, Bool_t print)
{

  Bool_t rc = kFALSE;
  
  if (IsEnvDefined(env, prefix, "Resolution", print))
    {
      SetResolution(GetEnvValue(env, prefix, "Resolution",fResolution));
      rc  = kTRUE;
    }
  if (IsEnvDefined(env, prefix, "RiseTime", print))
    {
      SetRiseTime(GetEnvValue(env, prefix, "RiseTime", fRiseTime));
      rc = kTRUE;
    }
  if (IsEnvDefined(env, prefix, "FallTime", print))
    {
      SetFallTime(GetEnvValue(env, prefix, "FallTime", fFallTime));
      rc = kTRUE;
    }
  
  Bool_t b = kFALSE;

  if (IsEnvDefined(env, prefix, "Amplitude", print))
    {
      b = GetEnvValue(env, prefix, "Amplitude", IsExtractionType(kAmplitude));
      if (b) 
        SetChargeType(kAmplitude);
      rc = kTRUE;
    }
  if (IsEnvDefined(env, prefix, "Integral", print))
    {
      b = GetEnvValue(env, prefix, "Integral", IsExtractionType(kIntegral));
      if (b) 
        SetChargeType(kIntegral);
      rc = kTRUE;
    }
  if (IsEnvDefined(env, prefix, "Maximum", print))
    {
      b = GetEnvValue(env, prefix, "Maximum", IsExtractionType(kMaximum));
      if (b) 
        SetTimeType(kMaximum);
      rc = kTRUE;
    }
  if (IsEnvDefined(env, prefix, "HalfMaximum", print))
    {
      b = GetEnvValue(env, prefix, "HalfMaximum", IsExtractionType(kHalfMaximum));
      if (b) 
        SetTimeType(kHalfMaximum);
      rc = kTRUE;
    }

  return MExtractTimeAndCharge::ReadEnv(env, prefix, print) ? kTRUE : rc;

}


