www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - multi_index

reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
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.
Feb 17 2012
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Mar 05 2012
prev sibling next sibling parent "mist" <none none.none> writes:
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.
Mar 05 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 05 2012
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Mar 05 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 05 2012
prev sibling parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
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>
Mar 05 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 05 2012