Implement order_by()

[PhilippC]

I tried implementing the order_by but got lost in template magic

I guess the approach that came closest to zero-compiler-errors-state was
the following, even though it's not very efficient.

Do you have a hint how to correctly derive the return type of that function?

    /*Put in interactive.h*/

//how to avoid this helper function (duplicated from below)?
template <typename Range>
static interactive<from_enumerable<Range>> _from(Range&& range)
{
    return from_enumerable<Range>(std::forward<Range>(range));
}


template <typename Selector, typename Compare>
/*what to put here?*/ order_by(Selector const& selector, Compare
                                                             compare = std::less<typename std::result_of<Selector(value_type)>::type>())
{
    //not sure if remove_reference is good here, but it seems like I need it
    typedef typename std::result_of<Selector(value_type)>::type key_type;
    typedef std::pair<typename std::remove_reference<key_type>::type,
            typename std::remove_reference<value_type>::type> pair_type;
    std::vector<pair_type> keys_and_values = select([&selector]
                                                                                                    (value_type const& value) {return std::make_pair(selector(value),
                                                                                                                                                                                                     value);}).to_vector();
    std::sort(keys_and_values.begin(), keys_and_values.end(), [&compare]
                        (pair_type const& p1, pair_type const& p2) {return compare(p1.first,
                                                                                                                                             p2.first);} );
    auto x = _from(keys_and_values);
    auto y = x.select([](pair_type const& p) { return p.second;
}).to_vector();
    return _from(y);


}

//Short test:
struct Point
{
    double x,y;
};
std::vector<Point> points = { {1,2}, {4,5}, {-4,3}, {2,1}};

auto points_sorted_by_x = linq::from(points)
                                                    .order_by([] (Point p) { return p.x;}, std::less<double>());

[timothy-shields]

Hi Phillip, thanks a lot for working on this! Here's a toy program to think about:

struct Point { double x,y; };
std::vector<Point> points = { {1,2}, {4,5}, {-4,3}, {2,1} };
auto sorted_points = linq::from(points).order_by([](Point p){ return p.x; });
auto A = sorted_points.to_vector();
points[1].x = -5;
auto B = sorted_points.to_vector();

What should the values of A and B be?

A should be (-4, 3), (1, 2), (2, 1), (4, 5).
B should be (-5, 2), (-4, 3), (2, 1), (4, 5).

We can consider this a test case for the library, since it really ought to work this way. I see two issues: first from takes Range&&, although it seems like it would make more sense to take Range&; and order_by is not doing deferred processing, even though that is a requirement if it is going to return an enumerable.

Try to mimick the implementation of other fundamental operations (for example, select_enumerable.h and select_enumerator.h). This will allow you to make things deferred.

[timothy-shields]

Additionally think about this:

linq::from(points).order_by([](Point p){ return p.x; }).then_by([](Point p){ return p.y; })

How will you end up performing only a single std::sort that uses a dictionary comparison?

[PhilippC]

Ok, I have started to understand a bit more how enumerables and enumerators are working. I have come up with the following solution which has deferred processing and implements "then_by" as well. What do you think?

//interactive.h

template <typename Selector>
    struct CompareFromSelector
    {
        typedef typename std::remove_reference<value_type>::type value_type_no_ref;

        CompareFromSelector (Selector const& select)
            :selector(select)
        {

        }

        CompareFromSelector (Selector&& select)
            :selector(std::move(select))
        {

        }

        Selector selector;
        bool operator() (value_type_no_ref const& v1, value_type_no_ref const& v2)
        {
            return selector(v1) < selector(v2);
        }
    };

    template <typename Selector>
    interactive<order_by_enumerable<enumerable_type, CompareFromSelector<Selector>>> order_by(Selector const& selector)
    {
        return order_by_enumerable<enumerable_type, CompareFromSelector<Selector>>(std::move(source), CompareFromSelector<Selector>(selector));
    }

    template <typename CompareFirst, typename CompareThen>
    struct MultiCompare
    {
        typedef typename std::remove_reference<value_type>::type value_type_no_ref;
        MultiCompare(CompareFirst const& c_first, CompareThen const& c_then)
            : c_first(c_first),
                c_then(c_then)
        {

        }

        CompareFirst c_first;
        CompareThen c_then;

        bool operator()(value_type_no_ref const& v1, value_type_no_ref const& v2)
        {
            if (c_first(v1,v2))
                return true;
            if (c_first(v2,v1))
                return false;
            return c_then(v1,v2);
        }

    };

    template <typename Selector, typename enumerable_type2 = enumerable_type>
    interactive<order_by_enumerable<typename enumerable_type2::source_type, MultiCompare<typename enumerable_type2::compare_type, CompareFromSelector<Selector>>>>
    then_by(Selector const& selector)
    {
        typedef MultiCompare<typename enumerable_type::compare_type, CompareFromSelector<Selector>> NewCompare;
        return order_by_enumerable<typename enumerable_type::source_type, NewCompare>(std::move(source.source), NewCompare(source.compare, CompareFromSelector<Selector>(selector)));


    }

//order_by_enumerable.h

#include "make_unique.h"
#include "enumerable.h"
#include "order_by_enumerator.h"

namespace linq {

template <typename Source, typename Compare>
class order_by_enumerable : public enumerable<typename std::remove_reference<typename Source::value_type>::type>
{
public:
    typedef order_by_enumerator<typename Source::enumerator_type, Compare> enumerator_type;
    typedef typename std::remove_reference<typename Source::value_type>::type value_type;
    typedef Source source_type;
    typedef Compare compare_type;


    Source source;
    Compare compare;
private:
    order_by_enumerable(order_by_enumerable const&); // not defined
    order_by_enumerable& operator=(order_by_enumerable const&); // not defined

public:
    order_by_enumerable(order_by_enumerable&& other)
        : source(std::move(other.source))
        , compare(std::move(other.compare))
    {
    }

    order_by_enumerable(Source&& source, Compare const& compare)
        : source(std::move(source))
        , compare(compare)
    {
    }

    enumerator_type get_enumerator()
    {
        return enumerator_type(source.get_enumerator(), compare);
    }

    std::unique_ptr<enumerator<value_type>> get_enumerator_ptr()
    {
        return make_unique<enumerator_type>(std::move(get_enumerator()));
    }
};

}

//order_by_enumerator.h

namespace linq {

template <typename Source, typename Compare>
class order_by_enumerator : public enumerator<typename std::remove_reference<typename Source::value_type>::type>
{
public:
    typedef typename std::remove_reference<typename Source::value_type>::type value_type;

private:
    std::vector<value_type> ordered_values;
    typename std::vector<value_type>::iterator curr;

    order_by_enumerator(order_by_enumerator const&); // not defined
    order_by_enumerator& operator=(order_by_enumerator const&); // not defined

public:
    order_by_enumerator(order_by_enumerator&& other)
        : ordered_values(std::move(other.ordered_values))
        ,curr(std::move(other.curr))
    {
    }

    order_by_enumerator(Source&& source, Compare const& compare)
    {
        if (!source.move_first())
        {
            curr = ordered_values.end();
        }
        while (true)
        {
            ordered_values.push_back(source.current());
            if (!source.move_next())
                break;
        }

        std::sort(ordered_values.begin(), ordered_values.end(), compare);
        curr = ordered_values.begin();
    }

    bool move_first()
    {
        return curr != ordered_values.end();
    }

    bool move_next()
    {
        ++curr;
        return curr != ordered_values.end();
    }

    value_type current()
    {
        return *curr;
    }
};

}


//test:
struct Point
{
  double x,y;
};
std::vector<Point> points = { {1,2}, {4,5}, {-4,3}, {1,1}, { 1,4}};

auto sorted_points = linq::from(points).order_by([](Point p){ return p.x; }).then_by([](Point p){ return p.y; });

auto vector_sorted_1 = sorted_points.to_vector();

for (auto el: vector_sorted_1)
  {
    std::cout << el.x << ", " << el.y << std::endl;
  }

std::cout << "modifying point and sorting report again..." << std::endl;
points[0].x = -5;

auto vector_sorted_2 = sorted_points.to_vector();

for (auto el: vector_sorted_2)
  {
    std::cout << el.x << ", " << el.y << std::endl;
  }

[timothy-shields]

This looks great. I have a few comments/questions:

• Is linq::from(points) only capturing a reference to points (that is, std::vector<Point>&)? Or is it moving points? We definitely want the former, but I think the library may be doing the latter.

• What happens if I writelinq::from(points).then_by([](Point p){ return p.y; })? Do I get a compiler error? Can we use static_assert to make that give a nice message?

  An alternative way to implement that is to have a specialization of the interactive<Enumerable> class, namely interactive<order_by_enumerable<...>>. The then_by function you have implemented will then live in that specialization of interactive<Enumerable>.

• Note that linq::from(points).order_by([](Point p){ return p.x; }).then_by([](Point p){ return p.y; }) and linq::from(points).order_by([](Point p){ return p.x; }).order_by([](Point p){ return p.y; }) are semantically different. Make sure that they both behave like you would expect.

• The C++11 way of doing this:

  order_by_enumerator(order_by_enumerator const&); // not defined
  order_by_enumerator& operator=(order_by_enumerator const&); // not defined
  

  Is this:

  order_by_enumerator(order_by_enumerator const&) = delete;
  order_by_enumerator& operator=(order_by_enumerator const&) = delete;
  

[PhilippC]

regarding 1) As far as I understand, the library does not move the vector. The from_enumerable specialization for Range& is used in the test case we have here (just tested with MS VC 2013, will test with GCC next week). This specialization stores a reference to the vector.

regarding 2) you get a compiler error because from_enumerable<..> does not have (public) typedefs for source_type and compare_type. Note I have added the "enumerable_type2" template argument just to avoid that compiler error for non "interactive<order_by<...>>". SFINAE only applies if the deduction depends on a template argument. Maybe there is a nicer trick to do that.
Not sure about template specialization here. Wouldn't you have to repeat all other methods from interactive in the specialization as well?

Adding

template <class T>
struct order_by_check
{
    static const bool is_no_order_by = true;
};

template <class T, class T2>
struct order_by_check< order_by_enumerable<T, T2> >
{
    static const bool is_no_order_by = false;
};

template <typename Selector, typename enumerable_type2 = enumerable_type>
typename std::enable_if<order_by_check<enumerable_type2>::is_no_order_by>::type then_by(Selector const& selector)
{
    static_assert(false, "You are trying to call then_by() on an enumerable which is no order_by_enumerable. Call order_by(..).then_by(..).");
}

produces the desired error message for linq::from(points).then_by(...).

regarding 3: this test is ok:

for (auto el : linq::from(points).order_by([](Point p){ return p.x; }).order_by([](Point p){ return p.y; }).to_vector())
{
    std::cout << el.x << ", " << el.y << std::endl;
}

regarding 4: this was copy-pasted from your code :-)

[timothy-shields]

Great work on all of this! You're right about point 2. Regarding point 4, you copy pasted it from me 2 years ago when I didn't know about that use of the delete keyword. Hahaha

Go ahead and make a pull request. If I recall correctly, I have Travis CI set up to build MSVC, GCC, and clang. I'll have to update the readme to reflect what is currently implemented.

On Feb 13, 2016, at 12:09 AM, "PhilippC" [email protected] wrote:

regarding 1) As far as I understand, the library does not move the vector. The from_enumerable specialization for Range& is used in the test case we have here (just tested with MS VC 2013, will test with GCC next week). This specialization stores a reference to the vector.

regarding 2) you get a compiler error because from_enumerable<..> does not have (public) typedefs for source_type and compare_type. Note I have added the "enumerable_type2" template argument just to avoid that compiler error for non "interactive>". SFINAE only applies if the deduction depends on a template argument. Maybe there is a nicer trick to do that.
Not sure about template specialization here. Wouldn't you have to repeat all other methods from interactive in the specialization as well?

Adding

template
struct order_by_check
{
static const bool is_no_order_by = true;
};

template <class T, class T2>
struct order_by_check< order_by_enumerable<T, T2> >
{
static const bool is_no_order_by = false;
};

template <typename Selector, typename enumerable_type2 = enumerable_type>
typename std::enable_if<order_by_check<enumerable_type2>::is_no_order_by>::type then_by(Selector const& selector)
{
static_assert(false, "You are trying to call then_by() on an enumerable which is no order_by_enumerable. Call order_by(..).then_by(..).");
}
produces the desired error message for linq::from(points).then_by(...).

regarding 3: this test is ok:

for (auto el : linq::from(points).order_by([](Point p){ return p.x; }).order_by([](Point p){ return p.y; }).to_vector())
{
std::cout << el.x << ", " << el.y << std::endl;
}
regarding 4: this was copy-pasted from your code :-)

—
Reply to this email directly or view it on GitHub.