Subversion Repositories programming

Rev

Rev 44 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 44 Rev 45
Line 4... Line 4...
4 
 
 4 
 
5 
class Driver {
 5 
class Driver {
6 
 
 6 
 
7 
    public static void main ( String [] args ) throws Exception {
 7 
    public static void main ( String [] args ) throws Exception {
8
8
9 
        //this should make a pole if the tree is not balanced
 - 
 
10 
        //if the tree is _not_ balanced, this will print height = 7
 - 
 
11 
        AVLTree poleTree = new AVLTree(1,new Integer(1));
 - 
 
12 
        poleTree.add(2,new Integer(2));
 - 
 
13 
        poleTree.add(3,new Integer(3));
 9 
        testBasicConstructor();
14 
        poleTree.add(4,new Integer(4));
 - 
 
15 
        poleTree.add(5,new Integer(5));
 - 
 
16 
        poleTree.add(6,new Integer(6));
 - 
 
17 
        poleTree.add(7,new Integer(7));
 - 
 
18 
 
 - 
 
19 
        System.out.println("poleTree.getHeight() = " + poleTree.getHeight());
 - 
 
20 
 
 - 
 
21 
        //this should do something similar to the above test, but
 - 
 
22 
        //it will use the alternate constructor
 - 
 
23 
        int[] nums = { 10,20,30,40,50,60,70 }; //some numbers
 - 
 
24 
        Integer[] data = makeIntegers(nums);
 - 
 
25
- 
 
26 
        poleTree = new AVLTree(nums,data);
 - 
 
27 
        System.out.println("poleTree.getHeight() = " + poleTree.getHeight());
 - 
 
28 
 
 - 
 
29 
        System.out.println();
 10 
        System.out.println();
30 
        System.out.println("poleTree.getRoot() = " + poleTree.getRoot());
 - 
 
- 
 
 11 
 
31 
        System.out.println("poleTree.getLeft() = " + poleTree.getLeft());
 12 
        testArrayConstructor();
32 
        System.out.println("poleTree.getRight() = " + poleTree.getRight());
 - 
 
33
- 
 
34 
        System.out.println();
 13 
        System.out.println();
35 
        System.out.println("poleTree.contains(70) = " + poleTree.contains(70));
 - 
 
36 
        System.out.println("poleTree.contains(90) = " + poleTree.contains(90));
 - 
 
37 
 
 14 
 
- 
 
 15 
        testGetters();
38 
        System.out.println();
 16 
        System.out.println();
39 
        System.out.println("poleTree.get(60) = " + poleTree.get(60));
 - 
 
40 
        System.out.println("poleTree.get(90) = " + poleTree.get(90));
 - 
 
41 
 
 17 
 
- 
 
 18 
        testContains();
42 
        System.out.println();
 19 
        System.out.println();
43 
        int[] nums2 = { 10,20,30,40,50,60,70 };
 - 
 
44 
        Integer[] data2 = makeIntegers(nums2);
 - 
 
45
- 
 
46 
        int[] nums3 = { 1,10,2,20,3,30,4,40,5,50 };
 - 
 
47 
        Integer[] data3 = makeIntegers(nums3);
 - 
 
48
- 
 
49 
        AVLTree eqlTree = new AVLTree(nums2,data2);
 - 
 
50 
        AVLTree nonEqlTree = new AVLTree(nums3,data3);
 - 
 
51 
 
 20 
 
52 
        System.out.println("poleTree = " + poleTree);
 - 
 
53 
        System.out.println("eqlTree = " + eqlTree);
 - 
 
54 
        System.out.println("nonEqlTree = " + nonEqlTree);
 - 
 
55 
        System.out.println("poleTree.equals(eqlTree) = " + poleTree.equals(eqlTree));
 - 
 
56 
        System.out.println("poleTree.equals(nonEqlTree) = " + poleTree.equals(nonEqlTree));
 - 
 
57 
        int[] iranums = { 2 };
 21 
        testGet();
58 
        Integer[] iradata = makeIntegers(iranums);
 - 
 
59 
        AVLTree iratree = new AVLTree(iranums,iradata);
 - 
 
60 
        iratree.ira_dm();
 22 
        System.out.println();
61 
 
 23 
 
62 
        /*
 24 
        testEquals();
63 
        System.out.println();
 25 
        System.out.println();
64 
        System.out.println("poleTree = " + poleTree);
 - 
 
65 
        System.out.println("poleTree.remove(10) = " + poleTree.remove(10) + "\n" + poleTree);
 - 
 
66 
        System.out.println("poleTree.remove(20) = " + poleTree.remove(20));
 - 
 
67 
        System.out.println("poleTree.remove(90) = " + poleTree.remove(90));
 - 
 
68 
        System.out.println("poleTree = " + poleTree);
 - 
 
- 
 
 26 
 
69 
        */
 27 
        testRemove();
70 
    }
 28 
    }
71
29
72 
    //creates an array of Integers from an array of ints. The returned array
 30 
    //creates an array of Integers from an array of ints. The returned array
73 
    //will have all of the values multiplied by 200 (just to give my data
 31 
    //will have all of the values multiplied by 200 (just to give my data
74 
    //different values from the keys
 32 
    //different values from the keys
Line 79... Line 37...
79 
        }
 37 
        }
80 
 
 38 
 
81 
        return answer;
 39 
        return answer;
82 
    }
 40 
    }
83
41
- 
 
 42 
    public static AVLTree createTestTree( int size ) {
- 
 
 43 
        int[] nums = new int[30];
- 
 
 44 
 
- 
 
 45 
        for( int i=0; i<30; i++ ) { nums[i] = i; }
- 
 
 46
- 
 
 47 
        //returns the int[] as a Integer[] with the values
- 
 
 48 
        //multiplied by 200
- 
 
 49 
        Integer[] data = makeIntegers(nums);
- 
 
 50 
 
- 
 
 51 
        return new AVLTree(nums,data);
- 
 
 52 
    }
- 
 
 53 
 
- 
 
 54
- 
 
 55 
    public static void testBasicConstructor() {
- 
 
 56 
        //this should make a pole if the tree is not balanced (IE: a plain BST)
- 
 
 57 
        //if the tree is _not_ balanced, this will print height = 7
- 
 
 58 
        AVLTree poleTree = new AVLTree(1,new Integer(1));
- 
 
 59 
        poleTree.add(2,new Integer(2));
- 
 
 60 
        poleTree.add(3,new Integer(3));
- 
 
 61 
        poleTree.add(4,new Integer(4));
- 
 
 62 
        poleTree.add(5,new Integer(5));
- 
 
 63 
        poleTree.add(6,new Integer(6));
- 
 
 64 
        poleTree.add(7,new Integer(7));
- 
 
 65
- 
 
 66 
        System.out.print("Should print 2: ");
- 
 
 67 
        System.out.println("height = " + poleTree.getHeight());
- 
 
 68 
    }
- 
 
 69
- 
 
 70 
    public static void testArrayConstructor() {
- 
 
 71 
        int[] nums = new int[30];
- 
 
 72 
 
- 
 
 73 
        for( int i=0; i<30; i++ ) { nums[i] = i; }
- 
 
 74
- 
 
 75 
        //returns the int[] as a Integer[] with the values
- 
 
 76 
        //multiplied by 200
- 
 
 77 
        Integer[] data = makeIntegers(nums);
- 
 
 78 
 
- 
 
 79 
        AVLTree tree = new AVLTree(nums,data);
- 
 
 80 
 
- 
 
 81 
        System.out.print("size should be 30: ");
- 
 
 82 
        System.out.println("size = " + tree.size());
- 
 
 83 
 
- 
 
 84 
        System.out.print("should be 4 or 5: ");
- 
 
 85 
        System.out.println("height = " + tree.getHeight());
- 
 
 86 
    }
- 
 
 87
- 
 
 88 
    public static void testGetters() {
- 
 
 89 
        AVLTree tree = new AVLTree(1,new Integer(1));
- 
 
 90 
        tree.add(2,new Integer(2));
- 
 
 91 
        tree.add(3,new Integer(3));
- 
 
 92 
 
- 
 
 93 
        System.out.println("tree = " + tree);
- 
 
 94 
        System.out.println("tree.getRoot() = " + tree.getRoot());
- 
 
 95 
        System.out.println("tree.getLeft() = " + tree.getLeft());
- 
 
 96 
        System.out.println("tree.getRight() = " + tree.getRight());
- 
 
 97 
    }
- 
 
 98 
 
- 
 
 99 
    public static void testContains() {
- 
 
 100 
        AVLTree tree = createTestTree(30);
- 
 
 101
- 
 
 102 
        System.out.println("tree.contains(20) = " + tree.contains(20));
- 
 
 103 
        System.out.println("tree.contains(50) = " + tree.contains(50));
- 
 
 104 
    }
- 
 
 105 
 
- 
 
 106 
    public static void testGet() {
- 
 
 107 
        AVLTree tree = createTestTree(30);
- 
 
 108 
 
- 
 
 109 
        System.out.println("tree.get(10) = " + tree.get(10));
- 
 
 110 
        System.out.println("tree.get(50) = " + tree.get(50));
- 
 
 111 
    }
- 
 
 112 
 
- 
 
 113 
    public static void testEquals() {
- 
 
 114 
        AVLTree tree1 = createTestTree(10);
- 
 
 115 
        AVLTree tree2 = createTestTree(10);
- 
 
 116
- 
 
 117 
        int[] nums = { 0,10,20,30,40,50,60,70,80,90 };
- 
 
 118 
        Integer[] data = makeIntegers(nums);
- 
 
 119 
        AVLTree tree3 = new AVLTree(nums,data);
- 
 
 120 
 
- 
 
 121 
        System.out.println("tree1 = " + tree1);
- 
 
 122 
        System.out.println("tree2 = " + tree2);
- 
 
 123 
        System.out.println("tree3 = " + tree3);
- 
 
 124 
 
- 
 
 125 
        System.out.println("tree1.equals(tree2) = " + tree1.equals(tree2));
- 
 
 126 
        System.out.println("tree1.equals(tree3) = " + tree1.equals(tree3));
- 
 
 127 
    }
- 
 
 128 
 
- 
 
 129 
    public static void testRemove() {
- 
 
 130 
        AVLTree tree = createTestTree(30);
- 
 
 131
- 
 
 132 
        //print the original tree
- 
 
 133 
        System.out.println("tree = " + tree);
- 
 
 134
- 
 
 135 
        //remove the first 10 elements
- 
 
 136 
        for( int i=0; i<10; i++ ) {
- 
 
 137 
            System.out.println("tree.remove(" + i + ") = " + tree.remove(i));
- 
 
 138 
        }
- 
 
 139
- 
 
 140 
        //remove some elements not in the tree
- 
 
 141 
        for( int i=50; i<55; i++ ) {
- 
 
 142 
            System.out.println("tree.remove(" + i + ") = " + tree.remove(i));
- 
 
 143 
        }
- 
 
 144
- 
 
 145 
        //print the tree after everything has been removed
- 
 
 146 
        System.out.println("tree = " + tree);
- 
 
 147 
    }
84 
}
 148 
}
85 
 
 149