#ifndef hVYFXl0fhRtHkuIHnrxmZOhDCeI
#define hVYFXl0fhRtHkuIHnrxmZOhDCeI

#include <assert.h>

#include <string>

#include "time.hpp"
#include "checkpoint.hpp"
#include "simlimits.hpp"
#include "template_helpers.hpp"
#include "vector.hpp"

// TODO: update r/w-barriers in vector

using std::string;

template<typename Quant>
struct Index;

template<typename Ptr>
struct CommonIndex {
  CommonIndex() = delete;
  CommonIndex(const string name, Ptr max);

  // type and const defs
  typedef Ptr ptr_t;
  static constexpr ptr_t nil() {
    BOOST_STATIC_ASSERT(( (ptr_t) -1 > 0 ));
    return -1;
  }

  // read operations
  //   HINT: time refers to creation time, not delievery time; the
  //         later is handled by Filter<>
  inline ptr_t last();                // returns the latest known event
  ptr_t last(Time t);                 // ... before (or at) time t
  inline ptr_t first(); // ... after (or at) ...
  ptr_t first(Time t);

  ptr_t binarySearch(Time t);

  virtual void sync() { 
    time.barrierRead() = time.barrierWrite();
    time.sync();
  }
  
  // vector storing timing
  Vector<Time> time;

  // writing
  inline ptr_t add(Time t);
};

template<typename Ptr>
inline typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::last() {
  // get ptr from any barrier (all should be the same!)
  ptr_t id = time.barrierWrite.get();
  if (id==0)
    return nil();
  else
    return id - 1;
}

template<typename Ptr>
inline typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::first() {
  // get ptr from any barrier (all should be the same!)
  ptr_t id = time.barrierWrite.get();
  if (id==0)
    return nil();
  else
    return 0;
}

template<typename Ptr>
CommonIndex<Ptr>::CommonIndex(const string name, ptr_t max) : 
  time(name, max)
{}

template<typename Ptr>
typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::last(Time t) {
  ptr_t cur = binarySearch(t);
  if ((cur == nil()) or (time(cur) > t))
    return nil();

  // there may be several elements with time = t; go to the last one
  while ((cur < last()) && (time(cur + 1) == t))
    cur++;

  return cur;
}

template<typename Ptr>
typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::first(Time t) {
  ptr_t cur = binarySearch(t);

  if (cur == nil())
    return nil();
  if ((time(cur) < t) && (cur < last()))
      cur = cur + 1;
  if (time(cur) < t)
    return nil();
    

  // there may be several elements with time = t; go to the first one
  while ((cur > first()) && (time(cur - 1) == t))
    cur--;
  return cur;
}

template<typename Ptr>
typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::binarySearch(Time t) {
  // TODO (optimize): use a constant frequency approximation to
  // initialize min, max and pivot (w/ proper fallback)

  // get the limits of the heap
  ptr_t max = last();
  if (max == nil()) return nil(); // no elements, yet
  ptr_t min = first();

  // check if t \in [min, max]
  if (t > time(max)) return max;
  if (t < time(min)) return min;

  // binary search in the heap
  // invariant: min <= target <= max
  while ((time(min) != time(max))) {
    ptr_t pivot = (min + max + 1) / 2;
    if (t >= time(pivot)) {
      min = pivot;
    }else{
      max = pivot - 1;
    }
  }

  return max; // min would be ok, too
}

template<typename Ptr>
inline typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::add(Time aTime) {
  ptr_t id = last() + 1;         // get position to write
  time.set(id, aTime);           // add new record
  time.barrierWrite.set(id + 1); // increase write barrier

  return id;
  }

#endif // hVYFXl0fhRtHkuIHnrxmZOhDCeI