BTreeVsArrayTest.java

import static org.junit.Assert.*;

import java.util.Random;

import org.junit.*;

public class BTreeVsArrayTest {

    static int ROUND = 10;

    static int RANGE = ROUND * 100;

    @Test

    public void basicTest() {

        System.out.println("=============basicTest=================");

        Random r = new Random();

        int j = ROUND;

        for(int L = 2; L < j; L++) {

            int[] arr = new int[L];

            for(int i = 0; i < L-1; i++) {

                arr[i] = r.nextInt(RANGE);

            }

            System.out.println("round " + L);

            BTree root = tree(arr);

            int size = BTreeVsArray.count(root);

            System.out.println("starting tree " + size);

            BTreeVsArray.printInOrder(root);

            System.out.println();

            int[] fill = new int[size];

            int[] ordered = BTreeVsArray.treeToArrayInorder(root, fill, 0, size-1);

            assertTrue(BTreeVsArray.isInorder(ordered));

            printArray(ordered);

            System.out.println();

            testRunner(ordered);

        } 

    }

    

    @Test

    public void basicTestPreorder() {

        System.out.println("=============basicTestPreorder=================");

        Random r = new Random();

        int j = ROUND;

        for(int L = 2; L < j; L++) {

            int[] arr = new int[L];

            for(int i = 0; i < L-1; i++) {

                arr[i] = r.nextInt(RANGE);

            }

            System.out.println("round " + L);

            BTree root = tree(arr);

            int size = BTreeVsArray.count(root);

            System.out.println("starting tree " + size);

            int[] fill = new int[size];

            int[] preordered = BTreeVsArray.treeToArrayPreorder(root, fill, 0, size-1);

            assertTrue(BTreeVsArray.isPreorder(preordered, 0, preordered.length-1));

            printArray(preordered);

            System.out.println();

            testRunner3(preordered);

        } 

    }

    

    @Test

    public void testSpecial() {

        int[] arr = {612, 581, 341, 180, 136, 13, 0, 479};

        BTree root = tree(arr);

        int size = BTreeVsArray.count(root);

        System.out.println("starting tree " + size);

        int[] fill = new int[size];

        int[] preordered = BTreeVsArray.treeToArrayPreorder(root, fill, 0, size-1);

        assertTrue(BTreeVsArray.isPreorder(preordered, 0, preordered.length-1));

        System.out.println("xxxxxxxxleft lean linked listxxxxxxxxxx");

        printArray(preordered);

        System.out.println();

        testRunner3(preordered);

    }

    

    @Test

    public void testDegradeTree() {

        int[] arr = {949, 662, 396, 51, 0};

        BTree root = tree(arr);

        int size = BTreeVsArray.count(root);

        System.out.println("starting tree " + size);

        int[] fill = new int[size];

        int[] preordered = BTreeVsArray.treeToArrayPreorder(root, fill, 0, size-1);

        assertTrue(BTreeVsArray.isPreorder(preordered, 0, preordered.length-1));

        System.out.println("xxxxxxxxleft lean linked listxxxxxxxxxx");

        printArray(preordered);

        System.out.println();

        testRunner3(preordered);

        System.out.println("xxxxxxxxright lean linked listxxxxxxxxxx");

        int[] postordered = BTreeVsArray.treeToArrayPostorder(root, fill, 0, size-1);

        assertTrue(BTreeVsArray.isPostorder(postordered, 0, postordered.length-1));

        printArray(postordered);

        System.out.println();

        testRunner3(postordered);

    }

    

    @Test

    public void basicTestPostorder() {

        System.out.println("=============basicTestPostorder=================");

        Random r = new Random();

        int j = ROUND;

        for(int L = 2; L < j; L++) {

            int[] arr = new int[L];

            for(int i = 0; i < L-1; i++) {

                arr[i] = r.nextInt(RANGE);

            }

            System.out.println("round " + L);

            BTree root = tree(arr);

            int size = BTreeVsArray.count(root);

            System.out.println("starting tree " + size);

            int[] fill = new int[size];

            int[] postordered = BTreeVsArray.treeToArrayPostorder(root, fill, 0, size-1);

            printArray(postordered);

            System.out.println();

            assertTrue(BTreeVsArray.isPostorder(postordered, 0, postordered.length-1));

            testRunner4(postordered);

        } 

    }

    

    @Test

    public void edgeTest() {

        System.out.println("=============EDGETEST=================");

        int[] ordered2 = {1};

        testRunner(ordered2);

        int[] ordered1 = {};

        testRunner2(ordered1);

        

        System.out.println("in-order array: ");

        printArray(null);

        System.out.println();

        ordered1 = null;

        

        BTree root = BTreeVsArray.arrayToTree(null, 0, 0);

        BTreeVsArray.printInOrder(root);

        System.out.println();

        BTreeVsArray.printPreOrder(root);

        System.out.println();

        BTreeVsArray.printInOrder(root);

        System.out.println();

        BTreeVsArray.printPostOrder(root);

        System.out.println();

        assertFalse(BTreeVsArray.isInorder(ordered1));

        assertFalse(BTreeVsArray.inOrderCompare(root, ordered1));

        assertFalse(BTreeVsArray.inOrderCompare2(root, ordered1, 0, 0));

        

        int[] preordered = new int[BTreeVsArray.count(root)];

        preordered = BTreeVsArray.treeToArrayPreorder(root, preordered, 0, 0);

        System.out.println("pre-order array: ");

        printArray(preordered);

        System.out.println();

        int[] preordered1 = copyArray(preordered);

        

        BTree root1 = BTreeVsArray.arrayToTreePreOrder(preordered, 0, 0);

        BTreeVsArray.printPreOrder(root1);

        System.out.println();

        BTreeVsArray.printInOrder(root1);

        System.out.println();

        BTreeVsArray.printPostOrder(root1);

        System.out.println();

        

        assertFalse(BTreeVsArray.isPreorder(preordered1, 0, 0));

        assertFalse(BTreeVsArray.preOrderCompare(root1, preordered1, 0, 0));

        

        int[] postordered = new int[BTreeVsArray.count(root)];

        postordered = BTreeVsArray.treeToArrayPostorder(root, postordered, 0, 0);

        System.out.println("post-order array: ");

        printArray(postordered);

        System.out.println();

        int[] postordered1 = copyArray(postordered);

        

        BTree root2 = BTreeVsArray.arrayToTreePostOrder(postordered, 0, 0);

        BTreeVsArray.printPostOrder(root2);

        System.out.println();

        BTreeVsArray.printInOrder(root2);

        System.out.println();

        

        assertFalse(BTreeVsArray.isPostorder(postordered1, 0, 0));

        assertFalse(BTreeVsArray.postOrderCompare(root2, postordered1, 0, 0));

    }

    

    private void testRunner(int[] ordered) {

        System.out.println("in-order array: ");

        printArray(ordered);

        System.out.println();

        int[] ordered1 = copyArray(ordered);

        

        System.out.println("3 prints: ");

        BTree root = BTreeVsArray.arrayToTree(ordered, 0, ordered.length - 1);

        assertTrue(BTreeVsArray.isBinarySearchTree(root));

        

        BTreeVsArray.printPreOrder(root);

        System.out.println();

        BTreeVsArray.printInOrder(root);

        System.out.println();

        BTreeVsArray.printPostOrder(root);

        System.out.println();

        assertTrue(BTreeVsArray.isInorder(ordered1));

        assertTrue(BTreeVsArray.inOrderCompare(root, ordered1));

        assertTrue(BTreeVsArray.inOrderCompare2(root, ordered1, 0, ordered1.length - 1));

        

        int[] preordered = new int[BTreeVsArray.count(root)];

        preordered = BTreeVsArray.treeToArrayPreorder(root, preordered, 0, preordered.length-1);

        System.out.println("pre-order array: ");

        printArray(preordered);

        System.out.println();

        int[] preordered1 = copyArray(preordered);

        

        BTree root1 = BTreeVsArray.arrayToTreePreOrder(preordered, 0, preordered.length - 1);

        assertTrue(BTreeVsArray.isBinarySearchTree(root1));

        BTreeVsArray.printPreOrder(root1);

        System.out.println();

        BTreeVsArray.printInOrder(root1);

        System.out.println();

        BTreeVsArray.printPostOrder(root1);

        System.out.println();

        

        assertTrue(BTreeVsArray.isPreorder(preordered1, 0, preordered1.length - 1));

        assertTrue(BTreeVsArray.preOrderCompare(root1, preordered1, 0, preordered1.length - 1));

        

        int[] postordered = new int[BTreeVsArray.count(root)];

        postordered = BTreeVsArray.treeToArrayPostorder(root, postordered, 0, postordered.length-1);

        System.out.println("post-order array: ");

        printArray(postordered);

        System.out.println();

        int[] postordered1 = copyArray(postordered);

        

        BTree root2 = BTreeVsArray.arrayToTreePostOrder(postordered, 0, postordered.length - 1);

        assertTrue(BTreeVsArray.isBinarySearchTree(root2));

        BTreeVsArray.printPreOrder(root2);

        System.out.println();

        BTreeVsArray.printInOrder(root2);

        System.out.println();

        BTreeVsArray.printPostOrder(root2);

        System.out.println();

        

        assertTrue(BTreeVsArray.isPostorder(postordered1, 0, postordered1.length - 1));

        assertTrue(BTreeVsArray.postOrderCompare(root2, postordered1, 0, postordered1.length - 1));

    }

    

    private void testRunner2(int[] ordered) {

        System.out.println("3 arrays: ");

        int[] ordered1 = copyArray(ordered);

        

        BTree root = BTreeVsArray.arrayToTree(ordered, 0, ordered.length - 1);

        assertTrue(BTreeVsArray.isBinarySearchTree(root));

        BTreeVsArray.printPreOrder(root);

        System.out.println();

        BTreeVsArray.printInOrder(root);

        System.out.println();

        BTreeVsArray.printPostOrder(root);

        System.out.println();

        assertFalse(BTreeVsArray.isInorder(ordered1));

        assertFalse(BTreeVsArray.inOrderCompare(root, ordered1));

        assertFalse(BTreeVsArray.inOrderCompare2(root, ordered1, 0, ordered1.length - 1));

        

        int[] preordered = new int[BTreeVsArray.count(root)];

        preordered = BTreeVsArray.treeToArrayPreorder(root, preordered, 0, preordered.length-1);

        int[] preordered1 = copyArray(preordered);

        

        BTree root1 = BTreeVsArray.arrayToTreePreOrder(preordered, 0, preordered.length - 1);

        assertTrue(BTreeVsArray.isBinarySearchTree(root1));

        System.out.println("pre-order array: ");

        printArray(preordered);

        System.out.println();

        BTreeVsArray.printPreOrder(root1);

        System.out.println();

        BTreeVsArray.printInOrder(root1);

        System.out.println();

        BTreeVsArray.printPostOrder(root1);

        System.out.println();

        

        assertFalse(BTreeVsArray.isPreorder(preordered1, 0, preordered1.length - 1));

        assertFalse(BTreeVsArray.preOrderCompare(root1, preordered1, 0, preordered1.length - 1));

        

        int[] postordered = new int[BTreeVsArray.count(root)];

        postordered = BTreeVsArray.treeToArrayPostorder(root, postordered, 0, postordered.length-1);

        System.out.println("post-order array: ");

        printArray(postordered);

        System.out.println();

        int[] postordered1 = copyArray(postordered);

        

        BTree root2 = BTreeVsArray.arrayToTreePostOrder(postordered, 0, postordered.length - 1);

        assertTrue(BTreeVsArray.isBinarySearchTree(root2));

        BTreeVsArray.printPreOrder(root2);

        System.out.println();

        BTreeVsArray.printInOrder(root2);

        System.out.println();

        BTreeVsArray.printPostOrder(root2);

        System.out.println();

        

        assertFalse(BTreeVsArray.isPostorder(postordered1, 0, postordered1.length - 1));

        assertFalse(BTreeVsArray.postOrderCompare(root2, postordered1, 0, postordered1.length - 1));

    }

    

    private void testRunner3(int[] preordered) {

        System.out.println("3 arrays: ");

        int[] preordered1 = copyArray(preordered);

        

        BTree root1 = BTreeVsArray.arrayToTreePreOrder(preordered, 0, preordered.length - 1);

        assertTrue(BTreeVsArray.isBinarySearchTree(root1));

        BTreeVsArray.printPreOrder(root1);

        System.out.println();

        BTreeVsArray.printInOrder(root1);

        System.out.println();

        BTreeVsArray.printPostOrder(root1);

        System.out.println();

        

        assertTrue(BTreeVsArray.isPreorder(preordered1, 0, preordered1.length - 1));

        assertTrue(BTreeVsArray.preOrderCompare(root1, preordered1, 0, preordered1.length - 1));

    }

    

    private void testRunner4(int[] postordered) {

        System.out.println("3 arrays: ");

        int[] postordered1 = copyArray(postordered);

        

        BTree root2 = BTreeVsArray.arrayToTreePostOrder(postordered, 0, postordered.length - 1);

        assertTrue(BTreeVsArray.isBinarySearchTree(root2));

        BTreeVsArray.printPreOrder(root2);

        System.out.println();

        BTreeVsArray.printInOrder(root2);

        System.out.println();

        BTreeVsArray.printPostOrder(root2);

        System.out.println();

        

        assertTrue(BTreeVsArray.isPostorder(postordered1, 0, postordered1.length - 1));

        assertTrue(BTreeVsArray.postOrderCompare(root2, postordered1, 0, postordered1.length - 1));

    }

    

    private BTree tree(int[] arr) {

        BTree root = null;

        for(int i: arr) {

            root = insert(root, i);

        }

        return root;

    }

    

    private BTree insert(BTree root, int i) {

        if(root == null) {

            return new BTree(i, null, null);

        }

        if(root.value == i) {

            return root;

        }

        if(root.value < i) {

            root.right = insert(root.right, i);

        } else {

            root.left = insert(root.left, i);

        }

        return root;

    }

    

    private int[] copyArray(int[] arr) {

        if(arr == null) return null;

        int[] copy = new int[arr.length];

        for(int i = 0; i < arr.length; i++) {

            copy[i] = arr[i];

        }

        return copy;

    }

    

    private void printArray(int[] arr) {

        if(arr == null) return;

        for(int i = 0; i < arr.length; i++) {

            System.out.print(arr[i] + ", ");

        }

    }

}