package ch04;

import java.util.Arrays;

public class SeqString implements IString{
	private char[] strvalue;			//×Ö·ûÊý×é£¬´æ·Å´®Öµ
	private int curlen;					//µ±Ç°´®µÄ³¤¶È
	public String toString(){
		return Arrays.toString(strvalue);
	}
	//¹¹Ôì·½·¨1£º¹¹ÔìÒ»¸ö¿Õ´®
	public SeqString(){
		strvalue = new char[0];		
		curlen=0;
	}
	//¹¹Ôì·½·¨2£ºÒÔ×Ö·û´®³£Á¿¹¹Ôì´®¶ÔÏó
	public SeqString(String str){
		char[] tempchararray =  str.toCharArray();
		strvalue =tempchararray;
		curlen = tempchararray.length;
	}
	//¹¹Ôì·½·¨3£ºÒÔ×Ö·û´®Êý×é¹¹Ôì´®¶ÔÏó
	public SeqString(char[] value){
		this.strvalue =new char[value.length];
		for(int i =0;i<value.length;i++){		//¸´ÖÆÊý×é
			this.strvalue[i] = value[i];
		}
		curlen = value.length;
	}
	@Override
	//ÖÃ¿Õ
	public void clear() {
		// TODO Auto-generated method stub
		this.curlen=0;
	}

	@Override
	//ÅÐ¿Õ
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return curlen==0;
	}

	@Override
	//Çó³¤¶È
	public int length() {
		// TODO Auto-generated method stub
		return curlen;
	}

	@Override
	//½ØÈ¡×Ö·û
	public char charAt(int index) {
		// TODO Auto-generated method stub
		if((index<0)||(index>=curlen)){
			throw new StringIndexOutOfBoundsException(index);
		}
		return strvalue[index];
	}

	//À©³ä×Ö·û´®´æ´¢¿Õ¼äÈÝÁ¿£¬²ÎÊýÖ¸¶¨ÈÝÁ¿
	public void allocate(int newCapacity){
		char[ ] temp =strvalue;
		strvalue =new char[newCapacity];
		for(int i=0;i<temp.length;i++){
			strvalue[i] = temp[i];
		}
	}
	//·µ»Ø´®ÖÐÐòºÅ´Óbegin¿ªÊ¼µ½end-1µÄ×Ó´®
	public IString substring(int begin, int end) {
		// TODO Auto-generated method stub
		if(begin<0){
			throw new StringIndexOutOfBoundsException("ÆðÊ¼Î»ÖÃ²»ÄÜÐ¡ÓÚ0");
		}
		if(end>curlen){
			throw new StringIndexOutOfBoundsException("½áÊøÎ»ÖÃ²»ÄÜ´óÓÚ´®µÄµ±Ç°³¤¶È");
		}
		if(begin>end){
			throw new StringIndexOutOfBoundsException("¿ªÊ¼Î»ÖÃ²»ÄÜ´óÓÚ½áÊøÎ»ÖÃ");
		}
		if(begin == 0 && end == curlen){
			return this;
		}else{
			char[] buffer = new char[end - begin];
			for(int i=0;i<buffer.length;i++){					//¸´ÖÆ×Ó´®
				buffer[i] = this.strvalue[i +begin];
			}
			return new SeqString(buffer);
		}
	}

	@Override
	//´®µÄ²åÈë²Ù×÷
	public IString insert(int offset, IString str) {
		// TODO Auto-generated method stub
		if((offset <0)||(offset>this.curlen)){
			throw new StringIndexOutOfBoundsException("²åÈëÎ»ÖÃ²»ºÏ·¨");
		}
		int len =str.length();
		int newCount =this.curlen+len;
		if(newCount>strvalue.length){
			allocate(newCount);
		}
		for(int i=this.curlen-1;i>=offset;i--){
			strvalue[len+i]=strvalue[i];
		}
		for(int i=0;i<len;i++){
			strvalue[offset + i]=str.charAt(i);
		}
		
		this.curlen=newCount;
		return this;
	}

	@Override
	//É¾³ý²Ù×÷
	public IString delete(int begin, int end) {
		// TODO Auto-generated method stub
		if(begin<0){
			throw new StringIndexOutOfBoundsException("ÆðÊ¼Î»ÖÃ²»ÄÜÐ¡ÓÚ0");
		}
		if(end>curlen){
			throw new StringIndexOutOfBoundsException("½áÊøÎ»ÖÃ²»ÄÜ´óÓÚ´®µÄµ±Ç°³¤¶È");
		}
		if(begin >end){
			throw new StringIndexOutOfBoundsException("¿ªÊ¼Î»ÖÃ²»ÄÜ´óÓÚ½áÊøÎ»ÖÃ");
		}
		for(int i =0;i<curlen -end;i++){
			strvalue[begin +i] = strvalue[end+i];
		}
		curlen =curlen -(end - begin);					//µ±Ç°´®³¤¶È¼õÈ¥(end-begin)
		return this;
	}

	@Override
	//Ìí¼ÓÖ¸¶¨´®strµ½µ±Ç°´®Î²
	public IString concat(IString str) {
		// TODO Auto-generated method stub
		return insert(curlen,str);
	}

	@Override
	//´®µÄ±È½Ï²Ù×÷
	public int comparaTo(SeqString str) {
		// TODO Auto-generated method stub
		int len1 =curlen;
		int len2 = str.curlen;
		int n =Math.min(len1, len2);
		char[] s1=strvalue;
		char[] s2 = str.strvalue;
		int k=0;
		while(k<n){
			char ch1 = s1[k];
			char ch2 = s2[k];
			if(ch1 != ch2){
				return ch1 -ch2;
			}
			k++;
		}
		return len1-len2;
	}

	@Override
	public int indexOf(IString str, int begin) {
		// TODO Auto-generated method stub
		if(this!=null&&str!=null&&str.length()>0&&this.length()>=str.length()){
			int slen,tlen,i=begin,j=0;								//µ±Ö÷´®±ÈÄ£Ê½´®³¤Ê±½øÐÐ±È½Ï
			slen = this.length();									//i±íÊ¾Ö÷´®ÖÐÄ³¸ö×Ó´®µÄÐòºÅ
			tlen = str.length();
			while((i<slen)&&(j<tlen)){
				if(this.charAt(i)==str.charAt(j)){					//jÎªÄ£Ê½´®µ±Ç°×Ö·ûµÄÏÂ±ê
					i++;
					j++;
				}else{
					i = i-j+1;										//¼ÌÐø±È½ÏºóÐø×Ö·û
					j=0;											//¼ÌÐø±È½ÏÖ÷´®ÖÐµÄÏÂÒ»¸ö×Ó´®
				}													//Ä£Ê½´®ÏÂ±êÍË»Øµ½0
			}
			if(j>=str.length())
				return i-tlen;										//Æ¥Åä³É¹¦£¬·µ»Ø×Ó´®ÐòºÅ
		}
		else{
			return -1;	
		}
		return -1;							//Æ¥ÅäÊ§°Ü·µ»Ø-1
}
	private int[] getNext(IString T){
		int[] next = new int[T.length()];
		int j=0;
		int k=-1;
		next[0]=-1;
		while(j<T.length()-1){
			if(k ==-1||T.charAt(j)== T.charAt(k)){
				j++;
				k++;
				if(T.charAt(j)!=T.charAt(k))
					next[j] =k;
				else
					next[j]=next[k];
			}else
				k = next[k];
		}
		return (next);
	}
	//KMPËã·¨
	public int index_KMP(IString T,int start){
		int[] next = getNext(T);			//¼ÆËãÄ£Ê½´®µÄnext()Öµ
		int i=start;
		int j=0;
		while(i<this.length()&&j<T.length()){
			if(j == -1||this.charAt(i)==T.charAt(j)){
				i++;
				j++;
			}else{
				j = next[j];
			}
		}
		if(j<T.length()){
			return -1;
		}else{
			return(i-T.length());
		}
	}
}
