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 two lambdas as variants.
 * Let fRight, fLeft be ILambda and b be some input object.
 * empty case: 
 *   InOrder2(empty, fRight, fLeft, b) = b;
 * non-empty case: 
 *   InOder(tree, fRight, fLeft, b) = 
 *     fRight(fLeft(InOrder2(tree.left, fRight, fLeft, b), tree)), 
 *            InOrder2(tree.right, fRight, fLeft, b));
 * @author DXN
 * @author SBW
 * @since 09/22/2004
 */
public class InOrder2 implements IVisitor {
    // an abstract function with domain (range of InOrder2, BiTree):
    private ILambda _fLeft;
    
    // an abstract function with domain (range of _fLeft, range of InOrder2):
    private ILambda _fRight;
    
    public InOrder2(ILambda fRight, ILambda fLeft) {
        _fRight = fRight;
        _fLeft = fLeft;
    }
    
    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), host), 
                             host.getRightSubTree().execute(this, b));
    }
    
    public static void main(String[] nu) {
        final ILambda add = Add.Singleton;
        ILambda add2 = new ILambda() {
            public Object apply(Object ... params) {
                return add.apply(params[0], ((BiTree)params[1]).getRootDat());
            }
        };
        // Add the numbers in the tree in in-order fashion:
        IVisitor inOrderAdd = new InOrder2(add, add2);
        
        final 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();
                }
            }
        };
        ILambda concat2 = new ILambda() {
            public Object apply(Object ... params) {
                return concat.apply(params[0], ((BiTree)params[1]).getRootDat());
            }
        };
        // Concatenate the String representation of the elements in the tree 
        // in in-order fashion:
        IVisitor inOrderConcat = new InOrder2(concat, concat2);
        
        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, ""));                
    }
}