!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);

  }

}