Solution for: java.lang.VerifyError: Bad method call from inside of a branch

I was using  Powermockito to write my junit test cases. When i ran my test case it started throwing  Verify Error.

Error
java.lang.VerifyError: Bad <init> method call from inside of a branch
Exception Details:
  Location:
   y/z/a/ABC.<init>(Lorg/powermock/core/IndicateReloadClass;)V @42: invokespecial
  Reason:
    Error exists in the bytecode
  Bytecode:
    0000000: 2a2b 4e4d 1300 c6b8 0051 04bd 0031 5903
    0000010: 2d53 1303 f6b8 0043 b800 ca3a 0519 05b2
    0000020: 005e a500 0e2a 01c0 00cc b700 cfa7 000a
    0000030: 2c2d b700 cf01 57b1                   
  Stackmap Table:
    full_frame(@48,{UninitializedThis,Object[#204],UninitializedThis,Object[#204],Top,Object[#49]},{})
    full_frame(@55,{Object[#2],Object[#204],Object[#2],Object[#204],Top,Object[#49]},{})

    at java.lang.Class.forName0(Native Method)
    at java.lang.Class.forName(Class.java:190)
    at javassist.runtime.Desc.getClassObject(Desc.java:43)
    at javassist.runtime.Desc.getClassType(Desc.java:152)
    at javassist.runtime.Desc.getType(Desc.java:122)
    at javassist.runtime.Desc.getType(Desc.java:78)
   

My application was running on java "1.7.0_67" and using power mockito "1.6.2". I was not knowing what is the wrong with my test cases.

Root Cause
The VM in JDK 7 uses the new verifier for code compiled in Java 7 mode, but falls back to the old one for code compiled in Java 6 mode. Thus, in theory there should be no problem.
They basically read the bytecode, tagged as Java 7 bytecode, and perform changes in Java 6 mode, saving the results still tagged in Java 7 mode. Thus, the VM in JDK 7 sees Java 7 bytecode and activates the new Java 7 verifier, which fails (or can fail) when it meet the bytecode manipulated in Java 6 mode.





Solution 
 We can solve this problem by 2 ways:

1. >By changing java version to older version (1.7.0_25)
2. By adding this VM runtime option: -XX:-UseSplitVerifier.

After applying this fix, power mockito worked fine for me. Hope it will work for you.

Trees In Data Structure

What is Tree:
A tree is a non linear data structure. A tree is a way of representing the hierarchical nature of a structure in graphical form.
A tree is a set of nodes that either:is empty or has a designated node, called the root, from
which hierarchically descend zero or more sub trees, which are also trees.

Terminology

• The Degree of a node is the number of sub trees of the nodes
• The Node with zero degree or has no children is called leaf or terminal node(E,H,C,I,K,G).
• A node that has subtrees is the parent of the roots of the subtrees
• The roots of these subtrees are the children of the node.
• Children of the same parent are siblings.
• The ancestors  of a node are all the nodes along the path from the root to the node.
• Root of tree is the node with no parents. There can be at most one root in a tree(node A in the above example)
• Children of same parent are called siblings(B,C, D are siblings).
• The height of a node is the length of the path from that node to deepest node. Height of a tree is the length of a path from root to deepest node in the tree.(Height of tree is 6 in the above example A to M)
• The depth of a node is the length of the path from root to that node.(depth of F is 3, A-D-F)
  

 Binary Tree:
     
        A tree is called binary tree if each node has zero child, one child or two children. Empty  tree is also a binary tree.
Example:

Binary Tree Traversal

1. DFS(Depth First Search): Depth-first traversal (Arkiletian traversal) is easily implemented via a stack
1. Pre-Order
2. Post Order
3. In Order
2. BFS (Breath First Search) is also known as level order in Tree. breadth-first traversal is easily implemented via a queue

 

Structure of Binary Tree:

public class BinaryTree {
    private int data;
    private BinaryTree left;
    private BinaryTree right;
   
    public BinaryTree() {
    }
    public BinaryTree(int data) {
        this.data=data;
    }
    public Integer getData() {
        return data;
    }
    public void setData(Integer data) {
        this.data = data;
    }
    public BinaryTree getLeft() {
        return left;
    }
    public void setLeft(BinaryTree left) {
        this.left = left;
    }
    public BinaryDataTree getRight() {
        return right;
    }
    public void setRight(BinaryTree right) {
        this.right = right;
    }
   
}






Operations on Binary Tree:

1. Inserting an element in to a tree.
2. Deleting an element from a tree.
3. Search for an element
4. Traversing a tree             
   

Auxiliary Operations:

1. Finding size of a tree
2. Height of a tree
3. LCA
4. Sum of the tree
5. Mirror Image etc.

Note: Will explain different problem on tree in next couple of articles. Subscribe for it.

Stack Implementation using single linked list in java

Stack is a data structure or collection that works on LIFO (Last In First Out) principle.


It is ordered list and order in which the data arrives is important. This means that the last thing we added (pushed) is the first thing that gets pulled (popped) off.

To understand how a stack works, think of a deck of playing cards that is face down. We can only easily access the card that is on top. When we want to look at the top card, there are two things we can do: we can peek at it, but leave it on the stack, or we can pop it off. When we pop off the top object, we are taking it off the stack. If we want to add another card to the top of the stack, we push.

Another example of stack is pile of plates of a cafeteria is a good example of stack. When a plate is required it is taken from the top of the stack. First plate placed on the stack is the last one to be used.

Stack ADT:
Following operations make a stack ADT.

Main Operations

• void push(Object data):Insert data onto stack in O(1) time complexity
• Object pop() Removes and returns the last inserted element from the stack in O(1) time complexity.

 Auxiliary Operations

• Object top():Returns the last inserted element without removing it.
• int size(): Returns the number of elements stored in stack.
• boolean isEmpty(): Indicates whether any elements are stored in stack or not.
• isStackFull(): Indicates whether stack is full or not.(Only when stack is bounded)

Stack can be implemented using array/linked list/queue.

Stack Example 

•  Recursive function internally usages stack to maintain the call stack.
• Even Java usages stack to maintain the method call hierarchy.

Stack Implementation Using Single Linked List:

Below is my Single Link List:

public class LinkList<T> {
    public LinkList() {
    }
    public LinkList(T data) {
        this.data = data;
    }
    private T data;
    private LinkList<T> next;
    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public LinkList<T> getNext() {
        return next;
    }
    public void setNext(LinkList<T> next) {
        this.next = next;
    }
}




Class LinkList has 2 members, one is data and other is reference to next node.

Stack Class:
public class StackUsingLinkedList<T> {
    LinkList<T> top = null;

    public void push(T data) {
        if (top == null) {
            top = new LinkList<T>(data);
        } else {
            LinkList<T> newNode = new LinkList<T>(data);
            newNode.setNext(top);
            top = newNode;
        }
    }

    public T pop() {
        T data = null;;
        if (isEmpty()) {
            System.out.println("Stack is Empty");
        } else {
            LinkList<T> temp=top;
            data = top.getData();
            top=top.getNext();
            temp.setNext(null);
        }
        return data;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public T top() {
        T data = null;;
        if (isEmpty()) {
            System.out.println("Stack is Empty");
        } else {
            data = top.getData();
        }
        return data;
    }
}

Explanation: Here if you noticed, we are adding new element at beginning of the linked list because to maintain the LIFO Principle and PUSH/POP both operation should be in O(1).


If we insert element at the last then we have to traversal through complete list. We can achieve this using two pointer but again we have to maintain 2 pointers.

PUSH Operation:
First, It checks whether Stack is empty or not. If yes then create a node and assign it to top, otherwise create a new node and new node's next will point to top and new node becomes top.

POP Operation: 
It also checks whether Stack is empty or not. If yes then Print stack is empty and return null, Otherwise take the top node and top becomes next node of the top.

Xml Signature Validation Failed

If you are getting below Exception while validating XML Signature

javax.xml.crypto.dsig.XMLSignatureException: javax.xml.crypto.URIReferenceException: com.sun.org.apache.xml.internal.security.utils.resolver.ResourceResolverException: Cannot resolve element with ID 







Now Digital Signature Policy has been change. 
Suppose you have below xml :

Node:

<test Id="my_271692"> 

Signature: 
<Reference URI="#my_271692"> 

In your code if you do:
XMLSignatureFactory factory = XMLSignatureFactory
                    .getInstance("DOM");
            javax.xml.crypto.dsig.XMLSignature signature = factory
                    .unmarshalXMLSignature(valContext);
  valid = signature.validate(valContext); 

Last line will throw exception: 
Now have to add below line to make it work:
DOMValidateContext valContext="...........

NodeList nl = doc.getElementsByTagNameNS(
               namespace, "test"); 
Element el = (Element) (n2.item(0));
            valContext.setIdAttributeNS(el, namespace, "Id"); 







Here I'm passing null because xmlns is not there for test tag. otherwise pass the namespace.
It will work fine.


 

Blocking Queue Implementation in java

Blocking Queue is specific form of Queue. As Name say "Blocking", means it blocks  Some operation.
As we all know, Queue works on "FIFO" Principle. Where FIFO stands for "First in First Out".

You write the object at one end and retrieves the objects at other end.

What happens, When you try to get the Element from empty queue. It will return null.
Suppose we have a requirement where we have to insert fixed number of Element not more than that. In this case Once Queue is full, will not allow us to insert another element.

BlockingQueue  works on same principle, Only fixed number of Element can be inserted. If we try to take the element from empty Queue then operation would be blocked until there is size of the queue becomes greater than 0 i.e it contains at least one Element.
When you user try to insert an Element if the size is full then blocks the enqueue Operation until at size becomes lesser than fixed number.

Producer and consumer problem can easily be achieved using Blocking Queue.






Code Snippet:How to write our own Blocking Queue.


import java.util.LinkedList;
import java.util.concurrent.atomic.AtomicInteger;

public class MyBlockingQueue<T> {

    private final LinkedList<T> list;
    AtomicInteger count=null;
    final int upperbound;
   
    public MyBlockingQueue(int upperBound) {
        count=new AtomicInteger(0);
        list=new LinkedList<T>();
        this.upperbound=upperBound;
    }
    public synchronized void offer(T t){
        while(count.get()==upperbound){
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        notifyAll();
        list.addFirst(t);
        count.incrementAndGet();
       
    }
    public synchronized T take(){
        while(count.get()==0){
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
         notifyAll();
        T t=list.pollLast();
        count.decrementAndGet();
        return t;
    }
   
}
 






Test Class

public class MyBlockingQueueTest {
    public static void main(String[] args) {
        MyBlockingQueue<String> myBlockingQueue=new MyBlockingQueue<String>(7);
        Producer<String> producer=new Producer<String>(myBlockingQueue);
        Consumer<String> consumer=new Consumer<String>(myBlockingQueue);
        consumer.start();
        producer.start();
      
    }
   
    static class Producer<T> extends Thread{
        MyBlockingQueue<T> queue;
        public Producer(MyBlockingQueue<T> queue) {
            this.queue=queue;
        }
        @Override
        public void run() {
            for (int i = 0; i < 10; i++) {
                queue.offer((T)Integer.toString(i));
            }
        }
    }
    static class Consumer<T> extends Thread{
        MyBlockingQueue<T> queue;
        public Consumer(MyBlockingQueue<T> queue) {
            this.queue=queue;
        }
        @Override
        public void run() {
            for (int i = 0; i < 10; i++) {
                System.out.println(queue.take());
            }
        }
    }
}


Note: Blocking Queue can also be implemented using Semaphore

Creating a ThreadPool in java

Couple of ThreadPools introduced in Java 6.0 onwards. Based on the requirement we can pick one of these ThreadPool and use it in our Application.
To understand the existing ThreadPool, we need to know what does it mean by ThreadPool.







ThreadPool maintains 2 Queues, one is WorkerQueue and another is WorkQueue.
Workers Queue keep track of Worker who are going to work on the submitted work and number of work can be configured by Application developer. There is a separate discussion all together to decide number of worker thread. WorkQueue is use to store the Submitted tasks.

Thread can be Created onDemand or As soon as it initialized. If there is no task in the WorkQueue then all the thread will wait for task to submit. As soon as task gets submitted to WorkQueue, one of the Thread from worker queue will pick the task and execute it.



How we can implement our own ThreadPool or How can we achieve this functionality.

import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class MyThreadPool {

 private BlockingQueue<Runnable> taskQueue = null;
 private Set<MyThread> threads = new HashSet<MyThread>();
 private boolean isStopped = false;

 public MyThreadPool(int noOfThreads) {
  taskQueue = new LinkedBlockingQueue<Runnable>();

  for (int i = 0; i < noOfThreads; i++) {
   threads.add(new MyThread(taskQueue));
  }
  for (MyThread thread : threads) {
   thread.start();
  }
 }

 public synchronized void execute(Runnable task) throws Exception {
  if (this.isStopped)
   throw new IllegalStateException("ThreadPool is stopped");
  this.taskQueue.add(task);
 }

 public synchronized void stop() {
  this.isStopped = true;
  for (MyThread thread : threads) {
   thread.doStop();
  }
 }

}

/*
* My Thread class
*/

import java.util.concurrent.BlockingQueue;

public class MyThread extends Thread {

 private BlockingQueue<Runnable> taskQueue = null;
 private boolean isStopped = false;

 public MyThread(BlockingQueue<Runnable> queue) {
  taskQueue = queue;
 }

 public void run() {
  while (!isStopped()) {
   try {
    Runnable runnable = taskQueue.take();
    runnable.run();
   } catch (Exception e) {
    //log the exception
   }
  }
 }

 public synchronized void doStop() {
  isStopped = true;
  this.interrupt(); 
  // stop the thread and it will come out from run
       // method.
 }

 public synchronized boolean isStopped() {
  return isStopped;
 }
}

Test Class

import java.util.concurrent.Callable;
import java.util.concurrent.FutureTask;

public class ThreadPoolTest {
    public static void main(String[] args) {
        TestCallable testCallable = new TestCallable();
        FutureTask<String> futureTask = new FutureTask<String>(testCallable);
        FutureTask<String> futureTask1 = new FutureTask<String>(testCallable);
        FutureTask<String> futureTask2 = new FutureTask<String>(testCallable);
        FutureTask<String> futureTask3 = new FutureTask<String>(testCallable);
        MyThreadPool myThreadPool = new MyThreadPool(5);
        try {
            myThreadPool.execute(futureTask);
            myThreadPool.execute(futureTask1);
            myThreadPool.execute(futureTask2);
            myThreadPool.execute(futureTask3);
            System.out.println(futureTask.get());
            System.out.println(futureTask1.get());
            System.out.println(futureTask2.get());
            System.out.println(futureTask3.get());
            myThreadPool.stop();
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

    private static class TestCallable implements Callable<String> {
        @Override
        public String call() throws Exception {
            return "Done";
        }

    }
}

Even and odd printing using 2 threads

So many interviewer ask this question, Where one thread prints even and another thread prints odd number.
This problem statement is specification of producer and consumer problem in threading. Only difference is Even and odd thread should be executed but same time none of thread must not run more than 1 time continuously .







How to solve this problem using OOPS concepts :

Below class will be behaved as shared resource between 2 threads:

class B {
    int i = 0;
    boolean status = true;

    public synchronized void evenPrint() throws InterruptedException {   
       if (!status) {
            wait();
        }        
        notifyAll();
        status = !status;
        System.out.println("Even Thread--"+i);
        i = i+1;
      
    }

    public synchronized void oddPrint() throws InterruptedException {
        if (status) {
            wait();
        }
        notifyAll();
        System.out.println("Odd Thread--"+i);
        i = i+1;
        status = !status;
      
    }
}






Above class has a int variable and its value be incremented by 2 asap completes its execution, there is another variable to control the flow of execution of threads. There are 2 method which are synchronized and will be executed by respective threads.


1) Even Thread:

class EvenThread implements Runnable {
    B a;
    @Override
    public void run() {
        int i = 0;
        while (i < 10) {
            try {
                a.evenPrint();
                i++;
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
    public EvenThread(B a) {
        this.a = a;
    }
}

2) Odd Thread: 

class OddThread implements Runnable {
    B a;
    int i = 0;
    @Override
    public void run() {
        while (i < 10) {
            try {
                a.oddPrint();
                i++;
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
    public OddThread(B a) {
        this.a = a;
    }
}



Main Class:

public class EvenOddPrinting {
    public static void main(String[] args) {
        B a = new B();
        Thread even = new Thread(new EvenThread(a));
        Thread odd = new Thread(new OddThread(a));
        even.start();
        odd.start();
    }
}









when you run this program, output will be :

Even Thread--0
Odd Thread--1
Even Thread--2
Odd Thread--3
Even Thread--4
Odd Thread--5
Even Thread--6
Odd Thread--7
Even Thread--8
Odd Thread--9
Even Thread--10
Odd Thread--11
Even Thread--12
Odd Thread--13
Even Thread--14
Odd Thread--15
Even Thread--16
Odd Thread--17
Even Thread--18
Odd Thread--19

How to reverse bits in Java

Today, I'm going to explain how we to reverse the bits in Java. When you take any integer value internally which is represented by bits. Take an example:






int i=5;
By default integer is 32 bit operation:
bitwise (int i=5):
0000 0000  0000 0000  0000 0000  0000 0101
When we say reverse the bit
For above example output would be :
O/P: 1010 0000  0000 0000  0000 0000  0000 0000  ==> Left most bit is 1 means number is negative Now We have to take the 2's complement of o/p:
 
Final out put ==>(-)0110 0000  0000 0000  0000 0000 0000 0000==> -1610612736

How to achieve this:
Take the alternative bits like - 1,3,5,7,........31  and perform & operation with given input:
     0000 0000  0000 0000  0000 0000  0000 0101
&  0101 0101  0101 0101  0101 0101  0101 0101
                                                                                   
     0000 0000  0000 0000  0000 0000  0000 0101

left shift Shift with 1 bit
X==> 0000 0000 0000 0000 0000 0000  0000 1010
Now we have to do first 1 unsigned right shift and then perform & operation with alternative 1's

1 bit Right shift :  0000 0000  0000 0000  0000 0000  0000 0010
                       &   0101 0101  0101 0101  0101 0101  0101 0101
                                                                                                         
Y==>                    0000 0000  0000 0000  0000 0000  0000 0000







now
i==> X|Y

X==>  0000 0000 0000 0000  0000 0000  0000 1010
Y==> 0000 0000  0000 0000  0000 0000  0000 0000
                                                                                       
i==>  0000 0000  0000 0000  0000 0000  0000 1010

Now we have have to find again X and Y by masking 2 alternative bits(first step we did by using masking one alternative bit )

X=  0000 0000  0000 0000  0000 0000  0000 1000
Y=  0000 0000  0000 0000  0000 0000  0000 0010
i =   0000 0000  0000 0000  0000 0000  0000 1010

Now we have have to find again X and Y by masking 4 alternative bits:
X= 0000 0000  0000 0000  0000 0000  1010 0000
Y= 0000 0000  0000 0000  0000 0000  0000 0000
                                                                                
i=  0000 0000  0000 0000  0000 0000  1010 0000


Now we have have to find again X and Y by masking 8 alternative bits:
X=  0000 0000  0000 0000  1010 0000  0000 0000
Y=  0000 0000  0000 0000  0000 0000  0000 0000
 i=  0000 0000  0000 0000  1010 0000  0000 0000

 Now we have have to find again X and Y by masking 16  alternative bits:
X= 1010 0000  0000 0000  0000 0000  0000 0000
Y=  0000 0000  0000 0000  0000 0000  0000 0000
 i=  1010 0000  0000 0000  0000 0000  0000 0000

 Note: we can avoid masking  8 bits and 16 bits, we can have single statement, which is little tricky.

Now Left most bit is 1 means number is negative Now We have to take the 2's complement of o/p:
Final out put ==>(-)0110 0000  0000 0000  0000 0000 0000 0000==> -1610612736







Summary : How your reverse function will look like:

 int reverse(int i){
        i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
        i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
        i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
         i = (i & 0x00ff00ff) << 8 | (i >>> 8) & 0x00ff00ff;
         i = (i & 0x0000ffff) << 16 | (i >>> 16) & 0x0000ffff;
   return i;
} 

Volatile variable in java

In java, volatile variables are weaker form of synchronization, to ensure that updates to a variable are propagated predictably to other threads. When a field is declared volatile, the compiler and runtime are put on notice that this variable is shared and that operations on it should not be reordered with other memory operations.Volatile variables are not cached in registers or in caches where they are hidden from other processors, so a read of a volatile variable always returns the most recent write by any thread. Yet accessing a volatile variable performs no locking and so can not cause the executing thread to block, making volatile variable a lighter-weight synchronization mechanism than synchronize.





                  The visibility effects of a volatile variables extend beyond the value of the volatile variable itself. When thread A writes to a volatile variable and subsequently thread B reads that same variable, the value of all variables that were visible to A prior to writing to volatile variable become visible to B after reading the volatile variable.

Locks Vs Volatile:
  Locking can guarantee  both visibility and atomicity; volatile variables can only guarantee only visibility.

When to use volatile variables:
 We have to use volatile variables when all the following criteria are met:

•  Write to the variables do not depend on its current value, or we can ensure that only a single thread ever updates the value.
• The variable does not participate in invariants(exit condition) with other state variables and
• Locking is not required for any other reason while the variable is being accessed.

How to reverse Single linklist in java

Singly Linked Lists are a type of data structure. It is a type of list. In a singly linked list each node in the list stores the contents of the node and a pointer or reference to the next node in the list.It has below properties:

1. Elements can be inserted indefinitely.
2. They don’t take contiguous memory locations. For this reason, they are suitable to be used even if the disk or memory is fragmented.
3. You can traversal in one direction

We can reverse the linkedlist using 2 approach:

1. Iterative approach:

public LinkedList<Integer> reverse(LinkedList<Integer> header) {
        if (header == null) {
            return null;
        }
        LinkedList<Integer> prev = null;
        LinkedList<Integer> next = header;
        while (header != null) {
            next = header.getNext();
            header.setNext(prev);
            prev = header;
            header = next;
        }
        return prev;
    }






2. Recursive approach: 

 private LinkedList<Integer> reverseRecursiveWay(LinkedList<Integer> header) {
        if (header == null) {
            return null;
        }
        LinkedList<Integer> startNode = reverseRecursiveWay(header.getNext());
        if (startNode != null) {
            LinkedList<Integer> next = header.getNext();
            next.setNext(header);
            /* Below statement is required because when all the nodes
              are reverse,  reached to first node and
               want to make sure that initial header will not
              point to second element.*/
            header.setNext(null);
            return startNode;
        }
        return header;
    }






LinkedList class looks like: 

public class LinkedList<T> {
    public LinkedList() {

    }

    public LinkedList(T data) {
        this.data = data;
    }

    private T data;
    private LinkedList<T> next;

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public LinkList<T> getNext() {
        return next;
    }

    public void setNext(LinkedList<T> next) {
        this.next = next;
    }

}

How to convert String to Integer.

Most of the interviewer ask to this question. Believe me, it is so simple problem to solve and required basic knowledge. Lets see how we can do it java.





public class ConvertStringNumberToInteger{
           public static void main(String args[]) throws NumberFormatException{
                       String input="12345";
                        int output=0;
                       for(int j=0;j<input.length();j++){
                             int temp=input.charAt(j)-'0';
                             if(0<=temp && temp<=9){
                                    throw new NumberFormatException("String should contain only number ");
                              }
                             output=output*10+temp;
                       }
                       System.out.println("output : "+output)
             }
}