#ifndef __JTIMESLICEROUTER__
#define __JTIMESLICEROUTER__

#include <vector>
#include <iterator>
#include <utility>
#include <limits>
#include <algorithm>

#include "JTools/JRouter.hh"
#include "JTools/JElement.hh"
#include "JTools/JGridBounds.hh"
#include "JTools/JGrid.hh"
#include "JDAQ/JDAQ.hh"
#include "JDAQ/JDAQModuleIdentifier.hh"
#include "JDAQ/JDAQSuperFrame.hh"
#include "JDAQ/JDAQTimeslice.hh"
#include "JDetector/JTimeRange.hh"
#include "JTrigger/JTriggerException.hh"


namespace JTRIGGER {

  namespace {
    using KM3NETDAQ::JDAQModuleIdentifier;
    using KM3NETDAQ::JDAQFrameSubset;
    using KM3NETDAQ::JDAQSuperFrame;
    using KM3NETDAQ::JDAQTimeslice;
    using KM3NETDAQ::getTimeSinceRTS;
    using KM3NETDAQ::getFrameTime;
    using JTOOLS::JRouter;
    using JTOOLS::JElement2D;
    using JTOOLS::JGrid;
    using JTOOLS::JGridBounds;
    using JTOOLS::make_grid_bounds;
    using JSIRENE::JTimeRange;
  }


  /**
   * Router for fast addressing of hits in JDAQTimeslice data structure
   * as a function of the optical module identifier and time.
   * Note that the data in a frame from the same PMT are time ordered 
   * but the data from different PMTs may be mixed.
   *
   * The time slice router class comprises two internal look-up tables:
   *
   * - The first table consists of a one dimensional look-up table in which
   *   the value of the element at position i corresponds to the position of 
   *   the frame in the time slice for which the module identifier is equal
   *   to i.
   *
   * - The second table consists of a two dimensional array.
   *   Each element in this array consists of a one dimensional look-up table.
   *   The index of the look-up table matches with the index of 
   *   the corresponding frame in the time slice.
   *   The look-up table consists of an array of values (x,lpos,rpos), where:
   *     1) lpos is the index of the first hit with time > x;
   *     2) rpos is the index of the last  hit with time < x;
   */
  class JTimesliceRouter
  {
    struct pair {
      int lpos;
      int rpos;
    };

    typedef JDAQTimeslice::const_iterator      const_iterator;
    typedef JElement2D<double, pair>           JElement_t;
    typedef JGrid<JElement_t>                  JGrid_t;

  public:

    /**
     * Constructor.
     *
     * \param  input           timeslice
     * \param  numberOfBins    number of bins
     */
    JTimesliceRouter(const JDAQTimeslice& input,
		     const int numberOfBins) :
      timeslice(input),
      router(),
      table()
    {
      using namespace std;

      for (const_iterator super_frame = timeslice.begin(); super_frame != timeslice.end(); ++super_frame)
	router.put(super_frame->getModuleID(), distance(timeslice.begin(), super_frame));

      const JDAQHit::JTDC_t TMIN = std::numeric_limits<JDAQHit::JTDC_t>::min();
      const JDAQHit::JTDC_t TMAX = std::numeric_limits<JDAQHit::JTDC_t>::max();

      double Tmin = getTimeSinceRTS(timeslice.getFrameIndex());    // [ns]
      double Tmax = Tmin + getFrameTime();                         // [ns]

      Tmin -= 0.05 * getFrameTime();
      Tmax += 0.05 * getFrameTime();

      if (Tmin < TMIN) Tmin = TMIN;
      if (Tmax > TMAX) Tmax = TMAX;

      int number_of_bins = 0;

      for (const_iterator super_frame = timeslice.begin(); super_frame != timeslice.end(); ++super_frame) {
	if (super_frame->size() > number_of_bins)
	  number_of_bins = super_frame->size();
      }

      if (number_of_bins > numberOfBins)
	number_of_bins = numberOfBins;

      if (number_of_bins < 2)
	number_of_bins = 2;

      const JGridBounds<double> bounds(make_grid_bounds(number_of_bins, Tmin, Tmax));


      // temporary buffer to store bin edges with proper data type

      typedef vector<JDAQHit::JTDC_t> JBuffer_t;

      JBuffer_t buffer(bounds.getNumberOfKeys() + 1);

      for (unsigned int i = 0; i != bounds.getNumberOfKeys(); ++i)
	buffer[i] = (JDAQHit::JTDC_t) bounds.getKey(i);

      buffer[bounds.getNumberOfKeys()] = numeric_limits<JDAQHit::JTDC_t>::max();


      table.resize(timeslice.size());      

      typedef vector<JDAQHit> JDAQFrame_t;

      JDAQFrame_t zbuf;                                                       // copy of data with begin and end marker

      const JDAQHit beginMarker(JDAQHit::JPMT_t(0), TMIN, JDAQHit::JTOT_t(0));
      const JDAQHit endMarker  (JDAQHit::JPMT_t(0), TMAX, JDAQHit::JTOT_t(0));

      vector<JGrid_t>::iterator grid = table.begin();

      for (const_iterator super_frame = timeslice.begin(); super_frame != timeslice.end(); ++super_frame, ++grid) {

	grid->configure(bounds);

	if (!super_frame->empty()) {

	  if (super_frame-> begin()->getT() < grid->getLowerKey())
	    throw JTriggerException("Hit time out of range (lower limit).");

	  if (super_frame->rbegin()->getT() > grid->getUpperKey())
	    throw JTriggerException("Hit time out of range (upper limit).");

	  const unsigned int N = super_frame->size() + 2;

	  zbuf.resize(N);

	  copy(super_frame->begin(), super_frame->end(), zbuf.begin() + 1);

	  *zbuf. begin() = beginMarker;
	  *zbuf.rbegin() = endMarker;

	  {
	    JDAQFrame_t::const_iterator hit = zbuf.begin(); ++hit;            // skip begin marker
	    JBuffer_t  ::const_iterator t1  = buffer.begin();

	    for (JGrid_t::iterator i = grid->begin(); i != grid->end(); ++i, ++t1) {
	    
	      while (hit->getT() < *t1)
		++hit;
	      
	      i->getValue().lpos = distance(static_cast<const JDAQFrame_t&>(zbuf).begin(),hit) - 1;
	    }
	  }

	  {
	    JDAQFrame_t::const_reverse_iterator hit = zbuf.rbegin(); ++hit;   // skip end marker
	    JBuffer_t  ::const_reverse_iterator t1  = buffer.rbegin();

	    for (JGrid_t::reverse_iterator i = grid->rbegin(); i != grid->rend(); ++i, ++t1) {
		
	      while (hit->getT() >= *t1)
		++hit;
	      
	      i->getValue().rpos = distance(static_cast<const JDAQFrame_t&>(zbuf).begin(),hit.base()) - 1;
	    }
	  }
	}
      }
    }


    const_iterator begin() const { return timeslice.begin(); }
    const_iterator end()   const { return timeslice.end(); }

    size_t size() const { return timeslice.size(); }

    bool empty() const { return timeslice.empty(); }
    

    /**
     * Get address of module.
     *
     * \param  module          module
     * \return                 address
     */
    const int getAddress(const JDAQModuleIdentifier& module) const
    {
      return router.get(module.getModuleID());
    }
    

    /**
     * Get super frame.
     *
     * \param  module          module
     * \return                 super frame
     */
    const JDAQSuperFrame& getSuperFrame(const JDAQModuleIdentifier& module) const
    {
      return timeslice[getAddress(module)];
    }
    

    /**
     * Has super frame.
     *
     * \param  module          module
     * \return                 true if module present; else false
     */
    bool hasSuperFrame(const JDAQModuleIdentifier& module) const
    {
      return router.has(module.getModuleID());
    }


    /**
     * Get subset of frame given module identifier and range of hit times.
     *
     * Note that the hit times should have been corrected for the maximal and minimal 
     * time offsets of the PMTs in the corresponding module.
     *
     * \param  module          module
     * \param  timeRange       time range [ns]
     * \return                 begin and end iterators
     */
    JDAQFrameSubset getFrameSubset(const JDAQModuleIdentifier& module, const JTimeRange& timeRange) const
    {
      const int address = getAddress(module);

      const JGrid_t&        grid  = table    [address];
      const JDAQSuperFrame& frame = timeslice[address];

      const int lpos = grid.getIndex(timeRange.getLowerLimit());
      const int rpos = grid.getIndex(timeRange.getUpperLimit());

      return frame.subset(grid[lpos].lpos, grid[rpos].rpos);
    }

  private:
    const JDAQTimeslice& timeslice;
    JRouter<int>         router;
    std::vector<JGrid_t> table;
  };
}

#endif