package myprojects.os;
//OPT最優置換算法實現及其命中率計算
class OPT{
	public OPT(){}	//缺省構造方法
	public float getOpt(int p){		//有參getOpt(int p)方法由測試類傳入內存頁面數，并用此
		int[] Opage = new int[p];	//參數計算其對應的OPT的命中率及返回該命中率；
		int[] dis = new int[p];		//dis[]數組，用于記錄對應當前內存頁面到下一次再次讀入此頁面的時間間隔
		int[] page= new int[400];
		GetRandom random = new GetRandom();
		page=random.getPage();	//定義一數組，用以接收頁面數組的內容
		int s,a,k,n=0;
		int i,j;
		float sum=0,Opercent;	//設置兩個float型變量，其中Opercent用于存放命中率,sum則用于記錄命中次數
		for(i=0;i<400;i++){
			if(n==0){	//內存為空
				Opage[0]=page[i];// 把當前頁面值存入內存
				n++;	//記錄當前內存空間
			}
			else{
				if(n<p-1){	//內存不為空且內存未滿
					s=0;
					for(j=0;j<n;j++)	//與內存存放的內容比較，相等則讀入下一條
						if(Opage[j]==page[i]){ //指令
							sum++;	//命中次數加1
							s=1;	//標記比較結果，有相等則s=1
							break;
						}
					if(s==0){//當前指令所對應的頁面值與內存所有內容比較不相等
						Opage[n]=page[i];//則將當前頁面值添加入內存
						n++;	//記錄當前內存空間
					}
				}
				else{		//內存已滿
					s=0;
					for(j=0;j<p;j++){		//與內存存放的內容比較，相等則讀入下一條
						if(Opage[j]==page[i]){ //指令
							sum++;		//命中次數加1
							s=1;		//標記比較結果，有相等則s=1
							break;
						}
					}
					if(s==0){	//當前指令所對應的頁面值與內存所有內容比較不相等
						for(j=0;j<p;j++)
							for(k=i+1;k<400;k++){ //讓內存內所有頁面從當前讀入指令的下一條指令對應	
								if(Opage[j]==page[k]){//的頁面值起與之隨后的指令逐一相比較，直到相
									dis[j]=k-i;		//等時記錄下兩者間的間距
									break;
								}
								else
									dis[j]=500;	// 比較不相等則間距記為最大值500
							}
						a=0;	
						for(j=0;j<p-1;j++)	//比較當前內存所有與之頁面對應的間距，
							if(dis[j]>dis[j+1])	//找出間距最大者，
								dis[j+1]=dis[j];
							else 
								a=j+1;
						Opage[a]=page[i];	//用當前讀入指令的頁面值替換最大者
					}		
				}
			}	
		}
		Opercent=sum/400; //計算命中率
		return Opercent;	//返回該值
	}
}