package brs.visitor;
import brs.*;
import fp.*;

/**
 * Traverse a binary tree in order:
 * For an empty tree:
 * do the appropriate processing.
 * For a non-empty tree:
 * Traverse the left subtree in order;
 * Process the root;
 * Traverse the right subtree in order;
 * 
 * Uses 3 lambdas as variants.
 * Let fRight, fLeft, fRoot be ILambda and b be some input object.
 * empty case: 
 *   InOrder3(empty, fRight, fLeft, fRoot, b) = b;
 * non-empty case: 
 *   InOder(tree, fRight, fLeft, fRoot, b) = 
 *     fRight(fLeft(InOrder3(tree.left, fRight, fLeft, fRoot, b), fRoot(tree)), 
 *            InOrder3(tree.right, fRight, fLeft, fRoot, b));
 * @author DXN
 * @author SBW
 * @since 09/20/2004
 */
public class InOrder3 implements IVisitor {
    // an abstract function on non-empty BiTrees only:
    private ILambda _fRoot;
    
    // an abstract function with domain (range of InOrder3, range of _fRoot):
    private ILambda _fLeft; 
    
    // an abstract function with domain (range of _fLeft, range of InOrder3):
    private ILambda _fRight;
    
    public InOrder3(ILambda fRight, ILambda fLeft, ILambda fRoot) {
        _fRight = fRight;
        _fLeft = fLeft;
        _fRoot = fRoot;
    }
    
    public Object emptyCase(BiTree host, Object b) {
        return b; 
    }

    public Object nonEmptyCase(BiTree host, Object b) {
        return _fRight.apply(_fLeft.apply(host.getLeftSubTree().execute(this, b), 
                                          _fRoot.apply(host)), 
                             host.getRightSubTree().execute(this, b));
    }
    
    public static void main(String[] nu) {
        ILambda getRoot = new ILambda() {
            public Object apply(Object ... params) {
                // assume params[0] is a non-empty BiTree:
                return ((BiTree)params[0]).getRootDat();  
            }
        };
        ILambda add = Add.Singleton;
        // Add the numbers in the tree in in-order fashion:
        IVisitor inOrderAdd = new InOrder3(add, add, getRoot);
        
        ILambda concat = new ILambda() {
            public Object apply(Object ... params) {
                if ("" != params[0].toString()) {
                    if ("" != params[1].toString()) {
                        return params[0].toString() + " " + params[1].toString();
                    }
                    else {
                        return params[0].toString();
                    }
                }
                else {
                    return params[1].toString();
                }
            }
        };
        // Concatenate the String representation of the elements in the tree 
        // in in-order fashion:
        IVisitor inOrderConcat = new InOrder3(concat, concat, getRoot);
        
        BiTree bt = new BiTree();
        System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
        System.out.println("In order concat \n" + bt.execute(inOrderConcat, "")); 
        
        bt.insertRoot(5);
        System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
        System.out.println("In order concat \n" + bt.execute(inOrderConcat, ""));  
        
        bt.getLeftSubTree().insertRoot(-2);
        System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
        System.out.println("In order concat \n" + bt.execute(inOrderConcat, ""));    
        
        bt.getRightSubTree().insertRoot(10);
        System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
        System.out.println("In order concat \n" + bt.execute(inOrderConcat, "")); 
        
        bt.getRightSubTree().getLeftSubTree().insertRoot(-9);
        System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
        System.out.println("In order concat \n" + bt.execute(inOrderConcat, ""));                
    }
}