/**
 * represents an undirected graph
*/
export class Graph {
    /**
     * creates a new  empty graph.
     * */
    constructor( ) {
        this.adjacent = new Map();
        this.vertexAttribute = new Map();
    }

    /**
     * (vertex:integer) => this
     * @param vertex {Number} a vertex
     * @return this graph
     * */
    addVertex(vertex) {
        if (! this.adjacent.has(vertex)) {
            let [isInteger, i] = toInteger(vertex);
            if (isInteger) {
                this.adjacent.set(i, []);
            } else {
                throw new TypeError(`Argument ${vertex} is not a valid vertex`)
            }
        }
        return this;
    }

    /**
     * (u: integer, v: integer) => undefined
     * @param u {Number} a vertex of edge
     * @param v {Number} a vertex of edge
     * */
    addEdge(u, v) {
        this.addVertex(u);
        this.addVertex(v);
        const vNeighbor = this.adjacent.get(v);
        if (!vNeighbor.includes(u) ) {
            vNeighbor.push(u);
        }
        const uNeighbor = this.adjacent.get(u);
        if(!uNeighbor.includes(v)) {
            uNeighbor.push(v);
        }
        return this;
    }

    /**
     * merge a map of attribute to a vertex. Usage example:
     * ```
     * let g = new Graph();
     * g.addVertex(1);
     * g.mergeAttribute(1, {'color': 0});
     * ```
     * @param v {Number} a vertex of graph
     * @param p {object|Map} attributes of the vertex, an empty object is allowed, but
     * undefined, empty array is not allow
     * */
    mergeAttribute(v, p) {
        if (!this.adjacent.has(v)) {
            throw new Error(`Graph does not include vertex ${v}`);
        }
        if (!p) {
            throw new Error(`Bad attribute`)
        }
        let newAttribute = (p instanceof Map) ? p : new Map(Object.entries(p));
        let oldAttribute = this.vertexAttribute.get(v) || new Map();
        this.vertexAttribute.set(v, new Map([...oldAttribute, ...newAttribute]));
        return this;
    }

    getAttribute(vertex) {
        if (this.adjacent.has(vertex)) {
            return this.vertexAttribute.get(vertex);
        } else {
            throw new Error(`Graph does not include vertex ${v}`);
        }
    }

    /**
     * example usage:
     * ```
     * for (let v of g.vertices() ) {
     *     // do something with v
     * }
     * ```
     * @return vertices array of the graph
     * */
    vertices() {
        return this.adjacent.keys();
    }

    forEachVertices(action) {
        for(const v of this.vertices() ) {
            action(v);
        }
    }

    /**
     * @param v {integer} a vertex of graph.
     * @return neighbor array of v
     * */
    adjacentOf(v) {
        if (!this.adjacent.has(v)) {
            throw new Error(`Graph does not include vertex ${v}`);
        }
        return this.adjacent.get(v);
    }

    forEachEdges(action) {
        const visitedEdges = new Map();
        for(const start of this.vertices() ) {
            for(const end of this.adjacentOf(start)) {
                const first = (start > end) ? start : end;
                const second = (start > end) ? end : start;
                if(visitedEdges.has(first)) {
                    const visitedAdjacent = visitedEdges.get(first);
                    if( !visitedAdjacent.has(second) ) {
                        visitedAdjacent.add(second);
                        action(start, end);
                    }
                }else {
                    const adjacent = new Set();
                    visitedEdges.set(first, adjacent);
                    adjacent.add(second);
                    action(start, end);
                }
            }
        }
    }


    toString() {
        let text = "";
        let sortedKeys = [...this.adjacent.keys()].sort();
        let lastKey = sortedKeys.pop();
        let adjacentFn = (key) => `[${this.adjacent.get(key).join(', ')}]`;
        for( let key of sortedKeys) {
            text += `${key} → ${adjacentFn(key)}\n`
        }
        text += `${lastKey} → ${adjacentFn(lastKey)}`;
        return text;
    }
}

function toInteger(value) {
    if (isNaN(value)) {
        return [false, NaN];
    }
    let x = parseFloat(value);
    let i = x | 0;
    return [i === x, i];
}