Sunday, October 12, 2014

Understanding and Implementing Observer Pattern in C++

Introduction

This article presents the basics of Observer Pattern, when to use it and how to implement it in C++. I have posted a similar article that talks about the Observer pattern in C#. The main aim of this article will be to implement the observer pattern in C++.

Background

Many a times, we need one part of our application updated with the status of some other part of the application. One way to do this is to have the receiver part repeatedly check the sender for updates but this approach has two main problems. First, it takes up a lot of CPU time to check the new status and second, depending on the interval we are checking for change we might not get the updates "immediately".
This problem has one easy solution, i.e., Observer Pattern. This is my own second article on Observer Pattern. I have a similar article talking about Observer Implementation in C#. I think this article is also worth sharing, as it could be useful for the C++ beginners and also the valuable comments I get on the article will let me learn more.
Here is the class diagram for Observer Pattern(Reference:  GoF Design Patterns)

Using the Code

Let us now discuss all the classes one by one:
  • Subject: This class keeps track of all the observers and provides the facility to add or remove the observers. Also it is the class that is responsible for updating the observers when any change occurs. In our solution, we have ASubject implemented for the same purpose.
  • ConcreteSubject: This class is the real class that implements the Subject. This class is the entity whose change will affect other objects. We have DummyProject class implemented for the same.
  • Observer: This represents an interface that defines the method that should be called whenever there is change. We have implemented this as IObserver.
  • ConcreteObserver: This is the class which needs to keep itself updated with the change. This class just needs to implement the Observer and register itself with the ConcreteSubject and it is all set to receive the updates. We have Shop class in our application serving the same purpose.


The Subject: ASubject

//Header File
#pragma once
#include <vector>
#include <list>
#include "shop.h"

class ASubject
{
    //Lets keep a track of all the shops we have observing
    std::vector list;

public:
    void Attach(Shop *product);
    void Detach(Shop *product);
    void Notify(float price); 
};

//CPP File
#include "ASubject.h"
#include <algorithm>

using namespace std;

void ASubject::Attach(Shop *shop)
{
    list.push_back(shop);
}
void ASubject::Detach(Shop *shop)
{    
    list.erase(std::remove(list.begin(), list.end(), shop), list.end());    
}

void ASubject::Notify(float price)
{
    for(vector::const_iterator iter = list.begin(); iter != list.end(); ++iter)
    {
        if(*iter != 0)
        {
            (*iter)->Update(price);
        }
    }
}

The ConcreteSubject: DummyProduct

//Header File
#pragma once
#include "ASubject.h"

class DummyProduct : public ASubject
{
public:
    void ChangePrice(float price);
};

//CPP File
#include "DummyProduct.h"

void DummyProduct::ChangePrice(float price)
{
    Notify(price);
}

The Observer: IObserver

#pragma once

class IObserver
{
public:
    virtual void Update(float price) = 0;
};
The ConcreteObserver: Shop
//Header File
#pragma once
#include <iostream>
#include <string>
#include "IObserver.h"

class Shop : IObserver
{
    //Name of the Shop
    std::string name;
    float price;
public:
    Shop(std::string n); 
    void Update(float price);          
};

//CPP File
#include "Shop.h"

Shop::Shop(std::string name)
{
    this->name = name;
}

void Shop::Update(float price)
{
    this->price = price;

    //Lets print on console just to test the working
    std::cout << "Price at "<< name << " is now "<< price << "\n";
}

Testing the Code

int main(int argc, char* argv[])
{
    DummyProduct product;
                    
    // We have four shops wanting to keep updated price set by product owner
    Shop shop1("Shop 1");
    Shop shop2("Shop 2");

    product.Attach(&shop1);
    product.Attach(&shop2);

    //Now lets try changing the products price, this should update the shops automatically
    product.ChangePrice(23.0f);

    //Now shop2 is not interested in new prices so they unsubscribe
    product.Detach(&shop2);            

    //Now lets try changing the products price again
    product.ChangePrice(26.0f);

    getchar();
    return 0;
}

Friday, September 12, 2014

Merge two sorted arrays into another sorted array

void merge(int a[], int m, int b[], int n, int sorted[]) {
  int i, j, k;

  j = k = 0;

  for (i = 0; i < m + n;) {
    if (j < m && k < n) {
      if (a[j] < b[k]) {
        sorted[i] = a[j];
        j++;
      }
      else {
        sorted[i] = b[k];
        k++;
      }
      i++;
    }
    else if (j == m) {
      for (; i < m + n;) {
        sorted[i] = b[k];
        k++;
        i++;
      }
    }
    else {
      for (; i < m + n;) {
        sorted[i] = a[j];
        j++;
        i++;
      }
    }
  }
}
courtesy: http://www.programmingsimplified.com/c/source-code/c-program-merge-two-arrays

Thursday, September 11, 2014

C Program->Hashing->Collision->OpenHashing->Chaining

Example Program To Implement Chain Hashing(in C):



  #include
  #include
  #include

  struct hash *hashTable = NULL;
  int eleCount = 0;

  struct node {
        int key, age;
        char name[100];
        struct node *next;
  };

  struct hash {
        struct node *head;
        int count;
  };

  struct node * createNode(int key, char *name, int age) {
        struct node *newnode;
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->key = key;
        newnode->age = age;
        strcpy(newnode->name, name);
        newnode->next = NULL;
        return newnode;
  }

  void insertToHash(int key, char *name, int age) {
        int hashIndex = key % eleCount;
        struct node *newnode =  createNode(key, name, age);
        /* head of list for the bucket with index "hashIndex" */
        if (!hashTable[hashIndex].head) {
                hashTable[hashIndex].head = newnode;
                hashTable[hashIndex].count = 1;
                return;
        }
        /* adding new node to the list */
        newnode->next = (hashTable[hashIndex].head);
        /*
         * update the head of the list and no of
         * nodes in the current bucket
         */
        hashTable[hashIndex].head = newnode;
        hashTable[hashIndex].count++;
        return;
  }

  void deleteFromHash(int key) {
        /* find the bucket using hash index */
        int hashIndex = key % eleCount, flag = 0;
        struct node *temp, *myNode;
        /* get the list head from current bucket */
        myNode = hashTable[hashIndex].head;
        if (!myNode) {
                printf("Given data is not present in hash Table!!\n");
                return;
        }
        temp = myNode;
        while (myNode != NULL) {
                /* delete the node with given key */
                if (myNode->key == key) {
                        flag = 1;
                        if (myNode == hashTable[hashIndex].head)
                                hashTable[hashIndex].head = myNode->next;
                        else
                                temp->next = myNode->next;

                        hashTable[hashIndex].count--;
                        free(myNode);
                        break;
                }
                temp = myNode;
                myNode = myNode->next;
        }
        if (flag)
                printf("Data deleted successfully from Hash Table\n");
        else
                printf("Given data is not present in hash Table!!!!\n");
        return;
  }

  void searchInHash(int key) {
        int hashIndex = key % eleCount, flag = 0;
        struct node *myNode;
        myNode = hashTable[hashIndex].head;
        if (!myNode) {
                printf("Search element unavailable in hash table\n");
                return;
        }
        while (myNode != NULL) {
                if (myNode->key == key) {
                        printf("VoterID  : %d\n", myNode->key);
                        printf("Name     : %s\n", myNode->name);
                        printf("Age      : %d\n", myNode->age);
                        flag = 1;
                        break;
                }
                myNode = myNode->next;
        }
        if (!flag)
                printf("Search element unavailable in hash table\n");
        return;
  }

  void display() {
        struct node *myNode;
        int i;
        for (i = 0; i < eleCount; i++) {
                if (hashTable[i].count == 0)
                        continue;
                myNode = hashTable[i].head;
                if (!myNode)
                        continue;
                printf("\nData at index %d in Hash Table:\n", i);
                printf("VoterID     Name          Age   \n");
                printf("--------------------------------\n");
                while (myNode != NULL) {
                        printf("%-12d", myNode->key);
                        printf("%-15s", myNode->name);
                        printf("%d\n", myNode->age);
                        myNode = myNode->next;
                }
        }
        return;
  }

  int main() {
        int n, ch, key, age;
        char name[100];
        printf("Enter the number of elements:");
        scanf("%d", &n);
        eleCount = n;
        /* create hash table with "n" no of buckets */
        hashTable = (struct hash *)calloc(n, sizeof (struct hash));
        while (1) {
                printf("\n1. Insertion\t2. Deletion\n");
                printf("3. Searching\t4. Display\n5. Exit\n");
                printf("Enter your choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                printf("Enter the key value:");
                                scanf("%d", &key);
                                getchar();
                                printf("Name:");
                                fgets(name, 100, stdin);
                                name[strlen(name) - 1] = '\0';
                                printf("Age:");
                                scanf("%d", &age);
                                /*inserting new node to hash table */
                                insertToHash(key, name, age);
                                break;

                        case 2:
                                printf("Enter the key to perform deletion:");
                                scanf("%d", &key);
                                /* delete node with "key" from hash table */
                                deleteFromHash(key);
                                break;

                        case 3:
                                printf("Enter the key to search:");
                                scanf("%d", &key);
                                searchInHash(key);
                                break;
                        case 4:
                                display();
                                break;
                        case 5:
                                exit(0);
                        default:
                                printf("U have entered wrong option!!\n");
                                break;
                }
        }
        return 0;
  }





  Output (C Program To Perform Insertion, Deletion In Chain Hash Table):
  jp@jp-VirtualBox:$ ./a.out
  Enter the number of elements:3

  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter your choice:1
  Enter the key value:3
  Name:Sally
  Age:23

  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter your choice:1
  Enter the key value:33
  Name:Harry
  Age:25

  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter your choice:1
  Enter the key value:7
  Name:Nick
  Age:30

  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter your choice:1
  Enter the key value:35
  Name:Raj
  Age:28

  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter your choice:4

  Data at index 0 in Hash Table:
  VoterID     Name          Age   
  --------------------------------
  33          Harry          25
  3           Sally          23
  
  Data at index 1 in Hash Table:
  VoterID     Name          Age   
  --------------------------------
  7           Nick           30

  Data at index 2 in Hash Table:
  VoterID     Name          Age   
  --------------------------------
  35          Raj            28

  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter your choice:2
  Enter the key to perform deletion:33
  Data deleted successfully from Hash Table

  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter your choice:4

  Data at index 0 in Hash Table:
  VoterID     Name          Age   
  --------------------------------
  3           Sally          23

  Data at index 1 in Hash Table:
  VoterID     Name          Age   
  --------------------------------
  7           Nick           30

  Data at index 2 in Hash Table:
  VoterID     Name          Age   
  --------------------------------
  35          Raj            28

  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter your choice:3
  Enter the key to search:35
  VoterID  : 35
  Name     : Raj
  Age      : 28

  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter your choice:5

Courtesy :- http://see-programming.blogspot.in

Wednesday, September 10, 2014

C Program->Hashing->Collision->ClosedHashing->LinearProbing

#include
  #include
  #include   

int tableSize = 0, totEle = 0;
struct node *hashTable = NULL;

  struct node {
        int age, key;
        char name[100];
        int marker;
  };

  void insertInHash(int key, char *name, int age) {
        int hashIndex = key % tableSize;
        if (tableSize == totEle) {
                printf("Can't perform Insertion..Hash Table is full!!");
                return;
        }
        while (hashTable[hashIndex].marker == 1) {
                hashIndex = (hashIndex + 1)%tableSize;
        }
        hashTable[hashIndex].key = key;
        hashTable[hashIndex].age = age;
        strcpy(hashTable[hashIndex].name, name);
        hashTable[hashIndex].marker = 1;
        totEle++;
        return;
  }
  void deleteFromHash(int key) {
        int hashIndex = key % tableSize, count = 0, flag = 0;
        if (totEle == 0) {
                printf("Hash Table is Empty!!\n");
                return;
        }

        while (hashTable[hashIndex].marker != 0 && count <= tableSize) {
                if (hashTable[hashIndex].key == key) {
                        hashTable[hashIndex].key = 0;
                        /* set marker to -1 during deletion operation*/
                        hashTable[hashIndex].marker = -1;
                        hashTable[hashIndex].age = 0;
                        strcpy(hashTable[hashIndex].name, "\0");
                        totEle--;
                        flag = 1;
                        break;
                }
                hashIndex = (hashIndex + 1)%tableSize;
                count++;
        }

        if (flag)
                printf("Given data deleted from Hash Table\n");
        else
                printf("Given data is not available in Hash Table\n");
        return;
  }
  void searchElement(int key) {
        int hashIndex = key % tableSize, flag = 0, count = 0;
        if (totEle == 0) {
                printf("Hash Table is Empty!!");
                return;
        }
        while (hashTable[hashIndex].marker != 0 && count <= tableSize) {
                if (hashTable[hashIndex].key == key) {
                        printf("Voter ID : %d\n", hashTable[hashIndex].key);
                        printf("Name     : %s\n", hashTable[hashIndex].name);
                        printf("Age      : %d\n", hashTable[hashIndex].age);
                        flag = 1;
                        break;
                }
                hashIndex = (hashIndex + 1)%tableSize;
        }

        if (!flag)
                printf("Given data is not present in hash table\n");
        return;
  }
  void display() {
        int i;
        if (totEle == 0) {
                printf("Hash Table is Empty!!\n");
                return;
        }
        printf("Voter ID     Name           Age    Index \n");
        printf("-----------------------------------------\n");
        for (i = 0; i < tableSize; i++) {
                if (hashTable[i].marker == 1) {
                        printf("%-13d", hashTable[i].key);
                        printf("%-15s", hashTable[i].name);
                        printf("%-7d", hashTable[i].age);
                        printf("%d\n", i);
                }
        }
        printf("\n");
        return;
  }
  int main() {
        int key, age, ch;
        char name[100];
        printf("Enter the no of elements:");
        scanf("%d", &tableSize);
        hashTable = (struct node *)calloc(tableSize, sizeof(struct node));
        while (1) {
                printf("1. Insertion\t2. Deletion\n");
                printf("3. Searching\t4. Display\n");
                printf("5. Exit\nEnter ur choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                printf("Enter the key value:");
                                scanf("%d", &key);
                                getchar();
                                printf("Name:");
                                fgets(name, 100, stdin);
                                name[strlen(name) - 1] = '\0';
                                printf("Age:");
                                scanf("%d", &age);
                                insertInHash(key, name, age);
                                break;
                        case 2:
                                printf("Enter the key value:");
                                scanf("%d", &key);
                                deleteFromHash(key);
                                break;
                        case 3:
                                printf("Enter the key value:");
                                scanf("%d", &key);
                                searchElement(key);
                                break;
                        case 4:
                                display();
                                break;
                        case 5:
                                exit(0);

                        default:

                                printf("U have entered wrong Option!!\n");

                                break;

                }

        }

        return 0;

  }



  Output (Closed Hashing - Linear probing Example):
  jp@jp-VirtualBox:~/cpgms/data_structures$ ./a.out
  Enter the no of elements:3
  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter ur choice:1
  Enter the key value:1
  Name:Harry  
  Age:23
  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter ur choice:1
  Enter the key value:2
  Name:Ram
  Age:24
  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter ur choice:1
  Enter the key value:3
  Name:Raj
  Age:23
  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter ur choice:4
  Voter ID     Name           Age    Index 
  -----------------------------------------
  3            Raj            23     0
  1            Harry          23     1
  2            Ram            24     2

  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter ur choice:2
  Enter the key value:1
  Given data deleted from Hash Table
  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter ur choice:4
  Voter ID     Name           Age    Index 
  -----------------------------------------
  3            Raj            23     0
  2            Ram            24     2

  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter ur choice:1
  Enter the key value:10
  Name:Ravi
  Age:23
  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter ur choice:4
  Voter ID     Name           Age    Index 
  -----------------------------------------
  3            Raj            23     0
  10           Ravi           23     1
  2            Ram            24     2

  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter ur choice:3
  Enter the key value:10
  Voter ID : 10
  Name     : Ravi
  Age      : 23
  1. Insertion 2. Deletion
  3. Searching 4. Display
  5. Exit
  Enter ur choice:5

Courtesy :- http://see-programming.blogspot.in