#ifndef BOOST_ITERATOR_ITERATOR_OPS_HPP
#define BOOST_ITERATOR_ITERATOR_OPS_HPP

#include <boost/iterator/iterator_categories.hpp>
#include <boost/iterator/iterator_concepts.hpp>

namespace boost {
	namespace detail {

		template <class IncrementableIterator, class Distance>
		void advance(boost::incrementable_traversal_tag,
			IncrementableIterator &i, Distance n)
		{
			boost::function_requires<
				boost_concepts::IncrementableIteratorConcept<
					IncrementableIterator
				>
			>();

			while(n) {
				++i;
				--n;
			}
		}

		// Single pass and forward traversal is the same.

		template <class BidirectionalTraversableIterator, class Distance>
		void advance(boost::bidirectional_traversal_tag,
			BidirectionalTraversableIterator &i, Distance n)
		{
			boost::function_requires<
				boost_concepts::BidirectionalTraversalConcept<
					BidirectionalTraversableIterator
				>
			>();

			if(n > 0) {
				while(n) {
					++i;
					--n;
				}
			} else {
				while(n) {
					--i;
					++n;
				}
			}
		}

		template <class RandomAccessTraversableIterator, class Distance>
		void advance(boost::random_access_traversal_tag,
			RandomAccessTraversableIterator &i, Distance n)
		{
			boost::function_requires<
				boost_concepts::RandomAccessTraversalConcept<
					RandomAccessTraversableIterator
				>
			>();

			i += n;
		}
	}

	// A replacement for std::advance that uses the new iterator categories.
	template <class IncrementableIterator, class Distance>
	void advance(IncrementableIterator &i, Distance n)
	{
		typedef BOOST_DEDUCED_TYPENAME boost::iterator_traversal<
				IncrementableIterator
			>::type traversal;
		detail::advance(traversal(), i, n);
	}

	namespace detail {
		template <class SinglePassIterator>
		BOOST_DEDUCED_TYPENAME std::iterator_traits<
			SinglePassIterator>::difference_type
		distance(boost::single_pass_traversal_tag,
			SinglePassIterator first,
			SinglePassIterator last)
		{
			boost::function_requires<
				boost_concepts::SinglePassIteratorConcept<
					SinglePassIterator
				>
			>();

			BOOST_DEDUCED_TYPENAME
			std::iterator_traits<SinglePassIterator>::difference_type
				n = 0;
			while(first != last) {
				++first;
				++n;
			}
			return n;
		}

		// Forward and bidirectional are the same.

		template <class RandomAccessTraversableIterator>
		BOOST_DEDUCED_TYPENAME std::iterator_traits<
			RandomAccessTraversableIterator>::difference_type
		distance(boost::random_access_traversal_tag,
			RandomAccessTraversableIterator first,
			RandomAccessTraversableIterator last)
		{
			boost::function_requires<
				boost_concepts::RandomAccessTraversalConcept<
					RandomAccessTraversableIterator
				>
			>();

			return last - first;
		}
	}

	// A replacement for std::distance that uses the new iterator categories.
	template <class SinglePassIterator>
	BOOST_DEDUCED_TYPENAME std::iterator_traits<
		SinglePassIterator>::difference_type
	distance(SinglePassIterator first,
		SinglePassIterator last)
	{
		typedef BOOST_DEDUCED_TYPENAME boost::iterator_traversal<
				SinglePassIterator
			>::type traversal;
		return detail::distance(traversal(), first, last);
	}
}

#endif