/**
 * @file grade_school_multiplication.cpp
 * @author Shirsih Reddy <shirishreddy89@gmail.com>
 * 
 * Multiplication is done using the grade school method 
 */


#include <iostream>
#include <list>
using namespace std;

/**
 * dec_bin function converts a given number to binary number 
 * 
 * @param A decimal number which is to be converted in to Binary number
 * @return Returns a 'list' of 0's and 1's representing the binary format of the given decimal number.
 */
list<int> dec_bin(int num)
{
	list<int> binary;
	while(1){
		if(num%2 == 0)
			binary.push_front(0);
		else 
			binary.push_front(1);
		num/=2;
		if(num == 1){
			binary.push_front(1);
			break;
		}
		else if(num == 0) {
			binary.push_front(0);
			break;
		}
	}
	return binary;
}

/**
 * 'pad' function sees to that both the lists are of same size by padding them with front zeros
 * 
 * @param Two lists of same or different sizes
 */
void pad(list<int> &n1, list<int> &n2){
	if(n1.size() < n2.size()) {
		for(unsigned i=n1.size(); i<n2.size(); i++)
			n1.push_front(0);
	}
	else if(n2.size() < n1.size()) {
		for(unsigned i = n2.size(); i<n1.size(); i++)
			n2.push_front(0);
	}
}

/**
 * add function adds two binary numbers and returns the result
 *
 * @param two numbers (binary lists) which are to be added
 * @return result is the number (binary list) obtained by adding given numbers
 */ 
list<int> add(list<int> n1, list<int> n2){
	list<int> result;
	list<int> :: reverse_iterator it1, it2;
		int carry = 0;
	pad(n1,n2);
	for(it1 = n1.rbegin(), it2 = n2.rbegin(); it1 != n1.rend() && it2 != n2.rend(); it1++, it2++) {
		if( *it1 == 1 && *it2 == 1) {
			if(carry == 0)
				result.push_front(0);
			else if (carry == 1)
				result.push_front(1);
			carry = 1;
		}
		else if( *it1 == 1 && *it2 == 0 ) {
			if(carry == 0) {
				result.push_front(1);
				carry = 0;
			}
			else if(carry == 1) {
				result.push_front(0);
				carry = 1;
			}
		}
		else if( *it1 == 0 && *it2 == 1 ) {
			if(carry == 0) {
				result.push_front(1);
				carry = 0;
			}
			else if(carry == 1) {
				result.push_front(0);
				carry = 1;
			}
		}
		else if( *it1 == 0 && *it2 == 0) {
			if(carry == 0)
				result.push_front(0);
			else if(carry == 1)
				result.push_front(1);
			carry = 0;
		}
	}
	if(carry == 1)
		result.push_front(1);
	return result;
}
			
/**
 * multiply function multiplies the given binary numbers and returns the result
 * 
 * @param two numbers (binary lists) which are to be multiplied
 * @return A list (binary number) obtained by multiplication
 */
list<int> multiply(list<int> n1, list<int> n2)
{
	list<int> p;
	list<int> :: reverse_iterator rit2;
	for(rit2 = n2.rbegin(); rit2!=n2.rend(); rit2++) {
		if(*rit2 == 1) {
			p = add(p,n1);	
		}
		n1.push_back(0);
	}
	return p;
}
		
	
	
int main(){
	list<int> ptr1 = dec_bin(900);
	list<int> ptr2 = dec_bin(3);
	list<int> res = add(ptr1, ptr2);
	list<int> mulr = multiply(ptr1,ptr2);
	list<int> :: iterator it;
	for(it = mulr.begin(); it!=mulr.end(); it++)
		cout<<*it;
	
	return 0;
}
	
		
		

101010001100