Advanced usages of CppLinq

One of the major reasons for building CppLinq is to allow developers writing their own range operators or range aggregators. While this is easy and straightforward in C# the lack of yield return and extension methods make it more of a challenge in C++ but since CppLinq is based around operator>> it is possible.

Building a range aggregator

The purpose of range aggregators is to aggregate a range into a sum, vector, map or something else. In the functional world it would be known as fold.

A range aggregator consists of two parts:
  1. A builder class which does the work
  2. A helper method to help contruct an instance of the builder class

A builder class has an implicit contract:
// -------------------------------------------------------------------------
// _builder classes:
//      inherit base_builder
//      COPYABLE
//      MOVEABLE (movesemantics)
//      typedef                 ...         this_type       ;
//      template<typename TRange>
//      TAggregated build (TRange range) const
// -------------------------------------------------------------------------

This means that in order to be a builder class the class has to be:
  1. Has to inherit base_builder
  2. Copyable
  3. Moveable
  4. Has member type called this_type which type is the builder class
  5. Has a member method called build that accepts a range and returns the aggregated value

Let's look at the sum_builder in CppLinq:
struct sum_builder : base_builder
{
    typedef                 sum_builder                     this_type       ;

    CPPLINQ_INLINEMETHOD sum_builder () CPPLINQ_NOEXCEPT
    {
    }

    CPPLINQ_INLINEMETHOD sum_builder (sum_builder const & v) CPPLINQ_NOEXCEPT
    {
    }

    CPPLINQ_INLINEMETHOD sum_builder (sum_builder && v) CPPLINQ_NOEXCEPT
    {
    }

    template<typename TRange>
    CPPLINQ_INLINEMETHOD typename TRange::value_type build (TRange range)
    {
        auto sum = typename TRange::value_type ();
        while (range.next ())
        {
            sum += range.front ();
        }
        return std::move (sum);
    }

};

sum_builder is a builder class as it's:
  1. Inherits base_builder
  2. Copyable
  3. Moveable
  4. Has member type this_type that evaluates to sum_builder
  5. It has a build method that accepts a range and returns TRange::value_type

The build method does all the work by traversing the input range range and accumulate a sum.

Finally the helper method sum needs to be provided
CPPLINQ_INLINEMETHOD detail::sum_builder  sum () CPPLINQ_NOEXCEPT
{
    return detail::sum_builder ();
}

This is what is needed to make a range aggregator that integrates with CppLinq.
int computes_a_sum ()
{
    using namespace cpplinq;    
    int ints[] = {3,1,4,1,5,9,2,6,5,4};

    // Computes the sum of all even numbers in the sequence above
    return 
            from_array (ints)
        >>  where ([](int i) {return i%2 ==0;})     // Keep only even numbers
        >>  sum ()                                  // Sum remaining numbers
        ;
}

Building a range operator

The purpose of range operator is to transmute a range into another range; ie the select range operator can transmute a range of ints into a range of strings, the where range operator can be used to transmute a range of ints to a range of ints containing only even numbers. It turns out that a range operator is a range aggregator with the added requirements that the build method of the builder class returns a new range.

A range operator consists of three parts:
  1. A range class which does the work
  2. A builder class which combined with a range produces a new range
  3. A helper method to help contruct an instance of the builder class

A range class has an implicit contract:
// -------------------------------------------------------------------------
// _range classes:
//      inherit base_range
//      COPYABLE
//      MOVEABLE (movesemantics)
//      typedef                 ...         this_type       ;
//      typedef                 ...         value_type      ;
//      typedef                 ...         return_type     ;   // value_type | value_type const &
//      enum { returns_reference = 0|1 };
//      return_type front () const
//      bool next ()
//      template<typename TRangeBuilder>
//      typename get_builtup_type<TRangeBuilder, this_type>::type operator>>(TRangeBuilder range_builder) const 
// -------------------------------------------------------------------------

This means that in order to be a range class the class has to be:
  1. Inherits base_range
  2. Copyable
  3. Moveable
  4. Has member type called this_type which type is the range class
  5. Has member type called value_type which is the type of value in the range
  6. Has member type called return_type which is value_type const & or value_type
  7. Has an enum member returns_reference which is either 0 or 1 depending if return_type is reference or not
  8. Has a member method called front which returns the current value as a return_type
    1. If called on a range where next has not be been called or the previous next returned false the behavior is undefined
    2. front () previously was required to return a value type, this has been relaxed to allow references as well (if its correct to do so)
  9. Has a member method called next which moves the range to the next value if available (returns true) or returns false if no value is available
    1. If called on a range where the previous next returned false next should do nothing and return false
    2. A range where next never has been should be seen as "pointing" to no-value (as opposed to begin () which "points" to the first value in a collection)
  10. Has a member method called operator>> that accepts a range builder and returns the new range
    1. This is the operator that chains the range expressions together

Note: There is no method to reset to range to the first position again. Once it's traversed the race is over. The rationale for that is that I like to support range sources that doesn't support resets. In practice for in-memory collections resets are possible but as long as the range source supports normal copy-semantics resets are achievable using that.

Let's look at the where_range in CppLinq:
template<typename TRange, typename TPredicate>
struct where_range : base_range
{
    typedef                 where_range<TRange, TPredicate> this_type       ;
    typedef                 TRange                          range_type      ;
    typedef                 TPredicate                      predicate_type  ;

    typedef                 typename TRange::value_type     value_type      ;
    typedef                 typename TRange::return_type    return_type     ;
    enum    
    { 
        returns_reference   = TRange::returns_reference   , 
    };

    range_type              range       ;
    predicate_type          predicate   ;

    CPPLINQ_INLINEMETHOD where_range (
            range_type      range
        ,   predicate_type  predicate
        ) CPPLINQ_NOEXCEPT
        :   range       (std::move (range))
        ,   predicate   (std::move (predicate))
    {
    }

    CPPLINQ_INLINEMETHOD where_range (where_range const & v)
        :   range       (v.range)
        ,   predicate   (v.predicate)
    {
    }

    CPPLINQ_INLINEMETHOD where_range (where_range && v) CPPLINQ_NOEXCEPT
        :   range       (std::move (v.range))
        ,   predicate   (std::move (v.predicate))
    {
    }

    template<typename TRangeBuilder>
    CPPLINQ_INLINEMETHOD typename get_builtup_type<TRangeBuilder, this_type>::type operator>>(TRangeBuilder range_builder) CPPLINQ_NOEXCEPT   
    {
        return range_builder.build (*this);
    }

    CPPLINQ_INLINEMETHOD return_type front () const 
    {
        return range.front ();
    }

    CPPLINQ_INLINEMETHOD bool next ()
    {
        while (range.next ())
        {
            if (predicate (range.front ()))
            {
                return true;
            }
        }

        return false;
    }
};

where_range is a range class as it's:
  1. Inherits base_range
  2. Copyable
  3. Moveable
  4. Has member type this_type that evaluates to where_range
  5. Has member type called value_type that evalutes to TRange::value_type
  6. Has member type called return_type that evalutes to TRange::return_type
  7. Has an enum member called returns_reference that evaluates to TRange::returns_reference
    1. where_range is easy in that it doesn't transmute the type, select_range has to rely on some tricks to figure out the value_type
  8. Has a member method called front which returns the current value as return_type
  9. Has a member method called next which moves the range to the next value if available (returns true) or returns false if no value is available
  10. Has a member method called operator>> that accepts a range builder and returns the new range
    1. Uses the meta-function get_builtup_type to figure out the range type

In addition the builder class has to be provided
template<typename TPredicate>
struct where_builder
{
    typedef                 where_builder<TPredicate>   this_type       ;
    typedef                 TPredicate                  predicate_type  ;

    predicate_type  const   predicate   ;

    CPPLINQ_INLINEMETHOD explicit where_builder (predicate_type predicate) CPPLINQ_NOEXCEPT
        :   predicate (std::move (predicate))
    {
    }

    CPPLINQ_INLINEMETHOD where_builder (where_builder const & v)
        :   predicate (v.predicate)
    {
    }

    CPPLINQ_INLINEMETHOD where_builder (where_builder && v) CPPLINQ_NOEXCEPT
        :   predicate (std::move (v.predicate))
    {
    }

    template<typename TRange>
    CPPLINQ_INLINEMETHOD where_range<TRange, TPredicate> build (TRange range) const CPPLINQ_NOEXCEPT
    {
        return where_range<TRange, TPredicate>(range, predicate);
    }

};

Finally the helper method where needs to be provided, this helper method accepts the predicate which is used to filter the range
template<typename TPredicate>
CPPLINQ_INLINEMETHOD detail::where_builder<TPredicate> where (
        TPredicate      predicate
    ) CPPLINQ_NOEXCEPT
{
    return detail::where_builder<TPredicate> (predicate);
}

This is what is needed to make a range operator that integrates with CppLinq.
int computes_a_sum ()
{
    using namespace cpplinq;    
    int ints[] = {3,1,4,1,5,9,2,6,5,4};

    // Computes the sum of all even numbers in the sequence above
    return 
            from_array (ints)
        >>  where ([](int i) {return i%2 ==0;})     // Keep only even numbers
        >>  sum ()                                  // Sum remaining numbers
        ;
}

Building a range source

The purpose of range sources is to take a concept of a collection of any kind such arrays, STL containers or generated collections and express it as cpplinq range in order to make it composable with cpplinq range operators and range aggregators.

A range source consists of two parts:
  1. A range class which does the work
  2. A helper method to help contruct an instance of the range class

The range class has the same implicit contract as above.

Let's look at the from_range in CppLinq ({from_range"} takes two iterators and make a range source from them):
template<typename TValueIterator>
struct from_range : base_range
{
    static TValueIterator get_iterator ();

    typedef                 from_range<TValueIterator>          this_type       ;
    typedef                 TValueIterator                      iterator_type   ;

    typedef                 decltype (*get_iterator ())         raw_value_type  ;
    typedef        typename cleanup_type<raw_value_type>::type  value_type      ;
    typedef                 value_type const &                  return_type     ;
    enum
    {
        returns_reference = 1,
    };

    iterator_type           current ;
    iterator_type           upcoming;
    iterator_type           end     ;


    CPPLINQ_INLINEMETHOD from_range (
            iterator_type begin
        ,   iterator_type end
        ) CPPLINQ_NOEXCEPT
        :   current (std::move (begin))
        ,   upcoming(current)
        ,   end     (std::move (end))
    {
    }

    CPPLINQ_INLINEMETHOD from_range (from_range const & v) CPPLINQ_NOEXCEPT
        :   current (v.current)
        ,   upcoming(v.upcoming)
        ,   end     (v.end)
    {
    }

    CPPLINQ_INLINEMETHOD from_range (from_range && v) CPPLINQ_NOEXCEPT
        :   current (std::move (v.current))
        ,   upcoming(std::move (v.upcoming))
        ,   end     (std::move (v.end))
    {
    }

    template<typename TRangeBuilder>
    CPPLINQ_INLINEMETHOD typename get_builtup_type<TRangeBuilder, this_type>::type operator>>(TRangeBuilder range_builder) const
    {
        return range_builder.build (*this);
    }

    CPPLINQ_INLINEMETHOD return_type front () const
    {
        assert (current != upcoming);
        assert (current != end);

        return *current;
    }

    CPPLINQ_INLINEMETHOD bool next () CPPLINQ_NOEXCEPT
    {
        if (upcoming == end)
        {
            return false;
        }

        current = upcoming;
        ++upcoming;
        return true;
    }
};

Finally the helper method from needs to be provided, this helper method takes a STL container and creates range source. from_range is also used to iterate over classic C arrays using the helper method from_array.
template<typename TContainer>
CPPLINQ_INLINEMETHOD detail::from_range<typename TContainer::const_iterator> from (
        TContainer  const & container
    )
{
    return detail::from_range<typename TContainer::const_iterator> (
            container.begin ()
        ,   container.end ()
        );
}

This is what is needed to make a range source that integrates with CppLinq.

Last edited Mar 23, 2014 at 10:54 AM by marten_range, version 3

Comments

No comments yet.