hoomanv
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[minIn dex]) > 0)
//if (arr[minIndex+1] > arr[minIndex])
minIndex ++;
}
if (arr[minIndex].compareTo(a rr[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.nextIn t(MaxNum) + 1);
prt("\nunSorted List: " + intHeap.toString()); // print list
intHeap.heapSort();
prt("\n Sorted List: " + intHeap.toString()+ "\n"); // print list
}
}
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
//if (arr[minIndex+1] > arr[minIndex])
minIndex ++;
}
if (arr[minIndex].compareTo(a
//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.nextIn
prt("\nunSorted List: " + intHeap.toString()); // print list
intHeap.heapSort();
prt("\n Sorted List: " + intHeap.toString()+ "\n"); // print list
}
}
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
>> You cannot assign it to: arr = (T[]) new Object[capacity + 1];
Since Object will be a super-type of T
Since Object will be a super-type of T
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.ne wInstance( Class Type, Size) to solve my problem
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.ne
>> 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.ne wInstance( 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 } ) ;
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.ne
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] ;
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] ;
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
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[]
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 :)
ASKER
thanks a lot ;-)
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(a
if ( ( ( T ) arr[minIndex] ) .compareTo ( arr[m] ) > 0 ) {