set union helper: iterator, range

set_iterators.hpp

#ifndef SET_UNION_ITERATOR_RANGE_HPP
#define SET_UNION_ITERATOR_RANGE_HPP

#include <type_traits>
#include <utility>

#include <boost/blank.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/iterator/iterator_categories.hpp>
#include <boost/logic/tribool.hpp>
#include <boost/range/iterator_range.hpp>

namespace detail {

template<typename type, typename value_compare_type, typename impl_type>
struct set_adaptor_traits {
    using container_type  = type;

    using traversal       = boost::forward_traversal_tag;
    using iterator        = typename type::iterator;
    using reference       = typename type::iterator::reference;
    using difference_type = typename type::iterator::difference_type;
    using value_type      = typename std::remove_reference<reference>::type;
    using base_type       = std::pair<iterator, iterator>;
    using value_compare   = typename std::conditional<std::is_same<value_compare_type, boost::use_default>::value, typename type::value_compare, value_compare_type>::type;

    using adaptor_type    = boost::iterator_adaptor<
        impl_type      ,
        base_type      ,
        value_type     ,
        traversal      ,
        reference      ,
        difference_type
    >;
};

struct set_union {
    using state = boost::tribool;

    template<typename iterator>
    static const iterator &get(const state &use_first, const iterator &first_i, const iterator &second_i)
    {
        if (use_first)
            return first_i;
        else
            return second_i;
    }

    template<typename iterator, typename comparator_type>
    static state compute_state(iterator &first_i, iterator &second_i, const iterator &first_end, const iterator &second_end, const comparator_type &comparator)
    {
        if (first_i == first_end)
            return false;
        else if (second_i == second_end)
            return true;
        else if (comparator(*first_i, *second_i))
            return true;
        else if (comparator(*second_i, *first_i))
            return false;
        else
            return boost::indeterminate;
    }

    template<typename iterator, typename comparator_type>
    static void increment(state &use_first, iterator &first_i, iterator &second_i, const iterator &first_end, const iterator &second_end, const comparator_type &comparator)
    {
        if (use_first)
            ++ first_i;
        else if (!use_first)
            ++second_i;
        else
            ++ first_i,
            ++second_i;

        use_first = compute_state(first_i, second_i, first_end, second_end, comparator);
    }
};

struct set_intersection {
    using state = boost::blank;

    template<typename iterator>
    static const iterator &get(const state &, const iterator &first_i, const iterator &)
    {
        return first_i;
    }

    template<typename iterator, typename comparator_type>
    static state compute_state(iterator &first_i, iterator &second_i, const iterator &first_end, const iterator &second_end, const comparator_type &comparator)
    {
        for (; first_i != first_end && second_i != second_end; )
        {
            if (comparator(*first_i, *second_i))
                ++first_i;
            else if (comparator(*second_i, *first_i))
                ++second_i;
            else
                return state();
        }

        if (first_i == first_end)
            return (second_i = second_end), state();
        else
            return ( first_i =  first_end), state();
    }

    template<typename iterator, typename comparator_type>
    static void increment(const state &, iterator &first_i, iterator &second_i, const iterator &first_end, const iterator &second_end, const comparator_type &comparator)
    {
        ++ first_i,
        ++second_i;

        compute_state(first_i, second_i, first_end, second_end, comparator);
    }
};

template<typename type, typename value_compare_type, typename determiner_type>
class set_iterator_impl : public set_adaptor_traits<type, value_compare_type, set_iterator_impl<type, value_compare_type, determiner_type>>::adaptor_type {
public:
    using traits_type  = set_adaptor_traits<type, value_compare_type, set_iterator_impl<type, value_compare_type, determiner_type>>;

    using iterator        = typename traits_type::iterator       ;
    using reference       = typename traits_type::reference      ;
    using difference_type = typename traits_type::difference_type;
    using value_type      = typename traits_type::value_type     ;
    using base_type       = typename traits_type::base_type      ;
    using value_compare   = typename traits_type::value_compare  ;
    using state_type      = typename determiner_type::state      ;

    set_iterator_impl(iterator first_i, iterator second_i, iterator first_end, iterator second_end, value_compare comp = value_compare())
        : traits_type::adaptor_type({std::move(first_i), std::move(second_i)})
        , state()
        , end(std::move(first_end), std::move(second_end))
        , comp(std::move(comp))
    {
        auto &  pair_i_local = this->base_reference();
        auto & first_i_local = std::get<0>(pair_i_local);
        auto &second_i_local = std::get<1>(pair_i_local);

        const auto & first_end_local = std::get<0>(end);
        const auto &second_end_local = std::get<1>(end);

        state = determiner_type::compute_state(first_i_local, second_i_local, first_end_local, second_end_local, comp);
    }

    reference dereference() const
    {
        const auto &  pair_i = this->base_reference();
        const auto & first_i = std::get<0>(pair_i);
        const auto &second_i = std::get<1>(pair_i);

        return *determiner_type::get(state, first_i, second_i);
    }

    void increment()
    {
        auto &  pair_i = this->base_reference();
        auto & first_i = std::get<0>(pair_i);
        auto &second_i = std::get<1>(pair_i);

        const auto & first_end = std::get<0>(end);
        const auto &second_end = std::get<1>(end);

        determiner_type::increment(state, first_i, second_i, first_end, second_end, comp);
    }

private:
    state_type     state;
    base_type      end;
    value_compare  comp;

};

}

template<typename type, typename value_compare_type = boost::use_default>
using set_union_iterator = detail::set_iterator_impl<type, value_compare_type, detail::set_union>;

template<typename type, typename value_compare_type = boost::use_default>
using set_intersection_iterator = detail::set_iterator_impl<type, value_compare_type, detail::set_intersection>;

template<typename type>
inline boost::iterator_range<set_union_iterator<type>> make_set_union_range(const type &first, const type &second)
{
    return {
        set_union_iterator<type>(first.begin(), second.begin(), first.end(), second.end(), first.value_comp()),
        set_union_iterator<type>(first.end  (), second.end  (), first.end(), second.end(), first.value_comp())
    };
}

template<typename type>
inline boost::iterator_range<set_intersection_iterator<type>> make_set_intersection_range(const type &first, const type &second)
{
    return {
        set_intersection_iterator<type>(first.begin(), second.begin(), first.end(), second.end(), first.value_comp()),
        set_intersection_iterator<type>(first.end  (), second.end  (), first.end(), second.end(), first.value_comp())
    };
}

#endif

test.cpp

#include <iostream>
#include <set>

#include "set_iterators.hpp"

int main() {
    std::set<int> set_a{1, 3, 5};
    std::set<int> set_b{2, 3, 4};

    set_union_iterator<std::set<int>> i   (set_a.begin(), set_b.begin(), set_a.end(), set_b.end());
    set_union_iterator<std::set<int>> iend(set_a.end  (), set_b.end  (), set_a.end(), set_b.end());
    auto                              range = make_set_union_range(set_a, set_b);

    for (; i != iend; ++i)
        std::cout << *i << std::endl;

    std::cout << "=====================================" << std::endl;

    for (const auto &value : range)
        std::cout << value << std::endl;

    std::cout << "=====================================" << std::endl;

    set_intersection_iterator<std::set<int>> i2   (set_a.begin(), set_b.begin(), set_a.end(), set_b.end());
    set_intersection_iterator<std::set<int>> i2end(set_a.end  (), set_b.end  (), set_a.end(), set_b.end());
    auto                                     range2 = make_set_intersection_range(set_a, set_b);

    for (; i2 != i2end; ++i2)
        std::cout << *i2 << std::endl;

    std::cout << "=====================================" << std::endl;

    for (const auto &value : range2)
        std::cout << value << std::endl;

    std::cout << "=====================================" << std::endl;

    return 0;
}