// Program to test solutions to problem #8 on the cse143 final, winter 2022.
// Fill in your solution to add, then compile and run the program

import java.util.*;

class IntTree {
    public void add(IntTree other) {
        // fill in your solution here and include any private methods below
        // you can rename the parameter
    }
    
    private IntTreeNode overallRoot;

    // this is the sample solution
    public void add2(IntTree other) {
        overallRoot = add2(overallRoot, other.overallRoot);
    }
    
    private IntTreeNode add2(IntTreeNode root1, IntTreeNode root2) {
        if (root2 != null) {
            if (root1 == null) {
                root1 = new IntTreeNode(0, null, null);
            }
            root1.data += root2.data;
            root1.left = add2(root1.left, root2.left);
            root1.right = add2(root1.right, root2.right);
        }
        return root1;
    }

    // post: constructs an empty tree
    public IntTree() {
        overallRoot = null;
    }

    // pre : the tree satisfies the binary search tree property
    // post: value is added so as to preserve the binary search tree property
    public void add(int value) {
        overallRoot = add(overallRoot, value);
    }

    // pre : the tree with given root satisfies the binary search tree property
    // post: value is added so as to preserve the binary search tree property
    private IntTreeNode add(IntTreeNode root, int value) {
        if (root == null) {
            root = new IntTreeNode(value, null, null);
        } else if (value <= root.data) {
            root.left = add(root.left, value);
        } else {
            root.right = add(root.right, value);
        }
        return root;
    }

    // post: prints the data fields of the tree, one per line, following
    //       an inorder traversal and using indentation to indicate node depth;
    //       prints right to left so that it looks correct when the output is
    //       rotated.
    public void printStructure() {
        printStructure(overallRoot, 0);
    }

    // post: prints in preorder the data fields of the given tree indenting
    //       each line to the given level
    private void printStructure(IntTreeNode root, int level) {
        if (root != null) {
            printStructure(root.right, level + 1);
            for (int i = 0; i < level; i++) {
                System.out.print("    ");
            }
            System.out.println(root.data);
            printStructure(root.left, level + 1);
        }
    }

    // returns true if this tree equals other tree
    public boolean equals(IntTree other) {
        return equals(overallRoot, other.overallRoot);
    }

    private boolean equals(IntTreeNode root1, IntTreeNode root2) {
        if (root1 == null || root2 == null) {
            return root1 == null && root2 == null;
        } else {
            return root1.data == root2.data
                && equals(root1.left, root2.left)
                && equals(root1.right, root2.right);
        }
    }

    public boolean distinctFrom(IntTree other) {
        Set<IntTreeNode> s1 = nodes(this);
        Set<IntTreeNode> s2 = nodes(other);
        int oldSize = s1.size();
        s1.removeAll(s2);
        return oldSize == s1.size();
    }

    private Set<IntTreeNode> nodes(IntTree t) {
        Set<IntTreeNode> s = new HashSet<IntTreeNode>();
        addNodes(s, t.overallRoot);
        return s;
    }

    private void addNodes(Set<IntTreeNode> s, IntTreeNode root) {
        if (root != null) {
            s.add(root);
            addNodes(s, root.left);
            addNodes(s, root.right);
        }
    }
}

public class FinalTest8 {
    public static void main(String[] args) {
        int fail = 0;
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                if (!test(i, j)) {
                    fail++;
                }
            }
        }
        if (fail > 0) {
            System.out.println("failed " + fail + " tests");
        } else {
            System.out.println("passed all tests");
        }
    }

    public static boolean test(int m, int n) {
        IntTree t1 = new IntTree();
        IntTree t2 = new IntTree();
        IntTree t3 = new IntTree();
        IntTree t4 = new IntTree();
        Random r = new Random();
        for (int i = 0; i < m; i++) {
            int next = r.nextInt(100);
            t1.add(next);
            t3.add(next);
        }
        for (int i = 0; i < n; i++) {
            int next = r.nextInt(100);
            t2.add(next);
            t4.add(next);
        }
        System.out.println("Testing with this t1:");
        t1.printStructure();
        System.out.println("and this t2:");
        t2.printStructure();
        int count1 = IntTreeNode.count;
        t1.add2(t2);
        count1 = IntTreeNode.count - count1;
        System.out.println("Expecting t1 to be this after t1.add(t2):");
        t1.printStructure();

        boolean fail = false;
        int count2 = IntTreeNode.count;
        try {
            t3.add(t4);
            count2 = IntTreeNode.count - count2;
        } catch (RuntimeException e) {
            System.out.println("    threw " + e);
            fail = true;
        }
        if (!fail && (!t1.equals(t3))) {
            System.out.println("their t1 result:");
            t3.printStructure();
            fail = true;
        }
        if (!fail && !(t2.equals(t4))) {
            System.out.println("t2 has been modified");
            fail = true;
        }
        if (!fail && count1 < count2) {
            System.out.println("correct but duplicate nodes were constructed");
            fail = true;
        }
        if (!fail && !t3.distinctFrom(t4)) {
            System.out.println("t1 and t2 have shared nodes");
            fail = true;
        }
        if (fail) {
            System.out.println("failed");
        } else {
            System.out.println("passed");
        }
        System.out.println("---------------------------------------------");
        return !fail;
    }
}

class IntTreeNode {
    public int data;       // data stored at this IntTreeNode
    public IntTreeNode left;  // reference to left subtree
    public IntTreeNode right; // reference to right subtree

    public static int count;

    // post: constructs a IntTreeNode with the given data and links
    public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
        this.data = data;
        this.left = left;
        this.right = right;
        count++;
    }
}