-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathindex.ts
More file actions
52 lines (48 loc) · 1.62 KB
/
index.ts
File metadata and controls
52 lines (48 loc) · 1.62 KB
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
function default_hash<T>(x: T): any {
return x;
}
/**
* Takes an array of arrays and optionally a hash function,
* and returns the elements that are present in all the arrays.
* When intersecting arrays of objects, you should use a custom
* hash function that returns identical values when given objects
* that should be considered equal in your application.
* The default hash function is the identity function.
* When performance is not critical, a handy hash function can be `JSON.stringify`.
*/
export default function intersect<T>(arrays: ReadonlyArray<T>[], hash=default_hash): T[] {
if (arrays.length === 0) return [];
// Put the smallest array in the beginning
for (let i=1; i<arrays.length; i++) {
if(arrays[i].length < arrays[0].length) {
let tmp = arrays[0];
arrays[0] = arrays[i];
arrays[i] = tmp;
}
}
// Create a map associating each element to its current count
const set = new Map();
for(const elem of arrays[0]) {
set.set(hash(elem), 1);
}
for (let i=1; i<arrays.length; i++) {
let found = 0;
for(const elem of arrays[i]) {
const hashed = hash(elem);
const count = set.get(hashed)
if (count === i) {
set.set(hashed, count + 1);
found++;
}
}
// Stop early if an array has no element in common with the smallest
if (found === 0) return [];
}
// Output only the elements that have been seen as many times as there are arrays
return arrays[0].filter(e => {
const hashed = hash(e);
const count = set.get(hashed);
if (count !== undefined) set.set(hashed, 0);
return count === arrays.length
});
}