#ifndef CONCATENATE_H
#define CONCATENATE_H

#include <type_traits>
#include <utility>

template <typename IT1, typename IT2>
class ConcatenatedIterator {
   public:
      using value_type = typename IT1::value_type;
      using reference = typename IT1::reference;

      friend void swap(ConcatenatedIterator& lhs, ConcatenatedIterator& rhs) {
	 using std::swap;
	 swap(lhs.is_end, rhs.is_end);
	 swap(lhs.begin1, rhs.begin1);
	 swap(lhs.end1, rhs.end1);
	 swap(lhs.begin2, rhs.begin2);
	 swap(lhs.end2, rhs.end2);
      }

      ConcatenatedIterator() : is_end(true) {
      }
      ConcatenatedIterator(IT1 begin1, IT1 end1, IT2 begin2, IT2 end2) :
	    is_end(false),
	    begin1(begin1), end1(end1), begin2(begin2), end2(end2) {
      }
      ConcatenatedIterator(const ConcatenatedIterator& other) :
	    is_end(other.is_end),
	    begin1(other.begin1), end1(other.end1),
	    begin2(other.begin2), end2(other.end2) {
      }
      ConcatenatedIterator(ConcatenatedIterator&& other) :
	    ConcatenatedIterator() {
	 swap(*this, other);
      }
      ConcatenatedIterator& operator=(ConcatenatedIterator other) {
	 swap(*this, other);
	 return *this;
      }
      
      reference operator*() const {
	 if (begin1 != end1) {
	    return *begin1;
	 } else {
	    return *begin2;
	 }
      }
      ConcatenatedIterator& operator++() {
	 if (!is_end) {
	    if (begin1 != end1) {
	       ++begin1;
	    } else if (begin2 != end2) {
	       ++begin2;
	    }
	    if (begin1 == end1 && begin2 == end2) is_end = true;
	 }
	 return *this;
      }
      bool operator==(const ConcatenatedIterator& other) const {
	 if (is_end && other.is_end) return true;
	 if (is_end != other.is_end) return false;
	 if (begin1 != end1 && other.begin1 != other.end1) {
	    return begin1 == other.begin1;
	 }
	 if (begin1 != end1 || other.begin1 != other.end1) return false;
	 if (begin2 != end2 && other.begin2 != other.end2) {
	    return begin2 == other.begin2;
	 }
	 return false;
      }
      bool operator!=(const ConcatenatedIterator& other) const {
	 return !(*this == other);
      }
   private:
      bool is_end;
      IT1 begin1; IT1 end1;
      IT2 begin2; IT2 end2;
};

template <typename C1, typename C2>
class ConcatenatedContainerView {
   public:
      using iterator = ConcatenatedIterator<
	 typename C1::const_iterator, typename C2::const_iterator>;
      using const_iterator = iterator;
      using value_type = typename C1::value_type;
      ConcatenatedContainerView(const C1& c1, const C2& c2) :
	    it(c1.begin(), c1.end(), c2.begin(), c2.end()) {
      }
      iterator begin() const {
	 return it;
      }
      iterator end() const {
	 return iterator();
      }
   private:
      const iterator it;
};

template <typename C1, typename C2>
using ConcatenationResult = typename std::enable_if<
   // check that both containers have the same element type
   std::is_same<
      decltype(*std::declval<const C1&>().begin()),
      decltype(*std::declval<const C2&>().begin())
   >::value,
   // check that C1 and C2 support iterators
   typename std::remove_reference<
      decltype(
	 std::declval<const C1&>().begin(),
	 std::declval<const C1&>().end(),
	 std::declval<const C2&>().begin(),
	 std::declval<const C2&>().end(),
	 std::declval<ConcatenatedContainerView<C1, C2>>()
      )
   >::type
>::type;

template <typename C1, typename C2>
ConcatenationResult<C1, C2>
concatenate(const C1& c1, const C2& c2) {
   return ConcatenatedContainerView<C1, C2>(c1, c2);
}

template <typename C1, typename C2>
ConcatenationResult<C1, C2>
operator&(const C1& c1, const C2& c2) {
   return concatenate(c1, c2);
}

#endif