// generic bubble sort in Java
// array version written Dec 99 by Ulrich Stern

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

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


public class sort {

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

    Lib.sort(a, new LBComparator());
    Lib.sort(a, new UBComparator());

    System.out.println("done.");
  }
}