FRIHOST FORUMS SEARCH FAQ TOS BLOGS COMPETITIONS
You are invited to Log in or Register a free Frihost Account!


Java 2D ArrayLists





polly-gone
My current project right now is an implementation of 2D ArrayLists in Java called ArrayListy.

Now, I know it sounds horribly inefficient, but it's not what you think. I have seen a lot of 2D ArrayList classes that are basically just wrappers for manipulating an object declared like

Code:
ArrayList<ArrayList<E>> list = new ArrayList<ArrayList<E>>();


I am doing it the right way, writing it from scratch first with improved standard ArrayList functionality, then with added 2D functionality.

I am also making improvements to the way that it works at the core. For example:

Code:

ArrayList<String> list = new ArrayList<String>();

for(int i = 0; i < 10; i ++)
{
     list.add("" + i);
}

list.add(20, "20"); //this would throw an exception
list.set(30, "30); //this would also throw an exception


My improved functionality works the way that you think it would. If you add to 20, rather than throwing an exception, it would just tack it on to the end of the list. The same with set(). I am also planning on including a constructor with an option to auto fill with a default constructor. This means that if you do list.set(50, "string"), it will fill every space from 10 to 50 with empty strings.

What do you think about this implementation? Do you have anything you would like to see in this implementation?

Let me know, I want ArrayListy to be useful to as many people as possible!

-Nick Smile Smile Smile
Fire Boar
Hm, the thing is, ArrayList is supposed to be sequential. So a 2D ArrayList would quite literally be a sequential list of sequential lists. The trouble here is with ordering: while on a 1-dimensional line the concept of an order makes sense, this breaks down in 2 dimensions. Is (0,1) greater than (1,0)? Who can tell?

It sounds to me like a better representation of an arbitrary n-dimensional grid would be a Map<List<Integer>, E>. You could then wrap this in a 2D grid class as follows:

Code:
class TwoDimensionalGrid<E> extends AbstractCollection<E>
{
  protected Map<List<Integer>, E> map;

  protected List<Integer> _getIndex(int x, int y)
  {
    List<Integer> index = new Vector<Integer>(2);
    index.add(x);
    index.add(y);
    return index;
  }

  public TwoDimensionalGrid()
  {
    map = new HashMap<List<Integer>, E>();
  }

  public Iterator<E> iterator()
  {
    return map.values().iterator();
  }

  public int size()
  {
    return map.size();
  }

  public boolean add(E element) throws UnsupportedOperationException
  {
    // Throw an exception - ordering has no meaning in more than 1 dimension.
    throw new UnsupportedOperationException();
  }

  public void set(int x, int y, E element)
  {
    map.put(_getIndex(x, y), element);
  }

  public E get(int x, int y)
  {
    return map.get(_getIndex(x, y));
  }

  public E remove(int x, int y)
  {
    return map.remove(_getIndex(x, y));
  }
}
polly-gone
I don't really understand what you are saying... an ArrayList isn't supposed to have any particular sort of order. Index 0 can be 287, 1 can be 6, and 2 can be 348724, it doesn't really matter. And each row can be arbitrary, with no relation to the others at all. You won't ever have to compare (0,1) and (1,0).

The idea for this arose when I was writing a radix sorter and having an ArrayList of ArrayLists was a headache and a casting nightmare; I decided to write a 2D ArrayList that would eliminate that problem.

ArrayList is simply an implementation to create dynamically sized arrays. If you create a regular array with a length of 20, to add 25 things to it later down the road, you have to make a new array, copy the old array into it, then add all of the new things. ArrayList does that, but on the fly.

My 2D ArrayList concept is basically just a way of creating and modifying 2D arrays on the fly.

I also don't really understand what you are trying to say with Map<List<Integer>, E>. First of all, Map and List are interfaces, so that just wouldn't work. Now, if you used say, a HashMap and a LinkedList, the implementation still doesn't make sense. The list is stored in the key field of the map, which means that no two lists can be the same. And I'm not exactly sure what you would be storing in the value field. If I wanted to store "Foo" and "Bar" in one row I would say

Code:

list.add("Foo");
list.add("Bar");
map.add(list, ????);


I don't understand what you would put in the value of the map.

That would also be a huge problem because you would have no way of adding multiple rows with the same values.

EDIT: See, the whole issue with your post is ArrayLists being sequential, but that's just not the case.

-Nick Confused Confused Confused
Fire Boar
What I mean is that ArrayLists have an order - they are ordered by keys. If you want to insert something in position 100, you need positions 0 to 99 available. Bit of a waste. The collection "add" method makes no sense in 2D - usually it "adds to the end of the list", but where is the end when you have keys in two dimensions? That's our problem.

About the list/map stuff, I see you don't quite understand where I'm getting. It's generally good practice to refer to the most general type possible - that way, if HashMap (see constructor) doesn't cut it, all you'd need to do is change the map type. Same with Vector as the concrete List, used in _getIndex. There is no need (and it's considered bad practice) to refer to the concrete type anywhere except where you actually instantiate the object. So having variables around of type Map<List<Integer>, E> is absolutely fine, you just can't say "new Map<List<Integer>, E>": you have to choose which type of Map you're going to use.

Correct me if I'm wrong, but I seem to recall that the generic Map goes by <Key, Value>, not <Value, Key>. In that case, adding your values via the list makes no sense and indeed is not allowed by the class. The list is, when turned into a concrete type, a 2D vector which indicates the coordinates - that's the position in the grid. The type E is the value, so TwoDimensionalGrid<String> is a wrapper for Map<List<Integer>, String> and would allow insertion of String data.

Here's an example usage of the class above:

Code:
TwoDimensionalGrid<String> grid = new TwoDimensionalGrid<String>();
grid.set(2, 6, "Foo"); // Inserts "Foo" into position (2,6).
System.out.println(grid.size()); // 1
grid.set(2, 6, "Bar"); // Inserts "Bar" into position (2,6), overwriting "Foo".
System.out.println(grid.size()); // Still 1
System.out.println(grid.get(2, 6)); // "Bar"
grid.add("Baz"); // Throws an exception, since we've got no idea where to put it.


There are contexts in which a 2D ArrayList is useful, but in all cases where I think that would be better than having a grid like the TwoDimensionalGrid class, it's because the arrays in the outer array are required to maintain all of their elements (e.g. if you had [[a,b,c],[c,d,e]] then [a,b,c] and [c,d,e] may be swapped, but shouldn't exchange elements). That is, you have an array of distinct objects that just happen to be arrays.

As for Radix sorting, I'm not really sure what you'd need a list of lists for at all. Start with a list and then... maybe turning ArrayList<String> into ArrayList<ArrayList<Integer>> or something? But then as far as I can see the arrays need not be resizable at all. I don't really have much to say on that without knowing how you were trying to do it and where the headaches were. I'll just say I think there's probably an easier way that doesn't require 2D variables.
polly-gone
Well, the entire thing is basically just an improvement on the basic ArrayList concept. You don't need it to be "ordered" and there would be methods that can handle 2D manipulation:

Code:
public boolean add2D(int row, Object o);
public boolean add2D(int row, int col, Object o);
public E get(int row, int col);


The entire point of an ArrayList is to have a quick and easy way to dynamically alter arrays; a 2D array list would do that, but it would be in 2 dimensions! The entire purpose of this project was really just to come up with a better method of having a 2D ArrayList. If you Google it, most of the implementations you will find are just an ArrayList of ArrayLists inside of a wrapper class, which is actually very, very inefficient.

-Nick Smile Smile Smile
Fire Boar
Hm, I'm curious now, how are you storing your data? As you say, a list of lists is horribly inefficient.
Peterssidan
A 2D ArrayLists can be used for maps, game boards and things like that. These things rarely need to change size. A chessboard will stay 8x8 squares whatever happens. They are grids!

If this is the things it will be used for it is not important to have it resizable. If you want you could have an resize method but speed is not very important here.

It can be a wrapper around a plain array T[] or ArrayList<T> if you like.

This is the usages I see for a 2D array/arraylist. Maybe you see other usages for it and therefore wants it dynamically resizable.
Related topics
Java Game
Java
Add to favorites script - Java
Problems with Java
Java Programming Introductory
Language
DSP Tutorial with Java Applets
Java
[JAVA TUTORIALS & FILES] - Java Scripting world
Java tutorials
Java tutorials
The Game creation topic! - Share experience - Find resources
Java/C++ helpers
Java, python, or c++?
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2011 Frihost, forums powered by phpBB.