// generic bubble sort in Java
// ArrayList version written Mar 00 by Ulrich Stern
// alek: added timings

import java.util.ArrayList;
import java.util.Date;

interface Comparator {
    boolean compare(Object o1, Object o2);
}


public class SortArrayList {

    static class Lib {
        static void sort(ArrayList a, Comparator cmp) {
            for (int i=0; i<a.size()-1; i++)
                for (int j=a.size()-1; j>i; j--)
                    if (! cmp.compare(a.get(j-1), a.get(j))) {
                        Object tmp = a.get(j-1);
                        a.set(j-1, a.get(j));
                        a.set(j, tmp);;
                    }
        }
    }
    static class Range {
        int lb;
        int ub;
        Range(int l, int u) {
            lb = l;  ub = u;
        }
        public String toString() {
            return "[" + lb + "," + ub + "]";
        }
    }

    // compare lower bound
    static class LBComparator implements Comparator {
        public boolean compare(Object o1, Object o2) {
            return (((Range)o1).lb < ((Range)o2).lb);
        }
    }

    // compare upper bound
    static class UBComparator implements Comparator {
        public boolean compare(Object o1, Object o2) {
            return (((Range)o1).ub < ((Range)o2).ub);
        }
    }

    public static void main(String[] args) {
        final int REPEAT = 10;

        final int N = 10000;
        ArrayList a = new ArrayList(N);
        for (int i=0; i<N; i++) {
            a.add(i, new Range(i*7%1000, i*13%1000));
        }

        //System.out.println("sorting (" + a.size() + " Ranges)...");
        System.out.println("sorting N="+N+" REPEAT="+REPEAT+" ...");
        System.out.println( "started at " + new Date()  );

        long stime = System.currentTimeMillis();

        for(int count = 0; count < REPEAT; ++count) {
            Lib.sort(a, new LBComparator());
            Lib.sort(a, new UBComparator());
        }

        long etime = System.currentTimeMillis();
        System.out.println( "finished at " +new Date()+" in "+((double)(etime-stime)/1000.0)+" sec");
        //System.out.println("done.");
    }
}