Difficulties with Iterator and Generics in Binary Search Tree Implementation

Question

Hey everyone! I am studying Data Structures in java and I am having difficulty with using generics in Binary Search Trees.

For our assignment we are to implement a Binary Search Tree using nodes that contain a parent, left and right node as well as a data value.

The data value in our case takes the form of a Pair object. This is what it looks like:

public class Pair<A,B> {

    public final A fst;
    public final B snd;

    public Pair(A x, B y) {
        fst = x;  snd = y;
    }

    public String toString() {
      return new String("("+fst.toString()+", "+snd.toString()+")");
    }
}

Pair is associtated with two different generics with the first part being the Key and the second being the Value associated with that key.

I also need to implement Iterator in my BST class. I am implementing the Iterator in an inner class that looks something like this:

public Iterator<Pair<K,T>> iterator() {
    return new BSTMapIter<Pair<K,T>>(this.root, this.size, this.order);
}

private class BSTMapIter<Pair<K,T>> implements Iterator<Pair<K,T>> { <=== Compiler error "> expected"
    ...
    ... (Implementation here)
    ...
}

The problem I am running into is a compiler error saying "> expected" which leads to other compiler errors ("<identifier expected>" etc.). From my understanding it is choking over <Pair<K,T>> but I have no idea why. I am assuming it is a mistake I made with using generics somewhere, but I am not entirely sure where to look.

I apologize if what I have provided is too vague but I have not encountered any problems with Pair in my implementation anywhere else but here in the implementation of the Iterator.

Can anyone tell me what I am doing wrong here??? If any further information is needed, let me know and I will do my best to provide :)

Answer 1

The problem is the way you're trying to make BSTMapIter generic. It needs to be generic in two type parameters, K and T. The Pair part is irrelevant at this point. (It's important when it comes to what interface it implements though.) So the declaration should be:

private class BSTMapIter<K,T> implements Iterator<Pair<K,T>>

However, that's if you want BSTMapIter to be generic in itself. If this is a nested class within a type which already has K and T as type parameters, you probably just want:

private class BSTMapIter implements Iterator<Pair<K,T>>

You also want to instantiate it slightly differently:

// When it's an inner class
public Iterator<Pair<K,T>> iterator() {
    return new BSTMapIter(this.root, this.size, this.order);
}

// When it's a standalone generic class
public Iterator<Pair<K,T>> iterator() {
    return new BSTMapIter<K, T>(this.root, this.size, this.order);
}