feat(bitfield): add toggleAt(), setRange(), update ctor

- update BitField ctor to accept bit string or bool array - add size check in resize(), bail if not different - add setRange() for BitField - add toggleAt() for BitField & BitMatrix - add bitField() and bitMatrix() factory fns - extract common toString()
thi-ng · Mar 5, 2020 · 6ed20c1 · 6ed20c1
1 parent 300fe2b
commit 6ed20c1
Show file tree

Hide file tree

Showing 3 changed files with 92 additions and 16 deletions.
diff --git a/packages/bitfield/src/bitfield.ts b/packages/bitfield/src/bitfield.ts
@@ -1,17 +1,19 @@
 import { align } from "@thi.ng/binary";
-import { B32 } from "@thi.ng/strings";
+import { toString } from "./util";
 
 /**
- * 1D bit field, backed by a Uint32Array. Size is always a multiple of
- * 32.
+ * 1D bit field, backed by a Uint32Array. Hence size is always rounded
+ * up to a multiple of 32.
  */
 export class BitField {
     data: Uint32Array;
     n: number;
 
-    constructor(n: number) {
-        this.n = align(n, 32);
+    constructor(bits: number | string | ArrayLike<boolean>) {
+        const isNumber = typeof bits === "number";
+        this.n = align(isNumber ? <number>bits : (<any>bits).length, 32);
         this.data = new Uint32Array(this.n >>> 5);
+        !isNumber && this.setRange(0, <any>bits);
     }
 
     /**
@@ -22,6 +24,7 @@ export class BitField {
      */
     resize(n: number) {
         n = align(n, 32);
+        if (n === this.n) return this;
         const dest = new Uint32Array(n >>> 5);
         dest.set(this.data.slice(0, dest.length));
         this.data = dest;
@@ -42,7 +45,7 @@ export class BitField {
     /**
      * Enables or disables bit `n`. Returns a non-zero value if the bit
      * was previously enabled. No bounds checking.
-     * .
+     *
      * @param n - bit number
      * @param v - new bit value
      */
@@ -58,7 +61,47 @@ export class BitField {
         return r;
     }
 
+    /**
+     * Sets bits from `start` index with given `values`. No bounds
+     * checking.
+     *
+     * @param start -
+     * @param vals -
+     */
+    setRange(start: number, vals: string | ArrayLike<boolean>) {
+        const isString = typeof vals === "string";
+        for (let i = 0, n = vals.length; i < n; i++) {
+            this.setAt(
+                start + i,
+                isString
+                    ? (<string>vals)[i] === "1"
+                    : (<ArrayLike<boolean>>vals)[i]
+            );
+        }
+    }
+
+    /**
+     * Inverts bit `n`. Returns a non-zero value if the bit was
+     * previously enabled. No bounds checking.
+     *
+     * @param n - bit number
+     */
+    toggleAt(n: number) {
+        const id = n >>> 5;
+        const mask = 0x80000000 >>> (n & 31);
+        const r = this.data[id] & mask;
+        if (r) {
+            this.data[id] &= ~mask;
+        } else {
+            this.data[id] |= mask;
+        }
+        return r;
+    }
+
     toString() {
-        return [...this.data].map(B32).join("");
+        return toString(this.data);
     }
 }
+
+export const bitField = (bits: number | string | ArrayLike<boolean>) =>
+    new BitField(bits);
diff --git a/packages/bitfield/src/bitmatrix.ts b/packages/bitfield/src/bitmatrix.ts
@@ -1,21 +1,21 @@
 import { align } from "@thi.ng/binary";
-import { B32 } from "@thi.ng/strings";
+import { toString } from "./util";
 
 /**
- * MxN row-major 2D bit matrix, backed by a Uint32Array. Width is always
- * a multiple of 32.
+ * MxN row-major 2D bit matrix, backed by a Uint32Array. Hence the width
+ * (number of columns) is always rounded up to a multiple of 32.
  */
 export class BitMatrix {
     data: Uint32Array;
     stride: number;
     m: number;
     n: number;
 
-    constructor(m: number, n = m) {
-        this.m = m;
-        this.n = n = align(n, 32);
-        this.stride = n >>> 5;
-        this.data = new Uint32Array(m * this.stride);
+    constructor(rows: number, cols = rows) {
+        this.m = rows;
+        this.n = cols = align(cols, 32);
+        this.stride = cols >>> 5;
+        this.data = new Uint32Array(rows * this.stride);
     }
 
     /**
@@ -27,6 +27,7 @@ export class BitMatrix {
      */
     resize(m: number, n = m) {
         n = align(n, 32);
+        if (m === this.m && n === this.n) return this;
         const dstride = n >>> 5;
         const sstride = this.stride;
         const w = Math.min(dstride, sstride);
@@ -79,11 +80,33 @@ export class BitMatrix {
         return r;
     }
 
+    /**
+     * Inverts bit at `m,n` (row major). Returns a non-zero value if the
+     * bit was previously enabled. No bounds checking.
+     *
+     * @param m - row
+     * @param n - column
+     */
+    toggleAt(m: number, n: number) {
+        const id = (n >>> 5) + m * this.stride;
+        const mask = 0x80000000 >>> (n & 31);
+        const r = this.data[id] & mask;
+        if (r) {
+            this.data[id] &= ~mask;
+        } else {
+            this.data[id] |= mask;
+        }
+        return r;
+    }
+
     toString() {
         const res: string[] = [];
         for (let i = 0, j = 0, s = this.stride; i < this.m; i++, j += s) {
-            res.push([...this.data.slice(j, j + s)].map(B32).join(""));
+            res.push(toString(this.data.subarray(j, j + s)));
         }
         return res.join("\n");
     }
 }
+
+export const bitMatrix = (rows: number, cols = rows) =>
+    new BitMatrix(rows, cols);
diff --git a/packages/bitfield/src/util.ts b/packages/bitfield/src/util.ts
@@ -0,0 +1,10 @@
+import { B32 } from "@thi.ng/strings";
+
+/**
+ * Converts 1D bitfield to binary string.
+ *
+ * @param data -
+ *
+ * @internal
+ */
+export const toString = (data: Uint32Array) => [...data].map(B32).join("");