2

I am trying to teach my students the proper way to use Java generics. I am teaching a data structures course, so I want them working with arrays and their own linked lists, not with the Java Collections (for example no ArrayList). A typical issue is providing an array implementation for an ADT. Here is an example where I am trying to use a heap implemented as an array to provide a Priority Queue. I would like to support a priority queue of any kind of data objects so I use a generic I start with an interface:

public interface PriQue<E> {
    void insert(int pri, E data);
    E remove(); // return null when empty
    boolean isEmpty();
}

Then I implemented it:

public class ArrayHeap<E> implements PriQue<E> {
//private class Entry<E> {  hides E of ArrayHeap which means remove fails
    private class Entry {  // uses E of ArrayHeap
        int pri;
        E data;
    . . .
    } // end of Entry
    Entry heap[];
    int cnt;
    public ArrayHeap(int size) {
        // heap = new Entry[size]; can not create generic array error
        // heap = (Entry[])new Object[size]; blows up on a cast error
        heap = (Entry[])new Object[size];
        cnt = 0;
    }
    . . .
    public E remove() {
        E tmp = (E)heap[--cnt].getData(); //bad don't want to cast
        // trickle down code here
        return tmp;
    }

Since the interface is parameterized I use the same generic in the implementing class – I think this is ok. I need to create an array of entries that will hold a priority and the corresponding data item. So I create a private class. Here my problem begins. If I leave the parameter out then since it is part of ArrayHeap it should pick up the E generic form there. This compiles but blows up when I try to create an array of Entry. Alternately I can have an explicit generic parameter to Entry. If I pick E it will “hide” E from ArrayHeap and when I try to remove an E from the array it does not realize it is the same E as the ArrayHeap E. If I name it something else, say V, then it cannot assign an E to a V and I cannot store any data. I think this is a fairly common situation in implementing a data structure.
I’ve tried reading http://www.angelikalanger.com/GenericsFAQ/FAQSections/ParameterizedTypes.html#FAQ104 But it does not cover a nested class (and its mostly about what does not work) I’ve tried reading the code for the Java collections map implementation and I don’t see what is different.

Improve this question
10
  • 1
    You declare your inner class with its own generic type - say V. Then, when you declare the instance if the inner class you use E - Entry<E> heap[];. This is when you set V equal to E. For an example take a look at the source for AbstractMap which has exactly the same pattern. You cannot create generic arrays; this is your main issue it seems. Commented Mar 12, 2014 at 16:08
  • How does remove() fails, when you use Entry<E> instead of Entry? Commented Mar 12, 2014 at 16:10
  • Have you looked at the source code for HashMap on GrepCode? It uses a nested class with generics: grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… Also, I don't understand what you mean when you say "should pick up the E generic form there". Can you clarify? Commented Mar 12, 2014 at 16:11
  • @BoristheSpider is right. You have to declare it Entry<E> heap[]; Commented Mar 12, 2014 at 16:12
  • on the @Rohit Jain comment if I declare Entry Commented Mar 14, 2014 at 13:58

2 Answers 2

Reset to default
3

This worked for me:

public class ArrayHeap<E> implements PriQue<E> {
    private static class Entry<E> {
        int pri;
        E data;

        // ...

        public E getData() {
            return data;
        }
    }

    Entry<E>[] heap;
    int cnt;

    public ArrayHeap(int size) {
        heap = (Entry<E>[])new Entry<?>[size];
        // or: heap = new Entry[size];
        cnt = 0;
    }

    public E remove() {
        E tmp = heap[--cnt].getData();
        return tmp;
    }

    // ...
}

The key is that Entry is changed to become a static nested class, rather than a non-static inner class (which would still be dependent on your outer class's type parameters). Then you can actually create an array of Entry<?>, and do a cast from that.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

You can even do Entry<E>[] heap = new Entry[size] and trade the cast for a compiler warning. Worth pointing out that the OP should stop using legacy array notation too.
@BoristheSpider Yep, indeed. (And in fact even the cast will cause a compiler warning.)
@BoristheSpider: except that raw types should be avoided
@newacct if you're in the business of abusing arrays to get a generic type then rawtypes are probably the least of your problems. Although I agree entirely, rawtypes are evil.
Yes, all these @BoristheSpider comments suggest Java may not be terribly usable. But, somehow folks use it.
|
1

The problem is that because Java erases generic type parameters at compile-time, it's not safe to create an array containing a generic type. You're going to need a cast somewhere: the best you can do is to hide it away in helper functions.

If you look at the JDK implementation of ArrayList, for example, you'll see that at its heart is an Object[].

Improve this answer

1 Comment

I'm well aware that the decision to to erase generic type at the end of compile time, made to avoid having to update JVM which was considered to widely distirbuted to changed, means everything in Java (other than primatives) ends up as an Object by runtime. The question is - is this problem contained enough to use Java to teach ADT's. Given that the Java collections class seems to work ok, it would seem that there is some way to do it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.