Java dynamic 2D matrix

l would like to create a dynamic 2D matrix, where the number of rows and columns is unknown. Filling it by adding one element at the time. For example, 1st button clic开发者_开发知识库k = M[1][1] (at this time, the matrix contains only this element), then M[1][2], [1][3]....etc.

Use collections to do this. For example:

List<List<Integer>> dynamic2D = new ArrayList<List<Integer>>();

dynamic2D.add(new ArrayList<Integer>());
dynamic2D.add(new ArrayList<Integer>());
dynamic2D.add(new ArrayList<Integer>());

dynamic2D.get(0).add(5);
dynamic2D.get(0).add(6);
dynamic2D.get(0).add(7);

System.out.println(dynamic2D.get(0).get(0)); // 5
System.out.println(dynamic2D.get(0).get(1)); // 6
System.out.println(dynamic2D.get(0).get(2)); // 7

Here's one option to consider to keep your 2D array fast for processing. It starts with a fixed size array of int[][] and grows only as necessary:

public class DynamicMatrix2D {
    private int[][] matrix = new int[5][5];

    public void set(int x, int y, int value) {
        if (x >= matrix.length) {
            int[][] tmp = matrix;
            matrix = new int[x + 1][];
            System.arraycopy(tmp, 0, matrix, 0, tmp.length);
            for (int i = x; i < x + 1; i++) {
                matrix[i] = new int[y];
            }
        }

        if (y >= matrix[x].length) {
            int[] tmp = matrix[x];
            matrix[x] = new int[y + 1];
            System.arraycopy(tmp, 0, matrix[x], 0, tmp.length);
        }

        matrix[x][y] = value;
    }

    public int get(int x, int y) {
        return x >= matrix.length || y >= matrix[x].length ? 0 : matrix[x][y];
    }

    public static void main(String[] args) {
        DynamicMatrix2D matrix2d = new DynamicMatrix2D();

        matrix2d.set(1, 1, 1);     // set (1, 1) to 1
        matrix2d.set(10, 10, 2);   // set (10, 10) to 2
        matrix2d.set(100, 100, 3); // set (100, 100) to 3

        System.out.println(matrix2d.get(1, 1));     // outputs 1
        System.out.println(matrix2d.get(10, 10));   // outputs 2
        System.out.println(matrix2d.get(100, 100)); // outputs 3 
    }
}

You could (1) use a hash map which maps points to button states and have the maximum number of rows and columns stored in separate variables; alternatively, you could (2) use a tree and have one node for each row, and add nodes to the corresponding row nodes to represent matrix entries.

You could also (3) use an ordered, dynamic list (array list, linked list, etc.) of integers, where the first n bits of each integer can store the row, the next n bits the column, and the rest of the bits any data pertaining to the state of the button. The size of n, however, depends on what your maximum bounds for the number of rows and columns are. Use bitwise operators to extract relevant data when you retrieve an element from the list.

The amount of memory allocated would be least for (3) if an array list is used, but otherwise, each entry will have some extra data associated with it when you add extra elements, due to the nature of the data structure. Searching would be fastest with (1); both (2) and (3) should exhibit O(log(n)) searching times, but I would suspect that (3) would be significantly faster because of the data locality. Of approaches (1) and (2), adding and removing elements would be fastest with (1); the time it takes for approach (3) to add or remove an element depends on the implementation of the list.

I'm sure there's plenty of other structures which you could use that I haven't listed here, but you may want to note that if you can guarantee that the number of rows and columns will remain within reasonable bounds, then using a static data structure could really speed things up.