"""
Test the heapsort strategy.
CSCI 204
Fall 2017
Xiannong Meng
"""
from arrayheap import *

from time import *
import random

def validate() :
    """Validate the basic operations"""

    print( 'Performing some basic checking ...' )
    values = [ 9, 5, 10, 0, 6, 11, -1, 1, 2 ]
    print( 'original data ...' )

    heap = MaxHeap( len( values ) )
    for x in values:
        heap.add( x )

    print( 'after building the heap' )
    print( heap )

    for i in range( len( values ) ):
        values[ i ] = heap.extract()

    print( 'array after heapsort : ' )
    for x in values:
        print( x, end = ', ')
    print()

def build_sort( size ):
    """ Test the building and sorting of a heap of size n"""

    print( 'Performing add and sort in ', size, ' keys...' )
    # First, generate a list of integers
    a = []
    for i in range( size ):
        a.append( random.randint( 1, size ) )

    heap = MaxHeap( len(a) )

    # record the start time for building the table
    startA = time()
    for i in range( size ):
        heap.add( a[i] )
    finishA = time()

    # record the start time for sorting
    startB = time()
    for i in range( len( a ) ):
        a[ i ] = heap.extract()
    
    # record the finish time for searching
    finishB = time()

    print( 'building time : ', '{0:0.6f}'.format(finishA - startA), ' seconds.' )
    print( 'sorting time : ', '{0:0.6f}'.format(finishB - startB), ' seconds.' )

def test_timing() :
    """Test the time needed"""
    random.seed( 10 )    # any integer to specify the seed

    build_sort( 10000 )
    build_sort( 100000 )


validate()
test_timing()