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