From db4698f9ce602227dc2c9aa79c409dd4ce508e7b Mon Sep 17 00:00:00 2001 From: "(quasar) nebula" Date: Sun, 3 Dec 2023 13:23:40 -0400 Subject: data: withFilteredList, withMappedList, withSortedList God bless thine soul, these are not unit tested. --- src/data/composite/data/excludeFromList.js | 7 +- src/data/composite/data/fillMissingListItems.js | 7 +- src/data/composite/data/index.js | 3 + src/data/composite/data/withFilteredList.js | 50 +++++++++ src/data/composite/data/withFlattenedList.js | 6 +- src/data/composite/data/withMappedList.js | 39 +++++++ src/data/composite/data/withPropertiesFromList.js | 4 +- src/data/composite/data/withPropertyFromList.js | 4 +- src/data/composite/data/withSortedList.js | 126 ++++++++++++++++++++++ src/data/composite/data/withUnflattenedList.js | 10 ++ 10 files changed, 241 insertions(+), 15 deletions(-) create mode 100644 src/data/composite/data/withFilteredList.js create mode 100644 src/data/composite/data/withMappedList.js create mode 100644 src/data/composite/data/withSortedList.js (limited to 'src') diff --git a/src/data/composite/data/excludeFromList.js b/src/data/composite/data/excludeFromList.js index 718f2294..d798dcdc 100644 --- a/src/data/composite/data/excludeFromList.js +++ b/src/data/composite/data/excludeFromList.js @@ -6,10 +6,9 @@ // - fillMissingListItems // // More list utilities: -// - withFlattenedList -// - withPropertyFromList -// - withPropertiesFromList -// - withUnflattenedList +// - withFilteredList, withMappedList, withSortedList +// - withFlattenedList, withUnflattenedList +// - withPropertyFromList, withPropertiesFromList // import {input, templateCompositeFrom} from '#composite'; diff --git a/src/data/composite/data/fillMissingListItems.js b/src/data/composite/data/fillMissingListItems.js index c06eceda..4f818a79 100644 --- a/src/data/composite/data/fillMissingListItems.js +++ b/src/data/composite/data/fillMissingListItems.js @@ -5,10 +5,9 @@ // - excludeFromList // // More list utilities: -// - withFlattenedList -// - withPropertyFromList -// - withPropertiesFromList -// - withUnflattenedList +// - withFilteredList, withMappedList, withSortedList +// - withFlattenedList, withUnflattenedList +// - withPropertyFromList, withPropertiesFromList // import {input, templateCompositeFrom} from '#composite'; diff --git a/src/data/composite/data/index.js b/src/data/composite/data/index.js index e2927afd..256c0490 100644 --- a/src/data/composite/data/index.js +++ b/src/data/composite/data/index.js @@ -5,10 +5,13 @@ export {default as excludeFromList} from './excludeFromList.js'; export {default as fillMissingListItems} from './fillMissingListItems.js'; +export {default as withFilteredList} from './withFilteredList.js'; export {default as withFlattenedList} from './withFlattenedList.js'; +export {default as withMappedList} from './withMappedList.js'; export {default as withPropertiesFromList} from './withPropertiesFromList.js'; export {default as withPropertiesFromObject} from './withPropertiesFromObject.js'; export {default as withPropertyFromList} from './withPropertyFromList.js'; export {default as withPropertyFromObject} from './withPropertyFromObject.js'; +export {default as withSortedList} from './withSortedList.js'; export {default as withUnflattenedList} from './withUnflattenedList.js'; export {default as withUniqueItemsOnly} from './withUniqueItemsOnly.js'; diff --git a/src/data/composite/data/withFilteredList.js b/src/data/composite/data/withFilteredList.js new file mode 100644 index 00000000..82e56903 --- /dev/null +++ b/src/data/composite/data/withFilteredList.js @@ -0,0 +1,50 @@ +// Applies a filter - an array of truthy and falsy values - to the index- +// corresponding items in a list. Items which correspond to a truthy value +// are kept, and the rest are excluded from the output list. +// +// TODO: It would be neat to apply an availability check here, e.g. to allow +// not providing a filter at all and performing the check on the contents of +// the list (though on the filter, if present, is fine too). But that's best +// done by some shmancy-fancy mapping support in composite.js, so a bit out +// of reach for now (apart from proving uses built on top of a more boring +// implementation). +// +// TODO: There should be two outputs - one for the items included according to +// the filter, and one for the items excluded. +// +// See also: +// - withMappedList +// - withSortedList +// +// More list utilities: +// - excludeFromList +// - fillMissingListItems +// - withFlattenedList, withUnflattenedList +// - withPropertyFromList, withPropertiesFromList +// + +import {input, templateCompositeFrom} from '#composite'; + +export default templateCompositeFrom({ + annotation: `withFilteredList`, + + inputs: { + list: input({type: 'array'}), + filter: input({type: 'array'}), + }, + + outputs: ['#filteredList'], + + steps: () => [ + { + dependencies: [input('list'), input('filter')], + compute: (continuation, { + [input('list')]: list, + [input('filter')]: filter, + }) => continuation({ + '#filteredList': + list.filter((item, index) => filter[index]), + }), + }, + ], +}); diff --git a/src/data/composite/data/withFlattenedList.js b/src/data/composite/data/withFlattenedList.js index b08edb4e..edfa3403 100644 --- a/src/data/composite/data/withFlattenedList.js +++ b/src/data/composite/data/withFlattenedList.js @@ -3,13 +3,13 @@ // successive source array. // // See also: -// - withFlattenedList +// - withUnflattenedList // // More list utilities: // - excludeFromList // - fillMissingListItems -// - withPropertyFromList -// - withPropertiesFromList +// - withFilteredList, withMappedList, withSortedList +// - withPropertyFromList, withPropertiesFromList // import {input, templateCompositeFrom} from '#composite'; diff --git a/src/data/composite/data/withMappedList.js b/src/data/composite/data/withMappedList.js new file mode 100644 index 00000000..e0a700b2 --- /dev/null +++ b/src/data/composite/data/withMappedList.js @@ -0,0 +1,39 @@ +// Applies a map function to each item in a list, just like a normal JavaScript +// map. +// +// See also: +// - withFilteredList +// - withSortedList +// +// More list utilities: +// - excludeFromList +// - fillMissingListItems +// - withFlattenedList, withUnflattenedList +// - withPropertyFromList, withPropertiesFromList +// + +import {input, templateCompositeFrom} from '#composite'; + +export default templateCompositeFrom({ + annotation: `withMappedList`, + + inputs: { + list: input({type: 'array'}), + map: input({type: 'function'}), + }, + + outputs: ['#mappedList'], + + steps: () => [ + { + dependencies: [input('list'), input('map')], + compute: (continuation, { + [input('list')]: list, + [input('map')]: mapFn, + }) => continuation({ + ['#mappedList']: + list.map(mapFn), + }), + }, + ], +}); diff --git a/src/data/composite/data/withPropertiesFromList.js b/src/data/composite/data/withPropertiesFromList.js index 76ba696c..08907bab 100644 --- a/src/data/composite/data/withPropertiesFromList.js +++ b/src/data/composite/data/withPropertiesFromList.js @@ -11,8 +11,8 @@ // More list utilities: // - excludeFromList // - fillMissingListItems -// - withFlattenedList -// - withUnflattenedList +// - withFilteredList, withMappedList, withSortedList +// - withFlattenedList, withUnflattenedList // import {input, templateCompositeFrom} from '#composite'; diff --git a/src/data/composite/data/withPropertyFromList.js b/src/data/composite/data/withPropertyFromList.js index 1983ebbc..a2c66d77 100644 --- a/src/data/composite/data/withPropertyFromList.js +++ b/src/data/composite/data/withPropertyFromList.js @@ -12,8 +12,8 @@ // More list utilities: // - excludeFromList // - fillMissingListItems -// - withFlattenedList -// - withUnflattenedList +// - withFilteredList, withMappedList, withSortedList +// - withFlattenedList, withUnflattenedList // import {input, templateCompositeFrom} from '#composite'; diff --git a/src/data/composite/data/withSortedList.js b/src/data/composite/data/withSortedList.js new file mode 100644 index 00000000..882907f5 --- /dev/null +++ b/src/data/composite/data/withSortedList.js @@ -0,0 +1,126 @@ +// Applies a sort function across pairs of items in a list, just like a normal +// JavaScript sort. Alongside the sorted results, so are outputted the indices +// which each item in the unsorted list corresponds to in the sorted one, +// allowing for the results of this sort to be composed in some more involved +// operation. For example, using an alphabetical sort, the list ['banana', +// 'apple', 'pterodactyl'] will output the expected alphabetical items, as well +// as the indices list [1, 0, 2]. +// +// If two items are equal (in the eyes of the sort operation), their placement +// in the sorted list is arbitrary, though every input index will be present in +// '#sortIndices' exactly once (and equal items will be bunched together). +// +// The '#sortIndices' output refers to the "true" index which each source item +// occupies in the sorted list. This sacrifices information about equal items, +// which can be obtained through '#unstableSortIndices' instead: each mapped +// index may appear more than once, and rather than represent exact positions +// in the sorted list, they represent relational values: if items A and B are +// mapped to indices 3 and 5, then A certainly is positioned before B (and vice +// versa); but there may be more than one item in-between. If items C and D are +// both mapped to index 4, then their position relative to each other is +// arbitrary - they are equal - but they both certainly appear after item A and +// before item B. +// +// This implementation is based on the one used for sortMultipleArrays. +// +// See also: +// - withFilteredList +// - withMappedList +// +// More list utilities: +// - excludeFromList +// - fillMissingListItems +// - withFlattenedList, withUnflattenedList +// - withPropertyFromList, withPropertiesFromList +// + +import {input, templateCompositeFrom} from '#composite'; +import {empty} from '#sugar'; + +export default templateCompositeFrom({ + annotation: `withSortedList`, + + inputs: { + list: input({type: 'array'}), + sort: input({type: 'function'}), + }, + + outputs: ['#sortedList', '#sortIndices', '#unstableSortIndices'], + + steps: () => [ + { + dependencies: [input('list'), input('sort')], + compute(continuation, { + [input('list')]: list, + [input('sort')]: sortFn, + }) { + const symbols = + Array.from({length: list.length}, () => Symbol()); + + const equalSymbols = + new Map(); + + const indexMap = + new Map(Array.from(symbols, + (symbol, index) => [symbol, index])); + + symbols.sort((symbol1, symbol2) => { + const comparison = + sortFn( + list[indexMap.get(symbol1)], + list[indexMap.get(symbol2)]); + + if (comparison === 0) { + if (equalSymbols.has(symbol1)) { + equalSymbols.get(symbol1).add(symbol2); + } else { + equalSymbols.set(symbol1, new Set([symbol2])); + } + + if (equalSymbols.has(symbol2)) { + equalSymbols.get(symbol2).add(symbol1); + } else { + equalSymbols.set(symbol2, new Set([symbol1])); + } + } + + return comparison; + }); + + const sortIndices = + symbols.map(symbol => indexMap.get(symbol)); + + const sortedList = + sortIndices.map(index => list[index]); + + const stableToUnstable = + symbols + .map((symbol, index) => + index > 0 && + equalSymbols.get(symbols[index - 1])?.has(symbol)) + .reduce((accumulator, collapseEqual) => { + if (empty(accumulator)) { + accumulator.push(0); + } else { + const last = accumulator[accumulator.length - 1]; + if (collapseEqual) { + accumulator.push(last); + } else { + accumulator.push(last + 1); + } + } + return accumulator; + }, []); + + const unstableSortIndices = + sortIndices.map(stable => stableToUnstable[stable]); + + return continuation({ + ['#sortedList']: sortedList, + ['#sortIndices']: sortIndices, + ['#unstableSortIndices']: unstableSortIndices, + }); + }, + }, + ], +}); diff --git a/src/data/composite/data/withUnflattenedList.js b/src/data/composite/data/withUnflattenedList.js index 3cfc247b..39a666dc 100644 --- a/src/data/composite/data/withUnflattenedList.js +++ b/src/data/composite/data/withUnflattenedList.js @@ -3,6 +3,16 @@ // of filtering them out), this function allows for recombining them. It will // filter out null and undefined items by default (pass {filter: false} to // disable this). +// +// See also: +// - withFlattenedList +// +// More list utilities: +// - excludeFromList +// - fillMissingListItems +// - withFilteredList, withMappedList, withSortedList +// - withPropertyFromList, withPropertiesFromList +// import {input, templateCompositeFrom} from '#composite'; import {isWholeNumber, validateArrayItems} from '#validators'; -- cgit 1.3.0-6-gf8a5