import { IMatrixReader , IMatrixWriter } from "@tiny-calc/nano" ; const x8ToInterlacedX16 = new Array ( 256 ) . fill ( 0 ) . map ( ( value , i ) => { let j = i ; j = ( j | ( j << 4 ) ) & 0x0f0f ; j = ( j | ( j << 2 ) ) & 0x3333 ; j = ( j | ( j << 1 ) ) & 0x5555 ; return j ; } ) ; const byte0 = ( x32 ) => x32 >>> 24 ; const byte1 = ( x32 ) => ( x32 << 8 ) >>> 24 ; const byte2 = ( x32 ) => ( x32 << 16 ) >>> 24 ; const byte3 = ( x32 ) => ( x32 << 24 ) >>> 24 ; const interlaceBitsX16 = ( x16 ) => ( x8ToInterlacedX16 [ byte2 ( x16 ) ] << 16 ) | x8ToInterlacedX16 [ byte3 ( x16 ) ] ; const r0ToMorton16 = ( row ) => ( interlaceBitsX16 ( row ) << 1 ) >>> 0 ; const c0ToMorton16 = ( col ) => interlaceBitsX16 ( col ) >>> 0 ; const r0c0ToMorton2x16 = ( row , col ) => ( r0ToMorton16 ( row ) | c0ToMorton16 ( col ) ) >>> 0 ; type RecurArrayHelper < T > = RecurArray < T > | T ; type RecurArray < T > = RecurArrayHelper < T > [ ] ; /** Undo JSON serialization's coercion of 'undefined' to null. */ const nullToUndefined = < T > ( array ) : RecurArray < T | undefined > => array . map ( ( value ) => { return value === null ? undefined : Array . isArray ( value ) ? nullToUndefined ( value ) : value ; } ) ; type UA < T > = ( T | undefined ) [ ] ; /**
 * A sparse 4 billion x 4 billion array stored as 16x16 tiles.
 */ export class SparseArray2D < T > implements IMatrixReader < T | undefined > , IMatrixWriter < T | undefined > { constructor ( private readonly root = [ undefined ] ) { } public get rowCount ( ) { return 0xFFFFFFFF ; } public get colCount ( ) { return 0xFFFFFFFF ; } public getCell ( row , col ) { const keyHi = r0c0ToMorton2x16 ( row >>> 16 , col >>> 16 ) ; const level0 = this . root [ keyHi ] ; if ( level0 !== undefined ) { const keyLo = r0c0ToMorton2x16 ( row , col ) ; const level1 = level0 [ byte0 ( keyLo ) ] ; if ( level1 !== undefined ) { const level2 = level1 [ byte1 ( keyLo ) ] ; if ( level2 !== undefined ) { const level3 = level2 [ byte2 ( keyLo ) ] ; if ( level3 !== undefined ) { return level3 [ byte3 ( keyLo ) ] ; } } } } return undefined ; } public get matrixProducer ( ) { return undefined as any ; } public setCell ( row , col , value ) { const keyHi = r0c0ToMorton2x16 ( row >>> 16 , col >>> 16 ) ; const keyLo = r0c0ToMorton2x16 ( row , col ) ; const level0 = this . getLevel ( this . root , keyHi ) ; const level1 = this . getLevel ( level0 , byte0 ( keyLo ) ) ; const level2 = this . getLevel ( level1 , byte1 ( keyLo ) ) ; const level3 = this . getLevel ( level2 , byte2 ( keyLo ) ) ; level3 [ byte3 ( keyLo ) ] = value ; } /**
     * Invokes the given 'callback' for each key in a 16 x 16 tile at the indicated row.
     *
     * (Note that 'rowBits' is the appropriate byte from 'r0ToMorton16' for the current
     * level being traversed.)
     */ private forEachKeyInRow ( rowBits , callback ) { for ( let col = 0 ; col < 16 ; col ++ ) { callback ( ( rowBits | c0ToMorton16 ( col ) ) >>> 0 ) ; } } /**
     * Invokes the given 'callback' for each key in a 16 x 16 tile at the indicated col.
     *
     * (Note that 'colBits' is the appropriate byte from 'c0ToMorton16' for the current
     * level being traversed.)
     */ private forEachKeyInCol ( col , callback ) { for ( let row = 0 ; row < 16 ; row ++ ) { callback ( ( r0ToMorton16 ( row ) | col ) >>> 0 ) ; } } /**
     * Invokes the give 'callback' with the next 'level' array for each populated region
     * of the given row  in the 'currentLevel'.
     *
     * (Note that 'rowBits' is the appropriate byte from 'r0ToMorton16' for the current
     * level being traversed.)
     */ private forEachInRow < V extends UA < any > , U extends UA < V > > ( currentLevel , rowBits , callback ) { this . forEachKeyInRow ( rowBits , ( key ) => { const nextLevel = currentLevel [ key ] ; if ( nextLevel !== undefined ) { callback ( nextLevel ) ; } } ) ; } /**
     * Invokes the give 'callback' with the next 'level' array for each populated region
     * of the given col in the 'currentLevel'.
     *
     * (Note that 'colBits' is the appropriate byte from 'c0ToMorton16' for the current
     * level being traversed.)
     */ private forEachInCol < V extends UA < any > , U extends UA < V > > ( currentLevel , colBits , callback ) { this . forEachKeyInCol ( colBits , ( key ) => { const nextLevel = currentLevel [ key ] ; if ( nextLevel !== undefined ) { callback ( nextLevel ) ; } } ) ; } /** Clears the all cells contained within the specified span of rows. */ public clearRows ( rowStart , rowCount ) { const rowEnd = rowStart + rowCount ; for ( let row = rowStart ; row < rowEnd ; row ++ ) { const rowHi = r0ToMorton16 ( row >>> 16 ) ; for ( let colHi = 0 ; colHi < 0x10000 ; colHi ++ ) { const keyHi = ( rowHi | c0ToMorton16 ( colHi ) ) >>> 0 ; const level0 = this . root [ keyHi ] ; if ( level0 !== undefined ) { const rowLo = r0ToMorton16 ( row ) ; this . forEachInRow ( level0 , byte0 ( rowLo ) , ( level1 ) => { this . forEachInRow ( level1 , byte1 ( rowLo ) , ( level2 ) => { this . forEachInRow ( level2 , byte2 ( rowLo ) , ( level3 ) => { this . forEachKeyInRow ( byte3 ( rowLo ) , ( key ) => { level3 [ key ] = undefined ; } ) ; } ) ; } ) ; } ) ; } } } } /** Clears the all cells contained within the specifed span of cols. */ public clearCols ( colStart , colCount ) { const colEnd = colStart + colCount ; for ( let col = colStart ; col < colEnd ; col ++ ) { const colHi = c0ToMorton16 ( col >>> 16 ) ; for ( let rowHi = 0 ; rowHi < 0x10000 ; rowHi ++ ) { const keyHi = ( colHi | r0ToMorton16 ( rowHi ) ) >>> 0 ; const level0 = this . root [ keyHi ] ; if ( level0 !== undefined ) { const colLo = c0ToMorton16 ( col ) ; this . forEachInCol ( level0 , byte0 ( colLo ) , ( level1 ) => { this . forEachInCol ( level1 , byte1 ( colLo ) , ( level2 ) => { this . forEachInCol ( level2 , byte2 ( colLo ) , ( level3 ) => { this . forEachKeyInCol ( byte3 ( colLo ) , ( key ) => { level3 [ key ] = undefined ; } ) ; } ) ; } ) ; } ) ; } } } } private getLevel < T > ( parent , subKey ) { const level = parent [ subKey ] ; return level === undefined ? ( parent [ subKey ] = new Array ( 256 ) . fill ( undefined ) ) : level ; } public snapshot ( ) { return this . root ; } public static load < T > ( data ) { return new SparseArray2D < T > ( nullToUndefined < T > ( data ) as SparseArray2D < T > [ "root" ] ) ; } }