printTree.test.ts

import { Tree, TNode } from './printTree';

test("Only root", () => {
  const root = new TNode("1");
  const tree = new Tree(root);
  tree.print();
  expect(true).toBe(true);
})

test("same value length, height 2", () => {
  const root = new TNode("1");
  root.addChild(new TNode("2"));
  root.addChild(new TNode("3"));
  root.addChild(new TNode("4"));
  const tree = new Tree(root);
  tree.print();
  expect(true).toBe(true);
})

test("same value length, height 3", () => {
  const root = new TNode("1");
  root.addChild(new TNode("2"));
  const three = new TNode("3");
  root.addChild(three);
  three.addChild(new TNode("5"));
  three.addChild(new TNode("6"));
  three.addChild(new TNode("7"));
  root.addChild(new TNode("4"));
  const tree = new Tree(root);
  tree.print();
  expect(true).toBe(true);
})

test("different value lengths, height 3", () => {
  const root = new TNode("1");
  root.addChild(new TNode("2"));
  const three = new TNode("3333");
  root.addChild(three);
  three.addChild(new TNode("5"));
  three.addChild(new TNode("6"));
  three.addChild(new TNode("7"));
  root.addChild(new TNode("4"));
  const tree = new Tree(root);
  tree.print();
  expect(true).toBe(true);
})

test("different value lengths, height 3 - 2", () => {
  const root = new TNode("1");
  const two = new TNode("2");
  two.addChild(new TNode("88"));
  two.addChild(new TNode("9"));
  root.addChild(two);
  const three = new TNode("3333");
  root.addChild(three);
  three.addChild(new TNode("5"));
  three.addChild(new TNode("6"));
  three.addChild(new TNode("7"));
  root.addChild(new TNode("4"));
  const tree = new Tree(root);
  tree.print();
  expect(true).toBe(true);
})

test("different value lengths, height 4", () => {
  const root = new TNode("1");
  const two = new TNode("2");
  two.addChild(new TNode("88"));
  const nine = new TNode("9");
  nine.addChild(new TNode("10"));
  nine.addChild(new TNode("11"));
  nine.addChild(new TNode("12"));
  two.addChild(nine);
  root.addChild(two);
  const three = new TNode("3333");
  root.addChild(three);
  three.addChild(new TNode("5"));
  three.addChild(new TNode("6"));
  const seven = new TNode("7");
  seven.addChild(new TNode("13"));
  seven.addChild(new TNode("14"));
  three.addChild(seven);
  root.addChild(new TNode("4"));
  const tree = new Tree(root);
  tree.print();
  expect(true).toBe(true);
})

printTree.ts

type Kind = "ROOT" | "FIRST" | "MIDDLE" | "LAST";
type ParentalStatus = "PARENT" | "NOT PARENT";
type PrefixEdgeDict = { [k in Kind]: string };
type SuffixEdgeDict = { [b in ParentalStatus]: string };
type PipeDict = { [k in Kind]: string };
type WorkingTable = WTRecord[];
type WTRecord = {
  offset: number,
  kind: Kind | undefined
};

const prefixEdgeDict: PrefixEdgeDict = {
  "ROOT": "",
  "FIRST": "-- ",
  "MIDDLE": "|- ",
  "LAST": "|_ ",
};

const suffixEdgeDict: SuffixEdgeDict = {
  "PARENT": " -",
  "NOT PARENT": ""
};

const pipeDict: PipeDict = {
  "ROOT": " ",
  "FIRST": "|",
  "MIDDLE": "|",
  "LAST": " "
};

export class Tree {
  root: TNode;
  constructor(root: TNode) {
    this.root = root;
  }
  toString(): string {
    // Preparation
    const workingTable: WorkingTable = [
      {
        offset: 0,
        kind: "ROOT"
      },
      {
        offset: this.root.v.length + 1,
        kind: undefined
      }
    ];
    const lines: string[] = [];
    this.root.generateLines(workingTable, 0, "ROOT", lines);
    return lines.join("\n");
  }
  print() {
    console.log(this.toString());
  }
}

export class TNode {
  v: string;
  children: TNode[];
  constructor(v: string) {
    this.v = v;
    this.children = [];
  }
  addChild(child: TNode) {
    this.children.push(child);
  }
  private parentalStatus(): ParentalStatus {
    return this.children.length > 0 ? "PARENT" : "NOT PARENT";
  }
  static runPipes(workingTable: WorkingTable, level: number): string {
    const acc = [];
    for (let i = 0; i < level; i++) {
      const record = workingTable[i];
      const offsetStr = " ".repeat(record.offset);
      const pipe = pipeDict[record.kind!];
      acc.push(offsetStr + pipe);
    }
    const currentRecord = workingTable[level];
    const offsetStr = " ".repeat(currentRecord.offset);
    acc.push(offsetStr);
    return acc.join("");
  }
  generateLines(workingTable: WorkingTable, level: number, kind: Kind, lines: string[]) {
    workingTable[level].kind = kind;
    const prefixEdge = prefixEdgeDict[kind];
    const parentalStatus = this.parentalStatus();
    const suffixEdge = suffixEdgeDict[parentalStatus];

    if (kind === "FIRST") {
      const line = lines.pop()!;
      const offsetStr = parentalStatus === "PARENT" ? "-".repeat(workingTable[level+1].offset-this.v.length-4) : ""
      const updatedLine = line.concat(prefixEdge + this.v + suffixEdge + offsetStr);
      lines.push(updatedLine);
    } else {
      const prefixPipes = TNode.runPipes(workingTable, level);
      const line = prefixPipes + prefixEdge + this.v + suffixEdge;
      lines.push(line);
    }
    if (parentalStatus === "PARENT") {
      // Update the record for the next next level
      workingTable[level + 2] = {
        offset: this.children.reduce((max, c) => Math.max(max, c.v.length), 0) + 4,
        kind: undefined
      };
      const firstChild = this.children[0];
      firstChild.generateLines(workingTable, level + 1, "FIRST", lines);
      for (let i = 1; i < this.children.length - 1; i++) {
        const middleChild = this.children[i];
        middleChild.generateLines(workingTable, level + 1, "MIDDLE", lines);
      }
      if (this.children.length > 1) {
        const lastChild = this.children[this.children.length - 1];
        lastChild.generateLines(workingTable, level + 1, "LAST", lines);
      }
    }
  }
}