#ifndef DataFormats_Common_ValueMap_h
#define DataFormats_Common_ValueMap_h
/* \class ValueMap<T>
 *
 * \author Luca Lista, INFN
 *
 *
 */

#include "DataFormats/Common/interface/CMS_CLASS_VERSION.h"
#include "DataFormats/Provenance/interface/ProductID.h"
#include "FWCore/Utilities/interface/EDMException.h"
#include <vector>
#include <map>
#include <iterator>
#include <algorithm>
#include <cstddef>

namespace edm {
  namespace helper {
    template <typename Map>
    class Filler {
    private:
      typedef std::vector<size_t> index_vector;
      typedef std::vector<typename Map::value_type> value_vector;
      typedef std::map<ProductID, value_vector> value_map;
      typedef typename Map::offset offset;
      typedef typename Map::id_offset_vector id_offset_vector;

    public:
      explicit Filler(Map& map) : map_(map), totSize_(0) { add(map); }
      void add(const Map& map) {
        if (map.empty())
          return;
        typename id_offset_vector::const_iterator j = map.ids_.begin();
        const typename id_offset_vector::const_iterator end = map.ids_.end();
        size_t i = 0;
        const size_t size = map.values_.size();
        // std::pair<ProductID, offset> id = *j;
        do {
          ProductID id = j->first;
          ++j;
          size_t max = (j == end ? size : j->second);
          typename value_map::iterator f = values_.find(id);
          if (f != values_.end())
            throwAdd();
          value_vector& values = values_.insert(std::make_pair(id, value_vector())).first->second;
          while (i != max)
            values.push_back(map.values_[i++]);
        } while (j != end);
      }
      template <typename H, typename I>
      void insert(const H& h, I begin, I end) {
        ProductID id = h.id();
        size_t size = h->size(), sizeIt = end - begin;
        if (sizeIt != size)
          throwFillSize();
        typename value_map::const_iterator f = values_.find(id);
        if (f != values_.end())
          throwFillID(id);
        value_vector& values = values_.insert(make_pair(id, value_vector(size))).first->second;
        std::copy(begin, end, values.begin());
        totSize_ += size;
      }
      void fill() {
        map_.clear();
        offset off = 0;
        map_.ids_.reserve(values_.size());
        map_.values_.reserve(totSize_);
        for (typename value_map::const_iterator i = values_.begin(); i != values_.end(); ++i) {
          ProductID id = i->first;
          map_.ids_.push_back(std::make_pair(id, off));
          const value_vector& values = i->second;
          for (typename value_vector::const_iterator j = values.begin(); j != values.end(); ++j) {
            map_.values_.push_back(*j);
            ++off;
          }
        }
        map_.shrink_to_fit();
      }

    protected:
      Map& map_;

    private:
      value_map values_;
      size_t totSize_;

      void throwFillSize() const {
        Exception::throwThis(errors::InvalidReference,
                             "ValueMap::Filler: handle and reference "
                             "collections should the same size\n");
      }
      void throwFillID(ProductID id) const {
        Exception e(errors::InvalidReference);
        e << "index map has already been filled for id: " << id << "\n";
        e.raise();
      }
      void throwAdd() const {
        Exception::throwThis(errors::InvalidReference,
                             "ValueMap: trying to add entries for an already existing product\n");
      }
    };
  }  // namespace helper

  template <typename T>
  class ValueMap {
  public:
    typedef T value_type;
    typedef std::vector<value_type> container;
    typedef unsigned int offset;
    typedef std::vector<std::pair<ProductID, offset> > id_offset_vector;
    typedef typename container::reference reference_type;
    typedef typename container::const_reference const_reference_type;

    ValueMap() {}

    void swap(ValueMap& other) {
      values_.swap(other.values_);
      ids_.swap(other.ids_);
    }

    template <typename RefKey>
    const_reference_type operator[](const RefKey& r) const {
      return get(r.id(), r.key());
    }
    // raw index of a given (id,key) pair
    size_t rawIndexOf(ProductID id, size_t idx) const {
      typename id_offset_vector::const_iterator f = getIdOffset(id);
      if (f == ids_.end())
        throwNotExisting();
      offset off = f->second;
      size_t j = off + idx;
      if (j >= values_.size())
        throwIndexBound();
      return j;
    }
    const_reference_type get(ProductID id, size_t idx) const { return values_[rawIndexOf(id, idx)]; }
    template <typename RefKey>
    reference_type operator[](const RefKey& r) {
      return get(r.id(), r.key());
    }
    reference_type get(ProductID id, size_t idx) { return values_[rawIndexOf(id, idx)]; }

    ValueMap<T>& operator+=(const ValueMap<T>& o) {
      add(o);
      return *this;
    }
    bool contains(ProductID id) const { return getIdOffset(id) != ids_.end(); }
    size_t size() const { return values_.size(); }
    size_t idSize() const { return ids_.size(); }
    bool empty() const { return values_.empty(); }
    void clear() {
      values_.clear();
      ids_.clear();
    }
    void shrink_to_fit() {
      ids_.shrink_to_fit();
      values_.shrink_to_fit();
    }

    typedef helper::Filler<ValueMap<T> > Filler;

    struct const_iterator {
      typedef ptrdiff_t difference_type;
      const_iterator() : values_(nullptr) {}
      ProductID id() const { return i_->first; }
      typename container::const_iterator begin() const { return values_->begin() + i_->second; }
      typename container::const_iterator end() const {
        if (i_ == end_)
          return values_->end();
        id_offset_vector::const_iterator end = i_;
        ++end;
        if (end == end_)
          return values_->end();
        return values_->begin() + end->second;
      }
      size_t size() const { return end() - begin(); }
      const T& operator[](size_t i) { return *(begin() + i); }
      const_iterator& operator++() {
        ++i_;
        return *this;
      }
      const_iterator operator++(int) {
        const_iterator ci = *this;
        ++i_;
        return ci;
      }
      const_iterator& operator--() {
        --i_;
        return *this;
      }
      const_iterator operator--(int) {
        const_iterator ci = *this;
        --i_;
        return ci;
      }
      difference_type operator-(const const_iterator& o) const { return i_ - o.i_; }
      const_iterator operator+(difference_type n) const { return const_iterator(i_ + n, end_, values_); }
      const_iterator operator-(difference_type n) const { return const_iterator(i_ - n, end_, values_); }
      bool operator<(const const_iterator& o) const { return i_ < o.i_; }
      bool operator==(const const_iterator& ci) const { return i_ == ci.i_; }
      bool operator!=(const const_iterator& ci) const { return i_ != ci.i_; }
      const_iterator& operator+=(difference_type d) {
        i_ += d;
        return *this;
      }
      const_iterator& operator-=(difference_type d) {
        i_ -= d;
        return *this;
      }

    private:
      const_iterator(const id_offset_vector::const_iterator& i_,
                     const id_offset_vector::const_iterator& end,
                     const container* values)
          : values_(values), i_(i_), end_(end) {}
      const container* values_;
      id_offset_vector::const_iterator i_, end_;
      friend class ValueMap<T>;
    };

    const_iterator begin() const { return const_iterator(ids_.begin(), ids_.end(), &values_); }
    const_iterator end() const { return const_iterator(ids_.end(), ids_.end(), &values_); }

    /// meant to be used in AssociativeIterator, not by the ordinary user
    const id_offset_vector& ids() const { return ids_; }
    /// meant to be used in AssociativeIterator, not by the ordinary user
    const_reference_type get(size_t idx) const { return values_[idx]; }

    //Used by ROOT storage
    CMS_CLASS_VERSION(10)

  protected:
    container values_;
    id_offset_vector ids_;

    typename id_offset_vector::const_iterator getIdOffset(ProductID id) const {
      typename id_offset_vector::const_iterator i = std::lower_bound(ids_.begin(), ids_.end(), id, IDComparator());
      if (i == ids_.end())
        return i;
      return i->first == id ? i : ids_.end();
    }

    void throwIndexBound() const {
      Exception::throwThis(errors::InvalidReference, "ValueMap: index out of upper boundary\n");
    }

  private:
    struct IDComparator {
      bool operator()(const std::pair<ProductID, offset>& p, const ProductID& id) { return p.first < id; }
    };
    void throwNotExisting() const {
      Exception::throwThis(errors::InvalidReference, "ValueMap: no associated value for given product and index\n");
    }

    void add(const ValueMap<T>& o) {
      Filler filler(*this);
      filler.add(o);
      filler.fill();
    }

    friend class helper::Filler<ValueMap<T> >;
  };

  template <typename T>
  inline ValueMap<T> operator+(const ValueMap<T>& a1, const ValueMap<T>& a2) {
    ValueMap<T> a = a1;
    a += a2;
    return a;
  }

  // Free swap function
  template <typename T>
  inline void swap(ValueMap<T>& lhs, ValueMap<T>& rhs) {
    lhs.swap(rhs);
  }

}  // namespace edm
#endif