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
|
// 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,
});
},
},
],
});
|
