import Exception from './../Exception' ; import BitArray from './BitArray' ; import System from './../util/System' ; import Arrays from './../util/Arrays' ; import StringBuilder from './../util/StringBuilder' ; author Sean Owen
 *  author dswitkin google export default class BitMatrix { /**
     * Creates an empty square  BitMatrix .
     *
     *  param dimension /**
     * Creates an empty  BitMatrix .
     *
     *  param width param height public constructor ( private width , private height ? , private rowSize ? , private bits ? ) { if ( undefined === height || null === height ) { height = width ; } this . height = height ; if ( width < 1 || height < 1 ) { throw new Exception ( Exception . IllegalArgumentException , "Both dimensions must be greater than 0" ) ; } if ( undefined === rowSize || null === rowSize ) { rowSize = Math . floor ( ( width + 31 ) / 32 ) ; } this . rowSize = rowSize ; if ( undefined === bits || null === bits ) { this . bits = new Int32Array ( this . rowSize * this . height ) ; } } /**
     * Interprets a 2D array of booleans as a  BitMatrix , where "true" means an "on" bit.
     *
     *  param image return { link public static parseFromBooleanArray ( image ) { const height = image . length ; const width = image [ 0 ] . length ; const bits = new BitMatrix ( width , height ) ; for ( let i = 0 ; i < height ; i ++ ) { const imageI = image [ i ] ; for ( let j = 0 ; j < width ; j ++ ) { if ( imageI [ j ] ) { bits . set ( j , i ) ; } } } return bits ; } public static parseFromString ( stringRepresentation , setString , unsetString ) { if ( stringRepresentation === null ) { throw new Exception ( Exception . IllegalArgumentException , "stringRepresentation cannot be null" ) ; } const bits = new Array < boolean > ( stringRepresentation . length ) ; let bitsPos = 0 ; let rowStartPos = 0 ; let rowLength = - 1 ; let nRows = 0 ; let pos = 0 ; while ( pos < stringRepresentation . length ) { if ( stringRepresentation . charAt ( pos ) === '\n' || stringRepresentation . charAt ( pos ) === '\r' ) { if ( bitsPos > rowStartPos ) { if ( rowLength === - 1 ) { rowLength = bitsPos - rowStartPos ; } else if ( bitsPos - rowStartPos != rowLength ) { throw new Exception ( Exception . IllegalArgumentException , "row lengths do not match" ) ; } rowStartPos = bitsPos ; nRows ++ ; } pos ++ ; } else if ( stringRepresentation . substring ( pos , pos + setString . length ) === setString ) { pos += setString . length ; bits [ bitsPos ] = true ; bitsPos ++ ; } else if ( stringRepresentation . substring ( pos , pos + unsetString . length ) === unsetString ) { pos += unsetString . length ; bits [ bitsPos ] = false ; bitsPos ++ ; } else { throw new Exception ( Exception . IllegalArgumentException , "illegal character encountered: " + stringRepresentation . substring ( pos ) ) ; } } if ( bitsPos > rowStartPos ) { if ( rowLength === - 1 ) { rowLength = bitsPos - rowStartPos ; } else if ( bitsPos - rowStartPos !== rowLength ) { throw new Exception ( Exception . IllegalArgumentException , "row lengths do not match" ) ; } nRows ++ ; } const matrix = new BitMatrix ( rowLength , nRows ) ; for ( let i = 0 ; i < bitsPos ; i ++ ) { if ( bits [ i ] ) { matrix . set ( Math . floor ( i % rowLength ) , Math . floor ( i / rowLength ) ) ; } } return matrix ; } param x param y return public get ( x , y ) { const offset = y * this . rowSize + Math . floor ( x / 32 ) ; return ( ( this . bits [ offset ] >>> ( x & 0x1f ) ) & 1 ) != 0 ; } param x param y public set ( x , y ) { const offset = y * this . rowSize + Math . floor ( x / 32 ) ; this . bits [ offset ] |= ( 1 << ( x & 0x1f ) ) & 0xFFFFFFFF ; } public unset ( x , y ) { const offset = y * this . rowSize + Math . floor ( x / 32 ) ; this . bits [ offset ] &= ~ ( ( 1 << ( x & 0x1f ) ) & 0xFFFFFFFF ) ; } param x param y public flip ( x , y ) { const offset = y * this . rowSize + Math . floor ( x / 32 ) ; this . bits [ offset ] ^= ( ( 1 << ( x & 0x1f ) ) & 0xFFFFFFFF ) ; } param mask public xor ( mask ) { if ( this . width != mask . getWidth ( ) || this . height != mask . getHeight ( ) || this . rowSize != mask . getRowSize ( ) ) { throw new Exception ( Exception . IllegalArgumentException , "input matrix dimensions do not match" ) ; } const rowArray = new BitArray ( Math . floor ( this . width / 32 ) + 1 ) ; const rowSize = this . rowSize ; const bits = this . bits ; for ( let y = 0 , height = this . height ; y < height ; y ++ ) { const offset = y * rowSize ; const row = mask . getRow ( y , rowArray ) . getBitArray ( ) ; for ( let x = 0 ; x < rowSize ; x ++ ) { bits [ offset + x ] ^= row [ x ] ; } } } /**
     * Clears all bits (sets to false).
     */ public clear ( ) { const bits = this . bits ; const max = bits . length ; for ( let i = 0 ; i < max ; i ++ ) { bits [ i ] = 0 ; } } param left param top param width param height public setRegion ( left , top , width , height ) { if ( top < 0 || left < 0 ) { throw new Exception ( Exception . IllegalArgumentException , "Left and top must be nonnegative" ) ; } if ( height < 1 || width < 1 ) { throw new Exception ( Exception . IllegalArgumentException , "Height and width must be at least 1" ) ; } const right = left + width ; const bottom = top + height ; if ( bottom > this . height || right > this . width ) { throw new Exception ( Exception . IllegalArgumentException , "The region must fit inside the matrix" ) ; } const rowSize = this . rowSize ; const bits = this . bits ; for ( let y = top ; y < bottom ; y ++ ) { const offset = y * rowSize ; for ( let x = left ; x < right ; x ++ ) { bits [ offset + Math . floor ( x / 32 ) ] |= ( ( 1 << ( x & 0x1f ) ) & 0xFFFFFFFF ) ; } } } param y param row return public getRow ( y , row ? ) { if ( row === null || row === undefined || row . getSize ( ) < this . width ) { row = new BitArray ( this . width ) ; } else { row . clear ( ) ; } const rowSize = this . rowSize ; const bits = this . bits ; const offset = y * rowSize ; for ( let x = 0 ; x < rowSize ; x ++ ) { row . setBulk ( x * 32 , bits [ offset + x ] ) ; } return row ; } param y param row BitArray to copy from
      public setRow ( y , row ) { System . arraycopy ( row . getBitArray ( ) , 0 , this . bits , y * this . rowSize , this . rowSize ) ; } /**
     * Modifies this {@code BitMatrix} to represent the same but rotated 180 degrees
     */ public rotate180 ( ) { const width = this . getWidth ( ) ; const height = this . getHeight ( ) ; let topRow = new BitArray ( width ) ; let bottomRow = new BitArray ( width ) ; for ( let i = 0 , length = Math . floor ( ( height + 1 ) / 2 ) ; i < length ; i ++ ) { topRow = this . getRow ( i , topRow ) ; bottomRow = this . getRow ( height - 1 - i , bottomRow ) ; topRow . reverse ( ) ; bottomRow . reverse ( ) ; this . setRow ( i , bottomRow ) ; this . setRow ( height - 1 - i , topRow ) ; } } return { code public getEnclosingRectangle ( ) { const width = this . width ; const height = this . height ; const rowSize = this . rowSize ; const bits = this . bits ; let left = width ; let top = height ; let right = - 1 ; let bottom = - 1 ; for ( let y = 0 ; y < height ; y ++ ) { for ( let x32 = 0 ; x32 < rowSize ; x32 ++ ) { const theBits = bits [ y * rowSize + x32 ] ; if ( theBits !== 0 ) { if ( y < top ) { top = y ; } if ( y > bottom ) { bottom = y ; } if ( x32 * 32 < left ) { let bit = 0 ; while ( ( ( theBits << ( 31 - bit ) ) & 0xFFFFFFFF ) === 0 ) { bit ++ ; } if ( ( x32 * 32 + bit ) < left ) { left = x32 * 32 + bit ; } } if ( x32 * 32 + 31 > right ) { let bit = 31 ; while ( ( theBits >>> bit ) === 0 ) { bit -- ; } if ( ( x32 * 32 + bit ) > right ) { right = x32 * 32 + bit ; } } } } } if ( right < left || bottom < top ) { return null ; } return Int32Array . from ( [ left , top , right - left + 1 , bottom - top + 1 ] ) ; } return { code public getTopLeftOnBit ( ) { const rowSize = this . rowSize ; const bits = this . bits ; let bitsOffset = 0 ; while ( bitsOffset < bits . length && bits [ bitsOffset ] == 0 ) { bitsOffset ++ ; } if ( bitsOffset === bits . length ) { return null ; } const y = bitsOffset / rowSize ; let x = ( bitsOffset % rowSize ) * 32 ; const theBits = bits [ bitsOffset ] ; let bit = 0 ; while ( ( ( theBits << ( 31 - bit ) ) & 0xFFFFFFFF ) === 0 ) { bit ++ ; } x += bit ; return Int32Array . from ( [ x , y ] ) ; } public getBottomRightOnBit ( ) { const rowSize = this . rowSize ; const bits = this . bits ; let bitsOffset = bits . length - 1 ; while ( bitsOffset >= 0 && bits [ bitsOffset ] === 0 ) { bitsOffset -- ; } if ( bitsOffset < 0 ) { return null ; } const y = Math . floor ( bitsOffset / rowSize ) ; let x = Math . floor ( bitsOffset % rowSize ) * 32 ; const theBits = bits [ bitsOffset ] ; let bit = 31 ; while ( ( theBits >>> bit ) === 0 ) { bit -- ; } x += bit ; return Int32Array . from ( [ x , y ] ) ; } return public getWidth ( ) { return this . width ; } return public getHeight ( ) { return this . height ; } return public getRowSize ( ) { return this . rowSize ; } public equals ( o ) { if ( ! ( o instanceof BitMatrix ) ) { return false ; } const other = < BitMatrix > o ; return this . width === other . width && this . height === other . height && this . rowSize === other . rowSize && Arrays . equals ( this . bits , other . bits ) ; } public hashCode ( ) { let hash = this . width ; hash = 31 * hash + this . width ; hash = 31 * hash + this . height ; hash = 31 * hash + this . rowSize ; hash = 31 * hash + Arrays . hashCode ( this . bits ) ; return hash ; } return param setString param unsetString return param setString param unsetString param lineSeparator return deprecated call  {@link #toString(String,String)} only, which uses \n line separator always
      public toString ( setString = "x" , unsetString = " " , lineSeparator = "\n" ) { return this . buildToString ( setString , unsetString , lineSeparator ) ; } private buildToString ( setString , unsetString , lineSeparator ) { let result = new StringBuilder ( ) ; result . append ( lineSeparator ) ; for ( let y = 0 , height = this . height ; y < height ; y ++ ) { for ( let x = 0 , width = this . width ; x < width ; x ++ ) { result . append ( this . get ( x , y ) ? setString : unsetString ) ; } result . append ( lineSeparator ) ; } return result . toString ( ) ; } public clone ( ) { return new BitMatrix ( this . width , this . height , this . rowSize , this . bits . slice ( ) ) ; } }