import structures_lib
import binary_tree

type Iterator = {
    reset->Void
    hasNext->Boolean
    get->T
    next->T}

type BinaryTree = {
    ==(_:BinaryTree)->Boolean
    getLeft->BinaryTree
    getRight->BinaryTree
    getParent->BinaryTree
    setLeft(_:BinaryTree)->Void   //when generic types totally work will
    setRight(_:BinaryTree)->Void  // take argument of type BinaryTree
    setParent(_:BinaryTree)->Void
    size->Number
    root->BinaryTree
    height->Number
    depth->Number
    isFull->Boolean
    isEmpty->Boolean
    isComplete->Boolean
    isBalanced->Boolean
    isLeftChild->Boolean
    isRightChild->Boolean
    getValue->T
    setValue(_:T)->Void
    treeString->String
    asString->String
    inorderIterator->Iterator
    preorderIterator->Iterator
    postorderIterator->Iterator}

// T needs to have ==, < as methods
type BinarySearchTree = {
    isEmpty->Boolean
    clear->Void
    size->Number
    add(_:T)->Void
    contains(_:T)->Boolean
    getValue(_:T)->T
    removeValue(_:T)->T
    iterator->Iterator
    treeString->String
    asString->String}

def missing is public, readable = object{
    method asString->String{"-"}
}

// returns instance of BST with no data
method new->BinarySearchTree{BinarySearchTreeClass.new}

class BinarySearchTreeClass.new{

    // node to be used as all leaves in this implementation
    def EMPTY:BinaryTree is readable = binary_tree.new

    var root:BinaryTree is readable := EMPTY
    var count:Number is readable:= 0
    
    // @post @return true iff BST contains no data
    method isEmpty->Boolean is public{root.isEmpty}

    // @post removes all elements from BST
    method clear->Void is public{
        root := EMPTY
        count := 0}

    // @post @return number of elements in BST
    method size->Number is public{count}

    // @pre root is not empty
    // @post @return existing tree node w/ desired value, or
    //               node to which value should be added
    // @param rt the root of the BST
    // @param value the value to be located within tree
    method locate(rt:BinaryTree, value:Dynamic)->BinaryTree is confidential{
        var rootValue:Dynamic := rt.getValue
        var child:BinaryTree
        if(rootValue == value) then{return rt}
        if(rootValue < value) then{
            child := rt.getRight}
        else{child := rt.getLeft}
        if(child.isEmpty) then{rt}
        else{locate(child, value)}
    }

    method predecessor(rt:BinaryTree)->BinaryTree is confidential{
        if(rt.isEmpty) then{return EMPTY}
        if(rt.getLeft.isEmpty) then{return EMPTY}
        var result:BinaryTree := rt.getLeft
        while{!result.getRight.isEmpty} do{
            result := result.getRight}
        result}

    method successor(rt:BinaryTree)->BinaryTree is confidential{
        if(rt.isEmpty) then{return EMPTY}
        if(rt.getRight.isEmpty) then {return EMPTY}
        var result:BinaryTree := rt.getRight
        while{!result.getLeft.isEmpty} do{
            result := result.getLeft}
        result}
  
    // @post adds a (possibly duplicate) value to BST
    // @param value the value to be added
    method add(value:Dynamic)->Void is public{
        var newNode:BinaryTree := binary_tree.withValue(value)
        // create value at root if there's no root
        if(root.isEmpty) then {root := newNode}
        else{
            var insertLocation:BinaryTree := locate(root, value)
            var nodeValue:Number := insertLocation.getValue
            // The location returned is successor or predecessor
            // of to-be-inserted value
            if(nodeValue < value) then{insertLocation.setRight(newNode)}
            else{
                if(!insertLocation.getLeft.isEmpty) then{
                    // if value is in tree, insert just before
                    predecessor(insertLocation).setRight(newNode)}
                else{insertLocation.setLeft(newNode)}
            }
        }
        count := count + 1}

    // @post @return true iff value is found within tree
    // @param value the value sought
    method contains(value:Dynamic)->Boolean is public{
        if(root.isEmpty) then{return false}
        var possibleLocation:BinaryTree := locate(root, value)
        return value == possibleLocation.getValue}

    // @post @return reference to value found in tree. Potentially
    // dangerous if returned value is modified.
    // @param value the value sought
    method getValue(value:Dynamic)->Dynamic is public{
        if(root.isEmpty) then{
            print "Tree is empty"
            return missing}
        var possibleLocation:BinaryTree := locate(root, value)
        if(value == possibleLocation.getValue) then{
            return possibleLocation.getValue}
        else{
            print "No such value in tree"
            return missing}
    }

    // @post removes one instance of value, if found
    // @param value the value to be removed
    // @return the actual value removed from tree
    method removeValue(value:Dynamic)->Dynamic is public{
        if(isEmpty) then {
            print "Tree is empty"
            return missing}
        if(value == root.getValue) then {
            var newroot:BinaryTree := removeTop(root)
            count := count -1 
            var result:Dynamic := root.getValue
            root := newroot
            return result}
        else{
            var location:BinaryTree := locate(root, value)
            if(value == location.getValue) then{
                count := count - 1
                var parent:BinaryTree := location.getParent
                if(parent.getRight == location) then{
                    parent.setRight(removeTop(location))}
                else{parent.setLeft(removeTop(location))}
                return location.getValue}
        }
        print "No such value in tree"
        return missing}

    // @pre topNode contains value we want to remove
    // @post removes top node & performs necessary rotations
    // to reconnect tree
    // @param topNode the node to be removed
    // @return root of new binary tree containing all of topNode's
    // descendants and rooted at its predecessor
    method removeTop(topNode:BinaryTree)->BinaryTree is confidential{
        var left:BinaryTree := topNode.getLeft
        var right:BinaryTree := topNode.getRight
        topNode.setLeft(EMPTY)
        topNode.setRight(EMPTY)
        if(left.isEmpty) then{return right}
        if(right.isEmpty) then{return left}
        var pred:BinaryTree := left.getRight
        if(pred.isEmpty) then{
            left.setRight(right)
            return left}
        var parent:BinaryTree := left
        while{!pred.getRight.isEmpty} do {
            parent := pred
            pred := pred.getRight}
        parent.setRight(pred.getLeft)
        pred.setLeft(left)
        pred.setRight(right)
        return pred}

    // @post @return in-order iterator to traverse binary tree.
    // Should not be used if tree is modified.
    method iterator->Iterator is public{root.inorderIterator}

    // @post @return string with graphical representation of tree
    method treeString->String is public{root.treeString}

    // @post @return string representation of tree
    method asString->String is public{
       var s:String := ""
       return s}
}