/*
 * set-06.cc    Standard Library, std::set, exercise 6.
 */
#include <iostream>
#include <iterator>
#include <set>
using namespace std;

template<typename T> 
ostream& operator<<(ostream& os, const set<T>& s)
{
   copy(begin(s), end(s), ostream_iterator<T>(cout, " "));
   return os;
}

// Exercise 5
template<typename T>
set<T> operator*(const set<T>& lhs, const set<T>& rhs)
{
   set<T> result;

   auto lhs_iter = lhs.cbegin();
   auto rhs_iter = rhs.cbegin();

   while (lhs_iter != end(lhs) && rhs_iter != end(rhs)) {
      if (*lhs_iter < *rhs_iter)
	 ++lhs_iter;
      else if (*lhs_iter > *rhs_iter)
	 ++rhs_iter;
      else {
	 result.insert(*lhs_iter);
	 ++lhs_iter;
	 ++rhs_iter;
      }
   }

   return result;
}

template<typename T> 
bool subset(const set<T>& lhs, const set<T>& rhs)
{
   return lhs == lhs * rhs;
}

int main()
{
   set<string> s1{ "foo", "bar" };
   set<string> s2{ "foo", "fum", "godzilla", "bar" };

   cout << '\n';
   cout << "s1: " << s1 << '\n';
   cout << "s2: " << s2 << "\n\n";

   cout << boolalpha;
   cout << "s1 is a subset of s2? " << subset(s1, s2) << '\n';
   cout << "s2 is a subset of s1? " << subset(s2, s1) << '\n';
   cout << "s1 is a subset of s1? " << subset(s1, s1) << '\n';

   return 0;
}