Skip to content

Instantly share code, notes, and snippets.

@dfee

dfee/node.test.ts

Created July 27, 2022 01:22
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save dfee/f4a89ccdd7c4fb42bbe7fecf5652984a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save dfee/f4a89ccdd7c4fb42bbe7fecf5652984a to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. dfee created this gist Jul 27, 2022.
    68 changes: 68 additions & 0 deletions node.test.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,68 @@
    import {
    Lineage,
    Node,
    getSubtreeByLineage,
    treeFromLineageArray,
    walkTreeDepthFirst,
    } from "../node";

    describe("Node", () => {
    const LINEAGE_ARRAY_FIXTURE: ReadonlyArray<Lineage> = [
    ["a"],
    ["b", "b1"],
    ["b", "b2"],
    ["c", "c1", "c1a"],
    ["c", "c1", "c1b"],
    ];
    const TREE_FIXTURE: Node = {
    a: null,
    b: { b1: null, b2: null },
    c: { c1: { c1a: null, c1b: null } },
    };
    const DFS_FIXTURE = [
    ["a", getSubtreeByLineage(TREE_FIXTURE, "a")],
    ["b1", getSubtreeByLineage(TREE_FIXTURE, "b", "b1")],
    ["b2", getSubtreeByLineage(TREE_FIXTURE, "b", "b2")],
    ["b", getSubtreeByLineage(TREE_FIXTURE, "b")],
    ["c1a", getSubtreeByLineage(TREE_FIXTURE, "c", "c1", "c1a")],
    ["c1b", getSubtreeByLineage(TREE_FIXTURE, "c", "c1", "c1b")],
    ["c1", getSubtreeByLineage(TREE_FIXTURE, "c", "c1")],
    ["c", getSubtreeByLineage(TREE_FIXTURE, "c")],
    ];

    describe("treeFromLineageArray", () => {
    it("should build complex tree", () => {
    expect(treeFromLineageArray(LINEAGE_ARRAY_FIXTURE)).toEqual(TREE_FIXTURE);
    });

    it("should return empty", () => {
    const input: ReadonlyArray<Lineage> = [];
    const expected: Node = {};
    expect(treeFromLineageArray(input)).toEqual(expected);
    });
    });

    describe("getSubtreeByLineage", () => {
    it("should get undefined", () => {
    expect(getSubtreeByLineage(TREE_FIXTURE, "z")).toBeUndefined();
    });

    it("should get null", () => {
    expect(getSubtreeByLineage(TREE_FIXTURE, "a")).toBeNull();
    });

    it("should get b's tree", () => {
    expect(getSubtreeByLineage(TREE_FIXTURE, "b")).toEqual(TREE_FIXTURE["b"]);
    });
    });

    describe("depth first ", () => {
    it("should walk depth first", () => {
    expect(walkTreeDepthFirst(TREE_FIXTURE)).toEqual(DFS_FIXTURE);
    });

    it("should walk nowhere", () => {
    expect(walkTreeDepthFirst({})).toEqual([]);
    });
    });
    });
    109 changes: 109 additions & 0 deletions node.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,109 @@
    import {
    either,
    function as func,
    option,
    ord,
    readonlyArray,
    readonlyNonEmptyArray,
    record,
    string,
    } from "fp-ts";

    export type Defined<T> = T extends undefined ? never : T;
    export type Node = {
    [K in string]?: Node | null;
    };
    export type NodeEntry = Defined<Node[keyof Node]>;
    export type Lineage = readonlyNonEmptyArray.ReadonlyNonEmptyArray<string>;

    export const enhanceTreeWithLineage = (
    tree: Node,
    [first, ...remainder]: Lineage,
    ): Node => {
    return {
    ...tree,
    [first]: func.pipe(
    remainder,
    readonlyNonEmptyArray.fromArray,
    option.map((nonEmptyRemainder) =>
    enhanceTreeWithLineage(
    func.pipe(
    option.fromNullable(tree[first]),
    option.getOrElse(() => ({})),
    ),
    nonEmptyRemainder,
    ),
    ),
    option.getOrElse<NodeEntry>(func.constNull),
    ),
    };
    };

    export const treeFromLineageArray = (
    lineages: ReadonlyArray<readonlyNonEmptyArray.ReadonlyNonEmptyArray<string>>,
    ): Node =>
    func.pipe(
    lineages,
    readonlyArray.reduce({}, (tree, lineage) =>
    enhanceTreeWithLineage(tree, lineage),
    ),
    );

    export const walkTreeDepthFirst = (
    tree: Node,
    ): ReadonlyArray<[string, NodeEntry]> =>
    func.pipe(
    tree,
    record.toEntries,
    readonlyArray.filter(
    (entry): entry is [string, NodeEntry] => entry[1] !== undefined,
    ),
    readonlyArray.sort(
    func.pipe(
    string.Ord,
    ord.contramap<string, [string, NodeEntry]>(([key]) => key),
    ),
    ),
    readonlyArray.map(([key, subtree]) =>
    func.pipe(
    subtree,
    option.fromNullable,
    option.map((nonNullSubtree) => walkTreeDepthFirst(nonNullSubtree)),
    option.map((results) =>
    func.pipe(results, readonlyArray.append(func.tuple(key, subtree))),
    ),
    option.getOrElse<ReadonlyArray<[string, NodeEntry]>>(() =>
    readonlyArray.of(func.tuple(key, subtree)),
    ),
    ),
    ),
    readonlyArray.flatten,
    );

    export const getSubtreeByLineage = (
    tree: Node,
    ...lineage: Lineage
    ): Node | null | undefined => {
    return func.pipe(
    lineage,
    readonlyNonEmptyArray.reduce(
    either.right<undefined, NodeEntry>(tree),
    (subtree, path) =>
    func.pipe(
    subtree,
    either.chain(
    func.flow(
    option.fromNullable,
    either.fromOption(func.constUndefined),
    either.map((value) => value[path]),
    either.filterOrElse(
    (value): value is NodeEntry => value !== undefined,
    func.constUndefined,
    ),
    ),
    ),
    ),
    ),
    either.fold(func.identity, func.identity),
    );
    };