// linkList.h: interface for the linkList class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_LINKLIST_H__DEB787DD_323C_45A8_8CFF_B62661FE246A__INCLUDED_)
#define AFX_LINKLIST_H__DEB787DD_323C_45A8_8CFF_B62661FE246A__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "listNode.h"

#include "fstream.h"
template<class T>
class linkList :public listNode<T>
{public:listNode<T> *first,*last;
public:
	linkList(){	
		first=NULL;
		last=NULL;	
	};

	void createLinkList(){	
		fstream infile;
		T dat;
		infile.open("linklist.txt",ios::in);//工程目錄下附有linkList.txt 文件
		if(!infile){		
			cout<<"linkList can't open.\n";
		}	
		while(!infile.eof()){//eof()判斷文件是否結束		
			infile>>dat;     //讀取數據
			inserFirst(dat);	
		}
		infile.close();
	}


	void inserFirst(T da){	
		listNode<T> *p=new listNode<T>;
		p->data=da;
		p->next=first;
		first=p;
		if(last==NULL)
			last=p;
	}
	/*
	*/
	///////插入排序方法
	void sort(){
	
		listNode<T> *lastInOrder;
		listNode<T> *firstOutOfOrder;
		listNode<T> *ptr;
		listNode<T> *pre;
		lastInOrder=first;
		if(first==NULL){		
			cout<<"Cannot sort an empty list"<<endl;		
		}
		else
			if(first->next==NULL)
				cout<<"The length is 1 ,don't need to be sorted"<<endl;
			else
				while(lastInOrder->next!=NULL){
				
					firstOutOfOrder=lastInOrder->next;
					if(firstOutOfOrder->data<first->data){
					
						lastInOrder->next=firstOutOfOrder->next;
						firstOutOfOrder->next=first;
						first=firstOutOfOrder;					
					}
					else{
					
						pre=first;
						ptr=first->next;
						while(ptr->data<firstOutOfOrder->data){
						
							pre=ptr;
							ptr=ptr->next;			
						}
						if(ptr!=firstOutOfOrder){
						
							lastInOrder->next=firstOutOfOrder->next;
							firstOutOfOrder->next=ptr;
							pre->next=firstOutOfOrder;					
						}
						else{						
							lastInOrder=lastInOrder->next;						
						}					
					}				
				}
	
	
	
	
	}
	void outPut(){	
		listNode<T> *p=first;
		while(p){		
			cout<<p->data<<" ";	
			p=p->next;
		}	
		
	}
	virtual ~linkList(){	
		listNode<T> *p,*pl;
		p=first;
		while(p){		
			pl=p->next;
			delete p;
			p=pl;		
		}	
	};

};

#endif // !defined(AFX_LINKLIST_H__DEB787DD_323C_45A8_8CFF_B62661FE246A__INCLUDED_)