Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

69
LINES

< > BotCompany Repo | #1035234 // BlockOptimizedIntMatrix - Matrix<Int> stored in blocks of a fixed size (very compact if an entire block is one value, gracefully degrades otherwise)

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (8681L/49K).

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

Author comment

Began life as a copy of #1033112

download  show line numbers  debug dex  old transpilations   

Travelled to 4 computer(s): bhatertpkbcr, ekrmjmnbrukm, mowyntqkapby, mqqgnosmbjvj

No comments. add comment

Snippet ID: #1035234
Snippet name: BlockOptimizedIntMatrix - Matrix<Int> stored in blocks of a fixed size (very compact if an entire block is one value, gracefully degrades otherwise)
Eternal ID of this version: #1035234/14
Text MD5: 4c1fdbf19bffd3977b4ad546058b8db5
Transpilation MD5: 61c0caaecbcc7c194e9be38ed5e41a6f
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2022-04-20 20:55:40
Source code size: 2109 bytes / 69 lines
Pitched / IR pitched: No / No
Views / Downloads: 185 / 277
Version history: 13 change(s)
Referenced in: [show references]