selection_algorithms.hpp

Go to the documentation of this file.

/*
    Copyright 2013 Adobe
    Distributed under the Boost Software License, Version 1.0.
    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
*/
/**************************************************************************************************/
 
#ifndef ADOBE_ALGORITHM_SELECTION_HPP
#define ADOBE_ALGORITHM_SELECTION_HPP
 
#include <adobe/config.hpp>
 
#include <algorithm>
#include <functional>
#include <vector>
 
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/size.hpp>
#include <boost/range/size_type.hpp>
#include <boost/range/value_type.hpp>
 
#include <adobe/algorithm/other_of.hpp>
#include <adobe/algorithm/rotate.hpp>
#include <adobe/iterator/type_functions.hpp>
 
/**************************************************************************************************/
 
namespace adobe {
 
/**************************************************************************************************/
/**************************************************************************************************/
template <typename S, // S models ForwardIterator, value_type(S) == I
          typename O, // O models OutputIterator
          typename P>
// P models BinaryPredicate
inline O selection_operation_remainder(S first, S last, O output, bool this_inside,
                                       bool other_inside, P pred) {
    bool prev_op_result(pred(this_inside, other_inside));
 
    while (first != last) {
        this_inside = !this_inside;
 
        bool cur_op_result(pred(this_inside, other_inside));
 
        if (prev_op_result != cur_op_result)
            *output++ = *first;
 
        prev_op_result = cur_op_result;
 
        ++first;
    }
 
    return output;
}
 
/**************************************************************************************************/
template <typename C1,      // C1 models ConvertibleToBool
          typename C2 = C1> // C2 models ConvertibleToBool
struct logical_xor {
    bool operator()(const C1& x, const C2& y) const {
        return static_cast<bool>(x) != static_cast<bool>(y);
    }
};
 
/**************************************************************************************************/
template <typename S1, // S1 models ForwardIterator, value_type(S1) == value_type(S2)
          typename S2, // S2 models ForwardIterator, value_type(S2) == value_type(S1)
          typename O,  // O models OutputIterator
          typename P,  // P models BinaryPredicate
          typename C>
// C models StrictWeakOrdering
O selection_operation(S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, bool s1_inside,
                      bool s2_inside, P pred, C comp) {
    if (s1_first == s1_last)
        return selection_operation_remainder(s2_first, s2_last, output, s2_inside, s1_inside, pred);
    else if (s2_first == s2_last)
        return selection_operation_remainder(s1_first, s1_last, output, s1_inside, s2_inside, pred);
 
    bool prev_op_result(pred(s1_inside, s2_inside));
 
    while (true) {
        typename std::iterator_traits<S1>::value_type next(comp(*s1_first, *s2_first) ? *s1_first
                                                                                      : *s2_first);
 
        if (*s1_first == next) {
            s1_inside = !s1_inside;
 
            ++s1_first;
        }
 
        if (*s2_first == next) {
            s2_inside = !s2_inside;
 
            ++s2_first;
        }
 
        bool cur_op_result(pred(s1_inside, s2_inside));
 
        if (prev_op_result != cur_op_result)
            *output++ = next;
 
        prev_op_result = cur_op_result;
 
        if (s1_first == s1_last)
            return selection_operation_remainder(s2_first, s2_last, output, s2_inside, s1_inside,
                                                 pred);
        else if (s2_first == s2_last)
            return selection_operation_remainder(s1_first, s1_last, output, s1_inside, s2_inside,
                                                 pred);
    }
 
    return output;
}
 
/**************************************************************************************************/
template <typename S1, // S1 models ForwardIterator, value_type(S1) == I
          typename S2, // S2 models ForwardIterator, value_type(S2) == I
          typename O,  // O models OutputIterator
          typename C>
// C models StrictWeakOrdering
inline O selection_union(S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, C comp,
                         bool s1_inside = false, bool s2_inside = false) {
    return selection_operation(s1_first, s1_last, s2_first, s2_last, output, s1_inside, s2_inside,
                               std::logical_or<bool>(), comp);
}
 
/**************************************************************************************************/
template <typename S1, // S1 models ForwardIterator, value_type(S1) == I
          typename S2, // S2 models ForwardIterator, value_type(S2) == I
          typename O,  // O models OutputIterator
          typename C>
// C models StrictWeakOrdering
inline O selection_intersection(S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, C comp,
                                bool s1_inside = false, bool s2_inside = false) {
    return selection_operation(s1_first, s1_last, s2_first, s2_last, output, s1_inside, s2_inside,
                               std::logical_and<bool>(), comp);
}
 
/**************************************************************************************************/
template <typename S1, // S1 models ForwardIterator, value_type(S1) == I
          typename S2, // S2 models ForwardIterator, value_type(S2) == I
          typename O,  // O models OutputIterator
          typename C>
// C models StrictWeakOrdering
inline O selection_difference(S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, C comp,
                              bool s1_inside = false, bool s2_inside = false) {
    return selection_intersection(s1_first, s1_last, s2_first, s2_last, output, comp, s1_inside,
                                  !s2_inside);
}
 
/**************************************************************************************************/
template <typename S1, // S1 models ForwardIterator, value_type(S1) == I
          typename S2, // S2 models ForwardIterator, value_type(S2) == I
          typename O,  // O models OutputIterator
          typename C>
// C models StrictWeakOrdering
inline O selection_symmetric_difference(S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output,
                                        C comp, bool s1_inside = false, bool s2_inside = false) {
    return selection_operation(s1_first, s1_last, s2_first, s2_last, output, s1_inside, s2_inside,
                               logical_xor<bool>(), comp);
}
 
/**************************************************************************************************/
template <typename S1, // S1 models InputIterator, value_type(S1) == I
          typename S2, // S2 models InputIterator, value_type(S2) == I
          typename C>
// C models StrictWeakOrdering
inline bool selection_includes(S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, C comp,
                               bool s1_inside = false, bool s2_inside = false) {
    if (s1_inside == s2_inside) {
        typedef typename std::iterator_traits<S1>::value_type value_type;
 
        std::vector<value_type> result;
 
        selection_intersection(s1_first, s1_last, s2_first, s2_last, std::back_inserter(result),
                               comp, s1_inside, s2_inside);
 
        return std::equal(s2_first, s2_last, result.begin());
    } else if (s1_inside) {
        return selection_includes(boost::next(s1_first), s1_last, s2_first, s2_last, comp,
                                  !s1_inside, s2_inside);
    }
 
    // s2_inside == true
    return selection_includes(s1_first, s1_last, boost::next(s2_first), s2_last, comp, s1_inside,
                              !s2_inside);
}
 
/**************************************************************************************************/
template <typename Selection1, typename Selection2>
Selection1 selection_intersection(const Selection1& x, const Selection2& y) {
    if (&x == &y)
        return x;
 
    Selection1 result(start_selected(x) && start_selected(y));
 
    adobe::selection_intersection(x.begin(), x.end(), y.begin(), y.end(),
                                  std::back_inserter(result),
                                  std::less<typename boost::range_value<Selection1>::type>(),
                                  start_selected(x), start_selected(y));
 
    return result;
}
 
/**************************************************************************************************/
template <typename Selection1, typename Selection2>
Selection1 selection_union(const Selection1& x, const Selection2& y) {
    if (&x == &y)
        return x;
 
    Selection1 result(start_selected(x) || start_selected(y));
 
    adobe::selection_union(x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(result),
                           std::less<typename boost::range_value<Selection1>::type>(),
                           start_selected(x), start_selected(y));
 
    return result;
}
 
/**************************************************************************************************/
template <typename Selection1, typename Selection2>
Selection1 selection_difference(const Selection1& x, const Selection2& y) {
    if (&x == &y)
        return Selection1();
 
    Selection1 result(start_selected(x) != start_selected(y));
 
    adobe::selection_difference(x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(result),
                                std::less<typename boost::range_value<Selection1>::type>(),
                                start_selected(x), start_selected(y));
 
    return result;
}
 
/**************************************************************************************************/
template <typename Selection1, typename Selection2>
Selection1 selection_symmetric_difference(const Selection1& x, const Selection2& y) {
    if (&x == &y)
        return Selection1();
 
    Selection1 result(start_selected(x) != start_selected(y));
 
    adobe::selection_symmetric_difference(
        x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(result),
        std::less<typename boost::range_value<Selection1>::type>(), start_selected(x),
        start_selected(y));
 
    return result;
}
 
/**************************************************************************************************/
template <typename Selection1, typename Selection2>
bool selection_includes(const Selection1& x, const Selection2& y) {
    if (&x == &y)
        return true;
 
    return adobe::selection_includes(x.begin(), x.end(), y.begin(), y.end(),
                                     std::less<typename boost::range_value<Selection1>::type>(),
                                     start_selected(x), start_selected(y));
}
 
/**************************************************************************************************/
template <typename Selection>
inline void invert(Selection& x) {
    x.invert();
}
 
/**************************************************************************************************/
template <typename Selection>
inline bool start_selected(const Selection& x) {
    return x.start_selected();
}
 
/**************************************************************************************************/
template <typename Selection>
inline typename boost::range_size<Selection>::type size(const Selection& x) {
    return x.size();
}
 
/**************************************************************************************************/
template <typename Selection, typename ForwardRange>
typename boost::range_size<Selection>::type size(const Selection& x, const ForwardRange& range) {
    typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
    typedef typename boost::range_size<Selection>::type selection_size_type;
    typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator;
 
    if (x.empty())
        return 0;
 
    // this is the case when the selection has no elements, but it starts selected
    // (in other words, every item in the selection is toggled as selected)
    if (x.size() == 0)
        return boost::size(range);
 
    selection_const_iterator s_iter(boost::begin(x));
    selection_const_iterator s_last(boost::end(x));
 
    range_const_iterator prev(boost::begin(range));
    range_const_iterator iter(boost::next(prev, *s_iter));
    range_const_iterator last(boost::end(range));
 
    selection_size_type result(0);
    bool inside(start_selected(x));
 
    while (true) {
        if (inside)
            result += static_cast<selection_size_type>(std::distance(prev, iter));
 
        if (iter == last)
            break;
 
        prev = iter;
 
        iter = ++s_iter == s_last ? last : boost::next(boost::begin(range), *s_iter);
 
        inside = !inside;
    }
 
    return result;
}
 
/**************************************************************************************************/
template <typename Selection>
bool is_selected(const Selection& x, typename Selection::value_type index) {
    typename boost::range_const_iterator<Selection>::type found(
        std::upper_bound(boost::begin(x), boost::end(x), index));
    typename boost::range_size<Selection>::type count(std::distance(boost::begin(x), found));
 
    return (count % 2 == 1) != start_selected(x);
}
 
/**************************************************************************************************/
template <typename Selection, typename ForwardRange, typename OutputIterator>
OutputIterator selection_copy(const Selection& x, const ForwardRange& range,
                              OutputIterator output) {
    typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
    typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator;
 
    if (boost::size(range) == 0)
        return output;
 
    bool inside(start_selected(x));
 
    selection_const_iterator s_iter(boost::begin(x));
    selection_const_iterator s_last(boost::end(x));
 
    range_const_iterator iter(boost::begin(range));
    range_const_iterator last(boost::end(range));
 
    while (iter != last) {
        if (s_iter != s_last && iter == boost::next(boost::begin(range), *s_iter)) {
            ++s_iter;
 
            inside = !inside;
        }
 
        if (inside)
            *output++ = *iter;
 
        ++iter;
    }
 
    return output;
}
 
/**************************************************************************************************/
template <typename Selection, typename ForwardRange, typename O1, // O1 models OutputIterator
          typename O2>
// O2 models OutputIterator
std::pair<O1, O2> selection_partition_copy(const Selection& selection, ForwardRange& range,
                                           O1 false_output, O2 true_output) {
    typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
    typedef typename boost::range_iterator<ForwardRange>::type range_iterator;
 
    if (boost::size(range) == 0)
        return std::make_pair(false_output, true_output);
 
    selection_const_iterator selection_first(boost::begin(selection));
    selection_const_iterator selection_last(boost::end(selection));
 
    range_iterator first(boost::begin(range));
    range_iterator last(boost::end(range));
 
    bool inside(start_selected(selection));
 
    while (true) {
        range_iterator copy_last(selection_first == selection_last
                                     ? last
                                     : boost::next(boost::begin(range), *selection_first));
 
        // REVISIT (fbrereto) : It'd be nice to collapse the following into ? :
        //                      notation, but some compilers require that the
        //                      types returned by ? : be the same, which we cannot
        //                      guarantee here.
        if (inside)
            std::copy(first, copy_last, true_output);
        else
            std::copy(first, copy_last, false_output);
 
        if (copy_last == last)
            break;
 
        first = copy_last;
        ++selection_first;
        inside = !inside;
    }
 
    return std::make_pair(false_output, true_output);
}
 
/**************************************************************************************************/
template <typename Selection, typename ForwardRange, typename UnaryFunction>
UnaryFunction selection_foreach(const Selection& x, const ForwardRange& range, UnaryFunction proc) {
    typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
    typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator;
 
    bool inside(start_selected(x));
 
    selection_const_iterator s_iter(boost::begin(x));
    selection_const_iterator s_last(boost::end(x));
 
    range_const_iterator iter(boost::begin(range));
    range_const_iterator last(boost::end(range));
 
    while (iter != last) {
        if (s_iter != s_last && iter == boost::next(boost::begin(range), *s_iter)) {
            ++s_iter;
 
            inside = !inside;
        }
 
        if (inside)
            proc(*iter);
 
        ++iter;
    }
 
    return proc;
}
 
/**************************************************************************************************/
template <typename Selection>
inline std::pair<typename boost::range_const_iterator<Selection>::type,
                 typename boost::range_size<Selection>::type>
selection_find_boundary(const Selection& selection, typename Selection::size_type p,
                        std::random_access_iterator_tag) {
    typedef typename boost::range_const_iterator<Selection>::type const_iterator;
    typedef typename boost::range_size<Selection>::type size_type;
    typedef std::pair<const_iterator, size_type> result_type;
 
    const_iterator bound(std::lower_bound(boost::begin(selection), boost::end(selection), p));
 
    return result_type(bound,
                       static_cast<size_type>(std::distance(boost::begin(selection), bound)));
}
 
/**************************************************************************************************/
template <typename Selection>
std::pair<typename boost::range_const_iterator<Selection>::type,
          typename boost::range_size<Selection>::type>
selection_find_boundary(const Selection& selection, typename Selection::size_type p,
                        std::forward_iterator_tag) {
    typedef typename boost::range_const_iterator<Selection>::type const_iterator;
    typedef typename boost::range_size<Selection>::type size_type;
    typedef std::pair<const_iterator, size_type> result_type;
 
    const_iterator iter(boost::begin(selection));
    const_iterator last(boost::end(selection));
    size_type boundary_count(0);
 
    while (iter != last && *iter < p) {
        ++boundary_count;
        ++iter;
    }
 
    return result_type(iter, boundary_count);
}
 
/**************************************************************************************************/
template <typename Selection>
inline std::pair<typename boost::range_const_iterator<Selection>::type,
                 typename boost::range_size<Selection>::type>
selection_find_boundary(const Selection& selection, typename Selection::size_type p) {
    typedef typename boost::range_const_iterator<Selection>::type const_iterator;
    typedef typename boost::range_size<Selection>::type size_type;
    typedef std::pair<const_iterator, size_type> result_type;
    typedef typename iterator_category<const_iterator>::type iterator_category;
 
    if (boost::size(selection) == 0)
        return result_type(boost::end(selection), 0);
 
    return selection_find_boundary(selection, p, iterator_category());
}
 
/**************************************************************************************************/
template <typename SelectionIterator, typename RangeIterator>
RangeIterator selection_stable_partition(SelectionIterator selection_first,
                                         SelectionIterator selection_last, RangeIterator first,
                                         RangeIterator range_first, RangeIterator range_last,
                                         std::size_t boundary_count = 0) {
    std::size_t n(static_cast<std::size_t>(std::distance(selection_first, selection_last)));
 
    if (n == 0)
        return boundary_count % 2 ? range_first : range_last;
 
    std::size_t half(n / 2);
    SelectionIterator selection_middle(boost::next(selection_first, half));
    RangeIterator range_middle(boost::next(first, *selection_middle));
 
    RangeIterator i(selection_stable_partition(selection_first, selection_middle, first,
                                               range_first, range_middle, boundary_count));
 
    RangeIterator j(selection_stable_partition(boost::next(selection_middle), selection_last, first,
                                               range_middle, range_last,
                                               boundary_count + half + 1));
 
    return other_of(adobe::rotate(i, range_middle, j), range_middle);
}
 
/**************************************************************************************************/
template <typename Selection, typename ForwardRange>
inline typename boost::range_iterator<ForwardRange>::type
selection_stable_partition(const Selection& selection, ForwardRange& range) {
    return selection_stable_partition(boost::begin(selection), boost::end(selection),
                                      boost::begin(range), boost::begin(range), boost::end(range),
                                      start_selected(selection));
}
 
/**************************************************************************************************/
template <typename Selection, typename ForwardRange>
std::pair<typename boost::range_iterator<ForwardRange>::type,
          typename boost::range_iterator<ForwardRange>::type>
selection_stable_partition_about(
    const Selection& selection, ForwardRange& range, std::size_t p,
    typename boost::range_size<Selection>::type prior_boundary_count = 0) {
    typedef typename boost::range_size<Selection>::type size_type;
    typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
    typedef typename boost::range_iterator<ForwardRange>::type range_iterator;
 
    std::pair<selection_const_iterator, size_type> selection_split =
        adobe::selection_find_boundary(selection, p);
 
    range_iterator first(boost::begin(range));
    range_iterator range_p(boost::next(first, p));
    range_iterator last(boost::end(range));
 
    range_iterator i(selection_stable_partition(boost::begin(selection), selection_split.first,
                                                first, first, range_p, prior_boundary_count));
 
    range_iterator j(selection_stable_partition(selection_split.first, boost::end(selection), first,
                                                range_p, last, selection_split.second + 1));
 
    return std::pair<range_iterator, range_iterator>(i, j);
}
 
/**************************************************************************************************/
template <typename I, typename N> // I models ForwardIterator
std::pair<I, N> find_sequence_end(I f, I l, N n) {
    while (f != l && n == *f) {
        ++n;
        ++f;
    }
    return {f, n};
}
 
 
/**************************************************************************************************/
 
template <typename I, // I models ForwardIterator
          typename O> // O models OutputIterator>
void index_set_to_selection(I f, I l, O output) {
    while (f != l) {
        auto n = *f;
        *output++ = n;
        ++f;
        ++n;
        std::tie(f, n) = find_sequence_end(f, l, n);
        *output++ = n;
    }
}
 
/**************************************************************************************************/
 
template <typename Selection, typename ForwardRange>
Selection index_set_to_selection(const ForwardRange& index_set) {
 
    Selection result;
 
    index_set_to_selection(std::begin(index_set), std::end(index_set), std::back_inserter(result));
 
    return result;
}
 
/**************************************************************************************************/
template <typename Selection, typename OutputIterator>
OutputIterator selection_to_index_set(const Selection& selection,
                                      typename boost::range_size<Selection>::type max_index,
                                      OutputIterator output) {
    typedef typename boost::range_size<Selection>::type size_type;
    typedef typename boost::range_const_iterator<Selection>::type selection_const_iterator;
 
    bool selected(start_selected(selection));
    size_type index(0);
    selection_const_iterator iter(boost::begin(selection));
    selection_const_iterator last(boost::end(selection));
 
    while (iter != last) {
        while (index != *iter && index != max_index) {
            if (selected)
                *output++ = index;
 
            ++index;
        }
 
        selected = !selected;
        ++iter;
    }
 
    if (selected)
        while (index != max_index)
            *output++ = index++;
 
    return output;
}
 
/**************************************************************************************************/
 
} // namespace adobe
 
/**************************************************************************************************/
 
#endif
 
/**************************************************************************************************/