selection_algorithms.hpp

Go to the documentation of this file.

/*
    Copyright 2005-2007 Adobe Systems Incorporated
    Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
    or a copy at http://stlab.adobe.com/licenses.html)
*/
/*************************************************************************************************/

#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/value_type.hpp>
#include <boost/range/size_type.hpp>
#include <boost/range/size.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 : std::binary_function<C1, C2, bool>
{
    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;

    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;

    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;

    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;

    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 Selection,
          typename ForwardRange>
Selection index_set_to_selection(const ForwardRange& index_set)
{
    Selection result;

    // REVISIT (fbrereto) : This would go much faster using divide-and-conquer
    //                      and eventually balanced reduction.

    typedef typename boost::range_const_iterator<ForwardRange>::type range_const_iterator;

    range_const_iterator iter(boost::begin(index_set));
    range_const_iterator last(boost::end(index_set));

    for (; iter != last; ++iter)
    {
        Selection tmp;

        tmp.push_back(*iter);
        tmp.push_back(*iter + 1);

        result = selection_union(result, tmp);
    }

    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));
    std::size_t              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;
    }

    return output;
}

/*************************************************************************************************/

} // namespace adobe

/*************************************************************************************************/

#endif

/*************************************************************************************************/