feat(transducers): add partitionBits() xform & tests

thi-ng · Aug 8, 2018 · a5e2c28 · a5e2c28
1 parent 6eb97b5
commit a5e2c28
Show file tree

Hide file tree

Showing 3 changed files with 90 additions and 0 deletions.
diff --git a/packages/transducers/src/index.ts b/packages/transducers/src/index.ts
@@ -68,6 +68,7 @@ export * from "./xform/multiplex-obj";
 export * from "./xform/noop";
 export * from "./xform/pad-last";
 export * from "./xform/page";
+export * from "./xform/partition-bits";
 export * from "./xform/partition-by";
 export * from "./xform/partition-of";
 export * from "./xform/partition-sort";

diff --git a/packages/transducers/src/xform/partition-bits.ts b/packages/transducers/src/xform/partition-bits.ts
@@ -0,0 +1,56 @@
+import { Transducer } from "../api";
+import { isReduced } from "../reduced";
+
+/**
+ * Transducer.
+ *
+ * @param fn
+ * @param stateful
+ */
+export function partitionBits(n: number, wordSize = 8): Transducer<number, number> {
+    return ([init, complete, reduce]) => {
+        const maxb = wordSize - n;
+        const m1 = (1 << wordSize) - 1;
+        const m2 = (1 << n) - 1;
+        let r = 0;
+        let y = 0;
+        return [
+            init,
+            (acc) => complete(r > 0 ? reduce(acc, y) : acc),
+            n < wordSize ?
+                (acc, x) => {
+                    let b = 0;
+                    do {
+                        acc = reduce(acc, y + ((x >>> (maxb + r)) & m2));
+                        b += n - r;
+                        x = (x << (n - r)) & m1;
+                        y = 0;
+                        r = 0;
+                    } while (b <= maxb && !isReduced(acc));
+                    r = wordSize - b;
+                    y = r > 0 ? (x >>> maxb) & m2 : 0;
+                    return acc;
+                } :
+                n > wordSize ?
+                    (acc, x) => {
+                        if (r + wordSize <= n) {
+                            y |= (x & m1) << (n - wordSize - r);
+                            r += wordSize;
+                            if (r === n) {
+                                acc = reduce(acc, y);
+                                y = 0;
+                                r = 0;
+                            }
+                        }
+                        else {
+                            const k = n - r;
+                            r = wordSize - k;
+                            acc = reduce(acc, y | ((x >>> r) & ((1 << k) - 1)));
+                            y = (x & ((1 << r) - 1)) << (n - r);
+                        }
+                        return acc;
+                    } :
+                    reduce
+        ];
+    };
+}
diff --git a/packages/transducers/test/partition-bits.ts b/packages/transducers/test/partition-bits.ts
@@ -0,0 +1,33 @@
+import * as assert from "assert";
+import { radix } from "@thi.ng/strings/radix";
+
+import { comp } from "../src/func/comp";
+import { range } from "../src/iter/range";
+import { iterator } from "../src/iterator";
+import { run } from "../src/run";
+import { bits } from "../src/xform/bits";
+import { map } from "../src/xform/map";
+import { padLast } from "../src/xform/pad-last";
+import { partition } from "../src/xform/partition";
+import { partitionBits } from "../src/xform/partition-bits";
+
+const src = [0xff, 0xa5, 0xfe, 0xf7];
+
+const xform = (n: number) =>
+    comp(partitionBits(n), map(radix(2, n)));
+
+const xformB = (n: number) =>
+    comp(bits(8), padLast(n, 0), partition(n, true), map((x) => x.join("")));
+
+const check = (n: number) =>
+    assert.deepEqual(
+        [...iterator(xform(n), src)],
+        [...iterator(xformB(n), src)],
+        `bits=${n}`
+    );
+
+describe("partitionBits", () => {
+
+    it("all sizes", () => run(map((n: number) => check(n)), range(1, 33)));
+
+});