from gvanim import Animation
from gvanim.jupyter import interactive
ga = Animation()

"""
Explanation: Using GraphvizAnim to show how heapsort works
Import the required packages and instantiate the animation
End of explanation
"""


heap = [ None, 5, 6, 7, 8, 9, 10, 11, 12 ]

"""
Explanation: Define an heap
End of explanation
"""


ga.label_node( 1, heap[ 1 ] )
for i in range( 2, len( heap ) ):
    ga.label_node( i, heap[ i ] )
    ga.add_edge( i // 2, i )

"""
Explanation: Now draw it (nodes will be named as the array indices and labelled as the array values)
End of explanation
"""


def down_heap( i, n ):
    t = heap[ i ]
    while i <= n // 2:
        ga.highlight_node( i )
        ga.next_step()
        j = 2 * i
        if j < n and heap[ j ] < heap[ j + 1 ]: j += 1
        ga.highlight_edge( i, j )    
        ga.next_step()
        if t >= heap[ j ]: break
        heap[ i ] = heap[ j ]
        ga.highlight_node( i )
        ga.highlight_node( j )
        ga.label_node( i, heap[ i ] )
        ga.label_node( j, heap[ j ] )             
        ga.next_step()
        i = j
    heap[ i ] = t
    ga.highlight_node( i )
    ga.label_node( i, heap[ i ] )
    ga.next_step()

"""
Explanation: Define the usual iterative down heap procedure (endowed with animation actions)
End of explanation
"""


n = len( heap ) - 1
ga.next_step()
for i in range( n // 2, 0, -1 ):
    down_heap( i, n )

"""
Explanation: Fix the heap calling down_heap on his lower half
End of explanation
"""


ga.next_step()
while n > 1:
    heap[ 1 ], heap[ n ] = heap[ n ], heap[ 1 ]
    ga.highlight_node( 1 )
    ga.highlight_node( n )
    ga.label_node( 1, heap[ 1 ] )
    ga.label_node( n, heap[ n ] )             
    ga.next_step()
    n -= 1
    down_heap( 1, n )

"""
Explanation: And finally exchange the top with heap positions starting form the last one (fixing again with down_heap)
End of explanation
"""


interactive( ga, 400 )

"""
Explanation: We are ready to plot the animation interactively! 
Be patient: to generate the required 68 graphs will take quite a bit of time; moreover, in case Jupyter does not correctly resize the cell just zoom in and out the document size (with the browser).
End of explanation
"""


