struct Arc
    u::Any
    v::Any
    key::Any
end

Arc(t::Tuple) = Arc(t[1], t[2], t[3])

source(a::Arc) = a.u
target(a::Arc) = a.v
key(a::Arc) = a.key

add_arc!(g::Graph, a::Arc) = add_arc!(g, a.u, a.v, a.key)
rem_arc!(g::Graph, a::Arc) = rem_arc!(g, a.u, a.v, a.key)

function add_arcs_from!(g::Graph, abunch::Vector{Arc})
    keylist = []
    for a in abunch
        res = add_arc!(g, a)
        push!(keylist, res)
    end
    return keylist
end

function rem_arcs_from!(g::Graph, abunch::Vector{Arc})
    removed = 0
    for a in abunch
        remove = try
            rem_arc!(g, a) # if a doesn't comply,
        catch end # just pass.
        if remove
            removed += 1
        end
    end
    return removed
end

function ==(a1::Arc, a2::Arc)
    return source(a1) == source(a2) && target(a1) == target(a2) && key(a1) == key(a2)
end

getindex(g::Graph, a::Arc) = g.fadj[a.u][a.v][a.key]
getindex(g::Graph, u, v, key) = g[Arc(u, v, key)]
getindex(g::Graph, a::Arc, attrib::Symbol) = g[a][attrib]
getindex(g::Graph, u, v, key, attrib::Symbol) = g[Arc(u, v, key)][attrib]

"""
    setindex!(g, val, a, attrib)
setindex! are exclusive for setting arc attributes only.
To delete an attribute, use delete!(g[a], attrib).
"""
function setindex!(g::Graph, val, a::Arc, attrib::Symbol)
    if has_arc(g, a)
        set!(g.fadj[a.u][a.v][a.key], attrib, val)
        set!(g.badj[a.v][a.u][a.key], attrib, val)
        return g[a,attrib]
    else
        return nothing
    end
end

setindex!(g::Graph, val, u, v, key, attrib::Symbol) = setindex!(
    g, val, Arc(u, v, key), attrib
)

"""
    has_arc(g, a)
has_arc checks wether elementary arc a (u,v,key) exists in graph.
"""
function has_arc(g::Graph, a::Arc)
    try
        g[a]
    catch KeyError
        return false
    end
    return true
end

"""
    ArcIter
An iterator of the arcs in the graph.
"""
struct ArcIter
    len::Integer
    ulist::Vector
    vlist::Vector
    keylist::Vector
end

function iterate(ait::ArcIter, state=1)
    if state <= ait.len
        res = Arc(ait.ulist[state], ait.vlist[state], ait.keylist[state])
        state += 1
        return res, state
    else
        return nothing
    end
end

eltype(::ArcIter) = Arc
length(ait::ArcIter) = ait.len
keys(ait::ArcIter) = 1:ait.len

function rand(ait::ArcIter)
    r = rand(1:ait.len)
    res = (ait.ulist[r], ait.vlist[r], ait.keylist[r])
    return res
end

function ==(ait1::ArcIter, ait2::ArcIter) 
    return ait1.len == ait2.len && ait1.ulist == ait2.ulist && ait1.vlist == 
    ait2.vlist && ait1.keylist == ait2.keylist
end

"""
    ArcIter(g)
constructs an iterator of all arc in graph.
"""
function ArcIter(g::Graph, ::Colon, ::Colon)
    ulist = []; sizehint!(ulist, g.na)
    vlist = []; sizehint!(vlist, g.na)
    keylist = []; sizehint!(keylist, g.na)
    @inbounds for n in keys(g.fadj), nbrs in keys(g.fadj[n]), key in keys(g.fadj[n][nbrs])
        push!(ulist, n)
        push!(vlist, nbrs)
        push!(keylist, key)
    end
    return ArcIter(g.na, ulist, vlist, keylist)
end

"""
    ArcIter(g, u)
constructs an iterator of all arc starting from u (single or multiple node).
ArcIter is precise and will raise an error if an element in u is not in graph.
"""
function ArcIter(g::Graph, u, ::Colon)
    len = 0
    ulist = []
    vlist = []
    keylist = []
    @inbounds for n in u, nbrs in keys(g.fadj[n]), key in keys(g.fadj[n][nbrs])
        push!(ulist, n)
        push!(vlist, nbrs)
        push!(keylist, key)
        len += 1
    end
    return ArcIter(len, ulist, vlist, keylist)
end

"""
    ArcIter(g, :, v)
constructs an iterator of all arc ending at v.
ArcIter is precise and will raise an error if an element in v is not in graph.
"""
function ArcIter(g::Graph, ::Colon, v)
    len = 0
    ulist = []
    vlist = []
    keylist = []
    @inbounds for nbrs in v, n in keys(g.badj[nbrs]), key in keys(g.badj[nbrs][n])
        push!(ulist, n)
        push!(vlist, nbrs)
        push!(keylist, key)
        len += 1
    end
    return ArcIter(len, ulist, vlist, keylist)
end

"""
    ArcIter(g, u, v)
constructs an iterator of all arc inside u-v.
ArcIter is precise and will raise an error if an element in v is not in graph.
"""
function ArcIter(g::Graph, u, v)
    len = length(g.fadj[u][v])
    ulist = []; sizehint!(ulist, len)
    vlist = []; sizehint!(vlist, len)
    keylist = []; sizehint!(keylist, len)
    @inbounds for key in keys(g.fadj[u][v])
        push!(ulist, u)
        push!(vlist, v)
        push!(keylist, key)
    end
    return ArcIter(len, ulist, vlist, keylist)
end

"""
    arcs(g, u, v)
Returns the arcs of a graph g starting from u, ending at v.
The default value of u and v are Colon() to collect every arc.
If u is an iterable container, v must be Colon, vice versa.
"""
arcs(g::Graph, u=:, v=:) = ArcIter(g, u, v)

function getindex(ait::ArcIter, inds)
    if isa(inds, Integer)
        return Arc(ait.ulist[inds], ait.vlist[inds], ait.keylist[inds])
    else
        res = Arc[]
        for i in inds
            push!(res, getindex(ait, i))
        end
        return res
    end
end

firstindex(ait::ArcIter) = 1
lastindex(ait::ArcIter) = ait.len

function has_attrib(g::Graph, attrib::Symbol)
    for a in arcs(g)
        if !(attrib in keys(g[a]))
            return false
        end
    end
    return true
end