import java.io.*;
import java.util.*;
 
public class Cache_simulator 
{
    
    public static void main(String[] args)throws IOException 
    {
        int block_num;
        int block_size;
        long address;
        int read_in_cache_size;
        int slot_num;
        int slots_in_cache;
        int cache_size ;
        int Degree_of_associativity;
        int compulsory_miss=0;
        int capacity_miss=0;
        int conflict_miss=0;
        int Total_miss=0;
        int hit=0;
        int index1=0;
        int p=0;
        
        
        Scanner kb= new Scanner(System.in);

        System.out.print("Please input the block size:");
        block_size = kb.nextInt();

        System.out.print("Please input the cache size- the num should be power by 2: ");
        read_in_cache_size = kb.nextInt(); 
        
        System.out.print("Please input the Degree of associativity(must 1,2,4,8):"); 
        Degree_of_associativity = kb.nextInt();        
            
        cache_size = read_in_cache_size*1024;
        
        System.out.println("Please input the replacement policy");
        String policy=kb.next(); 
        
        slots_in_cache = cache_size/block_size;
      
        int[] indexArr1=new int[slots_in_cache];
        int[] indexArr2= new int[slots_in_cache];
        
        if(Degree_of_associativity==1)
        {
            index1=slots_in_cache/Degree_of_associativity;

        }
        else if(Degree_of_associativity==2)
        {
            index1=slots_in_cache/Degree_of_associativity;
        }
        else if(Degree_of_associativity==4)
        {
            index1=slots_in_cache/Degree_of_associativity;
        }    
        else if(Degree_of_associativity==8)
        {
            index1=slots_in_cache/Degree_of_associativity;
        }
            
        if(Degree_of_associativity==2)
        {
           for(int n=0;n<index1;n++)
           indexArr2[n*Degree_of_associativity]=1;
        }
        else if(Degree_of_associativity==4)
        {
           for(int n=0;n<index1;n++)
           indexArr2[n*Degree_of_associativity]=1;
        }
        else if(Degree_of_associativity==8)
        { 
           for(int n=0;n<index1;n++)
           indexArr2[n*Degree_of_associativity]=1;
        }        
        
         Scanner Address = new Scanner(new File("smalltex.din"));
         for(int i=0;i<100000;i++ )
        {
           int line1 = Address.nextInt();
           String line2 = Address.next();
           long c = 0;
           int h=0;
        
         for(int bb = 0; bb < line2.length();bb++)
            {       
                switch(line2.charAt(bb))
                {
                  case '0':   h=0;break;
                 case '1':   h=1;break;
                 case '2':   h=2;break;
                 case '3':   h=3;break;
                 case '4':   h=4;break;
                 case '5':   h=5;break;
                 case '6':   h=6;break;
                 case '7':   h=7;break;
                 case '8':   h=8;break;
                 case '9':   h=9;break;
                 case 'a':   h=10;break;
                 case 'b':   h=11;break;
                 case 'c':   h=12;break;
                 case 'd':   h=13;break;
                 case 'e':   h=14;break;
                 case 'f':   h=15;break;
                 
                }
                  c =(long) (h*Math.pow(16,line2.length()-1-bb)+c);
                } 
              
                    address = c;
                    block_num=(int)(address/block_size);
             
                  slot_num=block_num%index1;
                  if(Degree_of_associativity==1)
               {
             
                  if(indexArr1[slot_num]==block_num)
               {
                   hit++;
               }
               else
               {
                   indexArr1[slot_num]=block_num;
               }
             }
             else if(Degree_of_associativity==2||Degree_of_associativity==4||Degree_of_associativity==8)
             {
                 if(policy=="R" || policy=="r") 
                      {  
                          
                         Random r=new Random(Degree_of_associativity);
                         
                             
                        if(indexArr1[Degree_of_associativity]==block_num)
                     {
                         hit++;
                     }
                     else
                     {
                         indexArr1[Degree_of_associativity*index1+r.nextInt(Degree_of_associativity)]=block_num;
                     }
                     }
                     
                     else
                     {
                      for(int q=0;q<Degree_of_associativity;q++)
                        {
                          if(indexArr2[slot_num*Degree_of_associativity+q]==1)
                         {
                             int e=slot_num*Degree_of_associativity+q;
                             if(q+1>=Degree_of_associativity)
                          {
                             indexArr2[slot_num*Degree_of_associativity]=1;
                             indexArr2[slot_num*Degree_of_associativity]=0;
                          }
                          else
                          {
                             indexArr2[slot_num*Degree_of_associativity+q]=0;
                             indexArr2[slot_num*Degree_of_associativity+q+1]=1;
                          }
                     
                                          
                     if(indexArr1[e]==block_num)
                          {
                             hit++;
                          }
                             else
                          {
                             indexArr1[e]=block_num;

                          }
                        }    
                      }
                    }
             }
             else
             {
                 if(policy=="R"||policy=="r")
                 {
                      Random r=new Random(slots_in_cache);
                     int hh=r.nextInt(slots_in_cache);
                      if(indexArr1[hh]==block_num)
                      {
                         hit++;
                      }
                       else
                      {
                       indexArr1[hh]=block_num;
                      }
                 }
                 else
                 {
                  if(p>slots_in_cache-1)
                  {
                     p=0;
                  }
                  if(indexArr1[p]==block_num)
                  {
                      hit++;
                  }
                  else
                  {
                     indexArr1[p]=block_num;
                  }
                     p++;
                  
                 }

             }
             
        
   
        }
        float Total_miss_rate=(1-(float)hit/100000)*100; 
        Total_miss = 100000-hit;
            
        System.out.println("Hit:" + hit);
        System.out.println("Total Miss:"+ Total_miss);
        
        System.out.println("compulsory miss:" + compulsory_miss+"%");
        System.out.println("capacity miss:" + capacity_miss+"%");
        System.out.println("conflict miss:" + conflict_miss+"%");
        System.out.println("Total Miss Rate:"+Total_miss_rate+"%");    
        Address.close();

        
      
    }
}