import { IBinaryTree, IBaseType, getStringWidth as sw } from '../../../';
import { ILogOptions, ICharMatrix, Cable } from '../type';
import { DEFAULT_TREENODE_SPACING } from '../const';
import { parse } from './';

interface IBinaryTreeInfo {
  val: ICharMatrix;
  valLength: number;
  width: number;
  offset: number[][];
  margin: number[];
  left: IBinaryTreeInfo | null;
  right: IBinaryTreeInfo | null;
}

function getBinaryTreeInfo(tree: IBinaryTree<IBaseType>): IBinaryTreeInfo {
  const l = tree.left && getBinaryTreeInfo(tree.left);
  const r = tree.right && getBinaryTreeInfo(tree.right);
  const h = {
    val: parse(tree.val),
    valLength: parse(tree.val).w | 1,
    margin: [0, 0],
    left: l,
    right: r,
  } as IBinaryTreeInfo;
  const vl = h.valLength;
  const m = l || r;

  if (l && r) {
    const lo = l.offset;
    const ro = r.offset;
    const lw = l.width;
    const rw = r.width;
    let mg = -lw;

    // 计算 l 和 r 之间可以的最小间距
    for (let i = Math.min(lo.length, ro.length) - 1; i >= 0; --i) {
      mg = Math.max(mg, DEFAULT_TREENODE_SPACING - lw - ro[i][0] + lo[i][1]);
    }

    let w = lw + mg + rw;
    let o = ((lo[0][0] + (l.valLength >> 1) + (w - (rw - ro[0][1] + (r.valLength >> 1) + 1))) >> 1) - (vl >> 1);

    if (o < 0) {
      h.margin[0] = -o;
      w -= o;
      o = 0;
    }

    const m0 = h.margin[0];
    const offset = [[o, o + vl]];
    for (let i = 0, il = Math.max(lo.length, ro.length); i < il; ++i) {
      const a = lo[i];
      const b = ro[i];

      offset.push([a ? m0 + a[0] : m0 + lw + mg + b[0], b ? m0 + lw + mg + b[1] : m0 + a[1]]);
    }

    h.width = Math.max(w, ...offset.map(v => v[1]));
    h.offset = offset;
    h.margin[1] = mg;
  } else if (m) {
    const offset = m.offset.map(v => v.slice());
    let w = m.width;
    let o = m.offset[0][0] + ((m.valLength - vl) >> 1) + (l ? 1 : -1);

    if (o < 0) {
      offset.forEach(v => ([v[0], v[1]] = [v[0] - o, v[1] - o]));
      w -= o;
      h.margin[0] = -o;
      o = 0;
    }

    offset.unshift([o, o + vl]);
    h.width = Math.max(w, o + vl);
    h.offset = offset;
  } else {
    h.width = vl;
    h.offset = [[0, vl]];
  }

  return h;
}

export function parseBinaryTree(tree: IBinaryTree<IBaseType>, options: ILogOptions): ICharMatrix {
  const root = getBinaryTreeInfo(tree);
  const strs: Array<Array<string | ICharMatrix>> = new Array(root.offset.length * 2 - 1).fill(0).map(() => []);
  const lens: number[] = new Array(strs.length).fill(0); // 记录目前已多长
  let task = [{ h: root, p: 0 }];
  let level = 0;

  while (task.length) {
    const newTask: typeof task = [];

    task.forEach(({ h, p }) => {
      const { left: l, right: r, val: v, valLength: vl, offset: o, margin: m } = h;
      let i = level * 2;

      // 处理节点
      strs[i].push(' '.repeat(p + o[0][0] - lens[i]));
      strs[i].push(v);
      lens[i] = p + o[0][0] + v.w;
      i++;

      // 处理连线
      if (l || r) {
        let s = '';
        // 添加 left
        if (l) {
          strs[i].push(' '.repeat(p + o[1][0] + (l.valLength >> 1) - lens[i]));
          s = Cable.RB + Cable.H.repeat(o[0][0] + (vl >> 1) - o[1][0] - (l.valLength >> 1) - 1);
          strs[i].push({
            v: [s],
            w: sw(s),
            h: 1,
            c: r ? 'greenBright' : 'yellowBright',
          });
        } else {
          strs[i].push(' '.repeat(p + o[0][0] + (vl >> 1) - lens[i]));
        }

        // 添加中间
        s = l && r ? Cable.MT : l ? Cable.LT : Cable.RT;
        strs[i].push({
          v: [s],
          w: sw(s),
          h: 1,
          c: l && r ? 'greenBright' : l ? 'yellowBright' : 'blueBright',
        });
        lens[i] = p + o[0][0] + (vl >> 1) + 1;

        // 添加 right
        if (r) {
          s = Cable.H.repeat(p + o[1][1] - (r.valLength >> 1) - 1 - lens[i]) + Cable.LB;
          strs[i].push({
            v: [s],
            w: sw(s),
            h: 1,
            c: l ? 'greenBright' : 'blueBright',
          });
          lens[i] = p + o[1][1] - (r.valLength >> 1);
        }
      }

      if (l) {
        newTask.push({ h: l, p: p + m[0] });
      }

      if (r) {
        newTask.push({ h: r, p: p + m[0] + (l ? l.width : 0) + m[1] });
      }
    });

    task = newTask;
    level++;
  }

  const logStrs: string[] = [];

  for (let i = 0, l = strs.length; i < l; ++i) {
    const s = strs[i].map(v => (typeof v === 'string' ? v : v.v[0])).join('');
    logStrs[i] = s + ' '.repeat(root.width - sw(s));
  }

  return { v: logStrs, w: sw(logStrs[0]), h: logStrs.length };
}