Saturday, May 10, 2014

Java ArrayList vs CopyOnWriteArrayList

ArrayList:

ArrayList is a basic implementation of List interface in Collection framework.It extends AbstractList. ArrayList supports dynamic array that can grow as needed.

Some of the important methods in ArrayList are

void add(int index,Object element):add the element at the specified index.
void add(Object element): Add the element at the end of the list.
void  clear(): clears the list when called on the list.
Object remove(int index): Remove the element at the specified location

We need an iterator to iterate over the list. ArrayList iterator is fail-fast by design.That means as soon as the underlying data structure changes after creating iterator it will throw java.util.ConcurrentModificationException.


Internally when we create an array list, it will maintains a modCount variable which will keep track of the modification count and every time we use add, remove or trimToSize method, it increments. expectedModCount is the iterator variable that is initialized when we create iterator with same value as modCount. This explains why we don’t get exception if we use set method to replace any existing element.

So basically iterator throws ConcurrentModificationException if list size is changed.

Let's run the program to see 


 package misc;  
 import java.util.ArrayList;  
 import java.util.Iterator;  
 import java.util.List;  
 public class CopyOnArrayListExample {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           List<String> list = new ArrayList<String>();  
           list.add("James Gosling");  
           list.add("Brendan Eich");  
           list.add("Rod Johnson");  
           list.add("Gavin King");  
           list.add("Un Known");  
           Iterator<String> itr = list.iterator();  
           while (itr.hasNext()) {  
                String str = itr.next();  
                System.out.println(str);  
                if(str.equals("Un Known")) list.remove("Un Known");}  
      }  
 }  

Output:

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
at java.util.AbstractList$Itr.next(AbstractList.java:343)
at misc.CopyOnArrayListExample.main(CopyOnArrayListExample.java:30)

As you can see, ArrayList iterator doesn't allow concurrent modification when we iterating.If we need to do concurrent modification then we need  CopyOnWriteArrayList.

Lets see CopyOnWriteArrayList in action.


package misc;  
 import java.util.Iterator;  
 import java.util.List;  
 import java.util.concurrent.CopyOnWriteArrayList;  
 public class CopyOnArrayListExample {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           List<String> list = new CopyOnWriteArrayList<String>();  
           list.add("James Gosling");  
           list.add("Brendan Eich");  
           list.add("Rod Johnson");  
           list.add("Gavin King");  
           list.add("Un Known");  
           Iterator<String> itr = list.iterator();  
           while (itr.hasNext()) {  
                String str = itr.next();  
                System.out.println(str);  
                if(str.equals("Un Known")) list.remove("Un Known");}  
      }  
 }  

In above code, we just changed the class definition from ArrayList to CopyOnWriteArrayList and see the output below.

James Gosling
Brendan Eich
Rod Johnson
Gavin King
Un Known

As you can see, the above code doesn't throw any exception as this one is thread safe variant of ArrayList.

Few things about CopyOnWriteArrayList from official documentation

A thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.
This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don't want to synchronize traversals, yet need to preclude interference among concurrent threads. The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove, set, and add) are not supported. These methods throw UnsupportedOperationException.

All elements are permitted, including null.

Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a CopyOnWriteArrayList happen-before actions subsequent to the access or removal of that element from the CopyOnWriteArrayList in another thread.

Thanks for visiting my blog!!!!!!!!

Sample Programs for Java Interviews-Series 1

Bubble Sort:

Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.

Bubble sort has worst-case and average complexity both О(n2), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other О(n2) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large.

Sample Program:


package sortings.BubbleSort;  
 public class BubbleSortExample {  
      public static void main(String a[]) {  
           int i;  
           int array[] = { 12, 9, 4, 99, 120, 1, 3, 10 };  
           bubble_srt(array, array.length);  
           System.out.print("Values after sorting: ");  
           for (i = 0; i < array.length; i++)  
                System.out.print(array[i] + " ");  
      }  
      public static void bubble_srt(int a[], int n) {  
           int i, j, t = 0;  
           for (i = 0; i < n; i++) {  
                for (j = 1; j < (n - i); j++) {  
                     if (a[j - 1] > a[j]) {  
                          t = a[j - 1];  
                          a[j - 1] = a[j];  
                          a[j] = t;  
                     }  
                }  
           }  
      }  
 }  


Output:

Values after sorting: 1  3  4  9  10  12  99  120


Fibonacci Series:

The Fibonacci sequence is a set of numbers that starts with a one or a zero, followed by a one, and proceeds based on the rule that each number (called a Fibonacci number) is equal to the sum of the preceding two numbers. If the Fibonacci sequence is denoted F ( n ), where n is the first term in the sequence, the following equation obtains for n = 0, where the first two terms are defined as 0 and 1 by convention


F (0) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

Sample Program:


package ramesh.programming;  
 public class FibonocciExample {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           int n = 15;  
           int f1, f2 = 0, f3 = 1;  
           System.out.println(f2);  
           for (int i = 1; i <= n; i++) {  
                System.out.print(" "+f3);  
                f1 = f2;  
                f2 = f3;  
                f3 = f1 + f2;  
           }  
      }  
 }  

Output:  1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

Fibonacci using recursive method:


package ramesh.programming;  
 public class FibonocciRecursive {  
      /**  
       * @param args  
       */  
      public static long fib(long num) {  
           if (num <= 1) {  
                return num;  
           }  
           return fib(num - 1) + fib(num - 2);  
      }  
      public static void main(String[] args) {  
           long n = 15;  
           for (int i = 1; i <= n; i++) {  
                System.out.print(fib(i)+"");  
           }  
      }  
 }  

Output: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 

Reverse a Number:

This is a sample program to reverse a given integer number



package ramesh.misc;  
 /**  
  * @author RameshM  
  * A sample program for reversing a given integer number  
  */  
 public class ReverseIntegerNumber {  
      public int reverseNumber(int number) {  
           int reverse = 0;  
           while (number != 0) {  
                reverse = (reverse * 10);  
                reverse = reverse + (number % 10);  
                number = number / 10;  
           }  
           return reverse;  
      }  
      public static void main(String a[]) {  
           ReverseIntegerNumber reverse = new ReverseIntegerNumber();  
           // Not handling the cases where the number is less than or equal to zero  
           // for brevity purposes.  
           System.out.println("Number after reversing: "  
                     + reverse.reverseNumber(14789));  
      }  
 }  


Output:

98741


Thanks for visiting my blog!!!!!!!!!


Thursday, May 8, 2014

Design Patterns implementations in Java API

Abstract factory  (recognizeable by creational methods returning the factory itself which in turn can be used to create another abstract/interface type)
Builder  (recognizeable by creational methods returning the instance itself)
·         java.lang.StringBuilder#append()  (unsynchronized)
·         java.lang.StringBuffer#append()  (synchronized)
·         java.nio.ByteBuffer#put()  (also on CharBuffer , ShortBuffer , IntBuffer , LongBuffer , FloatBuffer  and DoubleBuffer )
·         All implementations of java.lang.Appendable 
Factory method  (recognizeable by creational methods returning an implementation of an abstract/interface type)
·         java.util.Calendar#getInstance() 
·         java.net.URLStreamHandlerFactory#createURLStreamHandler(String)  (Returns singleton object per protocol)
Prototype  (recognizeable by creational methods returning a different instance of itself with the same properties)
·         java.lang.Object#clone()  (the class has to implement java.lang.Cloneable )
Singleton  (recognizeable by creational methods returning the same instance (usually of itself) everytime)
·         java.lang.Runtime#getRuntime() 
·         java.awt.Desktop#getDesktop() 


Adapter  (recognizeable by creational methods taking an instance of different abstract/interface type and returning an implementation of own/another abstract/interface type which decorates/overrides the given instance)
·         java.util.Arrays#asList() 
·         java.io.InputStreamReader(InputStream)  (returns a Reader)
·         java.io.OutputStreamWriter(OutputStream)  (returns a Writer)
Bridge  (recognizeable by creational methods taking an instance of different abstract/interface type and returning an implementation of own abstract/interface type which delegates/uses the given instance)
·         None comes to mind yet. A fictive example would be new LinkedHashMap(LinkedHashSet<K>, List<V>) which returns an unmodifiable linked map which doesn't clone the items, but uses them. The java.util.Collections#newSetFromMap()  and singletonXXX()  methods however comes close.
Composite  (recognizeable by behavioral methods taking an instance of same abstract/interface type into a tree structure)
·         java.awt.Container#add(Component)  (practically all over Swing thus)
·         javax.faces.component.UIComponent#getChildren()  (practically all over JSF UI thus)
Decorator  (recognizeable by creational methods taking an instance of same abstract/interface type which adds additional behaviour)
·         All subclasses of java.io.InputStream , OutputStream , Reader  and Writer  have a constructor taking an instance of same type.
·         java.util.Collections , the checkedXXX() , synchronizedXXX()  and unmodifiableXXX()  methods.
Facade  (recognizeable by behavioral methods which internally uses instances of different independent abstract/interface types)
·         javax.faces.context.FacesContext , it internally uses among others the abstract/interface types LifeCycle , ViewHandler , NavigationHandler  and many more without that the enduser has to worry about it (which are however overrideable by injection).
·         javax.faces.context.ExternalContext , which internally uses ServletContext , HttpSession , HttpServletRequest , HttpServletResponse , etc.
Flyweight  (recognizeable by creational methods returning a cached instance, a bit the "multiton" idea)
·         java.lang.Integer#valueOf(int)  (also on Boolean , Byte , Character , Short  and Long )
Proxy  (recognizeable by creational methods which returns an implementation of given abstract/interface type which in turndelegates/uses a different implementation of given abstract/interface type)
·         java.lang.reflect.Proxy 
·         java.rmi.* , the whole API actually.
The Wikipedia example is IMHO a bit poor, lazy loading has actually completely nothing to do with the proxy pattern at all.


Chain of responsibility  (recognizeable by behavioral methods which (indirectly) invokes the same method in anotherimplementation of same abstract/interface type in a queue)
·         java.util.logging.Logger#log() 
·         javax.servlet.Filter#doFilter() 
Command  (recognizeable by behavioral methods in an abstract/interface type which invokes a method in an implementation of adifferent abstract/interface type which has been encapsulated by the command implementation during its creation)
·         All implementations of java.lang.Runnable 
·         All implementations of javax.swing.Action 
Interpreter  (recognizeable by behavioral methods returning a structurally different instance/type of the given instance/type; note that parsing/formatting is not part of the pattern, determining the pattern and how to apply it is)
·         java.util.Pattern 
·         java.text.Normalizer 
·         All subclasses of java.text.Format 
·         All subclasses of javax.el.ELResolver 
Iterator  (recognizeable by behavioral methods sequentially returning instances of a different type from a queue)
·         All implementations of java.util.Iterator  (thus among others also java.util.Scanner !).
·         All implementations of java.util.Enumeration 
Mediator  (recognizeable by behavioral methods taking an instance of different abstract/interface type (usually using the command pattern) which delegates/uses the given instance)
·         java.util.Timer  (all scheduleXXX() methods)
·         java.util.concurrent.ExecutorService  (the invokeXXX() and submit() methods)
·         java.util.concurrent.ScheduledExecutorService  (all scheduleXXX() methods)
·         java.lang.reflect.Method#invoke() 
Memento  (recognizeable by behavioral methods which internally changes the state of the whole instance)
·         java.util.Date  (the setter methods do that, Date is internally represented by a long value)
·         All implementations of java.io.Serializable 
·         All implementations of javax.faces.component.StateHolder 
Observer (or Publish/Subscribe)  (recognizeable by behavioral methods which invokes a method on an instance ofanother abstract/interface type, depending on own state)
·         java.util.Observer /java.util.Observable  (rarely used in real world though)
·         All implementations of java.util.EventListener  (practically all over Swing thus)
·         javax.faces.event.PhaseListener 
State  (recognizeable by behavioral methods which changes its behaviour depending on the instance's state which can be controlled externally)
·         javax.faces.lifecycle.LifeCycle#execute()  (controlled by FacesServlet , the behaviour is dependent on current phase (state) of JSF lifecycle)
Strategy  (recognizeable by behavioral methods in an abstract/interface type which invokes a method in an implementation of adifferent abstract/interface type which has been passed-in as method argument into the strategy implementation)
·         java.util.Comparator#compare() , executed by among others Collections#sort().
·         javax.servlet.http.HttpServlet , the service() and all doXXX() methods take HttpServletRequest and HttpServletResponse and the implementor has to process them (and not to get hold of them as instance variables!).
·         javax.servlet.Filter#doFilter() 
Template method  (recognizeable by behavioral methods which already have a "default" behaviour definied by an abstract type)
·         All non-abstract methods of java.io.InputStream , java.io.OutputStream , java.io.Reader  and java.io.Writer .
·         All non-abstract methods of java.util.AbstractList , java.util.AbstractSet  and java.util.AbstractMap .
·         javax.servlet.http.HttpServlet , all the doXXX() methods by default sends a HTTP 405 "Method Not Allowed" error to the response. You're free to implement none or any of them.
Visitor  (recognizeable by two different abstract/interface types which has methods definied which takes each the otherabstract/interface type; the one actually calls the method of the other and the other executes the desired strategy on it)
·         javax.lang.model.element.Element  and ElementVisitor 
·         javax.lang.model.type.TypeMirror  and TypeVisitor 



I found this in stackoverflow  and thought of sharing and keep it for my future reference

Courtesy: BalusC

You can see the complete discussion at the below url

http://stackoverflow.com/questions/1673841/examples-of-gof-design-patterns/2707195#2707195

Thanks for visiting my blog.....