with(Statistics):
with(combinat):
with(StringTools):
with(FileTools):
with(FileTools[Text]):
with(GraphTheory):

Help_utilities:=proc()
    print(` section(n) , mex(st) , ident(n) , InitCounter(n) `):
    print(` IncCounter(counter) , CounterToSet(ctr) `):
    print(` RandCounter(n) , DequoteString(str) , MapleMod(n,m) `):
    print(` InitCompCounter(digs, start:=1) `):
    print(` IncCompCounter(counter) , ValCompCounter(counter) `):
    print(` ToLatexArray(str, hlimit, noconvsings:=true, noorphans:=true) `):
    print(` Parse(data) , VertexEncode(vtx) , EdgeMerge(elist) `):
    print(` TensorProductD() , WalkAvoider(G, avoid) `):
    print(` PruneD(G, start) , ArrivalsD(G, v) `):
    print(` DeparturesD(G, v) `):
end:

#First n integers in a set
section:=proc(n) local ret,i:
    ret:={}:
    for i from 1 to n do
        ret:=ret union {i}:
    od:

    return ret:
end:

#minimum excluded element
mex:=proc(st) local i:
    for i from 0 while i in st do od:
    return i:
end:

#identity function
ident:=proc(n):
    return n:
end:

#Counter from 0 to 2^n-1
InitCounter:=proc(n) local i:
    return [seq(0,i=1..n)]:
end:

#Increment the counter; return the new counter
#Return false if overflowed the counter
IncCounter:=proc(counter) local ctr,i:
    ctr:=counter:
    i:=1:
    while i<=nops(ctr) and ctr[i]=1 do
        ctr[i]:=0:
        i:=i+1:
    od:
    if i<=nops(ctr) then
        ctr[i]:=1:
    else
        return false:
    fi:
    return ctr:
end:

#Create a set from a counter
CounterToSet:=proc(ctr) local i,S:
    S:={}:
    for i from 1 to nops(ctr) do
        if ctr[i]=1 then
            S:=S union {i}:
        fi:
    od:
    return S:
end:

#Counter from 0 to 2^n-1, initialized with a random value
RandCounter:=proc(n) local i,ra:
    ra:=rand(0..1):
    return [seq(ra(),i=1..n)]:
end:

#Remove all literal quotes from a string
DequoteString:=proc(str) local ret:
    return Join(Split(str,"\"")):
end:

#Mod, but don't return 0, return m instead
MapleMod:=proc(n,m) local ret:
    ret:=n mod m:
    if ret=0 then
        return m:
    else
        return ret:
    fi:
end:

#Compound counter, each digit has a different cap,
#start from start
InitCompCounter:=proc(digs, start:=1) local i:
    return [[seq(start,i=1..nops(digs))],digs,start]:
end:

#Increment compound counter; return the new counter
#Return false if overflowed the counter
IncCompCounter:=proc(counter) local ctr,i:
    ctr:=counter:
    i:=1:
    while i<=nops(ctr[1]) and ctr[1][i]=ctr[2][i] do
        ctr[1][i]:=ctr[3]:
        i:=i+1:
    od:
    if i<=nops(ctr[1]) then
        ctr[1][i]:=ctr[1][i] + 1:
    else
        return false:
    fi:
    return ctr:
end:

#Get the value of a compound counter
ValCompCounter:=proc(counter)
    return counter[1]:
end:

#Convert a long, commaspace-separated list into a LaTeX array
#where hlimit is the point at which line splitting is begun
#to be considered
#If noconvsings is true, do not convert if would be one line
#If noorphans is true, then there will not be a singleton number in the last line
ToLatexArray:=proc(str, hlimit, noconvsings:=true, noorphans:=true)
local ret,k,l,orphan:
    ret:=[""]:
    l:=1:
    orphan:=false:
    for k from 1 to length(str) do
        if l >= hlimit and str[k] = " " then
            l:=1:
            ret:=[op(ret),""]:
            orphan:=true:
        else
            ret[nops(ret)]:=cat(ret[nops(ret)],str[k]):
            l:=l+1:
        fi:
        if str[k] = "," then
            orphan:=false:
        fi:
    od:
    if orphan and noorphans then
        ret[nops(ret)-1]:=cat(ret[nops(ret)-1], " ",
            ret[nops(ret)]):
        ret:=[op(1..nops(ret)-1,ret)]:
    fi:
    if noconvsings and nops(ret) = 1 then
        return str:
    else
        return cat("\n\\begin{array}{l}\n", Join(ret, "\\\\\n"),
            "\n\\end{array}\n"):
    fi:
end:

#Like parse, but works with non-string arguments
Parse:=proc(data)
    return parse(convert(data, string)):
end:

#Encode vertex
VertexEncode:=proc(vtx):
    return convert(vtx, string):
end:

#Merge edges
EdgeMerge:=proc(elist) local ret, i:
    ret:=[[],[]]:
    for i from 1 to nops(elist) do
        ret[1]:=[op(ret[1]), Parse(elist[i][1])]:
        ret[2]:=[op(ret[2]), Parse(elist[i][2])]:
    od:
    return [VertexEncode(ret[1]), VertexEncode(ret[2])]:
end:

#Tensor Product of Digraphs, because Maple is an idiot
TensorProductD:=proc() local GL, V, E, T, i, j, NV:
    GL:=[_passed]:
    #NV:=[seq(nops(Vertices(GL[i])), i=1..nops(GL))]:
    V:=[]:
    T:=cartprod([seq([seq(Parse(Vertices(GL[i])[j]),
        j=1..nops(Vertices(GL[i])))], i=1..nops(GL))]):
    while not T[finished] do
        V:=[op(V), VertexEncode(T[nextvalue]())]:
    od:
    E:={}:
    T:=cartprod([seq(Edges(GL[i]), i=1..nops(GL))]):
    while not T[finished] do
        E:=E union {EdgeMerge(T[nextvalue]())}:
    od:
    #print(V, E):
    return Graph(V, E):
end:

#Produce a graph G' which is like G but it avoids the walk avoid
#avoid must have length at least 2 and be able to appear in G
#or else the behavior is undefined
WalkAvoider:=proc(G, avoid)
local V, E, i, vertices, edges, e, T, newv, dep, v, E2:
    vertices:=Vertices(G):
    edges:=Edges(G):
    V:=[seq(VertexEncode([op(Parse(vertices[i])), 0]),
        i=1..nops(vertices))]:
    E:={seq([VertexEncode([op(Parse(e[1])),0]),
        VertexEncode([op(Parse(e[2])),0])], e in edges)}:
    T:=table():
    for i from 1 to nops(vertices) do
        #print(Parse(vertices[i])):
        T[Parse(vertices[i])[1]]:=1:
    od:
    E2:={}:
    for e in E do
        #print(e):
        if Parse(e[1])[1] <> avoid[1] or
                Parse(e[2])[1] <> avoid[2] then
            E2:=E2 union {e}:
        fi:
    od:
    E:=E2:
    for i from 2 to nops(avoid) - 1 do
        newv:=[op(Parse(avoid[i])), T[avoid[i]]]:
        V:=[op(V), VertexEncode(newv)]:
        T[avoid[i]]:=T[avoid[i]] + 1:
        E:=E union {[VertexEncode([op(Parse(avoid[i-1])),
            T[avoid[i-1]]-1]), VertexEncode(newv)]}:
        dep:=Departures(G, VertexEncode([avoid[i]])):
        for v in dep do
            if Parse(v)[1] <> avoid[i+1] then
                E:=E union {[VertexEncode(newv),
                    VertexEncode([op(Parse(v)), 0])]}:
            fi:
        od:
    od:
    return Graph(V, E):
end:

#Remove all of graph not reachable from start vertex
#Uses depth-first search
PruneD:=proc(G, start) local V, T, S, v, w, dep, vstart:
    vstart:=VertexEncode(start):
    S:=stack[new](vstart):
    V:={vstart}:
    while not stack[empty](S) do
        v:=stack[pop](S):
        dep:=Departures(G, v):
        for w in dep do
            if not(w in V) then
                V:=V union {w}:
                stack[push](w, S):
            fi:
        od:
    od:
    return InducedSubgraph(G, V):
end:

#Better arrivals, so strings don't need to be as good
ArrivalsD:=proc(G, v)
    return Arrivals(G, VertexEncode(Parse(v))):
end:

#Better departures, so strings don't need to be as good
DeparturesD:=proc(G, v)
    return Departures(G, VertexEncode(Parse(v))):
end: