带自定义设置值的 BitArray 和 BitMatrix 类实现

[nuintun]

utils.ts

/**
 * @module utils
 */

export function toBit(value: number): 0 | 1 {
  return (value & 0x01) as 0 | 1;
}

export function toInt32(value: number): number {
  return value | 0;
}

export function getBitMask(value: number): number {
  return 1 << getBitOffset(value);
}

export function getBitOffset(value: number): number {
  return value & 0x1f;
}

BitArray.ts

/**
 * @module BitArray
 */

import { getBitMask, getBitOffset, toBit, toInt32 } from './utils';

const LOAD_FACTOR = 0.75;

function offset(index: number): number {
  return toInt32(index / 32);
}

function makeArray(length: number): Int32Array {
  return new Int32Array(Math.ceil(length / 32));
}

export class BitArray {
  #length: number;
  #bits: Int32Array;

  constructor(length: number = 0) {
    this.#length = length;
    this.#bits = makeArray(length);
  }

  #alloc(length: number): void {
    const bits = this.#bits;

    if (length > bits.length * 32) {
      const array = makeArray(Math.ceil(length / LOAD_FACTOR));

      array.set(bits);

      this.#bits = array;
    }

    this.#length = length;
  }

  public get length(): number {
    return this.#length;
  }

  public get byteLength(): number {
    return Math.ceil(this.#length / 8);
  }

  public set(index: number, bit: 0 | 1 = 1): void {
    const bitOffset = offset(index);
    const bitMask = getBitMask(index);

    if (bit !== 0) {
      this.#bits[bitOffset] |= bitMask;
    } else {
      this.#bits[bitOffset] &= ~bitMask;
    }
  }

  public get(index: number): 0 | 1 {
    return toBit(this.#bits[offset(index)] >>> getBitOffset(index));
  }

  public xor(mask: BitArray): void {
    const bits = this.#bits;
    const maskBits = mask.#bits;
    const length = Math.min(this.#length, mask.#length);

    for (let i = 0; i < length; i++) {
      // The last int could be incomplete (i.e. not have 32 bits in
      // it) but there is no problem since 0 XOR 0 == 0.
      bits[i] ^= maskBits[i];
    }
  }

  public append(array: BitArray): void;
  public append(value: number, length?: number): void;
  public append(value: number | BitArray, length: number = 1): void {
    let index = this.#length;

    if (value instanceof BitArray) {
      length = value.#length;

      this.#alloc(index + length);

      for (let i = 0; i < length; i++) {
        if (value.get(i) !== 0) {
          this.set(index);
        }

        index++;
      }
    } else {
      this.#alloc(index + length);

      for (let i = length - 1; i >= 0; i--) {
        if (toBit(value >>> i) !== 0) {
          this.set(index);
        }

        index++;
      }
    }
  }

  public writeToUint8Array(bitOffset: number, target: Uint8Array, byteOffset: number, byteLength: number): void {
    for (let i = 0; i < byteLength; i++) {
      let byte = 0;

      for (let j = 0; j < 8; j++) {
        if (this.get(bitOffset++) !== 0) {
          byte |= 1 << (7 - j);
        }
      }

      target[byteOffset + i] = byte;
    }
  }

  public clear(): void {
    this.#bits.fill(0);
  }
}

BitMatrix.ts

/**
 * @module BitMatrix
 */

import { getBitMask, getBitOffset, toBit, toInt32 } from './utils';

export class BitMatrix {
  #width: number;
  #height: number;
  #rowSize: number;
  #bits: Int32Array;

  /**
   * @constructor
   * @param width The width of the matrix.
   * @param height The height of the matrix.
   * @param bits The initial bits of the matrix.
   */
  constructor(width: number, height: number, bits?: Int32Array) {
    const rowSize = Math.ceil(width / 32);
    const bitsCapacity = rowSize * height;

    this.#width = width;
    this.#height = height;
    this.#rowSize = rowSize;

    if (bits instanceof Int32Array) {
      if (bits.length !== bitsCapacity) {
        throw new Error(`matrix bits capacity mismatch: ${bitsCapacity}`);
      }

      this.#bits = bits;
    } else {
      this.#bits = new Int32Array(bitsCapacity);
    }
  }

  #offset(x: number, y: number): number {
    return y * this.#rowSize + toInt32(x / 32);
  }

  /**
   * @property width
   * @description The width of the matrix.
   */
  public get width(): number {
    return this.#width;
  }

  /**
   * @property height
   * @description The height of the matrix.
   */
  public get height(): number {
    return this.#height;
  }

  /**
   * @method set
   * @description Set the bit value of the specified coordinate.
   * @param x The x coordinate.
   * @param y The y coordinate.
   * @param bit The bit value to set, default is 1.
   */
  public set(x: number, y: number, bit: 0 | 1 = 1): void {
    const bitMask = 1 << (x & 0x1f);
    const bitOffset = getBitMask(x);

    if (bit !== 0) {
      this.#bits[bitOffset] |= bitMask;
    } else {
      this.#bits[bitOffset] &= ~bitMask;
    }
  }

  /**
   * @method get
   * @description Get the bit value of the specified coordinate.
   * @param x The x coordinate.
   * @param y The y coordinate.
   */
  public get(x: number, y: number): 0 | 1 {
    return toBit(this.#bits[this.#offset(x, y)] >>> getBitOffset(x));
  }

  /**
   * @method flip
   * @description Flip the bit value of the specified coordinate.
   */
  public flip(): void;
  /**
   * @method flip
   * @description Flip the bit value of the specified coordinate.
   * @param x The x coordinate.
   * @param y The y coordinate.
   */
  public flip(x: number, y: number): void;
  public flip(x?: number, y?: number): void {
    if (x != null && y != null) {
      this.#bits[this.#offset(x, y)] ^= getBitMask(x);
    } else {
      const bits = this.#bits;
      const { length } = bits;

      for (let i = 0; i < length; i++) {
        bits[i] = ~bits[i];
      }
    }
  }

  /**
   * @method clone
   * @description Clone the bit matrix.
   */
  public clone(): BitMatrix {
    return new BitMatrix(this.#width, this.#height, new Int32Array(this.#bits));
  }

  /**
   * @method setRegion
   * @description Set the bit value of the specified region.
   * @param left The left coordinate.
   * @param top The top coordinate.
   * @param width The width to set.
   * @param height The height to set.
   * @param bit The bit value to set, default is 1.
   */
  public setRegion(left: number, top: number, width: number, height: number, bit: 0 | 1 = 1): void {
    const bits = this.#bits;
    const right = left + width;
    const bottom = top + height;
    const rowSize = this.#rowSize;

    for (let y = top; y < bottom; y++) {
      const offset = y * rowSize;

      for (let x = left; x < right; x++) {
        const bitMask = getBitMask(x);
        const bitOffset = offset + toInt32(x / 32);

        if (bit !== 0) {
          bits[bitOffset] |= bitMask;
        } else {
          bits[bitOffset] &= ~bitMask;
        }
      }
    }
  }
}