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, fRoot, fLeft, b) = b;
 *
 * non-empty case: 
 *   InOder(tree, fRight, fRoot, fLeft, b) = 
 *     fRight(InOrder3(tree.right, fRight, fRoot, fLeft, b),
 *            fRoot(tree, 
 *                  fLeft(InOrder3(tree.left, fRight, fRoot, fLeft, b), b),
 *                  b),
 *            b);
 *
 * @author DXN
 * @author SBW
 * @author Mathias Ricken - Copyright 2008 - All rights reserved.
 * @since 09/22/2004
 */

public class InOrder3<T,P> implements IVisitor<T,P,P> {
    // binary function: <value from recursion to left>, b[0]
    private ILambda2<P,P,P> _fLeft;

    // ternary function: <value from _fLeft>, tree, b[0]
    private ILambda3<P,P,BiTree<T>,P> _fRoot;
    
    // ternary function: <value from _fRoot>, <value from recursion to right>, b[0]
    private ILambda3<P,P,P,P> _fRight;  
    
    public InOrder3(ILambda3<P,P,P,P> fRight, ILambda3<P,P,BiTree<T>,P> fRoot, ILambda2<P,P,P> fLeft) {
        _fRight = fRight;
        _fLeft = fLeft;
        _fRoot = fRoot;
    }
    
    public P emptyCase(BiTree<T> host, P... b) {
        return b[0]; 
    }
    
    public P nonEmptyCase(BiTree<T> host, P... b) {
        return _fRight.apply(_fRoot.apply(_fLeft.apply(host.getLeftSubTree().execute(this, b), 
                                                       b[0]),
                                          host,
                                          b[0]),
                             host.getRightSubTree().execute(this, b),
                             b[0]);
    }
    
    public static void main(String[] nu) {
        
        ILambda2<Integer,Integer,Integer> passThruInt =
            new ILambda2<Integer,Integer,Integer>() {
            public Integer apply(Integer arg1, Integer ignored) {
                return arg1;
            }
        };
        
        ILambda3<Integer,Integer,BiTree<Integer>,Integer> addToRoot =
            new ILambda3<Integer,Integer,BiTree<Integer>,Integer>() {
            public Integer apply(Integer arg1, BiTree<Integer> arg2, Integer ignored) {
                return arg1+arg2.getRootDat();
            }
        };
        
       ILambda3<Integer,Integer,Integer,Integer> addToRight =
            new ILambda3<Integer,Integer,Integer,Integer>() {
            public Integer apply(Integer arg1, Integer arg2, Integer ignored) {
                return arg1+arg2;
            }
        };
         
        // Add the numbers in the tree in in-order fashion:
        InOrder3<Integer,Integer> inOrderAdd =
            new InOrder3<Integer,Integer>(addToRight, addToRoot, passThruInt);
        
        ILambda2<String,String,String> passThruStr =
            new ILambda2<String,String,String>() {
            public String apply(String arg1, String ignored) {
                return arg1;
            }
        };

        final ILambda3<String,String,String,String> concat =
            new ILambda3<String,String,String,String>() {
            public String apply(String arg1, String arg2, String ignored) {
                if ("" != arg1.toString()) {
                    if ("" != arg2.toString()) {
                        return arg1.toString() + " " + arg2.toString();
                    }
                    else {
                        return arg1.toString();
                    }
                }
                else {
                    return arg2.toString();
                }
            }
        };
        
        ILambda3<String,String,BiTree<Integer>,String> concatToRoot =
            new ILambda3<String,String,BiTree<Integer>,String>() {
            public String apply(String arg1, BiTree<Integer> arg2, String ignored) {
                System.err.println(arg2.getRootDat());
                return concat.apply(arg1, arg2.getRootDat().toString(), ignored);  
            }
        };
        
        
        // Concatenate the String representation of the elements in the tree 
        
        // in in-order fashion:
        
        InOrder3<Integer,String> inOrderConcat = new InOrder3<Integer,String>(concat, concatToRoot, passThruStr);
        
        BiTree<Integer> bt = new BiTree<Integer>();
        System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
        System.out.println("In order concat \n" + bt.execute(inOrderConcat, "")); 
        System.out.println("==============================");
        
        bt.insertRoot(5);
        System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
        System.out.println("In order concat \n" + bt.execute(inOrderConcat, ""));  
        System.out.println("==============================");
        
        bt.getLeftSubTree().insertRoot(-2);
        System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
        System.out.println("In order concat \n" + bt.execute(inOrderConcat, ""));    
        System.out.println("==============================");
        
        bt.getRightSubTree().insertRoot(10);
        System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
        System.out.println("In order concat \n" + bt.execute(inOrderConcat, "")); 
        System.out.println("==============================");
        
        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, ""));                
    }
}