Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 | 1x 1x 1x 1x 1x 297x 294x 3x 1x 295x 295x 295x 295x 295x 727x 727x 295x 295x 727x 727x 727x 727x 252x 475x 727x 295x 295x | import {Array, pipe} from '#util'
import {branch, leaf, type Branch} from '#tree'
import {Option} from 'effect'
import {decode as decodeEdges, type EdgeList} from '../edges.js'
/**
* Convert a prüfer code into a tree.
* @category codec
* @function
*/
export const decode: (code: number[]) => Branch<number> = code =>
Array.isNonEmptyArray(code)
? pipe(code, toEdges, decodeEdges)
: branch(1, [leaf(2)])
/**
* Convert a prüfer code into a list of directed edges in linear time.
* @category codec
* @function
*/
export const toEdges = (
code: Array.NonEmptyReadonlyArray<number>,
): EdgeList<number> => {
const edges = [] as unknown as EdgeList<number>
const degree: number[] = [-1, 2, ...pipe(1, Array.replicate(code.length + 1))]
for (const node of code) {
;(degree[node] as number)++
}
let leaf = degree.indexOf(1)
for (const parent of code) {
edges.push([leaf, Option.some(parent)])
;(degree[leaf] as number)--
leaf =
--(degree[parent] as number) === 1 && parent < leaf
? parent
: degree.indexOf(1, leaf)
}
return [[1, Option.none()], [leaf, Option.some(1)], ...edges]
}
|