Skip to content

Instantly share code, notes, and snippets.

@menduz
Created March 15, 2023 20:30
Show Gist options
  • Save menduz/425bbbdb72aa4fe003a5847a9ea083d2 to your computer and use it in GitHub Desktop.
Save menduz/425bbbdb72aa4fe003a5847a9ea083d2 to your computer and use it in GitHub Desktop.
const BITS = 32
export function queryBit(data: Uint32Array, index: number) {
const mask = 1 << (index % BITS)
return (data[(index / BITS) | 0] & mask) != 0
}
export function turnOnBit(data: Uint32Array, index: number) {
const mask = 1 << (index % BITS)
return (data[(index / BITS) | 0] |= mask)
}
export function turnOffBit(data: Uint32Array, index: number) {
const mask = 1 << (index % BITS)
return (data[(index / BITS) | 0] &= ((-1 ^ mask) >>> 0))
}
export class BitMap {
readonly data: Uint32Array
maxDataValue = 0
constructor(public readonly totalBits: number) {
this.data = new Uint32Array(Math.ceil(totalBits / BITS))
}
has(index: number): boolean {
return queryBit(this.data, index)
}
add(index: number): void {
turnOnBit(this.data, index)
const slot = ((index / 32) | 0) + 1
if (slot > this.maxDataValue) {
this.maxDataValue = slot
}
}
remove(index: number): void {
const slotValue = turnOffBit(this.data, index)
const slot = ((index / 32) | 0) + 1
if (slot === this.maxDataValue && !slotValue) {
for (let index = this.maxDataValue; index >= 0; index--) {
if (this.data[index]) {
this.maxDataValue = index + 1
return
}
}
this.maxDataValue = 0
}
}
*[Symbol.iterator]() {
for (let table = 0; table < this.maxDataValue; table++) {
const values = this.data[table];
if (values) {
for (let bit = 0; bit < BITS; bit++) {
if ((1 << bit) & values) {
yield table * BITS + bit
}
}
}
}
}
toString() {
return `BitMap[${Array.from(this).join(',')}]`
}
}
import {BitMap} from '../../../src/lib/decentraland/ByteBuffer/bitmap'
describe('tests for permutation helper', () => {
const bm = new BitMap(10000000)
it('empty', () => {
const result = Array.from(bm)
expect(result).toEqual([])
expect(bm.maxDataValue).toEqual(0)
})
it('add 1', () => {
bm.add(1)
const result = Array.from(bm)
expect(result).toEqual([1])
expect(bm.maxDataValue).toEqual(1)
})
it('add 64', () => {
bm.add(64)
const result = Array.from(bm)
expect(bm.maxDataValue).toEqual(3)
expect(result).toEqual([1, 64])
})
it('remove 64', () => {
bm.remove(64)
const result = Array.from(bm)
expect(bm.maxDataValue).toEqual(1)
expect(result).toEqual([1])
})
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment