Subversion Repositories programming

Rev

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

Rev 45 Rev 49
Line 1... Line 1...
1 
// Written by Ira Snyder
 1 
// Written by Ira Snyder
2 
//
 2 
 
3 
import java.io.*;
 3 
import java.io.*;
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 {
Line 37... Line 37...
37 
        }
 37 
        }
38 
 
 38 
 
39 
        return answer;
 39 
        return answer;
40 
    }
 40 
    }
41
41
- 
 
 42 
    //method to make a test tree
42 
    public static AVLTree createTestTree( int size ) {
 43 
    public static AVLTree createTestTree( int size ) {
43 
        int[] nums = new int[30];
 44 
        int[] nums = new int[30];
44 
 
 45 
 
45 
        for( int i=0; i<30; i++ ) { nums[i] = i; }
 46 
        for( int i=0; i<30; i++ ) { nums[i] = i; }
46
47
Line 49... Line 50...
49 
        Integer[] data = makeIntegers(nums);
 50 
        Integer[] data = makeIntegers(nums);
50 
 
 51 
 
51 
        return new AVLTree(nums,data);
 52 
        return new AVLTree(nums,data);
52 
    }
 53 
    }
53 
 
 54 
 
54
55 
    //method to test the basic AVLTree constructor
55 
    public static void testBasicConstructor() {
 56 
    public static void testBasicConstructor() {
56 
        //this should make a pole if the tree is not balanced (IE: a plain BST)
 57 
        //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 
        //if the tree is _not_ balanced, this will print height = 7
58 
        AVLTree poleTree = new AVLTree(1,new Integer(1));
 59 
        AVLTree poleTree = new AVLTree(1,new Integer(1));
59 
        poleTree.add(2,new Integer(2));
 60 
        poleTree.add(2,new Integer(2));
Line 65... Line 66...
65
66
66 
        System.out.print("Should print 2: ");
 67 
        System.out.print("Should print 2: ");
67 
        System.out.println("height = " + poleTree.getHeight());
 68 
        System.out.println("height = " + poleTree.getHeight());
68 
    }
 69 
    }
69
70
- 
 
 71 
    //method to test the AVLTree array constructor
70 
    public static void testArrayConstructor() {
 72 
    public static void testArrayConstructor() {
71 
        int[] nums = new int[30];
 73 
        int[] nums = new int[30];
72 
 
 74 
 
73 
        for( int i=0; i<30; i++ ) { nums[i] = i; }
 75 
        for( int i=0; i<30; i++ ) { nums[i] = i; }
74
76
Line 83... Line 85...
83 
 
 85 
 
84 
        System.out.print("should be 4 or 5: ");
 86 
        System.out.print("should be 4 or 5: ");
85 
        System.out.println("height = " + tree.getHeight());
 87 
        System.out.println("height = " + tree.getHeight());
86 
    }
 88 
    }
87
89
- 
 
 90 
    //method to test the getter methods from Prog. Prob. 13.3
88 
    public static void testGetters() {
 91 
    public static void testGetters() {
89 
        AVLTree tree = new AVLTree(1,new Integer(1));
 92 
        AVLTree tree = new AVLTree(1,new Integer(1));
90 
        tree.add(2,new Integer(2));
 93 
        tree.add(2,new Integer(2));
91 
        tree.add(3,new Integer(3));
 94 
        tree.add(3,new Integer(3));
92 
 
 95 
 
Line 94... Line 97...
94 
        System.out.println("tree.getRoot() = " + tree.getRoot());
 97 
        System.out.println("tree.getRoot() = " + tree.getRoot());
95 
        System.out.println("tree.getLeft() = " + tree.getLeft());
 98 
        System.out.println("tree.getLeft() = " + tree.getLeft());
96 
        System.out.println("tree.getRight() = " + tree.getRight());
 99 
        System.out.println("tree.getRight() = " + tree.getRight());
97 
    }
 100 
    }
98 
 
 101 
 
- 
 
 102 
    //method to test the contains method from Prog. Prob. 13.4
99 
    public static void testContains() {
 103 
    public static void testContains() {
100 
        AVLTree tree = createTestTree(30);
 104 
        AVLTree tree = createTestTree(30);
101
105
102 
        System.out.println("tree.contains(20) = " + tree.contains(20));
 106 
        System.out.println("tree.contains(20) = " + tree.contains(20));
103 
        System.out.println("tree.contains(50) = " + tree.contains(50));
 107 
        System.out.println("tree.contains(50) = " + tree.contains(50));
104 
    }
 108 
    }
105 
 
 109 
 
- 
 
 110 
    //get the get() method from Prog. Prob. 13.5
106 
    public static void testGet() {
 111 
    public static void testGet() {
107 
        AVLTree tree = createTestTree(30);
 112 
        AVLTree tree = createTestTree(30);
108 
 
 113 
 
109 
        System.out.println("tree.get(10) = " + tree.get(10));
 114 
        System.out.println("tree.get(10) = " + tree.get(10));
110 
        System.out.println("tree.get(50) = " + tree.get(50));
 115 
        System.out.println("tree.get(50) = " + tree.get(50));
111 
    }
 116 
    }
112 
 
 117 
 
- 
 
 118 
    //test the equals method from Prog. Prob. 13.6
113 
    public static void testEquals() {
 119 
    public static void testEquals() {
114 
        AVLTree tree1 = createTestTree(10);
 120 
        AVLTree tree1 = createTestTree(10);
115 
        AVLTree tree2 = createTestTree(10);
 121 
        AVLTree tree2 = createTestTree(10);
116
122
117 
        int[] nums = { 0,10,20,30,40,50,60,70,80,90 };
 123 
        int[] nums = { 0,10,20,30,40,50,60,70,80,90 };
Line 124... Line 130...
124 
 
 130 
 
125 
        System.out.println("tree1.equals(tree2) = " + tree1.equals(tree2));
 131 
        System.out.println("tree1.equals(tree2) = " + tree1.equals(tree2));
126 
        System.out.println("tree1.equals(tree3) = " + tree1.equals(tree3));
 132 
        System.out.println("tree1.equals(tree3) = " + tree1.equals(tree3));
127 
    }
 133 
    }
128 
 
 134 
 
- 
 
 135 
    //method to test the remove method from Project 2
129 
    public static void testRemove() {
 136 
    public static void testRemove() {
130 
        AVLTree tree = createTestTree(30);
 137 
        AVLTree tree = createTestTree(30);
131
138
132 
        //print the original tree
 139 
        //print the original tree
133 
        System.out.println("tree = " + tree);
 140 
        System.out.println("tree = " + tree);