Java: sort a list of lists

Question

I have a list of lists of points ie: List<List<Point>>. e.g.:

List<Point> lp;
List<List<Point>> Llp;
Llp.add(lp);

lpwould be the first line of my matrix (x=0). Llpis the whole matrix.

I want to get the list ascendingly sorted according to both x and y of each point. I only managed to get the internal list sorted but not the whole list. Can anyone help me please? Thank you. Here is my code to sort the internal list (ie. the first line of the matrix) according to y.

private void ord_horiz (List<Point> tab)
{
    boolean ordered_horiz = false;
    int size = tab.size();

    while(!ordered_horiz)
    {
        ordered_horiz = true;

        for(int i=0 ; i < size-1 ; i++)
        {
            if(tab.get(i).y > tab.get(i+1).y)
            {
                swap(tab, i, i+1);
                ordered_horiz = false;
            }
        }
        size--;
    }   
}

private void swap(List<Point> tab, int ind1, int ind2) 
{
    Point c;
    c = tab.get(ind1); 
    tab.set(ind1, tab.get(ind2));
    tab.set(ind2, c);
}

Here is the code I wrote so far:

Collections.sort(tab,new Comparator<List<Point>>(){


        @Override
        public int compare(List<Point> o1, List<Point> o2) {
            if(o1 != null && o2 !=null)
            {
                Point var1 = o1.get(0);
                            int var1_x = var1.x;
                            int var1_y = var1.y;
                Point var2 = o2.get(0);
                            int var2_x = var2.x;
                            int var2_y = var2.y;

                            Integer.compare(var1_x, var2_x);
                            Integer.compare(var1_y, var2_y);
                return /* What shall I return ? */;                 
            }
            return 0;
        }
    });

Here is a screenshot of my console output. I want that point to be sorted. http://imageshack.us/scaled/large/515/38zy.png

Answer 1

"I want to sort the external list according to x and y, given that x is the order of lp within Llp and y is the order of the elements of each lp in Llp."

You should use a custom comparator. As I assume each list within LLP has the same number of elements, and each list is only for a distinct X, the following should work:

Example

//Create the Data

    List<List<Point>> Llp = new ArrayList<List<Point>>();

    for(int i=0; i< 50; i++)
    {
        List<Point> lp = new ArrayList<Point>();

        for(int j=0; j<50; j++)
        lp.add(new Point((int)(Math.random()*1000), i));

        Llp.add(lp);
    }



    // The comparators
    Comparator<List<Point>> comparator_rows = new Comparator<List<Point>>() {

        @Override
        public int compare(List<Point> o1, List<Point> o2) {
            int i = o2.get(0).y;
            int j = o1.get(0).y;
            if (i < j) {
                return 1;
            } else if (i > j) {
                return -1;
            } else {
                return 0;
            }
        }

    };

    Comparator<Point> comparator_columns = new Comparator<Point>() {

        @Override
        public int compare(Point o1, Point o2) {
            int i = o2.x;
            int j = o1.x;
            if (i < j) {
                return 1;
            } else if (i > j) {
                return -1;
            } else {
                return 0;
            }
        }

    };

    // Sort the rows
    Collections.sort(Llp, comparator_rows);

    // Sort the columns
    for (List<Point> element : Llp) 
        Collections.sort(element, comparator_columns);

    //Print the elements
    int rowIndex = 0, columnIndex=0;

    for (List<Point> row : Llp) 
    {
        for (Point element : row) 
        System.out.print("("+element.x+ "," + element.y +")|");

        System.out.println();
    }

The above code gets the first element of each row, and extracts the X coordinate. Then this x coordinate is used to sort all the rows.

Update

If your data is all mixed up, you can use the following code that uses TreeMaps to put your elements where they are supposed to be. The result is a jagged array.

//Create the Data

        List<List<Point>> Llp = new ArrayList<List<Point>>();

        for(int i=0; i< 50; i++)
        {
            List<Point> lp = new ArrayList<Point>();

            for(int j=0; j<50; j++)
            lp.add(new Point((int)(Math.random()*1000), (int)(Math.random()*1000)));

            Llp.add(lp);
        }


        //If all data is mixed up we need to filter into new rows based on X using a TreeMap

        TreeMap<Integer, TreeMap<Integer,Point>> data = new TreeMap<Integer,TreeMap<Integer,Point>>();

        for (List<Point> row : Llp) 
        {
            for (Point element : row) 
            {
                TreeMap<Integer,Point> rowForX;
                if(data.containsKey(element.x))
                    rowForX = data.get(element.x);
                else
                    data.put(element.x, rowForX = new TreeMap<Integer,Point>());    
                    //Create specific row in TreeMap

                rowForX.put(element.y,element);
            }           
        }


        //Convert Sorted TreeMap(s) to Lists

        Llp.clear();
        Iterator<Entry<Integer, TreeMap<Integer, Point>>> it = data.entrySet().iterator();

        while(it.hasNext())
            Llp.add(new ArrayList<Point>(it.next().getValue().values()));


        //Print the elements
        int rowIndex = 0, columnIndex=0;

        for (List<Point> row : Llp) 
        {
            for (Point element : row) 
            System.out.print("("+element.x+ "," + element.y +")|");

            System.out.println();
        }