#ifndef x9xBGzwmK2Ew29hQ89VsJgDlY3M
#define x9xBGzwmK2Ew29hQ89VsJgDlY3M

#include <boost/tuple/tuple.hpp>

#include "checkpoint.hpp"
#include "index.hpp"
#include "quant_types.hpp"

template<typename Ptr>
struct CommonSpikeIndex : CommonIndex<Ptr> {
  // type- and constdefs
  typedef Neuron::instance_ptr_t neuron_ptr_t;

  // lift stuff from CommonIndex
  typedef typename CommonIndex<Ptr>::ptr_t ptr_t;
  using CommonIndex<Ptr>::nil;
  using CommonIndex<Ptr>::first;
  using CommonIndex<Ptr>::last;
  using CommonIndex<Ptr>::time;
  //  using CommonIndex<Ptr>::nil;

  CommonSpikeIndex(string qname);

  // read operations
  ptr_t last(Time t, neuron_ptr_t n); // ... of neuron n
  ptr_t first(Time t, neuron_ptr_t n);

  // write operations
  template<typename SrcQuant>
  inline ptr_t add(Time time, Time eventTime /* ignored */, SrcQuant src);

  virtual void sync();

  // vectors storing topological information
  Vector<neuron_ptr_t::ptr_t> src;
  Vector<ptr_t> prev, next; // address of the previous and next spike
			    // of the same sender neuron

  // checkpoint to store the last known spike of every neuron (to
  // implement adding a spike in a fast way)
  Checkpoint<ptr_t, maxNeurons> prevCache;
};

template<typename Ptr>
CommonSpikeIndex<Ptr>::CommonSpikeIndex(string qname) :
  CommonIndex<Ptr>("index_" + qname + "_time", maxSpikes),
  src("index_" + qname + "_src", maxSpikes),
  prev("index_" + qname + "_prev", maxSpikes),
  next("index_" + qname + "_next", maxSpikes),
  prevCache("index_" + qname + "_checkpoint_prev", this->nil())
{ }

template<typename Ptr>
typename CommonSpikeIndex<Ptr>::ptr_t CommonSpikeIndex<Ptr>::last(Time t, neuron_ptr_t n) {
  // TODO (optimize): improve the alg to use prevCache as seed for
  // proper min/max values

  // get the last element before (at) time t
  ptr_t id = last(t);
  if (id == nil()) return nil(); // no spikes at all

  // get the last known spike of neuron
  Time lookup = fmin(prevCache.timeLimit(), t());
  ptr_t lst = prevCache.getValue(lookup, n());
  if (lst == nil()) return nil(); // n didn't fire at all
  if (lst < id) return lst; // no l' with time(lst) < time(lst') <= t may exist

  // do a linear search until a spike of n is found
  while (src(id) != n()) {
    id--;
  }

  return id;
}

template<typename Ptr>
typename CommonSpikeIndex<Ptr>::ptr_t CommonSpikeIndex<Ptr>::first(Time t, neuron_ptr_t n) {
  // TODO (optimize): improve the alg to use prevCache as seed for
  // proper min/max values

  // get the first element after (at) time t
  ptr_t id = first(t);
  if (id == nil()) return nil(); // no spikes at all

  // get the first known spike of neuron
  ptr_t lst;
  Time lookup = (t + prevCache.interval())();
  do {
    lookup = fmin(prevCache.timeLimit(), lookup());
    lst = prevCache.getValue(lookup, n());
    lookup += prevCache.interval();
  } while (lst == nil() && lookup < prevCache.timeLimit());
  if ((lst < id) || (lst == nil())) return nil(); // no spike of n after t exists

  // do a linear search until a spike of n is found
  while (src(id) != n()) {
    id++;
  }

  return id;
}

template<typename Ptr> template<typename AddPtr>
typename CommonSpikeIndex<Ptr>::ptr_t CommonSpikeIndex<Ptr>::add(Time aTime, Time,
							AddPtr rawSrc) {
  // cast to neuron ptr (only correct type for call)
  if (!boost::is_same<AddPtr, neuron_ptr_t>::value) DO_NOT_CALL;
  neuron_ptr_t &aSrc(FORCE_CONV(neuron_ptr_t, rawSrc));

  // check if all barriers are equal
  assert(time.barrierWrite() == src.barrierWrite());
  assert(time.barrierWrite() == prev.barrierWrite());
  assert(time.barrierWrite() == next.barrierWrite());

  // get position to write
  ptr_t id = last();
  if (last() == nil()) {
    id = 0;
  }else{
    id += 1;
  }
  
  // add new record
  time(id) = aTime;
  src(id) = aSrc();
  prev(id) = prevCache.getValue(aTime, aSrc());
  if (prevCache.getValue(aTime, aSrc()) != nil())
    next(prevCache.getValue(aTime, aSrc())) = id;
  next(id) = nil();
  prevCache.set(aTime, aSrc(), id);

  // increase all write barriers
  time.barrierWrite() = id + 1;
  src.barrierWrite() = id + 1;
  prev.barrierWrite() = id + 1;
  next.barrierWrite() = id + 1;

  return id;
}

template<typename Ptr>
void CommonSpikeIndex<Ptr>::sync() {
  CommonIndex<Ptr>::sync();
  src.sync();
  prev.sync();
  next.sync();
  prevCache.sync();
}

#endif // x9xBGzwmK2Ew29hQ89V