Saturday, July 23, 2011

The story of the ArrayList imposter

Each and everyone of us, undoubtedly has had used Array lists in our lives as programmers. This story is about an imposter who lives among us, unnoticed, undetected until WHAM you are presented with a bug that makes no sense. Let me give you an example to reveal this imposter :). I have a hypothetical system that stores information on games and their ratings. A glimpse of the DTO i would use is as follow;


/**
 * A class to hold basic data about game titles
 * @author dinuka
 *
 */
public class Game  {

	/**
	 * The name of the game
	 */
	private String title;
	/**
	 * The rating users have given the game
	 */
	private int rating;
	
	public Game(String title,int rating){
		this.title = title;
		this.rating = rating;
	}

	public String getTitle() {
		return title;
	}

	public void setTitle(String title) {
		this.title = title;
	}

	public int getRating() {
		return rating;
	}

	public void setRating(int rating) {
		this.rating = rating;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + rating;
		result = prime * result + ((title == null) ? 0 : title.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Game other = (Game) obj;
		if (rating != other.rating)
			return false;
		if (title == null) {
			if (other.title != null)
				return false;
		} else if (!title.equals(other.title))
			return false;
		return true;
	}

	@Override
	public String toString() {
		return "Game [title=" + title + ", rating=" + rating + "]";
	}
	
	
}

Nothing fancy. Just a plain old data holder value object with customary getter/setter methods. I have overriden equals,hashcode and tostring methods because i usually do that as a principal :). Ok moving on to reveal the culprit i will present you with a sample code and run the code and show you the problem at hand;


import java.util.Arrays;
import java.util.List;


public class Test {

	
	public static void main(String[] args) {

		Game[]gameArr = new Game[3];
		
		gameArr[0] = new Game("Metal gear solid 4",8);
		
		gameArr[1] = new Game("Unchartered 2",6);
		
		gameArr[2] = new Game("NFS Underground",2);
		
		Game[]newGameList = manipulateGames(gameArr);
		
		
	}
	
	/**
	 * Here we delete low rating games
	 * and add new game titles in place of those games
	 * @param gameArr
	 */
	private static Game[] manipulateGames(Game[]gameArr){
		List<Game>gameList = Arrays.asList(gameArr);
		
		for(int i=0;i<gameList.size();i++){
			Game game = gameList.get(i);
			if(game.getRating()<5){
				gameList.remove(game);
				Game newGame = new Game("NFS Hot pursuit 2",7);
				gameList.add(newGame);
			}
		}
		Game[]newArr = new Game[gameList.size()];
		return gameList.toArray(newArr);
	}
}


Ok these are my personal ratings i have given for the few of the games i love. Hopefully no one will take them personally because i do not want you to get off the topic here ;). So what we are doing here is, we have an array of games which we pass into a method which looks at the games with ratings lower than 5 and removes them and adds new games as substitutes. Do not consider implementation details as that is not my intention. My intention is to show you the problem at hand. So lets run this code and see what we get.

Ok what just happened? We get this really awkward error saying Unsupported exception. When i first got this i was thinking that maybe a previous version of java did not support removing from list given the object because i was at work using JDK 1.4 for work related things. But jdeclipse came to my help. If anyone has not used it, i can guarantee that it is one of the most useful plugins and a faithful companion in my eclipse workbench. Its a java decompiler which can decompile class files. Its much easier than downloading the JDK source and linking it.

I wanted to see the implementation of the Arrays.asList() method. This is where i found our little ArrayList imposter.....


public static <T> List<T> asList(T[] paramArrayOfT)
  {
    return new ArrayList(paramArrayOfT);
  }


By the looks of it, there is nothing implicitly wrong with this implementation. So most probably it should be a problem with the ArrayList. Lets see whats happening there;


private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, Serializable
  {
    private static final long serialVersionUID = -2764017481108945198L;
    private final E[] a;

    ArrayList(E[] paramArrayOfE)
    {
      if (paramArrayOfE == null)
        throw new NullPointerException();
      this.a = paramArrayOfE;
    }

    public int size()
    {
      return this.a.length;
    }

    public Object[] toArray()
    {
      return ((Object[])this.a.clone());
    }

    public <T> T[] toArray(T[] paramArrayOfT)
    {
      int i = size();
      if (paramArrayOfT.length < i)
        return Arrays.copyOf(this.a, i, paramArrayOfT.getClass());
      System.arraycopy(this.a, 0, paramArrayOfT, 0, i);
      if (paramArrayOfT.length > i)
        paramArrayOfT[i] = null;
      return paramArrayOfT;
    }

    public E get(int paramInt)
    {
      return this.a[paramInt];
    }

    public E set(int paramInt, E paramE)
    {
      Object localObject = this.a[paramInt];
      this.a[paramInt] = paramE;
      return localObject;
    }

    public int indexOf(Object paramObject)
    {
      int i;
      if (paramObject == null)
        for (i = 0; i < this.a.length; ++i)
          if (this.a[i] == null)
            return i;
      else
        for (i = 0; i < this.a.length; ++i)
          if (paramObject.equals(this.a[i]))
            return i;
      return -1;
    }

    public boolean contains(Object paramObject)
    {
      return (indexOf(paramObject) != -1);
    }
  }

Huh what is that?? Its an inner class extending the AbtractList class,residing within the Arrays class baring the name ArrayList. The problem here is that it does not override all methods available within AbtractList thus throwing the UnsupportedException as defined within the class AbtractList .

Why they have done this im not really sure. It maybe because they are syncing the Array you passed initially and what ever update you do, is done to the original Array you passed in. But why chose such an implementation is a question mark for me.

So if you ever want to remove elements when using an ArrayList composed using Arrays.asList make sure to wrap it with a call such as newArrayList(Array.asList(myArr)); This will guarantee that you will use the concrete ArrayList implementation and not our imposter we just discovered.


So that ends the story of the ArrayList imposter that bothered me last week at work :)


Thank you for reading and hope you guys have a peaceful day of coding!!!