diff options
Diffstat (limited to 'src/data/composite/data/withSortedList.js')
-rw-r--r-- | src/data/composite/data/withSortedList.js | 121 |
1 files changed, 121 insertions, 0 deletions
diff --git a/src/data/composite/data/withSortedList.js b/src/data/composite/data/withSortedList.js new file mode 100644 index 0000000..dd81078 --- /dev/null +++ b/src/data/composite/data/withSortedList.js @@ -0,0 +1,121 @@ +// 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'; + +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 = []; + const symbolToIndex = new Map(); + + for (const index of list.keys()) { + const symbol = Symbol(); + symbols.push(symbol); + symbolToIndex.set(symbol, index); + } + + const equalSymbols = new Map(); + + const assertEqual = (symbol1, symbol2) => { + if (equalSymbols.has(symbol1)) { + equalSymbols.get(symbol1).add(symbol2); + } else { + equalSymbols.set(symbol1, new Set([symbol2])); + } + }; + + const isEqual = (symbol1, symbol2) => + !!equalSymbols.get(symbol1)?.has(symbol2); + + symbols.sort((symbol1, symbol2) => { + const comparison = + sortFn( + list[symbolToIndex.get(symbol1)], + list[symbolToIndex.get(symbol2)]); + + if (comparison === 0) { + assertEqual(symbol1, symbol2); + assertEqual(symbol2, symbol1); + } + + return comparison; + }); + + const stableSortIndices = []; + const unstableSortIndices = []; + const sortedList = []; + + let unstableIndex = 0; + + for (const [stableIndex, symbol] of symbols.entries()) { + const sourceIndex = symbolToIndex.get(symbol); + sortedList.push(list[sourceIndex]); + + if (stableIndex > 0) { + const previous = symbols[stableIndex - 1]; + if (!isEqual(symbol, previous)) { + unstableIndex++; + } + } + + stableSortIndices[sourceIndex] = stableIndex; + unstableSortIndices[sourceIndex] = unstableIndex; + } + + return continuation({ + ['#sortedList']: sortedList, + ['#sortIndices']: stableSortIndices, + ['#unstableSortIndices']: unstableSortIndices, + }); + }, + }, + ], +}); |