Sort2Tex

Print into Tikz the steps of a sorting algorithm
mail@pastecode.io avatar
unknown
python
a year ago
4.3 kB
80
Indexable
Never

indentPattern="  "

def printTikzArray(a,indent=0,wrapInTikz=False,cellPrefix="c",scopeoptions=""):
    res=""
    n=len(a)
    if n<1:
        res="% Attempt to print an empty array\n"
    else:
        if wrapInTikz:
            res+=indentPattern*indent+"\\begin{tikzpicture}\n"
        else:
            res+=indentPattern*indent+"\\begin{scope}["+scopeoptions+"]\n"
        indent+=1
        res+=indentPattern*indent
        res+="\\node[cell,{styles}] ({pref}0) at (0,0) {{{v[val]}}};\n".format(v=a[0],pref=cellPrefix,styles=','.join(a[0]['style']))
        for i in range(1,n):
            res+=indentPattern*indent
            res+="\\node[cell,anchor=west,{styles}] ({pref}{curr}) at ({pref}{prev}.east){{{v[val]}}};\n".format(v=a[i],curr=i,prev=i-1,pref=cellPrefix,styles=','.join(a[i]['style']))
        indent-=1
        if wrapInTikz:
            res+=indentPattern*indent+"\\end{tikzpicture}\n"
        else:
            res+=indentPattern*indent+"\\end{scope}\n"
    return res

def unstyledArray(a,defaultStyle=[]):
    res=[]
    for v in a:
        res.append({'val':v,'style':defaultStyle.copy()})
    return res

def printArray(a):
    return "["+", ".join(map(str,a)) +"]"
    
def printArrayValues(a):
    return "["+", ".join(map(lambda x:str(x['val']),a)) +"]"

def displayedBubbleSort(a,vDist=15): # vDist: vertical shift distance between arrays, in pt
    sa=unstyledArray(a)
    indent=1
    res=""
    n=len(a)
    res+=indentPattern*indent+"\\begin{tikzpicture}\n"
    indent+=1
    step=0
    res+=indentPattern*indent+"% Initial array "+printArrayValues(sa)+"\n"
    res+=printTikzArray(sa,indent=indent,wrapInTikz=False,cellPrefix="step{s}c".format(s=step))
    step+=1 # Increase "step" after each print so arrays are vertically separated
    for p in range(0,n):
        for i in range(n-1,p,-1):
            swapped=False
            sa[i]['style'].append("current")
            sa[i-1]['style'].append("currentCmp")
            if sa[i]['val'] < sa[i-1]['val']:
                swapped=True
                # pre-swap print, maybe not needed?
                res+="\n"+indentPattern*indent+"% Phase {} (i={}), before - Array ".format(p,i)+printArrayValues(sa)+"\n"
                res+=printTikzArray(sa,indent=indent,wrapInTikz=False,cellPrefix="step{s}c".format(s=step),scopeoptions="yshift=-{y}pt".format(y=step*vDist))
                step+=1
                sa[i]['style'].append("swapped")
                sa[i-1]['style'].append("swapped")
                tmp=sa[i]['val']
                sa[i]['val']=sa[i-1]['val']
                sa[i-1]['val']=tmp
            res+="\n"+indentPattern*indent+"% Phase {} (i={}) - Array ".format(p,i)+printArrayValues(sa)+"\n"
            res+=printTikzArray(sa,indent=indent,wrapInTikz=False,cellPrefix="step{s}c".format(s=step),scopeoptions="yshift=-{y}pt".format(y=step*vDist))
            if swapped:
                res+=indentPattern*indent+"\\path[swaparrow] (step{sprev}c{last}.east) edge[swapedge] node[auto] {{swap!}} (step{s}c{last}.east);\n".format(s=step,sprev=step-1,last=n-1)
            step+=1
            for s in ("current","currentCmp","swapped"):
                for e in (sa[i]['style'],sa[i-1]['style']):
                    if s in e:
                        e.remove(s)
        sa[p]['style'].append("sorted")
    res+="\n"+indentPattern*indent+"% Final array "+printArrayValues(sa)+"\n"
    res+=printTikzArray(sa,indent=indent,wrapInTikz=False,cellPrefix="step{s}c".format(s=step),scopeoptions="yshift=-{y}pt".format(y=step*vDist))
    indent-=1
    res+=indentPattern*indent+"\\end{tikzpicture}\n"
    return res

def texWrap(f,c):
    preamble="""\\documentclass{article}
\\usepackage{tikz}

\\tikzstyle{cell}=[outer sep=0pt,draw]
\\tikzstyle{current}=[fill=black!80,text=white]
\\tikzstyle{currentCmp}=[fill=black!20,text=black]
\\tikzstyle{swapped}=[line width=1.5pt,draw=red!80!black]
\\tikzstyle{sorted}=[fill=green!10]
\\tikzstyle{swaparrow}=[draw]
\\tikzstyle{swapedge}=[out=10,in=-10,out distance=0.8cm,in distance=0.8cm,looseness=2,->]

\\begin{document}
"""
    tex = open(f, "w")
    tex.write(preamble)
    tex.write(c)
    tex.write("\\end{document}\n")
    tex.close()
    return


def main():
    testArr=[1,2,5,27,4,3,8] # I/O TODO
    texWrap("bubbleSort.tex",displayedBubbleSort(testArr,vDist=17))
    return

main()