Link to home
Start Free TrialLog in
Avatar of hoomanv
hoomanvFlag for Canada

asked on

generic array

Hi
I want to implement a generic Heap data structure but I dont know how to create a generic array that fits my need. I need a generic type T which must be a subclass of Comparable. my current approch would generate a ClassCastException. please help me.

import java.util.Random;

public class Heap <T extends Comparable> {
      protected int top;
      protected T arr[];
      protected int capacity;
      
      Heap(int k) {  // List Constructor
            capacity =  k; // Allocate Space
            arr = (T[]) new Object[capacity + 1];
      }

      public static void prt(String s){System.out.print(s);}
      
      // insert x at
      public void insert(T x) {
            arr[++top] = x;
      }
      
      // heap sort
      public void heapSort(){
            int i;
            // heapify from bottom to top
            for ( i = capacity / 2 ; i >= 1 ; i--)
                  heapify(i, capacity);
            for ( i = capacity ; i > 1 ; i--){
                  swap(1, i);
                  heapify(1, i-1);
            }
      }
      
      public void swap(int m, int n) {
            T tmp = arr[m];
            arr[m] = arr[n];
            arr[n] = tmp;
      }
//*******************************************************************
      public void heapify(int m, int k) {
            int minIndex = 2 * m;
            while (minIndex <= k){// m has at least one child
                  if (minIndex + 1 <= k) { // m has 2 children
                        if (arr[minIndex+1].compareTo(arr[minIndex]) > 0)
                        //if (arr[minIndex+1] > arr[minIndex])
                              minIndex ++;
                  }
                  if (arr[minIndex].compareTo(arr[m]) > 0) {
                  //if (arr[minIndex] > arr[m]) {
                        swap(m, minIndex);
                        m = minIndex;
                        minIndex = 2 * m;
                  }
                  else
                        break;
            }
      }
//*******************************************************************
      public String toString() {
            String s  = "[";
            for (int i = 1; i <= top; i++) {
                  s +=  ", " + arr[i] ;
            }
            return s + "]";
      }
//*******************************************************************
      public static void main(String args[]) {
            int p, x, MaxNum = 100;
            Random rand = new Random();
            p = 10;
            // Create List of type Integer
            Heap <Integer> intHeap = new Heap <Integer> (p);
            // Generate data
            for ( int i = 1 ; i <= p ; i++)
                  intHeap.insert(rand.nextInt(MaxNum) + 1);
            
            prt("\nunSorted List: " + intHeap.toString()); // print list
            intHeap.heapSort();
            prt("\n  Sorted List: " + intHeap.toString()+ "\n"); // print list
      }
}
Avatar of Mayank S
Mayank S
Flag of India image

That's because of: >> protected T arr[];

You cannot assign it to: arr = (T[]) new Object[capacity + 1];

An Object[] array cannot be converted to T[] directly. Instead, try these changes:

protected Object arr[] ;
arr = new Object[capacity + 1] ;

>> T tmp = arr[m];

T tmp = ( T ) arr[m] ;

>> if (arr[minIndex].compareTo(arr[m]) > 0) {

if ( ( ( T ) arr[minIndex] ) .compareTo ( arr[m] ) > 0 ) {
ASKER CERTIFIED SOLUTION
Avatar of Mayank S
Mayank S
Flag of India image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
>> You cannot assign it to: arr = (T[]) new Object[capacity + 1];

Since Object will be a super-type of T
Avatar of hoomanv

ASKER

mayankeagle:
thanks it works

> You cannot assign it to: arr = (T[]) new Object[capacity + 1];
but I've learned this from java's ArrayList that is doing it as well

assume the below code

class TestGenericArray <T> {
      public static void main(String[] args) {
            TestGenericArray <String> ti = new TestGenericArray <String> ();
            ti.test("String1","String2");
      }

      public void test(T... elements) {
            T[] t = (T[]) new Object[elements.length];
            for(int i = 0; i < t.length; i++)
                  System.out.println(t[i] = elements[i]);
      }
}

it works but if you change <T> to <T extends Comparable> it wont. why ?

as another question how to solve this one ?

class TestGenericArray<T> {
      public static void main(String[] args) {
            TestGenericArray<String> ti = new TestGenericArray<String>();
            String[] a = ti.test("String1", "String2");
            for (int i = 0; i < a.length; i++) {
                  System.out.println(a);
            }
      }

      public T[] test(T... elements) {
            T[] t = (T[]) (new Object[elements.length]);
            return t;
      }
}

BTW
how to use java.lang.reflect.Array.newInstance(Class Type, Size) to solve my problem
>> it works but if you change <T> to <T extends Comparable> it wont. why ?

Not sure, perhaps because T can also be an Object in that case. But when its a Comparable (or its derivative) then its certainly below Object (a sub-class of Object).

>> how to use java.lang.reflect.Array.newInstance(Class Type, Size) to solve my problem

Modify your constructor:

Heap(int k, T[] arr) {  // List Constructor
this.arr = ( T[] ) Array.newInstance ( arr[0].getClass (), capacity + 1 ) ;

Call it like:

Heap <Integer> intHeap = new Heap <Integer> ( p, new Integer[] { 1 } ) ;
>> as another question how to solve this one ?

Make:

>> String[] a = ti.test("String1", "String2");

as: Object[] a = ti.test("String1", "String2");

>> System.out.println(a);

as: System.out.println ( ( String ) a[i] ) ; // you also missed the index

In test (), add this at the end (after allocating the array):

for ( int i = 0 ; i < elements.length ; i ++ )
                t[i] = elements[i] ;
Avatar of hoomanv

ASKER

> as: Object[] a = ti.test("String1", "String2");

so the trick is getting the result as Object[] even though the return type is T[] or String[]
thanks but why is it so unpleasant. I thought its like C++ generics
Well, because as far as I know, in C++ you don't have every class extending an Object class....
>> String[] a = ti.test("String1", "String2");

Again has 'a' being assigned as a reference to an Object[]
Perhaps you can also do new T[] in C++ (not sure) but you cannot do that in Java. If you could do T[] array = new T[size], it would've been easier.
I'm leaving for the day now - perhaps all your Q's are answered :)
Avatar of hoomanv

ASKER

thanks a lot ;-)