Program for printing pemutations and combinations.

Description:
The below program prints permutation and combinations of a given string.

#include <iostream>
#include <string>

#include <stdlib.h>
#include <string.h>

using namespace std;
/*
 *  give all combinations of (abcd)
 *  {
 *   a + give all combinations of (bcd)
 *   b + give all combination of  (acd)
 *   c + give all combinations of (bad)
 *   d + give all combinations of (cba)
 *  }
 *
 */
void printPermutations(char output[], string input, int index, int searchindex, int r)
{

 
  if(1 == r)
  {
    for(int j = searchindex; j < input.length(); j++)
    {
       output[index] = input[j];
       cout << output << endl;
    }
    return;
  }

  for(int i = searchindex; i < input.length(); i++)
  {
    output[index] = input[searchindex];

     printPermutations(output, input, index + 1, searchindex + 1, r -1);

     input[searchindex] = input[i+1];
    input[i+1] = output[index];

  }
/*
 *                          abcdef
 *                         a  b c d
 *                      ab ac ad ae bc bd be cd ce de
 *      abc abd abe abf acd ace acf ade adf aef bcd bce bcf bde bdf bef cde cdf cef def
 *
 *
 *
 */
void printCombinations(char output[], string& input, int index, int searchindex,int r)
{

   //cout << index << "-" << searchindex << "-" << n << "-" << r << endl;

   if(1 == r)
   {
     for(int i = searchindex; i < input.length(); i++)
     {
       output[index] = input[i];
       cout << endl << output << " ";
     }
     return;
   }
   for(int j = searchindex; j+r <= input.length() ; j++)  // j < n
   {
     output[index] = input[j];
     printCombinations(output, input, index+1, j+1, r-1);
   }
}

int main(int argc, char** argv)
{
  int n,r;

  string input;

  cout << "Enter string:" << endl;

  cin >> input;

  cout << "How many you want to choose:" << endl;

  cin >> r;
  n = input.length();

  if(n < r)
  {
    cerr << "Invalid input" << endl;
    exit(1);
  }
  else if(n == r)
  {
    cout << "Possible combinations:" << endl << input << endl;
  }
  else
  {
   char* output = new char[r + 1];
   output[r] = '\0';

   cout << "Combinations:" << endl;

   printCombinations(output, input, 0, 0, r);

  }

   char* output = new char[n + 1];

   output[n] = '\0';
   cout << "Permutations:" << endl;
   printPermutations(output, input, 0, 0, r);

  exit(0);
}





Sample Ouput:

[root@localhost mytrials]# ./a.out
Enter string:
12345
How many you want to choose:
2
Combinations:

12
13
14
15
23
24
25
34
35
45 Permutations:
12
13
14
15
21
23
24
25
31
32
34
35
41
42
43
45
51
52
53
54
 

Boost Thread Local Storage Example

Description: The below demonstrates the usage of thread local storages. It uses boost's implementation of thread local storage. The program creates mulitple thread which sends mulitple HTTP requests using libcurl.  In order for each thread to use a single connection to send HTTP requests, each thread should have a single CURL handle. Each thread creates his own handle in his local storage.

Progaram:

#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <curl/curl.h>
#include <boost/thread/tss.hpp>
#include <iostream>

using namespace std;

class HTTPHandle
{
  private:
    CURL* curl;

  public:

    HTTPHandle()
    {
      cout << "Creating curl easy handle" << endl;
      curl = curl_easy_init();
    }

    CURL* getHandle()
    {
       return curl;
    }

    ~HTTPHandle()
    {
      cout << "Cleaning up easy handle" << endl;
      curl_easy_cleanup(curl);
    }
};

void destroyHttpHandle(HTTPHandle* ptr)
{
  delete ptr;
}
void makeRequest()
{

 //We cannote directly create instance of  CURL since it is defined as 'typedef CURL void;'
  static boost::thread_specific_ptr<HTTPHandle> instance(destroyHttpHandle);
  // Create new HTTPHandle object if not already created one for this thread
  if(! instance.get())
  {
    instance.reset(new HTTPHandle);
  }

  CURL* curl = instance->getHandle();

  CURLcode res;

  if(curl) {
    curl_easy_setopt(curl, CURLOPT_URL, "http://10.10.0.1");
    // example.com is redirected, so we tell libcurl to follow redirection
    curl_easy_setopt(curl, CURLOPT_FOLLOWLOCATION, 1L);

    // Perform the request, res will get the return code
    res = curl_easy_perform(curl);
    // Check for errors
    if(res != CURLE_OK)
      cerr << "curl_easy_perform() failed:" << curl_easy_strerror(res) << endl;
  }
}

// Starting point of thread. Makes two HTTP request
void* thread_func(void* arg)
{
  for(int i = 1; i <= 2; i++)
  {
    makeRequest();
  }

  pthread_exit(NULL);
}

int main(void)
{
  pthread_t thread1, thread2;

  cout << "Global curl init." << endl;

  //initialize libcurl
  curl_global_init(CURL_GLOBAL_ALL);


  //Start two threads.

  pthread_create(&thread1, NULL, thread_func, NULL);

  pthread_create(&thread2, NULL, thread_func, NULL);

  // Wait for two threads to finish
  pthread_join(thread1, NULL);
  pthread_join(thread2, NULL);

  // Two threads completed. Each would have made two HTTP requests. No. of connection to 10.10.0.1 would be only two.
  // Since each thread creates only one curl handle. Check this using 'netstat -nap | grep 10.10.0.1'

  cout << "Check output of 'netstat -nap | grep 10.10.0.1'" << endl;

  sleep(5);

  cout << "Global curl cleanup." << endl;
  // global libcurl cleanup
  curl_global_cleanup();

}

Output:

Global curl init.
Creating curl easy handle
Creating curl easy handle
Cleaning up easy handle

Cleaning up easy handle

Check output of 'netstat -nap | grep 10.10.0.1'
Global curl cleanup.
 

[root@localhost curl]# netstat -nap | grep 10.223.3.131
tcp        0      0 10.223.3.171:45511          10.10.0.1:80             TIME_WAIT   -
tcp        0      0 10.223.3.171:45512          10.10.0.1:80             TIME_WAIT   -
 

Extracting formatted input using stringstream

Description: The following program shows how to extract formatted input from a stringstream object.


#include <iostream>
#include <fstream>
#include <sstream>

/*
  Extracting formatted input using stringstream >> operator.

  While extracting input, if there are any errors it could set eofbit, badbit or failbit in its internal error state falgs.

  Then it checks its exception mask to decide wheter to throw an exception or not.

  For example if failbit is set in exception mask and  failbit was set during extraction then >> operation would

  throw an ios_base::failure exception.
*/

using namespace std;
void getexceptionmask(const stringstream& ss)
{

ios_base::iostate exceptionmask = ss.exceptions();


if(exceptionmask & ifstream::badbit)
{
cout << "badbit is set. If an operation on sstream causes this bit to be set, an exception of type ios_base::failure would be thrown.\n" ;
}

if(exceptionmask & ifstream::failbit)
{
cout << "failbit is set. If an operation on sstream causes this bit to be set, an exception of type ios_base::failure would be thrown.\n" ;
}
}

void checkerrorstate(const stringstream& ss)
{

if(ss.bad())
{
cout << "Bad bit is set. We failed to read an integer" << endl;
}

if(ss.fail())
{
cout << "Fail bit or Bad bit is set. We failed to read an integer" << endl;
}
}

int main(int argc, char** argv)
{

stringstream ss;

cout << "Printing the default exception mask." << endl;

getexceptionmask(ss);

cout << "Printing after setting badbit and failbit exception mask." << endl;

ss.exceptions(ifstream::badbit | ifstream::failbit);

getexceptionmask(ss);

cout << "Printing after clearing the exception mask." << endl;

/*  
*if exception mask  has only goodbit (which is zero) streams  do not throw exceptions due to error state flags being set
*/
ss.exceptions(ifstream::goodbit);

getexceptionmask(ss);

int n;

cout << "Trying to read an integer when the stream is empty." << endl;

ss >> n;

cout << "Checking if any of the error bits were set." << endl;

checkerrorstate(ss);

/*
* clearing the errot state.
*/

ss.clear();

cout << "Printing exception mask after setting fail bit." << endl;

ss.exceptions(ifstream::failbit);

getexceptionmask(ss);

cout << "Now again trying to read an integer. We should get an exception now." << endl;

ss >> n;

}

Output:

Printing the default exception mask.
Printing after setting badbit and failbit exception mask.
badbit is set. If an operation on sstream causes this bit to be set, an exception of type ios_base::failure would be thrown.
failbit is set. If an operation on sstream causes this bit to be set, an exception of type ios_base::failure would be thrown.
Printing after clearing the exception mask.
Trying to read an integer when the stream is empty.
Checking if any of the error bits were set.
Fail bit or Bad bit is set. We failed to read an integer
Printing exception mask after setting fail bit.
failbit is set. If an operation on sstream causes this bit to be set, an exception of type ios_base::failure would be thrown.
Now again trying to read an integer. We should get an exception now.
terminate called after throwing an instance of 'std::ios_base::failure'
  what():  basic_ios::clear

Aborted

A ReadWrite implementation with preference to waiting writers.

Description:  Below is an implementation of ReadWrite using Mutex and Condition Variables with preference to waiting writers. Before a read lock is given, we check if there are any writers waiting to get write lock. Similary, when a lock is released, if a writer is waiting to get the lock , preference is given to them over readers.

RwLock.h (Header File)

#include <pthread.h>


class RwLock
{

    //nreaders = 0 , indicates no. reader/writer exists.

    //nreaders > 0, indicates one or more read lock exists.

    //nreaders=-1, indicates a write lock exists.

    int nreaders;

    int nwaitwriters;
   
    pthread_mutex_t rw_mutex;

    pthread_cond_t rw_condreader;
   
    pthread_cond_t rw_condwriter;

    public:

    RwLock();

    void getReadLock();

    void getWriteLock();

    void unLock();

    ~RwLock();

       
};

RwLock.C (Implementation)

#include "RwLock.h"

RwLock :: RwLock()
{
    nreaders = 0;

    nwaitwriters = 0;

    pthread_mutex_init(&rw_mutex, NULL);   

    pthread_cond_init(&rw_condreader, NULL);

    pthread_cond_init(&rw_condwriter, NULL);
}

void RwLock :: getReadLock()
{
    //Obtain Lock.
    pthread_mutex_lock(&rw_mutex);

    //If  a WRITER exists(nreaders = -1)wait for signal from writer.
    while(-1 == nreaders || 0 < nwaitwriters)
    {
        pthread_cond_wait(&rw_condwriter, &rw_mutex);
    }

    //increment no. of readers
    nreaders++;

    pthread_mutex_unlock(&rw_mutex);       
}


void RwLock :: getWriteLock()
{
    //Obtain Lock
    pthread_mutex_lock(&rw_mutex);

    //if nreader is != 0 it means either a reader or writer is present. wait for signal from reader/writer (do it in a loop)
    while(0 != nreaders)
    {
        //Increment no. of waiting writers.
        nwaitwriters++;

        pthread_cond_wait(&rw_condreader, &rw_mutex);
       
        //Decrement no. of waiting writers.
        nwaitwriters--;
       
    }

    //set nreader = -1 indicating a writer is present.
    nreaders = -1;

    //unlock the mutex.
    pthread_mutex_unlock(&rw_mutex);
}

void RwLock :: unLock()
{
    //Obtain Lock
    pthread_mutex_lock(&rw_mutex);

    if(0 < nreaders)
    {
        //one of the readers is done. decrement readers count.
        nreaders--;

        if(0 == nreaders)
        {
            //last reader is done.

            if(0 < nwaitwriters)
            {
                //if a writer is waiting
                pthread_cond_signal(&rw_condreader);
            }
        }
    }
    else if(-1 == nreaders)
    {
        //a writer is done. set nreaders to 0 indicating no reader/writer exists.
        nreaders = 0;

        if(0 < nwaitwriters)
        {
            //if a writer is waiting.
            pthread_cond_signal(&rw_condreader);
        }
        else
        {           
            //broadcast to any waiting readers.
            pthread_cond_broadcast(&rw_condwriter);
        }
    }

    pthread_mutex_unlock(&rw_mutex);
}

RwLock :: ~RwLock()
{
    //Destroy condition variable and mutex.
    pthread_mutex_destroy(&rw_mutex);

    pthread_cond_destroy(&rw_condreader);

    pthread_cond_destroy(&rw_condwriter);
}

Implementation of readwrite lock using mutex and condition variables.

Description: Below is an implementation of readwrite lock using mutex and condition variables. Note that, the implementation does not give any preference to waiting writers.

RwLock.h (Header File)

#include <pthread.h>
 

class RwLock
{

    //nreaders = 0 , indicates no. reader/writer exists.

    //nreaders > 0, indicates one or more read lock exists.

    //nreaders=-1, indicates a write lock exists.

    int nreaders;
   
    pthread_mutex_t rw_mutex;

    pthread_cond_t rw_cond;

    public:

    RwLock();

    void getReadLock();

    void getWriteLock();

    void unLock();

    ~RwLock();
       
};

RwLock.C (Implementation of our  ReadWrite Lock)

#include "RwLock.h"

RwLock :: RwLock()
{
    nreaders = 0;

   

    // Initialize mutex and condition variable.
    pthread_mutex_init(&rw_mutex, NULL);   

    pthread_cond_init(&rw_cond, NULL);
}

void RwLock :: getReadLock()
{
    //Obtain Lock.
    pthread_mutex_lock(&rw_mutex);

    // If  a WRITER exists(nreaders = -1)wait for signal from writer.
    while(-1 == nreaders)
    {
        pthread_cond_wait(&rw_cond, &rw_mutex);
    }

    // Increment no. of reader
    nreaders++;

    //Unlock the mutex.
    pthread_mutex_unlock(&rw_mutex);       
}


void RwLock :: getWriteLock()
{
    //Obtain Lock
    pthread_mutex_lock(&rw_mutex);

    // If nreader is != 0 it means either a reader or writer is present. wait for signal from reader/writer (do it in a loop)
    while(0 != nreaders)
    {
        pthread_cond_wait(&rw_cond, &rw_mutex);
    }

    // Set nreader = -1 indicating a writer is present.
    nreaders = -1;

    // Unlock the mutex.
    pthread_mutex_unlock(&rw_mutex);
}

void RwLock :: unLock()
{
    // Obtain Lock.
    pthread_mutex_lock(&rw_mutex);

    if(0 < nreaders)
    {
        // One of the readers is done. decrement readers count.
        nreaders--;

        if(0 == nreaders)
        {
            // Last reader is done.
            pthread_cond_broadcast(&rw_cond);
        }
    }
    else if(-1 == nreaders)
    {
        // A writer is done. set nreaders to 0 indicating no reader/writer exists.
        nreaders = 0;
        pthread_cond_broadcast(&rw_cond);
    }

    // Unlock the mutex.
    pthread_mutex_unlock(&rw_mutex);
}

RwLock :: ~RwLock()
{
    // Destroy condition variable and mutex.
    pthread_mutex_destroy(&rw_mutex);

    pthread_cond_destroy(&rw_cond);
}

Below is a sample program that uses this implementation and output obtained.

#include<unistd.h>
#include<pthread.h>
#include<stdlib.h>
#include<iostream>

#include "RwLock.h"

using namespace std;

RwLock rwlock;

void* reader(void* arg)
{
    cout << "Obtaining read lock." << endl;

    rwlock.getReadLock();
   
    cout << "Obtained read lock." << endl;

    sleep(5);

    cout << "Releasing read lock." << endl;

    rwlock.unLock();

    cout << "Released read lock." << endl;   
}


void* writer(void* arg)
{
    cout << "Obtaining write lock." << endl;

    rwlock.getWriteLock();
   
    cout << "Obtained write lock." << endl;

    sleep(4);

    cout << "Releasing write lock." << endl;

    rwlock.unLock();

    cout << "Released write lock." << endl;   
}

int main(int argc, char** argv)
{
    pthread_t r1,r2,r3,w1,w2;

    int res;

    cout << endl;   

    res = pthread_create(&r1, NULL, reader, NULL);

    if(0 != res)
    {
        cout << "Failed to start thread." << endl;
        exit(1);
    }
           
    res = pthread_create(&r2, NULL, reader, NULL);

    if(0 != res)
    {
        cout << "Failed to start thread." << endl;
        exit(1);
    }           

    sleep(1);

    res = pthread_create(&w1, NULL, writer, NULL);

    if(0 != res)
    {
        cout << "Failed to start thread." << endl;
        exit(1);
    }   

    res = pthread_create(&w2, NULL, writer, NULL);

    if(0 != res)
    {
        cout << "Failed to start thread." << endl;
        exit(1);
    }   
    pthread_exit(NULL);       
}

Output:

Obtaining read lock.
Obtained read lock. 
Obtaining read lock.
Obtained read lock.            /*Two read locks obtained*/
Obtaining write lock.
Obtaining write lock.         /*Two threads waiting for write lock*/
Releasing read lock.
Released read lock.
Releasing read lock.
Released read lock.         /*Two read locks are released*/
Obtained write lock.       
Releasing write lock.
Released write lock.       /*A thread first gets write lock and releases it*/  
Obtained write lock.      /*Second thread gets the write lock*/
Releasing write lock.
Released write lock.

MinHeap implementation.

Description:  The below program is an implementation of MinHeap. While creating the MinHeap, youneed to specify the max. no of elements it can hold. It provides two operations insert() and getMinimum().


HeaderFile:

#include <exception>

using namespace std;

#define HEAP_EMPTY 1

#define HEAP_FULL 2

class MinHeapException : public exception
{
    private:
    int code;

    public:
    MinHeapException(int n) : code(n)
    {

    }

    const char* what() const throw()
    {
        switch(code)
        {
            case HEAP_EMPTY:
                return "Heap is empty.";

            case HEAP_FULL:
                return "Heap is full.";
        }
    }   
};


class MinHeap
{
    private:
   
    const int capacity;
    int size;
    int* ptr;

    public:

    MinHeap(int n);
       
    void insert(int n) throw(MinHeapException);

    int getMinimum() throw(MinHeapException);

    void display();

    ~MinHeap();   
};

Implementation of our MinHeap:

#include "MinHeap.h"
#include <iostream>

using namespace std;

MinHeap :: MinHeap(int n) : capacity(n), size(0), ptr(new int[n+1])
{
       
}


void MinHeap :: insert(int n) throw(MinHeapException)
{
    /*
     * If the heap is already full, throw a exception.
     */   
    if(size == capacity)
    {
        throw MinHeapException(HEAP_FULL);
    }

    int hole;

    /*Increment the size of heap*/
    size++;

     /*The hole points  to the last position.
     *Move up the hole, still we get suitable position. i.e the parent of the hole
     *must be greater than the new no. that we want to insert in the hole.
     */    for(hole = size ; hole > 1 && ptr[hole/2] > n; hole = hole/2)
    {
        ptr[hole] = ptr[hole/2];
    }

    ptr[hole] = n;
}


int MinHeap :: getMinimum() throw(MinHeapException)
{

    /*
     *If the heap is empty throw an exception.
     */        if(0 == size)
    {
        throw MinHeapException(HEAP_EMPTY);   
    }

    int firstelement = ptr[1];

    int lastelement = ptr[size];

    int hole;
    int smallelement;

    /*
     * Decrement the size of heap.
     */
    size--;

    /*
     * Intially the hole is created in the first element.
     * The hole is moved down till we get to a poistion where the childrens are greater than the last element.
     */      for(hole = 1;  hole <= size/2; hole = smallelement)
    {
       
        if(2*hole+1 <= size)
        {
            /*Ther are two childs*/
            if(lastelement < ptr[2*hole] && lastelement < ptr[2*hole+1])
            {
                /*Bot the children are greater than the lastelement. So last element can be placed here*/                break;
            }
           
            /*Find to which subtree the hole should be moved*/
            smallelement = ptr[2*hole] < ptr[2*hole+1] ? 2*hole : 2*hole+1;

        }
        else
        {       
            /*There is one child*/
            if(lastelement < ptr[2*hole])
            {
                /*The child is greater than the lastelement*/
                break;
            }
            smallelement = 2*hole;
        }

        /*Move the samllest children into hole. hole is moved done to smallest children  posistion*/            ptr[hole] = ptr[smallelement];   
    }
   
    /*Replace the hole with the last element*/
    ptr[hole] = lastelement;

    /*Return the first element*/
    return firstelement;

}

void MinHeap :: display()
{
    int i;

    for(i=1; i <= size; i++)
    {
        cout << ptr[i] << " ";
    }
    cout << endl;   
}

MinHeap :: ~MinHeap()
{
    delete [] ptr;
}


int main(int argc, char** argv)
{

    try
    {

            MinHeap heap(11);

            heap.insert(13);
            heap.insert(14);
            heap.insert(16);
            heap.insert(19);
            heap.insert(21);
            heap.insert(19);
            heap.insert(68);
            heap.insert(65);
            heap.insert(26);
            heap.insert(32);
            heap.insert(31);
            heap.insert(41);

            cout << "1st Minimum:" << heap.getMinimum() << endl;

            heap.display();

            cout << "2nd Minimum:" << heap.getMinimum() << endl;

            heap.display();

            cout << "3rd Minimum:" << heap.getMinimum() << endl;

            heap.display();

            cout << "4th Minimum:" << heap.getMinimum() << endl;

            heap.display();

            cout << "5th Minimum:" << heap.getMinimum() << endl;
    }
    catch(MinHeapException& e)
    {
        cout << e.what();
    }
}

Converting string representation of time to unix epoch time.

#include <iostream>
#include <string>
#include <time.h>
#include <stdlib.h>

using namespace std;

int main(int argc, char** argv)
{
    string s_time = "Thu, 19 Oct 2006 11:52:22 +0200";

    struct tm tm;

    /*Convert from string representation to struct tm */

    char* ptr = strptime(s_time.c_str(), "%a, %d %b %Y %T %z", &tm);

    if('\0' != *ptr)
    {
        /*A part of the string was not  processed*/
        cout << "Following part of string not processed:" << ptr  << endl;
    }

    /*Convert from struct tm to time_t structure.*/

    time_t time = mktime(&tm);

    if(-1 == time)
    {
        cout << "Failed to convert from 'struct tm' to 'time_t'" << endl;
        exit(1);
    }
    else
    {
        cout << "Given time in unix time stamp:" << time << endl;
    }

    exit(0);
}

Output:

Given time in unix time stamp:1161238942