#ifndef __ITERATOR_AMV
	#define __ITERATOR_AMV

#include <cstddef>

namespace amv	{

//tipos de iteradores
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag: public input_iterator_tag {};
struct bidirectional_iterator_tag: public forward_iterator_tag {};
struct random_access_iterator_tag: public bidirectional_iterator_tag  {};

//base para iteradores
template <class Cat, class type, class Dist=ptrdiff_t, class Ptr=type *, class Ref=type &>
struct iterator	{
	typedef Cat iterator_category;
	typedef type value_type;
	typedef Dist difference_type;
	typedef Ptr pointer;
	typedef Ref reference;
};

//las siguientes derivaciones se hacen para evitar el error de compilación C2504
//de tal manera que no debemos derivar directamente de iterator, sino de uno de los siguientes
template <class type, class Dist=ptrdiff_t, class Ptr=type *, class Ref=type &>
class InIt: public iterator<input_iterator_tag,type,Dist,Ptr,Ref>	{
};

template <class type, class Dist=ptrdiff_t, class Ptr=type *, class Ref=type &>
class OutIt: public iterator<output_iterator_tag,type,Dist,Ptr,Ref>	{
};

template <class type, class Dist=ptrdiff_t, class Ptr=type *, class Ref=type &>
class ForIt: public iterator<forward_iterator_tag,type,Dist,Ptr,Ref>	{
};

template <class type, class Dist=ptrdiff_t, class Ptr=type *, class Ref=type &>
class BidIt: public iterator<bidirectional_iterator_tag,type,Dist,Ptr,Ref>	{
};

template <class type, class Dist=ptrdiff_t, class Ptr=type *, class Ref=type &>
class RanIt: public iterator<random_access_iterator_tag,type,Dist,Ptr,Ref>	{
};

//rasgos de iteradores
template <class it>
struct iterator_traits	{
	typedef typename it::iterator_category iterator_category;
	typedef typename it::value_type value_type;
	typedef typename it::difference_type difference_type;
	typedef typename it::pointer pointer;
	typedef typename it::reference reference;
};

//en lugar de la especialización parcial para apuntadores, que no es soportada
//por este compilador, sólo hasta la versión 7.1 de VC++ .net
template <class type>
struct iterator_traits_pointer	{
	typedef random_access_iterator_tag iterator_category;
	typedef type value_type;
	typedef ptrdiff_t difference_type;
	typedef type * pointer;
	typedef type & reference;
};

//iterador inverso
template <class It>
class reverse_iterator: public iterator<iterator_traits<It>::iterator_category,
iterator_traits<It>::value_type, iterator_traits<It>::difference_type,
iterator_traits<It>::pointer, iterator_traits<It>::reference>	{
	protected:
		It I;
	public:
		typedef It iterator_type;

		reverse_iterator(const It newIterator=It()):
		I(newIterator)
			{
			}
		template <class It1>
		reverse_iterator(const reverse_iterator<It1> &rit):
		I(rit.realbase())
			{
			}
		It base() const
			{
			It temp(I);
			return --temp;
			}
		It realbase() const
			{
			return I;
			}
		reference operator *() const
			{
			It temp(I);
			return *--temp;
			}
		pointer operator ->() const
			{
			return &**this;
			}
		reverse_iterator &operator ++()
			{
			--I;
			return *this;
			}
		reverse_iterator operator ++(int i)
			{
			reverse_iterator temp(*this);
			--I;
			return temp;
			}
		reverse_iterator &operator --()
			{
			++I;
			return *this;
			}
		reverse_iterator operator --(int i)
			{
			reverse_iterator temp(*this);
			++I;
			return temp;
			}
		reverse_iterator &operator+=(difference_type n)
			{
			I-=n;
			return *this;
			}
		reverse_iterator &operator-=(difference_type n)
			{
			I+=n;
			return *this;
			}
		reverse_iterator operator+(difference_type n) const
			{
			reverse_iterator temp(*this);
			return (temp+=n);
			}
		reverse_iterator operator-(difference_type n) const
			{
			reverse_iterator temp(*this);
			return (temp-=n);
			}
		difference_type operator-(const reverse_iterator &it) const
			{
			return (it.base()-base());
			}
		reference operator[](difference_type n) const
			{
			return *(reverse_iterator(I-n));
			}
		bool operator==(const reverse_iterator &reverseIterator) const
			{
			return I==reverseIterator.I;
			}
		bool operator!=(const reverse_iterator &reverseIterator) const
			{
			return I!=reverseIterator.I;
			}
		bool operator<(const reverse_iterator &reverseIterator) const
			{
			return I>reverseIterator.I;
			}
		bool operator<=(const reverse_iterator &reverseIterator) const
			{
			return I>=reverseIterator.I;
			}
		bool operator>(const reverse_iterator &reverseIterator) const
			{
			return I<reverseIterator.I;
			}
		bool operator>=(const reverse_iterator &reverseIterator) const
			{
			return I<=reverseIterator.I;
			}

};

//iterador inverso para apuntadores
template <class It, class type>
class reverse_iterator_pointer: public iterator<iterator_traits_pointer<type>::iterator_category,
iterator_traits_pointer<type>::value_type, iterator_traits_pointer<type>::difference_type,
iterator_traits_pointer<type>::pointer, iterator_traits_pointer<type>::reference>	{
	protected:
		It I;
	public:
		typedef It iterator_type;

		reverse_iterator_pointer(const It newIterator=It()):
		I(newIterator)
			{
			}
		template <class It1, class type1>
		reverse_iterator_pointer(const reverse_iterator_pointer<It1,type1> &rit):
		I(rit.realbase())
			{
			}
		It base() const
			{
			It temp(I);
			return --temp;
			}
		It realbase() const
			{
			return I;
			}
		reference operator *() const
			{
			It temp(I);
			return *--temp;
			}
		pointer operator ->() const
			{
			return &**this;
			}
		reverse_iterator_pointer &operator ++()
			{
			--I;
			return *this;
			}
		reverse_iterator_pointer operator ++(int i)
			{
			reverse_iterator_pointer temp(*this);
			--I;
			return temp;
			}
		reverse_iterator_pointer &operator --()
			{
			++I;
			return *this;
			}
		reverse_iterator_pointer operator --(int i)
			{
			reverse_iterator_pointer temp(*this);
			++I;
			return temp;
			}
		reverse_iterator_pointer &operator+=(difference_type n)
			{
			I-=n;
			return *this;
			}
		reverse_iterator_pointer &operator-=(difference_type n)
			{
			I+=n;
			return *this;
			}
		reverse_iterator_pointer operator+(difference_type n) const
			{
			reverse_iterator_pointer temp(*this);
			return (temp+=n);
			}
		reverse_iterator_pointer operator-(difference_type n) const
			{
			reverse_iterator_pointer temp(*this);
			return (temp-=n);
			}
		difference_type operator-(const reverse_iterator_pointer &it) const
			{
			return (it.base()-base());
			}
		reference operator[](difference_type n) const
			{
			return *(reverse_iterator_pointer(I-n));
			}
		bool operator==(const reverse_iterator_pointer &reverseIterator) const
			{
			return I==reverseIterator.I;
			}
		bool operator!=(const reverse_iterator_pointer &reverseIterator) const
			{
			return I!=reverseIterator.I;
			}
		bool operator<(const reverse_iterator_pointer &reverseIterator) const
			{
			return I>reverseIterator.I;
			}
		bool operator<=(const reverse_iterator_pointer &reverseIterator) const
			{
			return I>=reverseIterator.I;
			}
		bool operator>(const reverse_iterator_pointer &reverseIterator) const
			{
			return I<reverseIterator.I;
			}
		bool operator>=(const reverse_iterator_pointer &reverseIterator) const
			{
			return I<=reverseIterator.I;
			}

};

//para apuntadores
template<class In, class type>
inline typename iterator_traits_pointer<type>::difference_type distance_pointer(In first, In last)
{
return (last-first);
}

template<class In>
inline typename iterator_traits<In>::difference_type distance(In first, In last)
{
return distance_helper(first,last,iterator_traits<In>::iterator_category());
}

template<class In>
inline typename iterator_traits<In>::difference_type distance_helper(In first, In last, input_iterator_tag)
{
typename iterator_traits<In>::difference_type d=0;
while(first!=last)
	{
	++d;
	++first;
	}

return d;
}

template<class Ran>
inline typename iterator_traits<Ran>::difference_type distance_helper(Ran first, Ran last, random_access_iterator_tag)
{
return (last-first);
}

//para apuntadores
template <class In, class Dist>
inline void advance_pointer(In &i, Dist n)
{
i+=n;
}

template <class In, class Dist>
inline void advance(In &i, Dist n)
{
advance_helper(i,n,iterator_traits<In>::iterator_category());
}

template <class In, class Dist>
inline void advance_helper(In &i, Dist n, input_iterator_tag)
{
while(n)
	{
	++i;
	--n;
	}
}

template <class Ran, class Dist>
inline void advance_helper(Ran &i, Dist n, random_access_iterator_tag)
{
i+=n;
}

//Insertores

template <class container>
class back_insert_iterator: public OutIt<void,void,void,void>	{
protected:
	container &c;
public:
	explicit back_insert_iterator(container &c1):
	c(c1)
		{
		}
	back_insert_iterator &operator=(const typename container::value_type &val)
		{
		c.push_back(val);

		return *this;
		}
	back_insert_iterator &operator*() {return *this;}
	back_insert_iterator &operator++() {return *this;}
	back_insert_iterator operator++(int i) {return *this;}

};

template <class container>
class front_insert_iterator: public OutIt<void,void,void,void>	{
protected:
	container &c;
public:
	explicit front_insert_iterator(container &c1):
	c(c1)
		{
		}
	front_insert_iterator &operator=(const typename container::value_type &val)
		{
		c.push_front(val);

		return *this;
		}
	front_insert_iterator &operator*() {return *this;}
	front_insert_iterator &operator++() {return *this;}
	front_insert_iterator operator++(int i) {return *this;}

};

template <class container>
class insert_iterator: public OutIt<void,void,void,void>	{
protected:
	container &c;
	typename container::iterator it;
public:
	explicit insert_iterator(container &c1, typename container::iterator i):
	c(c1), it(i)
		{
		}
	insert_iterator &operator=(const typename container::value_type &val)
		{
		it=c.insert(it,val);
		++it;

		return *this;
		}
	insert_iterator &operator*() {return *this;}
	insert_iterator &operator++() {return *this;}
	insert_iterator operator++(int i) {return *this;}

};

template <class container>
back_insert_iterator<container> back_inserter(container &c)
{
return back_insert_iterator<container>(c);
}

template <class container>
front_insert_iterator<container> front_inserter(container &c)
{
return front_insert_iterator<container>(c);
}

template <class container, class Out>
insert_iterator<container> inserter(container &c, Out p)
{
return insert_iterator<container>(c,p);
}

}

#endif