package lrs.visitor;

import lrs.*;
import brs.*;

/**
 * Builds a full BST from a sorted list.
 * @Copyright: Copyright (c) 2003 D.X. Nguyen - All rights reserved
 * @author D. X. Nguyen
 * @version 1.0
 */
public class BuildFullTree implements IAlgo {
    public static final BuildFullTree Singleton = new BuildFullTree();

    private  BuildFullTree() {
    }

    /**
     * What's a full BST that is built from an empty list?
     * @param host
     * @param inp
     * @return BiTree
     */
    public Object emptyCase(LRStruct host, Object inp) {
        return new BiTree();
    }

    /**
     * Splits the list in half and recursively builds the right subtree from
     * the right half and the left subtree from the left half.
     * @param host
     * @param inp
     * @return BiTree
     */
    public Object nonEmptyCase(LRStruct host, Object inp) {
        LRStruct rightHalf = (LRStruct)host.execute(Splitter.Singleton, null);
        BiTree result = new BiTree();
        result.insertRoot(rightHalf.getFirst());
        result.setRightSubTree((BiTree)rightHalf.getRest().execute(this, null));
        result.setLeftSubTree((BiTree)host.execute(this,null));
        return result;
    }

    /**
     * "Quick and dirty" test.
     * @param notUsed
     */
    public static void main(String[] notUsed) {
        LRStruct L = new LRStruct();
        L.insertFront(new Integer(8));
        L.insertFront(new Integer(7));
        L.insertFront(new Integer(6));
        L.insertFront(new Integer(5));
        L.insertFront(new Integer(4));
        L.insertFront(new Integer(3));
        L.insertFront(new Integer(2));
        L.insertFront(new Integer(1));
        System.out.println(L);
        System.out.println(L.execute(BuildFullTree.Singleton, null));
    }
}