[Fusion] Views of Associative Sequences

[Nate Knight]

I'm trying to find a solution to the following problem.  If I have an associative sequence such as a fusion::set
and I make a filter view of it, the view is not a model of an associative sequence and does not support the
has_key and at_key functions.  I can use fusion::as_set on the view to get an associative sequence again, but
this doesn't really have the effect I want as it results in a set holding copies of the original data whereas the
view referenced the original data.  Example below.

Would it be possible to create a view which supported the associative sequence interface?   Any suggested alternative approaches?

Thanks
Nate

~~~~~~~~~~~~~~~~~

#include <boost/fusion/include/set.hpp>
#include <boost/fusion/include/intrinsic.hpp>
#include <boost/fusion/include/filter_view.hpp>
#include <string>
#include <boost/type_traits/is_arithmetic.hpp>
#include <boost/mpl/placeholders.hpp>

namespace fusion = boost::fusion;
using boost::mpl::_;

int main()
{
    typedef fusion::set<int,double,std::string> set_t;
    set_t s(1,2.0,"hello");

    fusion::filter_view<set_t,boost::is_arithmetic<_>> filtered_view(s);
    fusion::front(filtered_view) = 4; //modifies s

    fusion::result_of::as_set<fusion::filter_view<set_t,boost::is_arithmetic<_> > >::type filtered_set(filtered_view);
    fusion::at_key<int>(filtered_set) = 16; // modifies the copied data in filtered_set.
}



_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Christopher Schmidt-4]

James Knight schrieb:

> I'm trying to find a solution to the following problem.  If I have an
> associative sequence such as a fusion::set
> and I make a filter view of it, the view is not a model of an
> associative sequence and does not support the
> has_key and at_key functions.  I can use fusion::as_set on the view to
> get an associative sequence again, but
> this doesn't really have the effect I want as it results in a set
> holding copies of the original data whereas the
> view referenced the original data.  Example below.
>
> Would it be possible to create a view which supported the associative
> sequence interface?   Any suggested alternative approaches?
>
> Thanks
> Nate

There is already a feature request for associative views (ticket 3473).
I will get down to it once I am granted write access to the trunk.
For now you could use my c++0x port of fusion. It correctly preserves
the category of the underlying sequence's for all views.
The port is fully backwards compatible, in terms of both features and
compiler (non-0x compiler are supported).
You can find the code in the sandbox (/sandbox/SOC/2009/fusion/).

-Christopher

_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Joel de Guzman-2]

Christopher Schmidt wrote:

> James Knight schrieb:
>> I'm trying to find a solution to the following problem.  If I have an
>> associative sequence such as a fusion::set
>> and I make a filter view of it, the view is not a model of an
>> associative sequence and does not support the
>> has_key and at_key functions.  I can use fusion::as_set on the view to
>> get an associative sequence again, but
>> this doesn't really have the effect I want as it results in a set
>> holding copies of the original data whereas the
>> view referenced the original data.  Example below.
>>
>> Would it be possible to create a view which supported the associative
>> sequence interface?   Any suggested alternative approaches?
>>
>> Thanks
>> Nate
>
> There is already a feature request for associative views (ticket 3473).
> I will get down to it once I am granted write access to the trunk.
> For now you could use my c++0x port of fusion. It correctly preserves
> the category of the underlying sequence's for all views.
> The port is fully backwards compatible, in terms of both features and
> compiler (non-0x compiler are supported).
> You can find the code in the sandbox (/sandbox/SOC/2009/fusion/).

And in case you are wondering, Christopher Schmidt's wonderful
c++0x port will be the future of fusion.

Regards,
--
Joel de Guzman
http://www.boostpro.com
http://spirit.sf.net
http://www.facebook.com/djowel

Meet me at BoostCon
http://www.boostcon.com/home
http://www.facebook.com/boostcon


_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Nate Knight]

Joel de Guzman <joel <at> boost-consulting.com> writes:

> And in case you are wondering, Christopher Schmidt's wonderful
> c++0x port will be the future of fusion.
>
> Regards,

Cool.  The port looks really nice.  After looking through the code, I've got a
couple of questions.  The most direct one regards the implementation of at_key
for set and map.  The implementation seems to have changed considerably from the
1.40 version.  If I'm reading things correctly at_key is now implemented using a
new find_key algorithm whereas the 1.40 version used some function overloading
mechanism.  Is there any run-time performance difference between the two
approaches?  It looks as if find_key is a constant time algorithm.  Am I correct
in my understanding?

Thanks



_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Joel de Guzman-2]

Nate Knight wrote:

> Joel de Guzman <joel <at> boost-consulting.com> writes:
>
>> And in case you are wondering, Christopher Schmidt's wonderful
>> c++0x port will be the future of fusion.
>>
>> Regards,
>
> Cool.  The port looks really nice.  After looking through the code, I've got a
> couple of questions.  The most direct one regards the implementation of at_key
> for set and map.  The implementation seems to have changed considerably from the
> 1.40 version.  If I'm reading things correctly at_key is now implemented using a
> new find_key algorithm whereas the 1.40 version used some function overloading
> mechanism.  Is there any run-time performance difference between the two
> approaches?  It looks as if find_key is a constant time algorithm.  Am I correct
> in my understanding?

I'd guess it would be the same. I'm not so sure about compile rime
performance though. I'll let Christopher provide details. At any
rate, I'd urge Christopher to add more benchmarks. I started one
a long time ago, but it needs to be beefed up, especially with the
upcoming 0x port.

Regards,
--
Joel de Guzman
http://www.boostpro.com
http://spirit.sf.net
http://www.facebook.com/djowel

Meet me at BoostCon
http://www.boostcon.com/home
http://www.facebook.com/boostcon


_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Christopher Schmidt-4]

Joel de Guzman schrieb:

> Nate Knight wrote:
>> Joel de Guzman <joel <at> boost-consulting.com> writes:
>>
>>> And in case you are wondering, Christopher Schmidt's wonderful
>>> c++0x port will be the future of fusion.
>>>
>>> Regards,
>>
>> Cool.  The port looks really nice.  After looking through the code,
>> I've got a
>> couple of questions.  The most direct one regards the implementation
>> of at_key
>> for set and map.  The implementation seems to have changed
>> considerably from the
>> 1.40 version.  If I'm reading things correctly at_key is now
>> implemented using a
>> new find_key algorithm whereas the 1.40 version used some function
>> overloading
>> mechanism.  Is there any run-time performance difference between the two
>> approaches?  It looks as if find_key is a constant time algorithm.  Am
>> I correct
>> in my understanding?
>
> I'd guess it would be the same. I'm not so sure about compile rime
> performance though. I'll let Christopher provide details. At any
> rate, I'd urge Christopher to add more benchmarks. I started one
> a long time ago, but it needs to be beefed up, especially with the
> upcoming 0x port.
>
> Regards,

My implementation introduces associative iterators. An associative
forward sequence shall provide an iterator that allows direct mapping
from the iterator (type) to the underlying element (type), key type and
the actual value (type) associated with the key.
I split fusion::find up in fusion::find_key and a new fusion::find. My
fusion::find does not care about the associative-ness of the sequence.
It searches for a plain element type. That is it returns the first
iterator for which is_same<fusion::result_of::value_of<mpl::_1>, Elem>
evaluates to true, or an end-iterator. fusion::find_key returns the
first iterator for which is_same<fusion::result_of::key_of<mpl::_1>,
Key> evaluates to true, or an end-iterator.

The compile-time evaluation of a
fusion::(result_of::)find_key-invocation should scale linear to the
number of elements of the sequence being searched on. The
fusion::find_key implementation uses fusion::detail::static_seq_find_if,
which is 4-unrolled optimized.
This should be slightly faster compared to the unoptimized
implementation of fusion::map<...>/set<...>::(meta_)find_impl(_const),
which are plain recursive metafunctions/n-overloaded functions.
The runtime performance of my port should be better if the compiler
supports rvalue references. If not, there should not be a difference in
any case at all. For fusion::find, the run-time performance is of course
constant.
The "old" implementation uses a distinct intrusive (meta-)function,
analogue to find, to implement at_key. I implemented fusion::at_key
based on fusion::find_key.

For more information on my port, have a look at the posts over at the
development mailing list.

http://article.gmane.org/gmane.comp.lib.boost.devel/194322

-Christopher

_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Joel de Guzman-2]

Christopher Schmidt wrote:

> My implementation introduces associative iterators. An associative
> forward sequence shall provide an iterator that allows direct mapping
> from the iterator (type) to the underlying element (type), key type and
> the actual value (type) associated with the key.
> I split fusion::find up in fusion::find_key and a new fusion::find. My
> fusion::find does not care about the associative-ness of the sequence.
> It searches for a plain element type. That is it returns the first
> iterator for which is_same<fusion::result_of::value_of<mpl::_1>, Elem>
> evaluates to true, or an end-iterator. fusion::find_key returns the
> first iterator for which is_same<fusion::result_of::key_of<mpl::_1>,
> Key> evaluates to true, or an end-iterator.
>
> The compile-time evaluation of a
> fusion::(result_of::)find_key-invocation should scale linear to the
> number of elements of the sequence being searched on. The
> fusion::find_key implementation uses fusion::detail::static_seq_find_if,
> which is 4-unrolled optimized.
> This should be slightly faster compared to the unoptimized
> implementation of fusion::map<...>/set<...>::(meta_)find_impl(_const),
> which are plain recursive metafunctions/n-overloaded functions.
> The runtime performance of my port should be better if the compiler
> supports rvalue references. If not, there should not be a difference in
> any case at all. For fusion::find, the run-time performance is of course
> constant.
> The "old" implementation uses a distinct intrusive (meta-)function,
> analogue to find, to implement at_key. I implemented fusion::at_key
> based on fusion::find_key.
>
> For more information on my port, have a look at the posts over at the
> development mailing list.

That's a well-thought and very nice design, Christopher!

Regards,
--
Joel de Guzman
http://www.boostpro.com
http://spirit.sf.net
http://www.facebook.com/djowel

Meet me at BoostCon
http://www.boostcon.com/home
http://www.facebook.com/boostcon


_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[g-h-d]

>
> There is already a feature request for associative views (ticket 3473).
> I will get down to it once I am granted write access to the trunk.

I see that the ticket is closed and the changes implemented in the trunk
: many thanks!

I wonder if I should wait for v1.41 (when : is there an estimate?) or if
I can already remove joint_view.hpp from my current copy of boost and
replace it with the new one : do you remember if the changes in
joint_view standalone?

_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Christopher Schmidt-4]

er schrieb:
> I wonder if I should wait for v1.41 (when : is there an estimate?) or if
> I can already remove joint_view.hpp from my current copy of boost and
> replace it with the new one : do you remember if the changes in
> joint_view standalone?

Unfortunately the changes in <boost/fusion/view/joint_view/*> are not
stand-alone, and I was too late to merge them into the 1.41 release branch.
I suggest you to work with a copy of the HEAD of the trunk.

-Christopher

_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[g-h-d]

Christopher Schmidt wrote:
>
> Unfortunately the changes in <boost/fusion/view/joint_view/*> are not
> stand-alone, and I was too late to merge them into the 1.41 release branch.

OK.

> I suggest you to work with a copy of the HEAD of the trunk.
>

Sorry for troubling you with more trivialities, but by HEAD do you mean
the latest update?

Could you please confirm if this is the link from which I should copy
fusion to my current release so I can start using the new facilities you
have provided:

http://svn.boost.org/svn/boost/trunk/boost/fusion/

Thanks.


_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Christopher Schmidt-4]

er schrieb:
> Sorry for troubling you with more trivialities, but by HEAD do you mean
> the latest update?
Yeah, the most up-to-date revision of the fusion trunk.
>
> Could you please confirm if this is the link from which I should copy
> fusion to my current release so I can start using the new facilities you
> have provided:
>
> http://svn.boost.org/svn/boost/trunk/boost/fusion/
That's correct.

svn co http://svn.boost.org/svn/boost/trunk/boost/fusion fusion

-Christopher

_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Joel de Guzman-2]

Christopher Schmidt wrote:

> er schrieb:
>> Sorry for troubling you with more trivialities, but by HEAD do you mean
>> the latest update?
> Yeah, the most up-to-date revision of the fusion trunk.
>> Could you please confirm if this is the link from which I should copy
>> fusion to my current release so I can start using the new facilities you
>> have provided:
>>
>> http://svn.boost.org/svn/boost/trunk/boost/fusion/
> That's correct.
>
> svn co http://svn.boost.org/svn/boost/trunk/boost/fusion fusion

Many thanks for working on this, Christopher!

Regards,
--
Joel de Guzman
http://www.boostpro.com
http://spirit.sf.net
http://www.facebook.com/djowel

Meet me at BoostCon
http://www.boostcon.com/home
http://www.facebook.com/boostcon


_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users