"""
Demonstrates simple binary search trees. 
Implements and performs string conversion and search only.
file: bst.py
language: python3
author: Phil White
author: A. Nunes-Harwitt
author: ben k steele
author: Sean Strout
"""

############################################################
# Class definitons
############################################################

class Empty():
    """An empty tree is represented as an instance of Empty"""
    __slots__ = ()   

class NonEmpty():
    """A non-empty tree is represented as an instance of NonEmpty"""
    __slots__ = ( 'left', 'value', 'right' )


############################################################
# Make functions
############################################################

def mkEmpty():
    """Constructor: mkEmpty: () -> Empty"""
    return Empty()

def mkNonEmpty( b1, v, b2 ):
    """Constructor: 
       mkNonEmpty: BinaryTree * Number * BinaryTree -> NonEmpty
    """
    node = NonEmpty()
    node.left = b1
    node.value = v
    node.right = b2
    return node


############################################################
# Sample trees
############################################################

exampleTree0 = mkEmpty()

exampleTree1 = mkNonEmpty( mkEmpty(), 1, mkEmpty() )

exampleTree2 = mkNonEmpty( mkNonEmpty( mkEmpty(), 1, mkEmpty() ), 3, mkEmpty() )

exampleTree3 = mkNonEmpty( mkEmpty(), 3, mkNonEmpty( mkEmpty(), 4, mkEmpty() ) )

# t2 in notes
exampleTree4 = mkNonEmpty( mkNonEmpty( mkEmpty(), 1, mkEmpty() ), \
                           3,\
                           mkNonEmpty( mkEmpty(), 4, mkEmpty() ) )

exampleTree5 = mkNonEmpty( mkNonEmpty( mkEmpty(), 6, mkEmpty() ), \
                           7,                                   \
                           mkNonEmpty( mkEmpty(), 9, mkEmpty() ) )

exampleTree6 = mkNonEmpty( exampleTree4, 5, exampleTree5 )

exampleTree7 = mkNonEmpty(mkEmpty(), 1, \
                          mkNonEmpty( mkEmpty(), 2, \
                                      mkNonEmpty( mkEmpty(), 3, \
                                                  mkNonEmpty( mkEmpty(), 4, \
                                                              mkNonEmpty( mkEmpty(), 5, \
                                                                          mkEmpty() )\
                                                              )\
                                                  )\
                                      )\
                          )
                          

############################################################
# String Conversion
############################################################

def bstToString( tr ):
    """bstToString: BinarySearchTree -> String"""
    return ""

# Tests
def test_bstToString():
    """
    test_bstToString : Void -> None
    """
    print( 'Testing bstToString' )
    print( bstToString( exampleTree0 ) == '', end=' ' )
    print( bstToString( exampleTree1 ) == '1 ', end=' ' )
    print( bstToString( exampleTree2 ) == '1 3 ', end=' ' )
    print( bstToString( exampleTree3 ) == '3 4 ', end=' ' )
    print( bstToString( exampleTree4 ) == '1 3 4 ', end=' ' )
    print( bstToString( exampleTree5 ) == '6 7 9 ', end=' ' )
    print( bstToString( exampleTree6 ) == '1 3 4 5 6 7 9 ', end = ' ' )
    print( bstToString( exampleTree7 ) == '1 2 3 4 5 ' )

############################################################
# Height
############################################################

def bstHeight( tr ):
    """
    bstHeight : BinarySearchTree -> Integer
    """
    return -1

# Tests
def test_bstHeight():
    """
    test_bstToString : Void -> None
    """
    print( 'Testing bstToString' )
    print( bstHeight( exampleTree0 ) ==-1,  end=' ' )
    print( bstHeight( exampleTree1 ) == 0, end=' ' )
    print( bstHeight( exampleTree2 ) == 1, end=' ' )
    print( bstHeight( exampleTree3 ) == 1, end=' ' )
    print( bstHeight( exampleTree4 ) == 1, end=' ' )
    print( bstHeight( exampleTree5 ) == 1, end=' ' )
    print( bstHeight( exampleTree6 ) == 2, end=' ' )
    print( bstHeight( exampleTree7 ) == 4 )

############################################################
# Print
############################################################

def bstPrint( tr ):
    pass

############################################################
# Search
############################################################

def bstSearch( tr, e ):
    """bstSearch: BinarySearchTree * Number -> Boolean"""
    return False

# Tests
def test_bstSearch():
    """
    test_bstSearch : Void -> None
    """
    print( 'Testing bstSearch' )
    print( bstSearch( exampleTree0, 3 ) == False, end=' ' )
    print( bstSearch( exampleTree1, 1 ) == True, end=' ' )
    print( bstSearch( exampleTree1, 3 ) == False, end=' ' )
    print( bstSearch( exampleTree2, 1 ) == True, end=' ' )
    print( bstSearch( exampleTree2, 3 ) == True, end=' ' )
    print( bstSearch( exampleTree2, 2 ) == False, end=' ' )
    print( bstSearch( exampleTree2, 4 ) == False, end=' ' )
    print( bstSearch( exampleTree3, 3 ) == True, end=' ' )
    print( bstSearch( exampleTree3, 4 ) == True, end=' ' )
    print( bstSearch( exampleTree3, 1 ) == False, end=' ' )
    print( bstSearch( exampleTree3, 5 ) == False, end=' ' )
    print( bstSearch( exampleTree4, 1 ) == True, end=' ' )
    print( bstSearch( exampleTree4, 3 ) == True, end=' ' )
    print( bstSearch( exampleTree4, 4 ) == True, end=' ' )
    print( bstSearch( exampleTree4, 0 ) == False, end=' ' )
    print( bstSearch( exampleTree4, 2 ) == False, end=' ' )
    print( bstSearch( exampleTree4, 3.5 ) == False, end=' ' )
    print( bstSearch( exampleTree4, 5 ) == False, end=' ' )
    print( bstSearch( exampleTree6, 1 ) == True, end=' ' )
    print( bstSearch( exampleTree6, 3 ) == True, end=' ' )
    print( bstSearch( exampleTree6, 4 ) == True, end=' ' )
    print( bstSearch( exampleTree6, 5 ) == True, end=' ' )
    print( bstSearch( exampleTree6, 6 ) == True, end=' ' )
    print( bstSearch( exampleTree6, 7 ) == True, end=' ' )
    print( bstSearch( exampleTree6, 9 ) == True, end=' ' )
    print( bstSearch( exampleTree6, 0 ) == False, end=' ' )
    print( bstSearch( exampleTree6, 2 ) == False, end=' ' )
    print( bstSearch( exampleTree6, 3.5 ) == False, end=' ' )
    print( bstSearch( exampleTree6, 4.5 ) == False, end=' ' )
    print( bstSearch( exampleTree6, 5.5 ) == False, end=' ' )
    print( bstSearch( exampleTree6, 6.5 ) == False, end=' ' )
    print( bstSearch( exampleTree6, 8 ) == False, end=' ' )
    print( bstSearch( exampleTree6, 10 ) == False )


# run tests

if __name__ == "__main__":
    test_bstToString()
    print("======================")
    test_bstHeight()
    print("======================")
    test_bstSearch()