#ifndef __ANTARESDAQ__TIMESTAMP__
#define __ANTARESDAQ__TIMESTAMP__

#include <utility>
#include <iterator>


/**
 * Auxiliary class to remove bit-flipped ARS data.
 *
 * The input data are reshuffeld such that the pair container contains:
 *   -  begin of correct output data
 *   -  end   of correct output data
 *
 * This class provides for the usual STL interface methods.
 */
template<class T>
class Timestamp :
  public std::pair<T,T> {
public:

  typedef T    const_iterator;
  
  
  /**
   * Constructor.
   *
   * \param  __begin    begin of input data
   * \param  __end      end   of input data
   */
  Timestamp(T __begin, T __end) :
    std::pair<T,T>(__begin, __end)
  {
    if (__begin != __end) {

      const_iterator p0 = __begin;
      const_iterator p1 = p0;

      ++p1;

      /*
       *  assure following start conditions
       *
       *  1.  p0 /= 0
       *  2.  p1 >  p0
       */
      while (p1 != __end && (p0->timestamp == 0 || p1->timestamp < p0->timestamp)) {
        ++p0;
        ++p1;
      }

      if (p1 != __end) {

        this->first  = p0;
	/*
	 *  assume following start conditions
	 *
	 *  1.  p0 /= 0
	 *  2.  p1 >  p0
	 */
        for (const_iterator p2 = p1; ++p2 != __end; ) {


         if (p2->timestamp > p1->timestamp) {
	   /*
            *        p2
            *       /
            *      p1
            *     /
            *    p0
	    */
            *(++p0) = *p1;
            *(++p1) = *p2;

          } else {

            if (p2->timestamp < p0->timestamp) {
	      /*
	       *        p1
	       *       /  \
	       *      /    \
	       *     p0     \
	       *             p2
	       *
	       */
            } else {
	      /*
	       *        p1
	       *       /  \
	       *      /    p2
	       *     /
	       *    p0
	       */
              *p1 = *p2;
            }
          }
        }

        this->second = ++p1;

      } else {

        this->first  = p0;
        this->second = p1;
      }
    }
  }

  const_iterator begin() const { return this->first; }  
  const_iterator end()   const { return this->second; }  

  size_t size()  const { return std::distance(this->begin(), this->end()); } 
  bool   empty() const { return this->begin() == this->end(); } 
};

#endif