import type { BuildEvents } from "#Source/event/index.ts"
import { EventManager } from "#Source/event/index.ts"
import { generateUuidV4FromUrl } from "#Source/identifier/index.ts"

import type { HashUnion, SearchUnion } from "../uri/index.ts"

import { Route } from "./route.ts"

/**
 * @description Router 内部历史动作的种类。
 */
export const ROUTE_ACTION_TYPE = {
  MOVE: "move",
  TRIM: "trim",
  PUSH: "push",
  REPLACE: "replace",
} as const

/**
 * @description Router 内部历史动作的联合字面量类型。
 */
export type RouteActionType = (typeof ROUTE_ACTION_TYPE)[keyof typeof ROUTE_ACTION_TYPE]

/**
 * @description 在历史链表上移动当前位置时使用的输入项。
 */
export interface RouteMoveOptions {
  step: number
}

/**
 * @description 在历史链表上移动当前位置后返回的结果。
 */
export interface RouteMoveResult {
  fromRouteEntry: RouteEntry
  toRouteEntry: RouteEntry
  direction: "forward" | "backward" | "none"
}

/**
 * @description 截断某个历史节点之后分支时使用的输入项。
 */
export interface RouteTrimOptions {
  routeEntry: RouteEntry
}

/**
 * @description 截断历史分支后返回的结果。
 */
export interface RouteTrimResult {
  fromRouteEntry: RouteEntry
  trimmedRouteEntries: RouteEntry[]
}

/**
 * @description 向历史尾部压入新路由时使用的输入项。
 */
export interface RoutePushOptions {
  route: Route
}

/**
 * @description 向历史尾部压入新路由后返回的结果。
 */
export interface RoutePushResult {
  fromRouteEntry: RouteEntry
  toRouteEntry: RouteEntry
}

/**
 * @description 用新路由替换当前位置时使用的输入项。
 */
export interface RouteReplaceOptions {
  route: Route
}

/**
 * @description 用新路由替换当前位置后返回的结果。
 */
export interface RouteReplaceResult {
  fromRouteEntry: RouteEntry
  toRouteEntry: RouteEntry
}

/**
 * @description 对外可见的路由历史操作类型。
 */
export const ROUTE_TYPE = {
  INITIALIZE: "initialize",
  REFRESH: "refresh",
  REPLACE_TO: "replace-to",
  SWITCH_TO: "switch-to",
  NAVIGATE_TO: "navigate-to",
  NAVIGATE_SEARCH: "navigate-search",
  NAVIGATE_HASH: "navigate-hash",
  REDIRECT_TO: "redirect-to",
  REDIRECT_SEARCH: "redirect-search",
  REDIRECT_HASH: "redirect-hash",
  ROAMING_BY: "roaming-by",
  ROAMING_FORWARD_BY: "roaming-forward-by",
  ROAMING_BACKWARD_BY: "roaming-backward-by",
  ROAMING_TO: "roaming-to",
  ROAMING_FORWARD_TO: "roaming-forward-to",
  ROAMING_BACKWARD_TO: "roaming-backward-to",
  GO_BY: "go-by",
  GO_FORWARD_BY: "go-forward-by",
  GO_BACKWARD_BY: "go-backward-by",
  GO_TO: "go-to",
  GO_FORWARD_TO: "go-forward-to",
  GO_BACKWARD_TO: "go-backward-to",
} as const

/**
 * @description 对外可见的路由历史操作类型联合。
 */
export type RouteType = (typeof ROUTE_TYPE)[keyof typeof ROUTE_TYPE]

/**
 * @description 初始化 Router 时使用的输入项。
 */
export interface RouteInitializeOptions {
  url: string
}

/**
 * @description 刷新当前路由时使用的输入项。
 */
export interface RouteRefreshOptions {}

/**
 * @description 用新地址替换当前位置时使用的输入项。
 */
export interface RouteReplaceToOptions {
  url: string
}

/**
 * @description 切换到历史尾部并替换目标地址时使用的输入项。
 */
export interface RouteSwitchToOptions {
  url: string
}

/**
 * @description 以追加历史的方式导航到新地址时使用的输入项。
 */
export interface RouteNavigateToOptions {
  url: string
}

/**
 * @description 以追加历史的方式导航到新 search 时使用的输入项。
 */
export interface RouteNavigateSearchOptions {
  search: SearchUnion
}

/**
 * @description 以追加历史的方式导航到新 hash 时使用的输入项。
 */
export interface RouteNavigateHashOptions {
  hash: HashUnion
}

/**
 * @description 以替换当前位置的方式重定向到新地址时使用的输入项。
 */
export interface RouteRedirectToOptions {
  url: string
}

/**
 * @description 以替换当前位置的方式重定向到新 search 时使用的输入项。
 */
export interface RouteRedirectSearchOptions {
  search: SearchUnion
}

/**
 * @description 以替换当前位置的方式重定向到新 hash 时使用的输入项。
 */
export interface RouteRedirectHashOptions {
  hash: HashUnion
}

/**
 * @description 在历史链表中按相对步数漫游时使用的输入项。
 */
export interface RouteRoamingByOptions {
  step: number
}

/**
 * @description 在历史链表中向前漫游时使用的输入项。
 */
export interface RouteRoamingForwardByOptions {
  step: number
}

/**
 * @description 在历史链表中向后漫游时使用的输入项。
 */
export interface RouteRoamingBackwardByOptions {
  step: number
}

/**
 * @description 在全部历史范围内按条件漫游时使用的输入项。
 */
export interface RouteRoamingToOptions {
  predicate: (routeEntry: RouteEntry) => boolean
}

/**
 * @description 在当前位置之后按条件漫游时使用的输入项。
 */
export interface RouteRoamingForwardToOptions {
  predicate: (routeEntry: RouteEntry) => boolean
}

/**
 * @description 在当前位置之前按条件漫游时使用的输入项。
 */
export interface RouteRoamingBackwardToOptions {
  predicate: (routeEntry: RouteEntry) => boolean
}

/**
 * @description 在历史链表中按相对步数移动并截断后续分支时使用的输入项。
 */
export interface RouteGoByOptions {
  step: number
}

/**
 * @description 在历史链表中向前移动并截断后续分支时使用的输入项。
 */
export interface RouteGoForwardByOptions {
  step: number
}

/**
 * @description 在历史链表中向后移动并截断后续分支时使用的输入项。
 */
export interface RouteGoBackwardByOptions {
  step: number
}

/**
 * @description 在全部历史范围内按条件移动并截断后续分支时使用的输入项。
 */
export interface RouteGoToOptions {
  predicate: (routeEntry: RouteEntry) => boolean
}

/**
 * @description 在当前位置之后按条件移动并截断后续分支时使用的输入项。
 */
export interface RouteGoForwardToOptions {
  predicate: (routeEntry: RouteEntry) => boolean
}

/**
 * @description 在当前位置之前按条件移动并截断后续分支时使用的输入项。
 */
export interface RouteGoBackwardToOptions {
  predicate: (routeEntry: RouteEntry) => boolean
}

/**
 * @description Router 在一次历史记录中执行的底层动作。
 */
export type RouteHistoryAction =
  | { type: "move"; options: RouteMoveOptions; result: RouteMoveResult }
  | { type: "trim"; options: RouteTrimOptions; result: RouteTrimResult }
  | { type: "push"; options: RoutePushOptions; result: RoutePushResult }
  | { type: "replace"; options: RouteReplaceOptions; result: RouteReplaceResult }

/**
 * @description Router 对外暴露的历史记录条目。
 */
export type RouteHistoryEntry =
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "initialize"
      options: RouteInitializeOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "refresh"
      options: RouteRefreshOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "replace-to"
      options: RouteReplaceToOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "switch-to"
      options: RouteSwitchToOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "navigate-to"
      options: RouteNavigateToOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "navigate-search"
      options: RouteNavigateSearchOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "navigate-hash"
      options: RouteNavigateHashOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "redirect-to"
      options: RouteRedirectToOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "redirect-search"
      options: RouteRedirectSearchOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "redirect-hash"
      options: RouteRedirectHashOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "roaming-by"
      options: RouteRoamingByOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "roaming-forward-by"
      options: RouteRoamingForwardByOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "roaming-backward-by"
      options: RouteRoamingBackwardByOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "roaming-to"
      options: RouteRoamingToOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "roaming-forward-to"
      options: RouteRoamingForwardToOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "roaming-backward-to"
      options: RouteRoamingBackwardToOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "go-by"
      options: RouteGoByOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "go-forward-by"
      options: RouteGoForwardByOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "go-backward-by"
      options: RouteGoBackwardByOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "go-to"
      options: RouteGoToOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "go-forward-to"
      options: RouteGoForwardToOptions
      actions: RouteHistoryAction[]
    }
  | {
      id: string
      from: RouteEntry
      to: RouteEntry
      type: "go-backward-to"
      options: RouteGoBackwardToOptions
      actions: RouteHistoryAction[]
    }

/**
 * @description Router 历史链表中的节点。
 */
export interface RouteEntry {
  route: Route
  prevEntry?: RouteEntry | undefined
  nextEntry?: RouteEntry | undefined
  history: RouteHistoryEntry[]
  index: number
}

/**
 * @description 1. `history.options` 中涉及 `predicate` 的地方替换为 `(): boolean => false`。
 * 2. 所有涉及 `Route` 的地方使用 `Route.clone()` 方法进行克隆。
 * 3. `RouteEntry.prevEntry` 和 `RouteEntry.nextEntry` 递归克隆。
 * 4. `RouteEntry.history` 中的每个 `RouteHistoryEntry` 都进行克隆。
 * 5. 克隆前后保持引用关系不变。
 */
const internalRouteMap = new Map<Route, Route>()
const internalRouteEntryMap = new Map<RouteEntry, RouteEntry>()
const internalRouteHistoryEntryMap = new Map<RouteHistoryEntry, RouteHistoryEntry>()
const internalCloneReset = (): void => {
  internalRouteMap.clear()
  internalRouteEntryMap.clear()
  internalRouteHistoryEntryMap.clear()
}
const internalCloneRoute = (sourceRoute: Route): Route => {
  const cachedRoute = internalRouteMap.get(sourceRoute)
  if (cachedRoute !== undefined) {
    return cachedRoute
  }

  const clonedRoute = sourceRoute.clone()
  internalRouteMap.set(sourceRoute, clonedRoute)
  return clonedRoute
}
const internalCloneRouteEntry = (sourceRouteEntry: RouteEntry): RouteEntry => {
  const cachedRouteEntry = internalRouteEntryMap.get(sourceRouteEntry)
  if (cachedRouteEntry !== undefined) {
    return cachedRouteEntry
  }

  const clonedRouteEntry: RouteEntry = {
    route: internalCloneRoute(sourceRouteEntry.route),
    prevEntry: undefined,
    nextEntry: undefined,
    history: [],
    index: sourceRouteEntry.index,
  }
  internalRouteEntryMap.set(sourceRouteEntry, clonedRouteEntry)

  clonedRouteEntry.prevEntry =
    sourceRouteEntry.prevEntry === undefined
      ? undefined
      : internalCloneRouteEntry(sourceRouteEntry.prevEntry)
  clonedRouteEntry.nextEntry =
    sourceRouteEntry.nextEntry === undefined
      ? undefined
      : internalCloneRouteEntry(sourceRouteEntry.nextEntry)
  clonedRouteEntry.history = sourceRouteEntry.history.map((historyEntry) => {
    return internalCloneRouteHistoryEntry(historyEntry)
  })

  return clonedRouteEntry
}
const internalCloneRouteHistoryEntry = (historyEntry: RouteHistoryEntry): RouteHistoryEntry => {
  const cloneHistoryOptions = (
    sourceHistoryEntry: RouteHistoryEntry,
  ): RouteHistoryEntry["options"] => {
    switch (sourceHistoryEntry.type) {
      case ROUTE_TYPE.INITIALIZE: {
        return {
          url: sourceHistoryEntry.options.url,
        }
      }
      case ROUTE_TYPE.REFRESH: {
        return {}
      }
      case ROUTE_TYPE.SWITCH_TO:
      case ROUTE_TYPE.REPLACE_TO:
      case ROUTE_TYPE.NAVIGATE_TO:
      case ROUTE_TYPE.REDIRECT_TO: {
        return {
          url: sourceHistoryEntry.options.url,
        }
      }
      case ROUTE_TYPE.NAVIGATE_SEARCH:
      case ROUTE_TYPE.REDIRECT_SEARCH: {
        return {
          search: structuredClone(sourceHistoryEntry.options.search),
        }
      }
      case ROUTE_TYPE.NAVIGATE_HASH:
      case ROUTE_TYPE.REDIRECT_HASH: {
        return {
          hash: structuredClone(sourceHistoryEntry.options.hash),
        }
      }
      case ROUTE_TYPE.ROAMING_BY:
      case ROUTE_TYPE.ROAMING_FORWARD_BY:
      case ROUTE_TYPE.ROAMING_BACKWARD_BY:
      case ROUTE_TYPE.GO_BY:
      case ROUTE_TYPE.GO_FORWARD_BY:
      case ROUTE_TYPE.GO_BACKWARD_BY: {
        return {
          step: sourceHistoryEntry.options.step,
        }
      }
      case ROUTE_TYPE.ROAMING_TO:
      case ROUTE_TYPE.ROAMING_FORWARD_TO:
      case ROUTE_TYPE.ROAMING_BACKWARD_TO:
      case ROUTE_TYPE.GO_TO:
      case ROUTE_TYPE.GO_FORWARD_TO:
      case ROUTE_TYPE.GO_BACKWARD_TO: {
        return {
          predicate: (_routeEntry: RouteEntry): boolean => false,
        }
      }
      default: {
        throw new Error(`Unsupported route history entry type`)
      }
    }
  }

  const cloneRouteHistoryAction = (sourceAction: RouteHistoryAction): RouteHistoryAction => {
    switch (sourceAction.type) {
      case ROUTE_ACTION_TYPE.MOVE: {
        return {
          type: ROUTE_ACTION_TYPE.MOVE,
          options: { step: sourceAction.options.step },
          result: {
            fromRouteEntry: internalCloneRouteEntry(sourceAction.result.fromRouteEntry),
            toRouteEntry: internalCloneRouteEntry(sourceAction.result.toRouteEntry),
            direction: sourceAction.result.direction,
          },
        }
      }
      case ROUTE_ACTION_TYPE.TRIM: {
        return {
          type: ROUTE_ACTION_TYPE.TRIM,
          options: { routeEntry: internalCloneRouteEntry(sourceAction.options.routeEntry) },
          result: {
            fromRouteEntry: internalCloneRouteEntry(sourceAction.result.fromRouteEntry),
            trimmedRouteEntries: sourceAction.result.trimmedRouteEntries.map((entry) => {
              return internalCloneRouteEntry(entry)
            }),
          },
        }
      }
      case ROUTE_ACTION_TYPE.PUSH: {
        return {
          type: ROUTE_ACTION_TYPE.PUSH,
          options: { route: internalCloneRoute(sourceAction.options.route) },
          result: {
            fromRouteEntry: internalCloneRouteEntry(sourceAction.result.fromRouteEntry),
            toRouteEntry: internalCloneRouteEntry(sourceAction.result.toRouteEntry),
          },
        }
      }
      case ROUTE_ACTION_TYPE.REPLACE: {
        return {
          type: ROUTE_ACTION_TYPE.REPLACE,
          options: { route: internalCloneRoute(sourceAction.options.route) },
          result: {
            fromRouteEntry: internalCloneRouteEntry(sourceAction.result.fromRouteEntry),
            toRouteEntry: internalCloneRouteEntry(sourceAction.result.toRouteEntry),
          },
        }
      }
      default: {
        throw new Error(`Unsupported route history action type`)
      }
    }
  }

  const cloneRouteHistoryEntry = (sourceHistoryEntry: RouteHistoryEntry): RouteHistoryEntry => {
    const cachedRouteHistoryEntry = internalRouteHistoryEntryMap.get(sourceHistoryEntry)
    if (cachedRouteHistoryEntry !== undefined) {
      return cachedRouteHistoryEntry
    }

    const clonedRouteHistoryEntry = {
      id: sourceHistoryEntry.id,
      from: internalCloneRouteEntry(sourceHistoryEntry.from),
      to: internalCloneRouteEntry(sourceHistoryEntry.to),
      type: sourceHistoryEntry.type,
      options: cloneHistoryOptions(sourceHistoryEntry),
      actions: [],
    } as RouteHistoryEntry
    internalRouteHistoryEntryMap.set(sourceHistoryEntry, clonedRouteHistoryEntry)

    clonedRouteHistoryEntry.actions = sourceHistoryEntry.actions.map((action) => {
      return cloneRouteHistoryAction(action)
    })

    return clonedRouteHistoryEntry
  }

  return cloneRouteHistoryEntry(historyEntry)
}

/**
 * @description Router 对外发出的事件集合。
 */
export type RouterEvents = BuildEvents<{
  history: (routeHistoryEntry: RouteHistoryEntry) => void
}>

/**
 * @description 创建 Router 时使用的输入项。
 */
export interface RouterOptions {
  url: string
}

/**
 * @description 路由历史管理器。
 *
 * Router 维护一条可漫游、可裁剪、可替换的路由历史链表，并通过 history 事件向外暴露每次动作对应的历史记录。
 */
export class Router {
  protected options: RouterOptions
  protected history: RouteHistoryEntry[]
  protected headRouteEntry!: RouteEntry
  protected tailRouteEntry!: RouteEntry
  protected routeEntry!: RouteEntry

  eventManager: EventManager<RouterEvents>

  constructor(options: RouterOptions) {
    this.options = options
    this.history = []
    this.eventManager = new EventManager<RouterEvents>()
    this.initialize({ url: options.url })
  }

  protected initialize(options: RouteInitializeOptions): void {
    const { url } = options

    const newRoute = new Route({ partialUrl: url })
    const initialRouteEntry: RouteEntry = {
      route: newRoute,
      prevEntry: undefined,
      nextEntry: undefined,
      history: [],
      index: -1,
    }
    this.headRouteEntry = initialRouteEntry
    this.tailRouteEntry = initialRouteEntry
    this.routeEntry = initialRouteEntry

    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: initialRouteEntry,
      to: initialRouteEntry,
      type: ROUTE_TYPE.INITIALIZE,
      options,
      actions: [],
    }
    this.pushHistory(historyEntry)
  }

  /**
   * @description 返回当前最新的历史记录快照。
   */
  getCurrentRouteHistoryEntry(): RouteHistoryEntry {
    const currentRouteHistoryEntry = this.history.at(-1)
    if (currentRouteHistoryEntry === undefined) {
      throw new Error(`No current route history entry`)
    }
    internalCloneReset()
    const clonedRouteHistoryEntry = internalCloneRouteHistoryEntry(currentRouteHistoryEntry)
    return clonedRouteHistoryEntry
  }

  /**
   * @description 返回当前最新历史记录的标识。
   */
  getCurrentRouteHistoryEntryId(): string {
    const currentRouteHistoryEntry = this.history.at(-1)
    if (currentRouteHistoryEntry === undefined) {
      throw new Error(`No current route history entry`)
    }
    const currentRouteHistoryEntryId = currentRouteHistoryEntry.id
    return currentRouteHistoryEntryId
  }

  protected pushHistory(routeHistoryEntry: RouteHistoryEntry): void {
    this.history.push(routeHistoryEntry)
    internalCloneReset()
    const clonedRouteHistoryEntry = internalCloneRouteHistoryEntry(routeHistoryEntry)
    this.eventManager.emit("history", clonedRouteHistoryEntry)
  }

  /**
   * @description 判断当前位置是否处于历史尾部之前。
   */
  isRoaming(): boolean {
    return this.routeEntry !== this.tailRouteEntry
  }

  /**
   * @description 返回当前位置最多还能向前漫游多少步。
   */
  getMaxRoamingForwardSteps(): number {
    return this.tailRouteEntry.index - this.routeEntry.index
  }

  /**
   * @description 返回当前位置最多还能向后漫游多少步。
   */
  getMaxRoamingBackwardSteps(): number {
    return this.routeEntry.index - this.headRouteEntry.index
  }

  /**
   * @description 判断当前位置是否还能继续向前漫游。
   */
  canRoamingForward(): boolean {
    return this.getMaxRoamingForwardSteps() > 0
  }

  /**
   * @description 判断当前位置是否还能继续向后漫游。
   */
  canRoamingBackward(): boolean {
    return this.getMaxRoamingBackwardSteps() > 0
  }

  protected move(options: RouteMoveOptions): RouteMoveResult {
    const { step } = options

    const fromRouteEntry = this.routeEntry
    let toRouteEntry = this.routeEntry
    const direction = step > 0 ? "forward" : step < 0 ? "backward" : "none"

    if (step > 0) {
      for (let currentStep = 0; currentStep < step; currentStep = currentStep + 1) {
        if (toRouteEntry.nextEntry === undefined) {
          break
        }
        toRouteEntry = toRouteEntry.nextEntry
      }
    } else if (step < 0) {
      for (let currentStep = 0; currentStep > step; currentStep = currentStep - 1) {
        if (toRouteEntry.prevEntry === undefined) {
          break
        }
        toRouteEntry = toRouteEntry.prevEntry
      }
    }

    this.routeEntry = toRouteEntry

    return { fromRouteEntry, toRouteEntry, direction }
  }

  protected trim(options: RouteTrimOptions): RouteTrimResult {
    const { routeEntry } = options

    const fromRouteEntry = routeEntry
    const trimmedRouteEntries: RouteEntry[] = []

    let nextEntry = fromRouteEntry.nextEntry
    while (nextEntry !== undefined) {
      trimmedRouteEntries.push(nextEntry)
      nextEntry = nextEntry.nextEntry
    }

    fromRouteEntry.nextEntry = undefined
    this.tailRouteEntry = fromRouteEntry

    return { fromRouteEntry, trimmedRouteEntries }
  }

  protected push(options: RoutePushOptions): RoutePushResult {
    const { route } = options

    const fromRouteEntry = this.routeEntry

    const toRouteEntry: RouteEntry = {
      route,
      prevEntry: this.routeEntry,
      nextEntry: undefined,
      history: [],
      index: this.routeEntry.index + 1,
    }

    this.routeEntry.nextEntry = toRouteEntry

    this.tailRouteEntry = toRouteEntry
    this.routeEntry = toRouteEntry

    return { fromRouteEntry, toRouteEntry }
  }

  protected replace(options: RouteReplaceOptions): RouteReplaceResult {
    const { route } = options

    const fromRouteEntry = this.routeEntry

    const prevEntry = this.routeEntry.prevEntry
    const nextEntry = this.routeEntry.nextEntry
    const toRouteEntry: RouteEntry = {
      route,
      prevEntry,
      nextEntry,
      history: [],
      index: fromRouteEntry.index,
    }

    if (prevEntry !== undefined) {
      prevEntry.nextEntry = toRouteEntry
    }
    if (nextEntry !== undefined) {
      nextEntry.prevEntry = toRouteEntry
    }

    if (prevEntry === undefined) {
      this.headRouteEntry = toRouteEntry
    }
    if (nextEntry === undefined) {
      this.tailRouteEntry = toRouteEntry
    }
    this.routeEntry = toRouteEntry

    return { fromRouteEntry, toRouteEntry }
  }

  protected internalFind(predicate: (routeEntry: RouteEntry) => boolean): RouteEntry | undefined {
    let currentEntry: RouteEntry | undefined = this.headRouteEntry
    while (currentEntry !== undefined) {
      if (predicate(currentEntry)) {
        return currentEntry
      }
      currentEntry = currentEntry.nextEntry
    }
    return undefined
  }

  protected internalFindForward(
    predicate: (routeEntry: RouteEntry) => boolean,
  ): RouteEntry | undefined {
    let currentEntry = this.routeEntry.nextEntry
    while (currentEntry !== undefined) {
      if (predicate(currentEntry)) {
        return currentEntry
      }
      currentEntry = currentEntry.nextEntry
    }
    return undefined
  }

  protected internalFindBackward(
    predicate: (routeEntry: RouteEntry) => boolean,
  ): RouteEntry | undefined {
    let currentEntry = this.routeEntry.prevEntry
    while (currentEntry !== undefined) {
      if (predicate(currentEntry)) {
        return currentEntry
      }
      currentEntry = currentEntry.prevEntry
    }
    return undefined
  }

  /**
   * @description 在当前位置生成一条 refresh 历史记录。
   */
  refresh(options: RouteRefreshOptions): void {
    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step: 0 }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.REFRESH,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 用新地址替换当前位置，并记录 replace-to 历史。
   */
  replaceTo(options: RouteReplaceToOptions): void {
    const { url } = options

    const newRoute = new Route({ partialUrl: url })

    const actions: RouteHistoryAction[] = []

    const replaceOptions: RouteReplaceOptions = { route: newRoute }
    const replaceResult = this.replace(replaceOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.REPLACE,
      options: replaceOptions,
      result: replaceResult,
    })

    const fromRouteEntry = replaceResult.fromRouteEntry
    const toRouteEntry = replaceResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.REPLACE_TO,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 切换到历史尾部并用新地址替换该位置。
   */
  switchTo(options: RouteSwitchToOptions): void {
    const { url } = options

    const newRoute = new Route({ partialUrl: url })
    const targetStep = this.getMaxRoamingForwardSteps()

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step: targetStep }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const trimOptions: RouteTrimOptions = { routeEntry: moveResult.toRouteEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const replaceOptions: RouteReplaceOptions = { route: newRoute }
    const replaceResult = this.replace(replaceOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.REPLACE,
      options: replaceOptions,
      result: replaceResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = replaceResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.SWITCH_TO,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 裁剪当前位置之后的分支，并把新地址压入历史尾部。
   */
  navigateTo(options: RouteNavigateToOptions): void {
    const { url } = options

    const newRoute = new Route({ partialUrl: url })

    const actions: RouteHistoryAction[] = []

    const trimOptions: RouteTrimOptions = { routeEntry: this.routeEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const pushOptions: RoutePushOptions = { route: newRoute }
    const pushResult = this.push(pushOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.PUSH,
      options: pushOptions,
      result: pushResult,
    })

    const fromRouteEntry = trimResult.fromRouteEntry
    const toRouteEntry = pushResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.NAVIGATE_TO,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 基于当前 route 更新 search，并以追加历史的方式导航。
   */
  navigateSearch(options: RouteNavigateSearchOptions): void {
    const { search } = options

    const newRoute = this.routeEntry.route.clone().search({ search })

    const actions: RouteHistoryAction[] = []

    const trimOptions: RouteTrimOptions = { routeEntry: this.routeEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const pushOptions: RoutePushOptions = { route: newRoute }
    const pushResult = this.push(pushOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.PUSH,
      options: pushOptions,
      result: pushResult,
    })

    const fromRouteEntry = trimResult.fromRouteEntry
    const toRouteEntry = pushResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.NAVIGATE_SEARCH,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 基于当前 route 更新 hash，并以追加历史的方式导航。
   */
  navigateHash(options: RouteNavigateHashOptions): void {
    const { hash } = options

    const newRoute = this.routeEntry.route.clone().hash({ hash })

    const actions: RouteHistoryAction[] = []

    const trimOptions: RouteTrimOptions = { routeEntry: this.routeEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const pushOptions: RoutePushOptions = { route: newRoute }
    const pushResult = this.push(pushOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.PUSH,
      options: pushOptions,
      result: pushResult,
    })

    const fromRouteEntry = trimResult.fromRouteEntry
    const toRouteEntry = pushResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.NAVIGATE_HASH,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 裁剪当前位置之后的分支，并直接替换当前位置为新地址。
   */
  redirectTo(options: RouteRedirectToOptions): void {
    const { url } = options

    const newRoute = new Route({ partialUrl: url })

    const actions: RouteHistoryAction[] = []

    const trimOptions: RouteTrimOptions = { routeEntry: this.routeEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const replaceOptions: RouteReplaceOptions = { route: newRoute }
    const replaceResult = this.replace(replaceOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.REPLACE,
      options: replaceOptions,
      result: replaceResult,
    })

    const fromRouteEntry = trimResult.fromRouteEntry
    const toRouteEntry = replaceResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.REDIRECT_TO,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 基于当前 route 更新 search，并直接替换当前位置。
   */
  redirectSearch(options: RouteRedirectSearchOptions): void {
    const { search } = options

    const newRoute = this.routeEntry.route.clone().search({ search })

    const actions: RouteHistoryAction[] = []

    const trimOptions: RouteTrimOptions = { routeEntry: this.routeEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const replaceOptions: RouteReplaceOptions = { route: newRoute }
    const replaceResult = this.replace(replaceOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.REPLACE,
      options: replaceOptions,
      result: replaceResult,
    })

    const fromRouteEntry = trimResult.fromRouteEntry
    const toRouteEntry = replaceResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.REDIRECT_SEARCH,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 基于当前 route 更新 hash，并直接替换当前位置。
   */
  redirectHash(options: RouteRedirectHashOptions): void {
    const { hash } = options

    const newRoute = this.routeEntry.route.clone().hash({ hash })

    const actions: RouteHistoryAction[] = []

    const trimOptions: RouteTrimOptions = { routeEntry: this.routeEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const replaceOptions: RouteReplaceOptions = { route: newRoute }
    const replaceResult = this.replace(replaceOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.REPLACE,
      options: replaceOptions,
      result: replaceResult,
    })

    const fromRouteEntry = trimResult.fromRouteEntry
    const toRouteEntry = replaceResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.REDIRECT_HASH,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 按相对步数在历史链表中漫游，但不裁剪分支。
   */
  roamingBy(options: RouteRoamingByOptions): void {
    const { step } = options

    if (Number.isInteger(step) === false) {
      throw new TypeError("Step must be an integer")
    }

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.ROAMING_BY,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 按非负步数向前漫游，但不裁剪分支。
   */
  roamingForwardBy(options: RouteRoamingForwardByOptions): void {
    const { step } = options

    if (Number.isInteger(step) === false) {
      throw new TypeError("Step must be an integer")
    }
    if (step < 0) {
      throw new RangeError("Step must be a non-negative integer")
    }

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.ROAMING_FORWARD_BY,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 按非负步数向后漫游，但不裁剪分支。
   */
  roamingBackwardBy(options: RouteRoamingBackwardByOptions): void {
    const { step } = options

    if (Number.isInteger(step) === false) {
      throw new TypeError("Step must be an integer")
    }
    if (step < 0) {
      throw new RangeError("Step must be a non-negative integer")
    }

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step: -step }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.ROAMING_BACKWARD_BY,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 在整条历史链表中查找首个匹配项并漫游到该位置。
   */
  roamingTo(options: RouteRoamingToOptions): void {
    const { predicate } = options

    const targetRouteEntry = this.internalFind(predicate)
    let targetStep: number
    if (targetRouteEntry === undefined) {
      targetStep = 0
    } else {
      targetStep = targetRouteEntry.index - this.routeEntry.index
    }

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step: targetStep }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.ROAMING_TO,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 在当前位置之后查找首个匹配项并漫游到该位置。
   */
  roamingForwardTo(options: RouteRoamingForwardToOptions): void {
    const { predicate } = options

    const targetRouteEntry = this.internalFindForward(predicate)
    let targetStep: number
    if (targetRouteEntry === undefined) {
      targetStep = 0
    } else {
      targetStep = targetRouteEntry.index - this.routeEntry.index
    }

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step: targetStep }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.ROAMING_FORWARD_TO,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 在当前位置之前查找首个匹配项并漫游到该位置。
   */
  roamingBackwardTo(options: RouteRoamingBackwardToOptions): void {
    const { predicate } = options

    const targetRouteEntry = this.internalFindBackward(predicate)
    let targetStep: number
    if (targetRouteEntry === undefined) {
      targetStep = 0
    } else {
      targetStep = targetRouteEntry.index - this.routeEntry.index
    }

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step: targetStep }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.ROAMING_BACKWARD_TO,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 按相对步数在历史链表中移动，并裁剪目标位置之后的分支。
   */
  goBy(options: RouteGoByOptions): void {
    const { step } = options

    if (Number.isInteger(step) === false) {
      throw new TypeError("Step must be an integer")
    }

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const trimOptions: RouteTrimOptions = { routeEntry: moveResult.toRouteEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.GO_BY,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 按非负步数向前移动，并裁剪目标位置之后的分支。
   */
  goForwardBy(options: RouteGoForwardByOptions): void {
    const { step } = options

    if (Number.isInteger(step) === false) {
      throw new TypeError("Step must be an integer")
    }
    if (step < 0) {
      throw new RangeError("Step must be a non-negative integer")
    }

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const trimOptions: RouteTrimOptions = { routeEntry: moveResult.toRouteEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.GO_FORWARD_BY,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 按非负步数向后移动，并裁剪目标位置之后的分支。
   */
  goBackwardBy(options: RouteGoBackwardByOptions): void {
    const { step } = options

    if (Number.isInteger(step) === false) {
      throw new TypeError("Step must be an integer")
    }
    if (step < 0) {
      throw new RangeError("Step must be a non-negative integer")
    }

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step: -step }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const trimOptions: RouteTrimOptions = { routeEntry: moveResult.toRouteEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.GO_BACKWARD_BY,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 在整条历史链表中查找首个匹配项并移动到该位置，同时裁剪后续分支。
   */
  goTo(options: RouteGoToOptions): void {
    const { predicate } = options

    const targetRouteEntry = this.internalFind(predicate)
    let targetStep: number
    if (targetRouteEntry === undefined) {
      targetStep = 0
    } else {
      targetStep = targetRouteEntry.index - this.routeEntry.index
    }

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step: targetStep }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const trimOptions: RouteTrimOptions = { routeEntry: moveResult.toRouteEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.GO_TO,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 在当前位置之后查找首个匹配项并移动到该位置，同时裁剪后续分支。
   */
  goForwardTo(options: RouteGoForwardToOptions): void {
    const { predicate } = options

    const targetRouteEntry = this.internalFindForward(predicate)
    let targetStep: number
    if (targetRouteEntry === undefined) {
      targetStep = 0
    } else {
      targetStep = targetRouteEntry.index - this.routeEntry.index
    }

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step: targetStep }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const trimOptions: RouteTrimOptions = { routeEntry: moveResult.toRouteEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.GO_FORWARD_TO,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 在当前位置之前查找首个匹配项并移动到该位置，同时裁剪后续分支。
   */
  goBackwardTo(options: RouteGoBackwardToOptions): void {
    const { predicate } = options

    const targetRouteEntry = this.internalFindBackward(predicate)
    let targetStep: number
    if (targetRouteEntry === undefined) {
      targetStep = 0
    } else {
      targetStep = targetRouteEntry.index - this.routeEntry.index
    }

    const actions: RouteHistoryAction[] = []

    const moveOptions: RouteMoveOptions = { step: targetStep }
    const moveResult = this.move(moveOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.MOVE,
      options: moveOptions,
      result: moveResult,
    })

    const trimOptions: RouteTrimOptions = { routeEntry: moveResult.toRouteEntry }
    const trimResult = this.trim(trimOptions)
    actions.push({
      type: ROUTE_ACTION_TYPE.TRIM,
      options: trimOptions,
      result: trimResult,
    })

    const fromRouteEntry = moveResult.fromRouteEntry
    const toRouteEntry = moveResult.toRouteEntry
    const historyEntry: RouteHistoryEntry = {
      id: generateUuidV4FromUrl(),
      from: fromRouteEntry,
      to: toRouteEntry,
      type: ROUTE_TYPE.GO_BACKWARD_TO,
      options,
      actions,
    }
    toRouteEntry.history.push(historyEntry)
    this.pushHistory(historyEntry)
  }

  /**
   * @description 优先向后漫游指定步数；若无法向后漫游，则重定向到指定地址。
   */
  roamingBackwardByOrRedirectTo(options: { step: number; url: string }): void {
    const { step, url } = options

    const canRoamingBackward = this.canRoamingBackward()
    if (canRoamingBackward === true) {
      return this.roamingBackwardBy({ step })
    } else {
      return this.redirectTo({ url })
    }
  }

  /**
   * @description 优先向后移动并裁剪历史；若无法向后移动，则重定向到指定地址。
   */
  goBackwardByOrRedirectTo(options: { step: number; url: string }): void {
    const { step, url } = options

    const canRoamingBackward = this.canRoamingBackward()
    if (canRoamingBackward === true) {
      return this.goBackwardBy({ step })
    } else {
      return this.redirectTo({ url })
    }
  }
}

/**
 * @description 创建一个 Router 实例。
 */
export const createRouter = (options: RouterOptions): Router => {
  return new Router(options)
}