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