import * as Colors from "@std/fmt/colors"

type UUID = string

export type VertexType<G> = G extends Graph<infer T, infer V> ? Vertex<T, V> : never
export type EdgeType<G> = G extends Graph<infer T, infer V> ? Edge<T, V> : never
export type PathType<G> = G extends Graph<infer T, infer V> ? Path<T, V> : never
/** Given an edge, this function should return the weight of that edge. */
export type WeightFn<Graph> = (this: Graph, e: EdgeType<Graph>) => number

interface GraphOpts<G> {
    directed: boolean
    weights: WeightFn<G>
}

interface EdgeOpts {
    directed: boolean
    id: UUID
}

/**
 * Represents a graph, consisting of vertices and edges.
 * @author MindfulMinun
 * @since 2022-07-26
 */
export class Graph<vData, eData> {
    /** A map of the vertices in the graph. To add a new vertex, please use the {@link Graph.createVertex} method instead. */
    vertices: Map<UUID, Vertex<vData, eData>>
    /** A map of the edges in the graph. To add a new edge, please use the {@link Graph.createEdge} method instead. */
    edges: Map<UUID, Edge<vData, eData>>
    /**
     * Whether or not edges created in the graph are directed when the value is omitted.
     * Note that edges created with the `directed` option will use that value instead.
     */
    directed: boolean
    /** A function that returns the weight of an edge. */
    weights: WeightFn<typeof this>

    constructor(opts: Partial<GraphOpts<Graph<vData, eData>>> = {}) {
        const options: GraphOpts<Graph<vData, eData>> = {
            directed: false,
            weights: () => 1,
            ...opts
        }
        this.directed = options.directed
        this.weights = options.weights
        this.vertices = new Map()
        this.edges = new Map()
    }

    createVertex(data: vData, id: UUID = crypto.randomUUID()): Vertex<vData, eData> {
        const V = new Vertex(this, id, data)
        this.vertices.set(id, V)
        return V
    }

    deleteVertex(V: Vertex<vData, eData>) {
        // Delete all edges connected to V, then delete V
        for (const E of V.adjacentEdges) E.delete()
        this.vertices.delete(V.id)
    }

    createEdge(u: Vertex<vData, eData>, v: Vertex<vData, eData>, data: eData, opts: Partial<EdgeOpts> = {}): Edge<vData, eData> {
        const options: EdgeOpts = {
            directed: this.directed,
            id: crypto.randomUUID(),
            ...opts
        }
        const E = new Edge(this, options.id, u, v, options.directed, data)
        this.edges.set(options.id, E)
        v.adjacentEdges.add(E)
        u.adjacentEdges.add(E)
        return E
    }

    deleteEdge(E: Edge<vData, eData>) {
        // Remove me from the caches of my connecting nodes, then delete me
        E.u.adjacentEdges.delete(E)
        E.v.adjacentEdges.delete(E)
        this.edges.delete(E.id)
    }


    createPath(start: Vertex<vData, eData>): Path<vData, eData> {
        return new Path<vData, eData>(this, start)
    }

    // FIXME: return type
    toJSON(
        vertexReplacer: (this: Graph<vData, eData>, data: vData) => unknown = data => data,
        edgeReplacer: (this: Graph<vData, eData>, data: eData) => unknown = data => data
    ): unknown {
        return {
            "@graph": Graph.signature,
            v: Array.from(this.vertices.values()).map(v => v.toJSON(vertexReplacer)),
            e: Array.from(this.edges.values()).map(e => e.toJSON(edgeReplacer))
        }
    }

    static fromJSON<vData, eData>(
        json: unknown,
        vertexReviver: (this: Graph<vData, eData>, json: unknown) => vData = data => data as vData,
        edgeReviver: (this: Graph<vData, eData>, json: unknown) => eData = data => data as eData
    ): Graph<vData, eData> {
        const G = new Graph<vData, eData>()

        if (!json || typeof json !== 'object') throw Error("Failed to parse: Unexpected object!")
        const obj = json as Record<string, unknown>
        if (obj['@graph'] !== Graph.signature) throw Error("Failed to parse: The object isn't a graph!")


        if (!Array.isArray(obj.v)) throw Error("Failed to parse: The vertices property isn't an array!")
        if (!Array.isArray(obj.e)) throw Error("Failed to parse: The edges property isn't an array!")

        for (const V of obj.v) {
            if (!Array.isArray(V)) throw Error("Failed to parse: One of the vertices isn't a tuple!")
            const [uuid, data] = V as [UUID, vData]
            if (typeof uuid != 'string') throw Error("Failed to parse: Unexpected UUID!")
            G.createVertex(vertexReviver.call(G, data), uuid)
        }

        for (const E of obj.e) {
            if (!Array.isArray(E)) throw Error("Failed to parse: One of the edges isn't a tuple!")
            const [uuid, u, v, isDirected, data] = E as [UUID, UUID, UUID, boolean, eData]
            if (typeof uuid != 'string') throw Error("Failed to parse: UUID wasn't a string!")
            if (typeof u != 'string') throw Error("Failed to parse: U wasn't a string!")
            if (typeof v != 'string') throw Error("Failed to parse: V wasn't a string!")

            const U = G.vertices.get(u)
            const V = G.vertices.get(v)

            if (!U) throw Error(`Vertex ${U} doesn't exist!`)
            if (!V) throw Error(`Vertex ${V} doesn't exist!`)

            G.createEdge(U, V, edgeReviver.call(G, data), {
                id: uuid,
                directed: isDirected
            })
        }

        return G
    }

    static signature = "Made with love by MindfulMinun <https://benjic.xyz>" as const
}

/**
 * Represents a vertex in a graph.
 * @author MindfulMinun
 * @since 2022-07-26
 */

export class Vertex<vData, eData> {
    /* The graph this vertex belongs to */
    graph: Graph<vData, eData>
    /* The value stored in this vertex, up to you! */
    data: vData
    /* The unique identifier of this vertex */
    id: UUID
    /* The edges connected to this vertex */
    adjacentEdges: Set<Edge<vData, eData>>

    constructor(parentGraph: Graph<vData, eData>, id: UUID, data: vData) {
        this.graph = parentGraph
        this.data = data
        this.id = id
        this.adjacentEdges = new Set()
    }

    /**
     * Remove this vertex from the graph. Edges connected to this vertex will also be removed.
     * Callers should discard this vertex after calling this method.
     */
    delete() { this.graph.deleteVertex(this) }

    // FIXME: return type as tuple
    toJSON(
        replacer: (this: Graph<vData, eData>, data: vData) => unknown = data => data
    ): [unknown, unknown] {
        return [this.id, replacer.call(this.graph, this.data)]
    }

    toString(): string {
        return Colors.cyan(`<${this.id.slice(0, 8)}>: ${this.data}`)
    }

    [Symbol.for("Deno.customInspect")](): string {
        return this.toString()
    }
}

/**
 * Represents an edge in a graph which connects two vertices.
 * @author MindfulMinun
 * @since 2022-07-26
 */
export class Edge<vData, eData> {
    /** The graph this edge belongs to */
    graph: Graph<vData, eData>
    /** The value stored in this edge, up to you! */
    data: eData
    /** A unique identifier for this edge. */
    id: UUID
    /** If directed, the vertex that this edge is coming from. */
    u: Vertex<vData, eData>
    /** If directed, the vertex that this edge is going to */
    v: Vertex<vData, eData>
    /** Whether or not this edge is directed */
    directed: boolean

    constructor(
        parentGraph: Graph<vData, eData>,
        id: UUID,
        u: Vertex<vData, eData>,
        v: Vertex<vData, eData>,
        directed: boolean,
        data: eData
    ) {
        this.graph = parentGraph
        this.data = data
        this.id = id
        this.directed = directed

        if (u.graph !== v.graph || u.graph !== parentGraph)
            throw Error("Both vertices and the new edge must all belong to the same graph.")
        
        this.u = u
        this.v = v
    }

    /** Given one vertex, get the opposite vertex of this edge */
    not(v: typeof this.u | typeof this.v): Vertex<vData, eData> {
        return this.v !== v ? this.v : this.u
    }

    delete() { this.graph.deleteEdge(this) }

    // FIXME: Type me as a tuple!
    toJSON(
        replacer: (this: Graph<vData, eData>, data: eData) => unknown = data => data
    ): [unknown, unknown, unknown, unknown, unknown] {
        return [
            this.id,
            this.u.id,
            this.v.id,
            this.directed,
            replacer.call(this.graph, this.data)
        ]
    }

    toString(): string {
        return Colors.magenta(`<${this.id.slice(0, 8)}>: ${this.u} ${!this.directed ? '<' : ''}--> ${this.v}`)
    }

    [Symbol.for("Deno.customInspect")](): string {
        return this.toString()
    }
}

export class Path<vData, eData> {
    /** The graph this path belongs to */
    graph: Graph<vData, eData>
    /** The vertex this path starts with */
    start: Vertex<vData, eData> | null
    /** The edges belonging to this path */
    edges: Edge<vData, eData>[]
    /** An internal cache of the vertices. */
    #vertices: Vertex<vData, eData>[] | null

    constructor(graph: Graph<vData, eData>, start?: Vertex<vData, eData>) {
        this.graph = graph
        this.edges = []
        this.start = start ?? null
        this.#vertices = null
    }

    addEdge(e: Edge<vData, eData>) {
        if (!this.start) this.start = e.u
        if (e.graph !== this.graph) throw Error("The edges in a path must all belong to the same graph.")
        this.edges.push(e)
        this.#vertices = null
    }

    /** The vertices belonging to this path */
    get vertices(): Iterable<Vertex<vData, eData>> {
        if (this.#vertices) return this.#vertices

        const vertices: Vertex<vData, eData>[] = []
        if (!this.start) return vertices

        let current = this.start
        vertices.push(current)

        for (const e of this.edges) {
            current = e.u !== current ? e.u : e.v
            vertices.push(current)
        }

        this.#vertices = vertices
        return this.#vertices
    }

    copy(): Path<vData, eData> {
        const path = new Path<vData, eData>(this.graph, this.start ?? undefined)
        path.edges = this.edges.slice()
        path.#vertices = this.#vertices?.slice() ?? null
        return path
    }
}