-
Notifications
You must be signed in to change notification settings - Fork 0
/
util.ts
140 lines (118 loc) · 3.32 KB
/
util.ts
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
139
140
/**
* Safely access an index of an array.
* If the accessed index is undefined, throws an error.
* Satisfies noUncheckedIndexedAccess of tsconfig.
*
* @param array - Array to access
* @param index - Index of Array to access
* @returns
*/
export function safeArrayAccess<T>(array: T[], index: number): T {
const access = array[index];
if (access == null) {
throw new Error("failed to access index in array");
}
return access;
}
export type Range = [
// inclusive start of range
start: number,
// exclusive end of range
end: number,
];
/**
* Yields elements of an array from start index to end index.
* Similar to array.slice, however negative numbers as parameters are not supported yet.
*
* @param array - Array to read from
* @param start - Index to start at (inclusive)
* @param end - Index to end at (exclusive)
*/
export function* readArray<T>(
array: T[],
start: number = 0,
end: number = array.length,
): Generator<T> {
if (start < 0) {
throw new Error("start cannot be negative");
}
if (start > Math.max(0, array.length - 1)) {
throw new Error("start cannot be greater than the indexes in the array");
}
if (end > array.length) {
throw new Error("end cannot be greater than length of the array");
}
if (end < start) {
throw new Error("end cannot be less than start");
}
while (start < end) {
yield safeArrayAccess(array, start);
start++;
}
}
export type PairwiseElement<A, B> = [A, null] | [null, B] | [A, B];
export type PairwiseDone = [source: boolean, target: boolean];
/**
* Only returns true if IteratorResult.value is undefined and IteratorResult.done is true
*
* @param result - Iterator Result
* @returns
*/
export const iteratorIsDone = (result: IteratorResult<unknown>): boolean =>
result.value === undefined && result.done === true;
/**
* Yields pairwise traversal of two ordered arrays.
*
* @param iterableA - First ordered array
* @param iterableB - Second ordered array
* @param comparator - Used to compare two set elements, same as Array.sort parameter
*/
export function* pairwiseTraversal<A, B>(
iterableA: Iterable<A>,
iterableB: Iterable<B>,
comparator: (a: A, b: B) => number,
): Generator<[...PairwiseElement<A, B>, ...PairwiseDone]> {
const iteratorA = iterableA[Symbol.iterator]();
const iteratorB = iterableB[Symbol.iterator]();
// initialize a and b values
let a = iteratorA.next();
let b = iteratorB.next();
let aIsDone = iteratorIsDone(a);
let bIsDone = iteratorIsDone(b);
while (!aIsDone && !bIsDone) {
const order = comparator(a.value, b.value);
const result = [null, null, aIsDone, bIsDone] as [
...PairwiseElement<A, B>,
...PairwiseDone,
];
if (order <= 0) {
result[0] = a.value;
a = iteratorA.next();
}
if (order >= 0) {
result[1] = b.value;
b = iteratorB.next();
}
yield result;
if (a.done === true) {
aIsDone = iteratorIsDone(a);
}
if (b.done === true) {
bIsDone = iteratorIsDone(b);
}
}
while (!aIsDone) {
yield [a.value, null, aIsDone, bIsDone];
a = iteratorA.next();
if (a.done === true) {
aIsDone = iteratorIsDone(a);
}
}
while (!bIsDone) {
yield [null, b.value, aIsDone, bIsDone];
b = iteratorB.next();
if (b.done === true) {
bIsDone = iteratorIsDone(b);
}
}
}