final sclass ChunkedLongList extends RandomAccessAbstractList<Long> {

  int chunkShift = 16; // => chunkSize = 65536

  new ArrayList<long[]> chunks;

  int actualChunks; // roughly keep track of chunk list's internal capacity so we can shrink in time

  int size;

  public void add(long i) {

    ensureCapacityInternal(size+1);

    set(size, i);

    ++size;

  }

  public Long set(int i, Long value) {

    ret set(i, (long) value);

  }

  public long set(int i, long value) {

    long[] chunk = chunks.get(i >> chunkShift);

    int idx = i & (chunkSize()-1);

    long old = chunk[idx];

    chunk[idx] = value;

    ret old;

  }

  public bool add(Long i) {

    add((long) i);

    true;

  }

  public int size() { ret size; }

  public Long get(int i) {

    ret getPrimitive(i);

  }

  public long getPrimitive(int i) {

    if (i >= 0 && i < size) ret chunks.get(i >> chunkShift)[i & (chunkSize()-1)];

    throw new IndexOutOfBoundsException(i + "/" + size);

  }

  void ensureCapacityInternal(int minCapacity) {

    while (l(chunks) << chunkShift < minCapacity) {

      chunks.add(new long[chunkSize()]);

      actualChunks = max(actualChunks, l(chunks));

    }

  }

  long[] toLongArray() {

    long[] a = new long[size];

    int i = 0;

    for (long[] chunk : chunks) {

      System.arraycopy(chunk, 0, a, i, min(chunk.length, size-i));

      i += chunk.length;

    }

    ret a;

  }

  int chunkSize() { ret 1 << chunkShift; }

  void truncateAt(int idx) {

    size = idx;

    while (size <= (l(chunks)-1) << chunkShift)

      popLast(chunks);

    if (l(chunks)*2 < actualChunks) {

      chunks.trimToSize();

      actualChunks = l(chunks);

    }

  }

}