#ifndef SEQUENCE_H
#define SEQUENCE_H

#include <cstddef>
#include <utility>
#include <iterator>

namespace e2 {
namespace lib {

//substitute for std::lexicographical_compare
template<class I1, class I2>
bool lexicographical_compare_x(I1 first1, I1 last1, I2 first2, I2 last2) {
	for (; first1!=last1 && first2!=last2; ++first1, ++first2) {
		if (*first1 < *first2) return true;
		if (*first2 < *first1) return false;
	}
	return first1==last1 && first2!=last2;
}

//The default template arguments produce a linear sequence using this:
template<class T>
class linear {
public:
	linear() : n_(1) {}
	linear(T n) : n_(n) {}
	T operator()(T current) const {return current+n_; }
	bool operator==(const linear& other) const {return n_==other.n_; }
	template<class X>
	bool operator==(const X&) const {return false; }
private:
	const T n_;
};

//Some helper template classes:
template<class D, class T> const D& transparent(const T& value) {return value; }
template<class T1, class T2> const T1& first(const std::pair<T1,T2>& value) {return value.first; }
template<class T1, class T2> const T2& second(const std::pair<T1,T2>& value) {return value.second; }

//The sequence container:
// use as sequence<type, generator, deref_type, deref_func>, where
//  type: the typedef "contained". defaults to int.
//  generator: the function that generates the next value. defaults to linear.
//  deref_type: the typedef when an iterator is dereferenced. defaults to "type".
//  deref_func: the function to obtain the deferenced value.
// See usage notes at end of file.
template<class T=int, class F=linear<T>, class D=T, const D& (&DF)(const T&)=transparent<D,T> >
class sequence {
public:
	typedef T value_type;
	typedef T& reference;
	typedef const T& const_reference;
	typedef size_t difference_type;
	typedef size_t size_type;
	typedef const D& (&DF_type)(const T&);
	//friend class iterator;
	class const_iterator : public std::iterator<std::input_iterator_tag, T, size_type, T*, T&> {
		friend class sequence;
	public:
		typedef D value_type;
		typedef size_t difference_type;
		typedef size_t size_type;
		//initialisation
		const_iterator() : value_(), functor_(), count_() {}
		const_iterator(const const_iterator& other) : value_(other.value_), functor_(other.functor_), count_(other.count_) {}
		~const_iterator() {};

		//overloads
		const_iterator& operator=(const const_iterator& other) {value_=other.value_; functor_=other.functor_, count_=other.count_; }
		const_iterator& operator++() {value_=functor_(value_); ++count_; return *this; }
		const_iterator operator++(int) {const_iterator old=*this; ++*this; return old; }
		difference_type operator-(const const_iterator& other) {return count_-other.count_; }
		bool operator==(const const_iterator& other) const {return count_==other.count_&&functor_==other.functor_; }
		bool operator!=(const const_iterator& other) const {return !operator==(other); }
		const D& operator*() const {DF_type df=DF; return df(value_); }
		const D* operator->() const {return &DF(value_); }
		
		//methods
		bool converged() const {return functor_.converged(); }
		size_type iterations() const {return count_; }
	protected:
		const_iterator(T start, F functor, size_type count) : value_(start), functor_(functor), count_(count) {}
		T value_;
		F functor_;
		size_type count_;
	};
	class iterator : public const_iterator {
		friend class sequence;
	public:
		typedef T value_type;
		//initialisation
		iterator() : const_iterator() {};
		iterator(const iterator& other) : const_iterator(other.value_, other.functor_, other.count_) {}
		iterator(const const_iterator& other) : const_iterator(other.value_, other.functor_, other.count_) {}
		~iterator() {}

		const T& operator*() const {return value_; }
		const T* operator->() const {return &value_; }
	protected:
		iterator(T start, F functor, size_type count) : const_iterator(start, functor, count) {}
	};

	//initialisation
	sequence() : start_(), size_(0), functor_() {}
	sequence(T start) : start_(start), size_(0), functor_() {}
	sequence(T start, size_type size) : start_(start), size_(size), functor_() {}
	template<class FInit>
	sequence(T start, FInit func_init, size_type size) : start_(start), size_(size), functor_(func_init) {}
	sequence(sequence& other) : start_(other.start_), size_(other.size_), functor_(other.functor_) {}
	~sequence() {}

	//overloads
	sequence& operator=(const sequence& other) {start_=other.start_; size_=other.size_; functor_=other.functor_; }
	bool operator==(const sequence& other) const {return start_==other.start_&&size_==other.size_&&functor_==other.functor_; }
	template<class C>
	bool operator==(const C& other) const {
		if (size_!=other.size()) {
			return false; 
		}
		return equal(begin(), end(), other.begin());
	}
	template<class C>
	bool operator!=(const C& other) const {return !operator==(other); }
	template<class C>
	bool operator<(const C& other) const {return lexicographical_compare_x(begin(), end(), other.begin(), other.end()); }
	template<class C>
	bool operator>(const C& other) const {return lexicographical_compare_x(other.begin(), other.end(), begin(), end()); }
	template<class C>
	bool operator<=(const C& other) const {return !operator>(other); }
	template<class C>
	bool operator>=(const C& other) const {return !operator<(other); }

	//iterators
	iterator begin() {return iterator(start_, functor_, size_type(0)); }
	const_iterator begin() const {return const_iterator(start_, functor_, size_type(0)); }
	const iterator end() {return iterator(start_, functor_, size_); }
	const const_iterator end() const {return iterator(start_, functor_, size_); }

	//methods
	T front() const {return start_; }
	size_type size() const {return size_; }
	size_type max_size() const {return size_; }
	bool empty() const {return size_==0; }
	void set_size(size_type size) {size_=size; }
	//void swap(sequence& other) {swap(start_, other.start_); std::swap(size_, other.size_); swap(functor_, other.functor_); }

private:
	T start_;
	size_type size_;
	F functor_;
};

template<class C, class T, class F, class D, const D& (&DF)(const T&)>
bool operator==(const C& other, const sequence<T,F,D,DF>& seq) {return seq.operator==(other); }

template<class C, class T, class F, class D, const D& (&DF)(const T&)>
bool operator!=(const C& other, const sequence<T,F,D,DF>& seq) {return !seq.operator==(other); }

template<class C, class T, class F, class D, const D& (&DF)(const T&)>
bool operator<(const C& other, const sequence<T,F,D,DF>& seq) {return seq.operator>(other); }

template<class C, class T, class F, class D, const D& (&DF)(const T&)>
bool operator>(const C& other, const sequence<T,F,D,DF>& seq) {return seq.operator<(other); }

template<class C, class T, class F, class D, const D& (&DF)(const T&)>
bool operator<=(const C& other, const sequence<T,F,D,DF>& seq) {return !seq.operator<(other); }

template<class C, class T, class F, class D, const D& (&DF)(const T&)>
bool operator>=(const C& other, const sequence<T,F,D,DF>& seq) {return !seq.operator>(other); }

}//namespace lib
}//namespace e2

/* USAGE NOTES:

Basic Usage:

	sequence<type, generator> counter(start, size);

Initialises a sequence of "size" values of type "type", starting at "start", with the next value calculated by calling generator.

e.g. sequence<> counter();

Initialises a sequence of int starting at 0, incrementing by 1.

e.g. sequence<long, linear<long,2> > evens(2, 10);

Initialises a sequence of long starting at 2, incrementing by 2, for a count of 10 values.

e.g. Populate a vector with even numbers from 2 to 20:

vector<int> my_vect;
copy(evens.begin(), evens.end(), my_vect.back_inserter());

See the test harness for examples of sequence generator functions.

Advance Usage:

For sequences where the next number cannot simply be calculated from the current, the type
contained and the type dereferenced will be different. For example, to generate squares,
the "internal" value would increment by 1 but the dereferenced value would be the square
of this, or for square roots, the incrementing value could be int but the returned root
a double.

	sequence<type, generator, deref_type, deref_func> counter(start, size);
	
e.g sequence<pair<int, double>, sqrt, double, pair<int, double>::second> sqroots(make_pair(0,0));

#endif