Java frameworks, encapsulation and code bloat, i.e., the javabean specification failed us!

I have recently run into the following error in my JAX-RS application running in Jersey 2.6 (on Tomcat 6):

 Failed to generate the schema for the JAX-B elements  
 com.sun.xml.internal.bind.v2.runtime.IllegalAnnotationsException: 1 counts of IllegalAnnotationExceptions  
 com.tinypass.rest.v3.framework.dto.RestDTOFromEntity does not have a no-arg default constructor.  
   this problem is related to the following location:  
    at com.tinypass.rest.v3.framework.dto.RestDTOFromEntity  
    at com.tinypass.rest.v3.dto.AppDTO  
    at com.tinypass.rest.v3.dto.AppSensitiveDTO  
   at com.sun.xml.internal.bind.v2.runtime.IllegalAnnotationsException$Builder.check(IllegalAnnotationsException.java:91)  
   at com.sun.xml.internal.bind.v2.runtime.JAXBContextImpl.getTypeInfoSet(JAXBContextImpl.java:436)  
   at com.sun.xml.internal.bind.v2.runtime.JAXBContextImpl.(JAXBContextImpl.java:277)  
   at com.sun.xml.internal.bind.v2.runtime.JAXBContextImpl$JAXBContextBuilder.build(JAXBContextImpl.java:1100)  
   at com.sun.xml.internal.bind.v2.ContextFactory.createContext(ContextFactory.java:143)  
   at com.sun.xml.internal.bind.v2.ContextFactory.createContext(ContextFactory.java:110)  
   at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)  
   at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)  
   at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)  
   at java.lang.reflect.Method.invoke(Method.java:597)  
   at javax.xml.bind.ContextFinder.newInstance(ContextFinder.java:202)  
   at javax.xml.bind.ContextFinder.find(ContextFinder.java:376)  
   at javax.xml.bind.JAXBContext.newInstance(JAXBContext.java:574)  
   at javax.xml.bind.JAXBContext.newInstance(JAXBContext.java:522)  
   at org.glassfish.jersey.server.wadl.internal.generators.WadlGeneratorJAXBGrammarGenerator.buildModelAndSchemas(WadlGeneratorJAXBGrammarGenerator.java:368)  
   at org.glassfish.jersey.server.wadl.internal.generators.WadlGeneratorJAXBGrammarGenerator.createExternalGrammar(WadlGeneratorJAXBGrammarGenerator.java:317)  
   at org.glassfish.jersey.server.wadl.internal.WadlBuilder.generate(WadlBuilder.java:121)  
   at org.glassfish.jersey.server.wadl.internal.WadlApplicationContextImpl.getApplication(WadlApplicationContextImpl.java:143)  
   at org.glassfish.jersey.server.wadl.internal.WadlApplicationContextImpl.getApplication(WadlApplicationContextImpl.java:162)  
   at org.glassfish.jersey.server.wadl.processor.WadlModelProcessor$OptionsHandler.apply(WadlModelProcessor.java:138)  
   at org.glassfish.jersey.server.wadl.processor.WadlModelProcessor$OptionsHandler.apply(WadlModelProcessor.java:120)  
   at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)  
   at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)  
   at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)  
   at java.lang.reflect.Method.invoke(Method.java:597)  
   at org.glassfish.jersey.server.model.internal.ResourceMethodInvocationHandlerFactory$1.invoke(ResourceMethodInvocationHandlerFactory.java:81)  
   at org.glassfish.jersey.server.model.internal.AbstractJavaResourceMethodDispatcher$1.run(AbstractJavaResourceMethodDispatcher.java:151)  
   at org.glassfish.jersey.server.model.internal.AbstractJavaResourceMethodDispatcher.invoke(AbstractJavaResourceMethodDispatcher.java:171)  
   at org.glassfish.jersey.server.model.internal.JavaResourceMethodDispatcherProvider$ResponseOutInvoker.doDispatch(JavaResourceMethodDispatcherProvider.java:152)  
   at org.glassfish.jersey.server.model.internal.AbstractJavaResourceMethodDispatcher.dispatch(AbstractJavaResourceMethodDispatcher.java:104)  
   at org.glassfish.jersey.server.model.ResourceMethodInvoker.invoke(ResourceMethodInvoker.java:406)  
   at org.glassfish.jersey.server.model.ResourceMethodInvoker.apply(ResourceMethodInvoker.java:350)  
   at org.glassfish.jersey.server.model.ResourceMethodInvoker.apply(ResourceMethodInvoker.java:106)  
   at org.glassfish.jersey.server.ServerRuntime$1.run(ServerRuntime.java:259)  
   at org.glassfish.jersey.internal.Errors$1.call(Errors.java:271)  
   at org.glassfish.jersey.internal.Errors$1.call(Errors.java:267)  
   at org.glassfish.jersey.internal.Errors.process(Errors.java:315)  
   at org.glassfish.jersey.internal.Errors.process(Errors.java:297)  
   at org.glassfish.jersey.internal.Errors.process(Errors.java:267)  
   at org.glassfish.jersey.process.internal.RequestScope.runInScope(RequestScope.java:319)  
   at org.glassfish.jersey.server.ServerRuntime.process(ServerRuntime.java:236)  
   at org.glassfish.jersey.server.ApplicationHandler.handle(ApplicationHandler.java:1028)  
   at org.glassfish.jersey.servlet.WebComponent.service(WebComponent.java:373)  
   at org.glassfish.jersey.servlet.ServletContainer.service(ServletContainer.java:381)  
   at org.glassfish.jersey.servlet.ServletContainer.service(ServletContainer.java:344)  
   at org.glassfish.jersey.servlet.ServletContainer.service(ServletContainer.java:219)  
   at org.apache.catalina.core.ApplicationFilterChain.internalDoFilter(ApplicationFilterChain.java:290)  
   at org.apache.catalina.core.ApplicationFilterChain.doFilter(ApplicationFilterChain.java:206)  
   at org.apache.catalina.core.StandardWrapperValve.invoke(StandardWrapperValve.java:233)  
   at org.apache.catalina.core.StandardContextValve.invoke(StandardContextValve.java:191)  
   at org.apache.catalina.core.StandardHostValve.invoke(StandardHostValve.java:127)  
   at org.apache.catalina.valves.ErrorReportValve.invoke(ErrorReportValve.java:102)  
   at org.apache.catalina.core.StandardEngineValve.invoke(StandardEngineValve.java:109)  
   at org.apache.catalina.connector.CoyoteAdapter.service(CoyoteAdapter.java:298)  
   at org.apache.coyote.http11.Http11Processor.process(Http11Processor.java:859)  
   at org.apache.coyote.http11.Http11Protocol$Http11ConnectionHandler.process(Http11Protocol.java:588)  
   at org.apache.tomcat.util.net.JIoEndpoint$Worker.run(JIoEndpoint.java:489)  
   at java.lang.Thread.run(Thread.java:662)  

It looks like this is happening when the user tries to retrieve the application.wadl file. This error occurs because the class RestDTOFromEntity does not have a default constructor. For some reason JAXB requires this no-arg constructor to generate the WADL file. This can be fixed by adding a private no-arg constructor to RestDTOFromEntity.

The absence of a default constructor for that class is motivated by design choices made to properly encapsulate the contents of this class. It's a safe way to force programmers to provide the parameters required to the constructor (which will appropriately throw in case of nulls etc.). A non default constructor would be required if the class was immutable (which is not in this case). This and other encapsulation choices are very common in "academic" object oriented design.

In this specific example, the solution does not break the encapsulation of the class, however it does increase the code bloat with a private no-arg constructor that sits there for no apparent reason (and I believe there might be instances in which framework support requires breaking encapsulation or other OOP principles).

I feel like most Java frameworks built on the javabean specification end up running into this kind of problems. Here are some examples:

• It's common practice in Spring to have default constructors and setters: this is terrible OOP design that leaves the object to all kinds of potential bugs; this can be fixed by using constructor injection but nobody does that because it's a feature added later and because everyone is so used to the javabean paradigm.
• Again, in Spring, it's common practice to instantiate beans with "singleton" scope: this "singleton" is usually an instance of a class; if by accident your application starts with two application contexts, you end up with two singletons! This problem can be solved by using an actual singleton and a factory method, e.g., `getInstance()`, to register the singleton with the Spring context. The method could also take care of DI, but again, this is an even more obscure feature of Spring that nobody uses.
• Objects serialized/deserialized using Jackson typically require a default constructor unless a constructor is defined as a JsonCreator. Once again, the javabean paradigm is so widely spread that many java programmers look at code like that and think I'm insane. Besides, the JsonCreator constructor usually looks pretty terrible and requires to define the properties name in two different places (code bloat + duplication)!

In my experience with (legacy) Java web apps, it looks like these problems are compounded by generally poor design practices, once again fostered by the javabean model: poor encapsulation and lack of immutability. This, together with layer violation in monolithic java apps (like a Spring app would be, ironically!), like using ORM objects in frontend code, leads to unmanageable and fragile code.

Some could argue that being diligent and methodical can prevent programmers from falling into bad practices. However, in my experience this also means swimming against the current because following the right path sometimes leads to horrible code bloat ("what's that giant constructor with all the properties? use setters!") in the best case scenarios and straight up bugs (as the one above) in the worst case scenarios. Taking the easy way out is then justified by the mere existence of the javabean paradigm: every class becomes mutable, with every property (be it a simple type or an object) effectively escaping encapsulation and thread safety (which is "fixed" by using heavy synchronized blocks). So in one single move, the javabean specification flushes down the toilet all the "academic" 101 design practices and makes our life so much harder in the long run.

Javabeans you have failed me!

Fun with Guava's ListeningExecutorService

As a follow up to my previous blog post, I decided to rewrite the code sample using the more advance Google Guava ListeningExecutorService and ListenableFuture API, so here it is:

 import com.google.common.util.concurrent.Futures;  
 import com.google.common.util.concurrent.ListenableFuture;  
 import com.google.common.util.concurrent.ListeningExecutorService;  
 import com.google.common.util.concurrent.MoreExecutors;  
 import java.util.ArrayList;  
 import java.util.List;  
 import java.util.Random;  
 import java.util.Scanner;  
 import java.util.concurrent.Callable;  
 import java.util.concurrent.ExecutionException;  
 import java.util.concurrent.Executors;  

 class ListenableFutureExample {  
   public static void main(String[] args) {  
     Scanner in = new Scanner(System.in);  
     final int nThreads = in.nextInt();  
     final int n = in.nextInt();  
     System.out.println("Using " + nThreads + " threads");  
     ListeningExecutorService service = MoreExecutors.listeningDecorator(Executors.newFixedThreadPool(nThreads));  
     try {  
       try {  
         testSomeWorkers(service, n);  
       } catch (InterruptedException | ExecutionException e) {  
         e.printStackTrace();  
       }  
       try {  
         testJobCanceling(service, n);  
       } catch (InterruptedException | ExecutionException e) {  
         e.printStackTrace();  
       }  
     } finally {  
       // necessary or the thread pool will keep the JVM up and running!  
       service.shutdown();  
     }  
   }  

   public static void testSomeWorkers(ListeningExecutorService service, int n) throws InterruptedException, ExecutionException {  
     // using the Guava's utility method allAsList will return all the results in a future list  
     // enormously simplifying the code:  
     ListenableFuture<List<Integer>> ret = Futures.successfulAsList(addSomeTasks(service, n));  
     // the call to get() is now the blocking piece of code  
     System.out.println("Values returned from computations: " + ret.get());  
     System.out.println("All done.");  
   }  

   public static void testJobCanceling(ListeningExecutorService service, int n) throws InterruptedException, ExecutionException {  
     List<ListenableFuture<Integer>> tasks = addSomeTasks(service, n);  
     ListenableFuture<List<Integer>> ret = Futures.allAsList(tasks);  
     Thread.sleep(1000);  
     System.out.println("Actually nevermind!");  
     ret.cancel(true);  
     // let's see how many tasks were actually cancelled by asking the original futures:  
     List<Integer> completed = new ArrayList<>();  
     for (ListenableFuture<Integer> f : tasks) if (!f.isCancelled()) completed.add(f.get());  
     System.out.println("There were " + (n - completed.size()) + " cancelled tasks and " + completed.size() + " completed tasks: " + completed);  
     System.out.println("All done.");  
   }  

   private static List<ListenableFuture<Integer>> addSomeTasks(ListeningExecutorService service, int howMany) {  
     System.out.println("Enqueuing " + howMany + " tasks...");  
     List<ListenableFuture<Integer>> ret = new ArrayList<>();  
     for (int i = 1; i <= howMany; i++) {  
       final int n = i;  
       ret.add(service.submit(new Callable<Integer>() {  
         @Override  
         public Integer call() {  
           try {  
             try {  
               System.out.println("Task " + n + ": Doing some very important work...");  
               Thread.sleep(200 + rnd.nextInt(200));  
             } catch (InterruptedException e) {  
               System.out.println("Task " + n + " interrupted while doing very important work");  
               return null;  
             }  
             try {  
               System.out.println("Task " + n + ": Doing more important work...");  
               Thread.sleep(200 + rnd.nextInt(200));  
             } catch (InterruptedException e) {  
               System.out.println("Task " + n + " interrupted while doing important work");  
               return null;  
             }  
             try {  
               System.out.println("Task " + n + ": Doing slightly less important work...");  
               Thread.sleep(200 + rnd.nextInt(200));  
             } catch (InterruptedException e) {  
               System.out.println("Task " + n + " interrupted while doing slightly less important work");  
               return null;  
             }  
             int ret = rnd.nextInt();  
             System.out.println("Task " + n + ": about to return " + ret);  
             return ret;  
           } finally {  
             System.out.println("Task " + n + ": cleaning up");  
           }  
         }  
       }));  
     }  
     return ret;  
   }  
   private final static Random rnd = new Random();  
 }  

The Guava API has the advantage to allow one to register a callback to a ListenableFuture and apply transformations to futures, resulting in a chain of non-blocking operations, very much like Scala's Futures. Non-blocking concurrency will greatly limit resource usage, if used properly since there will be no idle threads blocking while waiting on the results of other threads' computations.

Just for illustration purposes, an example of using Guava's future transformation capabilities to implement fully non-blocking asynchronous computations follows. Enjoy!

 import com.google.common.base.Function;  
 import com.google.common.base.Optional;  
 import com.google.common.util.concurrent.Futures;  
 import com.google.common.util.concurrent.ListenableFuture;  
 import com.google.common.util.concurrent.ListeningExecutorService;  
 import com.google.common.util.concurrent.MoreExecutors;  
 import java.math.BigInteger;  
 import java.util.ArrayList;  
 import java.util.List;  
 import java.util.Random;  
 import java.util.concurrent.Callable;  
 import java.util.concurrent.ExecutionException;  
 import java.util.concurrent.Executors;  

 class ListenableFutureChain {  
   public static void main(String[] args) {  
     ListenableFutureChain chain = new ListenableFutureChain(4);  
     // let's find a few 512 bit prime numbers for our awesome encryption algorithm!  
     ListenableFuture<List<BigInteger>> probablePrimes = chain.findSomePrimeNumbers(20, 512);  
     // now finally do something with the future prime list  
     try {  
       // WARNING: this call is blocking, for illustration purposes only.  
       // It's recommended to design so that you don't need to do this,  
       // as in the function findSomePrimeNumbers()  
       for (BigInteger i : probablePrimes.get()) System.out.println(i);  
     } catch (InterruptedException | ExecutionException e) {  
       e.printStackTrace();  
     }  
     // remember to call this or the executor service will keep the JVM "awake"!  
     chain.dispose();  
   }  

   public ListenableFutureChain(final int nThreads) {  
     executorService = MoreExecutors.listeningDecorator(Executors.newFixedThreadPool(nThreads));  
   }  

   public void dispose() {  
     executorService.shutdown();  
   }  

   private final ListeningExecutorService executorService;  
   private final Random random = new Random();  

   public ListenableFuture<List<BigInteger>> findSomePrimeNumbers(final int nAttempts, final int nBits) {  
     List<ListenableFuture<Optional<BigInteger>>> probablePrimes = new ArrayList<>(nAttempts);  
     for (int i = 0; i < nAttempts; i++) {  
       // submit a task for execution and retrieve the ListenableFuture  
       ListenableFuture<BigInteger> probablePrimeFuture = executorService.submit(new Callable<BigInteger>() {  
         @Override  
         public BigInteger call() throws Exception {  
           // I'm going to find a probable prime number  
           return BigInteger.probablePrime(nBits, random);  
         }  
       });  
       // transform the previous ListenableFuture using a function; returns another ListenableFuture (non blocking operation)  
       ListenableFuture<Optional<BigInteger>> primeOrNot = Futures.transform(probablePrimeFuture, new Function<BigInteger, Optional<BigInteger>>() {  
         @Override  
         public Optional<BigInteger> apply(BigInteger p) {  
           // I'm going to return only the probable primes that are actually prime  
           if (isPrime(p)) return Optional.of(p);  
           return Optional.absent();  
         }  
       }, executorService);  
       // add the second future to a list  
       probablePrimes.add(primeOrNot);  
     }  
     // transform the list of futures to a future of list (Guava magic!), only retain successful futures (again, non blocking!)  
     ListenableFuture<List<Optional<BigInteger>>> primesOrNoValues = Futures.successfulAsList(probablePrimes);  
     // transform the future list to a future list containing only the prime numbers in question and return this future (still non blocking)  
     return Futures.transform(primesOrNoValues, new Function<List<Optional<BigInteger>>, List<BigInteger>>() {  
       @Override  
       public List<BigInteger> apply(List<Optional<BigInteger>> primes) {  
         List<BigInteger> ret = new ArrayList<>(primes.size());  
         //  
         for (Optional<BigInteger> optional : primes)  
           if (optional != null && optional.isPresent()) ret.add(optional.get());  
         return ret;  
       }  
     }, executorService);  
     // Note that this whole function is non blocking; you can tell by the fact that there's no InterruptedException being thrown anywhere.  
   }  

   private boolean isPrime(final BigInteger p) {  
     // TODO: do some fancy primality test! (note that this would take a while in real life)  
     // let's just return true or false randomly for now... ;)  
     return random.nextBoolean();  
   }  
 }  

Fun with java's ExecutorService

It's surprisingly difficult to find a decent example of the java Executor framework that explains some of the API's "gotchas". It took me a while way back then when I was trying to figure it out, so I decided to post a hopefully useful example. In the code below, I use an executor service to execute some work in parallel. This is the easiest way to exploit simple parallelism in java 7 (java 8 introduces parallel streams which make things even simpler). The executor service is created as a fixed thread pool using a convenient static factory method available in the Executors class. It's very instructive to look at the javadoc for this and other static factory methods available in this class, and even the source code if you are feeling adventurous, to understand how the thread pools are created and what additional options are available to customize them.

The testSomeWorkers() method creates a few tasks (instances of Callable), invokes them using the executor service and retrieves their results using the corresponding Futures. The helper method addSomeTasks() simply calls the submit() method on the executor service to submit the n tasks and retrieve the corresponding future. The future will return the value returned by the Callable once the execution is over.

The testJobCanceling() method works pretty much like testSomeWorkers() but it shows how the tasks can be cancelled by using the Future.cancel() method. The cancel() method's only argument specifies whether or not the thread in which the job is running should be interrupted. In the Callable.call() function, invoking Thread.sleep() can potentially throw an InterruptedException. This will happen when we call cancel() on the future associated with this callable and thus the exception is handled by returning immediately. It's a common idiom in java to handle interruptions in this fashion to achieve some control over concurrent workers.

Enjoy the code:

 import java.util.*;  
 import java.util.concurrent.*;  
 class ExecutorServiceExample {  
   public static void main(String[] args) {  
     Scanner in = new Scanner(System.in);  
     final int nThreads = in.nextInt();  
     final int n = in.nextInt();  
     System.out.println("Using " + nThreads + " threads");  
     ExecutorService service = Executors.newFixedThreadPool(nThreads);  
     try {  
       testSomeWorkers(service, n);  
     } catch (InterruptedException | ExecutionException e) {  
       e.printStackTrace();  
     }  
     try {  
       testJobCanceling(service, n);  
     } catch (InterruptedException | ExecutionException e) {  
       e.printStackTrace();  
     }  
     // necessary or the thread pool will keep the JVM up and running!  
     service.shutdown();  
   }  
   public static void testSomeWorkers(ExecutorService service, int n) throws InterruptedException, ExecutionException {  
     // create and invoke some "tasks" on this executor service  
     Collection<Future<Integer>> taskFutures = addSomeTasks(service, n);  
     System.out.println("Waiting for all tasks to complete...");  
     List<Integer> ret = new ArrayList<>();  
     // retrieve the result of the tasks' computation  
     for (Future<Integer> f : taskFutures) ret.add(f.get());  
     System.out.println("Values returned from computations: " + ret);  
     System.out.println("All done.");  
   }  
   public static void testJobCanceling(ExecutorService service, int n) throws InterruptedException, ExecutionException {  
     Collection<Future<Integer>> taskFutures = addSomeTasks(service, n);  
     Thread.sleep(1000);  
     System.out.println("Actually nevermind!");  
     List<Integer> completed = new ArrayList<>();  
     List<Future<Integer>> cancelled = new ArrayList<>();  
     // try to cancel the tasks that are running  
     for (Future<Integer> f : taskFutures) {  
       // if successfully cancel add to the cancelled list  
       if (f.cancel(true)) cancelled.add(f);  
         // otherwise get the result  
       else completed.add(f.get());  
     }  
     System.out.println("" + cancelled.size() + " tasks were successfully cancelled");  
     if (!completed.isEmpty()) System.out.println("Values returned from computations: " + completed);  
     System.out.println("All done.");  
   }  
   private static Collection<Future<Integer>> addSomeTasks(ExecutorService service, int howMany) {  
     System.out.println("Enqueuing " + howMany + " tasks...");  
     List<Future<Integer>> ret = new ArrayList<>();  
     for (int i = 0; i < howMany; i++) {  
       final int n = i;  
       ret.add(service.submit(new Callable<Integer>() {  
         @Override  
         public Integer call() {  
           try {  
             try {  
               System.out.println("Task " + n + ": Doing some very important work...");  
               Thread.sleep(200 + rnd.nextInt(200));  
             } catch (InterruptedException e) {  
               System.out.println("Task " + n + " interrupted while doing very important work");  
               return null;  
             }  
             try {  
               System.out.println("Task " + n + ": Doing more important work...");  
               Thread.sleep(200 + rnd.nextInt(200));  
             } catch (InterruptedException e) {  
               System.out.println("Task " + n + " interrupted while doing important work");  
               return null;  
             }  
             try {  
               System.out.println("Task " + n + ": Doing slightly less important work...");  
               Thread.sleep(200 + rnd.nextInt(200));  
             } catch (InterruptedException e) {  
               System.out.println("Task " + n + " interrupted while doing slightly less important work");  
               return null;  
             }  
             return rnd.nextInt();  
           } finally {  
             System.out.println("Cleaning up after task " + n);  
           }  
         }  
       }));  
     }  
     return ret;  
   }  
   private final static Random rnd = new Random();  
 }  

Rabin-Karp Algorithm

Here's a juicy code example implementing the Rabin-Karp algorithm in java. The Rabin-Karp algorithm is a string matching algorithm: given a text and a pattern string, the algorithm will return the location(s) of the given pattern in the text. Assuming the size of the text is n characters and the size of the pattern is m characters the average and best case running time is O(n+m).
The idea is quite simple: treat the pattern p_0,m-1 as if it was a number expressed in radix-d notation, i.e., of the form:
P = p₀ × d^m-1+p₁ × d^m-2 + ... + p_m-1 × d⁰
Now, a match is found if a substring of the text represents the same exact integer, i.e., the pattern p_0,m-1 matches a substring t_k,k+m-1 (0 ≤ k ≤ n-m), or equivalently:
P = T_k = t_k × d^m-1 + t_k+1 × d^m-2 + ... + t_k+m-1 × d⁰
It's easy to see that the radix-d integer for the substring starting at index location k can be easily computed from the radix-d integer for the substring starting at k-1:
T_k = t_k × d^m-1 + t_k+1 × d^m-2 + ... + t_k+m-1 × d⁰ =
     = (t_k-1 × d^m-1 + t_k × d^m-2 + ... + t_k+m-2 × d⁰ - t_k-1 × d^m-1) × d + t_k+m-1 =
     = (T_k-1 - t_k-1 × d^m-1) × d + t_k+m-1
That is, subtract the first character of the previous substring multiplied by the radix to the size of the pattern minus one, then multiply by the radix and add the last character of the new substring. It's very straightforward on paper, although it can be tricky to get right.
This approach would certainly work if we could easily store in some integer type the radix-d numbers represented by the strings. Unfortunately, this is not always the case (almost never in fact). Let's look at a simple example: assume your char size is 8 bit, so that you would naturally choose the radix 256=2⁸, since each digit represents a value between 0 and 255=2⁸-1. An m-char string can express numbers between 0 and 256^m-1=2^8×m-1. If we want to store these integers in a 64 bit unsigned long type, we can only represent strings of length 8: 2^8×8=2⁶⁴. Bottom line: we can't express P and T_k using integers.
This is where the most powerful idea of the Rabin-Karp algorithm comes to play. We don't need to represent these huge numbers, but only their value modulo a big enough prime q, i.e., P mod q and T_k mod q. The catch is that if the match is positive, i.e., the hash codes are identical, we still need to check for equality between the pattern and the substring to make sure it's not a false positive. This obviously increases the computation time if there are a lot of false positives.
One last thing worth noting is that the Rabin-Karp algorithm works very well to match multiple patterns all at once: instead of storing a single key P, we can store a set of keys P_1,...,l for each pattern. Great care has to be made in computing the keys T_k now since the patterns can have different lengths, but once one gets the details right, it's quite straightforward.
Follows a simple java implementation of the Rabin-Karp algorithm to find all instances of a single pattern in a text.

Augmented Data Structures: LRU Cache

New post after a long absence. I have been busy with my job search but it seems to have come to an end, so I have time to write some more and share some code. Here's a post about augmenting data structures. Enjoy!
Augmenting a data structure allows to add additional operations to textbook data structure such as linked lists, trees or hash tables. The basic operations of the data structure should maintain their original asymptotic runtime and the new operations should be efficient. A very good introduction on the topic can be found on the CLR textbook.
This post focuses on a simple data structure that basically mixes a hash table with a linked list. This data structure can be used to implement a simple LRU cache. The idea is to only cache the N most recently used objects and discard the rest, i.e., the least recently used (LRU) ones. The run time complexity for data retrieval from the cache should be constant, i.e., from an object design point of view a cache object of the form Cache could provide a get(Key) method that returns the Data object in O(1) time.
The first idea that comes to mind is to have a hash table do the heavy lifting of storing (Key,Data) pairs, leading to constant retrieval time. The LRU requirement is more tricky. The first thing that one can think of is to use a queue to store the N most recently accessed keys. When the size of the queue exceeds N, we could just pop it and remove that key from the table as well. This strategy however will not work: what if the same key was accessed N times? We would be removing the only object in the cache! Moreover, if we store in the queue the same object for N times, we are basically storing just the last object used, not the last N. Replacing the queue with a linked list and scanning the whole list every time might fix this problem but it will make the access time linear in the size of the cache, i.e., O(N), which would completely defeat the purpose.
There are probably multiple ways to fix this problem, but I think the most elegant and efficient solution is to maintain a doubly linked list of (Key,Data) pairs and to store the nodes of the list in a hash table indexed by the key. When the get method is called, the node can be retrieved and can be put at the top of the linked list. We can easily make sure that the list never exceeds N elements by cutting its tail (and removing corresponding objects from the table), which will contain the least recently used keys.
Here's a java implementation of this idea. The interface DataSource simply defines the get(Key) method returning a Data object.

 import java.util.Hashtable;  
 public class LRUCache<Key, Data> implements DataSource<Key, Data> {  
      private final DataSource<Key, Data> source;  
      private final Hashtable<Key, Node> cache;  
      private final int maxRecords;  
      private Node head = null, tail = null;  
      public LRUCache(DataSource<Key, Data> source, int maxRecords) {  
           this.source = source;  
           this.maxRecords = maxRecords;  
           cache = new Hashtable<>();  
      }  
      @Override  
      public Data get(Key key) {  
           if (cache.containsKey(key)) {// the data is in the cache  
                Node node = cache.get(key);  
                if (node != head) {  
                     if (node == tail)  
                          tail = tail.prev;  
                     if (node.prev != null)  
                          node.prev.next = node.next;  
                     if (node.next != null)  
                          node.next.prev = node.prev;  
                     node.prev = null;  
                     node.next = head;  
                     if (head != null)  
                          head.prev = node;  
                     else  
                          tail = node;  
                     head = node;  
                }  
                // return the data  
                return node.data;  
           }  
           // retrieve the data from the source  
           Data data = source.get(key);  
           // put the data at the head of the list and into the table  
           Node node = new Node(key, data);  
           cache.put(key, node);  
           node.next = head;  
           if (head != null)  
                head.prev = node;  
           else  
                tail = node;  
           head = node;  
           while (cache.size() > maxRecords)  
                if (tail != null) {  
                     cache.remove(tail.key);  
                     if (tail.prev != null)  
                          tail.prev.next = null;  
                     tail = tail.prev;  
                }  
           return data;  
      }  
      private class Node {  
           public Node(Key key, Data data) {  
                this.key = key;  
                this.data = data;  
           }  
           final Key key;  
           final Data data;  
           Node prev;  
           Node next;  
      }  
 }  

It's worth noting that this implementation is NOT concurrent. Designing a concurrent LRU cache is a little more tricky: if we synchronize the get() method then the cache might block for a long time when accessing the data source (say, a database), while it could be responding to clients that are querying data that's already cached. A simple idea would be to synchronize the blocks of code that access the cache in the get() method and leave to the external DataSource object the task of synchronizing access to external resources. In the code above, the if statement in the get would have to be synchronized and so would the block going from the definition of the new node to right before returning. If a concurrent hash map was used, synchronization of the if statement itself wouldn't be necessary, just the if block would have to be synchronized.

Dynamic Programming and Memoization

I love dynamic programming. It's a great technique to solve many optimization problems. Now if you're familiar with dynamic programming, you know that it basically consists in solving a problem with optimal sub-structure, i.e., where the optimal solution is obtained by solving one or more smaller sub-problems of the same kind, and overlapping sub-problems, i.e., when the solution is obtained by repeatedly solving the same sub-problems over and over. Dynamic programming algorithms can usually be written in a recursive fashion, i.e., with a top-down approach. For example an algorithm to compute Fibonacci numbers might call itself recursively. The algorithm can be "memoized" by storing the value of the i-th Fibonacci number right after it's computed the first time and then use the stored values when needed. Writing algorithms in a top-down fashion is usually more intuitive and easy to understand, e.g., F_n = F_n-1+F_n-2 for the Fibonacci sequence. Memoization makes sure the algorithm doesn't compute the same Fibonacci number twice, thus the running time is O(n). Note that there are smarter ways to compute Fibonacci numbers, e.g., using the recursive formulas F_2n-1 = F_n²+F_n-1² and F_2n = (2F_n-1+F_n)F_n, which lead to logarithmic running time.
There are also smarter ways of writing dynamic programming algorithms. In fact, memoization is great because it allows writing code in a natural way, but it leaves us with a lot of overhead due to the call stack. The solution is to write the algorithm in a bottom-up fashion instead. This means solving the simplest sub-problems first and then using them to solve the higher level sub-problems in progressive order. Going back to our Fibonacci sequence, this means computing the elements of the sequence one after the other starting from F₀ = 0 and F₁ = 1, F₂ = F₀+F₁ and so on. The recursive program can be now written in iterative form, e.g., in a for loop. It's worth noting that the asymptotic running time is still O(n), but the time saved by reducing the call stack overhead will noticeably improve the constant factors, leading to a faster algorithm.
It's interesting to have an idea of this improvement. I decided to implement the cutting-rod problem with both approaches and compare the running times. I'm not going to describe the problem or the solution here, since it's really a textbook example. The figure below shows a plot of the running time for the two implementations of the rod cutting algorithm: the bottom-up one is obviously the winner with a constant factor about 3 times smaller than the top-down one (both algorithms run in O(n²)).

And here's the java code used to obtain the data in the plot. Enjoy!

 import java.util.Arrays;  
 import java.util.Random;  
 public class RodCutting {  
      public static void main(String[] args) {  
           // the random seed is chosen arbitrarily  
           Random rnd = new Random(2358761235817L);  
           // the class RodCutting contains the two algorithms  
           RodCutting cutRod = new RodCutting();  
           // this creates an array of rod lengths to test. 30 is the interval  
           // between lengths and 1500 the maximum value in the array, thus the  
           // array is {30,60,...,1470,1500}.  
           int rodLengths[] = computeRodLengths(30, 1500);  
           // generate 50 test cases to get consistent results  
           int nCases = 50;  
           // maximum price per rod piece  
           int max = 50;  
           // computing times in ns are stored in these two arrays  
           long[] computingTimeMemoized = new long[rodLengths.length];  
           long[] computingTimeBottomUp = new long[rodLengths.length];  
           for (int i = 0; i < nCases; i++) {  
                // create a test case  
                int[] p = generateTestCase(rodLengths[rodLengths.length - 1], max, rnd);  
                // run the algorithm for each selected rod length  
                for (int j = 0; j < rodLengths.length; j++) {  
                     computingTimeMemoized[j] += testMemoized(p, rodLengths[j], cutRod);  
                     computingTimeBottomUp[j] += testBottomUp(p, rodLengths[j], cutRod);  
                }  
           }  
           System.out.printf("%20s %20s %20s\n", "rod length",  
                     "memoized time [ns]", "bottom-up time [ns]");  
           for (int i = 0; i < rodLengths.length; i++) {  
                computingTimeMemoized[i] /= nCases;  
                computingTimeBottomUp[i] /= nCases;  
                System.out.printf("%20d %20d %20d\n", rodLengths[i],  
                          computingTimeMemoized[i], computingTimeBottomUp[i]);  
           }  
      }  
      public int cutRodMemoized(int[] p, int n) {  
           int r[] = new int[p.length + 1];  
           Arrays.fill(r, Integer.MIN_VALUE);  
           return cutRodMemoizedAux(p, n, r);  
      }  
      private int cutRodMemoizedAux(int[] p, int n, int[] r) {  
           if (r[n] >= 0)  
                return r[n];  
           int q = 0;  
           if (n != 0) {  
                q = Integer.MIN_VALUE;  
                for (int i = 1; i <= n; i++)  
                     q = Math.max(q, p[i - 1] + cutRodMemoizedAux(p, n - i, r));  
           }  
           r[n] = q;  
           return q;  
      }  
      public int cutRodBottomUp(int[] p, int n) {  
           int[] r = new int[p.length + 1];  
           r[0] = 0;  
           for (int j = 1; j <= n; j++) {  
                int q = Integer.MIN_VALUE;  
                for (int i = 1; i <= j; i++)  
                     q = Math.max(q, p[i - 1] + r[j - i]);  
                r[j] = q;  
           }  
           return r[n];  
      }  
      private static int[] computeRodLengths(int interval, int max) {  
           int l = max / interval;  
           int[] ret = new int[l];  
           for (int i = 0; i < l; i++)  
                ret[i] = interval * (i + 1);  
           return ret;  
      }  
      private static long testMemoized(int[] p, int n, RodCutting cutRod) {  
           long start = System.nanoTime();  
           cutRod.cutRodMemoized(p, n);  
           return System.nanoTime() - start;  
      }  
      private static long testBottomUp(int[] p, int n, RodCutting cutRod) {  
           long start = System.nanoTime();  
           cutRod.cutRodBottomUp(p, n);  
           return System.nanoTime() - start;  
      }  
      private static int[] generateTestCase(int n, int max, Random rnd) {  
           int[] ret = new int[n];  
           for (int i = 0; i < n; i++)  
                ret[i] = rnd.nextInt(max);  
           return ret;  
      }  
 }  

Maximum Consecutive Sum

This is a text-book dynamic programming problem, but it's still interesting since many job interview questions have the same level of complexity. You are given a sequence of numbers {x₁,x₂,...,x_n} and are asked to compute the maximum consecutive sum in the array. For example, the maximum consecutive sum in {1,-3,7} is 1-3+7 = 5; in {5,-1,2,-2,1} it's 5-1+2 = 6.
Now let's look at the optimal substructure of the problem. Let's define S_k-1 as the maximum consecutive sum for the sequence {x₁,...,x_k-1} and V_k-1 as the maximum consecutive sum for the same array including x_k-1. Note that S_k-1 and V_k-1 are in general distinct, e.g., for {5,-1,2,-2,1}, S₂ = 5, while V₂ = 5-1 = 4. The values of V_k and S_k can be computed using dynamic programming. In fact, V_k = max(V_k-1+x_k,x_k) and S_k = max(S_k-1,V_k). E.g., for {5,-1,2,-2,1}, V₃ = 5-1+2 = 6, S₂ = 5 and S₃ = V₃ = 6. At each step we only need S_k-1 and V_k, so we only store two variables. The problem has optimal substructure because the optimal solution S_k can be found by using the optimal solution S_k-1 of a sub-problem together with the additional information stored in V_k.
Finally, if we want to know the indices at which to start and end the sum, we need to keep track of the initial index to compute the sum V_k, call it m, and of the two indices that define S_k, say i,j. To keep track of m, we just need to notice that if x_k > V_k-1+x_k then m = k, otherwise m is unchanged; similarly, to keep track of i,j, if V_k > S_k-1, then i = m and j = k, otherwise i,k are unchanged.
Here's a very straight forward java implementation of this algorithm with a few test cases. Enjoy!

 public class MaximumConsecutiveSum {  
      public int maximumConsecutiveSum(int[] x) {  
           // initialize S[0]=V[0]=0  
           int runningMaxConsSum = 0, maxConsSumRightEdgeIncl = 0;  
           // left is the starting index for V[k], start,end the indices for S[k]  
           int left = 0, start = 0, end = 0;  
           for (int k = 0; k < x.length; k++) {  
                int tmp = maxConsSumRightEdgeIncl + x[k];  
                if (tmp > x[k])  
                     maxConsSumRightEdgeIncl = tmp;  
                else {  
                     maxConsSumRightEdgeIncl = x[k];  
                     left = k;  
                }  
                if (maxConsSumRightEdgeIncl > runningMaxConsSum) {  
                     runningMaxConsSum = maxConsSumRightEdgeIncl;  
                     start = left;  
                     end = k;  
                }  
           }  
           System.out.println("[" + start + "," + end + "]: " + runningMaxConsSum);  
           return runningMaxConsSum;  
      }  
      public static void main(String[] args) {  
           MaximumConsecutiveSum maxSum = new MaximumConsecutiveSum();  
           maxSum.maximumConsecutiveSum(new int[] { 2, -1, 3 });  
           maxSum.maximumConsecutiveSum(new int[] { 2, -8, 3 });  
           maxSum.maximumConsecutiveSum(new int[] { 5, -1, 2, -2, 1 });  
           maxSum.maximumConsecutiveSum(new int[] { 5, -8, 2, -2, 2, 5, 1, 6, 1, 2 });  
           maxSum.maximumConsecutiveSum(new int[] { 3, -9, 2, 9, 12 });  
      }  
 }  

Prerequisites Problem aka Task Priority with Lexicographic Order

People who are familiar with TopCoder might have run into the problem "Prerequisites". I won't rewrite the complete statement here as it is exclusive property of TopCoder, but I'll give my own definition of it.
The problem statement is relatively simple: N tasks are given; each task depends on a set of tasks that must be performed before the given one. The time required to perform a task is irrelevant and the tasks must be performed one at a time. The requirement is to sort the tasks so that all the dependencies are satisfied. In case of ties (i.e., two or more tasks could be performed at the same time), the tasks must be sorted according to a given lexicographic criterion (e.g., in alphabetical order). It's assumed that there are no conflicts between dependencies, i.e., the sorted list always exists and is unique.
By analyzing the structure of the input data, we easily recognize a directed acyclic graph (DAG) in which each task is a vertex and each edge represents a dependency of a task from another (A depends on B if and only if that there is an edge going from B to A). The requested solution is a particular topological sorting of the graph (examples of algorithms used for topological sorting are Kahn's algorithm or DFS). However, enforcing the lexicographic order to tied tasks requires complex topological sorting algorithms.
An interesting and very intuitive solution can be devised by applying the greedy strategy: always making the choice that looks best at the moment. This approach works if the problem has optimal substructure and I'll do my best to explain that it does in this case. Since there are no dependency conflicts (i.e., no cycles), there must be one or more tasks with no dependencies at all (no incoming edges). Once we found all of these tasks, we can sort them according to the lexicographic order to decide which one must be performed first. We append the first task in this sorted set to the output list. This first task will also be removed from the graph together with all its outgoing edges (i.e., the dependencies of all the other tasks from it: since this task is performed first, we can ignore all these dependencies). At this point we are left with one sub-problem that's absolutely analogous to the previous one (here's the optimal substructure!) and we can proceed to solve it as we did before, appending to the output list one task per sub-problem.
Follows a java implementation of this algorithm. There are N tasks. For simplicity, the tasks are identified by their name only. The input is composed of N strings. Each string is in the form "TASK: DEP1 DEP2 ... ", where "TASK" is the name of a task and "DEP1", "DEP2", etc. are its dependencies (there can be zero up to N-1). Each task will always appear only once as the head of the string.

 import java.util.Collections;  
 import java.util.Iterator;  
 import java.util.LinkedList;  
 import java.util.regex.Pattern;  
 public class TaskPriority {  
      public String[] orderTasks(String[] inputTasks) {  
           // this array will contain the sorted tasks  
           String[] sortedTasks = new String[inputTasks.length];  
           int index = 0;  
           // create a list of tasks and populate it  
           LinkedList<Task> tasks = new LinkedList<Task>();  
           for (String s : inputTasks)  
                tasks.add(new Task(s));  
           // list of independent tasks  
           LinkedList<Task> independentList = new LinkedList<Task>();  
           while (!tasks.isEmpty()) {  
                // find elements with no dependency, add them to the list of  
                // independent tasks and remove them to the task list  
                for (Iterator<Task> it = tasks.iterator(); it.hasNext();) {  
                     Task c = it.next();  
                     if (c.hasNoDependencies()) {  
                          // this task is independent  
                          independentList.add(c);  
                          // we can remove it from the list of tasks since it will  
                          // stay in the list of independent tasks instead  
                          it.remove();  
                     }  
                }  
                // sort the independent tasks  
                Collections.sort(independentList);  
                // poll the first independent task and store it into the return  
                // array  
                Task c = independentList.poll();  
                sortedTasks[index++] = c.toString();  
                // remove the dependencies to the task we just processed  
                for (Task a : tasks)  
                     a.removeDependency(c.toString());  
           }  
           // store the remaining tasks in the list of independent tasks into the  
           // output array. note that they are already properly sorted  
           while (!independentList.isEmpty())  
                sortedTasks[index++] = independentList.poll().toString();  
           return sortedTasks;  
      }  
      private final Pattern splitPattern = Pattern.compile("\\s");  
      private String[] getTokens(String s) {  
           return splitPattern.split(s);  
      }  
      private class Task implements Comparable<Task> {  
           private final String name;  
           private final LinkedList<String> dependencies;  
           @Override  
           public String toString() {  
                return name;  
           }  
           @Override  
           public boolean equals(Object o) {  
                if (o == null)  
                     return false;  
                if (this == o)  
                     return true;  
                if (o instanceof Task) {  
                     Task c = (Task) o;  
                     return name.equals(c.name);  
                }  
                return false;  
           }  
           public Task(String c) {  
                String[] tokens = getTokens(c);  
                name = tokens[0].substring(0, tokens[0].length() - 1);  
                dependencies = new LinkedList<String>();  
                for (int i = 1; i < tokens.length; i++) {  
                     dependencies.add(tokens[i]);  
                }  
           }  
           public boolean hasNoDependencies() {  
                return dependencies.isEmpty();  
           }  
           public boolean removeDependency(String s) {  
                return dependencies.remove(s);  
           }  
           public int compareTo(Task arg0) {  
                return this.name.compareTo(arg0.name);  
           }  
      }  
 }  

Note that the Task class might seem unnecessary since we are only dealing with strings and a simple alphabetical order. However, the lexicographic ordering can be more complex than that (it is in fact more complex in the original problem statement) and the Task class nicely encapsulate the properties of the graph making the algorithm much more readable and easy to understand.

Segmented Sieve of Eratosthenes in Java

As promised, here's a simple implementation of the segmented sieve. The segmented sieve is a very straight forward algorithm. The objective is to find all prime numbers between L and R. Typically L and R are very large (1e16-1e18), while R-L is much smaller (1e8-1e10). The odd prime numbers that have multiples in this interval are all smaller than sqrt(R) can be found by using a basic sieve. The sieve works in exactly the same way as before, except for each prime p we start sifting from its first multiple contained in the given interval. To find it, we need to find the first number n that satisfies the equation n mod p = 0. Now be q = -L mod p, then n = L + q. In fact, (L + p) mod p = (L - L) mod p = 0. L + q is the first number to be discarded; the rest of the multiples are found by repeatedly adding p to this number.
For example, if L = 100 and R = 200, all the odd primes smaller than sqrt(200) are 3, 5, 7, 11 and 13. -100 mod 3 = 2 and 102 is the first multiple of 3 contained in the interval. Likewise, -100 mod 5 = 0, -100 mod 7 = 5 and so on.
This implementation of the segmented sieve makes use of the basic sieve from my previous post. Note that for very big numbers (e.g., R=2^63, sqrt(R)>2^31) the basic sieve might not work as expected (int should be replaced by long).

 public class SegmentedPrimeSieve {  
      private final byte sieve[];  
      private final long start;  
      /**  
       * Creates a segmented sieve in the interval defined by the values of start  
       * and end.  
       *   
       * @param start  
       * @param end  
       */  
      public SegmentedPrimeSieve(long start, long end) {  
           // if the starting value is not odd, choose the next one  
           start = start % 2 == 0 ? ++start : start;  
           // length of the byte array  
           int length = (int) ((end - start) / 16 + 1);  
           sieve = new byte[length];  
           // finally, let's compute the extended range  
           end = start + length * 16 - 2;  
           // find all the primes up to sqrt(end)  
           int maxPrime = (int) Math.floor(Math.sqrt(end));  
           PrimeSieve baseSieve = new PrimeSieve((int) maxPrime);  
           System.out.println("Sieving numbers between " + start + " and " + end);  
           // maximum value of k to sift multiples of primes in the form 2*k+1  
           int maxK = maxPrime / 2;  
           long intervalHalfSize = 8 * length;  
           // let's assume primes in the form 2*k+1 starting from k=1  
           for (int k = 1; k <= maxK; k++) {  
                // if the number is marked as a prime in the basic sieve start  
                // sifting all of its multiples in the given interval  
                if (baseSieve.get(k)) {  
                     final int p = 2 * k + 1;  
                     // This is the initial offset to start sifting from (-start%p)  
                     int offset = (int) ((p - (start % p)) % p);  
                     // if the offset is odd, start+offset is even, skip it because  
                     // we don't have even numbers in the sieve. divide by two for  
                     // the same reason. Note that this step is crucial!  
                     if (offset % 2 == 1)  
                          offset += p;  
                     offset /= 2;  
                     for (; offset < intervalHalfSize; offset += p) {  
                          sieve[offset >> 3] |= (1 << (offset & 7));  
                     }  
                }  
           }  
           this.start = start;  
      }  
      public boolean isPrime(long n) {  
           if (n < start)
                throw new RuntimeException("The number " + n
                          + " is too small for the values in the sieve.");
           if (n == 2)  
                return true;  
           if (n == 1 || n % 2 == 0)  
                return false;  
           int dn = (int) (n - start);  
           int i = dn / 16;  
           if (i >= sieve.length)  
                throw new RuntimeException("The number " + n  
                          + " exceeds the values in the sieve.");  
           return ((sieve[i] >> ((dn / 2) & 7)) & 1) == 0;  
      }  
 }  

Eratosthenes Prime Sieve: a Java Implementation

One of the classical problems in the Sphere Online Judge consists in generating prime numbers. Such a problem can be solved using a prime sieve, a technique that allows finding new prime numbers by discarding all the multiples of known prime numbers. For example, we know that 2 is a prime, so we would automatically discard all even numbers, then we would go ahead and discard the multiples of 3, 5, 7 and so on. Eratosthenes came up with this algorithm roughly 2250 years ago (Wikipedia provides a good description of the sieve).
I wrote down a very straightforward implementation of Eratosthenes sieve in java. Since the algorithm can be used to find a considerable amount of prime numbers, usually it's implemented so that the amount of memory used is as small as possible. A single bit of information is used to store whether or not a number is prime. Thus each byte contains information about 8 numbers. Discarding all even numbers beforehand cuts in half the number of bits needed. Other techniques can be used to reduce the amount of memory used, but I decided to stop here for simplicity. Here's my source code:

 public class PrimeSieve {  
      private final byte sieve[];  
      /**  
       * Creates a sieve of integers up to n.  
       *   
       * @param n  
       */  
      public PrimeSieve(int n) {  
           // using one bit per number, skipping even numbers  
           int sieveSize = n / 16 + 1;  
           // round up to the next multiple of 16  
           n = sieveSize * 16;  
           System.out.println("Sieving numbers up to " + n);  
           // initialize the array of bytes. Each bit corresponds to an odd integer  
           // between 1 and n, starting with the rightmost bit of the first byte.  
           // If the bit is 0, the number is prime. Initially, all numbers are  
           // assumed to be prime and some will be sifted out.  
           sieve = new byte[sieveSize];  
           // 1 is composite  
           sieve[0] = 0x01;  
           // this is the maximum starting number to search for primes in the form  
           // 2*k+1  
           int maxK = (int) Math.floor(Math.sqrt(n / 2));  
           int nHalf = n / 2;  
           // loop on numbers of the form 2*k+1  
           for (int k = 1; k <= maxK; k++) {  
                // if 2*k+1 is marked as prime, sift all its multiples  
                if (get(k)) {  
                     // start from (2*k+1)^2: must divide this by two since the array  
                     // doesn't contain multiples of two. Thus the starting number is  
                     // (2*k+1)^2/2 = 2*k*(k+1). Note that this is odd.  
                     // the increment is 2*k+1 (since the sieve contains only odd  
                     // numbers, using this increment automatically skips to the next  
                     // odd multiple).  
                     final int increment = 2 * k + 1;  
                     for (int composite = 2 * k * (k + 1); composite < nHalf; composite += increment)  
                          // the index in the array is obtained by discarding the  
                          // rightmost 3 bits (or divide by 8); likewise, the position  
                          // in the byte is obtained by right shifting one as many  
                          // time as the number represented by the same 3 bits.  
                          // Note that the function get() is implemented similarly.  
                          sieve[composite >> 3] |= (1 << (composite & 7));  
                }  
           }  
      }  
      /**  
       * Checks if the number 2*n+1 is marked as prime.  
       *   
       * @param n  
       *      An integer number.  
       * @return True if 2*n+1 is marked as prime, false otherwise.  
       */  
      boolean get(int n) {  
           return ((sieve[n >> 3] >> (n & 7)) & 1) == 0;  
      }  
      /**  
       *   
       * @param n  
       *      An integer.  
       * @return True if n is prime.  
       */  
      public boolean isPrime(int n) {  
           if (n == 2)  
                return true;  
           if (n == 1 || n % 2 == 0)  
                return false;  
           int i = n / 16;  
           if (i >= sieve.length)  
                throw new RuntimeException("The number " + n  
                          + " exceeds the values in the sieve.");  
           return ((sieve[i] >> ((n / 2) & 7)) & 1) == 0;  
      }  
 }  

Sometimes it's useful to find prime numbers in a small interval instead of all of them up to a certain value. In cases like this, it's inconvenient to use the full sieve, since its speed and memory requirements always depend on the upper primes bound. A segmented sieve allows sifting the composite numbers in a given interval, ignoring most of the previous numbers. In this case speed and memory requirements will depend (mostly) on the length of the interval. I'll give an implementation of the segmented sieve in my next blog post.

Java Hashtable and the Apache Commons Lang package

Hash Table Review
Hash tables are data structures that map an object, the key, to another object, the value. Each key can only be mapped to one value, but different keys can be mapped to the same value. An array can be thought of as a hash table in which the key is an index and the value is the object stored in the corresponding position in the array. Each index maps one and only value in the array. Arrays have the advantage that, knowing the key, the time to retrieve the corresponding value (access time) is O(1). On the other hand, their limitation is that the key can only be a (non negative) integer.
Hash tables are designed to have O(1) access time just like an array, but with the feature of accepting arbitrary keys, for example floating point numbers, strings, or arbitrary objects. A hash table can be described as a collection of buckets containing a certain number of [key,value] pairs with distinct keys (e.g., Introduction to Algorithms by Cormen et al.). Each bucket is labeled by an integer and each key can only be in one of the buckets. The bucket label is called hash code. Each key uniquely defines its hash code, but two different keys can have the same hash code. The hash code can be computed in many ways, depending on the application and there are a lot of studies on this topic alone. Luckily, depending on the programming language of choice, there are facilities that simplify the creation of hash functions. For example, the Apache Software Foundation provides the commons lang package to create such functions in java, while the Boost C++ Libraries provide functions to do the same in C++. In my experience, using these functions greatly simplifies your life if you want to use hash tables.
Now, let's say we want to put a new [key,value] pair into a hash table. The given key will be compared to each key in the bucket corresponding to the key hash code. If the key is already there, its value will be replaced with the new one, otherwise the pair will be simply added to the bucket. This is the behavior we expect since each key maps to one value only. Similarly if we are looking for the value mapped to a given key, the hash table looks for the [key,value] pair in the bucket corresponding to the key hash code and returns the value (or nothing if the key is not there). If the buckets contain a small number of elements (and we will assume they will), the insertion time and access time are both O(1). For these two basic operations to work properly it must be possible to compare the keys to each other.

Java Hashtable
Now let's see what we need to use hash tables in java. First of all, it should be clear that we need to define a hash code function for the objects we intend to use as keys. The java Object class contains the hashCode() function, which should be overridden by the objects we want to use as keys. Second, we need to make sure that our keys can be compared to each other. This is done by overriding another method from the Object class, the equals() method.
The HashCodeBuilder class and the EqualsBuilder class from the Apache Commons Lang package allow to easily create these two function. Here's an example of a class that's ready to be used as a hash table key:

 import org.apache.commons.lang3.builder.EqualsBuilder;  
 import org.apache.commons.lang3.builder.HashCodeBuilder;  
 public class Point {  
      private final int x, y;  
      public Point(int x, int y) {  
           this.x = x;  
           this.y = y;  
      }  
      @Override  
      public int hashCode() {  
           return new HashCodeBuilder().append(x).append(y).toHashCode();  
      }  
      @Override  
      public boolean equals(Object other) {  
           if (other instanceof Point == false) {  
                return false;  
           }  
           if (this == other) {  
                return true;  
           }  
           Point rhs = (Point) other;  
           return new EqualsBuilder().append(x, rhs.x).append(y, rhs.y).isEquals();  
      }  
 }  

The Point class represents a simple data structure to store integer coordinates on a plane. The use of EqualsBuilder is probably an overkill for such a simple class but I think it's good practice to familiarize with it since it provides interesting features, e.g., the ability to use the super class' equals method as its basis.

Now the class Point can be used in a java Hashtable or HashSet (similar in behavior to a table, but only stores keys, no values). The use of final members in the class Point shouldn't surprise. It makes perfect sense that the members that contribute to the computation of the hash code won't change during the program execution. If this happened for a key already in the hash table, its hash code would suddenly change and thus any consequent access would fail to find the key because the hash table would look in a different bucket than before. Here's an example using the Point class:

 java.util.Hashtable<Point, Integer> table = new java.util.Hashtable<Point, Integer>();  
 table.put(new Point(0, 0), 0);  
 table.put(new Point(0, 1), 5);  
 table.put(new Point(1, 0), 8);  
 table.put(new Point(1, 1), 10);  
 // replacing a value  
 table.put(new Point(1, 0), 2);  
 System.out.println(table.get(new Point(1, 1)));  
 System.out.println(table.get(new Point(1, 0)));  

Running the code will print 10 and 2. Note that the type of the value of choice (Integer) is irrelevant to the example.

Double pitfall
here's an interesting example using the java Double class as a key. The functions hashCode() and equals() are already defined for this class and they (usually) work properly. However, I ran in an interesting behavior that can be reproduced easily with the following code (java 1.7):

 java.util.Hashtable<Double, String> table = new java.util.Hashtable<Double, String>();  
 table.put(0.1, "George");  
 table.put(Double.NaN, "Paul");  
 table.put(0.0, "John");  
 System.out.println(table.get(0.0));  
 // is this the same as before?  
 System.out.println(table.get(-0.0));  
 // replacing?  
 table.put(-0.0, "Ringo");  
 System.out.println(table.get(0.0));  
 System.out.println(table.get(-0.0));  
 System.out.println(table.get(Double.NaN));  

This example shows how the hashCode() function for the Double class seems to violate the assumption that two identical objects will necessarily lead to the same hash code: the hash codes for the value 0.0 and -0.0 are different. In fact, although 0.0 and -0.0 are the same number, their binary representations are different, thus the different hash codes (the hash code is computed using this binary representation). The design choice that led to the definition of this hash function can be considered poor, although it's consistent with the java guidelines to define hashCode(). Similarly, the equals() method has the same odd behavior:

 double positiveZero = 0.0, negativeZero = -0.0;  
 System.out.println(new Double(positiveZero).equals(new Double(negativeZero)));  
 System.out.println(positiveZero == negativeZero);  

The same applies to the Float class. My suggestion when using floating point values (or tuples of them) as keys in a java hash table is to make sure that only one of the two binary representations of zero is used throughout the code. For example:

 import org.apache.commons.lang3.builder.EqualsBuilder;  
 import org.apache.commons.lang3.builder.HashCodeBuilder;  
 public class PointFloat {  
      private final float x, y;  
      public PointFloat(float x, float y) {  
           if (x == 0)  
                x = 0;  
           if (y == 0)  
                y = 0;  
           this.x = x;  
           this.y = y;  
      }  
      @Override  
      public int hashCode() {  
           return new HashCodeBuilder().append(x).append(y).toHashCode();  
      }  
      @Override  
      public boolean equals(Object other) {  
           if (other instanceof PointFloat == false) {  
                return false;  
           }  
           if (this == other) {  
                return true;  
           }  
           PointFloat rhs = (PointFloat) other;  
           return new EqualsBuilder().append(x, rhs.x).append(y, rhs.y).isEquals();  
      }  
      public static void main(String[] args) {  
           java.util.Hashtable<PointFloat, Integer> table = new java.util.Hashtable<PointFloat, Integer>();  
           table.put(new PointFloat(0f, 0f), 0);  
           // replacing now works correctly  
           table.put(new PointFloat(-0f, 0f), 1);  
           table.put(new PointFloat(0f, -0f), 2);  
           table.put(new PointFloat(-0f, 1f), 5);  
           table.put(new PointFloat(1f, 0f), 8);  
           table.put(new PointFloat(1f, 1f), 10);  
           table.put(new PointFloat(1f, 0f), 3);  
           System.out.println(table.get(new PointFloat(1f, 1f)));  
           System.out.println(table.get(new PointFloat(1f, 0f)));  
           System.out.println(table.get(new PointFloat(0f, 0f)));  
      }  
 }  

The class constructor makes sure that if its members x,y are equal to zero, only the positive zero representation is used. Since the two member variables are declared final it's safe to assume that only the positive zero representation is used. The hash table now behaves as expected (the first 4 lines in the constructor can be commented to trigger the unwanted behavior).