// ICS 331 Assignment 4 Solution
// by David N. Chin
//
// N-way set-associative cache with LRU cache eviction policy

public class LruCache extends Cache
{
  // eviction method bookeeping
  private int rankings[][]; // 0 is LRU, associativity-1 is MRU
 
  public LruCache( int cacheSize, int numSets )
  {
    super(cacheSize, numSets);
    rankings = new int[slots][associativity];
    for( int i=0; i < slots; i++ ) {
      for( int j=0; j < associativity; j++ ) {
	rankings[i][j] = j;
      }
    }
  }
	
  // store new tag and data in the subcache with highest rank and 
  // recalculate rankings
  public void put ( int tag, int slotNum, boolean write ) {
    for( int subcache=0; subcache < associativity; subcache++ ) {
      if( rankings[slotNum][subcache] == 0 ) {
	store( slotNum, subcache, tag, write );
	rankings[slotNum][subcache] = associativity - 1;
      } else {
	rankings[slotNum][subcache]--;
      }
    }
  }
  
  public int find( int address, boolean write ) {
    int slotNum = address % slots;
    int subCache = super.find(address, write);
    if( subCache >= 0 ) {
      // recompute rankings
      int oldRank = rankings[slotNum][subCache];
      for( int subcache=0; subcache < associativity; subcache++ ) {
	if( rankings[slotNum][subcache] > oldRank )
	  rankings[slotNum][subcache]--;
      }
      rankings[slotNum][subCache] = associativity - 1;
    }
    return subCache;
  }
} // class LruCache