Lazy Evaluation for BinaryTree - HolmesJJ/OOP-FP GitHub Wiki

import java.lang.Comparable;
import java.util.List;
import java.util.ArrayList;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.function.Consumer;

/**
 * A "binary search tree" (BST) or "ordered binary tree" is a type
 * of binary tree where the nodes are arranged in order.
 */
public class BinaryTree<T extends Comparable<T>> {

    private final T value; // Node value
    private final Supplier<BinaryTree<T>> leftTree;
    private final Supplier<BinaryTree<T>> rightTree;
    private final boolean amIEmpty;

    /**
     * Use Supplier to freeze left and right subtrees.
     */
    public BinaryTree(T value, Supplier<BinaryTree<T>> left, Supplier<BinaryTree<T>> right) {
        this.value = value;
        this.leftTree = left;
        this.rightTree = right;
        this.amIEmpty = false;
    }

    /**
     * Private constructor of an empty list.
     */
    private BinaryTree() {
        this.value = null;
        this.leftTree = null;
        this.rightTree = null;
        this.amIEmpty = true;
    }

    /**
     * Create an empty LazyList.
     */
    public static <T extends Comparable<T>> BinaryTree<T> makeEmpty() {
        return new BinaryTree<T>();
    }

    /**
     * Return true if this BinaryTree is empty, false otherwise.
     */
    public boolean isEmpty() {
        return this.amIEmpty;
    }

    /**
     * Convert List to BinaryTree.
     */
    public static <T extends Comparable<T>> BinaryTree<T> fromList(List<T> list) {
        BinaryTree<T> result = BinaryTree.makeEmpty();
        for (T item : list) {
            result = result.add(item);
        }
        return result;
    }

    /**
     * Return node value.
     */
    public T value() {
        if (this.isEmpty())
            throw new IllegalArgumentException("value: empty tree!"); 
        return this.value;
    }

    /**
     * Return left Binary Tree.
     */
    public BinaryTree<T> leftTree() {
        if (this.isEmpty())
            throw new IllegalArgumentException("leftTree: empty tree!");
        return this.leftTree.get();
    }

    /**
     * Return right Binary Tree.
     */
    public BinaryTree<T> rightTree() {
        if (this.isEmpty())
            throw new IllegalArgumentException("rightTree: empty tree!");
        return this.rightTree.get();
    }

    /**
     * Return current node value.
     */
    @Override
    public String toString() {
        if (this.isEmpty()) {
            return "empty";
        } else {
            return this.value.toString() + ", <left>, <right>";
        }
    }

    /**
     * Add value to tree.
     */
    public BinaryTree<T> add(T thing) {
        if (this.isEmpty()) {
            return new BinaryTree<>(thing,
                    BinaryTree::makeEmpty,
                    BinaryTree::makeEmpty);
        }
        int compareResult = this.value().compareTo(thing);
        // already in tree
        if (compareResult == 0) {
            return this;
        }
        // add to left tree
        else if (compareResult > 0) {
            return new BinaryTree<>(this.value(),
                    ()-> this.leftTree().add(thing),
                    this::rightTree);
        }
        // add to right tree
        else {
            return new BinaryTree<>(this.value(),
                    this::leftTree,
                    ()-> this.rightTree().add(thing));
        }
    }

    /**
     * Lazy Evaluation
     * Return true if this tree contains item, false otherwise.
     */
    public Lazy<Boolean> contains(T searchItem) {
        return new Lazy<Boolean>(()-> this.eagerContains(searchItem));
    }

    /**
     * Eager Evaluation
     * Return true if this tree contains item, false otherwise.
     */
    public boolean eagerContains(T thing) {
        if (this.isEmpty()) {
            return false;
        }
        int compareResult = this.value().compareTo(thing);
        if (compareResult == 0) {
            return true;
        }
        // Find value from left tree
        else if (compareResult > 0) {
            return this.leftTree().eagerContains(thing);
        }
        // Find value from right tree
        else {
            return this.rightTree().eagerContains(thing);
        }
    }

    /**
     * Restore the BinaryTree after mapping
     */
    public <U extends Comparable<U>> BinaryTree<U> map(Function<T,U> f) {
        return this.mapHelper(f).restore();
    }

    /**
     * Map all the elements in the BinaryTree
     */
    private <U extends Comparable<U>> BinaryTree<U> mapHelper(Function<T,U> f) {
        if (this.isEmpty()) {
            return BinaryTree.makeEmpty();
        } else {
            return new BinaryTree<>(f.apply(this.value()),
                    ()-> this.leftTree().mapHelper(f),
                    ()-> this.rightTree().mapHelper(f));
        }
    }

    /**
     * Traverse the whole BinaryTree and add all the elements to List,
     * then create a new BinaryTree with the List.
     */
    private BinaryTree<T> restore() {
        List<T> list = new ArrayList<>();
        this.preOrder(list::add);
        return BinaryTree.fromList(list);
    }

    /**
     * Lazy Evaluation
     * Return the max value.
     */
    public Lazy<T> max() {
        return new Lazy<>(this::eagerMax);
    }

    /**
     * Eager Evaluation
     * Return the max value.
     */
    private T eagerMax() {
        if (this.isEmpty()) {
            return null;
        } else if (this.rightTree().isEmpty()) {
            return this.value();
        } else {
            return this.rightTree().eagerMax();
        }
    }

    /**
     * Algorithm Preorder
     * 1. Visit the root.
     * 2. Traverse the left subtree, i.e., call Preorder(left-subtree)
     * 3. Traverse the right subtree, i.e., call Preorder(right-subtree)
     */
    public void preOrder(Consumer<T> action) {
        if (!this.isEmpty()) {
            action.accept(this.value());
            this.leftTree().preOrder(action);
            this.rightTree().preOrder(action);
        }
    }
}

import java.util.function.Supplier;

/**
 * A Lazy way to get value.
 */

public class Lazy<T> {

    private final Supplier<T> value;

    public Lazy(Supplier<T> v) {
        this.value = v;
    }

    public T get() {
        return this.value.get();
    }
}