generateTree = {
const { Node, Empty } = TreeT;
const { F } = FracT;
const mediant = (left, right) =>
match({
[F]: ([leftNumerator, leftDenominator]) => {
return match({
[F]: ([rightNumerator, rightDenominator]) =>
F(
leftNumerator + rightNumerator,
leftDenominator + rightDenominator
)
})(right);
}
})(left);
function generateArray(numLevels) {
const allFractions = [F(0, 1), F(1, 0)];
const levelOrder = [];
for (let i = 0; i < numLevels; i++) {
for (let j = 0; j < allFractions.length - 1; j += 2) {
const [left, right] = [allFractions[j], allFractions[j + 1]];
const newFraction = mediant(left, right);
allFractions.splice(j + 1, 0, newFraction);
levelOrder.push(newFraction);
}
}
return levelOrder;
}
function buildFromArray(arr, i) {
if (typeof arr[i] === 'undefined') {
return Empty();
}
const left = buildFromArray(arr, 2 * i + 1);
const right = buildFromArray(arr, 2 * i + 2);
return Node(arr[i], left, right);
}
function generateTree(numLevels) {
const levelOrder = generateArray(numLevels);
return buildFromArray(levelOrder, 0);
}
return generateTree;
}