#include <iostream>
using namespace std;

template < class T >
int compare( T jeden, T dwa)
{
	if(jeden == dwa) return 0;
	if(jeden > dwa) return 1;
	else return -1;
}

template < class T >
class Lista
{
public:
		struct wezel
		{
			T wartosc;
			wezel *next;
		};

		wezel * pierwszy;
		int dlugosc;
		wezel * wskazywany;
		Lista(){	pierwszy = wskazywany = NULL; dlugosc = 0;	}


		class Iterator
		{
		public:
			wezel* element;
			Iterator& operator++() { Iterator n = *this; n.element = n.element->next; *this = n; return n; }
			wezel& operator*()	{ return *(this->element); }
			bool operator==(const Iterator& i2)
			{	return this->element->next == i2.element->next;	}
			bool operator!=(const Iterator& i2)
			{	return this->element->next != i2.element->next; }
		};

		Iterator iter;
		Iterator& Begin() { Iterator n; n.element = pierwszy; return n; }
		Iterator& End()	{ idzNaKoniec(); Iterator n; n.element = wskazywany; return n; }

		void idzO(int ile)
		{
			for(int i = 0; (i < ile) && (wskazywany->next != NULL); i++)
				wskazywany = wskazywany->next;
		}
		void idzNaKoniec()
		{
			idzNaPoczatek();
			while(wskazywany->next)
				wskazywany = wskazywany->next;
			return;
		}
		void idzNaPoczatek()
		{
			wskazywany = pierwszy;
		}
		void dodaj(T war)
		{
			wezel *nowy = new wezel;
			nowy->wartosc = war;
			idzNaPoczatek();
			if(wskazywany == NULL)
			{
				nowy->next = NULL;
				pierwszy = nowy;
			}
			else if(compare(war, wskazywany->wartosc) == -1){
				nowy->next = pierwszy;
				pierwszy = nowy;
			}
			else
			{
				while(compare(war, wskazywany->wartosc) == 1 && wskazywany->next != NULL)
				{
					idzO(1);
				}
				nowy->next = wskazywany->next;
				wskazywany->next = nowy;
			}
			dlugosc++;
			return;
		}
		void print()
		{
			idzNaPoczatek();
			int i = 0;
			while(i < dlugosc)
			{
				cout << wskazywany->wartosc << " ";
				wskazywany = wskazywany->next;
				i++;
			}
			return;
		}
		~Lista()
		{
			for(int i = 0; i < dlugosc; i++)
			{
				idzNaPoczatek();
				while(wskazywany->next)
				{
					wskazywany = wskazywany->next;
				}
				wskazywany = NULL;
				delete wskazywany;
				cout << "usuwam \n";
			}
		}
};

int main()
{
    Lista<int> *lista = new Lista<int>;
	for(int i = 3; i < 10; i++)
		lista->dodaj(i);
	lista->dodaj(2);
	lista->dodaj(32);
	lista->dodaj(6);
	lista->print();
	lista->idzNaKoniec();
	lista->iter = lista->Begin();
	cout << "\n" << lista->iter.element->wartosc << " ";
	lista->iter = lista->End();
	cout << lista->iter.element->wartosc << endl;

	delete lista;
	system("pause");
	return 0;
}