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