Saturday, April 23, 2011

Add node at the end of linked list

Given a singly linked list and node to insert, insert given node at the end of link list.

Below is the code to add node at the end of the linked list:

Here node is of form:

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

Node* AddAtEnd(Node* head, int value)
{
if(head == NULL)
{
head = new Node;
head->next=NULL;
head->data= value;
return head;     
}
Node* node = head;
while( node->next!=NULL)
node = node->next;

Node* tmp = new Node;
tmp->next= NULL;
tmp->data=value;
node->next = tmp;
return head;
}

Wednesday, April 6, 2011

Simple File Enumerator

Here I will explain the design of simple file enumerator program, which enumerates file under given directory.


The program uses FindFirstFile and FindNextFile functions to complete the task. You can read the information about these functions on MSDN.  


The class will accept the Directory path as input and will return the vector containing  file under directory, along with each file size. 


As we will be returning the file name, file size and file path, we will declare a struct which contains this information.



typedef struct
{
std::wstring m_strFilePath;
std::wstring m_strFileName;
DWORD m_nFileSizeHigh;
DWORD m_nFileSizeLow;
} FileInfo;

We will be returning the vector of this struct. Lets declare the typedef for our vector.

typedef std::vector<FileInfo> FileInfo_Vector;

Now we should define the class structure, I mean what are the methods and members this class will contain.



class DirectoryEnumerator
{
public:
     DirectoryEnumerator(const std::wstring & rkstrDirectoryPath);
     ~DirectoryEnumerator();
     HRESULT Init(DWORD dwDirDepth = -1 );
     void GetFilesInfo(FileInfo_Vector& rfileInfoVector);
 


private:
     void EnumerateDir(FileInfo_Vector& rfileInfoVector,
                       const std::wstring& rkstrFolderPath,
                       DWORD dwDirSearchDepth );


private:
     std::wstring  m_strRootDirectoryPath;
     DWORD         m_dwDirSearchDepth;
};

Here Init will get the extra input that is search depth in directory. If you want to search in all the subdirectories the input to Init will be -1, else a depth value. 

Init will check first if the given directory is exist and can be queried, if yes then it will return OK, else it will fail.

Once Init is successful, you can query GetFilesInfo, which will accept reference to vector and will update that vector with file information under directory.


EnumerateDir is our internal function which enumerate the directory and will fetch the required data.


As base structure of class ready, lets move towards actual code.



DirectoryEnumerator::DirectoryEnumerator(const std::wstring & rkstrDirectoryPath)
:m_strRootDirectoryPath(rkstrDirectoryPath)
,m_dwDirSearchDepth(-1)
{
}


DirectoryEnumerator::~DirectoryEnumerator()
{
}


HRESULT DirectoryEnumerator::Init( DWORD dwDirDepth, /* = -1 */ )
{
m_dwDirSearchDepth  = dwDirDepth;

if( m_dwDirSearchDepth == 0 || m_dwDirSearchDepth < -1)
m_dwDirSearchDepth = 1;


std::wstring strRootDir(m_strRootDirectoryPath);


size_t found = strRootDir.find(L"\\*");
if(found == std::wstring::npos)
strRootDir += L"\\*";


WIN32_FIND_DATA FindFileDataStruct;
HANDLE hFind = FindFirstFile(strRootDir.c_str(), &FindFileDataStruct);
if(hFind == INVALID_HANDLE_VALUE)
{


HRESULT  hr = ::GetLastError();
::FindClose(hFind);
return hr ;
}


::FindClose(hFind);
return S_OK;
}



void DirectoryEnumerator::EnumerateDir( FileInfo_Vector& rfileInfoVector, const std::wstring& rkstrFolderPath, DWORD dwDirSearchDepth )
{
std::vector<std::wstring>  SubDirectoryVector;
std::wstring strRootDir(rkstrFolderPath);


size_t found = strRootDir.find(L"\\*");
if(found == std::wstring::npos)
strRootDir += L"\\*";


WIN32_FIND_DATA FindFileDataStruct;
HANDLE hFind = FindFirstFile(strRootDir.c_str(), &FindFileDataStruct);
if(hFind == INVALID_HANDLE_VALUE)
{
::FindClose(hFind);
return;
}


try
{
do
{
BOOL BReturnValue= ::FindNextFile(hFind, &FindFileDataStruct);
if( 0 == BReturnValue )
{
DWORD dwError = ::GetLastError();
if(ERROR_NO_MORE_FILES == dwError)
{
//No more Files. Enumeration completed
}
else
{
//Error occured while enumerating directory
}
break;
}


if (FindFileDataStruct.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
{
if( !(m_dwDirSearchDepth == 1))
SubDirectoryVector.push_back (rkstrFolderPath + L"\\" + FindFileDataStruct.cFileName);
}
else
{
FileInfo fileInfoStruct;
fileInfoStruct.m_strFilePath = rkstrFolderPath;
fileInfoStruct.m_strFileName = FindFileDataStruct.cFileName;
fileInfoStruct.m_nFileSizeHigh = FindFileDataStruct.nFileSizeHigh;
fileInfoStruct.m_nFileSizeLow = FindFileDataStruct.nFileSizeLow;


rfileInfoVector.push_back(fileInfoStruct);
}


}while(true);
}
catch(...)
{
//Exception occured while enumeration.
}
::FindClose(hFind);


if(SubDirectoryVector.empty())
return;


if( dwDirSearchDepth == 0 )
return;


if( dwDirSearchDepth != -1)
dwDirSearchDepth -= 1;


std::vector<std::wstring>::const_iterator it = SubDirectoryVector.begin();

it++; //first directory will be always ".."


for(;it != SubDirectoryVector.end(); it++)
{
EnumerateDir(rfileInfoVector, *it, dwDirSearchDepth);
}
}

Wednesday, March 9, 2011

Code: Remove duplicate characters from string

Earlier we have seen code for checking for duplicates. We are now going to extend that code to remove the duplicates from the string.

void RemoveDuplicates(char* pchStringofDuplicates)
{
      if( NULL == pchStringofDuplicates || NULL == (pchStringofDuplicates +1))
            return ;

      char* pchPointToEnd, *pchPointToStart = pchStringofDuplicates++;
      pchPointToEnd = pchStringofDuplicates;

      while(*pchPointToEnd != NULL)
      {
            char* pchComparator = pchPointToStart;
            while(pchComparator != pchPointToEnd)
            {
                  if(*pchComparator == *pchPointToEnd)
                  {
                        break;
                  }
                  pchComparator++;
            }
            if(pchComparator == pchPointToEnd)
            {
                  *pchStringofDuplicates++ = *pchComparator;
            }
            pchPointToEnd++;
      }
      *pchStringofDuplicates = *pchPointToEnd;
}

Considering second character as tail(at first time), we will compare every character from start to tail, with tail. If we don't found match then we will add the tail in the same string. Do this till end of string.

Note: In C++ we are passing the char array to this function. If you try passing char* string you may get Access Violation error.  

Monday, March 7, 2011

Code: Make first character of string to upper case


Here the problem is just simple, we have to make uppercase to the first character of every input string. 


First Method: In this method we are going to consider that the string is having only ASCII characters. Then we will check first if the character fall between a to z, if yes then we will convert it to upper case by just adding the difference as shown below.

void MakeFirstCharUpper(char* pchInputString)
{
int aToInt = (int)'a';
int zToInt = (int)'z';
int AtoInt = (int)'A';


if(pchInputString == NULL)
return ;


int firstChar = (int)*pchInputString;
if(firstChar  <= zToInt && firstChar  >= aToInt )
{
*pchInputString = (char)(AtoInt + (firstChar  - aToInt));
}
}


Second Method: 
This will require when your string contains UNICODE characters. Here we will make copy of the original string, we will make that string to upper case, then we will only copy the first character of upper case string to original string.



void MakeFirstCharUpperUNICODEVersion(char* pchInputString)
{
if( NULL == pchInputString)
return;


if(strlen(pchInputString) == 1)
{
pchInputString = strupr(pchInputString);
return;
}


char* strPartI = new char(strlen(pchInputString));
strncpy(strPartI, pchInputString, strlen(pchInputString));


strPartI = strupr(strPartI);


*pchInputString = *strPartI;
}

Thursday, March 3, 2011

Check if duplicate characters present in string

The problem we are discussing here is you have to return true if string specified contain at least one duplicate character. First we will be trying this without using the additional buffer. 


Idea is just simple: Try comparing each character from second character to end, with every character from start to that character. Don't try to compare from first character, otherwise  you will find the first match at the start itself.




bool IsDuplicatesCharPresent(char* pchStringToVerify)
{
if(pchStringToVerify == NULL)
return false;


char *pchStringStart = pchStringToVerify++;


while(pchStringToVerify != NULL)
{
char* pchComparator = pchStringStart;
while(pchComparator != pchStringToVerify)
{
if(*pchComparator == *pchStringToVerify)
{
return true;
}
pchComparator++;
}
pchStringToVerify++;
}
return false;
}




This can also be done using additional buffer, but your additional buffer may vary using as per the string character set. For example suppose if you are sure of having only ASCII characters then you will require buffer of size 256 length only, as shown below.



bool IsDuplicatesCharPresent(char* pchStringToVerify)
{
if(pchStringToVerify == NULL || (pchStringToVerify + 1) == NULL)
return false;
bool bArray[256] = {false};


while(*pchStringToVerify != NULL)
{
if(true == bArray[ (int)*pchStringToVerify ] )
return true;
else
bArray[ (int)*pchStringToVerify ] = true;
pchStringToVerify++;
}


return false;
}


This code is written considering the string is C style string, i.e. terminating with NULL. 

Friday, February 25, 2011

C++ Code for String Reverse

Here is a code for a program which does task of reversing the input string.



void StringReverse(char* pchStringToReverse)
{
        //if string is empty or having one character no need to reverse.
if(pchStringToReverse == NULL || (pcStringToReverse +1 ) == NULL) 
{
return;
}             

char* pchPointToLast = pchStringToReverse;

while(pchPointToLast)
{
pchPointToLast++;
}

pchPointToLast--;

while(pchStringToReverse < pchPointToLast)
{
     Char chTempStorage = *pchStringToReverse;
     *pchStringToReverse++  = *pchPointToLast;
     *pchPointToLast-- = chTempStorage; 
}
}

This code is written considering the string is C style string, i.e. terminating with NULL. If your string is not terminating with null then you might be need to replace the terminating conditions of while loops.

Unit Test Cases for above function:
  1. Empty String.
  2. String with only one character.
  3. String with even number of characters.
  4. String with odd number of characters.
There is one other way of doing this - its using recursion. But using recursion you can only print the string not store the string(I am not 100% sure about this).

void DisplayReverseString( char* pchStringToReverse)
{
if(*pchStringToReverse == NULL)
{
return;
}
else
{
DisplayReverseString(++pchStringToReverse);
cout<<*(pchStringToReverse -1 );
}
}

Please share your comments if any on the code or if you have any suggestions.