All Permutations

Given a string,the task is to print all the permutations of the string.
A permutation is a rearrangement of the elements of an ordered list S.A string of length N has N! permutations.

Example-

Let the string be S=”abc”.

Length of the string=3

Number of permutations=3!=6

Permutations-

abc
acb
bac
bca
cab
cba

Algorithm-

Basic idea-

All permutations of a string X is the same thing as all permutations of each possible character in X, combined with all permutations of the string X without that letter in it.

All permutations of “abcd” are-

“a” concatenated with all permutations of “bcd”.
“b” concatenated with all permutations of “acd”.
“c” concatenated with all permutations of “bad”.
“d” concatenated with all permutations of “bca”.

Recursive solution-

The first character is kept constant and permutations are generated with the rest.Then,the first two characters are kept constant and permutations are generated with the rest until we are out of characters.

This algorithm is performed on the input string itself.Thus,no additional memeory is required.The “backtracking” undoes the changes to the string, leaving it in its original state.

Code-

[cpp]

char a[1000];//string

//to swap characters at position i and j

void swap (int i, int j)
{
char temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}

//i is the starting index
//n is the ending index
//initially,permute(0,n-1) is called

void permute(int i, int n)
{
int j;

if (i == n)
printf(“%s\n”, a);

else
{
for (j = i; j <= n; j++)
{
swap(i,j);
//increasing the number of fixed characters
permute(i+1, n);
swap(i,j); //backtrack
}
}
}

[/cpp]

Note-

It has a time complexity of O(N*N!) and is an example of Backtracking.

List View using Array Adapters – Part II : Using ListActivity

In the previous post, I showed you how to create a ListView and populate it with elements of a String array. If you can recall, we used a regular activity in the process. By regular activity I mean that our Java class extended Android.App.Activity class.

It is worth knowing that Android has a special class names Android.App.ListActivity that is meant specifically for a ListView purpose. In this post I am going to show you how to use ListActivity class for creating a ListView. Remember that even though it is meant specifically for a ListView, it does support other elements of an Android layout. Complete Source Code is at the bottom.

  • Start off an activity. Switch to the XML layout file and insert a ListView from the palette on the left.
  • Spread it all the way across the length and breadth of the activity.
  • Switch over to the MainActivity.java file and declare the ListView. Unlike what we did in the last post, we are going to use a different declaration here.
    [java]
    ListView lv = getListView();
    [/java]
  • Obviously, since we are using a dedicated class, getListView() method makes perfect sense. Remember that this cannot be used in a regular activity.
  • Remember that a ListActivity requires your ListView to be identified as android.R.id.list. In order to do that, you need to edit your XML file to set the android:id attribute of the ListView to @+id/list. In some systems, this needs to be set to @+id/android:list.
  • Create a string array containing elements that you want in the list. Try and put enough values so that you can also experience the scrolling feature of ListView provided by default in the ListView element.
  • We are now going to populate the ListView with elements from the string array with the help of an Array Adapter.
  • Now declare the Array Adapter and assign it to the ListView.
  • Save your work and run it on an emulator or device.

Array_Adapter1  Array_Adapter2

COMPLETE SOURCE CODE

activity_main.xml

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingBottom="@dimen/activity_vertical_margin"
    android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin" >

    <ListView
        android:id="@+id/android:list"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_alignParentLeft="true"
        android:layout_alignParentTop="true" >
    </ListView>

</RelativeLayout>

MainActivity.java

[java]
package com.nero.myfirstapp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLConnection;
import android.media.MediaPlayer;
import android.os.Bundle;
import android.preference.PreferenceManager;
import android.provider.ContactsContract;
import android.provider.ContactsContract.PhoneLookup;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ListActivity;
import android.app.ProgressDialog;
import android.content.ContentResolver;
import android.content.DialogInterface;
import android.content.Intent;
import android.content.SharedPreferences;
import android.database.Cursor;
import android.database.sqlite.SQLiteDatabase;
import android.util.Log;
import android.view.LayoutInflater;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.ArrayAdapter;
import android.widget.Button;
import android.widget.EditText;
import android.widget.ListView;
import android.widget.TextView;
import android.widget.Toast;

public class Main extends ListActivity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
String values[]=new String[]{“Vergil”, “Dante”, “Sparda”, “Nero”, “Arkham”, “Agni”, “Rudra”, “Beowulf”, “Nevan”};
ListView lv = getListView();
ArrayAdapter<String> adapter = new ArrayAdapter<String>(this, android.R.layout.simple_list_item_1, android.R.id.text1,values);
lv.setAdapter(adapter);
}
}

[/java]

List View using Array Adapters – Part I

Often times in your application when you want to list down a bunch of data you’re going to use a List View. It provides a predefined layout that helps create a list from a specific set of data. Now, inserting a list view in you activity’s layout is but trivial. Here we are going to see how to populate the list view.

It is to be remembered that a List can be implemented inside an activity in a number of ways. I will try and discuss all such ways in separate posts. Also remember that the classes we are going to use have overloaded constructors and we will be using any one of them. However, all of them are equally important in various situations, so I suggest you use the eclipse code-hinting feature to have a look at all those. Complete Source Code is at the bottom.

  • Start off an activity. Switch to the XML layout file and insert a ListView from the palette on the left.
  • Spread it all the way across the length and breadth of the activity.
  • Switch over to the MainActivity.java file and declare the ListView. 
  • Create a string array containing elements that you want in the list. Try and put enough values so that you can also experience the scrolling feature of ListView provided by default in the ListView element.
  • We are now going to populate the ListView with elements from the string array with the help of an Array Adapter.
  • In order to declare the ArrayAdapter write the below lines:
    [java]
    ArrayAdapter adapter = new ArrayAdapter(this, android.R.layout.simple_list_item_1, android.R.id.text1,values);
    [/java]
  • We can also declare the ArrayAdapter using the below declaration:
    [java]
    ArrayAdapter adapter = new ArrayAdapter(this, android.R.layout.simple_list_item_1, values);
    [/java]
  • As I said earlier, we can use one of many constructors of the ArrayAdapter class depending on our needs and the situation
  • values is the name of the string array containing the elements to be displayed.
  • Now, we have the ArrayAdapter ready and in order to populate the list we need to assign this adapter to the ListView:
    [java]
    lv.setAdapter(adapter);
    [/java]
  • lv is the name of the ListView of my activity.
  • Save your work and run it on an emulator or device.

Array_Adapter1  Array_Adapter2

Understanding the Code:

  • Adapters may be seen as the bridge between the UI components and the data source that fill the data into the UI.
  • There are various types of Adapters – ArrayAdapters, SimpleCursorAdapters, SimpleAdapters etc. We can even make custom adapters that serves our purposes.
  • The declarations that I have shown here has the below constructor:
    [java]
    ArrayAdapter = new ArrayAdapter(Context context, int resource, int textViewResourceId, T[] objects)
    [/java]
  • Once we have setup the bridge i.e. ArrayAdapter we need to use it to populate the List. We do this by using the setAdapter() method.

COMPLETE SOURCE CODE

main_activity.xml

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingBottom="@dimen/activity_vertical_margin"
    android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin" >

    <ListView
        android:id="@+id/android:list"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_alignParentLeft="true"
        android:layout_alignParentTop="true" >
    </ListView>
</RelativeLayout>

MainActivity.java

[java]
package com.nero.myfirstapp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLConnection;
import android.media.MediaPlayer;
import android.os.Bundle;
import android.preference.PreferenceManager;
import android.provider.ContactsContract;
import android.provider.ContactsContract.PhoneLookup;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.ContentResolver;
import android.content.DialogInterface;
import android.content.Intent;
import android.content.SharedPreferences;
import android.database.Cursor;
import android.database.sqlite.SQLiteDatabase;
import android.util.Log;
import android.view.LayoutInflater;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.ArrayAdapter;
import android.widget.Button;
import android.widget.EditText;
import android.widget.ListView;
import android.widget.TextView;
import android.widget.Toast;

public class Main extends Activity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
String values[]=new String[]{“Vergil”, “Dante”, “Sparda”, “Nero”, “Arkham”, “Agni”, “Rudra”, “Beowulf”, “Nevan”};
ListView lv = (ListView) findViewById(R.id.list);
ArrayAdapter adapter = new ArrayAdapter(this, android.R.layout.simple_list_item_1, android.R.id.text1,values);
lv.setAdapter(adapter);
}
}
[/java]

Content Providers in Android

One of the most striking features of Android is Content Providers. In a sentence, Content Providers consist of a centrally located database in Android that helps applications use the data from other applications or those provided by Android itself. A very comprehensive article is on the official Android Documentation here.
This post is aimed at shoeing you how to use Content Providers if you need certain data in your application and hence I will not go into the details of what Content Providers are. Nevertheless, the article linked above will familiarize you with it to a good extent.

Now, we are going to create an application that extracts the contacts from the device. It is obvious that there is no way you can access the contacts because it belongs to a different application that comes pre-installed with Android. This is where we are going to use Content Providers. Let us see how:

  • The first thing we are going to do is add a permission to the manifest file of our application. The permission is android.permission.READ_CONTACTS.
  • This tells Android that we are going to access the contacts list of the device. You don’t want your application to use the contact list of a device without letting the user know. This is hence done to protect user privacy.
  • We are going to extract the contacts and send it to Logcat so we can check if our application ran succesfully.
  • We are not going to have a layout for this activity as we do not need it.
  • Add the following lines below the super.onCreate(savedInstanceState)

    [java]
    Cursor c = getContentResolver().query(ContactsContract.Contacts.CONTENT_URI, null, null, null, null);
    while(c.moveToNext()){
    int nameidx = c.getColumnIndex(PhoneLookup.DISPLAY_NAME);
    String name = c.getString(nameidx);
    Log.d(“CONTACTS”, name);
    }
    [/java]
  • Save it and execute it on an emulator or a device.
  • Since there is no layout for this activity we are going to have to check out the DDMS for the Logs. Below is a snip of how it ran on my system. I have three contacs int my emulator- Nero, Vergil and Dante.

ContentP1

Understanding the Code:

  • Remember that the Content Providers are like a centrally located database.
  • A cursor can be considered analogous to a pointer in most programming languages. It points to the first of the rows retrieved from a query.
  • We access the Content Providers with the help of Content Resolvers class. Here, we make an inline query.
  • Each Content Provider is identified unquely by a URI i.e. Uniform Resource Identifier. The URI here is located with the help of ContactsContract class. The complete URI here is ContactsContract.Contacts.CONTENT_URI.
  • Since a cursor points to a complete row and we just need the name of the contact, we need to identify exactly which column will the contact name be in. For this we make use of the Column Index. We identify the Column Index by a particular constant string inside the PhoneLookup class i.e. PhoneLookup.DISPLAY_NAME. This name identifies uniquely the index of the column where the contact name is located.
  • Once we have the column index, we can easily extract the string from it and log it in the Logcat.
  • It must also be remembered that the Content Provider for this application is inbuilt in Android. If one wishes to share information between two standalone applications, one can create his own Content Provider. This would then enable all other applications to access the application’s data.

COMPLETE SOURCE CODE

MainActivity.java

[java]
package com.nero.myfirstapp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLConnection;

import android.media.MediaPlayer;
import android.os.Bundle;
import android.preference.PreferenceManager;
import android.provider.ContactsContract;
import android.provider.ContactsContract.PhoneLookup;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.ContentResolver;
import android.content.DialogInterface;
import android.content.Intent;
import android.content.SharedPreferences;
import android.database.Cursor;
import android.database.sqlite.SQLiteDatabase;
import android.util.Log;
import android.view.LayoutInflater;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.TextView;
import android.widget.Toast;

public class Main extends Activity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
Cursor c = getContentResolver().query(ContactsContract.Contacts.CONTENT_URI, null, null, null, null);
while(c.moveToNext()){
int nameidx = c.getColumnIndex(PhoneLookup.DISPLAY_NAME);
String name = c.getString(nameidx);
Log.d(“CONTACTS”, name);
}
}
}

[/java]

Network Access in Android Applications

In all the earlier posts throughout this tutorial section, we’ve been dealing with standalone applications i.e. ones that require no network access. But with the ever growing Android market and competitive applications on the play store, there will be times when you will want to introduce some type of network functionality in your application.

In this post, I’m going to help you create an application that will have a very basic network access. We’ll be providing the application a website and we’ll be displaying the source code of that webpage. Of course, we’ll need internet access on the device we run this application on. As far as emulators are concerned, they derive their network access from your system’s internet connection. So fire up an activity and start coding. Complete Source Code is at the bottom.

  • The first thing we need to do is add a permission in the manifest file for internet access. It tells the Android system that the application requires an active internet connection and it will access the connection as and when required.
  • So open up the Manifest file and switch to the permissions tab. Add in the Android.permission.INTERNET permission from the drop down menu.
  • Next we need to setup the layout. We’re going to have a minimal layout consisting of an EditText, a TextView and a Button. We’ll be entering the website name in the EditText and the TextView will display the source when the button is clicked. We’ll span the TextView over the entire area left after placing the other elements.
  • Switch over to the MainActivity.java file and declare the elements appropriately. Remember to make them final variables.
  • We’ll now set up the onClickListener() method of the button. Inside the onClick() method, write the following lines.
    [java]
    try{
    URL url = null;
    url = new URL(et.getText().toString());
    URLConnection conn = url.openConnection();
    BufferedReader x= new BufferedReader(new InputStreamReader(conn.getInputStream()));
    String line = “”;
    while((line=x.readLine())!=null){
    tv.append(line);
    }
    }catch(Exception e){
    e.printStackTrace();
    }
    [/java]
  • Save the activity and launch it in an emulator or a device. Here’s what it looks like on my Gingerbread emulator.

networkinit network

Understanding the Code

  • A closer look at the code clearly shows that we are not using any new concepts but basic Java.
  • We create an object of the URL class of Java and pass it the string value from the EditText.
  • We then set up a URL Connection. The openConnection() method helps us in doing so.
  • We are also using the basic BufferedReader class that we use in basic java programs. This is to read the source code of the website and accept it as input.
  • The whole section has been enclosed in a try catch block because we are dealing with networking here and there are many things that can go wrong like link failure, unrecognized connection etc. We do not want our application to crash but to properly handle these exceptions.
  • Also remember that we are doing exactly what a web browser does while rendering a webpage. Then the question arises why are we only seeing the source code instead of the webpage as in a web browser. This is because web browsers are programmed to understand and render hypertext while out simple TextView is not. Thus we are only able to see the raw source code.

COMPLETE SOURCE CODE

activity_main.xml

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingBottom="@dimen/activity_vertical_margin"
    android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin" >

    <EditText
        android:id="@+id/editText1"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_alignParentLeft="true"
        android:layout_alignParentTop="true"
        android:ems="10" />

    <Button
        android:id="@+id/button1"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_alignParentBottom="true"
        android:layout_alignParentLeft="true"
        android:text="Get Source" />

    <TextView
        android:id="@+id/textView1"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:layout_above="@+id/button1"
        android:layout_alignParentLeft="true"
        android:layout_below="@+id/editText1" />

</RelativeLayout>

MainActivity.java

[java]
package com.nero.myfirstapp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLConnection;

import android.media.MediaPlayer;
import android.os.Bundle;
import android.preference.PreferenceManager;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.content.SharedPreferences;
import android.database.Cursor;
import android.database.sqlite.SQLiteDatabase;
import android.util.Log;
import android.view.LayoutInflater;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.TextView;
import android.widget.Toast;

public class Main extends Activity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
final EditText et = (EditText) findViewById(R.id.editText1);
final Button b = (Button) findViewById(R.id.button1);
final TextView tv = (TextView) findViewById(R.id.textView1);

b.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View v) {
try{
URL url = null;
url = new URL(et.getText().toString());
URLConnection conn = url.openConnection();
BufferedReader x= new BufferedReader(new InputStreamReader(conn.getInputStream()));
String line = “”;
while((line=x.readLine())!=null){
tv.append(line);
}
}catch(Exception e){
e.printStackTrace();
}
}
});
}

}

[/java]

Introducing Android Debug Bridge – Part II

In the part I of this post, I gave you a brief explanation of what ADB is and what is it used for. Although, ADB is a very effective tool and is used in numerous fields of Android Development, we are going to focus on only one which is, using ADB to query our Databases.
It is most likely that you have the previous application on your disk where we had created a database. If not, follow this post, and create one.

Now, to start off follow the steps:

  • Launch Command Prompt and navigate to the platform-tools directory inside your SDK directory. This is where adb.exe is located
  • Launch the ADB shell by typing:
    adb shell
  • Each line should now start with a “#”.
  • If you can recall, I have told you in my earlier posts that all databases of an application is located in
    data -> data -> <your application name> -> databases -> <databasename>.db
  • Navigate to the above location using the following command. Remember that we are not going inside the .db file now:
    cd data/data/<your application name>/databases
  • Now, in order to query the database, we need to execute SQLite queries. To do this, we need to start off the SQLite3 module of the ADB. Execute the following command:
    sqlite3 <databasename>.db
  • If your command is syntactically correct you should see something like this
    SQLite version 3.5.0
    Enter “.help” for instructions
  • Each line should now start with “sqlite>”.
  • List tables : In order to list all the tables present in the database, use the following command
    .table
  • Now, you can execute raw SQLite queries just like you would in an SQLite RDBMS, in order to verify what data the tables in your database hold.
  • Try the below query by substituting NeroTable with the name of your table.
    select * from NeroTable
  • The above query should present you with all the rows and columns present in the table in a formatted fashion.

This post assumes that you have a fair knowledge of SQLite queries and hence I suggest you try some of those out so that you  can have a hands on practice of working with command line tools. It is quite apparent that this gives us a direct access to our databases and we do not have to resort to logs in order to view the data inside the tables as we were doing earlier. Also it prevents writing extra lines of code in our activity.
While developing complex applications containing multiple tables, ADB serves our purposes beautifully and is hence preferred.

Introducing Android Debug Bridge – Part I

Any development work invariably involves the use of terminals. There are many who find the terminal much more fascinating than the GUI. This post is mainly targeted towards those. However, those who are not so much into command user interface, also need to take a look.

ADB exapanded as Android Debug Bridge is a versatile command line tool. It lets your system interact directly with an Emulator instance’s or a tethered Android device’s file system. Remember that this can be done on the device or the emulator itself using a terminal emulator, but writing and executing commands on the device becomes quite a task.
ADB comes with the Android SDK and no separate installation is required. It is located in <your android sdk> -> platform-tools -> adb.exe.

To get started with ADB we need to launch it first. Below instructions are for Windows Users.

  • Open up Run on Windows by pressing Windows+R.
  • Type in cmd to launch the Command Prompt.
  • Now navigate to your Android SDK directory using the cd command. For instance, my SDK is located in G:\Android Development\
    So I type in:

    G:
    cd Android Development
  • Furthermore, in order to navigate to platform-tools I type in:
    cd sdk/platform-tools
  • Type in the below command:
    adb
  • The above command gives a detailed summary of the components present in the ADB. It’s quite a read so you can spare some time to have a look.
  • Now type in the following command:
    adb shell
  • You are now inside the ADB shell. Here you can type and execute ADB commands. Start an emulator and after it has successfully started, execute the below command:
    adb devices
  • This shows the list of all running emulators and tethered Android devices. Remember that in some cases you might need to turn on USB Debugging in your Android device for it to be recognized by the ADB.
  • You can practically control your device from this terminal.

Now that you have a fair idea of what ADB is and what it is used for, it is time you try out some commands on your own. You can start off by reading the official Android Documentation for ADB here.

The post should act as a precursor to what we are going to do next, which is to use ADB shell for SQLite queries on our Application databases. In the part II of this post I will show you how we can stop relying on logs to see the data in our application’s database and make use of ADB shell instead, to do this in a simpler and effective manner.

Path Finding

Given an undirected,unweighted graph and two vertices u and v,the task is to find the path between these two vertices.u can be considered as the source vertex and v as the destination vertex.

Example-

Number of vertices-5
Number of edges-4
Given vertices are 2 and 4.
Edges-
1 2
1 3
3 4
4 5
The path between 2 and 4 is 2->1->3->4.

Algorithm-

1.DFS is called on vertex u.
2.A stack S is kept to keep track of the path between the source vertex and the current vertex.
3.As soon as destination vertex v is encountered,we return the path as the contents of the stack.

Code-

[cpp]

#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;

vector<int>arr[10005];
int n,a,b,j=0,m;
int color[100005];
int u,v;
stack<int> path;

void dfs(int node)
{

//printing the vertices of the path
printf(“%d->”,node+1);

//until final vertex is reached
if(node!=v-1)
{

color[node]=2;//marking the visited nodes

for(int i=0;i<arr[node].size();++i)
{

if(color[arr[node][i]]==0)
{
dfs(arr[node][i]);
}
}
}
}

int main()
{
int t,p;
int i;
p=1;
j=0;

// n is the number of vertices
// m is the number of edges

scanf(“%d %d”,&n,&m);

// u is the source vertex
// v is the destination vertex

scanf(“%d %d”,&u,&v);

//clearing the arrays and vectors

for(i=0;i<n;i++)
arr[i].clear();

for(i=0;i<n;++i){
color[i]=0;
}

while(j<m)
{

//a and b denote the starting and ending points of the edge

scanf(“%d %d”,&a,&b);

//maintaining the adjacency lists

arr[a-1].push_back(b-1);
arr[b-1].push_back(a-1);
j++;

}

//calling dfs on source vertex

dfs(u-1);

return 0;
}

[/cpp]

Databases in Android using SQLite – Part III

Till now, we have restricted ourselves to very simple databases and hence we declare and define the database inside the Main Activity itself. However, this is mostly not the case. Often times in your application you would want to keep your Database and related functions separately from you activity. This is a much better idea because then your activity will consist of all related components and your database class will have all the methods related to creation, access or updation of the database.

In this post I will show you how to keep two classes, one for the Activity and another for your Database related operations. So create a project and follow along. Complete Source code is at the bottom.

  • Create a new Java Class, the super class of which is SQLiteOpenHelper. Name this DatabaseHelper.java
  • Once this is created, you can see that there are two methods that are already present, onCreate() and onUpgrade().
  • Create a class variable named DatabaseName of the type String and assign it a value “NeroDB or anything you like. This will be the name of your Database.
  • We will need to create a constructor for this Class, so write down the following lines just before onCreate() method
    [java]
    public DatabaseHelper(Context context) {
    super(context, DatabaseName, null, 1);
    }
    [/java]
  • Here we are calling the constructor of the Super Class and passing to it the Context, name of the database, CursorFactory(which is null here) and the version of our Database.
  • Now write the following lines in the onCreate(SQLiteDatabase db) method
    [java]
    db.execSQL(“CREATE TABLE IF NOT EXISTS NeroTable(LastName VARCHAR, FirstName VARCHAR, Age INT(3));”);
    [/java]
  • Again, write the following line in the onUpgrade(SQLiteDatabase db, int oldVersion, int newVersion) method
    [java]
    db.execSQL(“DROP TABLE NeroTable;”);
    db.execSQL(“CREATE TABLE IF NOT EXISTS NeroTable(LastName VARCHAR, FirstName VARCHAR, Age INT(3));”);
    [/java]
  • We have just told Android that when the database is created, create a table named NeroTable with the specified columns and if there is an upgrade in the version of the Database, drop the table and create it again leading to deletion of all data.
  • Now to insert values in the table, write the following method after the onUpgrade()

    [java]
    public void InsertValues()
    {
    SQLiteDatabase db = this.getWritableDatabase();
    db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast1’, ‘NeroFirst1’, 20);”);
    db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast2’, ‘NeroFirst2’, 21);”);
    db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast3’, ‘NeroFirst3’, 22);”);
    db.close();
    }
    [/java]
  • Now that we are done with the DatabaseHelper class, switch over to the Main activity and create an object of the DatabaseHelper class. Remember to declare it outside all methods and inside the class.
    [java]
    DatabaseHelper db;
    [/java]
  • Define this inside the onCreate() method of the Main activity.
    [java]
    db = new DatabaseHelper(this);
    [/java]
  • By creating the object and defining it, the constructor of the DatabaseHelper class has been called and hence the Database and the table has been created.
  • Now to insert the values,
    [java]
    db.InsertValues();
    [/java]
  • Remember that we are only using the basic OOP Concepts here of calling a class’s constructor and using the object of that class to call it’s methods.
  • Save your work and execute it on the emulator.

Understanding the Code

  • The onCreate() and the onUpgrade() methods are quite clear.
  • The constructor of the Super method passes the Database Version too. If this Database version is to be changed, the onUpgrade() method comes into play and the table is deleted and recreated. You can try it out by changing the value to a different number.

COMPLETE SOURCE CODE

DatabaseHelper.java

[java]
package com.nero.myfirstapp;

import android.content.Context;
import android.database.Cursor;
import android.database.sqlite.SQLiteDatabase;
import android.database.sqlite.SQLiteOpenHelper;

public class DatabaseHelper extends SQLiteOpenHelper {

static String DatabaseName=”NeroDB”;

public DatabaseHelper(Context context) {
super(context, DatabaseName, null, 1);
}

@Override
public void onCreate(SQLiteDatabase db) {
db.execSQL(“CREATE TABLE IF NOT EXISTS NeroTable(LastName VARCHAR, FirstName VARCHAR, Age INT(3));”);
}

@Override
public void onUpgrade(SQLiteDatabase db, int oldVersion, int newVersion) {
db.execSQL(“DROP TABLE NeroTable;”);
db.execSQL(“CREATE TABLE IF NOT EXISTS NeroTable(LastName VARCHAR, FirstName VARCHAR, Age INT(3));”);
}

public void InsertValues()
{
SQLiteDatabase db = this.getWritableDatabase();
db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast1’, ‘NeroFirst1’, 20);”);
db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast2’, ‘NeroFirst2’, 21);”);
db.execSQL(“INSERT INTO NeroTable VALUES(‘NeroLast3’, ‘NeroFirst3’, 22);”);
db.close();
}
}

[/java]

Main.java

[java]
package com.nero.myfirstapp;

import android.media.MediaPlayer;
import android.os.Bundle;
import android.preference.PreferenceManager;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.content.SharedPreferences;
import android.database.Cursor;
import android.database.sqlite.SQLiteDatabase;
import android.util.Log;
import android.view.LayoutInflater;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.Toast;

public class Main extends Activity {
DatabaseHelper db;
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
db = new DatabaseHelper(this);
db.InsertValues();
db.close();
}
}

[/java]

Longest path in a tree

Given an unweighted and undirected tree,the task is to find the length of the longest path (from one node to another) in that tree.The length of a path in this case is number of edges we traverse from source to destination.

Example-

Number of nodes=3
Number of edges=2
Edges-
1 2
2 3

Output-
2
(1->2->3 is the longest path in the given tree which has a length of 2 units).

Algorithm-

1.Loop through the vertices, starting a new depth first search whenever the loop reaches a vertex that has not already been included in previous DFS calls.
2.A dist[] array is constructed to record the distances of all the vertices from the starting vertex ie. vertex on which DFS is called.
3.Maximum of all the values of the dist[] array is found and the respective vertex number is found.Let it be v.
4.Now,DFS is called on v and dist[] array records the distances of all the vertices from the vertex v.
5.Maximum of all the values of the dist[] array is the final answer that is it is the length of the longest path in the tree.

Code-

[cpp]

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;

vector<int>arr[10005];

int n,a,b,j=0,m;

int color[10005],dist[10005];

//d denotes the distance of the node on which DFS is called from the starting vertex.
void dfs(int node,int d)
{
color[node]=2;
//marking the visited vertices

dist[node]=d;

for(int i=0;i<arr[node].size();++i)
{

if(color[arr[node][i]]==0)
{
dfs(arr[node][i],d+1);
}
}
}

int main()
{
int p;

int i1;
p=1;j=0;

//n is the number of vertices
scanf(“%d”,&n);

for(i=0;i<n;i++)
arr[i].clear();
for(i=0;i<n;++i)
{
color[i]=0;dist[i]=0;
}

//tree has n-1 edges

while(j<n-1)
{
scanf(“%d %d”,&a,&b);
//a and b denote the starting and ending vertices of an edge

arr[a-1].push_back(b-1);
arr[b-1].push_back(a-1);
j++;
}
for(i=0;i<n;++i)
{
if(color[i]==0)
dfs(i,0);
}

int max=0;

// p denotes the vertex with maximum distance

for(i=0;i<n;i++)
{
if(dist[i]>=max)

{ max=dist[i];
p=i;
}
}
//resetting the arrays to call DFS again

for(i=0;i<n;++i)
{
color[i]=0;dist[i]=0;
}

//calling dfs on vertex which has max distance

dfs(p,0);
max=0;
for(i=0;i<n;i++)
{
if(dist[i]>=max)

{ max=dist[i];
p=i;
}
}

cout<<max<<endl;

return 0;

}

[/cpp]