This is an automated email from the ASF dual-hosted git repository.
randall pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-annotator.git
The following commit(s) were added to refs/heads/master by this push:
new c6f0b10 Rewrite Cartesian product without dependencies
c6f0b10 is described below
commit c6f0b106cbe57c6b7d328ea4e8c89f36ac018d0e
Author: Randall Leeds <[email protected]>
AuthorDate: Sun Sep 20 00:41:05 2020 -0700
Rewrite Cartesian product without dependencies
Rewrite the Cartesian product function to accept iterables or
asynchronous iterables and inline the synchronous partial product
computation to remove a dependency.
---
packages/dom/package.json | 1 -
packages/dom/src/range/cartesian.ts | 104 ++++++++++++++----------------
packages/dom/src/range/match.ts | 4 +-
packages/dom/test/range/cartesian.test.ts | 40 ++++++------
yarn.lock | 9 +--
5 files changed, 72 insertions(+), 86 deletions(-)
diff --git a/packages/dom/package.json b/packages/dom/package.json
index 1bb3b2a..b623c60 100644
--- a/packages/dom/package.json
+++ b/packages/dom/package.json
@@ -19,7 +19,6 @@
"types": "./lib/index.d.ts",
"dependencies": {
"@babel/runtime-corejs3": "^7.8.7",
- "cartesian": "^1.0.1",
"dom-seek": "^5.1.0"
},
"devDependencies": {
diff --git a/packages/dom/src/range/cartesian.ts
b/packages/dom/src/range/cartesian.ts
index 04afad5..8c60cde 100644
--- a/packages/dom/src/range/cartesian.ts
+++ b/packages/dom/src/range/cartesian.ts
@@ -18,70 +18,66 @@
* under the License.
*/
-import cartesianArrays from 'cartesian';
-
-export async function* product<T>(
- ...iterables: AsyncIterable<T>[]
-): AsyncGenerator<Array<T>, void, undefined> {
- // We listen to all iterators in parallel, while logging all the values they
- // produce. Whenever an iterator produces a value, we produce and yield all
- // combinations of that value with the logged values from other iterators.
- // Every combination is thus made exactly once, and as soon as it is known.
-
- const iterators = iterables.map((iterable) =>
- iterable[Symbol.asyncIterator](),
- );
- // Initialise an empty log for each iterable.
- const logs: T[][] = iterables.map(() => []);
+/**
+ * Generates the Cartesian product of the sets generated by the given
iterables.
+ *
+ * ๐โ ร ... ร ๐โ = { (๐โ,...,๐โ) | ๐แตข โ ๐แตข }
+ */
+export async function* cartesian<T>(
+ ...iterables: (Iterable<T> | AsyncIterable<T>)[]
+): AsyncGenerator<T[], void, undefined> {
+ // Create iterators for traversing each iterable and tagging every value
+ // with the index of its source iterable.
+ const iterators = iterables.map((iterable, index) => {
+ const generator = async function* () {
+ for await (const value of iterable) {
+ yield { index, value };
+ }
+ return { index, value: undefined };
+ };
+ return generator();
+ });
- type NumberedResultPromise = Promise<{
- nextResult: IteratorResult<T>;
- iterableNr: number;
- }>;
+ // Track the number of non-exhausted iterators.
+ let active = iterators.length;
- function notNull(
- p: NumberedResultPromise | null,
- ): p is NumberedResultPromise {
- return p !== null;
- }
+ // Track all the values of each iterator in a log.
+ const logs = iterators.map(() => []) as T[][];
- const nextValuePromises: Array<NumberedResultPromise | null> = iterators.map(
- (iterator, iterableNr) =>
- iterator.next().then(
- // Label the result with iterableNr, to know which iterable produced
- // this value after Promise.race below.
- (nextResult) => ({ nextResult, iterableNr }),
- ),
- );
+ // Track the promise of the next value of each iterator.
+ const nexts = iterators.map((it) => it.next());
- // Keep listening as long as any of the iterables is not yet exhausted.
- while (nextValuePromises.some(notNull)) {
- // Wait until any of the active iterators has produced a new value.
- const { nextResult, iterableNr } = await Promise.race(
- nextValuePromises.filter(notNull),
- );
+ // Iterate the values of all the iterators in parallel and yield tuples from
+ // the partial product of each new value and the existing logs of the other
+ // iterators.
+ while (active) {
+ // Wait for the next result.
+ const result = await Promise.race(nexts);
+ const { index } = result.value;
- // If this iterable was exhausted, stop listening to it and move on.
- if (nextResult.done === true) {
- nextValuePromises[iterableNr] = null;
+ // If the iterator has exhausted all the values, set the promise
+ // of its next value to never resolve.
+ if (result.done) {
+ active--;
+ nexts[index] = new Promise(() => undefined);
continue;
}
- // Produce all combinations of the received value with the logged values
- // from the other iterables.
- const arrays = [...logs];
- arrays[iterableNr] = [nextResult.value];
- const combinations: T[][] = cartesianArrays(arrays);
+ // Append the new value to the log.
+ const { value } = result.value;
+ logs[index].push(value);
- // Append the received value to the right log.
- logs[iterableNr] = [...logs[iterableNr], nextResult.value];
+ // Record the promise of the next value.
+ nexts[index] = iterators[index].next();
- // Start listening for the next value of this iterable.
- nextValuePromises[iterableNr] = iterators[iterableNr]
- .next()
- .then((nextResult) => ({ nextResult, iterableNr }));
+ // Create a scratch input for computing a partial product.
+ const scratch = [...logs];
+ scratch[index] = [value];
- // Yield each of the produced combinations separately.
- yield* combinations;
+ // Synchronously compute and yield tuples of the partial product.
+ yield* scratch.reduce(
+ (a, b) => a.flatMap((v) => Array.from(b).map((w) => [...v, w])),
+ [[]] as T[][],
+ );
}
}
diff --git a/packages/dom/src/range/match.ts b/packages/dom/src/range/match.ts
index 30990ee..b80166d 100644
--- a/packages/dom/src/range/match.ts
+++ b/packages/dom/src/range/match.ts
@@ -20,7 +20,7 @@
import type { Matcher, RangeSelector, Selector } from '@annotator/selector';
import { ownerDocument } from '../owner-document';
-import { product } from './cartesian';
+import { cartesian } from './cartesian';
export function makeCreateRangeSelectorMatcher(
createMatcher: <T extends Selector>(selector: T) => Matcher<Range, Range>,
@@ -33,7 +33,7 @@ export function makeCreateRangeSelectorMatcher(
const startMatches = startMatcher(scope);
const endMatches = endMatcher(scope);
- const pairs = product(startMatches, endMatches);
+ const pairs = cartesian(startMatches, endMatches);
for await (const [start, end] of pairs) {
const result = ownerDocument(scope).createRange();
diff --git a/packages/dom/test/range/cartesian.test.ts
b/packages/dom/test/range/cartesian.test.ts
index 1b794dd..475bc79 100644
--- a/packages/dom/test/range/cartesian.test.ts
+++ b/packages/dom/test/range/cartesian.test.ts
@@ -19,7 +19,7 @@
*/
import { assert } from 'chai';
-import { product } from '../../src/range/cartesian';
+import { cartesian } from '../../src/range/cartesian';
async function* gen1() {
yield 1;
@@ -37,25 +37,23 @@ async function* gen3() {
}
describe('cartesian', () => {
- describe('product', () => {
- it('yields the cartesian product of the yielded items', async () => {
- const cart = product(gen1(), gen2(), gen3());
-
- const expected = [
- [1, 4, 5],
- [2, 4, 5],
- [3, 4, 5],
- [1, 4, 6],
- [2, 4, 6],
- [3, 4, 6],
- ];
-
- const result: number[][] = [];
- for await (const value of cart) {
- result.push(value);
- }
-
- assert.sameDeepMembers(result, expected, 'yields the expected items');
- });
+ it('yields the cartesian product of the yielded items', async () => {
+ const cart = cartesian(gen1(), gen2(), gen3());
+
+ const expected = [
+ [1, 4, 5],
+ [2, 4, 5],
+ [3, 4, 5],
+ [1, 4, 6],
+ [2, 4, 6],
+ [3, 4, 6],
+ ];
+
+ const actual: number[][] = [];
+ for await (const value of cart) {
+ actual.push(value);
+ }
+
+ assert.sameDeepMembers(actual, expected, 'yields the expected items');
});
});
diff --git a/yarn.lock b/yarn.lock
index c16063b..2e9fe82 100644
--- a/yarn.lock
+++ b/yarn.lock
@@ -2926,13 +2926,6 @@ caniuse-lite@^1.0.30001043:
resolved
"https://registry.yarnpkg.com/caniuse-lite/-/caniuse-lite-1.0.30001066.tgz#0a8a58a10108f2b9bf38e7b65c237b12fd9c5f04";
integrity
sha512-Gfj/WAastBtfxLws0RCh2sDbTK/8rJuSeZMecrSkNGYxPcv7EzblmDGfWQCFEQcSqYE2BRgQiJh8HOD07N5hIw==
-cartesian@^1.0.1:
- version "1.0.1"
- resolved
"https://registry.yarnpkg.com/cartesian/-/cartesian-1.0.1.tgz#ae3fc8a63e2ba7e2c4989ce696207457bcae65af";
- integrity sha1-rj/Ipj4rp+LEmJzmliB0V7yuZa8=
- dependencies:
- xtend "^4.0.1"
-
caseless@~0.12.0:
version "0.12.0"
resolved
"https://registry.yarnpkg.com/caseless/-/caseless-0.12.0.tgz#1b681c21ff84033c826543090689420d187151dc";
@@ -10417,7 +10410,7 @@ xmlchars@^2.2.0:
resolved
"https://registry.yarnpkg.com/xmlchars/-/xmlchars-2.2.0.tgz#060fe1bcb7f9c76fe2a17db86a9bc3ab894210cb";
integrity
sha512-JZnDKK8B0RCDw84FNdDAIpZK+JuJw+s7Lz8nksI7SIuU3UXJJslUthsi+uWBUYOwPFwW7W7PRLRfUKpxjtjFCw==
-xtend@^4.0.0, xtend@^4.0.1, xtend@~4.0.1:
+xtend@^4.0.0, xtend@~4.0.1:
version "4.0.2"
resolved
"https://registry.yarnpkg.com/xtend/-/xtend-4.0.2.tgz#bb72779f5fa465186b1f438f674fa347fdb5db54";
integrity
sha512-LKYU1iAXJXUgAXn9URjiu+MWhyUXHsvfp7mcuYm9dSUKK0/CjtrUwFAxD82/mCWbtLsGjFIad0wIsod4zrTAEQ==
