#include <iostream>
#include <string>
#include <vector>
using namespace std;
/*
	類名稱：Node
	類功能：將輸入的string以node形式組織起來，便于在LSD時進行分和收的操作
	與其它類的繼承和調用關系：無
*/
class Node{
public:
	string key;		//輸入的英文單詞
	int next;		//指向排序后該單詞的后一個單詞在數組的位置
};
/*
	類名稱：StaticQueue
	類功能：定義出在收集時每個桶的數據結構
	與其它類的繼承和調用關系：無
*/
class StaticQueue{
public:
	int head;	//指向當前關鍵碼所對應桶的第一個元素在數組中的下標，-1標記為無
	int tail;	//指向當前關鍵碼所對應桶的最后一個元素在數組中的下標，-1標記為無
};
/*
	類名稱：RadixSorter
	類功能：將所有解決英文單詞按基數排序的函數，數據封裝在一個類中
	與其它類的繼承和調用關系：調用Node類，將Node類作為所輸入的英文單詞在vector中的組織形式
*/
class RadixSorter{
public:
	RadixSorter():size(53){init();};	//構造函數
	void init();		//對輸入進行初始化的函數
	void DoSort();		//對輸入的數據進行基數排序的函數
	void PrintString(int );		//輸出數組中排序的結果
private:
	void Setlength();		//將所有的輸入的字母調整為定長
	void Distribute(int  , int  ,StaticQueue * );	//LSD中分的函數
	void Collect(int & , StaticQueue *);		//LSD中收的函數
	inline int GetKeynumber(char);		//返回當前字符對應關鍵碼的桶的位置
	const int size;			//桶的多少
	int stringnumber;		//記錄所輸入數據的總數
	int length;				//記錄給定的最長的字符
	vector<Node> Myvector;	//存儲所有輸入的數據
};
/*
	函數名：init
	函數功能：處理給定的輸入，并且將輸入的string以Node的形式組織在數組里，便于處理
*/
void RadixSorter::init (){
	cout<<"please enter the max length of the string"<<endl;
	cin>>length;	//最大的單詞長度
	string tempstring;	
	Node tempnode ;
	cout<<"please enter the number of the string"<<endl;
	cin>>stringnumber;
	int i=0;
	while(i++<stringnumber){
		cin>>tempstring;
		tempnode.key=tempstring;
		tempnode.next=i;
		Myvector.push_back (tempnode);
	}
}
/*
	函數名：GetKeynumber
	函數功能：根據傳入字符，返回其所對應的桶的編號，其對應原則是
	如果是結束符，那么在第0個桶，其余字母按順序，A-Z在1-26，a-z在27-52
	參量意義：所傳入，當前需要做排序處理的字符
*/
inline int RadixSorter::GetKeynumber(char a){
	if(a=='\0')
		return 0;
	else
		if(a>='A'&&a<='Z')
			return a-'A'+1;
		else
			if(a>='a'&&a<='z')
				return a-'a'+27;
}
/*
	函數名：PrintString
	函數功能：根據排序后的順序輸出序列
	參量意義：從某個給定的位置first開始打印數組
*/
void RadixSorter::PrintString (int first){
	int i=first;
	while(i!=-1){
		cout<<Myvector[i].key <<" ";
		i=Myvector[i].next ;
	}
	cout<<endl;
}
/*
	函數名：Distribute
	函數功能：實現LSD中分的功能，將當前序列分到桶中
	參數意義：first：當前序列起始元素的在數組中的序號
			  step：當前排序的字符串的位數
			  queue：用于實現這些桶的靜態鏈
*/
void RadixSorter::Distribute (int first , int step , StaticQueue * queue){
	for(int i=0;i<size;i++)
		queue[i].head =-1;		//對靜態鏈中元素的初始化
	int begin=first;			//begin為當前處理元素在數組中的下標
	while(begin!=-1){
		string temp=Myvector[begin].key ;
		int position=GetKeynumber(temp[step]);	//position為當前第step位關鍵字所在桶的序號
		if(queue[position].head ==-1)
			queue[position].head =begin;		//子序列為空，則當前記錄為第一個記錄
		else
			Myvector[queue[position].tail].next=begin;	//否則加到子序列尾部
		queue[position].tail=begin;			//當前記錄為序列的尾部
		begin=Myvector[begin].next ;		//繼續分配下一個記錄
	}
}
/*
	函數名：Collect
	函數功能：實現LSD中收的功能，將分好的桶合在一塊成為整個序列
	參數意義：first:合并完成后，序列的首元素
			  queue:用于實現桶的靜態鏈
*/
void RadixSorter::Collect (int & first  , StaticQueue * queue){
	int k=0;
	while(queue[k].head ==-1)	//找到第一個非空的桶
		k++;
	first=queue[k].head ;		//第一個非空的桶的首元素為新序列的首元素
	int last=queue[k].tail ;
	while(k<size-1){			
		k++;
		while(k<size-1&&queue[k].head==-1) k++;		//繼續收集下一個非空的桶
		if(queue[k].head !=-1)
		{
			Myvector[last].next =queue[k].head ;	//將這個序列與上一個非空的序列連接起來
			last=queue[k].tail ;
		}
	}
	Myvector[last].next =-1;		//對最后一個元素作標記
}
/*
	函數名：SetLength
	函數功能：將所有輸入的單詞調整成為給定的最長長度的單詞的長度，多出的部分補\0
*/
void RadixSorter::Setlength (){
	vector<Node>::iterator i=Myvector.begin ();
	for(;i!=Myvector.end ();i++)
	{
		if((*i).key.length()<length)
		{
			string::iterator i_string=(*i).key.end ();
			for(int j=0;j<length-(*i).key.length() ;j++)
			{
				(*i_string)='\0';		//對多余部分補\0
				i_string++;}
		}
	}
}
/*
	函數名：DoSort
	函數功能：用LSD的基數排序處理輸入的所有單詞
*/
void RadixSorter::DoSort (){
	Setlength();	//預處理，將當前所有的單詞調成給定的長度
	StaticQueue  * queue=new StaticQueue[size];		//申請實現桶的靜態鏈
	Myvector[stringnumber-1].next =-1;		//對序列最后一個元素進行標記
	cout<<"before sorting"<<endl;
	PrintString(0);
	int first=0;
	for(int j=length-1;j>=0;j--)	//一共處理n布
	{
		Distribute(first , j , queue);
		Collect(first  ,queue);
	}
	PrintString(first);
	delete []queue;		

}
int main(){
	RadixSorter mysort;
	mysort.DoSort ();
	return 1;
}