!include once #1027304 // Eclipse Collections

// read-only, so far. not thread-safe
final sclass BufferedDiskIntMemory implements IIntMemory, AutoCloseable {
  File file;
  long size; // file size in ints
  RandomAccessFile raf;
  bool bigEndian = true;
  bool writable = true;
  bool debug, verboseEvictions;
  long cacheSize = 128*1024*1024; // in bytes
  
  // pageSize is in ints
  // page indices are ints interpreted as unsigned
  int pageShift, pageSize, maxCachedPages;
  new IntObjectHashMap<CacheEntry> cache;
  CacheEntry newestCacheEntry, oldestCacheEntry;
  
  // stats
  int pageLoads, evictions;
  
  static int defaultPageSize = 4096; // in bytes
  
  sclass CacheEntry {
    int page;
    bool dirty;
    int[] data;
    CacheEntry newer, older; // MRU list
    
    toString { ret "Page " + page; }
  }
  
  *() {
    setPageSize(4096);
  }
  
  void setPageSize(int pageSizeInBytes) {
    clearCache();
    pageShift = 31-Int.numberOfLeadingZeros(pageSizeInBytes >> 2);
    pageSize = 1 << pageShift;
    updateMaxCachedPages();
  }
  
  void setMaxCachedBytes(long bytes) {
    cacheSize = bytes;
    updateMaxCachedPages();
  }
  
  // internal
  void updateMaxCachedPages {
    maxCachedPages = (int) (cacheSize >> (pageShift+2));
  }
  
  long maxCachedBytes() {
    ret ((long) maxCachedPages) << (pageShift+2);
  }
  
  long cachedBytes() {
    ret ((long) cache.size()) << (pageShift+2);
  }
  
  void clearCache {
    flush();
    cache = new IntObjectHashMap;
    newestCacheEntry = oldestCacheEntry = null;
  }
  
  
  *(File *file) {
    this(file, false);
  }
  
  *(File *file, bool *writable) {
    this();
    size = fileSize(file)/4;
    if (size > 0xFFFFFFFFL) fail("File too big");
    raf = newRandomAccessFile(file, writable ? "rw" : "r");
  }
  
  public void close {
    flush();
    dispose raf;
  }
  
  void flush {
    for (CacheEntry e: cache.values())
      flushPage(e);
  }
  
  public int get(int idx) {
    rangeCheck(uintToLong(idx), size);
    ret loadCell(idx).data[idx & (pageSize-1)];
  }
  
  CacheEntry loadCell(int idx) {
    int page = toInt(uintToLong(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;
  }
  
  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
    removeFromLinkedList(e);
    
    // re-insert at top
    e.newer = null; // nobody newer than us
    e.older = newestCacheEntry; // point to previous newest
    newestCacheEntry.newer = e; // point previous newest to us
    newestCacheEntry = e; // make us the newest
    
    if (debug) print("Touched page " + e.page + ". Older=" + e.older + ", newer=" + e.newer + ". Oldest=" + oldestCacheEntry + ", newest=" + newestCacheEntry);
  }
  
  void removeFromLinkedList(CacheEntry e) {
    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
    if (e.newer != null)
      e.newer.older = e.older; // Point who was on top of us to who was behind us (or no one)
    else
      newestCacheEntry = e.older;
  }
  
  bool cacheFull() { ret cache.size() >= maxCachedPages; }
  
  void evictAPage {
    ++evictions;
    CacheEntry e = oldestCacheEntry;
    flushPage(e);
    if (debug || verboseEvictions) print("Evicting page " + e.page);
    cache.remove(e.page);
    removeFromLinkedList(e);
  }
  
  void flushPage(CacheEntry e) ctex {
    if (!e.dirty) ret;
    if (debug) print("Saving page " + e.page);
    raf.seek(uintToLong(e.page) << (pageShift+2));
    byte[] buf = bigEndian ? intArrayToBytes(e.data) : intArrayToBytes_littleEndian(e.data);
    raf.write(buf);
    e.dirty = false;
  }
  
  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
    
    if (debug) print("Loaded page " + e.page + ". Older=" + e.older + ", newer=" + e.newer + ". Oldest=" + oldestCacheEntry + ", newest=" + newestCacheEntry);
    ret e;
  }
  
  public void set(int idx, int val) {
    checkWritable();
    rangeCheck(idx, size);
    CacheEntry e = loadCell(idx);
    e.data[idx & (pageSize-1)] = val;
    e.dirty = true;
  }
  
  void checkWritable {
    if (!writable) fail("read-only");
  }
  
  public long size() {
    ret size;
  }
  
  double cacheFullPercentage() {
    ret percentRatio(cache.size(), maxCachedPages);
  }
  
  public void ensureSize(int size) {
    this.size = max(this.size, size);
  }
}