#ifndef SORT_H_
#define SORT_H_
#include <iostream>
 
template <class Type>
class SortNumbers
{
private:
	struct SortLink
	{
		Type m_number;
		SortLink * m_next;
		SortLink(Type number, SortLink * next): m_number(number), m_next(next) {}
		SortLink() : m_number(0), m_next(0){}
	};
	SortLink * m_head;
	SortLink * m_last;
	int m_counts;
protected:
	void getItems();
	void sortArr();
public:
    SortNumbers();
    ~SortNumbers();
	SortLink * getHead()const{
		return this->m_head; }
	SortLink * getLast()const{
		return this->m_last; }
	SortLink * getSorted()const{
		return this->m_sorted; }
	int getCounts()const{
		return this->m_counts; }
	void show();
};
 
template <class Type>
void SortNumbers<Type>::getItems()
{
	using std::cout;
	using std::cin;
 
	cout <<"Enter the length of your items:  ";
	while(!(cin>>(this->m_counts)) || (this->m_counts)<0 || cin.get()!='\n')
	{
		cout <<"\tOOps! Enter error, enter again  ";
		cin.clear();
		while(cin.get()!='\n')
			continue;
	}
	SortLink * temp;
	for(int i=0;i<(this->getCounts()); i++)
	{
        temp = new SortLink;
		cout <<"\nPlease enter a positive number:  ";
		while(!(cin>>(temp->m_number)) || (temp->m_number)<0 || cin.get()!='\n')
		{
			cout <<"\tOOps, it has encounted an error! please enter it again:  ";
			cin.clear();
			while(cin.get()!='\n')
				continue;
		}
		temp->m_next = 0;
		if(i == 0)
			this->m_head = this->m_last = temp;
		else
		{
			this->m_last->m_next = temp;
			this->m_last = temp;
			if(i==((this->getCounts())-1))
                this->sortArr();
		}
	}
}
 
template <class Type>
void SortNumbers<Type>::sortArr()
{
	SortLink * tempJ;
	SortLink * tempI;
	SortLink key;
	int i = 0;
	tempI = tempJ =  this->getHead();
	for(int j=1; j<(this->getCounts()); j++)
	{
		tempI = tempJ = this->getHead();
		for(int k=0; k<j; k++)
            tempJ = tempJ->m_next;
        for(int m=0; m<(j-1); m++)
            tempI = tempI->m_next;
		key.m_number = tempJ->m_number;
		key.m_next = 0;
		i = j-1;
		while(i>=0 && ((tempI->m_number)>(key.m_number)))
		{
			tempI->m_next->m_number = tempI->m_number;
			i--;
            tempI = this->getHead();
            for(int n=0; n<i; n++)
                tempI = tempI->m_next;
		}
		if(i>=0)
			tempI->m_next->m_number = key.m_number;
		else
			this->m_head->m_number = key.m_number;
    }
}
 
template <class Type>
SortNumbers<Type>::SortNumbers()
{
	this->getItems();
}
 
template <class Type>
SortNumbers<Type>::~SortNumbers()
{
	delete [] m_head;
}
 
template <class Type>
void SortNumbers<Type>::show()
{
	using std::cout;
	using std::endl;
 
	SortLink * temp = this->getHead();
	if((this->getCounts()) != 0)
	{
		cout <<endl<<"Now, the sorted numbers are:\n\t";
		temp = this->m_head;
		for(int k=0; k<(this->getCounts()); k++)
		{
			cout <<(temp->m_number)<<" ";
			if(temp->m_next != 0)
				temp = temp->m_next;
		}
	}
	else
		cout <<"No numbers.\n";
}
 
#endif