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

    }

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.

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.

The annoying preciseness of Java : Charset.isSupported

If the charset is supported, return true, else return false - it does sound pretty simple, doesn't it.

It would be simple if the language designers focused on usability vs pristine accuracy. Java, obviously went for the latter.

Thus if you were to ask whether an illegal charset is supported, it won't return false, it will decide to throw the IllegalCharsetNameException exception. How precise.


How annoying. Now when all you wanted was to check for the availability of a charset, suddenly you end up checking for exceptions as well as the return value from Charset.isSupported.


Such is the art of programming in Java.

Jericho Parser new version fixes choking on unusual charset

Each day I find something completely wacko on the Net. Today it is an extremely interesting charset present in the headers of a certain site:

mpire@brwdbs01:~$ curl -I http://uk.real.com/realplayer/
HTTP/1.1 200 OK
Expires: 0
Date: Thu, 13 May 2010 22:44:16 GMT
Content-Length: 2690
Server: Caudium
Connection: close
Content-Type: text/html; charset='.().'
pragma: no-cache
X-Host-Name: hhnode21.euro.real.com
X-Got-Fish: Yes
Accept-Ranges: bytes
MIME-Version: 1.0
Cache-Control: no-cache, no-store, max-age=0, private, must-revalidate, proxy-revalidate

a charset of '.().' Strange indeed. This manages to choke the JerichoParser I'm using and I'm not too sure what to do about it. The parser does a pretty nice job parsing all kinds of encodings, and since it has no idea of this kind, it gives up. I could try and make it use the default (ISO-8859-1).

This has been fixed on a newer version of the Jericho Parser.

Normalizing a URL

Today, I had this interesting problem to do with fetching a web page.
I was processing HTTP meta-refresh headers and ran into this type of header:

<meta http-equiv="REFRESH" content="0; URL=../cgi-bin/main2.cgi">

If I try to turn this into an absolute url (the url this content was fetched being http://popyard.com) I would be trying to do this:

> curl -I http://popyard.com/../cgi-bin/main2.cgi
> HTTP/1.1 400 Bad Request

However, turns out that the browser deals with this just fine. Faced with a malformed URL, it guesses and keeps going, fetching http://popyard.com/cgi-bin/main2.cgi

This required me to do some cleanup of the url to handle this dot segments (..). There is a well-known protocol for doing this. I coded this up simply using a stack based approach.

Here is the code:

    //removes .. sequences from the url string handling extra .. sequences by stopping
    //at the domain, thus always returning a correct url.
    //ex: http://www.ex.com/a/xt/../myspace.html => http://www.ex.com/a/myspace.html
    //    http://www.ex.com/a/xt/../../../myspace.html => http://www.ex.com/myspace.html    
    public static String normalizePath(String url) {
        if (url.indexOf("..") == -1)
            return url; //no .. seqs, no need to normalize
        String[] toks = url.split("/");
        int i;
        for (i=0; i<toks.length && (toks[i].length() == 0 || toks[i].toLowerCase().indexOf(":") != -1); i++);
        if (i==toks.length)
            return url;     //no proper path found, simply return the url
        // toks[i] is the domain

        LinkedList<String> s = new LinkedList<String>();
        for (; i<toks.length; i++) {
            if (!toks[i].equals(".."))
                s.push(toks[i]);
            else if (s.size()>1)
                s.pop();
        }

        if (s.size()<1)
            return url;     //no proper domain found, simply return the url

        int idx = url.indexOf("://");
        StringBuilder sb = new StringBuilder();
        sb.append( (idx != -1 ? url.substring(0, idx+3) : "")).append(s.removeLast()); //get proto://domain

        while (s.size()>0) {
            sb.append("/").append(s.removeLast());
        }

        return sb.toString();
    }

Basically, what this code does is strip the url into the domain and the path components and use a stack to manipulate these terms. We push a term onto the stack, unless the term is a dot segment - ".." - in which case, if there is at least two terms on the stack, we pop the first one. This way, we never pop the last term on the stack, which is the domain.

Then we can find the normalized URL following the terms in the stack from bottom to top.

This is the reason we can't really use a stack, as we can't traverse from the bottom to the top. So we use a LinkedList instead.

Interesting performance characteristic in Lucene.Analysis.StopFilter

I was tracking down a slow indexing process and got this callstack with YourKit:




There is a Collection.addAll() being called for each invocation of tokenStream() which is called many times per document. The StopFilter is the culprit. When I checked the constructor, it looks like this:

  public StopFilter(boolean enablePositionIncrements, TokenStream input, Set stopWords, boolean ignoreCase)
  {
    super(input);
    if (stopWords instanceof CharArraySet) {
      this.stopWords = (CharArraySet)stopWords;
    } else {
      this.stopWords = new CharArraySet(stopWords.size(), ignoreCase);
      this.stopWords.addAll(stopWords);
    }
    this.enablePositionIncrements = enablePositionIncrements;
    init();
  }

As you can see, if the stopWords set is not of type org.apache.lucene.analysis.CharArraySet, a whole copy is made. I was using a regular Set for the stopWords and that was the problem.

This was very instructive, as the reason I didn't use lucene's StopFilter.makeStopSet() and used a regular Set was assuming that under the covers Lucene made a regular Set, and I wanted to save it the trouble as I could generate a Set directly from my input.

Another reason to profile, profile and profile....

After changing my code to use the Lucene Set (by calling StopFilter.makeStopSet) here is the result, faster for sure:



The performance improvements could be significant. In a real-world scenario where this code was used in creating a 10G size index, I saw a 4X speed-up in indexing.