Sunday, August 30, 2015

Problem with Multiple Inheritance in C++ (Diamond Problem)

Multiple Inheritance


 In multiple inheritance a derived class inherits from more than one class.The following figure gives an idea.

                                                   
                                                                   Figure 1

In Figure 1 class D is the derived class and B,C are base classes for it.


Problems with Multiple Inheritance


Consider the following program:
#include<iostream>
using namespace std;

class B{
private:
 int b_var;
public:
   B(){
    b_var=10;
   }
   void display(int b){
    cout<<"Called from B and value is"<<b<<"\n";
   }
};
class C{
private:
 int c_var;
public:
   C(){
    c_var=30;
   }
   void display(int c){
    cout<<"Called from C and value is"<<c<<"\n";
   }
};
class D:public B,public C{

public:
 int d_var;
   D(){
    d_var=40;
   }
 };

int main(){
 D dobject;
 dobject.display(dobject.d_var);
}
 We will get an error: request for member 'display' is ambiguous.
Why this happens? Think!!!

Let's look how the compiler evaluates the above program: 
After creating an object of type D when we call the function display using that object the compiler searches for display function in class D. As the compiler cannot find it then looks to see if any of the base classes have a function named display().
The problem is that 'dobject' actually contains two display() functions: one inherited from class B, and one inherited from class C. Therefore compiler cannot choose between the two and the function call is ambiguous, and will receive a compiler error.

How to solve this problem?

One way is to explicitly mention from which class the method has to be derived. This is known as explicit scoping.
dobject.B::display(dobject.d_var);

And the output is:
Called from B and value is 40

Diamond Problem

Let's complicate things a bit more. Now have a look at the following figure:

                                                                Figure 2

   If the function display is derived from A the program looks like this:
class A{
private:
 int a_var;
public:
   A(){
    a_var=100;
   }
   void display(int a){
    cout<<"Called from A and value is "<<a<<"\n";
   }
};

class B:public A{
private:
 int b_var;
public:
   B(){
    b_var=10;
   }

};
class C:public A{
private:
 int c_var;
public:
   C(){
    c_var=30;
   }

};
class D:public B,public C{

public:
 int d_var;
   D(){
    d_var=40;
   }
 };

int main(){
 D dobject;
 dobject.display(dobject.d_var);

 return 0;
}

The same problem as in the case of multiple inheritance exists and also adds more problems to it.
The compiler doesn't know whether it should have one or two copies of A and how to resolve such ambiguous references. While these problems can be solved using explicit scoping but the maintenance overhead increases.

If we create object of type D then by default compiler ends up creating two copies of class A. As shown in the figure 3.


                                                                        Figure 3

Most of the times we want the compiler to create only one copy of class A.

Is it possible?
Yes, it is possible with the help of virtual base classes.

So let's make some changes to the code and make it work.
class A{
private:
 int a_var;
public:
   A(){
    a_var=100;
   }
   void display(int a){
    cout<<"Called from A and value is "<<a<<"\n";
   }
};

class B:virtual public A{
private:
 int b_var;
public:
   B(){
    b_var=10;
   }

};
class C:virtual public A{
private:
 int c_var;
public:
   C(){
    c_var=30;
   }

};
class D:public B,public C{

public:
 int d_var;
   D(){
    d_var=40;
   }
 };

int main(){
 D dobject;
 dobject.display(dobject.d_var);

 return 0;
}
 And the Output looks like: 
Called from A and value is 40

Here Class A is constructed only once. Before finishing this topic there are few points to be remembered.
First virtual base classes are created before non-virtual base classes, which ensures all bases get created before their derived classes. 

Second, note that the constructors of Classes B and C still have calls to the A's constructor. If we are creating an instance of D, these constructor calls are simply ignored because D is responsible for creating the A, not B or C. However, if we were to create an instance of B or C, the virtual keyword is ignored, those constructor calls would be used, and normal inheritance rules apply.

Third, if a class inherits one or more classes that have virtual parents, the most derived class is responsible for constructing the virtual base class.

Happy Learning....

How Derived classes are constructed in C++

Inheritance is one of the object oriented concept where one object inherits the behavior of another object. This concept is mainly used by the programmers for the purpose of reusing their code.

To know how the order of derived class works lets start with an example:

#include<iostream>
using namespace std;

class Base {
private:
 int base_var;
public:
 Base() {
  base_var = 10;
  cout << "Base is called \n";
 }
};
class Derived: public Base {
private:
 int derived_var;
public:
 Derived() {
  derived_var = 0;
  cout << "Derived is called \n";
 }
};

int main() {
 cout << "Instantiating Base class \n";
 Base b;
 cout << "Instantiating Derived class \n";
 Derived d;

 return 0;
}

In this example the Derived class is derived from Base class, Derived class inherits the public functions and public variables of base class. Figure 1 shows the diagrammatic representation of the classes.
 
                                                                    Figure 1


 If we run the above problem the output looks like this:

Instantiating Base class 
Base is called 
Instantiating Derived class 
Base is called 
Derived is called 

What can we conclude from the output? We can say that when we instantiate a derived class it first calls base part and then derived part. So derived portion consists of two parts: a Base part and a derived part.
When the compiler constructs the derived objects, it does in such a way that it starts with base. Once the base portion is complete it then walks through the inheritance tree and constructs the derived portion. So what actually happens in this example is that the Base portion of Derived is constructed first. Once the Base portion is finished, the Derived portion is constructed. At this point, there are no more derived classes, so we are done.

The construction of the derived classes always starts with base class and then the next derived class and then so on until we reach our actual derived class.


Sunday, July 12, 2015

Left and Right View of a Binary Tree

Left View

Left view of a Binary Tree is set of nodes visible when a tree is seen from left side. 

The following are the steps :
1.Do level order.
2.Print the first node in every level.

                                                                             Figure 1

The figure above shows the nodes(marked with red arrow) that are seen from left side of the tree.

Code for printing the left view nodes:
 void LeftViewoftree(struct node* root) {

 if (root == NULL) return ;
 queue<node *> q;
 cout<<root->data<<" ";
 int flag=0;
 q.push(root);
 q.push(NULL);
 while (!q.empty()) {
  struct node *curr = q.front();
  q.pop();
  if (curr == NULL) {
     if (!q.empty()){
   q.push(NULL);
   flag=1;
  }

  }

  else {
   if(flag==1){
   cout<<curr->data<<" ";
   flag=0;
   }
   if (curr->left != NULL){       
   q.push(curr->left);
       
   }
   if (curr->right != NULL){
   q.push(curr->right);
   
   }
  }
          }
}

Friday, July 3, 2015

Finding Height of a Tree (Recursive and Iterative)

1. Recursive Method

                                                                                     Figure 1

We use the tree shown above as our example for better understanding and  height of the tree is 3.

The following are the steps to find the height recursively: 
  1. Calculate the height of left subtree and right subtree.
  2. Find the maximum height out of the two.
  3. Add 1 (in order to include the root) to the value which gives the answer.

The below diagram gives clear explanation of the recursion:

                                   height('1') = max(height('2'), height('3')) + 1
                                                             = 2 + 1
                                                                 /    \
                                                               /         \
                                                             /             \
                                                           /                 \
                                                          /                     \
                                             height('1')                  height('3') = 1
                    = max(height('4'), height('5')) + 1
                              = 1 + 1   = 2
                                   /    \
                                 /        \
                               /            \
                             /                \
                           /                    \
            height('4') = 1     height('5') = 1

The following code shows the function which calculates the height recursively:
 int height(node * root)
{
    struct node * curr=root;
    if(curr==NULL)   //base condition
        return 0;
    else
        return(1+max(height(curr->left),height(curr->right)));
  }
For the complete code of recursive method visit here.

2. Iterative Method

In an Iterative method we can use level order to find the height of the tree. The idea is to traverse level by level.

The following are the steps to find the height iteratively:
  1. Create a queue and push the root node into it.
  2. Whenever we reach next level we add NULL node to the queue and increment 'height' variable.
  3. Otherwise, we add left and right nodes of the current node into queue
  4. Steps 2 and 3 are repeated until the queue is empty.
The following figure shows the steps in detail to calculate height for tree shown in Figure 1.

                                                                             Figure 2        
              
The following code shows the function which calculates the height iteratively:

 int heightoftree(struct node* root) {
 int h = 0;
 if (root == NULL)
  return 0;
 queue<node *> q;
 q.push(root);
 q.push(NULL);
 while (!q.empty()) {

  struct node *curr = q.front();
  q.pop();

  if (curr == NULL) {
   h++;
   if (!q.empty())
    q.push(NULL);
   cout << h << " ";
  }

  else {
   if (curr->left != NULL)
    q.push(curr->left);
   if (curr->right != NULL)
    q.push(curr->right);
  }

 }
 return h;
}
For the complete code of iterative method visit here

Sunday, June 7, 2015

Addition of Large Numbers using strings in C++

The logic behind this is to store the large number as string and operate on each character as string is an array of characters each digit of the number is stored as a character. In order to work with characters there are two ways to do:
1.To write our own arithmetic operators to work with characters (overloading of operators)
2.Convert a character into an integer, work on integers and convert back to a character.  

How to convert a character into an integer?

Method 1:
If we have a character c='10'.We can follow  one of these steps:

int a                                
                                          a=(int)c                      //a has ascii value of 'c' i.e 58
             c=c-48                       //58-48=10

Ascii value of the digit can be obtained by adding 48 to the digit.


Method 2:
            int a                                                            
                    a=c-'0'               // i.e 58-48=10&a contains 10 
The character '0' means 48

Note: To convert from char to integer subtract ‘0’ and to convert from an integer to char add ‘0’


Here is the program to add two large numbers

#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
int main()
{
string str1="1234567891011121314151617181920", str2="1234567891011121314151617181920" ;
string rev_str1, rev_str2;
string final; //Final product string
int carry = 0;
rev_str1 = string(str1.rbegin(), str1.rend());
rev_str2 = string(str2.rbegin(), str2.rend());
for (int i = 0; i <rev_str1.length() ; i++)
{
int x=rev_str1[i]-'0'; //converting into integer
int y=rev_str2[i]-'0';
int z=x+y+carry;
final+=('0'+z%10); //converting into character
carry=z/10;
}
if(carry>0) //final carry
final+='0'+carry;
final = string(final.rbegin(), final.rend());
cout << "final = " << final << endl;
}

This numerical example gives better understanding of the program.
  
str1="129" str2="234"
rev_str1="921".rev_str2="432"

carry=0

i=0 to 2

i=0
  
x='9'-'0'=57-48=9
y='4'-'0'=52-48=4
z=9+4+0 //carry=0 for 1st iteration

final +='0'+13%10='3'
carry=13/10=1

i=1

x='2'-'0'=50-48=2
y='3'-'0'=51-48=3
z=2+3+1 //carry=1 

final +='0'+5%10='6'  //final="3"
carry=5/10=0

i=2

x='1'-'0'=59-48=1
y='2'-'0'=50-48=2

z=1+2+0 //carry=0 

final +='0'+3%10='3'  //final="36"
carry=3/10=0


final="363"




Multiplication of two large numbers by storing intermediate values in C++

If we are asked to multiply two numbers of hundred digits each, how we are going to solve this problem?

One approach to solve this kind of problems is to store intermediate values and compute the final result using this. The intermediate values will not be as large as the number with hundred digits, therefore the computation becomes easy.
The idea of this approach is taken from the basic multiplication that we were taught during school days. This naive approach i.e. write one number above the other, then do long multiplication helps us to know the intermediate values which is used to compute the final result.

Let's go back to naive method where we used to do multiplication in this way


    9999
x      19

     -----
                                  89991                  // array1
                             + 99990                 //array2
 ---------
 189981



If we multiply the first two digits of this example i.e 9*9 the intermediate value is 81 where 8 is carry and 1 is stored in a temporary array. In the next step we multiply next digit of multiplicand i.e 9*9 Similarly we repeat this process and store each intermediate digit at each index in an array. Here we can use two arrays for storing the entire intermediate values. Adding both arrays will give the result.


Here is an example program for multiplying two large numbers.



#include <string>
#include <vector>
#include <iostream>
#include <stdio.h>
using namespace std;
void product(string a, string b) {
vector<int> result(a.size() + b.size(), 0);
for( int i = a.size() - 1; i >= 0; i-- ){
for( int j = b.size() - 1; j >= 0; j-- ){
result[ i + j + 1 ] += ( b[ j ] - '0') * ( a[ i ] - '0' ); //single array to store intermediate values
}
}
for( int i = a.size() + b.size(); i >= 0; i-- ){
if( result[ i ] >= 10 ){
result[ i - 1 ] +=result[ i ] / 10;
result[ i ] %= 10;
}
}
cout << a << " * " << b << " = ";
for( int i = 0; i < a.size() + b.size(); i++ ){
cout << result[ i ];
}
cout << endl;
}
int main( void ){
string str1, str2 ;
str1 = "99999999999999999999";
str2 = "9985995948565498566";
product( str1, str2 );
return 0;
}