You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@annotator.apache.org by ra...@apache.org on 2020/09/20 08:28:04 UTC
[incubator-annotator] 01/01: Rewrite Cartesian product using IxJS
This is an automated email from the ASF dual-hosted git repository.
randall pushed a commit to branch rewrite-product
in repository https://gitbox.apache.org/repos/asf/incubator-annotator.git
commit ba1dbcc71ecf3111d40135a12a34212ada22cde8
Author: Randall Leeds <ra...@apache.org>
AuthorDate: Sun Sep 20 00:41:05 2020 -0700
Rewrite Cartesian product using IxJS
---
packages/dom/package.json | 4 +-
packages/dom/src/range/cartesian.ts | 94 ++++++++++++-------------------
packages/dom/src/range/match.ts | 4 +-
packages/dom/test/range/cartesian.test.ts | 14 ++---
yarn.lock | 27 ++++++---
5 files changed, 63 insertions(+), 80 deletions(-)
diff --git a/packages/dom/package.json b/packages/dom/package.json
index 1bb3b2a..c51490a 100644
--- a/packages/dom/package.json
+++ b/packages/dom/package.json
@@ -19,8 +19,8 @@
"types": "./lib/index.d.ts",
"dependencies": {
"@babel/runtime-corejs3": "^7.8.7",
- "cartesian": "^1.0.1",
- "dom-seek": "^5.1.0"
+ "dom-seek": "^5.1.0",
+ "ix": "^4.0.0"
},
"devDependencies": {
"@annotator/selector": "^0.1.0"
diff --git a/packages/dom/src/range/cartesian.ts b/packages/dom/src/range/cartesian.ts
index 04afad5..cefa115 100644
--- a/packages/dom/src/range/cartesian.ts
+++ b/packages/dom/src/range/cartesian.ts
@@ -18,70 +18,48 @@
* under the License.
*/
-import cartesianArrays from 'cartesian';
+// eslint-disable-next-line import/no-internal-modules
+import { merge } from 'ix/asynciterable';
-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(() => []);
-
- type NumberedResultPromise = Promise<{
- nextResult: IteratorResult<T>;
- iterableNr: number;
- }>;
+/**
+ * Generates the Cartesian product of the sets generated by the given iterables.
+ *
+ * ๐โ ร ... ร ๐โ = { (๐โ,...,๐โ) | ๐แตข โ ๐แตข }
+ */
+export async function* cartesian<T>(
+ s1: AsyncIterable<T>,
+ s2: AsyncIterable<T>,
+ ...ss: AsyncIterable<T>[]
+): AsyncGenerator<T[], void, undefined> {
+ // Collect all the values obtained from each iterable.
+ const logs = new Array(2 + ss.length) as T[][];
- function notNull(
- p: NumberedResultPromise | null,
- ): p is NumberedResultPromise {
- return p !== null;
- }
+ /**
+ * Generates tuples of the product while consuming one iterable.
+ *
+ * For each value of the iterable, appends the value to a log and yields all
+ * tuples of the product that contain values from the other logs and this new
+ * value. In this manner, generates a subset of the tuples of the Cartesian
+ * product such that together the generators produce all tuples.
+ */
+ async function* produce(iterable: AsyncIterable<T>, index: number) {
+ logs[index] = [];
- 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 }),
- ),
- );
+ for await (const value of iterable) {
+ logs[index].push(value);
- // 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),
- );
+ const snapshots = logs.slice() as [T[], ...T[][]];
+ snapshots[index] = [value];
- // If this iterable was exhausted, stop listening to it and move on.
- if (nextResult.done === true) {
- nextValuePromises[iterableNr] = null;
- continue;
+ yield* snapshots.reduce(
+ (a, b) => a.flatMap((v) => b.map((w) => [...v, w])),
+ [[]] as T[][],
+ );
}
+ }
- // 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 received value to the right log.
- logs[iterableNr] = [...logs[iterableNr], nextResult.value];
-
- // Start listening for the next value of this iterable.
- nextValuePromises[iterableNr] = iterators[iterableNr]
- .next()
- .then((nextResult) => ({ nextResult, iterableNr }));
-
- // Yield each of the produced combinations separately.
- yield* combinations;
+ const [g1, ...gs] = [s1, s2, ...ss].map(produce);
+ for await (const tuple of merge(g1, ...gs)) {
+ yield tuple;
}
}
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..7d2d2b0 100644
--- a/packages/dom/test/range/cartesian.test.ts
+++ b/packages/dom/test/range/cartesian.test.ts
@@ -19,7 +19,8 @@
*/
import { assert } from 'chai';
-import { product } from '../../src/range/cartesian';
+import { toArray } from 'ix/asynciterable';
+import { cartesian } from '../../src/range/cartesian';
async function* gen1() {
yield 1;
@@ -39,8 +40,7 @@ async function* gen3() {
describe('cartesian', () => {
describe('product', () => {
it('yields the cartesian product of the yielded items', async () => {
- const cart = product(gen1(), gen2(), gen3());
-
+ const actual = await toArray(cartesian(gen1(), gen2(), gen3()));
const expected = [
[1, 4, 5],
[2, 4, 5],
@@ -49,13 +49,7 @@ describe('cartesian', () => {
[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');
+ assert.sameDeepMembers(actual, expected, 'yields the expected items');
});
});
});
diff --git a/yarn.lock b/yarn.lock
index bd57937..4a532d6 100644
--- a/yarn.lock
+++ b/yarn.lock
@@ -1805,6 +1805,11 @@
resolved "https://registry.yarnpkg.com/@types/node/-/node-12.7.8.tgz#cb1bf6800238898bc2ff6ffa5702c3cadd350708"
integrity sha512-FMdVn84tJJdV+xe+53sYiZS4R5yn1mAIxfj+DVoNiQjTYz1+OYmjwEZr1ev9nU0axXwda0QDbYl06QHanRVH3A==
+"@types/node@^13.7.4":
+ version "13.13.21"
+ resolved "https://registry.yarnpkg.com/@types/node/-/node-13.13.21.tgz#e48d3c2e266253405cf404c8654d1bcf0d333e5c"
+ integrity sha512-tlFWakSzBITITJSxHV4hg4KvrhR/7h3xbJdSFbYJBVzKubrASbnnIFuSgolUh7qKGo/ZeJPKUfbZ0WS6Jp14DQ==
+
"@types/parse-json@^4.0.0":
version "4.0.0"
resolved "https://registry.yarnpkg.com/@types/parse-json/-/parse-json-4.0.0.tgz#2f8bb441434d163b35fb8ffdccd7138927ffb8c0"
@@ -2895,13 +2900,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"
@@ -6062,6 +6060,14 @@ iterate-value@^1.0.0:
es-get-iterator "^1.0.2"
iterate-iterator "^1.0.1"
+ix@^4.0.0:
+ version "4.0.0"
+ resolved "https://registry.yarnpkg.com/ix/-/ix-4.0.0.tgz#5907ff780c8ce0190c2199326ace499b100aedaa"
+ integrity sha512-uLV4o/iCaRifFOTwPIj9ZRrBq25j7UG5tgSPxrndeZsCfsFx5NlnEwaGI45ndOziz3azAKeYVbWw/rzloAwzGA==
+ dependencies:
+ "@types/node" "^13.7.4"
+ tslib "2.0.0"
+
"js-tokens@^3.0.0 || ^4.0.0", js-tokens@^4.0.0:
version "4.0.0"
resolved "https://registry.yarnpkg.com/js-tokens/-/js-tokens-4.0.0.tgz#19203fb59991df98e3a287050d4647cdeaf32499"
@@ -9634,6 +9640,11 @@ tsconfig-paths@^3.9.0:
minimist "^1.2.0"
strip-bom "^3.0.0"
+tslib@2.0.0:
+ version "2.0.0"
+ resolved "https://registry.yarnpkg.com/tslib/-/tslib-2.0.0.tgz#18d13fc2dce04051e20f074cc8387fd8089ce4f3"
+ integrity sha512-lTqkx847PI7xEDYJntxZH89L2/aXInsyF2luSafe/+0fHOMjlBNXdH6th7f70qxLDhul7KZK0zC8V5ZIyHl0/g==
+
tslib@^1.8.1, tslib@^1.9.0:
version "1.13.0"
resolved "https://registry.yarnpkg.com/tslib/-/tslib-1.13.0.tgz#c881e13cc7015894ed914862d276436fa9a47043"
@@ -10316,7 +10327,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==