Finding Longest substring having exactly ‘k’ unique characters

Posted on April 22, 2015 by neer1304

We can start with a simple case k = 2 then we can generalize our solution.

Algorithm

1) Take 3 pointers to keep track of two ends of substring and start of last substring.
2) Increment end pointer until we find second different character while start points to first char.
3) If end pointer equals length of string return as string has one type of char only (base case).
4) Else store current two different characters in an array.
5) Loop until string length
6) Check if current character is same or different
7) If we have one of the same character then check if current character is different than previous character then update lastGroupStart variable to keep track of new potential longest substring.
8) If we have different character then compare local maximal substring with global maximal substring length. Update the start, lastGroupStart variable and correspondingly char array for new potential substring.
9) After loop check for one more potential substring from start to string length.

#include<iostream>
#include<string>

using namespace std;

string longestTwoUniqueChar(string str)
{
    int start = 0;
    int i = 1;
    string res = "";
    string maxs = "";

    while (i < str.length() && str[i] == str[start])
        i++;

    if (i == str.length())
        return str;

    char chars[2] = {str[start], str[i]};
    int lastGroupStart = 0;

    while (i < str.length())
    {
        if (str[i] == chars[0] || str[i] == chars[1])
        {
            if (str[i] != str[i - 1])
                lastGroupStart = i;
        }
        else
        {
            res = str.substr(start,i-start);
            if(res.length() > maxs.length())
                maxs = res;
        
            start = lastGroupStart;
            lastGroupStart = i;
            chars[0] = str[start];
            chars[1] = str[lastGroupStart];
        }
        i++;
    }
      res = str.substr(start,str.length()-start);
      if(res.length() > maxs.length())
        maxs = res;
      return res;
}

int main()
{
    string s  = "aabaaddaa";
    cout<<longestTwoUniqueChar(s)<<endl; 
    return 0;
}

Now we can come to generic solution of ‘k’ unique character substring.

Algorithm :-

1) Take an unordered map with key as character and its last position as value.
2) Loop through the length of string.
3) If size of map is less than ‘k’ or we have previously seen present character then update map entry.
4) Else we have found new character (k+1 th),
4a) Update the global maxima.
4b) Delete the earliest character from map which is not previous character.
4c) update the start pointer and map entry.
5) update the global maxima after loop.

#include<iostream>
#include<string>
#include<unordered_map>
#include<limits.h>

using namespace std;

string longestKCharSubstring(string s, int k)
{
    int i, max_len = 0, start = 0;
    // either unique char & its last pos
    unordered_map<char, int> ht;
    string res = "";
    string maxs = "";
    char prev_char;

    for (i = 0; i < s.size(); i++)
    {
        if (ht.size() < k || ht.find(s[i]) != ht.end())
        {
            ht[s[i]] = i;
            prev_char = s[i];
        }
        else
        { 
            // map size greater than k and character does not appear in first k unique character         
            // (k + 1)-th char
            res = s.substr(start,i-start);
            if(res.length() > maxs.length())
                maxs = res;
           
            // start points to the next of the earliest char
            char earliest_char;          
            for (auto key : ht)
                if (key.second < INT_MAX && key.first!=prev_char)
                    earliest_char = key.first;          
            start = ht[earliest_char] + 1;
            // replace earliest_char         
            ht.erase(earliest_char);
            ht[s[i]] = i;
        }
    }
    res = s.substr(start,i-start);
     if(res.length() > maxs.length())
                maxs = res;
    return maxs;
}


int main()
{
    string s  = "aaabbbbaaaacccccccc";  
    cout<<longestKCharSubstring(s,2)<<endl;
    return 0;
}
Posted in Algorithms | Tagged , | Leave a comment

Efficient Algorithm for finding Longest Increasing Subsequence

Posted on April 4, 2015 by neer1304

Longest Increasing Subsequence(LIS) problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

For ex in sequence –

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 a longest increasing subsequence is 0, 2, 6, 9, 13, 15. This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance, 0, 4, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15
are other increasing subsequences of equal length in the same input sequence.

First we shall look into an O(n^2) solution using Dynamic Programming(DP)

Let dp[i] be the length of LIS which is ending at element at index i. To compute dp[i] we will look at all indices j dp[i] and array[j] < array[i](as it has to be increasing). If this is true we can update the current optimum for dp[i]. To find the global optimum for the array we can take the maximum value from DP[0..N-1].

Implementation 

#include <stdio.h>
#include <stdlib.h>

int LISdp(int arr[], int n)
{
   int maxLength = 1, bestEnd = 0;
   int dp[n]; //dp[i] be the length of LIS which is ending at element at index i
   dp[0] = 1; // for first element lis = 1
   int prev[n]; // keep the prev array to rebuild LIS sequence
   prev[0] = -1; // to find the terminating condition

   int i,j;

   for(i=1;i=0;j--)
       {
           if(dp[j]+1>dp[i] && arr[j]maxLength)
       {
           bestEnd = i;
           maxLength = dp[i];
       }
   }
   printf("The lis is - \n");

   while(bestEnd!=-1)
   {
       printf("%d ",arr[bestEnd]); // it prints LIS in reverse order
       bestEnd = prev[bestEnd];
   }

   return maxLength;
}

int main()
{
  int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
  int n = sizeof(arr)/sizeof(arr[0]);
  printf("\nLength of LIS is %d\n", LISdp( arr, n ) );
  return 0;
}

This problem can be solved more efficiently in O(nlogn) time. We shall apply binary search (logn) for every ‘n’ elements in the array to find if it can be part of current LIS.

Let S[pos] be defined as the smallest integer at end of an increasing sequence of length pos.

We iterate through the array and for every element 3 cases can arise :-
1) arr[i] > ‘last Element in S’, than append arr[i] at last of ‘S’ this means we have found new LIS.
2) arr[i] < 'first Element in S', replace the first element in 'S' with arr[i].
3) Otherwise binary search(since S is sorted) for a position 'k' such that S[k-1]<arr[i]<S[k]

For ex –

Set of integers: 10 22 9 33 21 50 41 60

Steps:

0. S = {} – Initialize S to the empty set
1. S = {10} – New largest LIS
2. S = {10, 22} – New largest LIS
3. S = {9, 22} – Changed 10 to 9
4. S = {9, 22, 33} – New largest LIS
5. S = {9, 21, 33} – Changed 22 to 21
6. S = {9, 21, 33, 50} – New Largest LIS
7. S = {9, 21, 33, 41} – Changed 50 to 41
8. S = {9, 21, 33, 41, 60} – New Largest LIS

The rationale for the above algorithm is that in order to get largest sequence we replace larger elements with smaller elements which can be potential source of new LIS.

To reconstruct the actual LIS we will again use a parent array. Let parent[i] be the predecessor of element with index i in the LIS ending at element with index i. We shall store index of elements of arr[] in S.

The actual LIS is:

arr[S[lastElementOfS]],
arr[parent[S[lastElementOfS]]],
arr[parent[parent[S[lastElementOfS]]]],
………………………………….

Implementation

#include<stdio.h>
#include<stdlib.h>

int binarySearch(int arr[], int t[], int left, int right, int key)
{
    int mid;

    while(right-left>1)
    {
        int mid = left + (right-left)/2;
        if(arr[t[mid]]>=key)
            right = mid;
        else
            left = mid;
    }
    return right;
}

int LisSequence(int arr[], int n)
{
    int S[n];
    int parent[n];
    int len;

    S[0] = 0;
    parent[0] = -1;

    len=1;

    for(int i=1;i<n;i++)
    {
        if(arr[i]arr[S[len-1]]) // case 2
        {
            parent[i] = S[len-1];
            S[len++] = i;
        }
        else // case 3
        {
            int k = binarySearch(arr,S,-1,len-1,arr[i]);
            parent[i] = S[k-1];
            S[k] = i;
        }
    }
    printf("LIS of given input is - \n");
    while(S[len-1]!=-1)
    {
        printf("%d ",arr[S[len-1]]);
        S[len-1] = parent[S[len-1]];
    }
    return len;
}

int main()
{
  int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
  int n = sizeof(arr)/sizeof(arr[0]);
  printf("\nLength of LIS is %d\n", LisSequence( arr, n ) );
  return 0;
}

References :-
http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming
http://www.geeksforgeeks.org/construction-of-longest-monotonically-increasing-subsequence-n-log-n/

Posted in Algorithms, Data Structures | Tagged , | Leave a comment

Connect nodes at the same level for a generic Binary tree using constant space

Posted on April 3, 2015 by neer1304

Algorithm
1) Take a pointer curr(points to root)
2) Loop while curr!=NULL
3) Take 2 more pointers to keep track of prev and next(initially NULL) nodes
4) In a nested while loop traverse each level one by one
4) Update the next pointer before starting level order traversal so that we can resume for next level once this level is finished.
5) Traverse the left and right nodes(pre-order fashion) of current node. Check if prev pointer is set then do prev->nextRight = curr->left or curr->right and update prev pointer.
6) Once curr is NULL set it to next for next level traversal.

#include 
#include 

struct node
{
    int data;
    struct node *left;
    struct node *right;
    struct node *nextRight;
};

 void connectNodes(struct node  *root)
 {
    struct node *curr = root;
    while (curr)
    {
        struct node *prev = NULL, *next = NULL;
        while (curr)  // traverse the current level
        {
            if (!next)
                next = curr->left ? curr->left : curr->right; // save the pointer for next level
            if (curr->left) // traverse in pre-order
            {
                if (prev)   // if prev exists then prev and curr->left are at same level
                    prev->nextRight = curr->left;
                prev = curr->left; // save prev pointer
            }
            if (curr->right)
            {
                if (prev)
                    prev->nextRight = curr->right;
                prev = curr->right;
            }
            curr = curr->nextRight;
        }
        curr = next;
    }
}

struct node* newnode(int data)
{
    struct node* node = (struct node*)
                        malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->nextRight = NULL;

    return(node);
}

/* Driver program to test above functions*/
int main()
{
  struct node *root = newnode(1);
  root->left = newnode(2);
  root->right = newnode(3);
  root->left->left = newnode(4);
  root->right->left = newnode(5);
  root->right->right = newnode(6);
  root->right->left->left = newnode(8);
  root->right->right->right = newnode(7);
 
    connectNodes(root);

    // Let us check the values of nextRight pointers
    printf("Following are populated nextRight pointers in the tree "
           "(-1 is printed if there is no nextRight) \n");
    printf("nextRight of %d is %d \n", root->data,
           root->nextRight? root->nextRight->data: -1);
    printf("nextRight of %d is %d \n", root->left->data,
           root->left->nextRight? root->left->nextRight->data: -1);
    printf("nextRight of %d is %d \n", root->right->data,
           root->right->nextRight? root->right->nextRight->data: -1);

    printf("nextRight of %d is %d \n", root->left->left->data,
           root->left->left->nextRight? root->left->left->nextRight->data: -1);
    printf("nextRight of %d is %d \n", root->right->right->data,
           root->right->right->nextRight? root->right->right->nextRight->data: -1);

    printf("nextRight of %d is %d \n", root->right->left->data,
           root->right->left->nextRight? root->right->left->nextRight->data: -1);
    printf("nextRight of %d is %d \n", root->right->left->left->data,
           root->right->left->left->nextRight? root->right->left->left->nextRight->data: -1);

    printf("nextRight of %d is %d \n", root->right->right->right->data,
           root->right->right->right->nextRight? root->right->right->right->nextRight->data: -1);

    return 0;
}
Posted in Algorithms, Data Structures | Tagged , | Leave a comment

Segregate even and odd numbers in Linked List

Posted on April 3, 2015 by neer1304

Algorithm

1) If head is NULL or one nodes in linked list return.
2) Move the end pointer to end of LL and count the number of nodes in list.
3) Update the head pointer to first even node in the list.
4) Traverse the linked list till all nodes are traversed.
5) If odd node is found move it to end of LL by updating curr, new_endp and prev pointer.
6) If even node found keep moving curr and prev pointer forward.

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *next;
};

void segregateEvenOdd(struct node **head_ref)
{
    if(*head_ref==NULL || (*head_ref)->next==NULL)
        return;

    struct node *endp = *head_ref;
    struct node *curr = *head_ref;
    int num_nodes=1;

    while(endp->next!=NULL)
    {
        endp = endp->next;
        num_nodes++;
    }

    struct node *new_endp = endp;
    struct node *feven=curr;

    while(feven!=NULL && (feven->data)%2!=0)
        feven = feven->next;

     if(feven!= NULL)
     {
        *head_ref = feven; // head ptr will point to first even node
     }
     else
     {
         return; //all nodes are odd
     }

    struct node *prev = NULL;
    int cnt = 0;

    while(curr!=new_endp && cntdata)%2!=0) // if odd move curr to end of LL
        {
            new_endp->next = curr;
            if(prev!=NULL)
                prev->next = curr->next; // update prev pointer
            curr = curr->next;  //update curr pointer
            new_endp->next->next = NULL;
            new_endp = new_endp->next; //update new_endp
        }
        else
        {
            prev = curr;
            curr = curr->next;
        }
        cnt++;
    }
}

void push(struct node** head_ref, int new_data)
{    
    struct node* new_node =
        (struct node*) malloc(sizeof(struct node));    
    new_node->data  = new_data;   
    new_node->next = (*head_ref);   
    (*head_ref)    = new_node;
}


void printList(struct node *node)
{
    while (node!=NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}

int main()
{    
    struct node* head = NULL;

    push(&head, 1);
    push(&head, 2);
    push(&head, 3);
    push(&head, 4);
    push(&head, 5);
    push(&head, 6);

    printf("\n Original Linked list ");
    printList(head);

    segregateEvenOdd(&head);

    printf("\n Modified Linked list ");
    printList(head);

    return 0;
}
Posted in Uncategorized | Tagged , | Leave a comment

Java Servlet

Posted on March 15, 2015 by neer1304

Servlet is used for development of dynamic web application in Java. Servlet is also used to describe components which are developed using servlet API. As a component Servlet is a class that is instantiated and managed by the Web Server for generating dynamic HTML.

Before Servlet dynamic Web Application used to be build using CGI.

CGI is a protocol that defines the mode of communication between a Web Server and a CGI scrip. A CGI script is a program written in C/C++/Perl that uses CGI to communicate with Web Server.

CGI based Web Application had following 2 problems –

1) CGI scripts were platform dependent.

2) Execution of CGI script was process based i.e. for each request a new process was initialized by the Web Server.

Process based execution creates lot of overhead and limits the scalability of the application.

Servlet as technology solved both these problems by providing a thread based of request processing.

javax.servlet and its sub-packages contains interfaces and helper classes which facilitates development of Servlet.

At the core of Servlet API we have –

javax.servlet.Servlet – is an interface of Servlet API that defines the life cycle method of a Servlet. Implementation of this interface need to be provided by each Servlet.

Life Cycle Method of each Servlet –

1) init() – This method is invoked only once after a Servlet object is created. It is used by the Web Server to provide the reference of an object of type javax.Servlet.ServletConfig to the Servlet.

It can be used by the application developer to perform initialization.

public void init(Servletconfig config);

ServletConfig is an interface of Servlet API implementation of which is provided by Web Server vendors.

2) service() – This method is invoked by the server each time a request for the servlet is received. It is used by application developers to process request.

public void service(ServletRequest request, ServletResponse response) throws ServletException, IOException. In this method Web Server provides the reference of objects of type ServletRequest and ServletResponse.

These are interfaces of Servlet API implementation of these are provided by Web Server vendor.

3) destroy() – is invoked only once just before a servlet is unloaded by the server. It can be used by the application developer to perform clean up operation.

public void destroy()

Servlet interface provides 2 non life cycle methods –

1) getServletConfig() – it is used by the application developer to obtain the reference of ServletConfig object.

public ServletConfig getServletConfig()

2) getServletInfo() – This method can be used by application developer to describe their Servlet.

public String getServletInfo();

App Developer    Client       WebServer   ServletConfig    ServletRequest    Servlet Response            Thread     Servlet

1.0 – Client sends initial request for a Servlet to WebServer

1.1 – Servlet object is created by the Web Server

1.2 – ServletConfig object is created by WebServer for Servlet.

1.3 – Reference of ServletConfig is passed in init() method.

1.4 – ServletRequest object is created by WebServer and populated with request data.

1.5 – ServletResponse object is created by WebServer.

1.6 – Request processing thread is started by WebServer.

1.7 – service() method is invoked by thread.

2.0 – Subsequent request for the Servlet is send from client

2.1 – same as 1.4

2.2 – same as 1.5

2.3 – same as 1.6

2.4 – service method is invoked by thread

3.0 – undeploy application

3.1 – destroy() method is invoked by WebServer

In order to define a Servlet implementation of Servlet interface need to be provided. It can be done in 2 ways directly or indirectly

Servlet  <—– YourServlet(Direct Implementation)

public class YourServlet implements Servlet

{

  definition of all the methods of Servlet interface need to be provided.

}

Servlet API provides an abstract class named GenericServlet which implements Servlet interface and can be used as a base class for a Servlet.

Servlet <—- GenericServlet  <—— YourServlet

public class YourServlet extends GenericServlet

{

    define service() method

}

Implementation of Servlet interface in GenericServlet is protocol neutral. In a web application Http protocol is used for communication between web server and clients. Http protocol supports multiple types of requests such as – Get, Post, Put, put, head, delete, trace, option, connect.

javax.servlet.http.HttpServlet class extends GenericServlet and defines methods which are used to handle http requests. Most commonly used among these methods are doGet() and doPost() which are used to process Http Get and Post request respectively.

public void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException

public void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException

HttpServletRequest extends ServletRequest

HttpServletResponse extends ServletResponse

Servlet <— GenericServlet <—- HttpServlet <—– YourServlet (Http specific methods)

public class YourServlet extends HttpServlet

{

    override doGet/doPost methods

}

//implementation of HttpServlet

public class HttpServlet extends GenericServlet

{

    public void service(ServletRequest request, ServletResponse response) throws ServletException,  
    IOException

    {
        HttpServletRequest req = (HttpServletRequest)request;

        HttpServletResponse res = (HttpServletResponse)response;

        service(req,res);
    }

    protected void service(HttpServletRequest request, HttpServletResponse response) throws ServletException,        
    IOException

    {
        type of request is checked and doGet(), doPost() method are invoked.
    }

    public void doGet()

    {

        // blank implementation

    }

    public void doPost()

    {

        // blank implementation

    }
}

Client   WebServer      Servlet     GenericServlet      HttpServlet       YourServlet

1.0 –  Client send a get request for a servlet to WebServer

1.1 – Servlet object is created by WebServer

1.2 – init() method is invoked by WebServer

1.3 – init() of GenericServlet is executed

1.4 – service(request, response) of Servlet is invoked by WebServer

1.5 – Servlet calls service(ServletRequest, ServletResponse) method of HttpServlet class is executed.

1.6 – In HttpServlet Class from public service() protected service() method is invoked.

1.7 – service(HttpServletRequest, HttpServletResponse) of HttpServlet is executed.

1.8 – Type of request is checked and doGet() of YourServlet is invoked

helloServlet

import javax.servlet.*;

import javax.servlet.http.*;

import java.io.*;

public class FirstServlet extends HttpServlet

{

    public void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, 
    IOException

    {

        String name = request.getParameter("txtName");

        response.getContetType("text/html");

        PrintWriter out = response.getWriter();

        out.println("Welcome,"+name);

        out.close();

    }

}

In order to compile servlets implementation classes of Servlet API must be available in classpath. These classes are not provided as core Java library rather these are provided by web server or application server vendors.

Different vendors provide these classes through different jar files for ex –

1) Tomcat –  servlet.api.jar

2) Weblogic server – weblogic.jar

3) GlassFish App Server – j2ee.jar

Each web application is self describing i.e. it contains information of all its components in xml format through an XML file named web.xml

It contains following elements :-

<web-app> – root element of web.xml file

<servlet> is the sub element web-app that is used to describe the servlet. It contains following sub-element –

a) <servlet-name> – unique identifier for servlet

b) <servlet-class>  – fully qualified name for the servlet class

<servlet-mapping> is a sub element of <web-app> that is used to map incoming request to a servlet. It contains following sub-element –

a) <servlet-name> – Unique identifier

b) <url-pattern> – URL used by client to invoke servlet

web.xml for HelloServlet

<web-app>

<servlet>

<servlet-name> s1 </servlet-name>

<servlet-class> First Servlet </servlet-class>

</servlet>

<servlet-mapping>

<servlet-name> s1 </servlet-name>

<url-pattern> helloServlet  </url-pattern>

</servlet-mapping>

...

</web-app>

1.0 – Request for HelloServlet is received

1.1 – Using the URL servlet mapping element of web.xml is identified

1.2 – From the <servlet-mapping> element <servlet name> is picked which is used to identify <servlet> element. From the servlet element name of servlet class is identified.

Passing Initialization Parameters to Servlets –

Initialization parameters represents data that is provided by the application developer to the servlets of an application through web.xml

Initialization parameters is of 2 types –

1) Application scope init parameters

2) Servlet specific init parameters

1) Application scope initialization parameters are defined by application developer using <context-param> sub element of <web-app> in web.xml file.

<web-app>

<context-param>

<param-name> Name </param-name>

<param-value> Value </param-value>

</context-param>

.....

</web-app>

Application scope initialization parameters are made available to all the servlets of an application by the application server.

An object of type javax.servlet.ServletContext is used by the application server to provide application scope initialization parameters to servlets.

For each application WebServer creates an object of type ServletContext at the time of deployment. This object serves following 3 purposes –

1) It is used by application developer to share data between servlets i.e. servlets can save data in the form of attributes in this object.

2) Application scope initialization parameters are provided to servlets using this object.

3) This object acts as interface between web server and application

2) Servlet specific initialization parameters are defined using <init-param> sub element of servlet in web.xml file

<web-app>

<servlet>

<servlet-name> ..  </servlet-name>

<servlet-class> ..  </servlet-class>

<init-param>

<param-name> ParameterName </param-name>

<param-value> value  </param-value>

</init-param>

...

</servlet>

...

</web-app>

For each servlet web server creates an object of type ServletConfig. This object serves following purpose –

1) It is used by the web server to provide the reference of ServletContext to the servlet.

2) It is used by the web server to provide servlet specific initialization parameters to the servlet.

App Developer   WebServer    ServletContext    ServletConfig     Servlet

1.0 – Web application is deployed by App Developer

1.1 – ServletContext object is created for application by WebServer

1.2 – Application scope initialization parameters are read from web.xml and are saved in ServletContext object by WebServer.

2.0 – Initial request for a servlet is received

2.1 – Servlet object is created by WebServer

2.2 – ServletConfig object is created by WebServer

2.3 – Reference of ServletContext object is saved in ServletConfig object by WebServer

2.4 – Servlet specific initialization parameters are read from web.xml and are saved in ServletConfig object by WebServer.

2.5 – Reference of ServletConfig object is provided to Servlet in init() method by WebServer.

Ex for LoginServlet

ServletConfig config = getServletConfig();

servletContext ctx = config.getServletContext();

Class.forName(ctx.getInitParameter("driverClass"));

Connection con  = DriverManager.getConnection(ctx.getInitParameter("url"),ctx.getInitParamter("user"),ctx.getInitParameter("password"));

Advantage of this code is that we don’t have to hard code the values in our java class.

State Management

Http is a protocol that is used to send request and receive response from web servers i.e. a stateless protocol i.e for each request a new http connection is created between the client and web server. This connection is closed as soon as response is received by the client.

The major drawback of the stateless protocol is that server fails to recognize series of logically related request coming from a client.

The problem of State Management deals with the maintenance of state between requests so that server can identify relation between these requests.

Following 4 methods are used for this purpose –

1) Cookies                  2) Hidden Form Field

3) URL Rewriting        4) HttpSession Object

1) Cookie
It represents textual information in the form of key value pair that is sent by server as part of response to the client machines. This information is sent by the browser to server with subsequent requests.

javax.servlet.http.Cookie class represents cookies in a web application.

addCookie() method of httpServletResponse interface is used to send a cookie as part of response.

Ex –

Cookie ck = new Cookie("user",name);

ck.setMaxAge(50000);

response.add(ck);

getCookie() method of httpServletRequest interface is used to obtain the reference of cookies received as part of request.

Ex –

Cookie ck[] = request.getCookies();

name = ck[0].getValue();

2) Hidden Form Field

In this method information to be persisted between one request to another is contained in invisible text fields which are added to the response page.

Whenever a new request is submitted from this page value of invisible text fields is sent as request parameters.

out.println("<br> <input type=hidden name=txtHidden value=\" "+name +"\">");

To get this parameter

String name = request.getParameter("txtHidden");

3) URL Rewriting

In this approach information to be persisted between one request to another is appended dynamically to the URL of the page on which information is required i.e. whenever a new request is submitted using the URL information is made available on the server as Request Parameters.

Ex –

out.println("<br> <a href = \"sorryServlet?userName="+name+"\"> Take a tour </a>");

4) HttpSession

In all three methods information to be persisted between requests is sent to the client machine in one form or another i.e. a round trip of information is involved.

In the 4th method information to be persisted between request is stored on the server in an object of type HttpSession.

HttpSession session = request.getSession();

session.setAttribute("name",name);

At time of retrieving

HttpSession session = request.getSession();

String name = (String)session.getAttribute("name");

Filter

It is an optional component of a web application that intercept request and may apply pre and post processing. It sits between WebServer and Servlet.

Following interface facilitate development of filters –

1) Filter

2) FilterChain

3) FilterConfig

1) Filter interface provides lifecycle method of filter. It contains following methods –

a) init() – is invoked only once just after a filter object is created. It is used by the Web Server to provide the reference of FilterConfig object to the filter.

public void init(FilterConfig config)

b) doFilter() – is invoked each time a request for the resource on which filter is applied is received.

public void doFilter(ServletRequest req, ServletResponse resp, FilterChain chain) throws ServletException, IOException

c) destroy() – is invoked only once just before a filter is unloaded.

2) FilterConfig – for each filter Web Server creates an object of type FilterConfig. This object serves 2 purpose –

a) It is used by the Web Server to provide the reference of ServletContext to the filter.

b) It is used by the Web Server to provide initialization parameters to the filter.

3) FilterChain – For each chain of resources WebServer creates an object of type FilterChain. This object provides the abstraction of forwarding request to the next resource in the chain. It contains 1 method –

public void doFilter(ServletRequest req, ServletResponse res) throws ServletException, IOException

This method is used by filter to invoke the next resources in the chain.

In order to create a filter implementation of Filter interface is need to be provided.

Following elements are to be added to web.xml to apply a filter on a resource.

<web-app>

<filter>

<filter-name> Unique Identifier  </filter-name>

<filter-class> Fully Qualified Class Name </filter-class>

<init-param>

<param-name> Name of paramter </param-name>

<param-value> Value of parameter </param-value>

</init-param>

---

</filter>

<filter-mapping>

<filter-name> Unique Identifier  </filter-name>

<servlet-name> Name of target servlet </servlet-name>

<url-pattern> url of target resource </url-pattern>

</filter-mapping>

---

</web-app>

public class MyFilter implements Filter

{

    FilterConfig config;

    public void init(FilterConfig c)

    {

        config = c;

    }

    public void destroy()

    { }

    public void doFilter(ServletRequest req, ServletResponse res, FilterChain chain)

    {
        System.out.println("Filter is invoked");

        //pre-processing logic

        chain.doFilter(request,response);

        //post processing logic

        System.out.println("Filter exiting");
    }
}
Posted in Framework | Tagged | Leave a comment

Web Service

Posted on March 15, 2015 by neer1304

Web Service represents business logic that is exposed in a platform and technology independent manner. Usually B2B components are implemented as Web Services.

Client -> Web Portal(B2C Component) -> Payment Gateway(B2B component) -> Bank

Before the concept of web services emerged B2B components were developed using CORBA. CORBA based B2B components had following problems –

a) CORBA was proprieted technology and only two vendors were licensed to develop CORBA implementation.

b) Third party drivers were required for inter-operability.

Web Services solved the problem related with CORBA based implementation of B2B components with the help of following XML based technologies –

i) SOAP – Simple Object Access Protocol

ii) WSDL – Web Service Descriptor Language

iii) UDDI – Universal Discovery and Directory Interface

SOAP is an XML based protocol that is used to describe the information of a method call and method result in XML format. For each Web Service call a SOAP packet is created and is payloaded into HTTP, SMTP or FTP packets which are send over the network to the application server where SOAP packet is unloaded, parsed and Web service method described by the packet is invoked.

Using the same process result of the Web Service is sent to the client.

WSDL is an XML based description language that is used to describe Web Service in technology independent manner. For each WebService a WSDL document is created which contains following information of Web Service in XML format –

a) Name and functional domain of the Web Service.

b) Methods description.

c) URL of the Web Service.

d) Protocol supported by the Web Service.

UDDI is used to facilitate auto-detection and discovery of Web Service. A UDDI server is used to publish and search WSDL documents.

Enterprise App  Application Server   Web Service  Service Proxy UDDI Server SOAP Client

1.0 – Enterprise App is Deployed on App Server

1.1 – Web Service is instantiated by App Server

1.2 – Proxy of Service is created by App Server

1.3 – App Server publishes WSDL Document on UDDI server

2.0 – Client reaches UDDI server

2.1 – WSDL document is returned to the Client

2.2 – Client invokes method using Service Proxy

2.3 – For the method call a SOAP packet is created and payloaded into HTTP packet

2.4 – HTTP packets are transmitted over the network from client side Servie Proxy to server side Service Proxy

2.5 – SOAP packet is extracted from HTTP packet and parsed

2.6 – Web Service method is invoked by Server side Service Proxy

2.7 – Web Service provides result to Service Proxy

2.8 – SOAP packet is created for the result and is payloaded in HTTP packet.

Creating a Web Service using ANT –

1) Define a java class functionality of which is to be exposed as a Web Service.

2) Use servicegen and service ant tasks provided by Weblogic server for packaging the java class as an enterprise module containing Web Service.

In order to use servicegen and service ant tasks following jar files must be available in the class path – webservices.jar and webserviceclient.jar.

Steps to define a Client for a Web Service

1) Obtain jar file containing client proxies and WSDL documents. This jar file is provided by the application server.

2) Use the code suggested by the application server for invoking the Web Service.

package mypack;

public class AdderSubtractor

{

    public int add(int x, int y)

    {

        return (x+y);

    }

    public int subtract(int x, int y)

    {

        return (x-y);

    }

}

build.xml

<project name="buildWebservice" default = "ear" basedir =".">

<target name = "compile">

<javac srcdir="." destdir = "." />

</target>

<target name = "ear" depends = "compile">

<servicegen destEar = "as.ear" contextURI = "adderSubtractor">

<service javaClassComponents = "mypack.AdderSubtractor" targetNamespace = "http://localhost:7001" serviceName = "AdderSubtractor" serviceURI = "/addSub" generateTypes = "True" expandMethods = "True">

<client packageName = "clientPack"/>

</service>

</servicegen>

</target>

</project>

import ClientPack.*;

import java.io.*;

class ServiceClient

{

    public static void main(String args[])

    {

        try

        {

            String wsdlUrl = "http://localhost:7001/adderSubtractor/addSub?WSDL";

            AdderSubtractor service = new AdderSubtractorImpl(wsdlUrl);

            AdderSubtractorPort port = service.getAdderSubtractorPort();

            BufferedReader b = new BufferedReader(new InputStreamReader(System.in));

            System.out.println("Enter first number");

            int x = Integer.parseInt(b.readLine());

            System.out.println("Enter second number");

            int y = Integer.parseInt(b.readLine());

            int s = port.add(x,y);

            int d = port.subtract(x,y);

            System.out.println("Sum is: "+s);

            System.out.println("Difference is: "+d);

        }catch(Exception e) {System.out.println(e); }
    }
}
Posted in Web Service | Tagged | Leave a comment

EJB 3.0

Posted on March 1, 2015 by neer1304

SyntaxHighlighter.all();

EJB(Enterprise Java Bean) 3.0 is framework for developing distributed application. The distributed application has following 2 types of functionality –

1) Application logic or data is to be made distributed.

2) Infrastructure services which expose business logic and application data as distributed component.

The main theme of EJB is to let the application developers focus on business logic and application data without bothering about how it shall be made distributed.

This framework consist of following 2 things –

1) An API which is used by the application developers to define application logic and data.

2) A run time environment called EJB container which provides infrastructure, services and exposes business logic and data as distributed component.

EJB can be of following 3 types –

1) Session bean

2) Message Driven Bean

3) Entity Bean

1) Session bean represents application logic of an application that is to be made distributed.

Session beans are of 2 types –

a) Stateless    b) Statefull

In a stateless session bean intermediate state between method invocation is not maintained.

In case of statefull session bean intermediate state between method invocation is maintained.

2) Message Driven Bean – represents business logic of an application.

Difference b/w Session bean and Message Driven Bean

1) Session beans are synchronous whereas message driven beans are asynchronous.

2) Session beans are based on RMI whereas message driven beans are based on Java Messaging Service(JMS);

3) Entity beans represents application data as distributed component.

In EJB 3 a new API called JPA(Java Persistence API) is introduced to manage persistent of entities.

Difference between Java Bean and EJB

1) Java bean are general purpose or application specific reusable components developed in Java whereas EJB are distributed component developed in Java.

2) EJB requires a specific run-time environment called EJB container for their execution whereas Java beans don’t require any such environment.

Implementation of Session Bean

A session bean consist of a remote or local interface and a bean class.

Remote or local interface contains method which can be invoked on a session bean by remote and local clients respectively.

Client is local if it is running in the same run time environment and it is remote if it is running in different run time environment.

In remote interface stub and skeleton are made like RMI whereas in local interface actual reference of object is passed.

Local and Remote annotation are used to define remote and local interfaces of a session bean.

@Remote

public interface Adder

{

    public int add(int x, int y)

}

Class for a stateless session bean is POJO class which implement remote and local interfaces defined for the bean and is annotated by stateless annotation.

@Stateless

public class AdderBean implements Adder

{
    public int add(int x, int y)

    {

        return x+y;
    }
}

EJB container stub in directory server we give its name.

package mypack;

import javax.ejb.Remote.*;

import javax.ejb.Stateless;

@Stateless (mappedName = "adder")

public class AdderBean implements Adder

{
    public int add(int x, int y)

    {
        System.out.println("add method invoked");

        return (x+y);
    }
}

Steps to define a client for a session bean

a) Bean stub is looked up in the directory server.

b) Remote methods are invoked on the bean stub.

Directory Server

It is a utility software that is used to access resources in a location and implementation transparent manner.

Different vendors provide different implementation of directory servers. Each directory server provide an application interface which is used by the applications to register and lookup resources.

javax.naming.Context interface is provided to register and look-up resources in directory servers. It provides following 2 methods –

a) bind() – used to register a resource

public void bind(String name, Object resource)

b) lookup – is used to lookup a resource

public Object lookup(String name) throws NamingException

InitialContext is an utility implementation of Context interface that hides vendor specific details from application developer.

Implementation for Statefull Bean

@Remote

public interface Account

{

    public void deposit(int amt);

    public boolean withdraw(int amt);

    public int getBalance();

}

@Stateful(mappedName = "myAccount")

public class AccountBean implements Account

{

    private int amount;

    public void deposit(int amt)

    {

        amount += amt;

    }

    public int getBalance()

    {

        return amount;

    }

    public boolean withdraw(int amt)

    {

        if(amt<amount)

        {

            amount -= amt;

            return true;

        }

        else

            return false;

    }

}

Account.jsp

<%@ page import="javax.naming.*,mypack.*" %>

<%
InitialContext ctx=new InitialContext();
Account stub=(Account)ctx.lookup(
"myAccount");
session.setAttribute("stub",stub);
int a=Integer.parseInt(request.getParameter(
"amount"));
stub.deposit(a);
%>
<b> Account is successfully opened. </b><br>
<jsp:include page="options.html" />

options.html

<b> Select Operations to perform </b>
<form action="operations.jsp">
Amount <input type="text" name="amount"> <br>
<input type="radio" name="opr"
value="deposit">Deposit <br>
<input type="radio" name="opr"
value="withdraw">Withdraw <br>
<input type="radio" name="opr"
value="balance">Check Balance <br>
<input type="submit" value="submit">
</form>

operations.jsp

<%@ page import="mypack.*" %>
<b>
<%
Account stub=(Account)session.getAttribute(
"stub");
String opr=request.getParameter("opr");
if (opr.equals("balance"))
{
int b=stub.getBalance();
out.println("Your current Balance is: "+b);
}
else
{
int a=Integer.parseInt(request.getParameter(
"amount"));
if (opr.equals("deposit"))
{
stub.deposit(a);
out.println("Successfully Deposited.");
}
else if(stub.withdraw(a))
out.println("Successfully Withdrawn.");
else
out.println("Insufficient Balance.");
}
%>
</b><br>
<jsp:include page="options.html" />

Java Messaging Service (JMS)

JMS is a messaging service that facilitate reliable message passing between disconnected clients. This service consists of a messaging server which is responsible for receiving and forwarding messages and an API which is used by application developers to define messaging clients.

In JMS application following 2 models are followed  to send and receive message

1) Peer to Peer/ Point to Point Model

2) Publisher/Subscriber Model

Point to point model is used when all the messages that are received on a messaging destination on a messaging server are to be delivered to a single client i.e. in this model destination and receiver has one to one correspondance.

A destination represents a thread on a messaging server that manages messages for a client or messages of a specific type. A messaging destination can be either queue or topic.

In peer to peer model queue is used and in publisher/subscriber model topic is used.

In publisher-subscriber model all the messages which are received on a topic are delivered to all the clients which are subscribed to the topic. This model is used when same message is to be send to multiple parties.

javax.jms package contains classes and interfaces of JMS API.

Point to Point

a) QueueConnectionFactory

b) QueueConnection

c) QueueSession

d) QueueSender

e) QueueReceiver

Publisher/Subscriber

a) TopicConnectionFactory

b) TopicConnection

c) TopicSession

d) TopicPublisher

e) TopicSubscriber

Common to both

a) Session

b) Message

c) MessageListener

d) TextMessage

e) MapMessage

f) ObjectMessage

Posted in Framework, Java | Tagged | Leave a comment

Java Struts2

Posted on March 1, 2015 by neer1304

SyntaxHighlighter.all();

Struts 2 is a framework  for developing web application in Java. This framework provides MVC implementation for developing web application and has following characteristics –

1) It is non-intusive framework (no change in Java classes).

2) It favors conventions over configuration.

3) It supports annotations for configurations (in addition to XML based configuration).

4) It supports dependency injection and aspect oriented programming.

5) It introduces concept of Value Stack and OGNL.

Model View Controller

It is a design pattern that is based on the concepts of division of labour and loose coupling. This design pattern can be used to develop application functionality whic can be divided into following 3 loosely connected components –

i) Model

ii) View (Presentation)

iii) Controller (Workflow)

Model represent state of an application. State of an application are controlled by data and processing logic.

View represents presentation logic i.e the way data is to presented to the end user. Same type of data can be presented to different type of users in different ways.

Controller is responsible for controlling the workflow of data and processing in an application.

MVC Implementation of Struts

Action 

In Struts application actions represent model components. An action is a POJO class which contains data members to store request data and contains method which encapsulate request processing logic.

Before Struts 2 model components used to represent data. In Struts 2 implementation actions are model component.

Results

Results are framework components which are responsible for generating views. Result is generic interface provided by the framework that can be implemented in different ways to support different presentation  technology such as JSP, Velocity templates, JSF, Tiles, AJAX etc.

Various implementation of Result are provided by the framework to support frequently used presentation technology.

Filter Dispatcher

It is a filter provided by the framework that act as a controller. It provides a single entry point into the application i.e all the requests submitted to a Struts application are intercepted by this filter.

Apart from providing single entry point this component is responsible for controlling the work flow of processing the request.

Value Stack 

To facilitate sharing of request data among different components involved in request processing concepts of Value Stack and OGNL are proposed by the framework.

Value Stack is a container object that is created by the Controller per request. This object holds all the data required in request processing. This object has following characteristics –

1) It exposes the properties of each objects added to it as the properties of its own.

2) It supports indexes to uniquely identify same properties of different objects.

To facilitate setting of properties in the value stack and to fetch value of properties from the value stack in a non-programmatic manner an expression language called OGNL(Object Graph Navigation Language) is provided by the framework.

This expression language is used to form expressions to identify properties in value stack. These expressions are provided to the custom tags of Struts Tag library for changing the value of properties or for fetching the values of properties.

Client   FilterDispatcher(Controller)  Action     Result      Config Info      JSP

1.0 – Request is submitted by client to Controller

1.1 – Controller identifies Action, Result and JSP from Configuration Information

1.2 – Controller creates Action

1.3 – ValueStack is created by Controller and reference of Action is passed

1.4  – Controller sets Action properties from request data

1.5 – Controller ask Action to process request

1.6 – Action processes the request and returns a String to Controller

1.7 – Contoller invokes Result and URL of JSP mapped to the returned String is provided.

1.8 – JSP is invoked by Result.

1.9 – JSP fetches Action data from ValueStack using OGNL expressions and custom tags

2.0 – View is generated for end user.

Interceptors

Struts 2 framework provides the concept of Interceptors for implementing additional and optional services in a request processing.

An Interceptor is a proxy object that is associated to an Action. Each Interceptor provides its services to the Action and gets two chances of applying its services. One before the Action is invoked and another one after the Result is rendered.

An application developer may associate multiple interceptors to an action using configuration information.

Workflow of an application is dynamic in nature i,e, it changes with time. If workflow is controlled by the application then maintenance problem are created because each time work flow is changed application is needed to be modified.

Struts 2 provides facility of controlling the framework in declarative manner with help of configuration information.

Steps to create a Struts 2 application in Eclipse-

1) Create a web project

2) Add Struts 2 jar files to the project.

3) Add following filter entry to the web.xml to enable Struts 2 controller.

<filter>

<filter-name> f1 </filter-name>

<filter-class> org.apache.struts2.dispatcher.FilterDispatcher </filter-class>

</filter>

<filter-mapping>

<filter-name> f1 </filter-name>

<url-pattern> /* </url-pattern>

</filter-mapping>

4) Define an action class to process request.

Action class is implemented as Java bean which contains data members their getter and setter methods and their request processing methods which is conventially named execute().

This method does not receive any parameters and returns a String.

src->new->package->mypack

new->class-> LoginAction

source -> generate getter and setter

package mypack;

public class LoginAction

{

    String name, password;

    public String execute()

    {

        if(name.startsWith("a") && password.startsWith("b"))

            return "SUCCESS";

        else

            return "FAILURE";

    }
//getter setter for name and password for getting value in jsp
}

4) Create jsp pages to receive request and to provide “Result” to the end user.

In the jsp pages custom tags of Struts Tag libraries are used to generate input form and to display result.

WebRoot -> index.jsp

<%@ taglib uri = "/struts-tags" prefix = "s" %>

<s:form action ="login">

<s:textfield name = "name" label = "Name"/>

<s:password name = "password" label = "Password" />

<s:submit value = "login"/>

</s:form>

new -> JSP -> welcome.jsp

<%@taglib uri = "/struts-tags" prefix = "s"%>

<b> Welcome, <s:property value = "name" /> </b>

new -> JSP -> relogin.jsp

<b> Invalid name or password <b>

<jsp:include page = "index.jsp"/>

5) Create a xml file named struts.xml under classes folder of Web-INF

6) Add the DTD to the struts.xml file

DTD of struts.xml file is provided with Struts2.core jar file. Add the configuration to the struts.xml file using struts package and action element.

<Struts> is the root element of the configuration file. <package> is a sub-element of Struts. A package represents configuration of a module i.e we can divide our application into different modules from configuration management point of view.

Concept of package in configuration facilitate inheritance of configuration information of one module into another.

A package named struts-default is defined by the framework. This package contains configuration of all the pre-defined results, interceptors and interceptors stack. Configuration of this package is usually inherited by all user defined packages.

<struts>

<package name = "demo" extends = "struts-default">

<action name = "login" class = "mypack.LoginAction">

<result name = "success"> /welcome.jsp </result>

<result name = "failure"> /relogin.jsp </result>

</action>

</package>

</struts>

ActionContext

ActionContext is a framework provided class which is instantiated per request.

ActionContext object is used by the framework to keep all the request data together.

This object holds parmas, request, session, application, attr and Value Stack.

ActionInvocation

ActionInvocation is a helper component of the controller which controls processing of a request. Per request an ActionInvocation object is created by the framework. This object is provided references of Action, ActionContext, Interceptor Stack and Result.

This object exposes a method named invoke() which is used by the controller and other framework components to request initiation and proceedings of the request processing.

Posted in Framework, Java | Tagged | Leave a comment

Java Collection Framework

Posted on March 1, 2015 by neer1304

A framework is a collection of classes and interfaces that facilitate development of specific kind of applications by providing an architectural model and reusable components.

Collection framework provides a unified model to work with different types of data structures such as arrays, linked list, BST, Hash Table etc.

At the core of Collection framework is an interface named java.util.Collection. This interface describes the common behaviour of all collections.

Methods of Collection interface –

a) add()             d) removeAll()     g) containsAll()

b) addAll()         e) retainAll()        h) size()

c) remove()       f) contains()         i) clear()

Iterator:- is an interface of Collection framework implementation of which are provided by all Collections. It is used for traversing the elements of Collection in implementation independent fashion.

Methods of iterator interface –

a) hasNext() – returns true if there is an element to be traversed.

b) next() – used to obtain next element from collection.

c) remove() – used to remove last traversed element from the collection.

List 

List represents indexed collection. Some commonly used methods are –

a) add()              d) indexOf()

b) addAll()          e) lastIndexOf()

c) get()               f) listIterator()

ListIterator facilitate traversing element of list in both directions. ListIterator extends iterator and adds following methods –

a) hasPrevious() – returns true if there is an element behind current index.

public boolean hasPrevious();

b) previous() – public Object previous()

c) add() – used to insert an element at the current index in a list.

public void add(Object element)

ArrayList

ArrayList provides implementation of List interface through Abstract List class. An object of array list represents a dynamic array.

Set

Non-indexed collection of unique element. Functionality of set represented by Set Interface which extends Collection interface but doesn’t define any additional method. It simply specifies that implementation of add method must be provided in such a manner that duplicate elements are not added.

HashSet and TreeSet classes provides implementation of Set interface through Abstract Set class.

Difference between HashSet and TreeSet is in their internal data structure. HashSet uses hash table for storing elements and TreeSet uses BST.

Map

It is a collection in which values are stored by associating them with keys which are used to retrieve values.

Functionality of Map is described by Map Interface which contains following methods –

1) put() – is used to store a key value pair in the map.

public boolean put(Object key, Object value)

2) get() – is used to obtain a value from a map.

public Object get(Object key)

3) remove() – is used to remove key-value pair from the map.

public boolean remove(Object key)

4) containsKey() – is used to search a key in the map

public boolean containsKey(Object key)

5) contains() – is used to search a value in the map

public boolean contains(Object value)

6) size() – used to find out number of elements in map.

public int size()

7) keySet() – returns a set for traversing the keys of a map.

public Set keySet();

8) entrySet() – returns a set for all the key value pairs of the Map.

public Set EntrySet();

The set that is returned by the entrySet() method contains objects of type Map.Entry. Entry is a nested interface of Map. All implementation of Map provides implementation of this interface as well.

This interface provides 2 methods –

a) getKey() – public Object getKey()

b) getValue() – public Object getValue()

HashMap and TreeMap classes provides implementation of Map interface through Map interface class.

class MapDemo

{

    public static void main(String[] args)

    {

        HashMap map = new HashMap();

        map.put("A",1);

        map.put("B",2);

        map.put("C",3);

        map.put("D",4);

        map.put("E",5);

        System.out.println("There are" + map.size() + "elements in map");

        System.out.println("Contents of map are");

        Set s = map.entrySet();

        Iterator itr = s.iterator();

        while(itr.hasNext())

        {
            Map.Entry m = (Map.Entry)itr.next();

            System.out.println(m.getKey() + "\t" + m.getValue());
        }
    }
}

Searching and Removing User Defined objects in Collection

Whenever an element is searched in a list using contains() method an exhaustive search is performed using equals() method i.e success or failure of a search operation entirely depends on the implementation of equals method.

Default implementation of equals() method on Object class compares the value of references not the contents of Object. Any two objects in Java cannot have same reference so equals() method returns false.

In case of String, String class have override the equals() method to match the contents.

In order to successfully search object of a class in a list equals() method must be overridden in the class to facilitate content wise comparison of objects.

public boolean equals(Object o)

{
    Emp e = (Emp)o;

    return this.name.equals(e.name) && this.job.equals(e.job) && this.salary==e.salary;   
}

HashSet

HashTable is implemented as an array of fixed size list which are called buckets.

In order to store an element in hashtable hashing function is used which returns index of a bucket in which element is stored. A simple hashing function can be of the following form –

h(e) = e%n

where e is the element to be stored and n is the number of buckets.

Most of the hashing functions are numeric which implies that only numeric elements can be added to a hash table. But we have to store objects. Every object can be represented as String(toString()) and a number(hashCode()).

In order to store object in hashing based collection objects must be represented by numbers. To facilitate numeric representation of object hashCode() method is provided in object class.

In a hashing based collection when a element is searched using contains() method following steps are performed –

a) HashCode of object is obtained.

b) On the hashCode of object hashing function is applied.

c) Object to be searched is compared with the elements of identified bucket using equals() method i.e. in a hashing based collection a selective search is performed.

Success or failure of a search operation depends on 2 factors –

a) Implementation of hashCode() method which is used to identify the bucket.

b) Implementation of equals() method which is used to compare element to be searched with the elements of the identified bucket.

public int hashCode()

{
    return name.hashCode() + job.hashCode() + salary;
}

If hashCode is same then they will be added in same bucket if contents are different then equals method will catch it.

TreeSet

It is BST based collection.

In order to add objects of a class in a tree based collection class must contain sorting logic.

Sorting logic can be added to a class in following 2 ways –

a) java.lang.Comparable interface

b) java.util.Comparator interface

a) Comparable interface is used to make a class comparable i.e if a class is comparable order of two objects of a class is obtained.

This interface provides a single method compareTo().

public int compareTo(Object o);

public int compareTo(Object o)

{
    Emp e = (Emp)o;

    return this.name.compareTo(e.name); // sort on name basis

    //sort on salary basis

    return this.salary-e.salary
}

Using the comparable interface single sorting order can be defined for the objects of a class.

b) Comparator interface is used to define multiple sorting orders for the objects of a class. It contains 2 methods –

public int compare(Object o, Object p)

public boolean equals(Object o)

Multiple sorting order can defined using Comparator because Comparator interface is implemented in a separate class i.e. for defining multiple sorting orders for the objects of a class multiple implementation of comparator interface can be provided.

Note – Comparable is implicitly used by Tree based collection whereas comparator need to be explicitly specified. If Comparator is given then sorting is based on that if not then compiler will check for comparable.

Ex – TreeSet ts1  = new TreeSet(new JobComparator());

class JobComparator implements Comparator
{
    public int compare(Object o, Object p)
    {

        Emp e = (Emp)o;

        Emp f = (Emp)p;

        return e.job.compareTo(f.job);
    }
}

class SalaryComparator implements Comparator

{

    public int compare(Object o, Object p)

    {

        Emp e = (Emp)o;

        Emp f = (Emp)p;

        return e.salary-f.salary;

    }

}

Complexities –

1) ArrayList – O(n)

2) HashSet, HashMap – O(1) atmost k where k is the size of buckets.

3) TreeSet, TreeMap – O(lgn) equals to height of BST.

Load Factor

It is a constant whose value is between 0 to 1. Value of load factor determines when the size of buckets is to be modified. In a hash table performance of insertion/search operation and space utilization are two inversely proportional objectives i.e if space utilization is maximized performance is decreased because optimization of space utilization results in hash collision which degrades performance. Optimization of performance results in under utilization of space.

By default value of load factor is 0.75 which represents that size of buckets is increased when 75% buckets are filled.

Vector

It is a legacy collection that represents dynamic array. After the introduction of collection framework vector is modified to make it compatible to the collection framework.

Difference between Vector and  ArrayList

1) Major difference between vector and array list is of thread safety. Vector is thread safe whereas ArrayList is not. Thread safety degrades performance.

2) Vector contains methods of collection and list interface as well as its own legacy methods.

3) Apart from iterator a vector provides enumeration for traversing its elements.

Enumeration is a legacy interface that provides methods which are used for traversing the elements of legacy collection. It provides following methods –

a) hasMoreElements() – returns true if there is an element to be traversed

public boolean hasMoreElements()

b) nextElement() – returns the reference of next element.

public Object nextElement();

ensureCapacity() – used to increase the capacity of Vector.

public void ensureCapacity(int requiredCapacity);

Major difference between enumerator and iterator is in their implementation. An iterator is designed to fail fast i.e an iterator fails as soon as the modification to the underlying collection is detected by throwing ConcurrentModification Exception.

The reason behind such a implementation is that iterator is mostly used for traversing the contents of non-thread safe collection in which consistency of modification operation is not guaranteed.

Enumeration is designed synchronized. Enumeration is used only with thread safe collection. In thread safe collection there is guarantee of consistency of data in case of concurrent modification hence enumeration never fails.

Posted in Framework, Java | Tagged | Leave a comment

Java Threads

Posted on March 1, 2015 by neer1304

SyntaxHighlighter.all();

Thread is a light weight process. An instance of java.lang.Thread is called thread in java. JVM calls main thread which calls main method.

When a thread is created corresponding stack area is created. Objects are made in heap area.

Different threads are executed in same memory address whereas different process utilize different memory allocation.

Advantages of multi-threaded application

a) Use less resources.

b) Inter-thread communication is easy.

Multithreading is used when we want to perform multiple task in a single application.

There are 2 ways to create Thread in Java

1) Implement Runnable Interface

2) Extend Thread Class

Method in Runnable Interface

public void run()

General steps to follow for creating a thread based app

1) Create the task.

2) Create the worker.

3) Assign the task to the worker.

4) Say start to the worker.

5) Worker will start performing the task.

6) When task will come to end the worker will die.

class Task implements Runnable

{

    public void run()

   {

       // define the task

   }

}

class User

{

    public static void main(String[] args)

    {

        Task t = new Task();

        Thread worker = new Thread();

        worker.start();
    }
}

Life Cycle of Thread

new Thread –> Ready to run –> Running –> Dead

Ready to run  –> Blocked State –> Ready to run (sleep(), join(), IO blocked state)

Priorities static variables in Thread class :-

MIN_PRIORITY

NORM_PRIORITY – default

MAX_PRIORITY

Priority is set always before start() method.

setPriority() – maximum number of CPU cycles to be given to the thread.

join() – method is used if parent or any peer thread has to wait for another thread.

Synchronization 

Synchronization  is used to achieve expected output in case when more than one thread are running in parallel. Multiple running threads can corrupt data of one another.

For ex –

class SyncTest implements Runnable

{
    public void run()

    {

        show();
    }

    synchronize void show()

    {

        for(int x=1;x<=5;x++)

        {

            System.out.println(Thread.currentThread().getName());

            System.out.println("["+"hi buddy");

            try

            {

                Thread.sleep();

            }
            catch(InterruptedException e) 
            { System.out.println(e);  }

            System.out.printn("]");
        }
    }    
}
public class SyncMethod

{

    public static void main(String[] args)

    {

        Runnable nr = new SyncTest();

        Thread one = new Thread(nr);

        Thread two = new Thread(nr);

        Thread three = new Thread(nr);

        one.setName("ABC");

        two.setName("XYZ");

        three.setName("PQR");

        one.start(); two.start(); three.start();
    }
}

If two methods are synchronized in the same class than only one thread can enter one synchronized method at a time. If one thread completes its work and releases the lock than only other thread can enter the method.

Static method get lock from class. If one get the lock other static methods will also be locked.

class Task

{

    synchronized static void method1() -> class lock is activated

    { //task t1}

    static void method2()

    { //task t2}

    // t3 will not be able to get the lock until class lock released by t1

    synchronized static void method3()

    {}

}

If we do not have source code of Task class we can use synchronized block to synchronize various methods.

Task tk = new Task();

synchronized(tk); // called when object is created

{

    tk.method1();

    tk.method2();

}

Actual meaning of Class lock

java.lang.Class object is created when class is loaded in JVM and that object represent our class.

Note

a) Class lock works on non-static method.

b) Lock our class can work on our block.

c) In synchronized block only calling is synchronized nor the method.

Threads are categorized into

1) User Thread

2) Daemon Thread

Daemon Threads are created to serve user threads if no user thread is there then daemon thread will finish.

Method used – setDaemon(bool);

For a thread we can set daemon before the thread is started. Garbage collector is an example of daemon thread.

The best approach for creating thread is  implementing Runnable interface because

a) We cannot extend more than one class.

b) Many methods will be inherited in our class which are not necessary.

Performing Inter-Thread Communication

Methods such as wait(), notify() and notifyAll() in Object class are used in inter thread communication.

Ex – Producer Consumer problem

class Inventory

{

    boolean flag = false;

    public synchronized void itemProduce(int i)

    {

        if(flag)

        {

            try

            {

                wait();

            }catch(Exception e) {}

        }

        System.out.println(i+"is going to produce..");

        try

        {

            Thread.sleep(1000);

        }catch(Exception e) {}

        System.out.println(i+"is produced..");

        flag = true;

        notify();
    }

    public synchronized void itemConsume(int i)

    {

        if(flag)

        {
            try 
            {
                wait();
            }
            catch(Exception e) {}
        }

        try
        {
            Thread.sleep(1000);
        } catch(Exception e) {}

        System.out.println(i+"item is consumed");

        flag = false;

        notify();
    }
}

class ProducerThread extends Thread
{
    Inventory br;

    ProducerThread(Inventory br)

    {
        this.br = br;
    }

    public void run()

    {
        for(int i=0;i<5;i++)

        {
            br.itemProduce(i);
        }
    }
}

class ConsumerThread extends Thread

{
    Inventory br;

    ConsumerThread(Inventory br)

    {
        this.br = br;
    }

    public void run()

    {
        for(int i=0;i<5;i++)

        {
            br.itemConsume(i);
        }
    }
}

class ProConProblem

{
    public static void main(String[] args)

    {
        System.out.println("Enter main");

        Inventory br = new Inventory();

        ProducerThread pt = new ProducerThread(br);

        ConsumerThread ct = new ConsumerThread(br);

        ct.start();

        pt.start();

        System.out.println("Exit main");
    }
}
Posted in Multi-Threading | Tagged , | Leave a comment