/r/arkadye set

// myset.h

#include <vector> // Internal representation.
#include <algorithm> // Sorting, comparing.
#include <initializer_list>
#include <string>
#include <sstream>
#include <iostream>

//typedef int T;
template <typename T>
class Set
{
private:
    std::vector<T> data;
    bool compl;

    // Utility functions
    static void cleanUpData(std::vector<T>& dat)
    {
        std::sort(dat.begin(), dat.end());
        dat.erase(std::unique(dat.begin(), dat.end()), dat.end());
    }

    static std::vector<T> mergeData(const std::vector<T> left, const std::vector<T> right)
    {
        auto result = std::vector<T>{};
        std::merge(left.begin(), left.end(), right.begin(), right.end(), std::back_inserter(result));
        cleanUpData(result);
        return result;
    }

    static std::vector<T> unionData(const std::vector<T> left, const std::vector<T> right)
    {
        auto result = std::vector<T>{};
        std::copy_if(left.begin(), left.end(), std::back_inserter(result),
            [&right](const T& item) {return std::binary_search(right.begin(), right.end(), item); });
        return result;
    }

    static std::vector<T> eraseData(const std::vector<T>& original, const std::vector<T>& toBeRemoved)
    {
        auto result = std::vector<T>{};
        std::copy_if(original.begin(), original.end(), std::back_inserter(result),
            [&toBeRemoved](const T& item){return !std::binary_search(toBeRemoved.begin(), toBeRemoved.end(), item); });
        return result;
    }

    // Build the vectors: used this way so we can make const Sets.
    std::vector<T> makeVector(const std::initializer_list<T>& init) const
    {
        auto dat = std::vector<T>{ init };
        cleanUpData(dat);
        return dat;
    }

    template <typename Iterator>
    std::vector<T> makeVector(const Iterator& start, const Iterator& finish) const
    {
        auto dat = std::vector<T>{ start, finish };
        cleanUpData(dat);
        return dat;
    }

    // One true constructor
    Set(std::vector<T>&& dat, bool complement) : data(dat), compl(complement) {}
public:
    template <typename Type> friend Set<Type> operator&&(const Set<Type>&, const Set<Type>&); // Intersection operator.
    template <typename Type> friend Set<Type> operator||(const Set<Type>&, const Set<Type>&); // Union operator
    template <typename Type> friend std::ostream& operator<<(std::ostream&, const Set<Type>&);

    // Make this STL compatible.
    typedef typename std::vector<T>::const_iterator const_iterator;
    typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
    const_iterator cbegin() const { return data.cbegin(); }
    const_iterator cend() const { return data.cend(); }
    const_reverse_iterator crbegin() const { return data.crbegin(); }
    const_reverse_iterator crend() const { return data.crend(); }
    const_iterator begin() const { return cbegin(); }
    const_iterator end() const { return cend(); }
    const_reverse_iterator rbegin() const { return crbegin(); }
    const_reverse_iterator rend() const { return crend(); }

    // CONSTRUCTORS
    Set() : Set(vector<T>{},false) {}
    Set(const Set&) = default;
    template <typename T2> Set(const Set<T2>& rhs) : Set(rhs.begin(), rhs.end()) {}
    Set(Set&& rvs) : Set(std::move(rvs.data), rvs.compl) {}
    Set(const std::initializer_list<T>& il) : Set(makeVector(il),false) {}
    template <typename It> Set(const It& start, const It& finish) : Set(makeVector(start, finish), false) {}

    Set operator=(const Set& rhs) { data = rhs.data; compl = rhs.compl; return *this; }
    Set operator=(Set&& rhs) { data = std::move(rhs.data); compl = rhs.compl; return *this; }

    // Set operations
    Set complement() const
    {
        return Set(std::vector<T>(data), !compl);
    }

    bool contains(const T& val) const
    {
        return std::binary_search(data.begin(), data.end(), val) == compl;
    }
};

template <typename T>
std::string to_string(const Set<T>& input)
{
    std::ostringstream oss;
    oss << input;
    return oss.str();
}

template <typename Type>
std::ostream& operator<<(std::ostream& os, const Set<Type>& set)
{
    if (set.compl) os << '!';
    if (set.data.empty())
    {
        os << "{}";
        return os;
    }
    os << '{' << *(set.begin());
    for (auto it = set.begin() + 1; it != set.end(); ++it)
    {
        os << ", " << *it;
    }
    os << '}';
    return os;
}

// EQUALS FUNCTION
// Normal overload. Both sets are the same size.
template<typename T>
bool operator==(const Set<T>& left, const Set<T>& right)
{
    if (left.size() != right.size())
    {
        return false;
    }
    const auto result = std::mismatch(begin(left), end(left), begin(right));
    return result.first == end(left);
}

// UNION OPERATOR
template<typename T>
Set<T> operator||(const Set<T>& left, const Set<T>& right)
{
    if (!left.compl && !right.compl)
    {
        return Set<T>(Set<T>::mergeData(left.data, right.data), false);
    }
    else if (!left.compl && right.compl)
    {
        return Set<T>(Set<T>::eraseData(right.data, left.data),true);
    }
    else if (left.compl && !right.compl)
    {
        return right || left;
    }
    else if (left.compl && right.compl)
    {
        return Set<T>(Set<T>::unionData(left.data, right.data), true);
    }
    return Set<T>{};
}

template <typename T1, typename T2>
Set<T1> operator||(const Set<T1>& left, const Set<T2>& right)
{
    return left || Set<T1>(right);
}

// INTERSECTION OPERATOR
template<typename T>
Set<T> operator&&(const Set<T>& left, const Set<T>& right)
{
    if (!left.compl && !right.compl)
    {
        return Set<T>(Set<T>::unionData(left.data, right.data), false);
    }
    else if (!left.compl && right.compl)
    {
        return Set<T>(Set<T>::eraseData(left.data, right.data), true);
    }
    else if (left.compl && !right.compl)
    {
        return right && left;
    }
    else if (left.compl && right.compl)
    {
        return Set<T>(Set<T>::mergeData(left.data, right.data), true);
    }
    return Set<T>{};
}

template <typename T1, typename T2>
Set<T1> operator&&(const Set<T1>& left, const Set<T2>& right)
{
    return left && Set<T1>(right);
}

// Complement operator
template <typename T>
Set<T> operator!(const Set<T> in)
{
    return in.complement();
}

// main.cpp

#include "myset.h"

#include <iostream>

using namespace std;

template <typename T>
void printSet(string name, const Set<T>& set)
{
    cout << name << " = " << set << '\n';
}

int main()
{
    auto setI = Set<int>{1, 2, 7, 9};
    auto setS = Set<short>{3, 6};
    auto setI2 = Set<int> {2, 6, 439};
    auto setI3 = Set<int>(begin(setI), end(setI));

    printSet("SetI", setI);
    printSet("SetS", setS);
    printSet("SetI2", setI2);
    printSet("SetI3", setI3);

    printSet("SetI && SetI2", setI && setI2);
    printSet("!SetI && SetI2", !setI && setI2);
    printSet("SetI && !SetI2", setI && !setI2);
    printSet("!SetI && !SetI2", !setI && !setI2);

    printSet("SetI || SetI2", setI || setI2);
    printSet("!SetI || SetI2", !setI || setI2);
    printSet("SetI || !SetI2", setI || !setI2);
    printSet("!SetI || !SetI2", !setI || !setI2);

    setI3 = setI2;
    printSet("setI3 =  setI2", setI3);

    printSet("int SetI", Set<int>(setS));

    cin.get();
}