2d-bit-array

A package for afficiently managing a 2D bit-array (also known as a bit-mask, bit-map, bit-string, or bit-vector). It can be used for any 2D array of flags but is especially suitable for working with images where the flags could be mapped to pixel transparencies.

Installation

Install using your package manager of choice:

pnpm i 2d-bit-array

Usage

BitArray

Create an instance of the BitArray class with the desired width and height:

import { BitArray } from '2d-bit-array'

const bv = new BitArray(320, 240)

The flag for each x, and y coordinate is stored as a single bit inside a Uint8Array which will always be the minimum size necssary to store all the possible flags. Use get(x, y) to check the flag value, set(x, y) to set it to true, clear(x, y) to set it to false, and toggle(x, y) to invert the current value.

The BitArray instance has an empty and length property to indicate if any flags are set, and how many are set. The set flags can be iterated:

for (const [x, y] of bv) {
  // do something with x & y
}

The .trim() method returns the smallest instance that bounds the set flags, with the x and y offsets of the BitArray itself set. So given a bit vector:

import { BitArray } from '2d-bit-array'

const bv = new BitArray(8, 8)
bv.set(2, 4)
bv.set(5, 6)

const trimmed = bv.trim()

// trimmed will be width = 4, height = 3, offset x = 2 and y =4
// the same flags can still be checked:

expect(trimmed.get(2, 4)).true
expect(trimmed.get(5, 6)).true

// iterating the flags will still return the same [2, 4] and [5, 6] coordinates

The reason this is desirable is for serialization, when the minimal amount of data can be stored or transmitted. When .toJSON() is used, the a trimmed version is returned automatically and the Uint8Array data encoded to a bas64 string. Use BitArray.fromJSON(value) to decode a JSON serialized version.

The flags from one BitArray can be added to another. So the previous trimmed values could be added to another instance to get back to the original state:

const bv2 = new BitArray(8, 8)
bv2.add(trimmed)

// bv2 now matches the original bv instance

Use .reset() to clear all the flags in an instance.

ChangeSet

Sometimes you need to track not just what has been set, but also what has been cleared. i.e. to store the difference between one set of flags and another. For this you can use the ChangeSet class. It's effectively just two BitArray instances, one to store added flags and one to store removed flags. Reversing an operation is slightly different - if you set a flag on a ChangeSet (which would set the added BitArray coordinate to true) and then clear it, it would simply delete the flag from the added BitArray. Likewise, clearing a flag would set the removed BitArray coordinate, and then setting it would clear the flag.

Only if the next result is to set or clear a flag will a flag be set in the added or removed BitArray layers.

The same empty and length properties indicate if any, and how many, flags are set.

Checking a flag using get(x, y) returns either the Added, Removed, or Unchanged state of the coordinate.

Iterating the flags returns an object containing the x and y properties plus the changed property (Added or Removed).

The ChangeSet can be applied to a BitArray to update it using the .applyTo(bv: BitArray) method, with any Added or Removed coordinated being applied as appropriate to set or clear the existing flags.

Any use of .toJSON will return a compact representation with empty layers marked as null for maximum space saving. Use ChangeSet.fromJSON to decode a JSON serialized version.

Image

The applyToImage method allows a BitArray to be applied to an ImageData instance. The transparency for a pixel will be set based on whether the matching flag coordinate is true (opaque) or false (transparent).