Tuesday, July 13, 2010

Why am I writing lower_bound() in Java again?

The second and the third time I find myself looking for a lower_bound() function according to generally accepted STL standard, I know that I'm not a Java-type developer. Java developers must have no need for these functions that I find very useful. A search for "java lower bound" or "java upper bound" does not yield the predictable result.

The Apache commons has some good collections utilities but not the lower_bound(), upper_bound() pair.

It is still a mystery why the Java Lib folks decided to ignore this function. The use of it is quite common for look-up tables. Today, I wanted to use these functions to look up for some limit values for input ranges from a table. The easiest way to explain this is that different input ranges require a look-up into a number determined by the range. The ranges are consecutive, say 0-25, 25-50, 50-100,100-500. Each range would map to a number, say 100, 212, 320, 400. The look-up function needs to return the correct number given an input number within a range.

For ex:

10 : 100
25 : 212
30 : 212
200 : 400

To satisfy the lower_bound, upper_bound standard specs, a number below the smallest range (say -10) would map to 100, and a number above the largest range will map to nothing.

lower_bound() should return an index to the first element in the sorted container that is equal to or above the number being looked up, and -1 if there is no such element.

upper_bound() should return an index to the first element in the sorted container that is above the number being looked up, and -1 if there is no such element.

Here are the functions I ended up writing:

    public static int lower_bound(Comparable[] arr, Comparable key) {
        int len = arr.length;
        int lo = 0;
        int hi = len-1;
        int mid = (lo + hi)/2;
        while (true) {
            int cmp = arr[mid].compareTo(key);
            if (cmp == 0 || cmp > 0) {
                hi = mid-1;
                if (hi < lo)
                    return mid;
            } else {
                lo = mid+1;
                if (hi < lo)
                    return mid<len-1?mid+1:-1;
            }
            mid = (lo + hi)/2;
        }
    }

    public static int upper_bound(Comparable[] arr, Comparable key) {
        int len = arr.length;
        int lo = 0;
        int hi = len-1;
        int mid = (lo + hi)/2;
        while (true) {
            int cmp = arr[mid].compareTo(key);
            if (cmp == 0 || cmp < 0) {
                lo = mid+1;
                if (hi < lo)
                    return mid<len-1?mid+1:-1;
            } else {
                hi = mid-1;
                if (hi < lo)
                    return mid;
            }
            mid = (lo + hi)/2;
        }
    }

Here are the tests:

    public void test_lower_bound() {
        final int arrSize = 500;
        final int maxNum = 1000;
        Integer[] bArr = new Integer[arrSize];
        Random r = new Random();
        for (int k=0; k<arrSize; k++) {
            bArr[k]=r.nextInt(maxNum);
        }
        Arrays.sort(bArr);

        final int numIter = 2000;
        for (int k=0; k<numIter; k++) {
            int n = r.nextInt(maxNum);
            int j = Utils.lower_bound(bArr, n);
            assertTrue((bArr[arrSize-1]<n && j==-1) || (bArr[j]>=n && (j==0 || bArr[j-1]<n)));
        }
    }

    public void test_upper_bound() {
        final int arrSize = 500;
        final int maxNum = 1000;
        Integer[] bArr = new Integer[arrSize];
        Random r = new Random();
        for (int k=0; k<arrSize; k++) {
            bArr[k]=r.nextInt(maxNum);
        }
        Arrays.sort(bArr);

        final int numIter = 2000;
        for (int k=0; k<numIter; k++) {
            int n = r.nextInt(maxNum);
            int j = Utils.upper_bound(bArr, n);
            assertTrue((bArr[arrSize-1]<=n && j==-1) || (bArr[j]>n && (j==0 || bArr[j-1]<=n)));
        }

    }

Saturday, July 10, 2010

beware of NoClassDefFoundError in java.util.Concurrent callbacks

If you use a particular class inside a Callable method used with java concurrency, and that class happens to be missing, it is likely that the NoClassDefFoundError thrown will be captured by the concurrency library and a different exception - ExecutionException - being thrown.

This can catch you by surprise - pun intended, and could involve some time in debugging, specially as this could happen after code is deployed on a new machine which has a missing jar, for example.

Here is an example of the issue:

    class Work implements Callable<Pair<String,byte[]>> {
        private String domain;
        public Work(String dom) {
            this.domain = dom;
        }
        public Pair<String, byte[]> call() {
            try {
                return new Pair<String, byte[]>(domain, InetAddress.getByName(domain).getAddress());
            } catch (UnknownHostException e) {
                return null;
            } catch (Exception e) {
                System.err.println("unexpected DNS error for: " + domain + " "+e.getMessage());
                return null;
            }
        }
    }


  //caller code

  ExecutorService pool = Executors.newFixedThreadPool(16);
  Future<Pair<String,byte[]>> future = pool.submit(new Work("http://lynx.com"));
  
  //sometime later, retrieve the future...

  if (future.isDone()) {
    try {
      Pair<String,byte[]> pair = future.get();
      if (pair != null) {
        //work with the results
      }

    } catch (ExecutionException e) {
        System.err.println("thread pool error " + e.getMessage());
    } catch (InterruptedException e) {
        System.err.println("thread pool interrupted " + e.getMessage());
    }
  } 

Here, the scenario is that the Pair class is missing. This class is invoked in the Callable method that returns the result from the thread to the caller. When the caller issues the future.get() call, the concurrency library calls the Callable.call() method, which then causes the JVM to throw the NoClassDefFoundError. The concurrency library dutifully catches this and re-throws the ExecutionException.

It pays to catch the ExecutionException and trace it in your code, even if you would never run the application in resource-tight scenarios when you really have to worry about catching these.

If the ExecutionException was not handled, this application would not fail visibly, but will likely not do what was intended.

Friday, July 09, 2010

block quotes in bash

:<<supercalifragilisticexpialidocious
echo oki doki goobledi loks
supercalifragilisticexpialidocious

The long string better not appear in the block. It could be any string of your choosing.