• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 213
  • Last Modified:

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
      }
}
0
hoomanv
Asked:
hoomanv
  • 9
  • 3
1 Solution
 
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

  • 9
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now