Select Git revision
3.8.0-3.9.0.sql
closure.test.js 16.84 KiB
import { closure } from './closure.js';
function f(x) {
return Math.floor(x / 2);
}
function bitsum(value) {
console.assert(Number.isInteger(value));
console.assert(value >= 0);
let result = 0;
for (let bits = value; bits > 0;) {
const bit = bits & ~(bits - 1);
++result;
bits -= bit;
}
return result;
}
function g(x) {
return bitsum(x * x);
}
function numerically(left, right) {
return left - right;
}
describe('the `closure` function', () => {
test('finds the closure under f of an empty set', () => {
expect([...closure(new Set(), f)].sort(numerically)).toEqual([]);
});
test('finds the closure under g of an empty set', () => {
expect([...closure(new Set(), g)].sort(numerically)).toEqual([]);
});
test('finds the closure under f of a singleton holding 0', () => {
expect([...closure(new Set([0]), f)].sort(numerically)).toEqual([0]);
});
test('finds the closure under g of a singleton holding 0', () => {
expect([...closure(new Set([0]), g)].sort(numerically)).toEqual([0]);
});
test('finds the closure under f of a singleton holding 1', () => {
expect([...closure(new Set([1]), f)].sort(numerically)).toEqual([0, 1]);
});
test('finds the closure under g of a singleton holding 1', () => {
expect([...closure(new Set([1]), g)].sort(numerically)).toEqual([1]);
});
test('finds the closure under f of a singleton holding 2', () => {
expect([...closure(new Set([2]), f)].sort(numerically)).toEqual([0, 1, 2]);
});
test('finds the closure under g of a singleton holding 2', () => {
expect([...closure(new Set([2]), g)].sort(numerically)).toEqual([1, 2]);
});
test('finds the closure under f of a singleton holding 3', () => {
expect([...closure(new Set([3]), f)].sort(numerically)).toEqual([0, 1, 3]);
});
test('finds the closure under g of a singleton holding 3', () => {
expect([...closure(new Set([3]), g)].sort(numerically)).toEqual([1, 2, 3]);
});
test('finds the closure under g of a singleton holding 4', () => {
expect([...closure(new Set([4]), g)].sort(numerically)).toEqual([1, 4]);
});
test('finds the closure under g of a singleton holding 5', () => {
expect([...closure(new Set([5]), g)].sort(numerically)).toEqual([1, 2, 3, 5]);
});
test('finds the closure under g of a singleton holding 6', () => {
expect([...closure(new Set([6]), g)].sort(numerically)).toEqual([1, 2, 6]);
});
test('finds the closure under g of a singleton holding 7', () => {
expect([...closure(new Set([7]), g)].sort(numerically)).toEqual([1, 2, 3, 7]);
});
test('finds the closure under g of a singleton holding 8', () => {
expect([...closure(new Set([8]), g)].sort(numerically)).toEqual([1, 8]);
});
test('finds the closure under g of a singleton holding 9', () => {
expect([...closure(new Set([9]), g)].sort(numerically)).toEqual([1, 2, 3, 9]);
});
test('finds the closure under g of a singleton holding 10', () => {
expect([...closure(new Set([10]), g)].sort(numerically)).toEqual([1, 2, 3, 10]);
});
test('finds the closure under g of a singleton holding 11', () => {
expect([...closure(new Set([11]), g)].sort(numerically)).toEqual([1, 2, 3, 5, 11]);
});
test('finds the closure under g of a singleton holding 12', () => {
expect([...closure(new Set([12]), g)].sort(numerically)).toEqual([1, 2, 12]);
});
test('finds the closure under g of a singleton holding 13', () => {
expect([...closure(new Set([13]), g)].sort(numerically)).toEqual([1, 4, 13]);
});
test('finds the closure under g of a singleton holding 14', () => {
expect([...closure(new Set([14]), g)].sort(numerically)).toEqual([1, 2, 3, 14]);
});
test('finds the closure under g of a singleton holding 15', () => {
expect([...closure(new Set([15]), g)].sort(numerically)).toEqual([1, 4, 15]);
});
test('finds the closure under g of a singleton holding 16', () => {
expect([...closure(new Set([16]), g)].sort(numerically)).toEqual([1, 16]);
});
test('finds the closure under g of a singleton holding 17', () => {
expect([...closure(new Set([17]), g)].sort(numerically)).toEqual([1, 2, 3, 17]);
});
test('finds the closure under g of a singleton holding 18', () => {
expect([...closure(new Set([18]), g)].sort(numerically)).toEqual([1, 2, 3, 18]);
});
test('finds the closure under g of a singleton holding 19', () => {
expect([...closure(new Set([19]), g)].sort(numerically)).toEqual([1, 2, 3, 5, 19]);
});
test('finds the closure under g of a singleton holding 20', () => {
expect([...closure(new Set([20]), g)].sort(numerically)).toEqual([1, 2, 3, 20]);
});
test('finds the closure under g of a singleton holding 21', () => {
expect([...closure(new Set([21]), g)].sort(numerically)).toEqual([1, 2, 6, 21]);
});
test('finds the closure under g of a singleton holding 22', () => {
expect([...closure(new Set([22]), g)].sort(numerically)).toEqual([1, 2, 3, 5, 22]);
});
test('finds the closure under g of a singleton holding 23', () => {
expect([...closure(new Set([23]), g)].sort(numerically)).toEqual([1, 2, 3, 23]);
});
test('finds the closure under g of a singleton holding 24', () => {
expect([...closure(new Set([24]), g)].sort(numerically)).toEqual([1, 2, 24]);
});
test('finds the closure under g of a singleton holding 25', () => {
expect([...closure(new Set([25]), g)].sort(numerically)).toEqual([1, 2, 3, 5, 25]);
});
test('finds the closure under g of a singleton holding 26', () => {
expect([...closure(new Set([26]), g)].sort(numerically)).toEqual([1, 4, 26]);
});
test('finds the closure under g of a singleton holding 27', () => {
expect([...closure(new Set([27]), g)].sort(numerically)).toEqual([1, 2, 6, 27]);
});
test('finds the closure under g of a singleton holding 28', () => {
expect([...closure(new Set([28]), g)].sort(numerically)).toEqual([1, 2, 3, 28]);
});
test('finds the closure under g of a singleton holding 29', () => {
expect([...closure(new Set([29]), g)].sort(numerically)).toEqual([1, 2, 3, 5, 29]);
});
test('finds the closure under g of a singleton holding 30', () => {
expect([...closure(new Set([30]), g)].sort(numerically)).toEqual([1, 4, 30]);
});
test('finds the closure under g of a singleton holding 31', () => {
expect([...closure(new Set([31]), g)].sort(numerically)).toEqual([1, 2, 3, 5, 31]);
});
test('finds the closure under f of a singleton holding a much larger value', () => {
expect([...closure(new Set([193]), f)].sort(numerically)).toEqual([0, 1, 3, 6, 12, 24, 48, 96, 193]);
});
test('finds the closure under g of a singleton holding a much larger value', () => {
expect([...closure(new Set([193]), g)].sort(numerically)).toEqual([1, 2, 3, 5, 193]);
});
test('finds the closure under f of a size-2 set', () => {
expect([...closure(new Set([
72, 193,
]), f)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 6, 9, 12, 18, 24, 36, 48, 72, 96, 193,
]);
});
test('finds the closure under g of a size-2 set', () => {
expect([...closure(new Set([
72, 193,
]), g)].sort(numerically)).toEqual([
1, 2, 3, 5, 72, 193,
]);
});
test('finds the closure under f of a size-3 set', () => {
expect([...closure(new Set([
72, 160, 193,
]), f)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 9, 10, 12, 18, 20, 24, 36, 40, 48, 72, 80, 96, 160, 193,
]);
});
test('finds the closure under g of a size-3 set', () => {
expect([...closure(new Set([
72, 160, 193,
]), g)].sort(numerically)).toEqual([
1, 2, 3, 5, 72, 160, 193,
]);
});
test('finds the closure under f of a size-4 set', () => {
expect([...closure(new Set([
62, 72, 160, 193,
]), f)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 15, 18, 20, 24, 31, 36, 40, 48, 62, 72, 80, 96, 160, 193,
]);
});
test('finds the closure under g of a size-4 set', () => {
expect([...closure(new Set([
62, 72, 160, 193,
]), g)].sort(numerically)).toEqual([
1, 2, 3, 5, 62, 72, 160, 193,
]);
});
test('finds the closure under g of a size-5 set', () => {
expect([...closure(new Set([
62, 65, 72, 160, 193,
]), g)].sort(numerically)).toEqual([
1, 2, 3, 5, 62, 65, 72, 160, 193,
]);
});
test('finds the closure under g of a size-6 set', () => {
expect([...closure(new Set([
62, 65, 72, 123, 160, 193,
]), g)].sort(numerically)).toEqual([
1, 2, 3, 5, 8, 62, 65, 72, 123, 160, 193,
]);
});
test('finds the closure under g of a size-7 set', () => {
expect([...closure(new Set([
24, 62, 65, 72, 123, 160, 193,
]), g)].sort(numerically)).toEqual([
1, 2, 3, 5, 8, 24, 62, 65, 72, 123, 160, 193,
]);
});
test('finds the closure under g of a size-8 set', () => {
expect([...closure(new Set([
24, 62, 65, 72, 91, 123, 160, 193,
]), g)].sort(numerically)).toEqual([
1, 2, 3, 5, 8, 24, 62, 65, 72, 91, 123, 160, 193,
]);
});
test('finds the closure under g of a size-9 set', () => {
expect([...closure(new Set([
24, 62, 65, 67, 72, 91, 123, 160, 193,
]), g)].sort(numerically)).toEqual([
1, 2, 3, 5, 8, 24, 62, 65, 67, 72, 91, 123, 160, 193,
]);
});
test('finds the closure under g of a size-10 set', () => {
expect([...closure(new Set([
24, 62, 65, 67, 72, 91, 123, 153, 160, 193,
]), g)].sort(numerically)).toEqual([
1, 2, 3, 5, 8, 9, 24, 62, 65, 67, 72, 91, 123, 153, 160, 193,
]);
});
test('finds the closure under g of a size-11 set', () => {
expect([...closure(new Set([
24, 30, 62, 65, 67, 72, 91, 123, 153, 160, 193,
]), g)].sort(numerically)).toEqual([
1, 2, 3, 4, 5, 8, 9, 24, 30, 62, 65, 67, 72, 91, 123, 153, 160, 193,
]);
});
test('finds the closure under g of a size-12 set', () => {
expect([...closure(new Set([
4, 24, 30, 62, 65, 67, 72, 91, 123, 153, 160, 193,
]), g)].sort(numerically)).toEqual([
1, 2, 3, 4, 5, 8, 9, 24, 30, 62, 65, 67, 72, 91, 123, 153, 160, 193,
]);
});
test('finds the closure under g of a size-13 set', () => {
expect([...closure(new Set([
4, 24, 30, 62, 65, 66, 67, 72, 91, 123, 153, 160, 193,
]), g)].sort(numerically)).toEqual([
1, 2, 3, 4, 5, 8, 9, 24, 30, 62, 65, 66, 67, 72, 91, 123, 153, 160, 193,
]);
});
test('finds the closure under g of a size-14 set', () => {
expect([...closure(new Set([
0, 4, 24, 30, 62, 65, 66, 67, 72, 91, 123, 153, 160, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 8, 9, 24, 30, 62, 65, 66, 67, 72, 91, 123, 153, 160, 193,
]);
});
test('finds the closure under g of a size-15 set', () => {
expect([...closure(new Set([
0, 4, 24, 30, 62, 65, 66, 67, 72, 91, 123, 153, 160, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 8, 9, 24, 30, 62, 65, 66, 67, 72, 91, 123, 153, 160, 179, 193,
]);
});
test('finds the closure under g of a size-16 set', () => {
expect([...closure(new Set([
0, 4, 24, 30, 62, 65, 66, 67, 72, 91, 123, 153, 154, 160, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 7, 8, 9, 24, 30, 62, 65, 66, 67, 72, 91, 123, 153, 154, 160, 179, 193,
]);
});
test('finds the closure under g of a size-17 set', () => {
expect([...closure(new Set([
0, 4, 24, 30, 62, 65, 66, 67, 72, 91, 123, 151, 153, 154, 160, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 24, 30, 62, 65, 66, 67, 72, 91, 123, 151, 153, 154, 160, 179, 193,
]);
});
test('finds the closure under g of a size-18 set', () => {
expect([...closure(new Set([
0, 4, 24, 30, 62, 65, 66, 67, 72, 74, 91, 123, 151, 153, 154, 160, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 24, 30, 62, 65, 66, 67, 72, 74, 91, 123, 151, 153, 154, 160, 179, 193,
]);
});
test('finds the closure under g of a size-19 set', () => {
expect([...closure(new Set([
0, 4, 24, 27, 30, 62, 65, 66, 67, 72, 74, 91, 123, 151, 153, 154, 160, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 24, 27, 30, 62, 65, 66, 67, 72, 74, 91, 123, 151, 153, 154, 160, 179, 193,
]);
});
test('finds the closure under g of a size-20 set', () => {
expect([...closure(new Set([
0, 4, 24, 27, 30, 62, 65, 66, 67, 71, 72, 74, 91, 123, 151, 153, 154, 160, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 24, 27, 30, 62, 65, 66, 67, 71, 72, 74, 91, 123, 151, 153, 154, 160, 179, 193,
]);
});
test('finds the closure under g of a size-21 set', () => {
expect([...closure(new Set([
0, 4, 5, 24, 27, 30, 62, 65, 66, 67, 71, 72, 74, 91, 123, 151, 153, 154, 160, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 24, 27, 30, 62, 65, 66, 67, 71, 72, 74, 91, 123, 151, 153, 154, 160, 179, 193,
]);
});
test('finds the closure under g of a size-22 set', () => {
expect([...closure(new Set([
0, 4, 5, 11, 24, 27, 30, 62, 65, 66, 67, 71, 72, 74, 91, 123, 151, 153, 154, 160, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 24, 27, 30, 62, 65, 66, 67, 71, 72, 74, 91, 123, 151, 153, 154, 160, 179, 193,
]);
});
test('finds the closure under g of a size-23 set', () => {
expect([...closure(new Set([
0, 4, 5, 11, 24, 27, 30, 62, 65, 66, 67, 71, 72, 74, 91, 123, 151, 153, 154, 160, 172, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 24, 27, 30, 62, 65, 66,
67, 71, 72, 74, 91, 123, 151, 153, 154, 160, 172, 179, 193,
]);
});
test('finds the closure under g of a size-24 set', () => {
expect([...closure(new Set([
0, 4, 5, 11, 24, 27, 30, 62, 65, 66, 67, 71, 72, 74, 91, 123, 131, 151, 153, 154, 160, 172, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 24, 27, 30, 62, 65, 66, 67,
71, 72, 74, 91, 123, 131, 151, 153, 154, 160, 172, 179, 193,
]);
});
test('finds the closure under g of a size-25 set', () => {
expect([...closure(new Set([
0, 4, 5, 11, 24, 27, 30, 45, 62, 65, 66, 67, 71, 72, 74, 91, 123, 131, 151, 153, 154, 160, 172, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 24, 27, 30, 45, 62, 65, 66,
67, 71, 72, 74, 91, 123, 131, 151, 153, 154, 160, 172, 179, 193,
]);
});
test('finds the closure under g of a size-26 set', () => {
expect([...closure(new Set([
0, 4, 5, 11, 24, 27, 30, 45, 62, 65, 66, 67, 71, 72, 74, 91, 93, 123, 131, 151, 153, 154, 160, 172, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 24, 27, 30, 45, 62, 65, 66, 67,
71, 72, 74, 91, 93, 123, 131, 151, 153, 154, 160, 172, 179, 193,
]);
});
test('finds the closure under g of a size-27 set', () => {
expect([...closure(new Set([
0, 4, 5, 11, 24, 27, 30, 45, 49, 62, 65, 66, 67, 71, 72, 74, 91, 93, 123, 131, 151, 153, 154, 160, 172, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 24, 27, 30, 45, 49, 62, 65, 66,
67, 71, 72, 74, 91, 93, 123, 131, 151, 153, 154, 160, 172, 179, 193,
]);
});
test('finds the closure under g of a size-28 set', () => {
expect([...closure(new Set([
0, 4, 5, 11, 24, 27, 30, 45, 49, 62, 65, 66, 67, 71, 72,
74, 90, 91, 93, 123, 131, 151, 153, 154, 160, 172, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 24, 27, 30, 45, 49, 62, 65, 66, 67,
71, 72, 74, 90, 91, 93, 123, 131, 151, 153, 154, 160, 172, 179, 193,
]);
});
test('finds the closure under g of a size-29 set', () => {
expect([...closure(new Set([
0, 4, 5, 11, 24, 27, 30, 45, 49, 62, 65, 66, 67, 71, 72, 74,
90, 91, 92, 93, 123, 131, 151, 153, 154, 160, 172, 179, 193,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 24, 27, 30, 45, 49, 62, 65, 66, 67,
71, 72, 74, 90, 91, 92, 93, 123, 131, 151, 153, 154, 160, 172, 179, 193,
]);
});
test('finds the closure under g of a size-30 set', () => {
expect([...closure(new Set([
0, 4, 5, 11, 24, 27, 30, 45, 49, 62, 65, 66, 67, 71, 72, 74, 90,
91, 92, 93, 123, 131, 151, 153, 154, 160, 172, 179, 193, 195,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 24, 27, 30, 45, 49, 62, 65, 66, 67, 71,
72, 74, 90, 91, 92, 93, 123, 131, 151, 153, 154, 160, 172, 179, 193, 195,
]);
});
test('finds the closure under g of a size-31 set', () => {
expect([...closure(new Set([
0, 4, 5, 11, 24, 27, 30, 45, 49, 62, 65, 66, 67, 71, 72, 74, 90,
91, 92, 93, 123, 128, 131, 151, 153, 154, 160, 172, 179, 193, 195,
]), g)].sort(numerically)).toEqual([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 24, 27, 30, 45, 49, 62, 65, 66, 67, 71, 72,
74, 90, 91, 92, 93, 123, 128, 131, 151, 153, 154, 160, 172, 179, 193, 195,
]);
});
});