Saturday, February 1, 2014

Tricky aspects of Anonymous Classes in Java

I have discussed briefly about anonymous classes in my earlier Inner class post. Some of the aspects of Anonymous classes are confusing which require more elaborate explanation. And few aspects are not well known to most of the programmers. So, I am revisiting these aspects of Anonymous class in detail here.

[Brush up Inner Class and Anonymous class basics - here]
[Java 7 Specification of Anonymous class - here]

As a refresher; Anonymous classes are declared inline inside another class, and hence they are inner as well. So we can call them as Anonymous class or Anonymous Inner class. Also, Anonymous class can never be static and abstract and they are implicitly final [Java Specification]. 


Compact and Efficient Code

If you use Anonymous classes properly, you can reduce the number of lines of code. Check out below example. It shows three styles of creating an instance of thread using Anonymous class.

 public class AnonymousSample {  
      public static void main(String[] args) {  
   
           // first approach  
           Runnable r = new Runnable() {  
                public void run() {  
                     System.out.println("run !");  
                }  
           };  
           Thread t = new Thread(r);  
           t.start();  
   
           // second approach  
           Thread tt = new Thread(new Runnable() {  
                public void run() {  
                     System.out.println("run !");  
                }  
           });  
           tt.start();  
   
           // third approach  
           new Thread() {  
                public void run() {  
                     System.out.println("run !");  
                }  
           }.start();  
      }  
 }  

All the above approaches achieve the same thing, but clearly, the third approach is much more compact and cleaner way. 

Can't have an explicit constructor

Yes, Anonymous class can't have a constructor.
There is a workaround, though. You can declare a local final variable and declare an instance initialization block as shown below:

 public class AnonymousConstructor {  
      public static void main(String[] args) {  
           final int attribute;  
           Object obj = new Object() {  
                {  
                     attribute = 20;  
                     System.out.println("arg = " + attribute);  
                     method();  
                }  
   
                public void method() {  
                     System.out.println("inside method");  
                }  
           };  
      }  
 }  


But, there is still a problem.
The variable attribute can't be modified inside the inner class (compiler forces you to make it final). So, we haven't been able to truly initialize/construct the variable inside initialization block. 

But there is a hack for it as well!
Java treats final objects and final primitives differently.

When an object is declared as final, its reference can't be changed but you can change the value contained in it. In below example, I have created a dummy array to contain the primitive value. (Remember that in Java array is also an object).

 public class AnonymousConstructor {  
      public static void main(String[] args) {  
           final int attribute[] = { 10 };  
           Object obj = new Object() {  
                {  
                     attribute[0] = 20;  
                     System.out.println("arg = " + attribute[0]);  
                     method();  
                }  
   
                public void method() {  
                     System.out.println("inside method");  
                }  
           };  
      }  
 }  
Bingo!!! So you can get around the limitation of no explicit constructor.

Double Brace Initialization

This is one of the unknown features of Java. It comes in handy to initialize Collection APIs (List, Set, Map) in a very compact manner. 

 import java.util.ArrayList;  
 import java.util.List;  
   
 public class DoubleBraceInitialization {  
      public static void main(String[] args) {  
           List<String> list = new ArrayList<String>() {  
                {  
                     add("abc");  
                     add("def");  
                }  
           };  
   
           System.out.println(" list is " + list);  
      }  
 }  

Output : list is [abc, def]
Note that, the second brace is instance initialization brace.
Want to read more about it? link

Can't access method outside class

Let's start with a problem directly to stress a point. What will be the output of the below code?

 import java.util.concurrent.Callable;  
 interface Sample{  
   public void sampleMethod();       
 }  
   
 public class AnonymouseMethodInvocation {  
      public static void main(String[] args) {  
           new Sample(){  
                public void sampleMethod(){  
                     System.out.println("inside sample method");  
                }  
                public void method(){  
                     System.out.println("sample method");  
                }  
           }.method();  
          
             
           Callable<String> c = new Callable<String>(){  
                @Override  
                public String call() throws Exception {  
                     return "hello";  
                }            
           };  
      }  
 }  

It won't compile.
Surprised???

The compiler will not allow you to call method m().
When you say

      Sample s = new Sample(){  };


Means that, Create an object of an Anonymous class that's inherited from class Sample.

The reference returned by the new expression is automatically upcast to a Sample reference.

So using superclass reference, you can call method contained in the base class, but not method added in subclass. Here, method m() is added in the anonymous class but sampleMethod() is from the base class itself. So you can call sampleMethod() but not method m().

---
do post your comments/questions below !!!

Tuesday, January 14, 2014

Detect Loop in a Linked List

Existence of loop/cycles in a linked list means that last node points to one of the existing nodes of the list instead of pointing to null. So normal approach of traversing the list until you find null will NOT work here. This is one of the most interesting and tricky problems of Linked List. In below sample; next pointer of Node 5, points to Node 3.

                                              1 -> 2 -> 3 -> 4 -> 5 -> 3


This is solved by the famous Tortoise and Hare Algorithm; also known as Floyd algorithm. I wanted to write this article on same, but dropped plan after finding few nicely written posts. So, in this post, I will be explaining an alternative and much easier solution to detect the cycle in a linked list.


Detect Using Map

Tortoise and Hare algorithm uses two pointers (slow and fast); these pointers traverse the list in such a way that fast runs twice as fast as the slower pointer. So, if both these pointers meet at some node; then it means there is a cycle/loop. This approach basically checks if a node points to an already traversed node (5 points to 3 in above example). 

An alternative approach is quite trivial compared to the normal approach but; it has some space overhead. Loop can be identified by storing nodes in a Map. And before putting the node; check if the node already exists. If the node already exists in the map then it means that Linked List has a loop.

Below method detects the loop. I have not given full source code of the linked list. You can get it from my earlier post here.


 public boolean loopDetector(Node<E> first) {  
           Node<E> t = first;  
           Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();  
           while (t != null) {  
                if (map.containsKey(t)) {  
                     System.out.println(" duplicate Node is --" + t  
                               + " having value :" + t.data);  
   
                     return true;  
                } else {  
                     map.put(t, t);  
                }  
                t = t.next;  
           }  
           return false;  
      }  

To test it, make sure that you create a linked list with a loop. To create a loop you need to refactor add method to take next reference as well. So in case of the cycle next reference will point to an existing node instead of pointing to null.

obj.add(item, previousNode);

Note here that, I have used, IdentityHashMap [Java Doc] implementation of Java. Instead of object equality, IdentityHashMap uses reference equality. It considers two keys k1 and k2 equal if and only if (k1==k2). So this map fits aptly in our case to check if the node is already added.

Friday, January 3, 2014

Find middle node of a LinkedList

Finding the middle node of a linked list by traversing the list twice is trivial. But what makes this problem interesting is; If you have to do this in a single pass/traversal. 

Here, I will be using Java to solve this problem. Java provides a built-in API LinkedList, so using inbuilt iterator and size method of this API, the middle element can be easily found. But that would defy the whole intention behind this problem. Better do it more crude way! 

In Linked List post, I have created a custom single linked list. I am reusing the same class here, and have added a new method/s to find the middle node.

Find Middle Node

Approach to find the middle node is: keep two references, one pointing to middle and other pointing to end of the list. Keep on traversing the list and make sure that middle reference always points to the middle node at any point of traversal. Done!!!

package algo;  
 /**  
  * Generic single linked list implementation with generics  
  *   
  * @author Siddheshwar  
  *   
  */  
 public class SingleLinkedList<E> {  
      Node<E> start; // points to the head or first node  
      /**  
       * Node class  
       */  
      private static class Node<E> {  
           E data;  
           Node<E> next;  
           public Node(E data, Node<E> next) {  
                this.data = data;  
                this.next = next;  
           }  
           public E getData() {  
                return data;  
           }  
           public Node<E> getNext() {  
                return next;  
           }  
           public void setNext(Node<E> next) {  
                this.next = next;  
           }  
      }  
      public void add(E d) {
           if (start == null) {  
                start = new Node<E>(d, null);  
           } else {  
                Node<E> tmp = start;  
                while (tmp.getNext() != null) {  
                     tmp = tmp.getNext();  
                }  
                tmp.setNext(new Node<E>(d, null));   // add at the end of list  
           }  
      }  
      public void print() {  
           Node<E> current = start;  
           System.out.print(" values in link-list are :");  
           while (current != null) {  
                System.out.print(current.getData() + "--> ");  
                current = current.getNext();  
           }  
           System.out.println("null");  
      }  
      /**  
       * Finds middle object/node of linked list  
       * Approach : increment middle node alternate time 
       * (i.e. when count is odd)  
       */  
      public Node<E> findMiddleNode(Node<E> start) {  
           if (start == null)  
                return null;  
           Node<Integer> end = (Node<Integer>) start;  
           Node<Integer> middle = (Node<Integer>) start;  
           int count = 0;  
           while (end != null) {  
                end = end.getNext();  
                // move middle pointer alternate times  
                if (count % 2 == 1) {  
                     middle = middle.getNext();  
                }  
                count++;  
           }  
           return (Node<E>) middle;  
      }  
      /**  
       * Find middle node - Alternate approach 
       *   
       */  
      public Node<E> middleNode(Node<E> start) {  
           if (start == null)  
                return null;  
           Node<Integer> end = (Node<Integer>) start;  
           Node<Integer> middle = (Node<Integer>) start;  
           while (end != null) {  
                end = end.getNext();  
                if (end != null) {  
                     end = end.getNext();  
                     middle = middle.getNext();  
                }  
           }  
           return (Node<E>) middle;  
      }  
      public static void main(String[] args) {  
           SingleLinkedList<Integer> sll = new SingleLinkedList<>();  
           sll.add(1);  
           sll.add(2);  
           sll.add(3);  
           sll.add(4);  
           sll.add(5);  
           sll.add(6);  
           sll.add(7);  
           sll.print();  
           Node<Integer> middle = sll.middleNode(sll.start);  
           System.out.println("Middle value --:" + middle.getData());  
           middle = sll.findMiddleNode(sll.start);  
           System.out.println("Middle value --:" + middle.getData());  
      }  
 } 

Output:
 values in link-list are :1--> 2--> 3--> 4--> 5--> 6--> 7--> null
Middle value --:4
Middle value --:4

Note that there are two methods to find the middle node; both are more or less same, though.


Complexity:
End reference traverses the list fully once (i.e. O(n) ) and middle reference traverses only till the middle of the list (i.e. n/2 nodes / O(n)). Summing up those two still makes its complexity as O(n).

You can use this approach to solve similar problems:
  • Find the nth node from the last.
  • Remove the middle node of the list. 
  • Pairwise swapping of nodes (1->2->3->4 becomes 2->1->4->3)
  • Split a linked list in 2 ( or 3) equal  or close to equal linked list
  • Delete the repeated elements from a linked list.
  • Append last n nodes of the list to the beginning. 

Tuesday, December 31, 2013

Java Bytecode or class file

This post, I will be focusing on the content of Java's class file, known as bytecodes.  Java Virtual Machine uses the stream of bytecode from the class file for executing the program. As a Java programmer one doesn't need to bother about internal structure and format of bytecodes at all, but it's worth knowing how it is organized under the hood.  

Reading Bytecodes

Before reading bytecodes, let's generate one first. I am taking a simple HelloWorld example for this. 

public class HelloWorld{
public static void main(String[] args){
System.out.println("Hello, World!");
}
}

Save above class in your editor to compile it (or compile manually through command prompt). Locate the generated class file and open the same in the text editor. Shown in the below screenshot :


Some of the text does look familiar but it doesn't make sense at all. In fact, it doesn't look like bytecode of the HelloWorld.java. It will make more sense if it had numbers( binary/hex). Even if you use the FileReader API of java to read the class file; the result will be the same. You will neither see the stream of bytes nor code mnemonics

Are we missing something ? Yes.
Class file consists of stream of bytecodes. So we need to read the file as an array of the byte as shown in below class.


import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
import javax.xml.bind.DatatypeConverter;

/**
 * Utility to read the contents of class file as byte stream
 * 
 * @author Siddheshwar
 * 
 */
public class ReadClassAsByteStream {

 public static byte[] readFileAsByteArray(String fle) throws IOException {
  RandomAccessFile f = new RandomAccessFile(new File(fle), "r");

  try {
   int length = (int) f.length();
   byte[] data = new byte[length];
   f.readFully(data);
   return data;
  } finally {
   f.close();
  }
 }

 // test method
 public static void main(String[] args) throws IOException {
  String file = "D://workspace/JavaSample/src/HelloWorld.class";
  byte[] b = null;

  try {
   b = readFileAsByteArray(file);
   // convert byte array to Hex
   System.out.println(DatatypeConverter.printHexBinary(b));
  } catch (IOException e) {
   e.printStackTrace();
  }
 }
}

Output:
CAFEBABE00000033001D0A0006000F09001000110800120A001300140700150700160100063C696E69743E010003282956010004436F646501000F4C696E654E756D6265725461626C650100046D61696E010016285B4C6A6176612F6C616E672F537472696E673B295601000A536F7572636546696C6501000F48656C6C6F576F726C642E6A6176610C000700080700170C0018001901000C48656C6C6F20576F726C642107001A0C001B001C01000A48656C6C6F576F726C640100106A6176612F6C616E672F4F626A6563740100106A6176612F6C616E672F53797374656D0100036F75740100154C6A6176612F696F2F5072696E7453747265616D3B0100136A6176612F696F2F5072696E7453747265616D0100077072696E746C6E010015284C6A6176612F6C616E672F537472696E673B2956002100050006000000000002000100070008000100090000001D00010001000000052AB70001B100000001000A000000060001000000010009000B000C00010009000000250002000100000009B200021203B60004B100000001000A0000000A000200000003000800040001000D00000002000E

Bingo !!! Now, this looks like what we were looking for.
In the main method, I have used DatatypeConverter API to convert the byte array into hex format to print the content in more compact format. 

What is Bytecode

Bytecode is a series of instructions for the Java Virtual Machine and it gets stored in the method area (of JVM). Each instruction consists of a one-byte opcode followed by zero or more operands. The opcode indicates the action to be taken by JVM. The number of opcodes is quite small  (<256) and hence one byte is enough to represent opcodes. This helps to keep the size of the class file compact.

Important Observations on Generated Bytecode

  1. Java class file is a binary stream of byte. These bytes are stored sequentially in class file, without any padding between adjacent items. 
  2. The absence of padding ensures that class file is compact and hence can be quickly transferred over the network. 
  3. Items which occupy more than one byte are split into multiple consecutive bytes in big-endian style (higher bytes first ).
  4. Notice that, the first four bytes are "CAFEBABE" -known as the magic number. The magic number makes the non-Java class file easier to identify. If the class file doesn't start with this magic number then it's definitely not a Java class file. 
  5. The second four bytes of the class file contain the minor and major version numbers. 

Mnemonics Representation of Bytecode

Bytecode of HelloWorld program can be even represented as mnemonics in a typical assembly language style. Java provides class file disassember utility named as javap for doing it. javap utility provides multiple options for printing the content of class file. You can also use ASM Eclipse plugin to see disassembled bytecode of a class in Eclipse.

D:\workspace\JavaSample\src>javap -c HelloWorld.class
Compiled from "HelloWorld.java"
public class HelloWorld {
  public HelloWorld();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  public static void main(java.lang.String[]);
    Code:
       0: getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;
       3: ldc           #3                  // String Hello World!
       5: invokevirtual #4                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
       8: return
}

Friday, December 20, 2013

Annotation parser in Java

Java SE 5 introduced Annotation processing API; which further got extended in Java 6 and in Java 7. Through this API, you can find annotations in your code base and then work with them. 

I have discussed the basics of Annotation in the previous post, link. In this post, I will be focusing on processing annotations put in a class file. 



Annotation Processor

This post will be diving deeper to understand how to process Annotations in a class file. If there is no logic/tool to process/parse annotations embedded in source code then annotations will look more like comments. Java provides support API to create these tools through reflection technique
Before finally looking into Annotation processors; let's see one sample annotation and its use. Below is a definition of an Annotation. Note, the meta-annotation put in below Annotation (meta-annotations have been discussed in the previous post). InvocationAnnotation will be used to specify how many times a method needs to run. 

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.METHOD)
public @interface InvocationAnnotation {
 int numberOfTimesToInvoke() default 1;
}


Now let's take a class where above annotation, InvocationAnnotation will be used. 


public class AnnotationUsage {
 @InvocationAnnotation(numberOfTimesToInvoke = 3)
 public void method1() {
  System.out.println(" method1 invocation ....3 times..");
 }

 @InvocationAnnotation
 public void method2() {
  System.out.println(" method2 invocation...1 time");
 }
}


Now let's turn to the real business of extracting information from above class and the performing task as expected.

import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;

public class ProcessAnnotationUsage {
 public static void main(String[] args) {
  AnnotationUsage at = new AnnotationUsage();
  Method[] methods = at.getClass().getMethods();

  for (Method m : methods) {

   InvocationAnnotation ia = m
     .getAnnotation(InvocationAnnotation.class);

   if (ia != null) {
    int count = ia.numberOfTimesToInvoke();

    for (int i = 0; i < count; i++) {
     try {
      m.invoke(at, null);
     } catch (IllegalAccessException 
      | IllegalArgumentException
      | InvocationTargetException e) {
      e.printStackTrace();
     }
    }
   }
  }
 }
}

Output :

method1 invocation ....3 times..

 method1 invocation ....3 times..

 method1 invocation ....3 times..

 method2 invocation...1 time


So above annotation processor reads annotation embedded in method through reflection. Then,  finds out how many times the method needs to be invoked and then finally does that using for loop. The output confirms the same. 

Java 5 also introduced an Annotation Processing Tool (APT) called as apt. And in JDK 6, apt was made part of the compiler.

---
do post your comments/questions below !!!