import structures_lib

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

type Stack = {
    push(_:T)->Void
    pop->T
    peek->T
    size->Number
    clear->Void
    contains(_:T)->Boolean
    isEmpty->Boolean
    iterator->Iterator
    asString->String}

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 should
    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}
    //levelorderIterator->Iterator} //don't have QueueList yet

//Instance of empty tree
def EmptyTree:BinaryTree is public, readable = object{

    method ==(other:BinaryTree)->Boolean is public{other.isEmpty}

    method getLeft->BinaryTree is public{self}

    method getRight->BinaryTree is public{self}

    method getParent->BinaryTree is public{self}

    method setLeft(_:BinaryTree)->Void is public{}

    method setRight(_:BinaryTree)->Void is public{}

    method setParent(_:BinaryTree)->Void is public{}

    method size->Number is public{0}

    method root->BinaryTree is public{self}

    method height->Number is public{-1}

    method depth->Number is public{0}

    method isFull->Boolean is public{true}

    method isEmpty->Boolean is public{true}

    method isComplete->Boolean is public{true}

    method isBalanced->Boolean is public{true}

    method isLeftChild->Boolean is public{false}

    method isRightChild->Boolean is public{false}

    method getValue->Dynamic is public{missing}

    method setValue(_)->Void is public{}

    method treeString->String is public{""}

    method asString->String is public{""}

    method inorderIterator->Iterator is public{EmptyIterator}

    method postorderIterator->Iterator is public{EmptyIterator}

    method preorderIterator->Iterator is public{EmptyIterator}
}

//Constructs empty tree
method new->BinaryTree is public{EmptyTree}

//Constructs tree with calue val and no children
method withValue(val)->BinaryTree is public{
    BinaryTreeClass.new(val, EmptyTree, EmptyTree)}

//Constructs tree with value val and left and right children lt and rt, respectively
method withValue(val)Left(lt:BinaryTree)Right(rt:BinaryTree)->BinaryTree is public{
    var newBT:BinaryTree := BinaryTreeClass.new(val, lt, rt)
    newBT.setLeft(lt)
    newBT.setRight(rt)
    return newBT}

// if generic types ever work for classes, value will be of type T,
// methods that return Dynamic should return T
class BinaryTreeClass.new(value, left:BinaryTree, right:BinaryTree){

    // Value associated with this node
    var val:Dynamic is readable := value

    // Parent of this node; initially empty
    var parent:BinaryTree is readable:= EmptyTree

    // @post @return true if other has same value and subtrees
    // as this tree
    method ==(other:BinaryTree)->Boolean is public{
         if(other.isEmpty) then {false}
         else{(val == other.getValue) && 
             (right == other.getRight) && (left == other.getLeft)}
    }

    // @post @return reference to (possibly empty) left subtree
    method getLeft->BinaryTree is public{left}

    // @post @return reference to (possibly empty) right subtree
    method getRight->BinaryTree is public{right}

    // @post @return reference to (possibly empty) parent node
    method getParent->BinaryTree is public{parent}

    // @post sets left subtree to newLeft, re-parents newLeft if
    // not empty
    // @param newLeft the root of the new left subtree
    method setLeft(newLeft:BinaryTree)->Void is public{
        if (!left.isEmpty && (left.getParent == self)) then{
            left.setParent(EmptyTree)}
        left := newLeft
        left.setParent(self)}

    // @post sets right subtree to newRight, re-parents newRight
    // if not empty
    // @param newRight the root of the new right subtree
    method setRight(newRight:BinaryTree)->Void is public{
        if(!right.isEmpty && (right.getParent == self)) then{
            right.setParent(EmptyTree)}
        right := newRight
        right.setParent(self)}

    // @post re-parents this node to parent reference or EmptyTree
    // @param newParent a reference to new parent of this node
    method setParent(newParent:BinaryTree)->Void is public{
        parent := newParent}

    // @post @return number of descendants of node
    method size->Number is public{left.size + right.size + 1}

    // @post @return reference to root of this node
    method root->BinaryTree is public{
        if(parent.isEmpty) then{self}
        else{parent.root}
    }

    // @post @return height of node in tree (maximum path length to
    // descendant)
    method height->Number is public{
        if(left.height > right.height) then {1 + left.height}
        else{1 + right.height}
    }

    // @post @return path length from node to root of tree
    method depth->Number is public{
        if(getParent.isEmpty) then{0}
        else{1 + getParent.depth}
    }

    // @post @return true iff tree is full (adding a node would 
    // necessarily increase its height)
    method isFull->Boolean is public{
        if(left.height != right.height) then {return false}
        left.isFull && right.isFull}

    // @post @return true iff tree rooted at node is complete (has
    // minimal height and any holes appear in last level to right)
    method isEmpty->Boolean is public{false}
    method isComplete->Boolean is public{
        var leftHeight:Number := left.height
        var rightHeight:Number := right.height
        var leftIsFull:Boolean := left.isFull
        var rightIsFull:Boolean := right.isFull
        var leftIsComplete:Boolean := left.isComplete
        var rightIsComplete:Boolean := right.isComplete
        if(leftIsFull && rightIsComplete &&
            (leftHeight == rightHeight)) then{return true}
        if(leftIsComplete && rightIsFull &&
            (leftHeight == (rightHeight + 1))) then{return true}        
        return false}

    // @post @return true iff tree is height balanced (at every node
    // the difference in heights of subtrees is no greater than one)
    method isBalanced->Boolean is public{
        var abs:Number := 
            if(left.height > right.height) then {left.height - right.height}
            else{right.height - left.height}
        return (abs <= 1) && left.isBalanced && right.isBalanced}

    // @pre node has a left subtree
    // @post rotates local portion of tree so left child is root
    method rotateRight->Void is confidential{
        var theParent:BinaryTree := getParent
        var newRoot:BinaryTree := getLeft
        var wasChild:Boolean := !theParent.isEmpty
        var wasLeftChild:Boolean := isLeftChild
        setLeft(newRoot.getRight)
        newRoot.setRight(self)
        if(wasChild) then {
            if(wasLeftChild) then{theParent.setLeft(newRoot)}
            else{theParent.setRight(newRoot)}
        }
    }
   
    // @pre node has a right subtree
    // @post rotates local portion of tree so right child is root
    method rotateLeft->Void is confidential{
        var theParent:BinaryTree := getParent
        var newRoot:BinaryTree := getRight
        var wasChild:Boolean := !parent.isEmpty
        var wasRightChild:Boolean := isRightChild
        setRight(newRoot.getLeft)
        newRoot.setLeft(self)
        if(wasChild) then{
            if(wasRightChild) then{parent.setRight(newRoot)}
            else{parent.setLeft(newRoot)}
        }
    }

    // @post @return true iff node is left child of parent
    method isLeftChild->Boolean is public{
        if(parent.isEmpty) then {false}
        else{self == parent.getLeft}
    }

    // @post @return true iff node is right child of parent
    method isRightChild->Boolean is public{
        if(parent.isEmpty) then {false}
        else{self == parent.getRight}
    }

    // @post @return value associated w/ node
    method getValue->Dynamic is public{val}

    // @post sets value associated w/node
    // @param newValue the new value of node
    method setValue(newValue:Dynamic)->Void is public{val := newValue}

    // @post @return string (graphically) representing tree rooted at node
    method treeString->String is public{
        var s:String := ""
        for(1..self.depth) do {i->
            s := s ++ "\t|"}
        s := s ++ "<{val} : {getHand}>\n"
        if(!left.isEmpty) then {s := s ++ left.treeString}
        if(!right.isEmpty) then {s := s++ right.treeString}
        return s}

    // @post @return R if node is right child, L if node is left child,
    // Root is node is root
    method getHand->String is private{
        if(isRightChild) then {return "R"}
        if(isLeftChild) then {return "L"}
        return "Root"}

    // @post @return string representing this subtree
    method asString->String is public{
        var s:String := ""
        return s}

    // @post @return iterator to traverse elements of tree in-order
    method inorderIterator->Iterator is public{
        var iter:Iterator := InorderIterator.new(root)
        iter.reset
        return iter}

    // @post @return iterator to traverse elements of tree in post-order
    method postorderIterator->Iterator{
        var iter:Iterator := PostorderIterator.new(root)
        iter.reset
        return iter}

    // @post @return iterator to traverse elements of tree in pre-order
    method preorderIterator->Iterator is public{
        var iter:Iterator := PreorderIterator.new(root)
        iter.reset
        return iter}
}

class InorderIterator.new(rt:BinaryTree){

    var todo:Stack is readable := structures_lib.newStack

    var root:BinaryTree is readable := rt

    method reset->Void is public{
        todo.clear
        var current:BinaryTree := root
        while{!current.isEmpty} do{
            todo.push(current)
            current := current.getLeft}
    }

    method hasNext->Boolean is public{!todo.isEmpty}

    method get->Dynamic is public{todo.peek.getValue}

    method next->Dynamic is public{
        var old:BinaryTree := todo.pop
        var result:Dynamic := old.getValue
        if(!old.getRight.isEmpty) then {
            var current:BinaryTree := old.getRight
            todo.push(current)
            current := current.getLeft
            while{!current.isEmpty} do {
                todo.push(current)
                current := current.getLeft}
        }
        return result}
}

class PostorderIterator.new(rt:BinaryTree){

    var todo:Stack is readable := structures_lib.newStack

    var root:BinaryTree is readable := rt

    method reset->Void is public{
        todo.clear
        var current:BinaryTree := root
        while{!current.isEmpty} do {
            todo.push(current)
            if(!current.getLeft.isEmpty) then{
                current := current.getLeft}
            else{current := current.getRight}
        }
    }

    method hasNext->Boolean is public{!todo.isEmpty}

    method get->Dynamic is public{todo.peek.getValue}

    method next->Dynamic is public{
        var current:BinaryTree := todo.pop
        var result:Dynamic := current.getValue
        if(!todo.isEmpty) then{
            var parent:BinaryTree := todo.peek
            if(current == parent.getLeft) then{
                current := parent.getRight
                while{!current.isEmpty} do{
                    todo.push(current)
                    if(!current.getLeft.isEmpty) then{
                        current := current.getLeft}
                    else{current := current.getRight}
                }
            }
        }
        return result}
}

class PreorderIterator.new(rt:BinaryTree){

    var todo:Stack is readable := structures_lib.newStack

    var root:BinaryTree is readable := rt

    method reset->Void is public{
        todo.clear
        if(!root.isEmpty) then {todo.push(root)}
    }

    method hasNext->Boolean is public{!todo.isEmpty}

    method get->Dynamic is public{todo.peek.getValue}

    method next->Dynamic is public{
        var old:BinaryTree := todo.pop
        var result:Dynamic := old.getValue
        if(!old.getRight.isEmpty) then{todo.push(old.getRight)}
        if(!old.getLeft.isEmpty) then{todo.push(old.getLeft)}
        return result}
}
 
// only to be used for Empty Tree, since needs iterator method
// to conform to Binary Tree type      
def EmptyIterator:Iterator is public, readable = object{

    method reset->Void is public{}

    method get->Dynamic is public{missing}

    method next->Dynamic is public{missing}

    method hasNext->Boolean is public{false}
}