Java Generics Help

Question

I'm working on this homework that's kind of confusing me...

I am provided with the following BinarySearchTree class

import java.util.NoSuchElementException;

/**
 *
 * @param <T> The type of data stored in the nodes of the tree, must implement  Comparable<T> with the compareTo method.
 */
public class BinarySearchTree<T extends Comparable<T>> {


    BinaryTree<T> tree;

    int size;
    public BinarySearchTree() {
     tree = new BinaryTree<T>();
     size = 0;
    }

    public boolean isEmpty() {
     return tree.isEmpty();
    }

    protected BinaryTree<T> recursiveSearch(BinaryTree<T> root, T key) {
     if (root == null) {
      return null;
     }
     int c = key.compareTo(root.data);
     if (c == 0) {
      return root;
     }
     if (c < 0) {
      return recursiveSearch(root.left, key);
     } else {
      return recursiveSearch(root.right, key);
     }
    }

    public T search(T key) {
     if (tree.isEmpty()) { 
      return null;
     }
     return recursiveSearch(tree, key).data;
    }

    public void insert(T item) {

     if (tree.isEmpty()) { // insert here
      tree.makeRoot(item);
      size++;
      return;
     }

     // do an iterative descent
     BinaryTree<T> root = tree;
     boolean done=false;
     BinaryTree<T> newNode = null;
     while (!done) {
      int c = item.compareTo(root.data);
      if (c == 0) { // duplicate found, cannot be inserted
       throw new OrderViolationException();
      }
      if (c < 0) { // insert in left subtree
       if (root.left == null) { // insert here as left child
        newNode = new BinaryTree<T>();
        root.left = newNode;
        done=true;
       } else { // go further down left subtree
        root = root.left;
       }
      } else { // insert in right subtree
       if (root.right == null) { // insert here as right child 
        newNode = new BinaryTree<T>();
        root.right = newNode;
        done=true;
       } else { // go further down right subtree
        root = root.right;
       }
      }
     }
     // set fields of new node
     newNode.data = item;
     newNode.parent = root;
     size++;
    }

    /**
     * @param deleteNode Node whose parent will receive new node as right or left child,
     *      depending on whether this node is its parent's right or left child. 
     * @param attach The node to be attached to parent of deleteNode.
     */
    protected void deleteHere(BinaryTree<T> deleteNode, BinaryTree<T> attach) {

     // deleteNode has only one subtree, attach
     BinaryTree<T> parent = deleteNode.parent;
     deleteNode.clear();  // clear the fields
     if (parent == null) {
      return;
     }
     if (deleteNode == parent.left) {
      // left child of parent, attach as left subtree
      parent.detachLeft();
      parent.attachLeft(attach);
      return;
     }
     // attach as right subtree
     parent.detachRight();
     parent.attachRight(attach);
    }


    protected BinaryTree<T> findPredecessor(BinaryTree<T> node) {
     if (node.left == null) {
      return null;
     }
     BinaryTree<T> pred = node.left; // turn left once
     while (pred.right != null) { // keep turning right
      pred = pred.right;
     }
     return pred;
    }


    public T delete(T key) {
     if (tree.isEmpty()) { // can't delete from an empty tree
      throw new NoSuchElementException();
     }

     // find node containing key 
     BinaryTree<T> deleteNode = recursiveSearch(tree, key);
     if (deleteNode == null) { // data not found, can't delete
      throw new NoSuchElementException();
     }

     BinaryTree<T> hold;

     // case c: deleteNode has exactly two subtrees
     if (deleteNode.right != null && deleteNode.left != null) {
      hold = findPredecessor(deleteNode);
      deleteNode.data = hold.data;
      deleteNode = hold; // fall through to case a or b
     }

     // case a: deleteNode is a leaf
     if (deleteNode.left == null && deleteNode.right == null) {
      deleteHere(deleteNode, null);
      size--;
      return deleteNode.data;
     }  

     // case b: deleteNode has exactly one subtree
     if (deleteNode.right != null) {
      hold = deleteNode.right;
      deleteNode.right = null;
     } else {
      hold = deleteNode.left;
      deleteNode.left = null;
     }

     deleteHere(deleteNode,hold);
     if (tree == deleteNode) { // root deleted
      tree = hold;
     }
     size--;
     return deleteNode.data;
    }


    public T minKey() {
     if (tree.data == null) { // tree empty, can't find min value
      throw new NoSuchElementException();
     }

     BinaryTree<T> root = tree;
     T min=root.data;
     root = root.left;  // turn left once
     while (root != null) {  // keep going left to leftmost node
      min = root.data;
      root = root.left;
     }
     return min;
    }


    public T maxKey() {
     if (tree.getData() == null) { // tree empty, can't find max value
      throw new NoSuchElementException();
     }

     BinaryTree<T> root=tree;
     T max=root.data;
     root = root.right;  // turn right once
     while (root != null) { // keep going to rightmost node
      max = root.data;
      root = root.right;
     }
     return max;
    }


    public int size() {
     return size;
    }


    protected void recursivePreOrder(BinaryTree<T> root, Visitor<T> visitor) {
     if (root != null) {
      visitor.visit(root);
      recursivePreOrder(root.left, visitor);
      recursivePreOrder(root.right, visitor);
     }
    }


    public void preOrder(Visitor<T> visitor) {
     if (tree.isEmpty()) {
      return;
     }
     recursivePreOrder(tree, visitor);
    }


    protected void recursiveInOrder(BinaryTree<T> root, Visitor<T> visitor) {
     if (root != null) {
      recursiveInOrder(root.left, visitor);
      visitor.visit(root);
      recursiveInOrder(root.right, visitor);
     }
    }


    public void inOrder(Visitor<T> visitor) {
     if (tree.isEmpty()) { 
      return;
     }
     recursiveInOrder(tree, visitor);
    }


    protected void recursivePostOrder(BinaryTree<T> root, Visitor<T> visitor) {
     if (root != null) {
      recursivePostOrder(root.left, visitor);
      recursivePostOrder(root.right, visitor);
      visitor.visit(root);
     }
    }

    public void postOrder(Visitor<T> visitor) {
     if (tree.isEmpty()) {
      return;
     }
     recursivePostOrder(tree, visitor);
    }
}

================================================================================

Now I have another class Student.... I want to create a binary search tree of Student objects..

BinarySearchTree<Student> tree = new BinarySearchTree<Student>();

However when I do that I get the following error:

Bound mismatch: The type Student is not a valid substitute for the bounded parameter > of the type BinarySearchTree

Any ideas what's happening here... I can't figure it out.

Answer 1

Does the class Student implement Comparable?

Answer 2

but I'm not quite sure how to implement the compareTo method.

Basically it's something like the following. How the ordering works you have to decide.

class Student implements Comparable<Student> {

    //...

    int compareTo(Student other) {
        // return some negative number if this object is less than other
        // return 0 if this object is equal to other
        // return some positive number if this object is greater than other
    }
}

Answer 3

 public class BinarySearchTree<T extends Comparable<T>>

A formal generics argument, in your case T, lists what's required for a class to be a valid T. In you case, you've said, "to be a valid T, a class must implement Comparable" (The keyword is "extends", but in practice that means "extends or implements".)

In your instantiation, T is Student. If we substitute Student for T:

public class BinarySearchTree<Student extends Comparable<Student>>

is that a true statement? Does Student really implement Comparable?

If it does, Student fits the requirement of being a T, and so you can use Student as the actual parameter for the formal parameter T.

If not, you get the compiler's complaint you saw.

Actually, to cover more complicated situations where a subclass's implementation of Comparable is done by a super class, the more general form would be:

   public class BinarySearchTree<T extends Comparable<? super T > >

So you need to make Student implement Comparable< Student >.

Note that I didn't say that the compiler's looking for a Student.compareTo. It doesn't even get that far. It's looking to see if T (in your case, Student) is declared as implementing Comparable< T> (in your case, Comparable< Student >).

Now adding implements Comparable< Student > to Student will also make the compiler ensure that there's a public int compareTo method on Student. But without the "implements Comparable", even if the compiler knows there's a method Student.compareTo, it doesn't know that that compareTo is the Comparable.compareTo.

(In other words, we're looking for declared implementation, not just that there happens to be a method with the right name and signature.)

Answer 4

Ok I implemented Comparable in the student class... my compareTo looks like this:

public int compareTo(Object o) { 
     Student cr = (Student) o; 
     int cn1 = Integer.parseInt(this.id); 
     int cn2 = Integer.parseInt(cr.id); 
        if(cn1 > cn2) 
           return 1; 
        else if(cn1 < cn2) 
           return -1; 
        else 
           return 0; 
     }

However I still get the same error