package brs.visitor;

import brs.*;
import lrs.*;

/**
 * This visitor returns an LRStruct that contains all the leaves of
 * the BiTree. The nodes that are leaves in the BiTree are then removed
 * from the BiTree.
 **/
/*
tree=
1
|_ 2
|  |_ 3
|  |  |_ []
|  |  |_ []
|  |_ 4
|     |_ []
|     |_ []
|_ 5
   |_ 6
   |  |_ []
   |  |_ []
   |_ []
trim --> (3 4 6)

tree=
1
|_ 2
|  |_ []
|  |_ []
|_ 5
   |_ []
   |_ []
trim --> (2 5)

tree=
1
|_ []
|_ []
trim --> (1)

tree=
[]

trim --> ()

tree=
[]
*/
public class BRSTrim implements IVisitor {
    public static final BRSTrim Singleton = new BRSTrim();
    private BRSTrim() {}
    
    // STUDENT TO COMPLETE
    public Object emptyCase(BiTree host, Object... nu) {
        return new LRStruct();
    }
    
    public Object nonEmptyCase(BiTree outerHost, Object... nu) {
        return outerHost.execute(new IVisitor() {
            public Object emptyCase(BiTree host, Object... inp) {
                return inp[0];
            }
            public Object nonEmptyCase(final BiTree host, final Object... inp) {
                return host.getLeftSubTree().execute(new IVisitor() {
                    public Object emptyCase(BiTree h, Object... nu) {
                        // left is empty
                        return host.getRightSubTree().execute(new IVisitor() {
                            public Object emptyCase(BiTree h, Object... nu) {
                                // right is empty ==> this is a leaf
                                LRStruct l = (LRStruct)inp[0];
                                Object o = host.remRoot();
                                l.insertFront(o);
                                return l;
                            }
                            public Object nonEmptyCase(BiTree h, Object... nu) {
                                return interiorNodeCase(host, inp);
                            }
                        });
                    }
                    public Object nonEmptyCase(BiTree h, Object... nu) {
                        return interiorNodeCase(host, inp);
                    }
                });
            }
            Object interiorNodeCase(BiTree host, Object... inp) {
                // not a leaf
                return host.getLeftSubTree().execute(this,
                                                     host.getRightSubTree().execute(this, inp));
            }
        }, new LRStruct());
    }    
}

