Android - Communication with Services

Tuesday 9 December 2014



As defined by the developer.android site a Service is a application component that can perform long running tasks in the background without an user interface. It can run on a separate process or on the same process as the Activity that started the Service and it will continue to run in the background even if the user switches to another application. Additionally a component can bind to a service to interact with it or even perform inter process communication. We will look into how to make this work but first we must understand the two forms a Service might take:
Bound form - In bound form an application component binds to the Service and allows Components and Service to interact with each other.
Started Free Form - Once started a service can run if free indefinitely or till the task completes depending or restart itself with a null or the same intent depending upon the use.

Creating the Service:

We can create a Service by extending the Service class of Android and overriding the callback methods. Also we need to declare the service in the Manifest file of the application. To have a clear idea of the running have a look at what might be the life cycle of a Service in Android in both bound and started form.

Once running, a service can notify the user of events using Toast Notifications or Status Bar Notifications.For a detailed understanding you can go through the examples in the developer site : http://developer.android.com/guide/components/services.html

Bound Service and Communication:
There are three cases that we will discuss which are enumerated below:
1. When the Service and the Application both belong to the same process then by implementing a binder they can communicate by calling public methods of the Service [TODO]
2. Implementing a Messenger to handle IPC requests
3. Implementing AIDL to allow the operating system to pass the message between boundaries.

In this post we will handle only case one after which we will follow up on the other cases in the upcoming posts. In our example we call a Activity that fires up a service if it is not running which then which then fires up the activity based on a boolean value present in the activity.The code along with the explanation in comments is given below.

//MainActivity.java
package com.example.activityservicecommunication;

import com.example.activityservicecommunication.MyService.MyBinder;

import android.app.Activity;
import android.app.ActivityManager;
import android.app.ActivityManager.RunningServiceInfo;
import android.content.ComponentName;
import android.content.Context;
import android.content.Intent;
import android.content.ServiceConnection;
import android.os.Bundle;
import android.os.Handler;
import android.os.IBinder;
import android.util.Log;
import android.widget.Toast;

public class MainActivity extends Activity {
 
 private final String serviceName = "com.example.activityservicecommunication.MyService";
 private boolean isRanging = false;
 
 MyService myservice; //stores the current instance of the Service
 boolean isBound = false; //value to check if the current instance is present
 
 /**
  * This connection is given which assigns our service class with the instance of the 
  * running service when the activity binds to the service and sets the value of the bound
  * variable as true.
  */
 private ServiceConnection myConnection = new ServiceConnection(){

  @Override
  public void onServiceConnected(ComponentName name, IBinder service) {
   MyBinder binder = (MyBinder) service;
   myservice = binder.getService();
   isBound = true;
  }

  @Override
  public void onServiceDisconnected(ComponentName name) {
   isBound = false;
  }
  
 };

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        if(isMonitoringServiceRunning()){
         //donot fire up
         Toast.makeText(getApplicationContext(), "Service already running", Toast.LENGTH_SHORT).show();
        }else{
         //fire up the service
         Toast.makeText(getApplicationContext(), "Starting Service", Toast.LENGTH_SHORT).show();
         Intent serviceIntent = new Intent(getApplicationContext(),MyService.class);
         bindService(serviceIntent,myConnection,Context.BIND_AUTO_CREATE);
        }
        //simulate the changing values of the variables
        new Handler().postDelayed(new Runnable(){

   @Override
   public void run() {
    isRanging = true;
    if(isBound){
     Toast.makeText(getApplicationContext(), "You should get Notifcation now", Toast.LENGTH_SHORT).show();
     myservice.setRanging();
    }
    new Handler().postDelayed(new Runnable(){

     @Override
     public void run() {
      isRanging = false;
      if(isBound){
       Toast.makeText(getApplicationContext(), "You should get Notifcation now", Toast.LENGTH_SHORT).show();
       myservice.unsetRanging();
      }
     }
     
    }, 5000);
   }
         
        }, 5000);
    }
    

 @Override
 protected void onStop() {
  super.onStop();
  if(isBound){
   unbindService(myConnection);
   isBound = false;
  }
 }




 private boolean isMonitoringServiceRunning(){
     ActivityManager manager = (ActivityManager)getSystemService(ACTIVITY_SERVICE);
     for(RunningServiceInfo service:manager.getRunningServices(Integer.MAX_VALUE)){
      Log.d("MESSAGE",service.service.getClassName());
      if(serviceName.equals(service.service.getClassName())){
       return true;
      }
     }
     return false;
    }
}



package com.example.activityservicecommunication;
import android.app.Notification;
import android.app.NotificationManager;
import android.app.PendingIntent;
import android.app.Service;
import android.content.Context;
import android.content.Intent;
import android.os.Binder;
import android.os.IBinder;
import android.widget.Toast;

public class MyService extends Service {
 
 private final IBinder mbinder = new MyBinder();
 private boolean isRanging = false;
 private boolean prevValue = false;
 private NotificationManager notificationManager;
 private static final int NOTIFICATION_ID = 123;
 
 public class MyBinder extends Binder{
  MyService getService(){
   return MyService.this;
  }
 }

 @Override
 public IBinder onBind(Intent intent) {
  return mbinder;
 }

 @Override
 public void onCreate() {
  notificationManager = (NotificationManager) getSystemService(Context.NOTIFICATION_SERVICE);
  new Thread(){

   @Override
   public void run() {
    while(true){
     if(isRanging!=prevValue){
      postNotification("Rabging Value Changed");
      prevValue = isRanging;
     }
    }
   }

   
  }.start();
  super.onCreate();
 }
 
 public void setRanging(){
  isRanging = true;
 }
 
 public void unsetRanging(){
  isRanging = false;
 }
 
 private void postNotification(String msg) {
     Intent notifyIntent = new Intent(MyService.this, MyService.class);
     notifyIntent.setFlags(Intent.FLAG_ACTIVITY_SINGLE_TOP);
     PendingIntent pendingIntent = PendingIntent.getActivities(
       MyService.this,
         0,
         new Intent[]{notifyIntent},
         PendingIntent.FLAG_UPDATE_CURRENT);
     Notification notification = new Notification.Builder(MyService.this)
         .setSmallIcon(R.drawable.beacon_gray)
         .setContentTitle("Notify Demo")
         .setContentText(msg)
         .setAutoCancel(true)
         .setContentIntent(pendingIntent)
         .build();
     notification.defaults |= Notification.DEFAULT_SOUND;
     notification.defaults |= Notification.DEFAULT_LIGHTS;
     notificationManager.notify(NOTIFICATION_ID, notification);
   }

}  

Put in some xml layout according to the code and register the service in the manifest. You should see two notifications coming up according to when the activity changes the isRanging value in the Service via the public methods.

Largest Contiguous Subarray Sum in O(n) : Kadane's Algorithm

Saturday 6 September 2014



Another important algorithm that is commonly used for finding the largest contiguous subarray sum in linear time is Kadane's algorithm. The pseudocode for the algorithmm is given below:

msf = 0
meh = 0
for each element in the array
    meh = meh + A[i]
    if meh < 0:
        meh = 0
    if msf < meh:
        msf = meh
return msf

Russian Peasant Multiplication

Saturday 30 August 2014
Following is an algorithm to multiply two numbers without using the multiplication operator.Although there are other ways of doing this like using bit-wise operators this method is particularly mentioned because it is named the Russian Peasant Multiplication.

int res = 0;
while(b>0){
    if(b&1==0)
        res = res + a;
    a = a << 1;
    b = b >> 1;
}
return res; 

XOR Linked List

Saturday 9 August 2014
It is a doubly linked list with an advantage of storage requirements than the previous by storing only one pointer. The pointer stores the XOR of the previous and the next node.
 ...  A        B         C         D         E  ...
         <–>  A⊕C  <->  B⊕D  <->  C⊕E  <-> 
For traverisng the list in the forward direction i.e. if you are in C and you need the address of D you can XOR the location of C with the location of B giving you the location of D.Similarly in the case of moving backward to get the location of B we can XOR the location of C and D. Notice however that we always need two locations to start traversing. Hence even though the storage requirements are reduced a number of fallbacks exist between this and the doubly linked lists.

The disadvantages of using a XOR linked list include :
1. Less space requirement increases code complexity
2. Garbage collection schemes wont work with data structures that donot contain literal pointers
3. XOR of pointers is not defined in some context as in C hence need to convert them to integers and store
4. Ability to delete a node knowing only the address of the node is not present
5. Ability to insert a node knowing only its address is not present

The program below shows a doubly linked list using a single pointer to the next node with add and display functions.
 
#include<iostream>
#include<cstdlib>
using namespace std;

struct Node {
 int data;
 unsigned int next;
}*start,*end,*newNode;

typedef struct Node NODE;

int menu(){
 int choice;
 cout << "1. Add" << endl;
 cout << "2. Display" << endl;
 cout << "3. Exit" << endl;
 cin >> choice;
 return choice;
}

void add(){
 newNode = (NODE *)malloc(sizeof(NODE));
 newNode->next = 0;
 cout << "Enter nodes data:" ;
 cin >> (newNode->data);
 if(start==NULL){
  start = end = newNode;
 }else{
  newNode->next = (unsigned int)end ^ 0;
  end->next = (end->next^0)^(unsigned int)newNode;
  end=newNode;
 }
}

void display(){
 NODE *temp,*curr,*prev;
 prev = curr = temp = NULL;
 for ( curr = start; curr != end ; temp = prev ,\
    prev = curr , curr = ( NODE * ) ( curr -> next ^ (unsigned int)temp ) )
       cout << curr -> data << endl;
    cout << curr -> data << endl;
}

int main()
{
 int choice;
 while(1){
  choice = menu();
  if(choice==3)
   break;
  switch(choice){
  case 1: add();break;
  case 2: display();break;
  }
 }
 return 0;
} 

Getting the next largest palindrome

Thursday 31 July 2014
For a given number n we need to find the numerically larger number that is a palindrome. The simple approach which is not good for large numbers is to check if the number is palindrome and increment by 1 till we find the next number which is  a palindrome.

A smarter algorithm is as follows :
1. Split the string into the left and right halfs
2. Compare the last digit in the left half and the first digit in the right half.
     a. If right is greater than the left, increment the left and stop
     b. If right is less than the left, stop
     c. If right is equal to the left, then continue the step 3 with the next the previous digit and so on
3. Take the left half and append the reverse to it.

Now complications may arise when the number is odd length and when the new palindrome is of greater length than the current number.So for this we check if our new palindrome is less than the given number. If so than we start increasing our middle digit by 1 and mirroring it  to the other digits. If the middle digit is a 9 than we need to change it to zero and update the next digit by 1 or make it zero if it is a 9 until we reach a number that is not 9. Else we need to add 1 to the start of the number.The C code for the procedure is given below:

                cin >> str;
  s = str;
  int inc,dec;
  inc = s.size()/2;
  dec = inc;
  if(s.size()%2==0)
   dec--;
  for(int i=inc,j=dec;i<s.size() && j>=0;i++,j--)
   s[i] = s[j];
  while(s<=str && s.size()<=str.size()){
   int i=dec,j=inc;
   while((s[i]-'0')==9 && i>=0 && j<=s.size()){
    s[i] = s[j] = '0';
    i--;
    j++;
   }
   if(i<0){
    s = '1' + s;
    int l = s[s.size()-1] - '0';
    l++;
    s[s.size()-1] = (l+'0');
   }else{
    int l = s[i] - '0';
    l++;
    s[i]=s[j]=(l+'0');
   }
  }
  cout << s << endl;

Reverse Polish Notation : Expression Transformation

Tuesday 29 July 2014
Reverse Polish notation (RPN) is a mathematical notation in which every operator follows all of its operands, in contrast to Polish notation, which puts the operator in the prefix position. It is also known as postfix notation and is parenthesis-free as long as operator arities are fixed. The description "Polish" refers to the nationality of logician Jan Ɓukasiewicz, who invented (prefix) Polish notation in the 1920s.In computer science, postfix notation is often used in stack-based and concatenative programming languages. It is also common in dataflow and pipeline-based systems, including Unix pipelines.

The C code for converting an expression into RPN format as required in SPOJ problem 4 is done using one stack to store the members and one integer to denote the opening brackets. The function printRPN takes a string expression and prints the RPN  equivalent.

void printRPN(string s){
 stack<string> members;
 int opening_brackets = 0;
 for(int i=0;i<s.length();i++){
  if(s[i]==' ')continue;
  else
  if(s[i]=='(')opening_brackets++;
  else
  if(s[i]==')'){
   opening_brackets--;
   string op1 = members.top();members.pop();
   string op2 = members.top();members.pop();
   string op3 = members.top();members.pop();
   op3.append(op1);
   op3.append(op2);
   members.push(op3);
  }else
  members.push(string(1,s[i]));
 }
 cout << members.top() << endl;
}

Substring Matching Algorithms

Substring matching is an important part of any algorithmic problem. There are different complexities to consider about like the size of the string, the size of the pattern, the running time etc. Considering all these we list down some of the approaches which is used in solving the substring problem.

Naive Brute Force approach :

In the naive approach we iterate over all the elements of the text and start matching for each character of the pattern.If it doesnot match we advance the start of the match of the text by one character and again check for the presence of the pattern. Since for each character of the text we match the next characters for the pattern the worst case time complexity if n is the length of the pattern and m is the length of the text is O(mn). The code is mentioned below :

void naiveBruteForce(string a,string b){
 bool isMatched = true;
 int i=0;
 for(i=0;i<=a.length() - b.length();i++){
  isMatched = true;
   for(int j=0;j<b.length();j++){
    if(a[i+j] != b[j])
     isMatched = false;
   }
  if(isMatched)
   break;
 }
 cout << isMatched << " offset :" <<  i << endl;
}

Rabin Karp Algorithm :

In the Rabin Karp method we try to eliminate the two inner loop computation of the naive algorithm in which we try to match two strings. Instead of matching two strings we assign a value by using a hash of the characters. We precompute the hash of the pattern and we only check the if the hash of the substring of the text matches the pattern's hash value. Again problem will arise if the number of characters is big or the length of the string is big in which case we can use a modular hash function. But in this two strings may have the same value even if they do not match, thus the modulus M should be taken a large number. A sample code in which we have taken squares of the ascii value of the characters as a hash value is given below:

void rabinKarp(string a,string b){
 int hashsub = 0,tmp,tmp1,hash = 0;
 for(int i=0;i&ltb.length();i++){
  tmp = b[i];
  tmp1 = a[i];
  hashsub += tmp * tmp;
  hash += tmp1 * tmp1;
 }
 for(int i=b.length();i&lta.length();i++){
  if(hash==hashsub)
   cout << "offset :" << i - b.length() << endl;
  tmp = a[i - b.length()];
  tmp1 = a[i];
  hash -= (tmp * tmp);
  hash += (tmp1 * tmp1);
 }
}

Knuth-Morris-Pratt Algorithm:

In KMP algorithm we use the fact that if a substring match fails then we know by precomputing the pattern that we can certainly shift by a certain amount in which the substring wont match. The precomputing is done by finding the longest substring of the pattern that is a prefix as well as a suffix. This can be done in the following way- Consider a string in the pattern b1b2...bk...bj. Sup pose we know that the longest substring that is a prefix as well as a suffix is the substring upto k. Then F[j] = k, and if k+1th character is equal to the j+1th character then F[j+1] = F[j] + 1. Else there would be some other substring smaller than bk that would be initial and terminal substring then it would also be a border string of b1...bk. Hence if the above condition is false then we check for the string F[F[j]] for the initial and terminal and this check continues until we find a border or there is no border at all in which case we inialize it to  . The pseudocode is as follows:
Prefix-Compute-Function(Pattern):
F[1] = 0;
for j from 1 to m-1 do:
    i = F[j];
    while(bi+1 != bj+1 and i>0) i=F[i]; //reduce the search space
    if(i==0 and bi+1 != bj+1) F[j+1] = 0;
    else
    F[j+1] = i+1;

The C implimentation is given below :

int* KMP_Preprocess(string pattern){
 int *pre = (int *)malloc(sizeof(int)*pattern.length());
 memset(pre,0,pattern.length());
 for(int i=1;i<pattern.length();i++){
  pre[i] = pre[i-1];
  while(pattern[i] != pattern[pre[i]]){
   if(pre[i] == 0){
    pre[i] = -1;
    break;
   }else{
    pre[i] = pre[pre[i] - 1];
   }
  }
  pre[i] = pre[i] + 1;
 }
 return pre;
}

void KMP_Match(string a, string b){
 int *pre = KMP_Preprocess(b);
 for(int i=0,j=0;i<a.length();){
  while(a[i+j] == b[j]){
   ++j;
   if(j==b.length()){
    cout << "Match offset :" << i << endl;
    break;
   }
  }
  if(j>0){
   i+=(j-pre[j-1] > 1)?(j-pre[j-1]):1;
   j = pre[j-1];
  }else{
   ++i;
  }
 }
}
Copyright @ 2013 code-craft. Designed by Templateism | MyBloggerLab