BTreeCopyTest.java

import static org.junit.Assert.*;

import java.util.Random;

import org.junit.Test;

public class BTreeCopyTest {

    @Test

    public void basicTest() {

        int[] ordered = {1, 2, 3, 4, 5, 6, 7, 8, 9};

        testRunner(ordered);

        int[] ordered1 = {1, 2, 3, 4, 5, 6, 7, 8};

        testRunner(ordered1);

        

        Random r = new Random();

        

        int j = 100;

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

            int[] ordered3 = new int[L];

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

                ordered3[i] = r.nextInt(1000);

            }

            testRunner3(ordered3);

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

                ordered3[i] = r.nextInt(1000);

            }

            testRunner3(ordered3);

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

                ordered3[i] = r.nextInt(1000);

            }

            testRunner3(ordered3);

        }

    }

    

    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;

    }

    

    @Test

    public void edgeTest() {

        int[] ordered2 = {1};

        testRunner2(ordered2);

        int[] ordered1 = {};

        testRunner2(ordered1);

        

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

        System.out.println("original tree");

        BTreeCopy.printLevelOrder(root);

        BTree root2 = BTreeCopy.copyTree(root);

        System.out.println("copied tree");

        BTreeCopy.printLevelOrder(root2);

        BTree root4 = BTreeCopy.copyTreeMirror(root);

        System.out.println("copied mirror tree");

        BTreeCopy.printLevelOrder(root4);

        BTree root5 = BTreeCopy.makeMirrorInPlace(root);

        System.out.println("make mirror tree in place");

        BTreeCopy.printLevelOrder(root5);

        

        BTree root1 = BTreeCopy.arrayToTree(null, 0, 0);

        assertTrue(BTreeCopy.compareTree(root1, root2));

        assertTrue(BTreeCopy.compareTree(root1, root4));

        assertTrue(BTreeCopy.compareTree(root4, root5));

        assertTrue(BTreeCopy.compareTree(root, root4));

    }

    

    private void testRunner(int[] ordered) {

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

        System.out.println("original tree");

        BTreeCopy.printLevelOrder(root);

        BTree root2 = BTreeCopy.copyTree(root);

        System.out.println("copied tree");

        BTreeCopy.printLevelOrder(root2);

        BTree root4 = BTreeCopy.copyTreeMirror(root);

        System.out.println("copied mirror tree");

        BTreeCopy.printLevelOrder(root4);

        BTree root5 = BTreeCopy.makeMirrorInPlace(root);

        System.out.println("make mirror tree in place");

        BTreeCopy.printLevelOrder(root5);

        

        BTree root1 = BTreeCopy.arrayToTree(ordered, 0, ordered.length - 1);

        assertTrue(BTreeCopy.compareTree(root1, root2));

        assertFalse(BTreeCopy.compareTree(root1, root4));

        assertTrue(BTreeCopy.compareTree(root4, root5));

        assertTrue(BTreeCopy.compareTree(root, root4));

    }

    

    private void testRunner2(int[] ordered) {

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

        System.out.println("original tree");

        BTreeCopy.printLevelOrder(root);

        BTree root2 = BTreeCopy.copyTree(root);

        System.out.println("copied tree");

        BTreeCopy.printLevelOrder(root2);

        BTree root4 = BTreeCopy.copyTreeMirror(root);

        System.out.println("copied mirror tree");

        BTreeCopy.printLevelOrder(root4);

        BTree root5 = BTreeCopy.makeMirrorInPlace(root);

        System.out.println("make mirror tree in place");

        BTreeCopy.printLevelOrder(root5);

        

        BTree root1 = BTreeCopy.arrayToTree(ordered, 0, ordered.length - 1);

        assertTrue(BTreeCopy.compareTree(root1, root2));

        assertTrue(BTreeCopy.compareTree(root1, root4));

        assertTrue(BTreeCopy.compareTree(root4, root5));

        assertTrue(BTreeCopy.compareTree(root, root4));

    }

    

    private void testRunner3(int[] ordered) {

        BTree root = tree(ordered);

        System.out.println("original tree");

        BTreeCopy.printLevelOrder(root);

        BTree root2 = BTreeCopy.copyTree(root);

        System.out.println("copied tree");

        BTreeCopy.printLevelOrder(root2);

        BTree root4 = BTreeCopy.copyTreeMirror(root);

        System.out.println("copied mirror tree");

        BTreeCopy.printLevelOrder(root4);

        BTree root5 = BTreeCopy.makeMirrorInPlace(root);

        System.out.println("make mirror tree in place");

        BTreeCopy.printLevelOrder(root5);

        

        BTree root1 = tree(ordered);

        assertTrue(BTreeCopy.compareTree(root1, root2));

        assertFalse(BTreeCopy.compareTree(root1, root4));

        assertTrue(BTreeCopy.compareTree(root4, root5));

        assertTrue(BTreeCopy.compareTree(root, root4));

    }

}