#include <iostream>
#include <cstdlib>
#include <vector>
#include <list>
#include <iterator>   //for iterator_traits
#include "node.h"
using namespace std;

template <class RANDOM, class DIFFERENCE_TYPE>
inline void __my_advance(RANDOM& it, DIFFERENCE_TYPE d,
	random_access_iterator_tag)
{
	cout << "random access iterator __my_advance\n";
	it += d;
}

template <class BIDIRECTIONAL, class DIFFERENCE_TYPE>
void __my_advance(BIDIRECTIONAL& it, DIFFERENCE_TYPE d,
	bidirectional_iterator_tag)
{
	cout << "bidirectional iterator __my_advance\n";

	for (; d > 0; --d) {
		++it;
	}

	for (; d < 0; ++d) {
		--it;
	}
}

template <class INPUT, class DIFFERENCE_TYPE>
void __my_advance(INPUT& it, DIFFERENCE_TYPE d, input_iterator_tag)
{
	cout << "input iterator __my_advance\n";

	if (d < 0) {
		cerr << "Can't move a non-bidirectional iterator backwards.\n";
		exit(EXIT_FAILURE);
	}

	for (; d > 0; --d) {
		++it;
	}
}

//The dispatching function is always inline.

template <class INPUT, class DIFFERENCE_TYPE>
inline void my_advance(INPUT& it, DIFFERENCE_TYPE d)
{
	__my_advance(it, d,
		typename iterator_traits<INPUT>::iterator_category());
}

int main()
{
	const int a[] = {10, 20, 30, 40, 50};
	const size_t n = sizeof a / sizeof a[0];

	vector<int> v(a, a + n);
	vector<int>::iterator it1 = v.begin();
	my_advance(it1, 4);
	cout << *it1 << "\n";

	list<int> li(a, a + n);
	list<int>::iterator it2 = li.begin();
	my_advance(it2, 4);
	cout << *it2 << "\n";

	node *begin = new node(50, 0);
	begin = new node(40, begin);
	begin = new node(30, begin);
	begin = new node(20, begin);
	begin = new node(10, begin);

	node::iterator it3 = begin;
	my_advance(it3, 4);
	cout << *it3 << "\n";

	return EXIT_SUCCESS;
}