// Note: Optimizes only when you call optimize or optimizeBlock

persistable sclass BlockOptimizedIntMatrix extends AbstractMatrix<Int> {

  // Each block is square with side length being a power of two

  // (i.e. blockSize = 1 << blockShift)

  int blockShift, blockSize;

  int bw, bh; // number of block cols/block rows

  int[][] fullBlocks; // if entry != null, it's a detailed block

  int[] simpleBlocks; // if fullBlocks entry is null, find block value here

  *(int *w, int *h, int *blockShift) {

    blockSize = 1 << blockShift;

    bw = rshift_ceil(w, blockShift);

    bh = rshift_ceil(h, blockShift);

    simpleBlocks = new int[bw*bh];

    fullBlocks = new int[bw*bh][];

  }

  public Int get(int x, int y) {

    int bx = x >> blockShift, by = y >> blockShift;

    int iBlock = by*bw+bx;

    int[] block = fullBlocks[iBlock];

    if (block != null)

      ret block[x & (blockSize-1) | ((y & (blockSize-1)) << blockShift)];

    ret simpleBlocks[iBlock];

  }

  public void set(int x, int y, Int a) {

    int bx = x >> blockShift, by = y >> blockShift;

    int iBlock = by*bw+bx;

    int[] block = fullBlocks[iBlock];

    if (block == null) {

      int val = simpleBlocks[iBlock];

      if (val == a) ret; // no change

      // convert to full block

      block = new int[1 << (blockShift*2)];

      fullBlocks[iBlock] = block;

      fillArray(block, val);

      simpleBlocks[iBlock] = 0; // set irrelevant array entry to 0 for beauty reasons

    }

    block[x & (blockSize-1) | ((y & (blockSize-1)) << blockShift)] = a;

  }

  void optimizeBlock(int iBlock) {

    int[] block = fullBlocks[iBlock];

    if (block == null) ret; // already optimized

    int val = block[0];

    for (int i = 1; i < block.length; i++)

      if (block[i] != val)

        ret; // Can't optimize

    // Can optimize!

    simpleBlocks[iBlock] = val;

    fullBlocks[iBlock] = null;

  }

  // optimize all blocks

  void optimize {

    int n = simpleBlocks.length;

    for i to n:

      optimizeBlock(i);

  }

}