import graphviz as gv

"""
Explanation: Heapsort
Graphical Representation
End of explanation
"""


def toDot(A, f, g, u=None):
    n   = len(A)
    dot = gv.Digraph(node_attr={'shape': 'record'})
    for k, p in enumerate(A):
        if k == u:
            dot.node(str(k), label='{' + str(p) + '|' + str(k) + '}', style='filled', fillcolor='orange')
        elif k < f:
            dot.node(str(k), label='{' + str(p) + '|' + str(k) + '}', style='filled', fillcolor='red')
        elif k < g:
            dot.node(str(k), label='{' + str(p) + '|' + str(k) + '}', style='rounded')
        else:
            dot.node(str(k), label='{' + str(p) + '|' + str(k) + '}', style='filled', fillcolor='green')
    for k in range(0, n // 2):
        if 2 * k + 1 < g:
            dot.edge(str(k), str(2 * k + 1))
        if 2 * k + 2 < g:
            dot.edge(str(k), str(2 * k + 2))
    return dot

"""
Explanation: The function toDot takes four arguments:
- A is an array of natural numbers of length $n$,
- f is a natural number such that $0 \leq f < n$ holds,
- g is a natural number such that $f < g < n$ holds,
- u is a natural number such that $0 \leq u < n$ holds.
  This argument is optional.
The function returns a graphical representation of the array A as a heap. 
This graphical representation is stored as a directed graph with an encoding suitable for graphviz. 
The part A[0:g] is represented as a binary tree, while the part A[g:] is represented
as a list.  Furthermore, all indexes in the range A[k:g] satisfy the heap condition.  The nodes in the range [0:k-1]
are colored red.  If u is set, the node A[u] is colored orange.
End of explanation
"""


def swap(A, i, j):
    A[i], A[j] = A[j], A[i]

"""
Explanation: HeapSort
The function call swap(A, i, j) takes an array A and  two indexes i and j and exchanges the elements at these indexes.
End of explanation
"""


def ascend(A, k):
    while k > 0:
        p = (k - 1) // 2
        if A[k] < A[p]:
            swap(A, p, k)
            k = p
        else:
            return   

"""
Explanation: The function ascend takes two arguments:
- A is an array that is represented as a list in Python.
- k is an index into the array A.
Therefore we have $k \in \bigl{0, \cdots, \texttt{len}(A)-1\bigr}$.
The array A represents a heap.  However, the <em style="color:blue">heap condition</em> might be violated 
at index k: It might be the case that the element at this index is to small and needs to rise to the top
of the heap.  The function ascend will fix the heap condition and will rise the element A[k] as much 
as is necessary to turn A into a heap.
End of explanation
"""


def descend(A, k, n):
    while 2 * k + 1 <= n:
        j = 2 * k + 1
        if j + 1 <= n and A[j] > A[j + 1]:
            j += 1
        if A[k] < A[j]:
            return
        swap(A, k, j)
        k = j

"""
Explanation: The function sink takes three arguments.
- A is the array representing the heap.
- k is an index into the array A.
- n is the upper bound  of the part of this array that has to be transformed into a heap.  
The array A itself might actually have more than $n+1$ elements, but for the
purpose of the method sink we restrict our attention to the subarray
A[k:n]. 
When calling sink, the assumption is that A[k:n+1] should represent a heap 
that possibly has its heap condition violated at its root, i.e. at index k.  The
purpose of the procedure sink is to restore the heap condition at index k.
- We compute the index j of the left subtree below index k.
- We check whether there also is a right subtree at position j+1.
This is the case if j + 1 &lt;= n.
- If the heap condition is violated at index k, we exchange the element at  position k 
  with the child that has the higher priority, i.e. the child that is smaller. 
- Next, we check in line 9 whether the heap condition is violated at index k.
  If the heap condition is satisfied, there is nothing left to do and the procedure returns.  

Otherwise, the element at position k is swapped with
  the element at position j.  

Of course, after this swap it is possible that the heap condition is
  violated at position j.  Therefore,  k is set to j and the while-loop continues
  as long as the node at position k has at least one child, i.e. as long as 
  2 * k + 1 &lt;= n.
End of explanation
"""


def heap_sort(A):
    n = len(A)
    for k in range(1, n):
        display(toDot(A, 0, k+1, k))
        ascend(A, k)
        display(toDot(A, 0, k+1))
    n = n - 1
    while n >= 1:
        swap(A, 0, n)
        display(toDot(A[:], 1, n + 1))
        n -= 1
        descend(A, 0, n)
        display(toDot(A[:], 0, n + 1))

"""
Explanation: The function $\texttt{heapSort}$ has the task to sort the array A and proceeds in two phases.
- In phase one our goal is to transform the array Ainto a heap that is stored in A.
In order to do so, we traverse the array A in reverse in a loop.
  The invariant of this loop is that before ascend is called, the array A[:k]
  is a heap.  The call ascend(A, k) inserts the element A[k] at the proper place and
  thereby extends the heap to A[:k+1].
- In phase two we remove the elements from the heap one-by-one and insert them at the end of
  the array.
When the while-loop starts, the array A contains a heap.  Therefore,
  the smallest element is found at the root of the heap.  Since we want to sort the
  array A descendingly, we move this element to the end of the array A and in
  return move the element from the end of the arrayAto the front.
  After this exchange, the sublist A[0:n-1] represents a heap, except that the
  heap condition might now be violated at the root.  Next, we decrement n, since the
  last element of the array A is already in its correct position.
  In order to reestablish the heap condition at the root, we call sink with index
  \texttt{0}.
End of explanation
"""


import random as rnd

def demo():
    L = [ rnd.randrange(1, 200) for n in range(12) ]
    print("L = ", L)
    heap_sort(L)
    print("L = ", L)

demo()

"""
Explanation: Testing
End of explanation
"""


