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
127
128
129
130
131
132
133
134
135
136
137
138
|
// 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 symbolToIndex =
new Map(Array.from(symbols,
(symbol, index) => [symbol, index]));
const indexToSymbol =
new Map(Array.from(symbols,
(symbol, index) => [index, symbol]));
const assertEqual = (symbol1, symbol2) => {
if (equalSymbols.has(symbol1)) {
equalSymbols.get(symbol1).add(symbol2);
} else {
equalSymbols.set(symbol1, new Set([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 sortIndices =
symbols.map(symbol => symbolToIndex.get(symbol));
const sortedList =
sortIndices.map(index => list[index]);
const stableToUnstable =
symbols
.map((current, index) => {
if (index === 0) {
return false;
}
const previous = symbols[index - 1];
return equalSymbols.get(previous)?.has(current);
})
.reduce((accumulator, collapseEqual, index) => {
if (index === 0) {
return accumulator;
}
const last = accumulator.at(-1);
if (collapseEqual) {
accumulator.push(last);
} else {
accumulator.push(last + 1);
}
return accumulator;
}, [0]);
const unstableSortIndices =
Array.from(
{length: list.length},
(_, index) =>
stableToUnstable[symbols.indexOf(indexToSymbol.get(index))]);
return continuation({
['#sortedList']: sortedList,
['#sortIndices']: sortIndices,
['#unstableSortIndices']: unstableSortIndices,
});
},
},
],
});
|
