import { Method, Request, Response } from "./types";

/**
 * A handler for a request
 */
export type Handler = (
  ctx: RouteContext,
  req: Request,
  res: Response,
) => Promise<void>;

export default class Router {
  private readonly trees: { [method in Method]?: Node } = {};

  /**
   * register adds a new handler to the router for the given method and path
   *
   * @throws {Error} If a handler is already registered for the given method and path
   * @throws {Error} If a dynamic segment is registered without a name (i.e. `/users/:/comments` would result in an
   *   error)
   */
  register(method: Method, path: string, handler: Handler) {
    const segments = routeSplit(this.cleanPath(path));
    let methods: Method[] = [method];
    if (method === Method.Any) {
      methods = [
        Method.GET,
        Method.POST,
        Method.PUT,
        Method.PATCH,
        Method.DELETE,
      ];
    }

    for (const method of methods) {
      let tree = this.trees[method];
      if (tree === undefined) {
        tree = new Node(null, "/", EdgeType.Static);
        this.trees[method] = tree;
      }
      this._register(tree, path, segments, handler);
    }
  }

  private _register(
    node: Node,
    path: string,
    segments: string[],
    handler: Handler,
  ) {
    let remaining = "";
    let dynamicSegmentIdx = 0;
    const placeholderNames: string[] = [];

    // For each segment
    let wildcardSegmentFound = false;
    for (const segment of segments) {
      if (segment.length === 0) {
        throw new Error(`Empty segment in path: ${path}`);
      }
      if (wildcardSegmentFound) {
        throw new Error(
          `Wildcard segment must be the last segment in a path: ${path}`,
        );
      }

      switch (segment[0]) {
        case ":":
          placeholderNames.push(segment.slice(1));
          node = node.insertDynamic(`${dynamicSegmentIdx++}`);
          break;
        case "*":
          placeholderNames.push(segment.slice(1));
          node = node.insertWildcard(`${dynamicSegmentIdx++}`);
          wildcardSegmentFound = true;
          break;
        default:
          // Find the closest node to the path
          [node, remaining] = node.find(segment, false);

          // If we have a remaining path, then we need to insert a new node
          if (remaining !== "") {
            node = node.insertStatic(remaining);
          }
          break;
      }
    }

    node.register(handler, placeholderNames);
  }

  /**
   * Find returns the handler for the given method and path or null if not found
   */
  find(method: Method, path: string): RouteContext | null {
    const cleanedPath = this.cleanPath(path);
    const tree = this.trees[method];
    if (tree === undefined) {
      return null;
    }
    let [node, remaining, params, , swapTrailingSlashes] = tree.find(
      cleanedPath,
      true,
    );

    let tsrSuggestion: string | undefined;
    if (remaining !== "" || node.handler === undefined) {
      // Trailing Slash Fix: If we didn't find a handler after greedily applying trailing slash fixes as we walked the
      // path, this means we might need to apply a trailing slash fix to the nearest handler and find from that point
      // down.
      if (remaining === "" || remaining[remaining.length - 1] !== "/") {
        const [tsfNode, tsfRemaining, newParams] = node.find(
          remaining + "/",
          true,
        );

        if (tsfRemaining === "" && tsfNode.handler !== undefined) {
          // If we found a match, then we need to apply the trailing slash suggestion
          swapTrailingSlashes = true;
          node = tsfNode;
          remaining = "";
          params = [...params, ...newParams];
        }
      }

      if (remaining !== "" || node.handler === undefined) {
        return null;
      }
    }

    if (swapTrailingSlashes) {
      if (path.length > 0 && path[path.length - 1] === "/") {
        tsrSuggestion = path.slice(0, -1);
      } else {
        tsrSuggestion = path + "/";
      }
    }

    return {
      handler: node.handler.handler,
      path: node.path,
      paramNames: node.handler.placeholders,
      params,
      tsfSuggestion: tsrSuggestion,
    };
  }

  /**
   * clean path ensures there is no leading slash
   */
  private cleanPath(path: string) {
    if (path.length > 0 && path[0] === "/") {
      path = path.slice(1);
    }

    return path;
  }

  /**
   * debug returns a string representation of the router tree,
   * this is mainly used for unit test snapshots as a simplified
   * way to verify the tree is being built correctly.
   */
  debug(): string {
    let out = "";

    let numNodes = 0;
    let sumNodeDepth = 0;
    let numHandlers = 0;
    let sumDepthHandlers = 0;
    let maxDepth = 0;

    const entires = Object.entries(this.trees);

    for (let i = 0; i < entires.length; i++) {
      const [method, tree] = entires[i];

      let indent = "   ";
      if (i === entires.length - 1) {
        indent = `  ${indent}`;
      } else {
        indent = ` |${indent}`;
      }

      const debugInfo = tree.debug(indent, 1);

      if (i === entires.length - 1) {
        out += ` └─ ${method} (${debugInfo.numHandlers} handlers, avg depth: ${
          Math.round(
            (debugInfo.sumDepthHandlers / debugInfo.numHandlers) * 100,
          ) / 100
        })\n    "/"`;
      } else {
        out += ` ├─ ${method} (${debugInfo.numHandlers} handlers, avg depth: ${
          Math.round(
            (debugInfo.sumDepthHandlers / debugInfo.numHandlers) * 100,
          ) / 100
        })\n |  "/"`;
      }

      out += debugInfo.str;
      numNodes += debugInfo.numNodes;
      sumNodeDepth += debugInfo.sumNodeDepth;
      numHandlers += debugInfo.numHandlers;
      sumDepthHandlers += debugInfo.sumDepthHandlers;
      maxDepth = Math.max(maxDepth, debugInfo.maxDepth);
    }

    return `Number Nodes: ${numNodes} (avg depth: ${
      Math.round((sumNodeDepth / numNodes) * 100) / 100
    })
Number Handlers: ${numHandlers} (avg depth: ${
      Math.round((sumDepthHandlers / numHandlers) * 100) / 100
    })
Max Depth: ${maxDepth}

Router
${out}`;
  }
}

export interface RouteContext {
  handler: Handler; // The handler to call
  path: string; // The registered path
  paramNames: string[]; // The names of the params extracted from the path
  params: string[]; // The params extracted from the path

  /**
   * If set then there was no exact match for the path, but we found a route that
   * matched if we where to either add or remove a trailing slash. This field would
   * then be set to the true path to use.
   *
   * i.e. if the user requested `/users` but the route is registered as `/users/`, then
   *      we would return the `/users/` handler and set this field to `/users/`.
   *
   * The opposite is also true, if the user requested `/users/` but the route was reigstered
   *  as `/users`, then we would return the `/users` handler and set this field to `/users`.
   */
  tsfSuggestion?: string;
}

/**
 * createParamsObj returns an object with the param names as keys and the values extracted from the route request
 */
export function createParamsObj(ctx: RouteContext): Record<string, string> {
  if (ctx.paramNames.length !== ctx.params.length) {
    throw new Error(
      `Invalid number of params, expected ${ctx.paramNames.length}, got ${ctx.params.length}`,
    );
  }

  const params: Record<string, string> = {};
  for (let i = 0; i < ctx.paramNames.length; i++) {
    params[ctx.paramNames[i]] = ctx.params[i];
  }
  return params;
}

export function reconstructRegisteredURL(ctx: RouteContext): string {
  let url = ctx.path;
  for (let i = ctx.paramNames.length - 1; i >= 0; i--) {
    url = url.replace(`:${i}`, `:${ctx.paramNames[i]}`);

    if (i === ctx.paramNames.length - 1) {
      url = url.replace(`*${i}`, `*${ctx.paramNames[i]}`);
    }
  }
  return url;
}

enum EdgeType {
  Static,
  Dynamic,
  Wildcard,
}

type RemainingPath = string;
type FoundParams = string[];
type NodeMatches = boolean;
type TrailingSlashSuggestion = boolean;
type NodeFindResult = [
  Node,
  RemainingPath,
  FoundParams,
  NodeMatches,
  TrailingSlashSuggestion,
];

class Node {
  /**
   * The parent of this node
   */
  parent: Node | null;

  /**
   * The prefix to get to this node from the parent
   */
  prefixToNode: string;

  /**
   * The type of the prefix to get to this node from the parent
   */
  prefixType: EdgeType;

  /**
   * Edges from this node
   */
  children: Node[] = [];

  /**
   * The dynamic child of this node, if any
   */
  dynamicChild: Node | null = null;

  /**
   * The wildcard child of this node, if any
   */
  wildcardChild: Node | null = null;

  /**
   * Handlers registered at this node
   */
  handler?: { placeholders: string[]; handler: Handler };

  constructor(parent: Node | null, prefixToNode: string, prefixType: EdgeType) {
    this.parent = parent;
    this.prefixToNode = prefixToNode;
    this.prefixType = prefixType;
  }

  /**
   * Path returns the full path to this node as it would have been
   * registered with the router.
   */
  get path(): string {
    const parentPath = this.parent?.path ?? "";
    switch (this.prefixType) {
      case EdgeType.Static:
        return `${parentPath}${this.prefixToNode}`;
      case EdgeType.Dynamic:
        return `${parentPath}:${this.prefixToNode}`;
      case EdgeType.Wildcard:
        return `${parentPath}*${this.prefixToNode}`;
    }
  }

  /**
   * Find returns the node and the remaining path to match, walking
   * down the tree until it finds a match. If no match is found,
   * it will return the closest node and the remaining path to match.
   * If a match is found, then that node will be returned along with an
   * empty string.
   */
  find(path: string, forRouteFind: boolean): NodeFindResult {
    if (path === "") {
      if (
        this.wildcardChild !== null &&
        forRouteFind &&
        this.wildcardChild.handler !== undefined
      ) {
        return [this.wildcardChild, "", [path], true, false];
      }

      // Check for a case where we've ended up on a node which has no path left and no handler
      // but it has a child which is just a trailing slash and has a handler, if so, return that as a trailing slash fix
      //
      // TSF Use Case: `/foo/bar` => `/foo/bar/` (with the nodes being ["/foo/bar" -> "/"])
      if (
        forRouteFind &&
        this.handler === undefined &&
        this.prefixToNode[this.prefixToNode.length - 1] !== "/"
      ) {
        for (const child of this.children) {
          if (child.prefixToNode === "/" && child.handler !== undefined) {
            return [child, "", [], true, true];
          }
        }
      }

      return [this, "", [], !forRouteFind || this.handler !== undefined, false];
    }

    let closest: NodeFindResult = [this, path, [], false, false];

    const tsrOption =
      path[path.length - 1] === "/" ? path.slice(0, -1) : path + "/";

    for (const child of this.children) {
      // Add an additional check for to see the child would match if we did a trailing slash fix (either adding or removing the trailing slash)
      //
      // TSF Use Case: `/foo/bar` => `/foo/bar/` (with the nodes being ["/foo/" -> "bar/" -> "baz"])
      // TSF Use Case: `/foo/bar/` => `/foo/bar` (with the nodes being ["/foo/" -> "bar" -> "baz"])
      const isTSFMatch =
        forRouteFind &&
        child.handler !== undefined &&
        child.prefixToNode === tsrOption;

      if (path.startsWith(child.prefixToNode) || isTSFMatch) {
        // Otherwise recurse into the child with the remaining path
        closest = child.find(
          path.slice(child.prefixToNode.length),
          forRouteFind,
        );

        if (isTSFMatch) {
          closest[4] = true;
        }

        if (closest[3]) {
          // If we found an exact match, then return it
          // otherwise keep looking for a closer match
          return closest;
        }

        break;
      }
    }

    // If after checking our static children we didn't find a match, let's check if the path we where called
    // with was just a trailing slash and if we have a handler, we're a strong static match
    //
    // TSF Use Case: "/foo/bar/" => "/foo/bar" (with the nodes being ["/foo/bar"])
    if (forRouteFind && path === "/" && this.handler !== undefined) {
      return [this, "", [], true, true]; // strong literal match
    }

    if (forRouteFind) {
      // Then check the dynamic child
      if (this.dynamicChild !== null) {
        const nextSegment = path.indexOf("/");
        const thisParam =
          nextSegment === -1 ? path : path.slice(0, nextSegment);
        const [finalNode, remaining, params, foundHandler, tsrFix] =
          this.dynamicChild.find(path.slice(thisParam.length), forRouteFind);

        if (remaining === "") {
          return [
            finalNode,
            remaining,
            [thisParam, ...params],
            foundHandler,
            tsrFix,
          ];
        }
      }

      // And the wildcard
      if (this.wildcardChild !== null) {
        return [
          this.wildcardChild,
          "",
          [path],
          this.wildcardChild.handler !== undefined,
          false,
        ];
      }
    }

    return closest;
  }

  /**
   * insert adds a new node to the tree for the given path
   */
  insertStatic(path: string): Node {
    for (let i = 0; i < this.children.length; i++) {
      const child = this.children[i];

      const commonPrefix = longestCommonPrefix(path, child.prefixToNode);
      if (commonPrefix.length > 0) {
        // If we found a common prefix for this child, then we want to insert
        // a new node for the common prefix and move the existing child to be
        // a child of the new node. Then we can insert the new path into that new node.
        const newChild = new Node(this, commonPrefix, EdgeType.Static);
        child.parent = newChild;
        child.prefixToNode = child.prefixToNode.slice(commonPrefix.length);
        newChild.children.push(child);
        this.children[i] = newChild;

        // If the new path is the same length as the common prefix, then we're done
        // and can return the new node we just created.
        if (path.length == commonPrefix.length) {
          return newChild;
        }

        // Otherwise, we need to add a new edge to the new node for the remaining
        // and return that node.
        const remainingNewPath = path.slice(commonPrefix.length);
        return newChild.insertStatic(remainingNewPath);
      }
    }

    const node = new Node(this, path, EdgeType.Static);
    this.children.push(node);
    this.children.sort((a, b) => a.prefixToNode.localeCompare(b.prefixToNode));
    return node;
  }

  /**
   * insertDynamic adds a new node to the tree for the given dynamic path
   */
  insertDynamic(keyName: string): Node {
    if (this.dynamicChild === null) {
      if (this.wildcardChild !== null) {
        throw new Error(
          `Wildcard sub route already registered for ${this.path}`,
        );
      }

      this.dynamicChild = new Node(this, keyName, EdgeType.Dynamic);
    }
    return this.dynamicChild;
  }

  insertWildcard(keyName: string): Node {
    if (this.wildcardChild === null) {
      if (this.dynamicChild !== null) {
        throw new Error(
          `Dynamic sub route already registered for ${this.path}`,
        );
      }

      if (this.prefixToNode[this.prefixToNode.length - 1] !== "/") {
        throw new Error(
          `Wildcard sub route must be preceded by a slash for ${this.path} (prefix was: ${this.prefixToNode})`,
        );
      }

      this.wildcardChild = new Node(this, keyName, EdgeType.Wildcard);
    }
    return this.wildcardChild;
  }

  /**
   * register adds a handler to the node for the given method
   *
   * @throws {Error} If a handler is already registered for the given method
   */
  register(handler: Handler, placeholderNames: string[]) {
    if (this.handler !== undefined) {
      throw new Error(`Handler already registered for ${this.path}`);
    }
    this.handler = {
      placeholders: placeholderNames,
      handler,
    };
  }

  /**
   * debug returns a string representation of the node and its children
   */
  debug(indent: string, depth: number): nodeDebugInfo {
    let out = "";

    if (this.handler !== undefined) {
      out +=
        " (handler: " +
        reconstructRegisteredURL({
          handler: this.handler.handler,
          path: this.path,
          paramNames: this.handler.placeholders,
          params: [],
        }) +
        ")\n";
    } else {
      out += "\n";
    }

    const children = [
      ...this.children,
      this.dynamicChild,
      this.wildcardChild,
    ].filter((child) => child !== null) as Node[];

    let numNodes = 1;
    let sumNodeDepth = depth;
    let maxDepth = depth;
    let numHandlers = this.handler !== undefined ? 1 : 0;
    let sumDepthHandlers = depth * numHandlers;

    for (let i = 0; i < children.length; i++) {
      const child = children[i];

      let prefix: string;
      switch (child.prefixType) {
        case EdgeType.Static:
          prefix = `"${child.prefixToNode}"`;
          break;
        case EdgeType.Dynamic:
          prefix = `:${child.prefixToNode}`;
          break;
        case EdgeType.Wildcard:
          prefix = `*${child.prefixToNode}`;
      }

      let childIndent = indent;
      if (i === children.length - 1) {
        out += indent + `└─ ${prefix}`;
        childIndent += "    ";
      } else {
        out += indent + `├─ ${prefix}`;
        childIndent += "|    ";
      }

      const childDebug = child.debug(childIndent, depth + 1);
      numNodes += childDebug.numNodes;
      sumNodeDepth += childDebug.sumNodeDepth;
      numHandlers += childDebug.numHandlers;
      sumDepthHandlers += childDebug.sumDepthHandlers;
      maxDepth = Math.max(maxDepth, childDebug.maxDepth);
      out += childDebug.str;
    }

    return {
      str: out,
      numNodes,
      sumNodeDepth,
      numHandlers,
      sumDepthHandlers,
      maxDepth: maxDepth,
    };
  }
}

interface nodeDebugInfo {
  str: string;
  numNodes: number;
  sumNodeDepth: number;
  numHandlers: number;
  sumDepthHandlers: number;
  maxDepth: number;
}

function longestCommonPrefix(str1: string, str2: string): string {
  let i = 0;
  while (i < str1.length && i < str2.length) {
    if (str1[i] !== str2[i]) {
      break;
    }
    i++;
  }
  return str1.substring(0, i);
}

/**
 * routeSplit splits a route into parts, where each part is either a static
 * part of the path, a dynamic segment (until the next /), or a wildcard (*).
 */
function routeSplit(str: string): string[] {
  const segmentPrefixChars = "*:";
  const result: string[] = [];
  let buffer = "";
  let captureUntilSlash = false;
  let previousCharWasSlash = true;

  // eslint-disable-next-line @typescript-eslint/prefer-for-of
  for (let i = 0; i < str.length; i++) {
    const char = str[i];

    if (captureUntilSlash) {
      if (char === "/") {
        captureUntilSlash = false;
        previousCharWasSlash = true;

        result.push(buffer);
        buffer = "";
      }
      buffer += char;
      continue;
    }

    if (previousCharWasSlash && segmentPrefixChars.includes(char)) {
      previousCharWasSlash = false;

      if (buffer) {
        result.push(buffer);
      }
      buffer = char;
      captureUntilSlash = true;
    } else {
      previousCharWasSlash = char === "/";
      buffer += char;
    }
  }

  if (buffer) {
    result.push(buffer);
  }

  return result;
}