1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
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.at(-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,
});
},
},
],
});
|
