!include once #1027304 // Eclipse Collections

// read-only, so far. not thread-safe
final sclass BufferedDiskIntMemory implements IIntMemory, AutoCloseable {
  File file;
  int size;
  RandomAccessFile raf;
  bool bigEndian = true;
  bool debug;
  
  // pageSize is in ints
  int pageShift, pageSize, maxCachedPages;
  new IntObjectHashMap<CacheEntry> cache;
  CacheEntry newestCacheEntry, oldestCacheEntry;
  
  // stats
  int pageLoads, evictions;
  
  sclass CacheEntry {
    int page;
    int[] data;
    CacheEntry newer, older; // MRU list
    
    toString { ret "Page " + page; }
  }
  
  *() {
    int cacheSizeInBytes = 16384;
    pageShift = 31-Int.numberOfLeadingZeros(cacheSizeInBytes >> 2);
    pageSize = 1 << pageShift;
    maxCachedPages = (128*1024*1024) >> pageShift;
  }
  
  *(File *file) {
    this();
    size = toInt_safe(fileSize(file)/4);
    raf = randomAccessFileForReading(file);
  }
  
  public void close {
    dispose raf;
  }
  
  public int get(int idx) {
    rangeCheck(idx, size);
    int page = idx >> pageShift;
    CacheEntry e = cache.get(page);
    if (e == null) {
      if (debug) print("Accessing unloaded cell " + intToHex(idx));
      e = loadPage(page);
    } else
      touchPage(e);
    ret e.data[idx & (pageSize-1)];
  }
  
  void touchPage(CacheEntry e) {
    if (e == newestCacheEntry) ret;
    if (debug) print("Touching page " + e.page + ". Older=" + e.older + ", newer=" + e.newer + ". Oldest=" + oldestCacheEntry + ", newest=" + newestCacheEntry);
    
    // Take out of list, insert at top
    if (e.older != null)
      e.older.newer = e.newer; // There is an older page, point it to who was on top of us
    else
      oldestCacheEntry = e.newer; // We were the oldest, point it to who was on top uf os
    e.newer.older = e.older; // Point who was on top of us to who was behind us (or no one)
    e.newer = null; // nobody newer than us
    e.older = newestCacheEntry; // point to previous newest
    newestCacheEntry = e; // make us the newest
  }
  
  bool cacheFull() { ret cache.size() >= maxCachedPages; }
  
  void evictAPage {
    ++evictions;
    CacheEntry e = oldestCacheEntry;
    if (debug) print("Evicting page " + e.page);
    cache.remove(e.page);
    oldestCacheEntry = e.newer;
    if (oldestCacheEntry == null) newestCacheEntry = null;
  }
  
  CacheEntry loadPage(int page) ctex {
    ++pageLoads;
    if (cacheFull()) evictAPage();
    if (debug) print("Loading page " + page);
    raf.seek(((long) page) << (pageShift+2));
    byte[] buf = new[pageSize*4];
    raf.read(buf);
    new CacheEntry e;
    e.page = page;
    e.data = bigEndian ? intArrayFromBytes(buf) : intArrayFromBytes_littleEndian(buf);
    cache.put(page, e);
    
    // put e in front of MRU list
    e.older = newestCacheEntry; // point to previous top
    if (newestCacheEntry != null) // list is not empty, update "newer" pointer of current top
      newestCacheEntry.newer = e;
    else oldestCacheEntry = e; // otherwise, we are also the oldest entry
    newestCacheEntry = e; // we are new top
    ret e;
  }
  
  public void set(int idx, int val) {
    fail("read-only");
  }
  
  public int size() {
    ret size;
  }
}