#ifndef function_input_iterator_H
#define function_input_iterator_H

#include <boost/iterator/iterator_facade.hpp>
#include <iterator>
#include <boost/type_traits.hpp>

namespace boost {
  template<typename FUNC>
  struct CACHED {
    typedef typename boost::remove_reference<FUNC>::type::result_type result_type;

    result_type operator() () {
      if (!cacheValid) {
	cache = f();
	cacheValid = true;
      }

      return cache;
    }

    void operator++ () { cache = f(); cacheValid = true; }

    CACHED (FUNC _f) : f (_f), cacheValid (false) {}

    FUNC f;
    bool cacheValid;
    result_type cache;
  };


  template<typename FUNC>
  class function_input_iterator : public boost::iterator_facade<
    function_input_iterator<FUNC>,
    typename boost::remove_reference<FUNC>::type::result_type,
    boost::forward_traversal_tag,
    typename boost::remove_reference<FUNC>::type::result_type
    >
  {
  public:
    typedef typename boost::iterator_facade<
    function_input_iterator<FUNC>,
    typename boost::remove_reference<FUNC>::type::result_type,
    boost::forward_traversal_tag,
    typename boost::remove_reference<FUNC>::type::result_type> super_t;

    typedef typename super_t::difference_type difference_type;
    typedef typename super_t::reference reference;
    typedef typename super_t::value_type value_type;

    explicit function_input_iterator() {}

    explicit function_input_iterator (FUNC _f, int _cnt=0) :
      f (_f), cnt (_cnt) {}

  private:
    friend class boost::iterator_core_access;
  

    void increment () {
      ++f;
      ++cnt;
    }

    void advance (difference_type n) {
      assert (n >= 0);
      for (int i = 0; i < n; i++) 
	increment();
    }

    difference_type
    distance_to (function_input_iterator<FUNC> const& y) const {
      return -(cnt - y.cnt);
    }

    bool equal (function_input_iterator<FUNC> const& y) const {
      return distance_to (y) == 0;
    }

    reference dereference() const { return f(); }

  private:

    mutable CACHED<FUNC> f;
    int cnt;
  };

  template<typename FUNC>
  function_input_iterator<FUNC> make_function_input_iterator(FUNC f, int cnt=0) {
    return function_input_iterator<FUNC> (f, cnt);
  }

} //namespace boost

#endif