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
      }
}
LVL 14
hoomanvAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Mayank SAssociate Director - Product EngineeringCommented:
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 ) {
0
Manikandan ThiagarajanSenior consultantCommented:
0
Mayank SAssociate Director - Product EngineeringCommented:
So after those changes, the code should be like:

import java.util.* ;

public class Heap <T extends Comparable> {
     protected int top;
     protected Object arr[];
     protected int capacity;

     Heap(int k) {  // List Constructor
          capacity =  k; // Allocate Space
          arr = 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 = ( T ) 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 ( ( ( T ) arr[minIndex+1] ).compareTo(arr[minIndex]) > 0)
                    //if (arr[minIndex+1] > arr[minIndex])
                         minIndex ++;
               }
               if ( ( ( T ) 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
     }
}

And it seems to work.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Cloud Class® Course: Python 3 Fundamentals

This course will teach participants about installing and configuring Python, syntax, importing, statements, types, strings, booleans, files, lists, tuples, comprehensions, functions, and classes.

Mayank SAssociate Director - Product EngineeringCommented:
>> You cannot assign it to: arr = (T[]) new Object[capacity + 1];

Since Object will be a super-type of T
0
hoomanvAuthor Commented:
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
0
Mayank SAssociate Director - Product EngineeringCommented:
>> 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 } ) ;
0
Mayank SAssociate Director - Product EngineeringCommented:
>> 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] ;
0
hoomanvAuthor Commented:
> 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
0
Mayank SAssociate Director - Product EngineeringCommented:
Well, because as far as I know, in C++ you don't have every class extending an Object class....
0
Mayank SAssociate Director - Product EngineeringCommented:
>> String[] a = ti.test("String1", "String2");

Again has 'a' being assigned as a reference to an Object[]
0
Mayank SAssociate Director - Product EngineeringCommented:
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.
0
Mayank SAssociate Director - Product EngineeringCommented:
I'm leaving for the day now - perhaps all your Q's are answered :)
0
hoomanvAuthor Commented:
thanks a lot ;-)
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.