bitmap.ts

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])
  })
})