// generic bubble sort in C++
// STL / object version Jan 00 by Amit Patel

#include <iostream.h>
#include <vector.h>

template<class Iter, class Comparator>
void mysort(Iter a, Iter b, Comparator cmp) {
  for(Iter i=a; i+1 != b; ++i)
    for(Iter j=b-1; j!=i; --j)
      if(!cmp(*(j-1), *j)) swap(*(j-1), *j);
}

struct Range {
  int lb, ub;
  Range() {}
  Range(int l, int u): lb(l), ub(u) {}
};

ostream& operator << (ostream& out, const Range& r) {
  return out << '[' << r.lb << ',' << r.ub << ']';
}

struct LBComparator {
  bool operator() (const Range& a, const Range& b) const {
    return a.lb < b.lb;
  }
};

struct UBComparator {
  bool operator() (const Range& a, const Range& b) const {
    return a.ub < b.ub;
  }
};

int main() {
  const int N = 10000;
  vector<Range> a(N);

  for(int i=0; i<N; i++)
    a[i] = Range(i*7%1000, i*13%1000);

  cout << "sorting...\n";  cout.flush();

  mysort(a.begin(), a.end(), LBComparator());
  mysort(a.begin(), a.end(), UBComparator());

  cout << "done.\n";  cout.flush();
}