// all sizes+addresses are in ints (4 bytes)

sclass ManagedIntObjects_indirect implements IIntMemory_indirect {
  replace Addr with int.
  replace BoxedAddr with Int.
  
  int[] mem = new int[0];
  new FreeList freeList;
  bool collecting, compacting; // GC phases

  *() {
    assertEquals(0, alloc(reservedSpaceAtBeginning())); // so 0 is usable as the null pointer
  }
  
  *(int[] *mem) {}
  
  // overridable
  public long size() { ret mem.length; }
  public int get(Addr i) { ret mem[i]; }
  public void set(Addr i, int val) { mem[i] = val; }
  
  swappable void onMemorySizeChanged() {}
  
  void ensureCapacity(int size) {
    if (memorySize() < size)
      setMemorySize(roundUpToPowerOfTwo(size));
  }
  
  void setMemorySize(int newSize) {
    int size = memorySize();
    if (newSize == size) ret;
    if (newSize < size) unimplemented("Shrinking memory");
    print("New memory size: " + newSize);
    mem = resizeIntArray(mem, newSize);
    free(size, newSize-size);
    onMemorySizeChanged();
  }
  
  void growMemory() {
    setMemorySize(max(1, memorySize()*2));
  }
  
  // all allocated ranges are filled with zero
  int alloc(int length) {
    IntRange r;
    while ((r = freeList.findFreeSpace(length)) == null) {
      print("No free space for length " + length + " - growing");
      growMemory();
    }
    
    freeList.remove(IntRange(r.start, r.start+length));
    ret r.start;
  }
  
  void free(int start, int length) {
    if (length == 0) ret;
    deb()?.print("Freeing " + start + " (l=" + length + ")");
    freeList.add(IntRange(start, start+length));
    fillMem(start, start+length, 0);
  }
  
  void fillMem(int start, int end, int value) {
    Arrays.fill(mem, start, end, value);
  }
  
  final int memorySize() { ret mem.length; }
  final public int read(Addr i) { ret get(i); }
  final void write(Addr i, int val) { set(i, val); }
  
  // words a pointer requires
  int sizeOfPointer() { ret 1; }
  int wordSizeInBytes() { ret 4; }
  
  public Addr nullPtr() { ret 0; }
  
  // convenience pointer array handling (memory layout: length + data)
  
  L<BoxedAddr> pointerArray(Addr addr) {
    if (addr == 0) null;
    int size = get(addr);
    ret new RandomAccessAbstractList<BoxedAddr>() {
      public int size() { ret size; }
      public BoxedAddr get(int i) { rangeCheck(i, size); ret read(addr+1+i); }
      public Int set(int i, Int val) { rangeCheck(i, size); Int old = get(i); write(addr+1+i, val); ret old; }
    };
  }
  
  Addr newPointerArray(int size) {
    deb()?.printVars("newIntArray", +size);
    Addr a = alloc(size+1);
    set(a, size);
    ret a;
  }
  
  void freePointerArray aka freeIntArray(Addr a) {
    if (a == 0) ret;
    deb()?.print("freePointerArray at " + a);
    free(a, read(a)+1);
  }
  
  Addr newIntArray(int[] array) {
    if (array == null) ret 0;
    int n = l(array);
    deb()?.printVars("newIntArray", +n);
    Addr ptr = alloc(n+1);
    set(ptr, n);
    for i to n:
      set(ptr+1+i, array[i]);
    ret ptr;
  }
  
  // a can be nullPtr(), then we just make a new array
  Addr resizePointerArray(Addr a, int newSize) {
    deb()?.printVars("resizePointerArray", +a, +newSize);
    if (a == 0) ret newPointerArray(newSize);
    int oldSize = get(a);
    if (oldSize == newSize) ret a;
    
    Addr a2 = realloc(a, oldSize+1, newSize+1);
    set(a2, newSize);
    ret a2;
  }
  
  // a can be nullPtr(), then we just make a new array
  Addr realloc(Addr a, int oldSize, int newSize) {
    deb()?.printVars("realloc", +a, +oldSize, +newSize);
    if (a == 0) ret alloc(newSize);
    if (oldSize == newSize) ret a;
    if (oldSize > newSize) {
      free(a+newSize, oldSize-newSize);
      ret a;
    }
    // newSize is bigger than oldSize
    // Try growing.
    
    IntRange r = new(a+oldSize, a+newSize);
    if (freeList.canRemove(r)) {
      // Great! Grow it and we're done
      deb()?.print("Chunk grown");
      freeList.remove(r);
      ret a;
    }
    
    // We have to move the whole thing
    deb()?.printVars("realloc copy", +newSize);
    Addr a2 = alloc(newSize);
    memCopy(a, a2, oldSize);
    deb()?.printVars("realloc free old, returning", +a2);
    free(a, oldSize);
    ret a2;
  }
  
  void memCopy(int src, int dest, int n) {
    arraycopy(mem, src, mem, dest, n);
  }
  

  
  // even more convenient typed object array handling as List
  
  <A extends AbstractManagedObject> L<A> objectArray(Addr addr,
    IF1<BoxedAddr, A> wrapPointer) {
    ret convertListElementsBothWays(
      wrapPointer,
      element -> element.addr,
      pointerArray(addr));
  }
  
  int totalFree() { ret freeList.totalFree(); }
  
  int reservedSpaceAtBeginning() { ret 1; }
  
  void copyReservedArea(int[] newMem) { newMem[0] = get(0); }
  
  void collectAndCompact(IManagedObject rootObject, ManagedIntObjects_v1_Collector collector default new ManagedIntObjects_v1_Collector(this)) {
    collecting = true;
    if (rootObject != null)
      rootObject.scanForCollection(collector);
    compacting = true;
    collector.collectAndCompact();
    compacting = false;
    collecting = false;
  }
  
  bool collecting() { ret collecting; }
  bool compacting() { ret compacting; }
  
  void printStats {
    print("Managed memory size: " + toM(size()*(long) wordSizeInBytes()) + " MB, free: " + ratioToIntPercent(freeList.totalFree(), size()) + "%");
  }
  
  // +1, actually
  int highestUsedWord() {
    IntRange r = freeList.highestFreeRange();
    ret r != null && r.end == size() ? r.start : (int) size();
  }
  
  void saveToFile(File f) {
    // only save used part
    stream2file(IntArrayInputStream_littleEndian(mem, 0, highestUsedWord()), f);
    printFileInfo(f);
  }
  
  // we use the reserved int for a user-defined value to bootstrap
  // the system
  void setRootField(int val) {
    set(0, val);
  }
  
  int getRootField() {
    ret get(0);
  }
  
  int[] readIntArray(BoxedAddr ptr) {
    if (ptr == 0) null;
    int n = mem[ptr++];
    int[] a = new[n];
    arraycopy(mem, ptr, a, 0, n);
    ret a;
  }
  
  Addr newString(S s) {
    if (s == null) ret 0;
    byte[] array = toUtf8(s);
    int[] ints = intArrayFromBytes_littleEndian_flexLength(array);
    Addr ptr = alloc(l(ints)+1);
    for i over ints:
      set(ptr+1+i, ints[i]);
    set(ptr, l(array)^0x80000000);
    ret ptr;
  }
  
  S readString(Addr addr) {
    if (addr == 0) null;
    int n = get(addr) ^ 0x80000000;
    int[] ints = new[(n+3)/4];
    for i over ints:
      ints[i] = get(addr+1+i);
    byte[] bytes = intArrayToBytes_littleEndian_flexLength(ints, n);
    ret fromUtf8(bytes);
  }
  
  // cycle from "disk" (memory)
  selfType rotate() {
    ret new ManagedIntObjects_v1(mem);
  }
}

Began life as a copy of #1029226