Sorting Loop in Java

Question

There is a list of objects I need to add to a grid without receiving an IndexOutOfBoundsException. Each object has two numbers associated with it which corresponds to it's index and column position in a grid. There can be 3 columns and unlimited rows. I need to call add() method for this grid but only in the correct order, so :

(0,0),(0,1),(0,2),(1,0)...

The grid would therefore look like this:

  0 1 2
0 x x x
1 x x x
2 x x x
3 x x x

I must also take into account the chance that no object exists for a certain position. For example:

A) x x x  B) x   x   C) x x x
   x x x     x   x        x x
   x   x         x        x
   x   x         x        x
   x   x

Can this be done? I'm not sure where to start.

Per [this question](http://stackoverflow.com/questions/416266/sorted-collection-in-java), you may want to consider the [PriorityQueue](http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html). OTOH, if the number of items in the list isn't likely to be too high, you may want to consider [insertion sort](http://en.wikipedia.org/wiki/Insertion_sort). — GreenMatt, Jan 11 '11 at 15:32
I don't understand where the whole "sorting" topic comes into play. It's in your question title and in your tags but not in your question itself. — Mark Peters, Jan 11 '11 at 15:36

score 3 · Answer 1 · answered Jan 11 '11 at 15:26

What you are looking for is probably a sparse matrix implementation.

One of the most simple implementations of this is the dictionary-of-keys approach, which is basically a table linking coordinates to an object. Something like this:

Map<Point, T> grid = new HashMap<Point, T>();
grid.put(new Point(5, 2), myObj);

Point would be a class you implement containing a column and index field, with hashCode() and equals() properly implemented. Or, if you're really lazy, you could hack it by using java.awt.Point.

You could encapsulate this within an interface similar to the one suggested by @sblundy. I'd suggest something like this:

public interface Grid<T> {
   public T set(int column, int index, T val);
   public T get(int column, int index);
   //other optional methods
}

Where does the `Point` class come into play? Would I loop `HashMap.entryset()` and it will be in the order? — Federer, Jan 11 '11 at 16:03
@BlueMalc: It would come into play for storing and retrieving the object. It wouldn't make any guarantees about iterating over the keys. You didn't mention anything like that in your post. — Mark Peters, Jan 11 '11 at 16:21

score 3 · Accepted Answer · edited May 23 '17 at 12:34

Maybe you should think about another datastructure that stores objects by (row,column). It's interface would look like

public interface GridModel {
  void set(int row, int column, Object o);
  Object get(int row, int column)
}

And than you can use a list of lists to store the data. List<List<Object>> or, as Mark Peters suggests, a sparse matrix

If working with the cell values is important, add a cell iterator method. A simple implementation would look like:

public Iterable<Object> cellIterator() {
    final List<Object> items = new java.util.ArrayList<Object>();
    for(final List<Object> row : cells) {
        for(final Object cell: row) {
            items.add(cell);
        }
    }
    return items;
}

If all of the data follows the pattern in the OP's examples (A, B, and C), where in a given column there are no gaps in the filled indices, the list of lists is a better data structure. — Mark Peters, Jan 11 '11 at 15:34

score 0 · Answer 3 · edited May 23 '17 at 09:58

0

The answer to this question may help.

edited May 23 '17 at 09:58

Community

1
1

answered Jan 11 '11 at 15:25

highlycaffeinated

19,729
9
60
91

Sorting Loop in Java

3 Answers3