Euclid's GCD Algorithm

Before turning our head to Euclid's algorithm for calculating GCD, let's cover the more fundamental approach to calculate GCD.

GCD (Greatest Common Divisor)

GCD of two integers A and B is the largest integer that divides them both without a remainder. It is also known as GCF(Greatest Common Factor), HCF(Highest Common Factor) and GCM(Greatest Common Measure).

So GCD(A, B) will be between 1 and min(A, B), both inclusive. So it can be implemented as shown below:

 public int gcd(int a, int b) {

   for (int i = Math.min(a, b); i > 1; i--) {

     if (a % i == 0 && b % i == 0) {

       return i;

     }

   }

   return 1;

 }

Euclid's Algorithm

Above algorithm is not very efficient, as in worst case it can end up doing min(a,b) modulo operations. Euclid's or Euclidian algorithm is an efficient algorithm for calculating GCD of two numbers. And due to its efficiency and simplicity, it is one of the oldest numerical algorithms which is still in use. This algorithm iterates over the two numbers until the remainder is 0. 

To calculate GCD,

Express first in terms of the second number i.e. A = B*K + C

Now repeat the operation for K and C (until C is 0)

The last non-zero remainder is GCD. 

GCD(18,12) => 18 = 12*1 + 6

GCD(6,1)    =>  6 = 1*6 + 0

GCD = 6

Recurrence relation would be:

GCD(A,0) = A

GCD(A,B) = GCD(B, A mod B), for B>0

Implementation

Recursive implementation is quite trivial:

public int euclidGcd(int a, int b){

  if(b ==0 ) return a;

  return euclidGcd(b, a%b);

}

--
keep coding !!!

Lambda Expression in Java 8

Let's go functional!

Lambda Expression (Closure or Anonymous method) is one of the most important additions to Java 8.  In fact, it's the most incredible additions to language in its history; it is going to change the way we write programs in Java.  With this new feature, Java adds one of the modern programming technique, Functional Programming.

This is useful for Functional Interfaces (the interface that requires exactly one method to be implemented). Runnable, Callable, Comparable and other interfaces which just have a single method are called functional interfaces. You can even define your own interface with a single method to unleash the power of Lambdas.

Syntax of Lambda

Lambda consists of 3 parts :

1. Parenthesized set of parameters
2. Arrow sign ( -> )
3. Body in form of single expression or a block 

i.e. (Parameter1 p1, Parameter2 p2)            ->                           { }
       (parameters)                                   (arrow sign)          (method body)

Properties:

• It doesn't have an explicit name for the method, so it's called an anonymous method as well
• It can throw Exceptions
• It's more like a method (and not a class), it has a list of parameter, body and return type
• It can be passed as an argument to a method and can be stored as a value in a variable

Runnable Implementation without Lambdas

Before going all out on Lambda. Let's see how these interfaces get implemented without it.

Approach 1: Implement the interface

public class MyRunnableImpl implements Runnable{
     @override
     public void run(){
         //TODO: Implementation
     }
}

Approach 2: Using anonymous (inner) class
   

Runnable task = new Runnable(){

    public void run(){

       //TODO: Implementation

   }

};

Approach 2 is better than first but still, it's quite verbose and there is hardly any scope of reusability.

Implementing functional interfaces through Lambda

The compiler knows beforehand that the Runnable interface has only one method to be implemented. So this lack of ambiguity around which method needs to be implemented helps in making the Runnable implementation more compact and efficient using lambdas. 

So using Lambda; above code can be replaced as :

Runnable task = () -> System.out.println("inside run method");
or 
Runnable task = () -> { System.out.println("inside run method"); };

And on similar lines you can implement Callable as well :

Callable<Integer> task = () -> {

       Random r = new Random(101);

       return r.nextInt(101);

};

If the method takes some argument, then they get passed inside parentheses. Let's take case of Comparator interface:

Comparator<String> c = (String a, String b) -> { return a.compareTo(b); };

Before version 8, the lowest level of abstraction in Java was classes. Functions were not treated as the first-class citizen as you need to have an object handle to use functions (functions don't exist without object). But functions are as valuable and important as objects and classes. Programming languages with first-class functions let you find more opportunities for abstraction which means your code is smaller, lighter, more reusable and scalable.

Related Post: Functional Interfaces

---
keep coding !!!

Understanding JAVA EE Interceptors

Interceptors are used to implement orthogonal or cross-cutting concerns such as logging, auditing, profiling etc in Java EE applications. In this aspect, it is similar to aspect-oriented programming (AOP).

In Java EE 5, Interceptors were part of EBJs, but in later versions, Interceptors have evolved into a new specification of its own. Interceptors were split into an individual spec in Java EE 7 (Interceptors 1.2) and are part of Context and Dependency Injection(CDI) specification.  They can be applied to any managed classes/beans like EJBs, Servlets, SOAP and RESTful web services. Managed Beans are container-managed objects (unlike Java Beans or POJOs which run inside JVM).  In Java EE 7, Dependency Injection (JSR 330) and  CDI (JSR 299) are merged. You can refer to managed beans as CDI bean as well. These managed beans are injectable and interceptable.

In this post, I will be using terms CDI bean and managed bean interchangeably.

Interceptors

Interceptor is a class whose methods are invoked when methods on a target class are invoked. And this invocation of interceptors methods is performed by the container. Obviously, this would be possible if the target class and the interceptors both are managed by the container.  This is possible because beans managed by containers (servlet or EJB) provides the ability to intercept method invocation through interceptors. 

Interceptors are powerful means to decouple technical concerns from business logic. And it uses strongly typed annotations to achieve it instead of String-based identifiers. This way usage of XML descriptors is minimized. Interceptors use a mandatory deployment descriptor, bean.xml. This is required so that CDI is able to discover the bean from the classpath.

Below are interceptor metadata annotations (from javax.interceptor ):

• @AroundConstruct associates with the constructor of the target class
• @AroundInvoke associates with a business method and gets called while entering and exiting
• @AroundTimeout associates with timeout methods
• @PostConstruct & @PreDestroy on corresponding lifecycle events of the target class

Using Interceptors

Interceptors, intercept a particular target class so they have the same life cycle as that of the target class. Target class can have any number of associated interceptors.

Intercepting a REST Service

Interceptors can intercept any managed bean; so it can intercept servlet, REST entry point, EJB etc. I will be showing an example of intercepting a REST service.

import java.lang.annotation.ElementType;
import java.lang.annotation.Inherited;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;
import javax.interceptor.InterceptorBinding;

/**
 * Interface for logging/auditing JAX-RS requests
 *
 */
@Inherited
@InterceptorBinding
@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.METHOD, ElementType.TYPE})
public @interface Auditor {
}

import javax.inject.Inject;
import javax.interceptor.AroundInvoke;
import javax.interceptor.Interceptor;
import javax.interceptor.InvocationContext;
/**
 * CDI/Managed bean which intecepts REST API
 * Add @Interceptors(RestAuditor.class) to the target class/method
 *
 */
@Interceptor
@Auditor
public class RestAuditor {
 @AroundInvoke
 public Object intercept(InvocationContext context) throws Exception {
  //context.getMethod().getName())
               // audit/log the request
  return context.proceed();

  //control comes back after target method execution 
 }
}

<beans xmlns="http://java.sun.com/xml/ns/javaee"
   xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
   xsi:schemaLocation="
      http://java.sun.com/xml/ns/javaee 
      http://java.sun.com/xml/ns/javaee/beans_1_0.xsd">
   <interceptors>
        <class>RestAuditor</class>  <!--fully qualified class name -->
    </interceptors>
</beans>

So interceptor definition and the declaration of the interceptor in bean.xml completes the interceptor part. Now next step is to use above defined interceptor on a REST service. Please note that the intercept method will be called before actually calling the REST method and then again once REST method is complete, the control comes back. So the request as well response both can be logged in the intercept(..) method. Using the interceptor is quite trivial, we just need to annotate the REST class as shown below :

@Path("/sample")
@ApplicationScoped

@Interceptors(RestAuditor.class)  

public class SampleRestService implements Serializable {
 

 @GET
 @Produces(MediaType.APPLICATION_JSON)
 public boolean getLogs() {
  boolean resp = true;
  return resp;
 }
}

That's it!

Important Points

• If the application contains several jar files and you want to enable CDI across the application then you need to have beans.xml in each jar. Only then CDI will trigger bean discovery for each jar. 
• Interceptors can be applied to method as well as class level. If you want to intercept a specific method then put the annotation at method level only (NOT at class level as shown above).

References

• https://code.google.com/p/jee6-cdi/source/browse/tutorial/cdi-aop-example/src/main/java/org/cdi/advocacy/DebugingInterceptor.java?r=181
• http://blog.dblevins.com/2012/11/cdi-when-to-break-out-ejbs.html

--
keep coding !

TRIE data structure

TRIE, another Search Tree!

Trie is an infix of the word reTRIEval, and pronounced as TREE but to distinguish it from the tree some people also pronounce it as TRY. As the name suggests it is an efficient retrieval or searching data structure. 

The root node represents an empty string (""), if you go down one level it represents all single character words. Similarly, at level 10, trie represents words or prefixes of 10 letters/characters. It is a search tree where each vertex or node represents a single word or a prefix (but each node actually stores a single letter or character). 

Let's take a sample dictionary of 6 words.
Dictionary, D = {a, an, out, the, them, their}

You can use Hashing or Binary search tree to implement a dictionary,  but here we will use trie to implement it.

Below are trie representations of the above dictionary, D. Both left as well as right trie represents the same dictionary (two different representations). If you want to understand the trie the right one is more suitable and left one represents trie from the implementation point of view. Leaf nodes (colored in blue) represents the last node of a word so 'e' of the word 'the' will be the leaf node. The leaf node signals end of a word, but it can get extended further (like 'a' and 'an'). So every node which is the last character of the word will be the leaf node. The implementation can be achieved by a boolean flag.

Two TRIE representation of the same dictionary

Possible operations:
addWord(String): adds a single word to the trie
search(String): search if the given word or prefix exists in the trie
countWords(String): number of words that match in trie with the given word
countPrefixes(String): number of words that have given the prefix

Implementation

To make it simple, let's consider only English alphabets (a-z); and also make case insensitive. This means each node can have maximum of 26 children. So it's just a generalization of Binary Search Tree.

Java implementation this post, here. 

Trie implementation provides operations like add a word and find a word. If you understand the fundamentals, implementing other methods is not going to be difficult. 

Analyzing Performance

Cost of looking up a word or prefix in a vocabulary/dictionary implemented using trie depends only on the number of characters in the word/prefix. It doesn't depend on the size of the dictionary. This is an important distinction from the HashMap/HashTable based dictionary implementations.  As shown in the above diagram the cost of finding the word 'the' requires just 3 steps. 

Runtime complexity of lookup = O(length of word)

String comparison is considered as a single operation, so above can be generalized as O(1).

Trie implementation requires more memory than an array or tree. This is because at each level, the node takes space for 26 characters but not all of them will be used. But the space overhead gets compensated with the constant time search performance. 

References:

• http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries
• http://www.toptal.com/java/the-trie-a-neglected-data-structure
• http://marknelson.us/1996/08/01/suffix-trees/

---

keep coding !!!

TRIE implementation in Java

I have covered the fundamentals of trie in this post.

/**
 * TRIE implementation in Java 

 * Tries are general search tree where every node
 * can have some pre-defined number of children. Length of children is 26. Max
 * depth of trie is equal to max length of the word in the dictionary
 *
 * Constraints: 1. assume that all words are lowercase (uppercase letters are
 * converted to lowercase) 2. accept only a-z letters—no punctuation, no
 * hyphens, no accents, etc
 * 
 * Main Operations supported: 1. addword(..) : add a word to the dictionary 2.
 * search(..) : check if the given word exists in dictionary
 *
 * @author Siddheshwar
 */
public class Trie {
 private Node root;

 public Trie() {
  root = new Node();
 }

 /**
  * adds a dictionary word to the vocabolary or dictionary
  * 
  * @param word
  */
 public void addWord(String word) {
  if (word == null || !word.matches("[a-zA-Z]+")) { // or matches ("\\w+")
   return;
  }

  Node r = root;
  int index;
  for (char c : word.toLowerCase().toCharArray()) {
   index = this.getIndex(c);

   if (!r.hasChildAt(index)) {
    r = r.addChild(c);
   } else {
    r = r.getChildAt(index);
   }
  }
  r.setAsLeaf();
 }

 /**
  * Get index where the character will get mapped in the array 'a'/'A' will
  * be mapped to 0th, 'z'/'Z' will get mapped to 25th index
  * 
  * @param ch
  * @return index
  */
 private int getIndex(char ch) {
  // return (int)(ch - 'a');
  return String.valueOf(ch).codePointAt(0)
    - String.valueOf('a').codePointAt(0);
 }

 /**
  * Is word present in the trie
  * 
  * @param word
  * @return
  */
 public boolean contains(String word) {
  if (word == null)
   return true;
  Node r = root;
  for (char c : word.toCharArray()) {
   r = r.getChildAt(this.getIndex(c));
   if (r == null) {
    return false;
   }
  }
  return true;
 }

 /**
  * Returns the node (or null if word is not found)
  * 
  * @param word
  * @return Node
  */
 public Node getNodeEndingWithWord(String word) {
  if (word == null)
   return null;
  Node r = root;
  for (char c : word.toCharArray()) {
   r = r.getChildAt(this.getIndex(c));
   if (r == null) {
    return null;
   }
  }
  return r;
 }
}

import java.util.Arrays;
import java.util.List;

/**
 * Vertex or Node of a TRIE tree. Supports only alphabets a-z (ignores case) 'a'
 * occupies 0th position and 'z', 25th in Node array(i.e. children)
 */
public class Node {
 private Node[] childen;
 private boolean leaf;
 private char value;
 static final char NULL_CHAR = '\0';

 public Node() {
  childen = new Node[26];
  leaf = false;
  value = NULL_CHAR;
 }

 public Node(char c) {
  childen = new Node[26];
  leaf = false;
  value = c;
 }

 public List<Node> getChilden() {
  return Arrays.asList(childen);
 }

 public boolean hasChildAt(int index) {
  return this.childen[index] == null ? false : true;
 }

 public boolean isLeaf() {
  return leaf;
 }

 public char getValue() {
  return value;
 }

 public Node getChildAt(int index) {
  return this.childen[index];
 }

 public void setAsLeaf() {
  this.leaf = true;
 }

 public boolean isCharValid() {
  return this.value != NULL_CHAR ? true : false;
 }

 /**
  * add a child node to the current node
  * 
  * @param ch
  * @return Node
  */
 public Node addChild(char ch) {
  Node childNode = new Node(ch);
  // int index = (int)(ch - 'a'); prefer below approach
  int index = String.valueOf(ch).codePointAt(0)
    - String.valueOf('a').codePointAt(0);
  this.childen[index] = childNode;
  return childNode;
 }

 /**
  * Get count of valid children; upper limit is 26.
  * 
  * @return count
  */
 public int getChildrenCount() {
  int count = 0;
  for (int i = 0; i < 26; i++) {
   if (this.hasChildAt(i)) {
    count++;
   }
  }
  return count;
 }

 /**
  * Returns comma separated list of children for the node
  * 
  * @return
  */
 public String getChildren() {
  StringBuilder output = new StringBuilder();
  for (int i = 0; i < 26; i++) {
   if (this.hasChildAt(i)) {
    output.append((char) (i + 65)).append(",");
   }
  }
  return output.substring(0, output.length() - 1);
 }
}