Sunday, May 31, 2015

Lambda Calculas

Lambda Calculus

Lambda Calculus comes under formal system in mathematical logic.

Formal System in programming language has 2 aspects:

  1. Syntax – what the language looks like.
  2. Semantics – what is the meaning of words, signs and symbols.

Lambda Calculus is used for expressing based on abstraction and application using variable binding and substitution.

  • To make semantics simple λ-calculus incorporates two simplifications. 
    • First is that it treats the functional anonymously without explicit names. 
      • For example cubeSum(x, y, z) = (x * x * x) + (y * y * y) + (z * z * z) 
      • Can now be rewritten in anonymous form as
        (x, y, z) → (x * x * x) + (y * y * y) + (z * z * z)
    • Second simplification is that we can chain functions inside functions.
      x → (y →(some formulae))(parameter1)) (parameter2)


This is basics of Lambda Calculus. This post was intended to be just the basic introduction for Lambda.


In next post we will learn about Lambda Operator in Java, Functional Interface, How to use Lambda and when to use Lambda?

Convert List to String (Delimiters, Prefix and Suffix)

Convert ArrayList to String

To convert any collection to string AbstractCollection<E> class has a method called toString(). 

Suppose we have List of numbers from 1 to 5 then output of toString() is
[1, 2, 3, 4, 5]

Now in this post we will convert this Collection to String using our own method. Also we will make sure to insert a delimiter of our choice. In addition to that we will insert some prefix and suffix if needed to each element in the Collection.

First we will design our method for conversion of List<E> to String. Let’s say we have delimiter as “::”. So output would look like this
1::2::3::4::5

So for this we would iterate through the list and then append object of list and the delimiter. We will also make sure that delimiter is not appended at the end. Delimiter is always appended between two objects.
Let us write code for it.
              StringBuilder sb = new StringBuilder();
              Iterator<?> iter = c.iterator();
              sb.append(iter.next());
              while (iter.hasNext()) {
                     sb.append(delimiter).append(iter.next());
              }

Now the above code will work.
Now we will write code for appending prefix and suffix string to each element in list.
[1, 2, 3, 4, 5]
Prefix = “p”
Suffix=”s”
Delimiter=”$”

p1s$p2s$p3s$p4s$p5s


              StringBuilder sb = new StringBuilder();
              Iterator<?> iter = c.iterator();
             
              sb.append(prefix)
                .append(iter.next())
                .append(suffix);
             
              while (iter.hasNext()) {
                     sb.append(delimiter)
                       .append(prefix)
                       .append(iter.next())
                       .append(suffix);
              }

Entire program is below:

package org.collections;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

public class ConvertListToString {

       public static void main(String[] args) {

           List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
           System.out.println(list);
           String str = convert(list, "$");
           System.out.println(str);
       }

       public static String convert(Collection<?> c, String delimiter) {
              return convert(c, delimiter, "", "");
       }
      
       public static String convert(Collection<?> c
                                    String delimiter
                                    String prefix
                                    String suffix) {

              if (c == null) {
                     throw new 
                       NullPointerException("Input Collection can't be null");
              }

              delimiter = resolveNull(delimiter);
              prefix = resolveNull(prefix);
              suffix = resolveNull(suffix);

              StringBuilder sb = new StringBuilder();
              Iterator<?> iter = c.iterator();
             
              sb.append(prefix)
                .append(iter.next())
                .append(suffix);
             
              while (iter.hasNext()) {
                     sb.append(delimiter)
                       .append(prefix)
                       .append(iter.next())
                       .append(suffix);
              }
              return sb.toString();
       }
      
       public static String resolveNull(String str) {
              return str == null ? "" : str;
       }
      
}



That’s all on List to String. 

When to use List and Set

When to use List<E> and Set<E>


In this post we will see when to use List<E> and Set<E>.

  • If we need to maintain insertion order and duplicates then use List<E>.
  • And if insertion order and duplicates are not required then use Set<E>. We can maintain order of elements in Set<E> using LinkedHashSet<E> class.


Difference between List and Set

Differences between List<E> and Set<E>

List<E> and Set<E> are part of Java CollectionsFramework and are used widely. Most common implementation of List<E> is ArrayList<E> and for Set<E> is HashSet<E>. There are few differences between the two and in this post we will see them.

This post is part of Java Collections Interview Questionsand you can find several interview questions here.

List<E> and Set<E> difference.
  • First difference is that List<E> allows you to insert duplicate elements. While Set<E> isn’t kind enough to let you insert duplicate elements. If you try to value that exists in Set<E> then it will replace that value. Set<E> contains unique elements.
  • Second difference is that List<E> maintains the order of Insertion. As discussed here List<E> maintains the order of insertion of elements. Set<E> does not maintain order. But we can use SortedSet<E> which can store elements defined by Comparator<T>. LinkedHashSet<E>(concrete implementation of Set<E>) allows you to maintain the insertion order but does not allow indexed access.
  • Third difference is in terms of index access or Random access of elements. List<E> interface has ArrayList<E> as concrete implementation. ArrayList<E> is backed by an array and hence it supports indexed retrieval of elements. This cannot be achieved by any concrete implementation of Set<E>.
  • Fourth difference is that we can use Iterator<E> and ListIterator<E> to iterate through the List<E>. For Set<E> we can only use Iterator<E> interface.



That’s all on difference between List<E> and Set<E>. Click here to see when to use List<E> and Set<E>.

Saturday, May 30, 2015

How to convert List to Set in 3 different ways

How to convert List<E> to Set<E>? 

At times needs arise to convert one collection to another. Same is for this question. Conversion to list to set is one such thing to do.

Now remember when we learned about root Java Collections Framework interface called Collection<E> interface, we learnt about addAll(Collection<? extends E> c).

boolean addAll(Collection<? extends E> c); - This method is used for bulk operation. It takes another collection of type    <? extends E> i.e. any type that extends E. We use <? extends E> if we need to get elements from Collection. So here we use this bounded wildcard and get all elements from collection c specified in parameter and insert into another collection. It returns true if collection is changed because of call to this method.

  • Below is code for using addAll(Collection<? extends E> c) method

              Set<String> set2=new HashSet<String>();
              set2.addAll(list);


  • We can do this by iterating list and inserting each element into Set using add(E e) method.

              Set<String> set3=new HashSet<String>();
              for(String str:list){
                     set3.add(str);
              }

  • Now as we are using class HashSet<E> we can use its parameterized constructor.
    • public HashSet(Collection<? extends E> c)
    • Now we just put list as parameter
      • Set<String> set1=new HashSet<String>(list);


Below is the code for all 3 ways:
package org.collections;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ListToSet {

       public static void main(String[] args) {

              List<String> list = new ArrayList<String>();
              list.add("Adam");
              list.add("Cain");
              list.add("Eve");
              list.add("Adam");
              list.add("Sam");
              list.add("Dean");

              Set<String> set1 = new HashSet<String>(list);
              System.out.println("By parameterized constructor "+set1);

              Set<String> set2 = new HashSet<String>();
              set2.addAll(list);
              System.out.println("Using addAll(..) method "+set1);

              Set<String> set3 = new HashSet<String>();
              for (String str : list) {
                     set3.add(str);
              }
              System.out.println("Using add(e) method "+set1);

       }

}

Output is as follows;

By parameterized constructor [Adam, Eve, Cain, Sam, Dean]
Using addAll(..) method [Adam, Eve, Cain, Sam, Dean]
Using add(e) method [Adam, Eve, Cain, Sam, Dean]

As you see the size of List<E> and Set<E> is different. The reason is List<E> contains duplicates but Set<E> does not accept duplicates.

Set<E> is unordered collection.


The better ways to solve this question is to either use parameterized constructor or use addAll(Collection<? extends E> c) method.

Comparison of 2 ArrayList in 2 ways

Comparison of 2 ArrayList<E>

Problem statement is that given two ArrayList we have to compare them. If both the list are identical then return true else return false.

We will solve this particular question in 2 different methods.

  • First, we will compare them by searching for each element from list1 to list2 and if found remove that element from both lists. The searching is done by contains(Object o) method which take O(n) time for each element. In all, searching for all elements in other list results in O(n2).

/**
               * Take iterator and iterate through the list.
               * */
              Iterator<Integer> iter = l1.iterator();
              while (iter.hasNext()) {
                     /**Take the next element from list1 into x*/
                     Integer x = iter.next();
                     /**Check if x is in list2*/
                     int index = l2.indexOf(x);
                     /**If not then return false*/
                     if (index == -1) {
                           return false;
                     } else {
                           /**If found then remove it from both lists.*/
                           l2.remove(index);
                           iter.remove();
                     }
              }

  • Second, we will sort both the lists and then we will use equals method of AbstractList<E> class to compare lists. Why equals(Object o) method of AbstractList<E>? Because ArrayList<E> class extends AbstractList<E> class and hence child inherits properties of parent. And ArrayList<E> does not have equals(Object o) but AbstractList<E> has it. Let us understand equals(Object o) method of AbstractList<E> class then we will move forward with our solution.
    • I have written a post regarding Abstract<E> and its methods are also explained. I would recommend visiting it.
    • Below is the explanation for equals(Object o) method.
    • equals(Object o) - Checks if 2 lists are same or not. More precisely both should be instance of List, both lists must have same elements & same size. Below is equals(Object o) method with comments.
    /**
     * This method is used to compare this list with the parameter
     * Object o for equality.
     * If both of them are list, both have same size, both have same element pairs
     * then only lists are same else return false.
     * */
   public boolean equals(Object o) {
          /**
           * If o and this are same the return true
           * */
        if (o == this)
            return true;
        /**
         * If o is not instance of List then return false.
         * */
        if (!(o instanceof List))
            return false;
        //Take listIterator() for this list.
        ListIterator<E> e1 = listIterator();

        /**
         * Now o is instance of List so we will cast it to List<?> and get
         * listIterator() for it.
         * */
        ListIterator<?> e2 = ((List<?>) o).listIterator();
        /**
         * Now we compare if both of them has next or not.
         * Reason is if one list's size is less then another
         * than this test will fail.
         * Pretty neat approach
         * */
        while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            //Comparaision of elements of both lists
            if (!(o1==null ? o2==null : o1.equals(o2)))
                return false;
        }
        /**
         * If any of list has next element then lists are not same
         * return false.
         * */
        return !(e1.hasNext() || e2.hasNext());
    }

Now below is the code for comparing 2 lists for second method.
              /**
               * Sort both the lists
               */
              Collections.sort(l1);
              Collections.sort(l2);

              return l1.equals(l2);
Below is the entire code:
package arraylist;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class ArrayListEquals {

       public static void main(String[] args) {

              List<Integer> l1 = new ArrayList<Integer>();
              l1.add(1);
              l1.add(2);
              l1.add(20);
              l1.add(12);
              l1.add(2);
              List<Integer> l2 = new ArrayList<Integer>();
              l2.add(2);
              l2.add(20);
              l2.add(1);
              l2.add(12);
              l2.add(21);
              boolean bool = compareBySort(l1, l2 = null);
              System.out.println(bool);
       }

       /**
        * This method is used to compare two list's
        * returns true if both lists has same elements
        * else returns false
        * */
       public static boolean compare(List<Integer> l1, List<Integer> l2) {

              if(bothNull(l1, l2)){
                     return true;
              }

              if(eitherNullOrNoSameSize(l1,l2)){
                     return false;
              }

              /**
               * Take iterator and iterate through the list.
               * */
              Iterator<Integer> iter = l1.iterator();
              while (iter.hasNext()) {
                     /**Take the next element from list1 into x*/
                     Integer x = iter.next();
                     /**Check if x is in list2*/
                     int index = l2.indexOf(x);
                     /**If not then return false*/
                     if (index == -1) {
                           return false;
                     } else {
                           /**If found then remove it from both lists.*/
                           l2.remove(index);
                           iter.remove();
                     }
              }
              return (l1.size() == 0 && l2.size() == 0);
       }

       public static boolean compareBySort(List<Integer> l1, List<Integer> l2) {

              if(bothNull(l1, l2)){
                     return true;
              }

              if(eitherNullOrNoSameSize(l1,l2)){
                     return false;
              }
              /**
               * Sort both the lists
               */
              Collections.sort(l1);
              Collections.sort(l2);

              return l1.equals(l2);
       }

       public static boolean bothNull(List<Integer> l1, List<Integer> l2){
              /**
               * If both the lists are null return true
               * */
              if (l1 == null && l2 == null) {
                     return true;
              }
              return false;
       }
      
       public static boolean eitherNullOrNoSameSize(List<Integer> l1, List<Integer> l2){
              /**
               * 3 conditions leads to return false.
               * First two conditions are if either lists are null then return false.
               * Third is size are not same then return false.
               * */
              if ((l1 == null && l2 != null)
                           || (l1 != null && l2 == null)
                           || (l1.size() != l2.size())) {
                     return true;
              }
              return false;
       }
      
}

Let us run some test cases against it.
  • If both lists are null return true.
  • If both lists are empty return true.
  • If either list is null (i.e. first list is not null or second list is not null) then return false.
  • Lists with same elements passes the test.
  • Lists with different elements fails the test.


Below are the test cases for both the methods written above.

package arraylist;

import java.util.ArrayList;
import java.util.List;

import junit.framework.Assert;

import org.junit.Test;

public class ArrayListEqualsTestCase {

       /**
        * Comparison for both list
        * Both lists are null
        * */
       @Test
       public void testForBothNull() {
              ArrayList<Integer> l1 = null;
              ArrayList<Integer> l2 = null;
              Assert.assertTrue(ArrayListEquals.compare(l1, l2));
       }

       /**
        * Comparison for either list is null
        * */
       @Test
       public void testForFirstListNull() {
              ArrayList<Integer> l1 = null;
              ArrayList<Integer> l2 = new ArrayList<Integer>();
              Assert.assertFalse(ArrayListEquals.compare(l1, l2));
       }

       /**
        * Comparison for either list is null
        * */
       @Test
       public void testForSecondListNull() {
              ArrayList<Integer> l1 = new ArrayList<Integer>();
              ArrayList<Integer> l2 = null;
              Assert.assertFalse(ArrayListEquals.compare(l1, l2));
       }

       /**
        * Test for empty lists.
        * */
       @Test
       public void testForEmptyLists(){
              ArrayList<Integer> l1 = new ArrayList<Integer>();
              ArrayList<Integer> l2 = new ArrayList<Integer>();
              Assert.assertTrue(ArrayListEquals.compare(l1, l2));
       }
      
       /**
        * Comparison that returns false.
        * */
       @Test
       public void compareFails() {
              List<Integer> l1 = new ArrayList<Integer>();
              l1.add(1);
              l1.add(2);
              l1.add(20);
              l1.add(12);
              l1.add(2);
              List<Integer> l2 = new ArrayList<Integer>();
              l2.add(2);
              l2.add(20);
              l2.add(1);
              l2.add(12);
              l2.add(21);
              Assert.assertFalse(ArrayListEquals.compare(l1, l2));
       }

       /**
        * Comparison that returns true.
        * */
       @Test
       public void comparePasses() {
              List<Integer> l1 = new ArrayList<Integer>();
              l1.add(1);
              l1.add(2);
              l1.add(20);
              l1.add(12);
              l1.add(2);
              List<Integer> l2 = new ArrayList<Integer>();
              l2.add(2);
              l2.add(20);
              l2.add(1);
              l2.add(12);
              l2.add(2);
              Assert.assertTrue(ArrayListEquals.compare(l1, l2));
       }

       // ------------------
      
       /**
        * Comparison for both list
        * Both lists are null
        * */
       @Test
       public void testForBothNullBySort() {
              ArrayList<Integer> l1 = null;
              ArrayList<Integer> l2 = null;
              Assert.assertTrue(ArrayListEquals.compareBySort(l1, l2));
       }

       /**
        * Comparison for either list is null
        * */
       @Test
       public void testForFirstListNullBySort() {
              ArrayList<Integer> l1 = null;
              ArrayList<Integer> l2 = new ArrayList<Integer>();
              Assert.assertFalse(ArrayListEquals.compareBySort(l1, l2));
       }

       /**
        * Comparison for either list is null
        * */
       @Test
       public void testForSecondListNullBySort() {
              ArrayList<Integer> l1 = new ArrayList<Integer>();
              ArrayList<Integer> l2 = null;
              Assert.assertFalse(ArrayListEquals.compareBySort(l1, l2));
       }

       /**
        * Test for empty lists.
        * */
       @Test
       public void testForEmptyListsBySort(){
              ArrayList<Integer> l1 = new ArrayList<Integer>();
              ArrayList<Integer> l2 = new ArrayList<Integer>();
              Assert.assertTrue(ArrayListEquals.compareBySort(l1, l2));
       }
      
       /**
        * Comparison that returns false.
        * */
       @Test
       public void compareFailsBySort() {
              List<Integer> l1 = new ArrayList<Integer>();
              l1.add(1);
              l1.add(2);
              l1.add(20);
              l1.add(12);
              l1.add(2);
              List<Integer> l2 = new ArrayList<Integer>();
              l2.add(2);
              l2.add(20);
              l2.add(1);
              l2.add(12);
              l2.add(21);
              Assert.assertFalse(ArrayListEquals.compareBySort(l1, l2));
       }

       /**
        * Comparison that returns true.
        * */
       @Test
       public void comparePassesBySort() {
              List<Integer> l1 = new ArrayList<Integer>();
              l1.add(1);
              l1.add(2);
              l1.add(20);
              l1.add(12);
              l1.add(2);
              List<Integer> l2 = new ArrayList<Integer>();
              l2.add(2);
              l2.add(20);
              l2.add(1);
              l2.add(12);
              l2.add(2);
              Assert.assertTrue(ArrayListEquals.compareBySort(l1, l2));
       }

}



That’s all on comparison of two lists.

Do check other blogs such as iterating over List<E>(6 ways), iterating over Map<K, V>(5 ways), Differences and similarities between LinkedList<E> and ArrayList<E> and when to use them.


I am also writing on Collection Interview Questions. Do check it out.

Ads Inside Post