// ANSI C Headers 
#include <stdlib.h> 
// C++ STL Headers 
#include <algorithm>
#include <iostream>
#include <list>
#include <string>

using namespace std; 

void printList(list<int> lis) {
	list<int>::iterator iter; 
	for ( iter = lis.begin(); iter != lis.end(); iter++ ) 
		cout << *iter << " ";
	cout << endl;
}

list<int> append(list<int> lis, list<int>m) {
		if (lis.size() == 0)
			return m;
		else {
			int first = *lis.begin();
			lis.pop_front();
			list<int> appendedList = append(lis, m);
			appendedList.push_front(first);
			return appendedList;
		}
}

int count(list<int> lis) {
	if (lis.size() == 0)
		return 0;
	else {
		lis.pop_front();
		return 1 + count(lis);
	}
}

bool member(int atm, list<int> lis) {
	if (lis.size() == 0)
		return false;
	else if (*lis.begin() == atm)
		return true;
	else {
		lis.pop_front();
		return member(atm,lis);
	}
}

int smallest(list<int> lis, int small) {
	if (lis.size() == 0)
		return small;
	else if (*lis.begin() < small) {
		int first = *lis.begin();
		lis.pop_front();
		return smallest(lis, first);
	} else {
		lis.pop_front();
		return smallest(lis, small);
	}
}

list<int> remove(list<int> lis, int item) {
	if (lis.size() == 0)
		return lis;
	else if (*lis.begin() == item) {
		lis.pop_front();
		return lis;
	}
	else {
		int first = *lis.begin();
		lis.pop_front();
		list<int> removedList = remove(lis, item);
		removedList.push_front(first);
		return removedList;
	}
}

list<int> selectionsort(list<int> lis) {
	if (lis.size() == 0) return lis;
	else {
		int first = *lis.begin();
		list<int> rest = lis;
		rest.pop_front();
		int s = smallest(rest, first);
		list<int> sortedList = selectionsort(remove(lis,s));
		sortedList.push_front(s);
		return sortedList;
	}
}

list<int> insert(int element, list<int> lis) {
	if (lis.size() == 0) {
		lis.push_front(element);
		return lis;
	} else if (element > *lis.begin()) {
		int first = *lis.begin();
		lis.pop_front();
		list<int> inserted = insert(element, lis);
		inserted.push_front(first);
		return inserted;
	} else {
		lis.push_front(element);
		return lis;
	}
}

list<int> insertionsort(list<int> lis) {
	if (lis.size()==0) return lis;
	else {
		int first = *lis.begin();
		lis.pop_front();
		list<int> sorted = insertionsort(lis);
		return insert(first, sorted);
	}
}


list<int> reverse(list<int> lis) {
	if (lis.size() == 0)
		return lis;
	else {
		int first = *lis.begin();
		lis.pop_front();
		list<int> reversed;
		reversed = reverse(lis);
		reversed.push_back(first);
		return reversed;
	}
}

int gcd(int num1, int num2) {
	if (num2 == 0)
		return num1;
	else 
		return gcd(num2, num1 % num2);
}


int main( int argc, char *argv[] ) 
{ 
	int vals[] = { 10,  5, 18, 2, 3, 20, 1, 4 }; 
	const int N = sizeof(vals)/sizeof(vals[0]); 
	list<int> lis;
	list<int> lis2;
	list<int>::iterator iter; 
	int val;
		
	for ( int i = 0; i < N ; i++) 
		lis.push_back( vals[i] ); 
	for ( int i = 0; i < N ; i++) 
		lis2.push_back( vals[i]*2 ); 
	cout << "List: ";
	printList(lis);
	cout << "Size of list = " << count(lis) 
		<< " = " << lis.size() <<endl;
	cout << "Check for what value? "; 
	cin >> val;
	cout << member(val, lis) << endl;
	cout << "gcd(28,124)=" << gcd(28,124) << endl;
	cout << "List reversed: ";
	printList(reverse(lis));
	cout << "Append 2 lists: ";
	printList(append(lis,lis2));
	cout << "Remove 20: ";
	printList(remove(lis,20));
	cout << "Smallest = ";
	cout << smallest(lis,100) << endl;
	cout << "Sorted list= ";
	printList(selectionsort(lis));
	cout << "Original list= ";
	printList(lis);
	cout << "Sorted list= ";
	printList(insertionsort(lis));	
	return( EXIT_SUCCESS ); 
}