001 package brs.visitor;
002
003 import brs.*;
004 import fp.*;
005
006 /**
007 * Traverse a binary tree in order:
008 * For an empty tree:
009 * do the appropriate processing.
010 * For a non-empty tree:
011 * Traverse the left subtree in order;
012 * Process the root;
013 * Traverse the right subtree in order;
014 *
015 * Uses two lambdas as variants.
016 * Let fRight, fLeft be ILambda and b be some input object.
017 * empty case:
018 * InOrder2(empty, fRight, fLeft, b) = b;
019 * non-empty case:
020 * InOder(tree, fRight, fLeft, b) =
021 * fRight(fLeft(InOrder2(tree.left, fRight, fLeft, b), tree)),
022 * InOrder2(tree.right, fRight, fLeft, b));
023 * @author DXN
024 * @author SBW
025 * @author Mathias Ricken - Copyright 2008 - All rights reserved.
026 * @since 09/22/2004
027 */
028 public class InOrder2<T,P> implements IVisitor<T,P,P> {
029 // an abstract function with domain (range of InOrder2, BiTree):
030 private ILambda2<P,P,BiTree<T>> _fLeft;
031
032 // an abstract function with domain (range of _fLeft, range of InOrder2):
033 private ILambda2<P,P,P> _fRight;
034
035
036 public InOrder2(ILambda2<P,P,P> fRight, ILambda2<P,P,BiTree<T>> fLeft) {
037 _fRight = fRight;
038 _fLeft = fLeft;
039 }
040
041
042 public P emptyCase(BiTree<T> host, P... b) {
043 return b[0];
044 }
045
046 public P nonEmptyCase(BiTree<T> host, P... b) {
047 return _fRight.apply(_fLeft.apply(host.getLeftSubTree().execute(this, b), host),
048 host.getRightSubTree().execute(this, b));
049 }
050
051
052 public static void main(String[] nu) {
053 final ILambda2<Integer,Integer,Integer> add =
054 new ILambda2<Integer,Integer,Integer>() {
055 public Integer apply(Integer arg1, Integer arg2) {
056 return arg1+arg2;
057 }
058 };
059
060 ILambda2<Integer,Integer,BiTree<Integer>> add2 =
061 new ILambda2<Integer,Integer,BiTree<Integer>>() {
062 public Integer apply(Integer arg1, BiTree<Integer> arg2) {
063 return add.apply(arg1,arg2.getRootDat());
064 }
065 };
066
067 // Add the numbers in the tree in in-order fashion:
068 InOrder2<Integer,Integer> inOrderAdd = new InOrder2<Integer,Integer>(add, add2);
069
070
071 final ILambda2<String,String,String> concat = new ILambda2<String,String,String>() {
072 public String apply(String arg1, String arg2) {
073 if ("" != arg1.toString()) {
074 if ("" != arg2.toString()) {
075 return arg1.toString() + " " + arg2.toString();
076 }
077 else {
078 return arg1.toString();
079 }
080 }
081 else {
082 return arg2.toString();
083 }
084 }
085 };
086 ILambda2<String,String,BiTree<Integer>> concat2 = new ILambda2<String,String,BiTree<Integer>>() {
087 public String apply(String arg1, BiTree<Integer> arg2) {
088 return concat.apply(arg1, arg2.getRootDat().toString());
089 }
090 };
091 // Concatenate the String representation of the elements in the tree
092 // in in-order fashion:
093 InOrder2<Integer,String> inOrderConcat = new InOrder2<Integer,String>(concat, concat2);
094
095
096 BiTree<Integer> bt = new BiTree<Integer>();
097 System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
098 System.out.println("In order concat \n" + bt.execute(inOrderConcat, ""));
099
100
101 bt.insertRoot(5);
102 System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
103 System.out.println("In order concat \n" + bt.execute(inOrderConcat, ""));
104
105
106 bt.getLeftSubTree().insertRoot(-2);
107 System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
108 System.out.println("In order concat \n" + bt.execute(inOrderConcat, ""));
109
110
111 bt.getRightSubTree().insertRoot(10);
112 System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
113 System.out.println("In order concat \n" + bt.execute(inOrderConcat, ""));
114
115
116 bt.getRightSubTree().getLeftSubTree().insertRoot(-9);
117 System.out.println(bt + "\nAdd \n" + bt.execute(inOrderAdd, 0));
118 System.out.println("In order concat \n" + bt.execute(inOrderConcat, ""));
119 }
120 }