// generic bubble sort in Java
// Vector version written Jan 00 by Ulrich Stern
// alek: added timing

import java.util.Date;
import java.util.Vector;

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

public class SortVector {
    static class Lib {
        static void sort(Vector 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.elementAt(j-1), a.elementAt(j))) {
                        Object tmp = a.elementAt(j-1);
                        a.setElementAt(a.elementAt(j), j-1);
                        a.setElementAt(tmp, j);;
                    }
        }
    }

    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;
        Vector a = new Vector(N);
        a.setSize(N);
        for (int i=0; i<a.size(); i++) {
            a.setElementAt(new Range(i*7%1000, i*13%1000), i);
        }

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