// https://github.com/exercism/typescript/blob/master/exercises/binary-search-tree/README.md

enum NodeKind {
  Empty,
  Node,
}

type NodeEmpty = { kind: NodeKind.Empty };
type NodeData = {
  kind: NodeKind.Node;
  data: number;
  left: Node;
  right: Node;
};
type Node = NodeEmpty | NodeData;

const NODE_EMPTY = { kind: NodeKind.Empty } as const;

const newNodeData: (d: number) => Node = (data) => ({
  kind: NodeKind.Node,
  data,
  left: NODE_EMPTY,
  right: NODE_EMPTY,
});

function insert(node: NodeData, data: number): void {
  if (data <= node.data) {
    if (node.left.kind === NodeKind.Node) insert(node.left, data);
    else node.left = newNodeData(data);
    return;
  }

  if (node.right.kind === NodeKind.Node) insert(node.right, data);
  else node.right = newNodeData(data);
}

function* makeIterator(tree: Node): Generator<number, unknown, unknown> {
  const stack: NodeData[] = [];
  let node: NodeData | undefined =
    tree.kind === NodeKind.Node ? tree : undefined;

  while (node || stack.length > 0) {
    while (node) {
      stack.push(node);
      node = node.left.kind === NodeKind.Node ? node.left : undefined;
    }

    const current = stack.pop()!;
    node = current.right.kind === NodeKind.Node ? current.right : undefined;
    yield current.data;
  }
  return;
}

type ExportEmpty = [];
type ExportSubTree = ExportNode | number | undefined;
type ExportNode = [ExportSubTree, number, ExportSubTree];
type ExportTree = ExportEmpty | ExportNode;

const exportLeft: (n: NodeData) => ExportSubTree = (node) =>
  node.left.kind === NodeKind.Node ? exportHelper(node.left) : undefined;

const exportRight: (n: NodeData) => ExportSubTree = (node) =>
  node.right.kind === NodeKind.Node ? exportHelper(node.right) : undefined;

function exportHelper(node: NodeData): ExportSubTree {
  const left = exportLeft(node);
  const right = exportRight(node);
  return left || right ? [left, node.data, right] : node.data;
}

function exportTree(root: Node): ExportTree {
  switch (root.kind) {
    case NodeKind.Node:
      return [exportLeft(root), root.data, exportRight(root)];
    default:
      return [];
  }
}

class BinarySearchTree {
  #tree: Node = NODE_EMPTY;

  constructor(values?: Iterable<number>) {
    // Note: Due to coercion `values != null`
    // fails for both `null` and `undefined`
    if (values != null && typeof values[Symbol.iterator] === 'function')
      for (const v of values) this.insert(v);
  }

  insert(data: number): void {
    const tree = this.#tree;
    if (tree.kind === NodeKind.Node) insert(tree, data);
    else this.#tree = newNodeData(data);
  }

  [Symbol.iterator](): Iterator<number, unknown> {
    return makeIterator(this.#tree);
  }

  export(): ExportTree {
    return exportTree(this.#tree);
  }
}

export default BinarySearchTree;

// https://www.typescriptlang.org/docs/handbook/typescript-in-5-minutes-func.html#discriminated-unions