再帰データ型のように振る舞うset型を作る

概要と結論

集合論において普遍的な集合を取り扱う時，ある集合は元として集合そのものも含めることができる必要があります．

A~ =~ \bigl\{~ 0,~ 1,~ 2,~ \bigl\{ ~ 3, ~ 4, ~ 5 ~ \bigr\} \bigr\} \\

よって仮にその集合をC++で表す型setがあった時，以下のように動作することが望ましいです．

int main(){
    set<int> A, B;

    // { 0, 1, 2 } ⊂ A
    A.insert(0);
    A.insert(1);
    A.insert(2);

    // { 3, 4, 5 } = B
    B.insert(3);
    B.insert(4);
    B.insert(5);

    // { 3, 4, 5 } ∈ A
    A.insert(B);

    return 0;
}

このsetを実装すると以下のようになります．

#include <set>
#include <boost/variant.hpp>
#include <boost/any.hpp>
template<class T>
struct multiplex_less;

template<class T>
class set : public std::set<boost::variant<T, set<T>>, multiplex_less<T>>{
public:
    set() = default;
    set(const set&) = default;
    set(set&&) = default;
    ~set() = default;
};

template<class T>
struct multiplex_less{
    bool operator ()(const boost::variant<T, set<T>> &a, const boost::variant<T, set<T>> &b) const{
        if(a.which() < b.which()){
            return true;
        }else if(a.which() > b.which()){
            return false;
        }else{
            switch(a.which()){
            case 0:
                return std::less<T>()(boost::get<const T&>(a), boost::get<const T&>(b));

            case 1:
                {
                    const set<T> &sa = boost::get<const set<T>&>(a);
                    const set<T> &sb = boost::get<const set<T>&>(b);
                    if(sa.size() < sb.size()){
                        return true;
                    }else if(sa.size() > sb.size()){
                        return false;
                    }else{
                        auto iter = sa.begin();
                        auto jter = sb.begin();
                        for(; iter != sa.end(); ++iter, ++jter){
                            if(multiplex_less()(*iter, *jter)){
                                return true;
                            }else if(multiplex_less()(*jter, *iter)){
                                return false;
                            }
                        }
                        return false;
                    }
                }
            }

            // unreachable poiont.
            return false;
        }
    }
};