#pragma once 

#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/concept_check.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/or.hpp>
#include <boost/type_traits.hpp>
#include <boost/static_assert.hpp>
#include <iterator>

namespace LibFundament {

  template <class _OuterIterator>
  class flat_iterator;

  namespace Details {

    /// @brief Derive the inner iterator type based on the outer iterator type
    /// @details The outer iterators value type is required to model STL Container concept.
    /// The inner iterator type is chosen based on const-qualification of the outer iterators
    /// reference type.
    template<class _OuterIterator>
    struct derive_inner_iterator_type {
      typedef typename std::iterator_traits<_OuterIterator>::reference outer_reference_type;
      typedef typename std::iterator_traits<_OuterIterator>::value_type outer_value_type;

      /// The value-type of the outer iterator must model a STL container concept.
      BOOST_CONCEPT_ASSERT((boost::Container<outer_value_type>));

      typedef typename boost::mpl::if_<
        boost::is_const< typename boost::remove_reference<outer_reference_type >::type >,
        typename outer_value_type::const_iterator,
        typename outer_value_type::iterator
      >::type type;
    };
     
    /// @brief Derive the value type of the adopted iterator.
    /// @details Const-qualification is added to the value type of the inner iterator 
    /// if either the outer iterators or inner iterators reference is const-qualified.
    template<class _OuterIterator, class _InnerIterator>
    struct derive_value_type {
      typedef typename std::iterator_traits<_OuterIterator>::reference outer_reference_type;
      typedef typename std::iterator_traits<_InnerIterator>::reference inner_reference_type;
      typedef typename std::iterator_traits<_InnerIterator>::value_type inner_value_type;

      typedef typename boost::mpl::if_<
        boost::mpl::or_< 
          boost::is_const< typename boost::remove_reference<outer_reference_type >::type >,
          boost::is_const< typename boost::remove_reference<inner_reference_type >::type >
        >,
        typename boost::add_const<inner_value_type>::type,
        inner_value_type
      >::type type;
    };

    /// @brief Derive traversal category based on inner and outer iterator traversal categories.
    /// @details Inner and outer iterators have to provide at least forward traversal. If both, 
    /// outer and inner, iterators provide bidirectional traversal the resulting
    /// traversal category is bidirectional. If either outer or inner iterator model provide
    /// forward traversal the resulting traversal category is forward only.
    template<class _OuterIterator, class _InnerIterator>
    struct derive_iterator_traversal_category {
      typedef typename boost::iterator_traversal<_OuterIterator>::type outer_trav_category;
      typedef typename boost::iterator_traversal<_InnerIterator>::type inner_trav_category;
    private:
      // If your compiler traps here either outer or inner iterator type does not model forward iterator.
      BOOST_STATIC_ASSERT((
        boost::is_convertible<outer_trav_category, boost::forward_traversal_tag>::value &&
        boost::is_convertible<inner_trav_category, boost::forward_traversal_tag>::value));
    public:
     
      typedef typename boost::mpl::if_<
        boost::mpl::and_<
          boost::is_convertible<outer_trav_category, boost::bidirectional_traversal_tag>,
          boost::is_convertible<inner_trav_category, boost::bidirectional_traversal_tag>
        >,
        boost::bidirectional_traversal_tag,
        boost::forward_traversal_tag
      >::type type;
    };

    /// @brief Base class for iterating nested containers.
    template<class _OuterIterator>
    struct flat_iterator_base {
      typedef _OuterIterator outer_iterator;
      typedef typename derive_inner_iterator_type<_OuterIterator>::type inner_iterator;

      typedef boost::iterator_adaptor<
        flat_iterator<_OuterIterator>,               // Derived
        _OuterIterator,                              // Adopted Iterator
        typename derive_value_type<                  // Value type
          _OuterIterator, 
          inner_iterator
        >::type,
        typename derive_iterator_traversal_category< // Iterator category
          _OuterIterator,
          inner_iterator
        >::type
      > type;
    };
  }

  template<class _OuterIterator>
  class flat_iterator : public Details::flat_iterator_base<_OuterIterator>::type
  {
  private:
    typedef typename Details::flat_iterator_base<_OuterIterator>::type super_type;
    typedef typename Details::flat_iterator_base<_OuterIterator>::outer_iterator outer_iterator;
    typedef typename Details::flat_iterator_base<_OuterIterator>::inner_iterator inner_iterator;
    struct enabler {};

  public:
    /// @brief Empty constructor
    flat_iterator() {}

    /// @brief Construct from outer iterator and outer iterator end
    flat_iterator(_OuterIterator outer, _OuterIterator outer_end = _OuterIterator())
      :super_type(outer), _outer_end(outer_end) 
    {
      if (outer != outer_end) {
        if (outer->empty()) {
          forward_outer_inner();
        } else {
          _inner = outer->begin();
        }
      }
    }

    /// @brief Copy construct from other iterator
    template<class _OtherIterator>
    flat_iterator(
      flat_iterator<_OtherIterator> const &other,
      typename boost::enable_if<
        boost::is_convertible<_OtherIterator, _OuterIterator>, 
        enabler
      >::type = enabler()
    )
      : super_type(other.base()), _outer_end(other._outer_end), _inner(other._inner) {}

    inner_iterator inner() const {
      return _inner;
    }

  private:
    friend class boost::iterator_core_access;

    
    /// @brief Compare for equality
    template<class _OtherIterator>
    bool equal(flat_iterator<_OtherIterator> const& other) const
    {
      bool same_outer = this->base() == other.base();
      if (!this->outer_end_reached() && !other.outer_end_reached()) {
        return same_outer && _inner == other._inner;
      }
      return same_outer;
    }

    /// @brief Increment iterator
    /// @details Increments the inner iterator if possible. If the inner iterator reached inner end,
    /// the outer iterator is moved forward until the next non-empty container is found or outer end
    /// is reached.
    void increment() { 
      if (!this->outer_end_reached() && !this->increment_inner()) {
        this->forward_outer_inner();
      }
    }

    /// @brief Decrement iterator
    /// @details Decrements the inner iterator if possible. If the outer iterator reached outer end
    /// or the inner iterator reached the current containers begin iterator then the outer iterator is
    /// moved backward until the next non-empty container is found. The inner iterator is updated to
    /// point to the last element of the container.
    void decrement() {
      if (this->outer_end_reached() || !this->decrement_inner()) {
        this->backward_outer();
      }
    }

    /// @brief Test if outer iteator reached meets the outer end iterator.
    inline bool outer_end_reached() const {
      return (this->base() == _outer_end);
    }

    /// @brief Increment inner iterator if possible
    /// @pre _outer != _outer_end
    /// @return true if inner iterator points to a valid element after incrementation, false otherwise
    inline bool increment_inner() {
      inner_iterator inner_end = this->base()->end();
      return (_inner != inner_end && ++_inner != inner_end);
    }

    /// @brief Decrement inner iterator if possible
    /// @pre _outer != _outer_end
    /// @return true if decrementing inner iterator succeeded, false otherwise
    inline bool decrement_inner() {
      bool success = false;
      inner_iterator inner_begin = this->base()->begin();
      if (_inner != inner_begin) {
        --_inner;
        success = true;
      }
      return success;
    }

    /// @brief Forward outer iterator to next non-empty leaf
    /// @pre this->base() != _outer_end
    inline void forward_outer_inner(){
      while (++(this->base_reference()) != _outer_end && this->base()->empty()) {}
      if (this->base() != _outer_end) {
        _inner = this->base()->begin();
      }
    }

    /// @brief Backward outer iterator to previous non-empty leaf
    inline void backward_outer() {
      while ((--this->base_reference())->empty()) {}
      _inner = --(this->base_reference()->end());
    }

    typename super_type::reference dereference() const {
      return *_inner;
    }

    outer_iterator _outer_end;
    inner_iterator _inner;
  };

  template<class _OuterIterator>
  typename flat_iterator<_OuterIterator> 
    make_flat_iterator(_OuterIterator outer, _OuterIterator outer_end) 
  {
    return flat_iterator<_OuterIterator>(outer, outer_end);
  }


}