Felicitations.

Last summer I wrote a port of boost::multi_index when I had some down time (I haven't had too much since until now). It is here:

https://bitbucket.org/ariovistus/multi_index/

some cursory ddoc here:

http://ariovistus.bitbucket.org/multi_index.html

It is functional, if not fully featured and also not heavily tested.

I welcome feedback on design, missing/possible functionality, additional index types, bikeshedding, etc.

Enjoy [the C++-esque error messages that come with waaay too much template abuse]



Hi Steve, I stole your red black tree code.

On Fri, 17 Feb 2012 22:29:42 -0500, Ellery Newcomer <ellery-newcomer@utulsa.edu> wrote:

> Felicitations.
>
> Last summer I wrote a port of boost::multi_index when I had some down time (I haven't had too much since until now). It is here:
>
> https://bitbucket.org/ariovistus/multi_index/
>
> some cursory ddoc here:
>
> http://ariovistus.bitbucket.org/multi_index.html
>
> It is functional, if not fully featured and also not heavily tested.
>
> I welcome feedback on design, missing/possible functionality, additional index types, bikeshedding, etc.
>
> Enjoy [the C++-esque error messages that come with waaay too much template abuse]
>
>
>
> Hi Steve, I stole your red black tree code.

You didn't steal it since you gave me credit :)  That's what the boost license is for!

I'm glad you found some use for it!

-Steve

Ah, boost::multi_index!
I tend to dream that one day this approach (with template mess cleaned using D capabilities) will find it's way to std.container
So yummy.

On 2/17/12 9:29 PM, Ellery Newcomer wrote:
> Felicitations.
>
> Last summer I wrote a port of boost::multi_index when I had some down
> time (I haven't had too much since until now). It is here:
>
> https://bitbucket.org/ariovistus/multi_index/
>
> some cursory ddoc here:
>
> http://ariovistus.bitbucket.org/multi_index.html
>
> It is functional, if not fully featured and also not heavily tested.
>
> I welcome feedback on design, missing/possible functionality, additional
> index types, bikeshedding, etc.
>
> Enjoy [the C++-esque error messages that come with waaay too much
> template abuse]

Great! I meant for a long time to suggest Steve Schveighoffer to accept a variadic number of predicates for the red-black tree. This is even more general (nevertheless I still think it would be great if RedBlackTree accepted multiple predicates).

Andrei

On Mon, 05 Mar 2012 08:05:16 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 2/17/12 9:29 PM, Ellery Newcomer wrote:
>> Felicitations.
>>
>> Last summer I wrote a port of boost::multi_index when I had some down
>> time (I haven't had too much since until now). It is here:
>>
>> https://bitbucket.org/ariovistus/multi_index/
>>
>> some cursory ddoc here:
>>
>> http://ariovistus.bitbucket.org/multi_index.html
>>
>> It is functional, if not fully featured and also not heavily tested.
>>
>> I welcome feedback on design, missing/possible functionality, additional
>> index types, bikeshedding, etc.
>>
>> Enjoy [the C++-esque error messages that come with waaay too much
>> template abuse]
>
> Great! I meant for a long time to suggest Steve Schveighoffer to accept a variadic number of predicates for the red-black tree. This is even more general (nevertheless I still think it would be great if RedBlackTree accepted multiple predicates).

Sounds like an interesting idea.  I'd have to redesign RBT's node to use N sets of tree pointers.

I'll add it to my (growing) pile :)

-Steve

On 03/05/2012 07:05 AM, Andrei Alexandrescu wrote:
>
> Great! I meant for a long time to suggest Steve Schveighoffer to accept
> a variadic number of predicates for the red-black tree. This is even
> more general (nevertheless I still think it would be great if
> RedBlackTree accepted multiple predicates).
>
> Andrei
>
>

The point of that would just be to have your collection sorted multiple ways, right? It kinda seems like multi_index is most useful in that case, but then I don't use multi_index that often, so I don't know.

It would be a nice addition for RedBlackTree.


<code golf>

import multi_index;
import replace;

template RBTreeZ(Value, Preds...){
    template Splat(size_t i, size_t N){
        static if(i >= N) enum Splat = "";
        else{
            enum Splat = Replace!(q{
                OrderedUnique!("a", Preds[$i]),
            }, "$i",i) ~ Splat!(i+1, N);
        }
    }
    enum ss = (Replace!( q{
        alias MultiIndexContainer!(Value,
            IndexedBy!($indeces)) RBTreeZ;
    }, "$indeces",Splat!(0,Preds.length)));
    mixin(ss);
}
void main(){
    alias RBTreeZ!(int, "a<b", "a>b") MahRBTree;
    // it compiles; good enough for me
}

</code golf>

On 3/5/12 6:21 AM, Steven Schveighoffer wrote:
> Sounds like an interesting idea. I'd have to redesign RBT's node to use
> N sets of tree pointers.

Exactly. The advantage here is that you have the same payload sitting in different trees, which saves duplication.

Multikey rb-trees are used extensively in jemalloc, and are a significant contributor to its performance.


Andrei

On 3/5/12 11:07 AM, Ellery Newcomer wrote:
> import multi_index;
> import replace;
>
> template RBTreeZ(Value, Preds...){
> template Splat(size_t i, size_t N){
> static if(i >= N) enum Splat = "";
> else{
> enum Splat = Replace!(q{
> OrderedUnique!("a", Preds[$i]),
> }, "$i",i) ~ Splat!(i+1, N);
> }
> }
> enum ss = (Replace!( q{
> alias MultiIndexContainer!(Value,
> IndexedBy!($indeces)) RBTreeZ;
> }, "$indeces",Splat!(0,Preds.length)));
> mixin(ss);
> }
> void main(){
> alias RBTreeZ!(int, "a<b", "a>b") MahRBTree;
> // it compiles; good enough for me
> }

That's pretty cool. We should define easier ways to do this kind of stuff.

Andrei