Implementing Set <T>T[] toArray(T[] a)

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 1800 Views - Last Post: 31 May 2012 - 06:15 PM Rate Topic: -----

#1 cre8tion  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 19
  • Joined: 29-May 12

Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 02:24 AM

public T[] toArray(){
   @SuppressWarnings("unchecked")
        T[] result = (T[])new Object[length]; // unchecked cast
        int index = 0;
        
        Node currentNode = firstNode;
        while ((index < length) && (currentNode != null)) {
          result[index] = currentNode.data;
          
          index++;
          currentNode = currentNode.next;
        } // end while
        
        return result;
      } // end toArray()
  
  public <T>T[] toArray(T[] a){
    @SuppressWarnings("unchecked")
        T[] result = (T[])a[length]; // unchecked cast
        int index = 0;
        
        Node currentNode = firstNode;
        while ((index < length) && (currentNode != null)) {
          result[index] = (T) currentNode.data;
          
          index++;
          currentNode = currentNode.next;
        } // end while
        
        return result;
  } //end toArray(a)



My T[] toArray() works but I don't really understand the <T>T[] toArray(T[] a) implementation...

If i pass:
Object[] array = set4.toArray(new BigInteger[0]);
      for(int k=0; k<array.length; k++){
         System.out.println("at index " + k + " found " + array[k]);

I get an out of bounds exception :|

Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: Implementing Set <T>T[] toArray(T[] a)

#2 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2833
  • View blog
  • Posts: 12,000
  • Joined: 20-September 08

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 02:54 AM

http://technojeeves....free/118-errors
Was This Post Helpful? 0
  • +
  • -

#3 cre8tion  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 19
  • Joined: 29-May 12

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 02:58 AM

Its not really the error I was concerned with, its implementing the method correctly.

But the error is :

java.lang.ArrayIndexOutOfBoundsException: 4
at LinkedSet.toArray(LinkedSet.java:213)
at TestLinkedSet.main(TestLinkedSet.java:123)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
at java.lang.reflect.Method.invoke(Method.java:597)
at edu.rice.cs.drjava.model.compiler.JavacCompiler.runCommand(JavacCompiler.java:271)
Was This Post Helpful? 0
  • +
  • -

#4 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2833
  • View blog
  • Posts: 12,000
  • Joined: 20-September 08

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 03:30 AM

OK. In LinkedSet.java, which is line 213?
Was This Post Helpful? 0
  • +
  • -

#5 Kakerergodt  Icon User is offline

  • D.I.C Head

Reputation: 87
  • View blog
  • Posts: 201
  • Joined: 01-May 12

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 03:39 AM

I'm betting it's this line:
T[] result = (T[])a[length]; // unchecked cast

that gives you an ArrayIndexOutOfBoundsException, there's little point to casting a whole array of one class to another class without iterating through the array, which you do later in the code anyways. But if you want to cast it to type T switch it to:
T[] result = (T[])a; // unchecked cast

But the best way to do it is to switch it to:
T[] result = new T[length];

This post has been edited by Kakerergodt: 31 May 2012 - 03:42 AM

Was This Post Helpful? 0
  • +
  • -

#6 cre8tion  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 19
  • Joined: 29-May 12

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 03:44 AM

View PostKakerergodt, on 31 May 2012 - 03:39 AM, said:

I'm betting it's this line:
T[] result = (T[])a[length]; // unchecked cast

that gives you an ArrayIndexOutOfBoundsException, there's little point to casting a whole array of one class to another class without iterating through the array, which you do later in the code anyways. But if you want to cast it to type T switch it to:
T[] result = (T[])a; // unchecked cast

But the best way to do it is to switch it to:
T[] result = new T[length];


Swapped it out and it gives me an error pointing to that line..

Error: /Users/jdh428/Documents/Java/LinkedSet.java:211: generic array creation
Was This Post Helpful? 0
  • +
  • -

#7 Kakerergodt  Icon User is offline

  • D.I.C Head

Reputation: 87
  • View blog
  • Posts: 201
  • Joined: 01-May 12

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 03:46 AM

View Postcre8tion, on 31 May 2012 - 03:44 AM, said:

Swapped it out and it gives me an error pointing to that line..

Error: /Users/jdh428/Documents/Java/LinkedSet.java:211: generic array creation

Ahh, didn't test my code first, think it should work if you switch it to this instead:
T[] result = (T[])a; // unchecked cast

Was This Post Helpful? 0
  • +
  • -

#8 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5941
  • View blog
  • Posts: 12,870
  • Joined: 16-October 07

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 03:49 AM

If you have a template type T defined, then this sig probably isn't right.
// because the Ts are different
// public <T>T[] toArray(T[] a){
public <T>T2[] toArray(T2[] a){
	// you've alread been given an array; don't screw with it
    // T[] result = (T[])a[length]; // unchecked cast
	int index = 0;

	Node currentNode = firstNode;
	// in your implementation, how can these not be the same?
	// while ((index < length) && (currentNode != null)) {
	// pick one
	while (currentNode != null) {
		// you're filling a, cast to the result it expects
		// result[index] = (T) currentNode.data;
		a[index++] = (T2)currentNode.data;
		currentNode = currentNode.next;
	}
    return a;
}


Was This Post Helpful? 0
  • +
  • -

#9 cre8tion  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 19
  • Joined: 29-May 12

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 04:00 AM

View Postbaavgai, on 31 May 2012 - 03:49 AM, said:

If you have a template type T defined, then this sig probably isn't right.
// because the Ts are different
// public <T>T[] toArray(T[] a){
public <T>T2[] toArray(T2[] a){
	// you've alread been given an array; don't screw with it
    // T[] result = (T[])a[length]; // unchecked cast
	int index = 0;

	Node currentNode = firstNode;
	// in your implementation, how can these not be the same?
	// while ((index < length) && (currentNode != null)) {
	// pick one
	while (currentNode != null) {
		// you're filling a, cast to the result it expects
		// result[index] = (T) currentNode.data;
		a[index++] = (T2)currentNode.data;
		currentNode = currentNode.next;
	}
    return a;
}



--------------
*** Errors ***
--------------
File: /Users/jdh428/Documents/Java/LinkedSet.java [line: 212]
Error: /Users/jdh428/Documents/Java/LinkedSet.java:212: cannot find symbol
symbol : class T2
location: class LinkedSet<T>
File: /Users/jdh428/Documents/Java/LinkedSet.java [line: 212]
Error: /Users/jdh428/Documents/Java/LinkedSet.java:212: cannot find symbol
symbol : class T2
location: class LinkedSet<T>
File: /Users/jdh428/Documents/Java/LinkedSet.java [line: 224]
Error: /Users/jdh428/Documents/Java/LinkedSet.java:224: cannot find symbol
symbol : class T2
location: class LinkedSet<T>

Here is my full code:
import java.util.*;

public class LinkedSet<T> implements Set<T>, Iterable<T> {
  
  private Node firstNode; //reference to first node in this set
  private Node lastNode; //reference to last node in this set
  private int length;         //number of items in set
  
  //Constructor creates an empty list
  public LinkedSet() {
    firstNode = null;
    lastNode = null;
    length = 0;
  } 
  
 //toString() method
  public String toString(){
      if(isEmpty()) return "{}";
      
      String result = "{";
      
      Node p = firstNode;
      int cnt = 1;
      
      while(cnt < length){
          result += p.data + ", ";
          cnt++;
          p = p.next;
      }
      
      result += p.data + "}";
      
      return result;
  }
  /* Method to add a new item
   * @param T newItem
   * 
   */
  public boolean add(T newItem){
    Node newNode = new Node(newItem);
    if (firstNode == null) {
      firstNode = newNode;
      lastNode = firstNode;
      length++;
      return true;
    }
    if (contains(newItem))
      return false;
    lastNode.next = newNode;
    lastNode = newNode;
    length++;
    return true;
  } //end add()
  
  /* Method to add a collection of items
   * @param Collection c
   * 
   */
  public boolean addAll(Collection c) {
    boolean result = false;
    for (Object item : c) {
      if (!contains(item)) {
       add((T)item);
       result = true;
      }
    }
    return result;
  } //end addAll()
  
  /* A method to clear the list
   * 
   */
  public void clear() {
    firstNode = null;
    lastNode = null;
    length = 0;
  } //end clear()
  
  public Iterator<T> iterator() {
    return new LinkedSetIterator();
  }
  
  public boolean contains(Object newItem) {
    boolean found = false;
    Node currentNode = firstNode;
     while(!found && currentNode != null) {
      if (newItem.equals(currentNode.data))
        found = true;
      currentNode = currentNode.next;
    } //end while loop
    return found; 
    } //end contains()
       
  public boolean containsAll(Collection c) {
    boolean result = false;
    for (Object item : c)
      if (contains(item))
      result = true;
    return result;
  } //end containsAll()
  
  public boolean equals(Object item) {
    boolean result = false;
    if (item == null)
      result = false;
    else if (this == item)
      result = true;
    else if ( !(item instanceof LinkedSet) )
      result = false;
    else {
      LinkedSet that = (LinkedSet) item;
  //return
      Node currentNodeThis = this.firstNode;
      Node currentNodeThat = that.firstNode;
      
      while (currentNodeThis != null && currentNodeThat != null && result == false){
        result = currentNodeThis.data.equals(currentNodeThat.data);
        currentNodeThis = currentNodeThis.next;
        currentNodeThat = currentNodeThat.next;
      }
      
    }
       
      return result;
        
  } //end equals()
  
  /*
   * Method to return int hashCode() of set
   * 
   * Adds hashCode of each indivdiaul node.data & takes the sum
   * 
   */
  public int hashCode() {
    int hashCode = 0;
    Node currentNode = firstNode;
    
    while(currentNode !=null){
      hashCode += currentNode.data.hashCode();
      currentNode = currentNode.next;
    } 
    
    return hashCode;
  } //end hashCode()
  
  public boolean isEmpty() {
    return length == 0;
  } //end isEmpty()
  
  public boolean remove (Object anEntry) {
  boolean result = false;
  Node currentNode = firstNode;
  Node previousNode = firstNode;
         while (!result && (currentNode != null)){
           if (anEntry.equals(firstNode.data)) {
             result = true;
             firstNode = firstNode.next;
             length--;
             break;
           }
           else if (anEntry.equals(currentNode.data)) {
                 result = true;
                 previousNode.next = currentNode.next;
                 length--;
                 break;
           }
               else {
                 previousNode = currentNode;
                 currentNode = currentNode.next;
               }
         }
         return result;
       } // end remove()
  
  public boolean removeAll(Collection c){
    boolean result = false;
    for (Object anEntry : c)
      remove(anEntry);
    result = true;
    return result;
  } //end removeAll()
  
  public boolean retainAll(Collection c){
    this.clear();
    for (Object item : c)
      this.add((T) item);
     return true;
  } //end retainAll()
  
  public int size(){
    return length;
  } // end size()
  
  public T[] toArray(){
   @SuppressWarnings("unchecked")
        T[] result = (T[])new Object[length]; // unchecked cast
        int index = 0;
        
        Node currentNode = firstNode;
        while ((index < length) && (currentNode != null)) {
          result[index] = currentNode.data;
          
          index++;
          currentNode = currentNode.next;
        } // end while
        
        return result;
      } // end toArray()
  
// because the Ts are different
// public <T>T[] toArray(T[] a){
public <T>T2[] toArray(T2[] a){
 // you've alread been given an array; don't screw with it
    // T[] result = (T[])a[length]; // unchecked cast
 int index = 0;

 Node currentNode = firstNode;
 // in your implementation, how can these not be the same?
 // while ((index < length) && (currentNode != null)) {
 // pick one
 while (currentNode != null) {
  // you're filling a, cast to the result it expects
  // result[index] = (T) currentNode.data;
  a[index++] = (T2)currentNode.data;
  currentNode = currentNode.next;
 }
    return a;
}



  
  private class Node {
    private T data; //data of the node
    private Node next; //next node
    
    private Node(T dataPortion) {
      this(dataPortion,null);
    } //end constructor
    
    private Node(T dataPortion, Node nextNode){
      data = dataPortion;
      next = nextNode;
    } //end constructor
  } //end Node class
  
  private class LinkedSetIterator implements Iterator<T>{
    private int current;
    private Node currentNodeIt;
    
    LinkedSetIterator() {
      current = 0;
      currentNodeIt = firstNode;
    }
    
    public boolean hasNext() {
      return current < length;
    }
    
    public T next() {
      if (!hasNext()) 
        throw new NoSuchElementException();
        T itemIt = currentNodeIt.data;
        current++;
        currentNodeIt = currentNodeIt.next;
        return itemIt;
    }
       
    public void remove() {
      throw new UnsupportedOperationException();
    }

  } //end LinkedSetIterator
} //end LinkedSet

  

Was This Post Helpful? 0
  • +
  • -

#10 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2833
  • View blog
  • Posts: 12,000
  • Joined: 20-September 08

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 04:04 AM

What exactly is the objective of that method that is now not compiling?
Was This Post Helpful? 0
  • +
  • -

#11 cre8tion  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 19
  • Joined: 29-May 12

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 04:06 AM

View Postg00se, on 31 May 2012 - 04:04 AM, said:

What exactly is the objective of that method that is now not compiling?


http://docs.oracle.c...tml#toArray%28T[]%29

toArray

<T> T[] toArray(T[] a)

Returns an array containing all of the elements in this set; the runtime type of the returned array is that of the specified array. If the set fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this set.

If this set fits in the specified array with room to spare (i.e., the array has more elements than this set), the element in the array immediately following the end of the set is set to null. (This is useful in determining the length of this set only if the caller knows that this set does not contain any null elements.)

If this set makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.

Like the toArray() method, this method acts as bridge between array-based and collection-based APIs. Further, this method allows precise control over the runtime type of the output array, and may, under certain circumstances, be used to save allocation costs.

Suppose x is a set known to contain only strings. The following code can be used to dump the set into a newly allocated array of String:

String[] y = x.toArray(new String[0]);

Note that toArray(new Object[0]) is identical in function to toArray().

Specified by:
toArray in interface Collection<E>

Parameters:
a - the array into which the elements of this set are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.
Returns:
an array containing all the elements in this set
Throws:
ArrayStoreException - if the runtime type of the specified array is not a supertype of the runtime type of every element in this set
NullPointerException - if the specified array is null
Was This Post Helpful? 0
  • +
  • -

#12 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2833
  • View blog
  • Posts: 12,000
  • Joined: 20-September 08

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 04:08 AM

Sorry - didn't notice you were implementing an API interface
Was This Post Helpful? 0
  • +
  • -

#13 Kakerergodt  Icon User is offline

  • D.I.C Head

Reputation: 87
  • View blog
  • Posts: 201
  • Joined: 01-May 12

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 04:32 AM

Your question was actually a bit more tricky than I first thought, but this should do the trick:
public <T>T[] toArray(T[] arrayType)
{
	Object[] original = toArray();
	T[] result = Arrays.copyOf(arrayType, original.length);

	for(int i = 0; i < original.length; i++)
	{
		result[i] = (T)original[i];
	}
	return result;
}


Tried it by implementing it on a class that extended LinkedList, and it worked great, but it's probably not the most elegant solution.
Was This Post Helpful? 2
  • +
  • -

#14 cre8tion  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 19
  • Joined: 29-May 12

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 04:40 AM

View PostKakerergodt, on 31 May 2012 - 04:32 AM, said:

Your question was actually a bit more tricky than I first thought, but this should do the trick:
public <T>T[] toArray(T[] arrayType)
{
	Object[] original = toArray();
	T[] result = Arrays.copyOf(arrayType, original.length);

	for(int i = 0; i < original.length; i++)
	{
		result[i] = (T)original[i];
	}
	return result;
}


Tried it by implementing it on a class that extended LinkedList, and it worked great, but it's probably not the most elegant solution.


Thanks everyone for all the help. This worked =))))
Was This Post Helpful? 0
  • +
  • -

#15 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5941
  • View blog
  • Posts: 12,870
  • Joined: 16-October 07

Re: Implementing Set <T>T[] toArray(T[] a)

Posted 31 May 2012 - 05:59 AM

View PostKakerergodt, on 31 May 2012 - 07:32 AM, said:

probably not the most elegant solution.


The way Java handles generics in respect to arrays ain't all that elegant. Nice work around.

Now I was confused as to why the array was passed at all. A full implementation is a little wonky.
toArray

Quote

<T> T[] toArray(T[] a)

Returns an array containing all of the elements in this set; the runtime type of the returned array is that of the specified array. If the set fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this set.

If this set fits in the specified array with room to spare (i.e., the array has more elements than this set), the element in the array immediately following the end of the set is set to null.
-- http://docs.oracle.c...a/util/Set.html


Also, I saw this question before, the implementation of Set and Iterable. So:
public class LinkedSet<T> implements Set<T>, Iterable<T> {
	@Override
	public <T2> T2[] toArray(T2[] ts) {
		int size = this.size();
		if (ts.length>size) { ts = Arrays.copyOf(ts, size); }
		int i = 0;
		// if we implement Iterable, use it.
		for(T item : this) { ts[i++] = (T2)item; }
		if (size<ts.length) { ts[size] = null; }
		return ts;
	}




Which is why I mentioned the T2 thing, but I buggered it in the first post. :P Still, I think it's a good idea to avoid type confusion.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2