#include <iterator>
#include <algorithm>
#include <tuple>
#include <functional>

using std::size_t;

template <typename TypeA, typename... Types>
class ZipIterator : public std::iterator<std::random_access_iterator_tag, std::tuple<decltype(*TypeA::begin()), decltype(*Types::begin())...>> {
public:
  typedef decltype(TypeA::begin()) TypeAit;
  typedef std::tuple<TypeAit, decltype(Types::begin())...> ItT;
  typedef std::tuple<decltype(*TypeA::begin()), decltype(*Types::begin())...> DataT;
  typedef std::tuple<TypeA*, Types*...> ContainerT;

  ZipIterator(TypeA first, Types... rest) :
      m_index(0) {
    if (sizeof...(rest) != 0) {
      ZipIterator leftover(rest...);
      m_its = std::tuple_cat(std::tuple<TypeAit>(first.begin()), leftover.m_its);
      m_containers = std::tuple<TypeA*, Types*...>(first.begin(), leftover.m_containers);
    } else {
      m_its = std::tuple<TypeAit>(first.begin());
      m_containers = std::tuple<TypeA*>(first.begin());
    }
  }

  ZipIterator(ZipIterator const& rhs) {
    copy(rhs);
  }

  inline ZipIterator& operator=(ZipIterator const& rhs) {
    copy(rhs);
  }
  
  inline ZipIterator& operator+=(int steps) const {
    additionImpl(m_its, steps);
    return *this;
  }

  inline ZipIterator& operator-=(int steps) const {
    subtractionImpl(m_its, steps);
    return *this;
  }

  inline DataT operator*() const {
    return construct(m_its);
  }

  inline DataT* operator->() const {
    return &construct(m_its);
  }

  inline DataT operator[](int rhs) const {
    return constructAt(rhs);
  }

  inline ZipIterator& operator++() {
    incrementImpl(m_its);
    return *this;
  }

  inline ZipIterator& operator--() {
    decrementImpl(m_its);
    return *this;
  }

  inline ZipIterator operator++(int) {
    ZipIterator tmp(*this);
    ++this;
    return tmp;
  }

  inline ZipIterator operator--(int) {
    ZipIterator tmp(*this);
    --this;
    return tmp;
  }

  inline ZipIterator operator+(int steps) const {
    ZipIterator copy(*this);
    copy.additionImpl(copy.m_its, steps);
    return copy;
  }

  inline ZipIterator operator-(int steps) const {
    ZipIterator copy(*this);
    copy.subtractionImpl(copy.m_its, steps);
    return copy;
  }

  inline int operator-(ZipIterator const& rhs) {
    return std::get<0>(m_its) - std::get<0>(rhs.m_its);
  }

  friend inline ZipIterator operator+(int lhs, ZipIterator const& rhs) {
    return rhs + lhs;
  }

  friend inline ZipIterator operator-(int lhs, ZipIterator const& rhs) {
    return rhs - lhs;
  }

  inline bool operator==(ZipIterator const& rhs) const {
    if (valid() || rhs.valid())
      return m_its == rhs.m_its;
    return true;
  }

  inline bool operator!=(ZipIterator const& rhs) const {
    return !(*this == rhs);
  }

  inline bool operator<(ZipIterator const& rhs) const {
    return m_its < rhs.m_its;
  }

  inline bool operator<=(ZipIterator const& rhs) const {
    return (*this == rhs) || (*this < rhs);
  }

  inline bool operator>=(ZipIterator const& rhs) const {
    return !(*this < rhs);
  }

  inline bool operator>(ZipIterator const& rhs) const {
    return !(*this <= rhs);
  }

  inline ZipIterator begin() const {
    ZipIterator copy(*this);
    copy.m_its = beginImpl(copy);
    return copy;
  }

  inline ZipIterator end() const {
    ZipIterator copy(*this);
    copy.m_its = endImpl(copy);
    return copy;
  }

private:
  inline void copy(ZipIterator const& copy) {
    m_its = copy.m_its;
    m_containers = copy.m_containers;
    m_index = copy.m_index;
  }

  //Begin

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I == sizeof...(Tp)), DataT>::type
  beginImpl(std::tuple<Tp...> const& its) {
    return std::tuple<>();
  }

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I < sizeof...(Tp)), DataT>::type
  beginImpl(std::tuple<Tp...> const& its) {
    return std::tuple_cat(
             std::tuple<decltype(*std::get<I>(its))>(
               std::get<I>(m_containers).begin();
             ),
             constructImpl<I + 1>(its)
           );
  }
 
  //End

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I == sizeof...(Tp)), DataT>::type
  endImpl(std::tuple<Tp...> const& its) {
    return std::tuple<>();
  }

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I < sizeof...(Tp)), DataT>::type
  endImpl(std::tuple<Tp...> const& its) {
    return std::tuple_cat(
             std::tuple<decltype(*std::get<I>(its))>(
               std::get<I>(m_containers).end();
             ),
             constructImpl<I + 1>(its)
           );
  }

  //Increment

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I == sizeof...(Tp)), void>::type
  incrementImpl(std::tuple<Tp...> const& its) { }

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I < sizeof...(Tp)), void>::type
  incrementImpl(std::tuple<Tp...> const& its) {
    ++(std::get<I>(its));
    incrementImpl<I + 1>(its);
  }

  //Decrement

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I == sizeof...(Tp)), void>::type
  decrementImpl(std::tuple<Tp...> const& its) { }

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I < sizeof...(Tp)), void>::type
  decrementImpl(std::tuple<Tp...> const& its) {
    --(std::get<I>(its));
    decrementImpl<I + 1>(its);
  }
  
  //Addition

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I == sizeof...(Tp)), void>::type
  additionImpl(std::tuple<Tp...> const& its, int steps) { }

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I < sizeof...(Tp)), void>::type
  additionImpl(std::tuple<Tp...> const& its, int steps) {
    std::get<I>(its) + steps;
    incrementImpl<I + 1>(its);
  }

  //Subtraction

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I == sizeof...(Tp)), void>::type
  subtractionImpl(std::tuple<Tp...> const& its, int steps) { }

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I < sizeof...(Tp)), void>::type
  subtractionImpl(std::tuple<Tp...> const& its, int steps) {
    std::get<I>(its) + steps;
    decrementImpl<I + 1>(its);
  }

  //Construct

  template<size_t I = 0, typename... Tp>
  inline auto constructImpl(std::tuple<Tp...> const& its) ->
  typename std::enable_if<(I == sizeof...(Tp)), typename std::tuple<decltype(*Tp)...>>::type {
    return std::tuple<>();
  }

  template<size_t I = 0, typename... Tp>
  inline auto constructImpl(std::tuple<Tp...> const& its) ->
  typename std::enable_if<(I < sizeof...(Tp)), typename std::tuple<decltype(*Tp)...>>::type {
    return std::tuple_cat(
             std::tuple<decltype(*std::get<I>(its))>(
               *std::get<I>(its)
             ),
             constructImpl<I + 1>(its)
           );
  }

  inline DataT construct() {
    if (valid()) {
      return constructImpl(m_its);
    }
    throw StarAlgorithm("Attempted to construct zipped tuple beyond end.");
  }

  //ConstructAt

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I == sizeof...(Tp)), typename std::tuple<decltype(*Tp)...>>::type
  constructAtImpl(std::tuple<Tp...> const& its, size_t index) {
    return std::tuple<>();
  }

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I < sizeof...(Tp)), typename std::tuple<decltype(*Tp)...>>::type
  constructImpl(std::tuple<Tp...> const& its, size_t index) {
    return std::tuple_cat(
             std::tuple<decltype(*std::get<I>(its))>(
               std::get<I>(its)[index]
             ),
             constructAtImpl<I + 1>(its, index)
           );
  }

  inline DataT constructAt(size_t index) {
    if (validAt(index)) {
      constructAtImpl(m_its, index);
    }
    throw StarAlgorithm("Attempting to construct zipped tuple beyond end.");
  }

  //Valid

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I == sizeof...(Tp)), bool>::type
  validImpl(std::tuple<Tp...> const& its) {
    return true;
  }

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I < sizeof...(Tp)), bool>::type
  validImpl(std::tuple<Tp...> const& its) {
    return std::get<I>(its) != std::get<I>(m_containers).end() &&
           validImpl<I + 1>(its);
  }

  inline bool valid() {
    validImpl(m_its);
  }

  //ValidAt

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<(I == sizeof...(Tp)), bool>::type
  validAtImpl(std::tuple<Tp...> const& its, size_t index) {
    return true;
  }

  template<size_t I = 0, typename... Tp>
  inline typename std::enable_if<I < sizeof...(Tp), bool>::type
  validAtImpl(std::tuple<Tp...> const& its, size_t index) {
    try {
      std::get<I>(its)[index];
    } catch (AlgorithmException const& e) {
      return false;
    }
    return validAtImpl<I + 1>(its, index);
  }

  inline bool validAt(size_t index) {
    validAtImpl(m_its, index);
  }

  ItT m_its;
  ContainerT m_containers;
};