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 <[email protected]> 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" [email protected]: + 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==
