Wednesday, June 29, 2016

Reverse an array without affecting special characters in Java

Simple Solution:
1) Create a temporary character array say temp[].
2) Copy alphabetic characters from given array to temp[].
3) Reverse temp[] using standard string reversal algo.
4) Now traverse input string and temp in a single loop. Wherever there is alphabetic character is input string, replace it with current character of temp[].

Efficient Solution:
Time complexity of above solution is O(n), but it requires extra space and it does two traversals of input string.
We can reverse with one traversal and without extra space. Below is algorithm.

Solution 1:

public class ReverseArrayWithoutSpecial
{
   public static void main(String[] args)
   {
     System.out.println(reverseString("man ish#"));
   }
   public static String reverseString(String input)
   {
     char[] inputArr = input.toCharArray();
     char[] tempArr = new char[input.length()];
     int i=0;
     int j=0;
     for (char ch:inputArr)
     {
       if(Character.isAlphabetic(ch))
       {
         tempArr[i] = ch;
         i++;
       }
     }
     i--;
     while(j<i)
     {
       char temp = tempArr[i];
       tempArr[i]= tempArr[j];
       tempArr[j]=temp;
       j++;
       i--;
     }
     for(i=0,j=0;i<input.length();i++)
     {
       if(Character.isAlphabetic(inputArr[i]))
       {
         inputArr[i]= tempArr[j++];
       }
     }
     return new String(inputArr);
   }
 }

Result: hsi nam#


Solution 2:

public class ReverseArrayWithoutSpecial
{
   public static void main(String[] args)
   {
     System.out.println(reverseString("a,b$c"));
   }
   public static String reverseString(String input) {
    char[] inputArr = input.toCharArray();
    int l = 0;
    int r = inputArr.length - 1;
    while (l < r) {
      if (!Character.isAlphabetic(inputArr[l])) {
        l++;
      } else if (!Character.isAlphabetic(inputArr[r])) {
        r--;
      } else {
        char tempChar = inputArr[l];
        inputArr[l] = inputArr[r];
        inputArr[r] = tempChar;
        l++;
        r--;
      }
    }
    return new String(inputArr);
  }

 }

Result: c,b$a


Detect Cycle in a an Undirected Graph in Java

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.

Union: Join two subsets into a single subset.

Union-Find Algorithm can be used to check whether an undirected graph contains cycle or not. Note that we have discussed an algorithm to detect cycle. This is another method based on Union-Find. This method assumes that graph doesn’t contain any self-loops.

We can keeps track of the subsets in a 1D array, lets call it parent[].

Program Sample:

/**
 *
 */
/**
 * @author Abhinaw.Tripathi
 *
 */
public class Graph
{
int V;

int E;

Edge edge[];
class Edge
{
 int src,dest;
};

public Graph(int v,int e)
{
this.E=e;
this.V=v;
edge=new Edge[E];
for(int i=0;i<e;i++)
edge[i]=new Edge();
}

int find(int parent[],int i)
{
if(parent[i]==-1)
return i;
return find(parent,parent[i]);
}

void union(int parent[],int x,int y)
{
int xset=find(parent, x);
int yset=find(parent, y);
parent[xset]=yset;
}

int isCycle(Graph graph)
{
int parent[]=new int[ graph.V];

for (int i=0; i<graph.V; ++i)
            parent[i]=-1;

        for (int i = 0; i < graph.E; ++i)
        {
            int x = graph.find(parent, graph.edge[i].src);
            int y = graph.find(parent, graph.edge[i].dest);

            if (x == y)
                return 1;

            graph.union(parent, x, y);
        }
        return 0;
   
}

public static void main(String[] args)
{
int V = 3, E = 3;
        Graph graph = new Graph(V, E);

        // add edge 0-1
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;

        // add edge 1-2
        graph.edge[1].src = 1;
        graph.edge[1].dest = 2;

        // add edge 0-2
        graph.edge[2].src = 0;
        graph.edge[2].dest = 2;

        if (graph.isCycle(graph)==1)
            System.out.println( "graph contains cycle" );
        else
            System.out.println( "graph doesn't contain cycle" );
}

}

Result:

graph contains cycle

Tuesday, June 28, 2016

Applications of Depth First Search and Breadth First Traversal

Applications of Depth First Search

Depth-first search (DFS) is an algorithm (or technique) for traversing a graph.

Following are the problems that use DFS as a building block.

1) For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree and all pair shortest path tree.

2) Detecting cycle in a graph 
A graph has cycle if and only if we see a back edge during DFS. So we can run DFS for the graph and check for back edges.

3) Path Finding

We can specialize the DFS algorithm to find a path between two given vertices u and z.

i) Call DFS(G, u) with u as the start vertex.
ii) Use a stack S to keep track of the path between the start vertex and the current vertex.
iii) As soon as destination vertex z is encountered, return the path as the
contents of the stack

4) Topological Sorting

Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbol dependencies in linkers [2].

5) To test if a graph is bipartite

We can augment either BFS or DFS when we first discover a new vertex, color it opposited its parents, and for each other edge, check it doesn’t link two vertices of the same color. The first vertex in any connected component can be red or black.

6) Finding Strongly Connected Components of a graph A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex.

7) Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)


Applications of Breadth First Traversal

We have earlier discussed Breadth First Traversal Algorithm for Graphs. We have also discussed Applications of Depth First Traversal. In this article, applications of Breadth First Search are discussed.

1) Shortest Path and Minimum Spanning Tree for unweighted graph In unweighted graph, the shortest path is the path with least number of edges. With Breadth First, we always reach a vertex from given source using minimum number of edges. Also, in case of unweighted graphs, any spanning tree is Minimum Spanning Tree and we can use either Depth or Breadth first traversal for finding a spanning tree.

2) Peer to Peer Networks. In Peer to Peer Networks like BitTorrent, Breadth First Search is used to find all neighbor nodes.

3) Crawlers in Search Engines: Crawlers build index using Bread First. The idea is to start from source page and follow all links from source and keep doing same. Depth First Traversal can also be used for crawlers, but the advantage with Breadth First Traversal is, depth or levels of built tree can be limited.

4) Social Networking Websites: In social networks, we can find people within a given distance ‘k’ from a person using Breadth First Search till ‘k’ levels.

5) GPS Navigation systems: Breadth First Search is used to find all neighboring locations.

6) Broadcasting in Network: In networks, a broadcasted packet follows Breadth First Search to reach all nodes.

7) In Garbage Collection: Breadth First Search is used in copying garbage collection using Cheney’s algorithm. Refer this and for details. Breadth First Search is preferred over Depth First Search because of better locality of reference:

8) Cycle detection in undirected graph: In undirected graphs, either Breadth First Search or Depth First Search can be used to detect cycle. In directed graph, only depth first search can be used.

9) Ford–Fulkerson algorithm In Ford-Fulkerson algorithm, we can either use Breadth First or Depth First Traversal to find the maximum flow. Breadth First Traversal is preferred as it reduces worst case time complexity to O(VE2).

10) To test if a graph is Bipartite We can either use Breadth First or Depth First Traversal.

11) Path Finding We can either use Breadth First or Depth First Traversal to find if there is a path between two vertices.

12) Finding all nodes within one connected component: We can either use Breadth First or Depth First Traversal to find all nodes reachable from a given node.

Many algorithms like Prim’s Minimum Spanning Tree and Dijkstra’s Single Source Shortest Path use structure similar to Breadth First Search.

There can be many more applications as Breadth First Search is one of the core algorithm for Graphs.

Depth First Search Algorithm(DFS) Example Java

Depth First Search algorithm(DFS) traverses a graph in a depth ward motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration.

The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array.
For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Depth First Traversal of the following graph is 2, 0, 1, 3.

As in example given above, DFS algorithm traverses from A to B to C to D first then to E, then to F and lastly to G.

It employs following rules.

Rule 1 − Visit adjacent unvisited vertex. Mark it visited. Display it. Push it in a stack.

Rule 2 − If no adjacent vertex found, pop up a vertex from stack. (It will pop up all the vertices from the stack which do not have adjacent vertices.)

Rule 3 − Repeat Rule 1 and Rule 2 until stack is empty.

As C does not have any unvisited adjacent node so we keep popping the stack until we find a node which has unvisited adjacent node. In this case, there's none and we keep popping until stack is empty.

DFS Implementation:

import java.util.Iterator;
import java.util.LinkedList;

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class Graph
{
private int V;
private LinkedList<Integer> adjacentList[];

Graph(int v)
    {
        V = v;
        adjacentList = new LinkedList[v];
        for (int i=0; i<v; ++i)
        adjacentList[i] = new LinkedList();
    }

// Function to add an edge into the graph
    void addEdge(int v,int w)
    {
    adjacentList[v].add(w);
    }


 // A function used by DFS
    void DFSUtil(int v,boolean visited[])
    {
        // Mark the current node as visited and print it
        visited[v] = true;
        System.out.print(v+" ");

        // Recur for all the vertices adjacent to this vertex
        Iterator<Integer> i = adjacentList[v].listIterator();
        while (i.hasNext())
        {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // The function to do DFS traversal. It uses recursive DFSUtil()
    void DFS(int v)
    {
        // Mark all the vertices as not visited(set as
        // false by default in java)
        boolean visited[] = new boolean[V];

        // Call the recursive helper function to print DFS traversal
        DFSUtil(v, visited);
    }

public static void main(String[] args)
{

Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Following is Depth First Traversal "+
                           "(starting from vertex 2)");

        g.DFS(2);
}

}


Result: 

Following is Depth First Traversal (starting from vertex 2)
2 0 1 3

Note that the above code traverses only the vertices reachable from a given source vertex. All the vertices may not be reachable from a given vertex (example Disconnected graph). To do complete DFS traversal of such graphs, we must call DFSUtil() for every vertex. Also, before calling DFSUtil(), we should check if it is already printed by some other call of DFSUtil().

Graph Breadth First Search Example in Java

Breadth First Search algorithm(BFS) traverses a graph in a breadth wards motion and uses a queue to remember to get the next vertex to start a search when a dead end occurs in any iteration. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. For simplicity, it is assumed that all vertices are reachable from the starting vertex.


For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Breadth First Traversal of the following graph is 2, 0, 3, 1.

It employs following rules.

Rule 1 − Visit adjacent unvisited vertex. Mark it visited. Display it. Insert it in a queue.

Rule 2 − If no adjacent vertex found, remove the first vertex from queue.

Rule 3 − Repeat Rule 1 and Rule 2 until queue is empty.

At this stage we are left with no unmarked (unvisited) nodes. But as per algorithm we keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied the program is over.

Graph Implementation:

import java.util.Iterator;
import java.util.LinkedList;

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class Graph
{
private int V;
private LinkedList<Integer> adjacentList[];

Graph(int v)
    {
        V = v;
        adjacentList = new LinkedList[v];
        for (int i=0; i<v; ++i)
        adjacentList[i] = new LinkedList();
    }

// Function to add an edge into the graph
    void addEdge(int v,int w)
    {
    adjacentList[v].add(w);
    }

 // prints BFS traversal from a given source s
    void BFS(int s)
    {
        // Mark all the vertices as not visited(By default
        // set as false)
        boolean visited[] = new boolean[V];

        // Create a queue for BFS
        LinkedList<Integer> queue = new LinkedList<Integer>();

        // Mark the current node as visited and enqueue it
        visited[s]=true;
        queue.add(s);

        while (queue.size() != 0)
        {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            System.out.print(s+" ");

            // Get all adjacent vertices of the dequeued vertex s
            // If a adjacent has not been visited, then mark it
            // visited and enqueue it
            Iterator<Integer> i = adjacentList[s].listIterator();
            while (i.hasNext())
            {
                int n = i.next();
                if (!visited[n])
                {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }  
public static void main(String[] args)
{
Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Following is Breadth First Traversal "+
                           "(starting from vertex 2)");

        g.BFS(2);
}


}

Result:

Following is Breadth First Traversal (starting from vertex 2)
2 0 3 1 


Note that the above code traverses only the vertices reachable from a given source vertex. All the vertices may not be reachable from a given vertex (example Disconnected graph). To print all the vertices, we can modify the BFS function to do traversal starting from all nodes one by one  .

Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.

Graph and its representations in Java

A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.


Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices.




Graph Data Structure

Mathematical graphs can be represented in data-structure. We can represent a graph using an array of vertices and a two dimensional array of edges. Before we proceed further, let's familiarize ourselves with some important terms −

Vertex − Each node of the graph is represented as a vertex. In example given below, labeled circle represents vertices. So A to G are vertices. We can represent them using an array as shown in image below. Here A can be identified by index 0. B can be identified using index 1 and so on.

Edge − Edge represents a path between two vertices or a line between two vertices. In example given below, lines from A to B, B to C and so on represents edges. We can use a two dimensional array to represent array as shown in image below. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations as 0.

Adjacency − Two node or vertices are adjacent if they are connected to each other through an edge. In example given below, B is adjacent to A, C is adjacent to B and so on.


Path − Path represents a sequence of edges between two vertices. In example given below, ABCD represents a path from A to D.


Basic Operations

Following are basic primary operations of a Graph which are following.

Add Vertex − add a vertex to a graph.

Add Edge − add an edge between two vertices of a graph.


Display Vertex − display a vertex of a graph.


Graph is a data structure that consists of following two components:

1. A finite set of vertices also called as nodes

2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is not same as (v, u) in case of directed graph(di-graph). The pair of form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.

Graphs are used to represent many real life applications: Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used in social networks like LinkedIn, Facebook. For example, in Facebook, each person is represented with a vertex(or node). Each node is a structure and contains information like person id, name, gender and locale.

   

Following two are the most commonly used representations of graph.

1. Adjacency Matrix
2. Adjacency List

There are other representations also like, Incidence Matrix and Incidence List. The choice of the graph representation is situation specific. It totally depends on the type of operations to be performed and ease of use.


Adjacency Matrix:

Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

The adjacency matrix for the above example graph is:


Pros: Representation is easier to implement and follow. Removing an edge takes O(1) time. Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be done O(1).

Cons: Consumes more space O(V^2). Even if the graph is sparse(contains less number of edges), it consumes the same space. Adding a vertex is O(V^2) time.


Adjacency List:

An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be stored in nodes of linked lists.



Pros: Saves space O(|V|+|E|) . In the worst case, there can be C(V, 2) number of edges in a graph thus consuming O(V^2) space. Adding a vertex is easier.

Cons: Queries like whether there is an edge from vertex u to vertex v are not efficient and can be done O(V).


Android JSON parsing without Volley example

1)
?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android" 
   package="com.myandroid.jsonparsing" 
   android:versionCode="1" 
   android:versionName="1.0" >

    <uses-sdk
        android:minSdkVersion="8" 
       android:targetSdkVersion="18" />
    
   <uses-permission android:name="android.permission.INTERNET" />
    <application 
       android:icon="@drawable/ic_launcher" 
       android:label="@string/app_name" >
        <activity
            android:label="@string/app_name" 
           android:name="com.myandroid.jsonparsing.MainActivity" >
            <intent-filter >
                <action android:name="android.intent.action.MAIN" />

                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>
        
          <activity
            android:label="Contact"
            android:name="com.myandroid.jsonparsing.SingleContactActivity" >
        </activity>
    </application>

</manifest>


2)ServiceHandler.Java


import java.io.IOException;
import java.io.UnsupportedEncodingException;
import java.util.List;

import org.apache.http.HttpEntity;
import org.apache.http.HttpResponse;
import org.apache.http.NameValuePair;
import org.apache.http.client.ClientProtocolException;
import org.apache.http.client.entity.UrlEncodedFormEntity;
import org.apache.http.client.methods.HttpGet;
import org.apache.http.client.methods.HttpPost;
import org.apache.http.client.utils.URLEncodedUtils;
import org.apache.http.impl.client.DefaultHttpClient;
import org.apache.http.util.EntityUtils;

public class ServiceHandler {

   static String response = null;
   public final static int GET = 1;
   public final static int POST = 2;

   public ServiceHandler() {

   }

   public String makeServiceCall(String url, int method) {
      return this.makeServiceCall(url, method, null);
   }

     public String makeServiceCall(String url, int method,
         List<NameValuePair> params) {
      try {
         // http client         DefaultHttpClient httpClient = new DefaultHttpClient();
         HttpEntity httpEntity = null;
         HttpResponse httpResponse = null;
         
         // Checking http request method type         if (method == POST) {
            HttpPost httpPost = new HttpPost(url);
            // adding post params            if (params != null) {
               httpPost.setEntity(new UrlEncodedFormEntity(params));
            }

            httpResponse = httpClient.execute(httpPost);

         } else if (method == GET) {
            // appending params to url            if (params != null) {
               String paramString = URLEncodedUtils
                     .format(params, "utf-8");
               url += "?" + paramString;
            }
            HttpGet httpGet = new HttpGet(url);

            httpResponse = httpClient.execute(httpGet);

         }
         httpEntity = httpResponse.getEntity();
         response = EntityUtils.toString(httpEntity);

      } catch (UnsupportedEncodingException e) {
         e.printStackTrace();
      } catch (ClientProtocolException e) {
         e.printStackTrace();
      } catch (IOException e) {
         e.printStackTrace();
      }
      
      return response;

   }
}


3)MainActivity.java
import java.util.ArrayList;
import java.util.HashMap;

import org.json.JSONArray;
import org.json.JSONException;
import org.json.JSONObject;

import android.app.ListActivity;
import android.app.ProgressDialog;
import android.content.Intent;
import android.os.AsyncTask;
import android.os.Bundle;
import android.util.Log;
import android.view.View;
import android.widget.AdapterView;
import android.widget.AdapterView.OnItemClickListener;
import android.widget.ListAdapter;
import android.widget.ListView;
import android.widget.SimpleAdapter;
import android.widget.TextView;

public class MainActivity extends ListActivity 
{
 private ProgressDialog pDialog;
 // URL to get contacts JSON
 private static String url = "http://api.androidhive.info/contacts/";
 // JSON Node names
 private static final String TAG_CONTACTS = "contacts";
 private static final String TAG_ID = "id";
 private static final String TAG_NAME = "name";
 private static final String TAG_EMAIL = "email";
 private static final String TAG_ADDRESS = "address";
 private static final String TAG_GENDER = "gender";
 private static final String TAG_PHONE = "phone";
 private static final String TAG_PHONE_MOBILE = "mobile";
 private static final String TAG_PHONE_HOME = "home";
 private static final String TAG_PHONE_OFFICE = "office";

 // contacts JSONArray
 JSONArray contacts = null;
 // Hashmap for ListView
 ArrayList<HashMap<String, String>> contactList;
 @Override
 public void onCreate(Bundle savedInstanceState)
        {
   super.onCreate(savedInstanceState);
   setContentView(R.layout.activity_main);

   contactList = new ArrayList<HashMap<String, String>>();

   ListView lv = getListView();

   // Listview on item click listener
     lv.setOnItemClickListener(new OnItemClickListener() 
              {

  @Override
  public void onItemClick(AdapterView<?> parent, View view,
     int position, long id) {
    // getting values from selected ListItem
    String name = ((TextView) view.findViewById(R.id.name))
      .getText().toString();
    String cost = ((TextView) view.findViewById(R.id.email))
      .getText().toString();
    String description = ((TextView) view.findViewById(R.id.mobile))
      .getText().toString();

    // Starting single contact activity
    Intent in = new Intent(getApplicationContext(),
      SingleContactActivity.class);
    in.putExtra(TAG_NAME, name);
    in.putExtra(TAG_EMAIL, cost);
    in.putExtra(TAG_PHONE_MOBILE, description);
    startActivity(in);

   }
  });

  // Calling async task to get json
  new GetContacts().execute();
 }

 /**
  * Async task class to get json by making HTTP call
  * */
 private class GetContacts extends AsyncTask<Void, Void, Void> {

  @Override
  protected void onPreExecute() {
   super.onPreExecute();
   // Showing progress dialog
   pDialog = new ProgressDialog(MainActivity.this);
   pDialog.setMessage("Please wait...");
   pDialog.setCancelable(false);
   pDialog.show();

  }

  @Override
  protected Void doInBackground(Void... arg0) {
   // Creating service handler class instance
   ServiceHandler sh = new ServiceHandler();

   // Making a request to url and getting response
   String jsonStr = sh.makeServiceCall(url, ServiceHandler.GET);

   Log.d("Response: ", "> " + jsonStr);

   if (jsonStr != null) {
    try {
     JSONObject jsonObj = new JSONObject(jsonStr);
     
     // Getting JSON Array node
     contacts = jsonObj.getJSONArray(TAG_CONTACTS);

     // looping through All Contacts
     for (int i = 0; i < contacts.length(); i++) {
      JSONObject c = contacts.getJSONObject(i);
      
      String id = c.getString(TAG_ID);
      String name = c.getString(TAG_NAME);
      String email = c.getString(TAG_EMAIL);
      String address = c.getString(TAG_ADDRESS);
      String gender = c.getString(TAG_GENDER);

      // Phone node is JSON Object
      JSONObject phone = c.getJSONObject(TAG_PHONE);
      String mobile = phone.getString(TAG_PHONE_MOBILE);
      String home = phone.getString(TAG_PHONE_HOME);
      String office = phone.getString(TAG_PHONE_OFFICE);

      // tmp hashmap for single contact
      HashMap<String, String> contact = new HashMap<String, String>();

      // adding each child node to HashMap key => value
      contact.put(TAG_ID, id);
      contact.put(TAG_NAME, name);
      contact.put(TAG_EMAIL, email);
      contact.put(TAG_PHONE_MOBILE, mobile);

      // adding contact to contact list
      contactList.add(contact);
     }
    } catch (JSONException e) {
     e.printStackTrace();
    }
   } else {
    Log.e("ServiceHandler", "Couldn't get any data from the url");
   }

   return null;
  }

  @Override
  protected void onPostExecute(Void result) {
   super.onPostExecute(result);
   // Dismiss the progress dialog
   if (pDialog.isShowing())
    pDialog.dismiss();
   /**
    * Updating parsed JSON data into ListView
    * */
   ListAdapter adapter = new SimpleAdapter(
     MainActivity.this, contactList,
     R.layout.list_item, new String[] { TAG_NAME, TAG_EMAIL,
       TAG_PHONE_MOBILE }, new int[] { R.id.name,
       R.id.email, R.id.mobile });

   setListAdapter(adapter);
  }

 }

}




4)SingleContactActivity.java

import android.app.Activity;
import android.content.Intent;
import android.os.Bundle;
import android.widget.TextView;
import info.androidhive.jsonparsing.R;

public class SingleContactActivity  extends Activity {
   
   // JSON node keys   private static final String TAG_NAME = "name";
   private static final String TAG_EMAIL = "email";
   private static final String TAG_PHONE_MOBILE = "mobile";
   @Override    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_single_contact);
        
          Intent in = getIntent();
   
        String name = in.getStringExtra(TAG_NAME);
        String email = in.getStringExtra(TAG_EMAIL);
        String mobile = in.getStringExtra(TAG_PHONE_MOBILE);
        
        TextView lblName = (TextView) findViewById(R.id.name_label);
        TextView lblEmail = (TextView) findViewById(R.id.email_label);
        TextView lblMobile = (TextView) findViewById(R.id.mobile_label);
        
        lblName.setText(name);
        lblEmail.setText(email);
        lblMobile.setText(mobile);
    }
}




5)activity_main.xml:


<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android" 
   android:layout_width="fill_parent"    android:layout_height="fill_parent" 
   android:orientation="vertical">
    <ListView   
     android:id="@android:id/list"  
      android:layout_width="fill_parent"
        android:layout_height="wrap_content"/>

</LinearLayout>


6)activity_single_contact.xml


<?xml version="1.0" encoding="utf-8"?>
<LinearLayout  xmlns:android="http://schemas.android.com/apk/res/android"
  android:orientation="vertical"  android:layout_width="match_parent" 
 android:layout_height="match_parent"  android:padding="10dp">
  <!-- Name Label -->  <TextView android:id="@+id/name_label"       
     android:layout_width="fill_parent"           
 android:layout_height="wrap_content"          
  android:textSize="25dip"         
   android:textStyle="bold"         
   android:paddingTop="10dip"        
    android:paddingBottom="10dip"         
   android:textColor="#43bd00"/>
  <TextView android:id="@+id/email_label"      
      android:layout_width="fill_parent"     
       android:layout_height="wrap_content"    
        android:textColor="#acacac"/>
  <TextView android:id="@+id/mobile_label"    
      android:layout_width="fill_parent"       
   android:layout_height="wrap_content"    
      android:textStyle="bold"/>
</LinearLayout>


7)list_item.xml:


<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="fill_parent"
    android:layout_height="wrap_content"
    android:orientation="vertical"
    android:padding="10dp" 
   android:paddingLeft="10dp"
    android:paddingRight="10dp" >

    <!-- Name Label -->
    <TextView     
   android:id="@+id/name"  
      android:layout_width="fill_parent"   
     android:layout_height="wrap_content"   
     android:paddingBottom="2dip"      
  android:paddingTop="6dip"      
  android:textColor="#43bd00"    
    android:textSize="16sp"     
   android:textStyle="bold" />

 <TextView 
       android:id="@+id/email"
        android:layout_width="fill_parent" 

       android:layout_height="wrap_content" 
       android:paddingBottom="2dip" 
       android:textColor="#acacac" />
  <TextView   
     android:id="@+id/mobile" 
       android:layout_width="wrap_content"  
      android:layout_height="wrap_content"  
      android:gravity="left"   
     android:text="Mobile: "   
     android:textColor="#5d5d5d" 
       android:textStyle="bold" />

</LinearLayout>


Android Best Practices for Interaction and Engagement for Developers

Best Practices for Interaction and Engagement:

These classes teach you how to engage and retain your users by implementing the best interaction patterns for Android. For instance, to help users quickly discover content in your app, your app should match their expectations for user interaction on Android. And to keep your users coming back, you should take advantage of platform capabilities that reveal and open your content without requiring users to go through the app launcher.

2)Designing Effective Navigation:

One of the very first steps to designing and developing an Android application is to determine what users are able to see and do with the app. Once you know what kinds of data users are interacting with in the app, the next step is to design the interactions that allow users to navigate across, into, and back out from the different pieces of content within the app.

This class shows you how to plan out the high-level screen hierarchy for your application and then choose appropriate forms of navigation to allow users to effectively and intuitively traverse your content. Each lesson covers various stages in the interaction design process for navigation in Android applications, in roughly chronological order. After going through the lessons in this class, you should be able to apply the methodology and navigation paradigms outlined here to your own applications, providing a coherent navigation experience for your users.

2.a)Planning Screens and Their Relationships:

Most apps have an inherent information model that can be expressed as a tree or graph of object types. In more obvious terms, you can draw a diagram of different kinds of information that represents the types of things users interact with in your app. Software engineers and data architects often use entity-relationship diagrams (ERDs) to describe an application's information model.

b)Create a Screen List: 

Once you define the information model, you can begin to define the contexts necessary to enable users to effectively discover, view, and act upon the data in your application. In practice, one way to do this is to determine the exhaustive set of screens needed to allow users to navigate to and interact with the data. The set of screens we actually expose should generally vary depending on the target device; it's important to consider this early in the design process to ensure that the application can adapt to its environment.

In our example application, we want to enable users to view, save, and share categorized stories and photos. Below is an exhaustive list of screens that covers these use cases.

Home or "launchpad" screen for accessing stories and photos
List of categories
List of news stories for a given category
Story detail view (from which we can save and share)
List of photos, uncategorized
Photo detail view (from which we can save and share)
List of all saved items
List of saved photos
List of saved stories

c)Diagram Screen Relationships:

Now we can define the directed relationships between screens; an arrow from one screen A to another screen B implies that screen B should be directly reachable via some user interaction in screen A. Once we define both the set of screens and the relationships between them, we can express these in concert as a screen map, which shows all of your screens and their relationships.
If we later wanted to allow users to submit news stories or upload photos, we could add additional screens to this diagram.

d)Go Beyond a Simplistic Design:

At this point, it's possible to design a completely functional application from this exhaustive screen map. A simplistic user interface could consist of lists and buttons leading to child screens:

Buttons leading to different sections (e.g., stories, photos, saved items)
Vertical lists representing collections (e.g., story lists, photo lists, etc.)
Detail information (e.g., story view, full-screen photo view, etc.)
However, you can use screen grouping techniques and more sophisticated navigation elements to present content in a more intuitive and device-sensitive way. In the next lesson, we explore screen grouping techniques, such as providing multi-pane layouts for tablet devices. Later, we'll dive into the various navigation patterns common on Android.

3)Planning for Multiple Touchscreen Sizes:

The exhaustive screen map from the previous lesson isn't tied to a particular device form factor, although it can generally look and work okay on a handset or similar-size device. But Android applications need to adapt to a number of different types of devices, from 3" handsets to 10" tablets to 42" TVs. In this lesson we explore reasons and tactics for grouping together multiple screens from the exhaustive map.

Note: Designing applications for television sets also requires attention to other factors, including interaction methods (i.e., the lack of a touch screen), legibility of text at large reading distances, and more. Although this discussion is outside the scope of this class, you can find more information on designing for TVs in the Google TV documentation for design patterns.

4)Group Screens with Multi-pane Layouts:

Multi-pane Layout Design

For design guidelines, read Android Design's Multi-pane Layouts pattern guide.
3 to 4-inch screens are generally only suitable for showing a single vertical pane of content at a time, be it a list of items, or detail information about an item, etc. Thus on such devices, screens generally map one-to-one with levels in the information hierarchy (categories → object list → object detail).

Larger screens such as those found on tablets and TVs, on the other hand, generally have much more available screen space and are able to present multiple panes of content. In landscape, panes are usually ordered from left to right in increasing detail order. Users are especially accustomed to multiple panes on larger screens from years and years of desktop application and desktop web site use. Many desktop applications and websites offer a left-hand navigation pane or use a master/detail two-pane layout.

In addition to addressing these user expectations, it's usually necessary to provide multiple panes of information on tablets to avoid leaving too much whitespace or unwittingly introducing awkward interactions, for example 10 x 0.5-inch buttons.

The following figures demonstrate some of the problems that can arise when moving a UI (user interface) design into a larger layout and how to address these issues with multi-pane layouts:

Implementation Note: After deciding on the screen size at which to draw the line between single-pane and multi-pane layouts, you can provide different layouts containing one or multiple panes for devices in varying screen size buckets (such as large/xlarge) or varying minimum screen widths (such as sw600dp).

Implementation Note: While a single screen is implemented as an Activity subclass, individual content panes can be implemented as Fragment subclasses. This maximizes code re-use across different form factors and across screens that share content.

5)Design for Multiple Tablet Orientations:

Although we haven't begun arranging user interface elements on our screens yet, this is a good time to consider how your multi-pane screens will adapt to different device orientations. Multi-pane layouts in landscape work quite well because of the large amount of available horizontal space. However, in the portrait orientation, your horizontal space is more limited, so you may need to design a separate layout for this orientation.

Below are a few common strategies for creating portrait tablet layouts.

Stretch  Stretch strategy:

The most straightforward strategy is to simply stretch each pane's width to best present the content in each pane in the portrait orientation. Panes could have fixed widths or take a certain percentage of the available screen width.

Expand/collapse  Expand/collapse strategy:

A variation on the stretch strategy is to collapse the contents of the left pane when in portrait. This works quite well with master/detail panes where the left (master) pane contains easily collapsible list items. An example would be for a realtime chat application. In landscape, the left list could contain chat contact photos, names, and online statuses. In portrait, horizontal space could be collapsed by hiding contact names and only showing photos and online status indicator icons. Optionally also provide an expand control that allows the user to expand the left pane content to its larger width and vice versa.

Show/Hide  Show/Hide strategy:

In this scenario, the left pane is completely hidden in portrait mode. However, to ensure the functional parity of your screen in portrait and landscape, the left pane should be made available via an onscreen affordance (such as a button). It's usually appropriate to use the Up button in the Action Bar (pattern docs at Android Design) to show the left pane, as is discussed in a later lesson.

Stack  Stack strategy:

The last strategy is to vertically stack your normally horizontally-arranged panes in portrait. This strategy works well when your panes aren't simple text-based lists, or when there are multiple blocks of content running along the primary content pane. Be careful to avoid the awkward whitespace problem discussed above when using this strategy.

6)Group Screens in the Screen Map:

Now that we are able to group individual screens together by providing multi-pane layouts on larger-screen devices, let's apply this technique to our exhaustive screen map from the previous lesson to get a better sense of our application's hierarchy on such devices: