Binary search implememtation in C Language

In previous post we have seen how we can search the list by using simple loop and process is called sequential search. This is useful when we have small lists. But in real world we encounter large lists having thousands or even millions of elements(data).

Iterating over such a large list using simple loop is inefficient in terms of time. Considering the large list having sorted elements we can employ binary search. Generally when storing the data itself if we stored them in sorted order makes our life simple at later part of time when we are retrieving data.

If you observe the name of search algorithm "Binary Search". It conveys we have two parts(Binary). The part of the list having the desired data and the part does not having the desired data.

The c code which explains the binary search is as follows:

int binarySearch(int* array, int size, int reqNum, bool *result )
{
    int startIdx;
    int endIdx;
    int midIdx;
   
    startIdx = 0;
    endIdx = size;
   
    while ( startIdx <= endIdx)
    {
        midIdx = ( startIdx + endIdx ) / 2 ;
        if (reqNum > array[midIdx])
        {
            startIdx = midIdx + 1;
        }
        else if (reqNum < array[midIdx])
        {
            endIdx = midIdx - 1;
        }
        else
        {
            startIdx = endIdx + 1;
        }
    }
    *result = ( reqNum == array[midIdx]);
    return midIdx+1;
}

The logic returns the position of the desired elements in the list. But if we dose not have the required data in the list then also the algorithm returns the 1. but before that we are comparing if the required number is present at the array[midIdx] if the number does not there we are passing the failure as the pointer to the calling function. By using that the calling function can determine weather the data is present in the list are not.

the calling function can be coded as

int main ()
{
    int a[10] = {1,2,120, 240, 256, 300,312, 440, 456, 512};
    bool result;
    int index = binarySearch(a,10, 0, &result );
    if (result)
    {
        printf("Required Number Present at %d position",index );
    }
    else
    {
        printf("Target not found");
    }
}

Sequential Search using Array

In day to today programming we face lot of situations where we need to find something in the stored data. Generally the data is organized as arrays or in any form grouped together. If we are adding data to the already existing group we generally tend to add new data at the end of the group.
This leads to unsorted data. Searching unsorted data is time consuming. We have to go one element by element to find the desired data. consider basic scenario where we have 10 numbers stored in an array and that is unsorted. If we want to find if the desired number is present in that array or not then we have to read each element and we have to compare that with the desired one. If we put all the above in form of algorithm:


read the element from array
compare the element with the desired one
if both are matching stop the search we have desired one in array
else continue till we get the desired one or we reach end of array.

int getIndex(int *data, int length, int num)
{
    int i;
    for ( i = 0; i < length; i++)
    {
        if ( data[i] == num )
        {
            return i;
        }
    }
    return length+1;
}

and the main function to use the algorithm is
int main ()
{
    int a[10] = {1,2,56,34,21,67,22,99,88,0};
    int index = getIndex(a,10,9);
    if (index < 10)
    {
        printf ("The desired element is at position %d",index+1);
    }
    else
    {
        printf ("There is no such element in Array");
    }
}
in the function getIndex we are returning the index of the element if the desired number is present in array. If the desired number is not present in array we are returning length+1 so that the code in main function knows that there is no number which is matching our requirement.

GCD of two number using C language

The gcd of two numbers is the largest number which divides the tow numbers with out leaving any reminder. gcd often known as greatest common factor (GCF), the highest common factor (HCF), and the greatest common measure (GCM).
In this post I will explain the calculation of GCD of tow numbers with Euclidean algorithm. This algorithm is recursive. So we can use recursion in any programming language which supports recursion to calculate GCD with Euclidean algorithm.
According to the algorithm the GCD of the two numbers will not change if the larger number is replaced with the difference of the small number and large number.
In each step of recursion we have to replace the large number with the difference of the small number and large number.
The implementation of the Euclidean algorithm for the problem is as simple as below

int calculateGCD (int num1 , int num2)
{
    if ( num2 == 0 )
    {
        return num1;
    }
    else if ( num1== 0 )
    {
        return num2;
    }
    return calculateGCD ( num2 , num1 % num2 );
}

in this algorithm we are returning the number if that is zero as a pre check. If both the numbers passed to the algorithm are non zeros then we have call the function itself till any one of the number becomes. in lase step when one of the number becomes zero we will return the number which is not zero to the previous step.

Create and write text to the word document table using Apache POI in Java

In previous posts I explained how we can use Apache POI to read the text from word documents. It is the time to dwell into the writing of word documents using Java. You may get doubt  why to write word documents from Java(we can directly use word to write). But in so  many scenarios we directly work with data bases and some times we have to take the reports from database for further processing.

The database nothing more than tables in an organised and inter linked manner for easy retrieval of data. We can store that data into xls or we can use word tables to store for further use.

In this post I will explain how to write the tables in word document, how to create new rows, cells and putting data in the cells.

We are writing means we need one output stream to write to the disk. Obviously FileOutputStream comes handy. we will create object for FileOutputStream. Do not forget to catch the exceptions otherwise wisely throw them JVM is there to take care. But is is not good always to throw the exceptions.

FileOutputStream fos = new FileOutputStream("")

The next step is to create object for the word document. This is pretty straight forward just create object of type XWPFDocument.

XWPFDocument doc = new XWPFDocument()

All the thing(data) what we are going to write into above object will be part of our final word document which will be available after the finishing of our program(Java).

The next thing we have to do is to create table in word document to write the data into the cell. There are three steps we have to do sequentially to write the data to the table are creating the table in the XWPFDocument object, creating  row in that table and creating cell in the row to put the text.

XWPFTable table = doc.createTable()
XWPFTableRow row = table.getRow(0)

You may wonder how we can get the row with out creating it. One thing I want to make sure is that the table which we created will have default row. Just we are sing it as the table header row where we will keep all our columns headings. Now we are headed toward creating the cell in the row but not the first one as I said the default first row already has one for us.

The next step is creating one more cell if we want this looks like

XWPFTableCell cell1 = row.createCell()

if we want to set the text we can use

cell1.setText("")

After that based on our demand we can create as many rows as we need just be creating the row in the XWPFDocument object. One thing we have to be clear is we have to create the cells in the very first row only after that there is no need. Because the cells will be create automatically for us in the newly created rows of the table.

We have to get those cells and need to put the text.

The code snippet which will get you going will be

fos = new FileOutputStream("D:/POI/tableTest.docx");
            doc = new XWPFDocument();
            XWPFTable table = doc.createTable();
            XWPFTableRow row = table.getRow(0);
            row.getCell(0).setText("Name");
            XWPFTableCell cell1 = row.createCell();
            cell1.setText("Age");
            XWPFTableCell cell2 = row.createCell();
            cell2.setText("UID");
            for (int rows = 0; rows < 2 ; rows++ )
            {
                row = table.createRow();
                for (XWPFTableCell cell : row.getTableCells())
                {
                    cell.setText(" ");
                }
            }
            doc.write(fos);
            fos.close();

Do not forget to write the document by suing the line
            doc.write(fos)
The argument is just the object of FileOutPutStream which we have create earlier. The good way to end the logic is just by closing the all opened connections especially streams.

Reading table from word document with multiple paras in cell with Apache POI

In previous post I explained about the reading of text from table having only one paragraph. But always this is not the case. Lot of documents daily we are processing has multiple paragraphs in cell. By using the method described in earlier we will get all the text from the cell. But we will miss the formatting of the paragraphs. If we want to get the individual paragraphs from the cell we can use the below line of code.

for ( XWPFParagraph para : cell.getParagraphs() )
{
}

The above for loop will give the one para at every iteration from the cell in the order they are typed in table cell.

The consolidated code to get all the text from the table with paragraphs is

fis = new FileInputStream("D:/POI/ex1.docx");
            doc = new XWPFDocument(fis);
            tables = doc.getTables();
            for ( XWPFTable table : tables )
            {
                for ( XWPFTableRow row : table.getRows() )
                {
                    for ( XWPFTableCell cell : row.getTableCells() )
                    {
                            for ( XWPFParagraph para : cell.getParagraphs() )
                            {
                                    System.out.println(para.getText());
                            }
                    }
                    System.out.println("");
                }
            }

Reading table data from word document with Apache POI frame work

In previous posts reading word document I explained how we can use POI frame work to read the plain text data from the word document. Always this is not the case some times we may encounter tables in the document.
POI frame work has the built in support to read the tables data. It is so nice that we can read the data row by row and cell by cell. Java collection framework made it so easy to iterate over the table. Irrespective of the number of tables in the word document we can process the word document.
It is so simple to write Java code for reading the tables data. we want to read the table from word document so we need one input stream to open the word document for us. The Java code to accomplish this will look like

FileInputStream fis = new FileInputStream("")

After getting the data stream we need to use this in POI frame work. Just get the word document object in Java code by creating the object of XWPFDocument by passing the object of FileInputStream as the argument of the XWPFDocument constructor.

We will get the object of the word document. The following LOC will do this

XWPFDocument doc = new XWPFDocument(fis)

The object supports lot of methods to work on word document. In this post I will explain how to use this object to get the data present in the table. It is so simple by using the getTables method on the XWPFDocument object we will get all the tables of the word document which we are loaded in FileInputStream. This implies that we need one collection to hold all the tables. In fact the getTables method will return the List of the tables. This look like

List<XWPFTable>  tables = doc.getTables()

After getting the list of tables it is easy for us to iterate through all the tables of the word document. You may get doubt the size of the tables in the document may vary then how we can iterate with simple loop. It is so easy we are no where hard coding the number of columns or the number of rows of the table.

Every table object has the methods to get the number of rows and columns of the table. We can use Java for all loop to achieve this easily. The code to iterate through the tables look like

for ( XWPFTable table : tables )
{
} 

The code inside the above for loop can use table(one table returned by the for loop from the list) as the object pointing the real table in word document. This table object has so many methods one is to get the number of rows of the table

for ( XWPFTableRow row : table.getRows() )
{
}

we can use row the local variable of the above for loop to get cell and in turn to get the data present in that cell.

for ( XWPFTableCell cell : row.getTableCells() )
{
   System.out.print(cell.getText());
}

The method getText will return the text data by removing any formatting of the text.
The following code snippet is useful for reading and printing the table data as table on the Java console.
fis = new FileInputStream("D:/POI/ex1.docx");
            doc = new XWPFDocument(fis);
            tables = doc.getTables();
            for ( XWPFTable table : tables )
            {
                for ( XWPFTableRow row : table.getRows() )
                {
                    for ( XWPFTableCell cell : row.getTableCells() )
                    {
                        System.out.print(cell.getText());
                        System.out.print("\t");
                    }
                    System.out.println("");
                }
            }
It looks like so simple but we have one problem in  this code that is the formatting of the data is lost. And the cell may contain multiple paragraphs and tables as well we will see how to get the data with out lose of formatting in the next post.

Reading documents containing Images with POI

In previous post on POI frame work I discussed on reading the word docs having only paragraphs having text. This is not very useful cause lot of documents will have formatting contains Images tables etc.
For  example consider document having images in between text paragraphs. Every object embedded inside the document can be accessed as the paragraph even Images. So these are also become part of paragraph. While accessing the document from the code some times we are not interested in images. by using following code we will get only the text containing in the paragraphs.

try
        {
            FileInputStream fis = new FileInputStream("");
            HWPFDocument doc = new HWPFDocument(fis);
            Range range = doc.getRange();
            int numOfParas = range.numParagraphs();
            for(int i = 0; i < numOfParas; i++)
            {
                Paragraph para = range.getParagraph(i);           
                if(!para.text().trim().equalsIgnoreCase(""))
                {
                    System.out.println(para.text());
                }
            }
        }
        catch(FileNotFoundException fnfe)
        {
            fnfe.printStackTrace();
        }
        catch(IOException ioe)
        {
            ioe.printStackTrace();
        }

This is same as the code used to read the simple word docs without any images. Just we added one condition while displaying the text. If the paragraph contains image only then there will not be any text if we run the .trim().equalsIgnoreCase("") on this paragraph text we will get Boolean true as result because there is not text.

Readind word document with Apache POI

Reading the files is very easy with Java. we can read any type of file. But each file has it's own formatting and the features. consider word document and the excel sheet each has it's own formatting. we can use buffered reader and any other type of readers available in java but these are not feasible while handling the documents containing lot of formatting.
We have sophisticated framework developed by Apache called POI to process the any type of document generated using MS office. Apache provides the ready made jars just we have to include them in our class path and we can use the functionality provide by them.
Following example provides the very basic functionality of reading the word document containing single paragraph single line.

public static void main(String[] args)
    {
        try
        {
            FileInputStream fis = new FileInputStream("C:/Practice/Reading.doc");
            HWPFDocument doc = new HWPFDocument(fis);
            Range range = doc.getRange();
            int numOfParas = range.numParagraphs();
            for(int i = 0; i < numOfParas; i++)
            {
                Paragraph para = range.getParagraph(i);
                System.out.println(para.text());
            }
        }
        catch(FileNotFoundException fnfe)
        {
            fnfe.printStackTrace();
        }
        catch(IOException ioe)
        {
            ioe.printStackTrace();
        }
    }

HWPFDocument is the wrapper containing all the data structures of the word document. The variable doc of type HWPFDocument points to the instance of the word document pointed by the HWPFDocument class. HWPFDocument takes the File or path to the word document as string. The variable range is of type Range contains all the data of the word document except the header and footer section. By using range we can read all the data present in the word document. The method numParagraphs employed on range gives the total number of paragraphs of the word document. getParagraph  method returns the paragraph of provided index.

Pulse Width Modulation with Microcontroller

Pulse width modulation is the type of modulation where we alter the duty cycle of the square wave. we vary the on period and the off period of the square wave to generate the variable duty cycle. This ultimately changes the average voltage output of the square wave.

we can simulate the above behaviour using micro controller programmed to alter the voltage of the output pin. For certain period of the time the output will be heigh and for some period it will be low causing square wave generation. we can alter the time for which the output is heigh this simulates the PWM behaviour.

The circuit has four switches each one will change the on period of the square wave. based on the closed switch on period will be changed in the micro controller. The code which does this as fallows:

#include <regx52.h>

#define OutPut P2_0

#define Sw1 P1_0

#define Sw2 P1_1

#define Sw3 P1_2

#define Sw4 P1_3

int Period = 0;

void delay1ms()

{                        int c=0;

while(c<1000)

            {

                          TMOD=0x01;

                          TH0=0xFC;

                          TL0=0x66;

                          TR0= 1;

                          while(!TF0);

                                    TR0=0;

                                    TF0=0;

                                     c++;

            }

}

void main()

{

int j,i;

Sw1 = 1;

Sw2 = 1;

Sw3 = 1;

Sw4 = 1;

OutPut = 0;

while(1)

{

  if(!Sw1)

  {

  Period = 1;

  }

  if(!Sw2)

  {

  Period = 2;

  }

  if(!Sw3)

  {

Period = 3;

  }

  if(!Sw4)

  {

Period = 4;

  }

  OutPut = 1;

  for(i=0;i<Period;i++)

  {

  delay1ms();

  }

  OutPut = 0;

  for(j=0;j<4-Period;j++)

  {

  delay1ms();

  }

}

}

Total time period of the square wave is 4 seconds. Timer is used to generate the 1 ms delay. 

Extract frame from video when user presses a key in Open CV

Capturing the frames from video using Open CV is very simple. Just we need to use cvSaveImage method from Open CV library. But some times we need to capture the images interactively like when the user presses a key. For doing this we can use the function kbhit(). this function returns non zero values when there is something in the keyboard buffer. So by using this we can interactively extract the frames.

By using the fallowing code we can accomplish this.

#include "stdafx.h"
#include "cv.h"
#include "highgui.h"
#include <conio.h>

void main()
{
IplImage * img;
CvCapture * v;
v = cvCreateFileCapture("E:/v.mp4");
int k = 0;
char text[10];
while(true)
{
if(_kbhit())
{
sprintf(text,"%s%d%s","E:/Image",k,".jpeg");
cvSaveImage(text,img);
getch();
}
else
{
img= cvQueryFrame(v);
cvWaitKey(0);
k++;
}
}
_getch();
}

we have one while loop which continuously reads the frames from the video. The if block will be executed when the user presses a key from keyboard else else block gets executed. In else block we are extracting the frames from the video we have one delay loop as well else the the computer reads all the frames one by one with in fraction of seconds.

To change the saved image file name every time we are using char buffor. By using sprintf we are changing the file name. cvSaveImage saves the image on the specifed path supplied as first argument and the image to be saved as second argument. getch() is used to clear the buffor else the if block executed continuously.

RGB to YUV format conversion using Open CV and C Language

You may think why we need to convert the image from one format to another format. There are lot of advantages if we convert the format for transmission as well as for display purpose. Some times processing of the one format of images i s easy compared to another. Generally images are processed by algorithms in YUV domain and then converted to RGB domain for Display purpose. While capturing the images camera uses RGB format b ut for storing we use YUV format for compression. When we need to display them we will again convert them to the RGB format. Generally YUV format images require the less band width compared to the RGB. Generally color correction is done in the RGB color space and contrast enhancement is done in the YUV color space. Y component used for carrying the brightness of the image and remaining two components are used for the color representation.

Fallowing code explains how we can achieve the above things:

#include "stdafx.h" 
#include "cv.h"
#include "highgui.h"
#include <conio.h>

void main()
{
    IplImage *img=cvLoadImage("E:/test.jpg");
    IplImage *Dimg=cvCreateImage(cvSize(img->width,img->height),img->depth,img->nChannels);
    //VUY
    IplImage *Y=cvCreateImage(cvSize(img->width,img->height),img->depth,3);
    IplImage *U=cvCreateImage(cvSize(img->width,img->height),img->depth,3);
    IplImage *V=cvCreateImage(cvSize(img->width,img->height),img->depth,3);

    for(int i=0;i<img->width*img->height*3;i+=3)
    {
        int y=0.257*img->imageData[i+2]+0.504*img->imageData[i+1]+0.098*img->imageData[i]+16;
        int u=-0.148*img->imageData[i+2]-0.291*img->imageData[i+1]+0.439*img->imageData[i]+128;
        int v=img->imageData[i+2]*0.439-0.368*img->imageData[i+1]-0.071*img->imageData[i]+128;
        Dimg->imageData[i]=(v<255||v>0)?v:(v>255?255:0);
        Dimg->imageData[i+1]=(u<255||u>0)?u:(u>255?255:0);
        Dimg->imageData[i+2]=(y<255||y>0)?y:(y>255?255:0);

        Y->imageData[i+2]=Dimg->imageData[i+2];
        U->imageData[i+1]=Dimg->imageData[i+1];
        V->imageData[i]=Dimg->imageData[i];
    }

    cvNamedWindow("Y",0);
    cvResizeWindow("Y",300,300);
    cvNamedWindow("U",0);
    cvResizeWindow("U",300,300);
    cvNamedWindow("V",0);
    cvResizeWindow("V",300,300);
    cvShowImage("Y",Y);
    cvShowImage("U",U);
    cvShowImage("V",V);
    cvWaitKey(0);
    _getch();
}

While calculating the YUV components some times we will encounter the under flow as well as over flow. so we have to make sure that the code does not breaks while running. So we have to tap all these things in our code.
Above code loads the image in to the code using open cv. Then the individual channels are extracted and then they are converted to the YUV domain and stored in the newly created image. To get the difference between the YUV components we represented the each channel separately in separate windows.