#include <iostream>
using std::ostream;
#include <vector>
#include <random>
using std::vector;
using std::cout;
using std::cin;

/*Write the function Similarity() that computes a measure of similarity between two sorted vectors. 
The similarity metric is defined as the count of elements the vectors have in common divided by the 
average size of the vectors.
*/
double Similarity(vector<char>& v1, vector<char>& v2) {
	double avgsize = ((double)v1.size() + v2.size()) / 2;
	vector<char>::iterator it1 = v1.begin();
	vector<char>::iterator it2 = v2.begin();
	unsigned count{ 0 };
	while(it1!=v1.end() && it2!=v2.end())
		if (*it1 == *it2) {
			++count;
			++it1;
			++it2;
		}
		else if (*it1 < *it2) ++it1;
		else ++it2;
	return count / avgsize;
}

//template<typename T>
ostream& operator<<(ostream& os, const vector<char>& v) {
	os << '{';
	for (unsigned i = 0; i < v.size() - 1; ++i)
		os << v[i] << ", ";
	os << v[v.size() - 1] << '}';
	return os;
}

int main() {
	vector<char> v1{ 'a', 'b', 'c', 'c', 'e' };
	vector<char> v2{ 'a', 'c', 'c', 'k', 'm' };
	vector<char> v3{ 'a', 'm' };
	vector<char> v4{ 'w', 'x', 'y', 'z' };
	vector<char> v5{ 'j', 'k', 'k' };
	vector<char> v6{ 'k', 'z' };
	//vector<char> v3{ a, m };
	cout << "The similarity between " << v1 << " and " << v2 << " is " << Similarity(v1, v2) << '\n';
	cout << "The similarity between " << v3 << " and " << v4 << " is " << Similarity(v3, v4) << '\n';
	cout << "The similarity between " << v5 << " and " << v6 << " is " << Similarity(v5, v6) << '\n';
	cin.get();
}