import IllegalArgumentException from '../IllegalArgumentException' ; import Arrays from '../util/Arrays' ; import Integer from '../util/Integer' ; import System from '../util/System' ; author Sean Owen
  export default class BitArray { private size : number ; private bits : Int32Array ; public constructor ( size ? , bits ? ) { if ( undefined === size ) { this . size = 0 ; this . bits = new Int32Array ( 1 ) ; } else { this . size = size ; if ( undefined === bits || null === bits ) { this . bits = BitArray . makeArray ( size ) ; } else { this . bits = bits ; } } } public getSize ( ) { return this . size ; } public getSizeInBytes ( ) { return Math . floor ( ( this . size + 7 ) / 8 ) ; } private ensureCapacity ( size ) { if ( size > this . bits . length * 32 ) { const newBits = BitArray . makeArray ( size ) ; System . arraycopy ( this . bits , 0 , newBits , 0 , this . bits . length ) ; this . bits = newBits ; } } param i return public get ( i ) { return ( this . bits [ Math . floor ( i / 32 ) ] & ( 1 << ( i & 0x1F ) ) ) !== 0 ; } param i public set ( i ) { this . bits [ Math . floor ( i / 32 ) ] |= 1 << ( i & 0x1F ) ; } param i public flip ( i ) { this . bits [ Math . floor ( i / 32 ) ] ^= 1 << ( i & 0x1F ) ; } param from return see public getNextSet ( from ) { const size = this . size ; if ( from >= size ) { return size ; } const bits = this . bits ; let bitsOffset = Math . floor ( from / 32 ) ; let currentBits = bits [ bitsOffset ] ; currentBits &= ~ ( ( 1 << ( from & 0x1F ) ) - 1 ) ; const length = bits . length ; while ( currentBits === 0 ) { if ( ++ bitsOffset === length ) { return size ; } currentBits = bits [ bitsOffset ] ; } const result = ( bitsOffset * 32 ) + Integer . numberOfTrailingZeros ( currentBits ) ; return result > size ? size : result ; } param from return see public getNextUnset ( from ) { const size = this . size ; if ( from >= size ) { return size ; } const bits = this . bits ; let bitsOffset = Math . floor ( from / 32 ) ; let currentBits = ~ bits [ bitsOffset ] ; currentBits &= ~ ( ( 1 << ( from & 0x1F ) ) - 1 ) ; const length = bits . length ; while ( currentBits === 0 ) { if ( ++ bitsOffset === length ) { return size ; } currentBits = ~ bits [ bitsOffset ] ; } const result = ( bitsOffset * 32 ) + Integer . numberOfTrailingZeros ( currentBits ) ; return result > size ? size : result ; } param i param newBits public setBulk ( i , newBits ) { this . bits [ Math . floor ( i / 32 ) ] = newBits ; } param start param end public setRange ( start , end ) { if ( end < start || start < 0 || end > this . size ) { throw new IllegalArgumentException ( ) ; } if ( end === start ) { return ; } end -- ; const firstInt = Math . floor ( start / 32 ) ; const lastInt = Math . floor ( end / 32 ) ; const bits = this . bits ; for ( let i = firstInt ; i <= lastInt ; i ++ ) { const firstBit = i > firstInt ? 0 : start & 0x1F ; const lastBit = i < lastInt ? 31 : end & 0x1F ; const mask = ( 2 << lastBit ) - ( 1 << firstBit ) ; bits [ i ] |= mask ; } } /**
     * Clears all bits (sets to false).
     */ public clear ( ) { const max = this . bits . length ; const bits = this . bits ; for ( let i = 0 ; i < max ; i ++ ) { bits [ i ] = 0 ; } } param start param end param value return throws public isRange ( start , end , value ) { if ( end < start || start < 0 || end > this . size ) { throw new IllegalArgumentException ( ) ; } if ( end === start ) { return true ; } end -- ; const firstInt = Math . floor ( start / 32 ) ; const lastInt = Math . floor ( end / 32 ) ; const bits = this . bits ; for ( let i = firstInt ; i <= lastInt ; i ++ ) { const firstBit = i > firstInt ? 0 : start & 0x1F ; const lastBit = i < lastInt ? 31 : end & 0x1F ; const mask = ( 2 << lastBit ) - ( 1 << firstBit ) & 0xFFFFFFFF ; if ( ( bits [ i ] & mask ) !== ( value ? mask : 0 ) ) { return false ; } } return true ; } public appendBit ( bit ) { this . ensureCapacity ( this . size + 1 ) ; if ( bit ) { this . bits [ Math . floor ( this . size / 32 ) ] |= 1 << ( this . size & 0x1F ) ; } this . size ++ ; } param value { code param numBits public appendBits ( value , numBits ) { if ( numBits < 0 || numBits > 32 ) { throw new IllegalArgumentException ( 'Num bits must be between 0 and 32' ) ; } this . ensureCapacity ( this . size + numBits ) ; for ( let numBitsLeft = numBits ; numBitsLeft > 0 ; numBitsLeft -- ) { this . appendBit ( ( ( value >> ( numBitsLeft - 1 ) ) & 0x01 ) === 1 ) ; } } public appendBitArray ( other ) { const otherSize = other . size ; this . ensureCapacity ( this . size + otherSize ) ; for ( let i = 0 ; i < otherSize ; i ++ ) { this . appendBit ( other . get ( i ) ) ; } } public xor ( other ) { if ( this . size !== other . size ) { throw new IllegalArgumentException ( 'Sizes don\'t match' ) ; } const bits = this . bits ; for ( let i = 0 , length = bits . length ; i < length ; i ++ ) { bits [ i ] ^= other . bits [ i ] ; } } param bitOffset param array array to write into. Bytes are written most-significant byte first. This is the opposite
     *  of the internal representation, which is exposed by  {@link #getBitArray()} param offset param numBytes public toBytes ( bitOffset , array , offset , numBytes ) { for ( let i = 0 ; i < numBytes ; i ++ ) { let theByte = 0 ; for ( let j = 0 ; j < 8 ; j ++ ) { if ( this . get ( bitOffset ) ) { theByte |= 1 << ( 7 - j ) ; } bitOffset ++ ; } array [ offset + i ] = theByte ; } } return public getBitArray ( ) { return this . bits ; } /**
     * Reverses all bits in the array.
     */ public reverse ( ) { const newBits = new Int32Array ( this . bits . length ) ; const len = Math . floor ( ( this . size - 1 ) / 32 ) ; const oldBitsLen = len + 1 ; const bits = this . bits ; for ( let i = 0 ; i < oldBitsLen ; i ++ ) { let x = bits [ i ] ; x = ( ( x >> 1 ) & 0x55555555 ) | ( ( x & 0x55555555 ) << 1 ) ; x = ( ( x >> 2 ) & 0x33333333 ) | ( ( x & 0x33333333 ) << 2 ) ; x = ( ( x >> 4 ) & 0x0f0f0f0f ) | ( ( x & 0x0f0f0f0f ) << 4 ) ; x = ( ( x >> 8 ) & 0x00ff00ff ) | ( ( x & 0x00ff00ff ) << 8 ) ; x = ( ( x >> 16 ) & 0x0000ffff ) | ( ( x & 0x0000ffff ) << 16 ) ; newBits [ len - i ] = x ; } if ( this . size !== oldBitsLen * 32 ) { const leftOffset = oldBitsLen * 32 - this . size ; let currentInt = newBits [ 0 ] >>> leftOffset ; for ( let i = 1 ; i < oldBitsLen ; i ++ ) { const nextInt = newBits [ i ] ; currentInt |= nextInt << ( 32 - leftOffset ) ; newBits [ i - 1 ] = currentInt ; currentInt = nextInt >>> leftOffset ; } newBits [ oldBitsLen - 1 ] = currentInt ; } this . bits = newBits ; } private static makeArray ( size ) { return new Int32Array ( Math . floor ( ( size + 31 ) / 32 ) ) ; } public equals ( o ) { if ( ! ( o instanceof BitArray ) ) { return false ; } const other = < BitArray > o ; return this . size === other . size && Arrays . equals ( this . bits , other . bits ) ; } public hashCode ( ) { return 31 * this . size + Arrays . hashCode ( this . bits ) ; } public toString ( ) { let result = '' ; for ( let i = 0 , size = this . size ; i < size ; i ++ ) { if ( ( i & 0x07 ) === 0 ) { result += ' ' ; } result += this . get ( i ) ? 'X' : '.' ; } return result ; } public clone ( ) { return new BitArray ( this . size , this . bits . slice ( ) ) ; } }