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

  }

}