// generic bubble sort in Java
// array version written Dec 99 by Ulrich Stern
// alek: added timing

import java.util.Date;

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


public class Sort {

    static class Lib {
        static void sort(Object[] a, Comparator cmp) {
            for (int i=0; i<a.length-1; i++)
                for (int j=a.length-1; j>i; j--)
                    if (! cmp.compare(a[j-1], a[j])) {
                        Object tmp = a[j-1];
                        a[j-1] = a[j];
                        a[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;
        Range[] a = new Range[N];
        for (int i=0; i<a.length; i++) {
            a[i] = new Range(i*7%1000, i*13%1000);
        }

        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");
    }
}