// Because working with row and column-spanning cells is not quite
// trivial, this code builds up a descriptive structure for a given
// table node. The structures are cached with the (persistent) table
// nodes as key, so that they only have to be recomputed when the
// content of the table changes.
//
// This does mean that they have to store table-relative, not
// document-relative positions. So code that uses them will typically
// compute the start position of the table and offset positions passed
// to or gotten from this structure by that amount.

import { Node } from "prosemirror-model";
import { CellAttrs, EditorSchema, NodeTypeName } from "../schema";
import { Bias, CartesianAxis, TableNode, TablePosOfCell } from "../types";
import { EdgeRect } from "./EdgeRect";
import { zeroes } from "@heydovetail/array";

const cache = new WeakMap<Node, TableMap>();
const readFromCache = (key: Node) => cache.get(key);
const addToCache = (key: Node, value: TableMap) => {
  cache.set(key, value);
  return value;
};

export const enum TableMapProblemType {
  COLLISION,
  COLWIDTH_MISMATCH,
  MISSING,
  OVERLONG_ROWSPAN
}

export interface CollisionProblem {
  type: TableMapProblemType.COLLISION;
  row: number;
  pos: number;
  n: number;
}

export interface ColWidthMismatchProblem {
  type: TableMapProblemType.COLWIDTH_MISMATCH;
  pos: number;
  colwidth: Array<number>;
}

export interface MissingProblem {
  type: TableMapProblemType.MISSING;
  row: number;
  // The number of missing cells in the row.
  n: number;
}

export interface OverlongRowspanProblem {
  type: TableMapProblemType.OVERLONG_ROWSPAN;
  pos: number;
  n: number;
}

export type TableMapProblem = CollisionProblem | ColWidthMismatchProblem | MissingProblem | OverlongRowspanProblem;

export class TableMap {
  /**
   * A table map describes the structore of a given table. To avoid recomputing
   * them all the time, they are cached per table node. To be able to do that,
   * positions saved in the map are relative to the start of the table (i.e.
   * first position in the table), rather than the start of the document.
   *
   * @param width The width of the table
   * @param height The table's height
   * @param map A width * height array with the start position of the cell
   * covering that part of the table in each slot
   * @param problems An optional array of problems (cell overlap or
   * non-rectangular shape) for the table, used by the table normalizer.
   */
  constructor(
    public readonly width: number,
    public readonly height: number,
    public readonly map: ReadonlyArray<TablePosOfCell>,
    // This is mutated via findBadColWidths
    public problems: Array<TableMapProblem> | null
  ) {}

  /**
   * Find the dimensions of the cell at the given position.
   */
  public findCell(pos: TablePosOfCell): EdgeRect {
    for (let i = 0; i < this.map.length; i++) {
      const curPos = this.map[i];

      if (curPos != pos) {
        continue;
      }

      const left = i % this.width;
      const top = (i / this.width) | 0;

      let right = left + 1;
      let bottom = top + 1;

      for (let j = 1; right < this.width && this.map[i + j] == curPos; j++) {
        right++;
      }

      for (let j = 1; bottom < this.height && this.map[i + this.width * j] == curPos; j++) {
        bottom++;
      }

      return new EdgeRect(left, top, right, bottom);
    }
    throw new RangeError("No cell with offset " + pos + " found");
  }

  /**
   * Find the column index for a cell.
   *
   * @param pos Position of a cell.
   */
  public columnIndex(pos: TablePosOfCell): number {
    for (let i = 0; i < this.map.length; i++) {
      if (this.map[i] == pos) {
        return i % this.width;
      }
    }

    throw new RangeError("No cell with offset " + pos + " found");
  }

  /**
   * Find the row index for a cell.
   *
   * @param pos Position of a cell.
   */
  public rowIndex(pos: TablePosOfCell): number {
    for (let i = 0; i < this.map.length; i++) {
      if (this.map[i] == pos) {
        return Math.floor(i / this.width);
      }
    }

    throw new RangeError("No cell with offset " + pos + " found");
  }

  /**
   * Find the next cell in the given direction, starting from the cell at `pos`, if any.
   */
  public nextCell(pos: TablePosOfCell, axis: CartesianAxis, bias: Bias): number | null | undefined {
    const { left, right, top, bottom } = this.findCell(pos);
    switch (axis) {
      case CartesianAxis.HORIZONTAL: {
        if (bias == Bias.BACKWARD ? left == 0 : right == this.width) {
          return null;
        }
        return this.map[top * this.width + (bias == Bias.BACKWARD ? left - 1 : right)];
      }
      case CartesianAxis.VERTICAL: {
        if (bias == Bias.BACKWARD ? top == 0 : bottom == this.height) {
          return null;
        }
        return this.map[left + this.width * (bias == Bias.BACKWARD ? top - 1 : bottom)];
      }
      default: {
        const exhausted: never = axis;
        throw exhausted;
      }
    }
  }

  /**
   * Get the rectangle spanning the two given cells.
   */
  public rectBetween(a: TablePosOfCell, b: TablePosOfCell): EdgeRect {
    const { left: leftA, right: rightA, top: topA, bottom: bottomA } = this.findCell(a);
    const { left: leftB, right: rightB, top: topB, bottom: bottomB } = this.findCell(b);
    return new EdgeRect(Math.min(leftA, leftB), Math.min(topA, topB), Math.max(rightA, rightB), Math.max(bottomA, bottomB));
  }

  /**
   * Return the position of all cells that have the top left corner in the given rectangle.
   */
  public cellsInRect(rect: EdgeRect): Array<number> {
    const result = [];
    const seen = [];

    for (let row = rect.top; row < rect.bottom; row++) {
      for (let col = rect.left; col < rect.right; col++) {
        const index = row * this.width + col;
        const pos = this.map[index];

        if (seen.indexOf(pos) > -1) {
          continue;
        }
        seen.push(pos);

        if (
          (col != rect.left || col === 0 || this.map[index - 1] != pos) &&
          (row != rect.top || row === 0 || this.map[index - this.width] != pos)
        ) {
          result.push(pos);
        }
      }
    }
    return result;
  }

  /**
   * Return the position at which the cell at the given row and column starts,
   * or would start, if a cell started there.
   */

  public positionAt(row: number, col: number, table: Node): number {
    for (let i = 0, rowStart = 0; ; i++) {
      const rowEnd = rowStart + table.child(i).nodeSize;
      if (i == row) {
        let index = col + row * this.width;
        const rowEndIndex = (row + 1) * this.width;
        // Skip past cells from previous rows (via rowspan)
        while (index < rowEndIndex && this.map[index] < rowStart) {
          index++;
        }
        return index == rowEndIndex ? rowEnd - 1 : this.map[index];
      }
      rowStart = rowEnd;
    }
  }

  /**
   * Find the table map for the given table node.
   */
  public static get(table: TableNode): TableMap {
    const existing = readFromCache(table);
    return existing !== undefined ? existing : addToCache(table, computeMap(table));
  }
}

/**
 * Compute a table map.
 */
function computeMap(table: Node<EditorSchema>): TableMap {
  if (table.type.name !== ("tbl" as NodeTypeName)) {
    throw new RangeError("Not a table node: " + table.type.name);
  }

  const width = findWidth(table);
  const height = table.childCount;
  const map: Array<TablePosOfCell> = [];
  let mapPos = 0;
  let problems: Array<TableMapProblem> | null = null;
  const colWidths = [];

  for (let i = 0, e = width * height; i < e; i++) {
    map[i] = 0 as TablePosOfCell;
  }

  for (let row = 0, pos = 0; row < height; row++) {
    const rowNode = table.child(row);
    pos++;
    for (let i = 0; ; i++) {
      while (mapPos < map.length && map[mapPos] != 0) {
        mapPos++;
      }
      if (i == rowNode.childCount) {
        break;
      }
      const cellNode = rowNode.child(i);
      const { colspan, rowspan, colwidth } = cellNode.attrs;
      for (let h = 0; h < rowspan; h++) {
        if (h + row >= height) {
          if (problems === null) {
            problems = [];
          }
          problems.push({ type: TableMapProblemType.OVERLONG_ROWSPAN, pos, n: rowspan - h });
          break;
        }
        const start = mapPos + h * width;
        for (let w = 0; w < colspan; w++) {
          if (map[start + w] == 0) {
            map[start + w] = pos as TablePosOfCell;
          } else {
            if (problems === null) {
              problems = [];
            }
            problems.push({ type: TableMapProblemType.COLLISION, row, pos, n: colspan - w });
          }
          const colW = colwidth && colwidth[w];
          if (colW) {
            const widthIndex = ((start + w) % width) * 2;
            const prev = colWidths[widthIndex];
            if (prev == null || (prev != colW && colWidths[widthIndex + 1] == 1)) {
              colWidths[widthIndex] = colW;
              colWidths[widthIndex + 1] = 1;
            } else if (prev == colW) {
              colWidths[widthIndex + 1]++;
            }
          }
        }
      }
      mapPos += colspan;
      pos += cellNode.nodeSize;
    }
    const expectedPos = (row + 1) * width;
    let missing = 0;

    while (mapPos < expectedPos) {
      if (map[mapPos++] == 0) {
        missing++;
      }
    }

    if (missing > 0) {
      if (problems === null) {
        problems = [];
      }
      problems.push({ type: TableMapProblemType.MISSING, row, n: missing });
    }

    pos++;
  }

  const tableMap = new TableMap(width, height, map, problems);
  let badWidths = false;

  // For columns that have defined widths, but whose widths disagree
  // between rows, fix up the cells whose width doesn't match the
  // computed one.
  for (let i = 0; !badWidths && i < colWidths.length; i += 2) {
    if (colWidths[i] != null && colWidths[i + 1] < height) {
      badWidths = true;
    }
  }

  if (badWidths) {
    findBadColWidths(tableMap, colWidths, table);
  }

  return tableMap;
}

function findWidth(table: Node): number {
  let width = -1;
  let hasRowSpan = false;

  for (let row = 0; row < table.childCount; row++) {
    const rowNode = table.child(row);
    let rowWidth = 0;

    if (hasRowSpan) {
      for (let j = 0; j < row; j++) {
        const prevRow = table.child(j);
        for (let i = 0; i < prevRow.childCount; i++) {
          const cell = prevRow.child(i);
          if (j + cell.attrs.rowspan > row) {
            rowWidth += cell.attrs.colspan;
          }
        }
      }
    }

    for (let i = 0; i < rowNode.childCount; i++) {
      const cell = rowNode.child(i);
      rowWidth += cell.attrs.colspan;
      if (cell.attrs.rowspan > 1) {
        hasRowSpan = true;
      }
    }

    if (width == -1) {
      width = rowWidth;
    } else if (width != rowWidth) {
      width = Math.max(width, rowWidth);
    }
  }
  return width;
}

function findBadColWidths(map: TableMap, colWidths: ReadonlyArray<number | undefined>, table: Node): void {
  for (let i = 0, seen = []; i < map.map.length; i++) {
    const pos = map.map[i];

    if (seen.indexOf(pos) > -1) {
      continue;
    }
    seen.push(pos);

    const node = table.nodeAt(pos);
    if (node != null) {
      let updated: Array<number> | null = null;
      const attrs = node.attrs as CellAttrs;

      for (let j = 0; j < attrs.colspan; j++) {
        const col = (i + j) % map.width;
        const colWidth = colWidths[col * 2];
        if (colWidth !== undefined && (attrs.colwidth == null || attrs.colwidth[j] != colWidth)) {
          if (updated === null) {
            updated = freshColWidth(attrs);
          }
          updated[j] = colWidth;
        }
      }

      if (updated !== null) {
        if (map.problems === null) {
          map.problems = [];
        }

        map.problems.unshift({ type: TableMapProblemType.COLWIDTH_MISMATCH, pos, colwidth: updated });
      }
    }
  }
}

function freshColWidth(attrs: CellAttrs) {
  return attrs.colwidth != null ? attrs.colwidth.slice() : zeroes(attrs.colspan);
}