"""
    Graph
A generic directed graph capable of storing parallel arcs and its attributes.
"""
mutable struct Graph
    nn::Integer
    na::Integer
    fadj::Dictionary
    badj::Dictionary
end

# Accessors
nn(g::Graph) = g.nn
na(g::Graph) = g.na
fadj(g::Graph) = g.fadj
badj(g::Graph) = g.badj

# convenience
function ==(g::Graph, h::Graph)
    return g.fadj == h.fadj && g.badj == h.badj && g.nn == h.nn && g.na == h.na
end

function empty!(g::Graph)
    g.nn = 0; g.na = 0
    empty!(g.fadj); empty!(g.badj)
    return g
end

"""
    Graph(n)
Constructs a graph with `n` number of nodes.
"""
function Graph(n::Integer=0)
    fadj = dictionary(Pair{Any,Dictionary}(i, Dictionary()) for i in 1:n)
    badj = dictionary(Pair{Any,Dictionary}(i, Dictionary()) for i in 1:n)
    return Graph(n, 0, fadj, badj)
end

"""
    Graph(abunch)
Constructs a graph from a bunch of arcs `abunch` defined by tuples.
"""
function Graph(abunch::Vector)
    G = Graph(); add_arcs_from!(G, abunch)
    return Graph(G.nn, G.na, G.fadj, G.badj)
end

"""
    add_arc!(g,u,v,key)
Add an arc (u,v,key) to graph g. The default for key is nothing.
Node existence will be first checked then the keys.
"""
function add_arc!(g::Graph, u, v, key=nothing)
    if !(u in keys(g.fadj))
        insert!(g.fadj, u, Dictionary())
        insert!(g.badj, u, Dictionary())
        g.nn += 1 # add node
    end
    if !(v in keys(g.fadj))
        insert!(g.fadj, v, Dictionary())
        insert!(g.badj, v, Dictionary())
        g.nn += 1 # add node
    end
    if isnothing(key)
        key = new_arc_key(g, u, v)
    end
    if v in keys(g.fadj[u])
        innerdict = g.fadj[u][v]
        attribdict = get(innerdict, key, Dictionary())
        if !(key in keys(innerdict))
            g.na += 1 # add arc
        end
        set!(innerdict, key, attribdict)
    else
        attribdict = Dictionary()
        innerdict = Dictionary()
        set!(innerdict, key, attribdict)
        set!(g.fadj[u], v, innerdict)
        set!(g.badj[v], u, innerdict)
        g.na += 1 # add arc
    end
    return key
end

"""
    new_arc_key(g,u,v)
New key generator for arc (u,v). The key will be the lowest integer not used.
The function is internally used for adding arcs.
"""
function new_arc_key(g::Graph, u, v)
    keydict = try
        g.fadj[u][v] # no arc yet
    catch KeyError
        return 1 # lowest key is 1
    end
    key = length(keydict)
    while key in keys(keydict)
        key += 1
    end # find lowest integer not used
    return key
end

"""
    rem_arc!(g, u, v, key)
remove an arc u,v,key from the graph. u and v are nodes.
key is used to distinguish multiple arcs between pair of nodes.
"""
function rem_arc!(g::Graph, u, v, key=nothing)
    d = try
        g.fadj[u][v]
    catch KeyError
        return false # no key uv on graph
    end
    if isnothing(key)
        unset!(d, Dictionaries.lastindex(d)) # pop!
    else
        if haskey(d, key)
            delete!(d, key) # remove the item key
        else # doesn't have key
            return false
        end
    end
    if length(d) == 0
        delete!(g.fadj[u], v)
        delete!(g.badj[v], u)
    end
    g.na -= 1
    return true
end

"""
    add_arcs_from!(g, abunch)
add arcs from an iterable input. abunch is the container of the arc.
each arc can be one of 2-tuples (u,v) or 3-tuples (u,v,k).
adding an already existing arc will update its list of keys. 
all non-compliant arc will be silently not added.
"""
function add_arcs_from!(g::Graph, abunch::Vector)
    keylist = []
    for a in abunch
        la = length(a)
        if la == 2 # 2-tuple
            u, v = a; key = nothing
        elseif la == 3 # 3-tuple
            u, v, key = a
        end
        res = add_arc!(g, u, v, key)
        push!(keylist, res)
    end
    return keylist
end

"""
    rem_arcs_from!(g, abunch)
remove several arcs in abunch from g. the arcs in abunch can be one of:
    - 2-tuples (u,v)
    - 3-tuples (u,v,k)
nonexisting arcs in abunch will silently not be removed.
"""
function rem_arcs_from!(g::Graph, abunch::Vector)
    removed = 0
    for a in abunch
        if length(a) >= 2
            remove = try
                rem_arc!(g, a...) # if a doesn't comply,
            catch end # just pass.
            if remove
                removed += 1
            end
        end
    end
    return removed
end

"""
    add_node!(g, u)
add a node u to graph g. silently doesn't add anything if object is already a node.
"""
function add_node!(g::Graph, u)
    if !haskey(g.fadj, u) # operation only for nonexisting
        insert!(g.fadj, u, Dictionary())
        insert!(g.badj, u, Dictionary())
        g.nn += 1
        return u # something done
    else
        return nothing
    end
end

"""
    rem_node!(g, n)
Removes the node n and all adjacent arcs.
Attempting to remove a non-existent node will raise an exception.
"""
function rem_node!(g::Graph, n)
    succs = try
        g.fadj[n]
    catch KeyError
        return false # node n not in graph
    end  
    for u in keys(g.fadj[n])
        delete!(g.badj[u], n) # delete arc n-u on pred
    end
    g.na -= length(g.fadj[n]) # delete all arc from n on succ
    delete!(g.fadj, n)
    for u in keys(g.badj[n])
        g.na -= length(g.fadj[u][n])
        delete!(g.fadj[u], n) # delete arc u-n on succ
    end
    delete!(g.badj, n)
    g.nn -= 1
    return true # successful operation returns true
end

"""
    add_nodes_from!(g, nbunch)
add nodes from nbunch to g. nbunch is a container of nodes to add.
"""
function add_nodes_from!(g::Graph, nbunch::Vector)
    added = []
    for n in nbunch
        add = add_node!(g, n)
        if !isnothing(add)
            push!(added, add)
        end
    end
    return added
end

"""
    rem_nodes_from!(g, nbunch)
remove several nodes at once. nbunch are the containers of nodes to remove.
If a node in the container is not in the graph it is silently ignored.
"""
function rem_nodes_from!(g::Graph, nbunch::Vector)
    removed = 0
    for n in nbunch
        remove = try
            rem_node!(g, n) # if any key error,
        catch end # just pass.
        if remove
            removed += 1
        end
    end
    return removed
end