www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - RBTree delegates and types

reply Viktor <viktor.ivanov gmail.com> writes:
Hey,

I'm trying to convert an old legacy app to D and have a couple of 
questions. It has been a very fun weekend!

First, I could not make std.container.rbtree use a delegate for a 
comparator. The docs say it should be possible, but I got a weird 
error.

I tracked it down to RedBlackTreee.opEquals() using explicit 
function when calling equals():

return equal!(function(Elem a, Elem b) => !_less(a,b) && 
!_less(b,a))(thisRange, thatRange);

When I removed the "function" things started compiling (I have 

-b unittest without issues so it might be OK.

So, the first...several questions are: do you think this change 
is safe and should I raise an issue in the bugzilla or do a PR 
for it on github? Should it include a new unittest that makes 
sure rbtree can be instantiated with a delegate?

The other part I'm still struggling with is about auto types. Can 
I store the rbtree type in the following class so it can be used 
from another method?

class Indexer(T, alias pred)
{
    this(T storage)
    {
       this.storage = storage;
       auto index = new RedBlackTree!(uint, (a,b) => comp(a, b));
       // how to store index?
    }

    void dumpIndex()
    {
        // how to get my dirty hands on the index here?
    }

    bool comp(uint i1, uint i2)
    {
       auto rec1 = storage[i1];
       auto rec2 = storage[i2];
       return pred(rec1, rec2);
    }

    private T storage;
    ??? index;
}
Mar 18 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/18/18 8:34 AM, Viktor wrote:

 Hey,
 
 I'm trying to convert an old legacy app to D and have a couple of 
 questions. It has been a very fun weekend!
 
 First, I could not make std.container.rbtree use a delegate for a 
 comparator. The docs say it should be possible, but I got a weird error.
 
 I tracked it down to RedBlackTreee.opEquals() using explicit function 
 when calling equals():
 
 return equal!(function(Elem a, Elem b) => !_less(a,b) && 
 !_less(b,a))(thisRange, thatRange);
 
 When I removed the "function" things started compiling (I have yet to 

 without issues so it might be OK.
 
 So, the first...several questions are: do you think this change is safe 
 and should I raise an issue in the bugzilla or do a PR for it on github? 


Yes, seems like an oversight. RedBlackTree.opEquals was added almost 6 
years ago, and it's possible this wouldn't have worked back then 
(https://github.com/dlang/phobos/pull/900)



 Should it include a new unittest that makes sure rbtree can be 
 instantiated with a delegate?


Definitely. Thanks for thinking of this!


 
 The other part I'm still struggling with is about auto types. Can I 
 store the rbtree type in the following class so it can be used from 
 another method?
 
 class Indexer(T, alias pred)
 {


       alias RBType = RedBlackTree!(uint, (a, b) => comp(a, b));

     this(T storage)
     {
        this.storage = storage;


          this.index = new RBType();


     }



 
     void dumpIndex()
     {
         // how to get my dirty hands on the index here?


           // answer: just use it?


     }
 
     bool comp(uint i1, uint i2)
     {
        auto rec1 = storage[i1];
        auto rec2 = storage[i2];
        return pred(rec1, rec2);
     }
 
     private T storage;


       RBType index;


 }
 


-Steve
Mar 18 2018
parent reply Viktor <viktor.ivanov gmail.com> writes:
On Sunday, 18 March 2018 at 17:21:58 UTC, Steven Schveighoffer 
wrote:

 On 3/18/18 8:34 AM, Viktor wrote:

 Hey,
 
 I'm trying to convert an old legacy app to D and have a couple 
 of questions. It has been a very fun weekend!
 
 First, I could not make std.container.rbtree use a delegate 
 for a comparator. The docs say it should be possible, but I 
 got a weird error.
 
 I tracked it down to RedBlackTreee.opEquals() using explicit 
 function when calling equals():
 
 return equal!(function(Elem a, Elem b) => !_less(a,b) && 
 !_less(b,a))(thisRange, thatRange);
 
 When I removed the "function" things started compiling (I have 

 dub -b unittest without issues so it might be OK.
 
 So, the first...several questions are: do you think this 
 change is safe and should I raise an issue in the bugzilla or 
 do a PR for it on github?


 Yes, seems like an oversight. RedBlackTree.opEquals was added 
 almost 6 years ago, and it's possible this wouldn't have worked 
 back then (https://github.com/dlang/phobos/pull/900)



 Should it include a new unittest that makes sure rbtree can be 
 instantiated with a delegate?


 Definitely. Thanks for thinking of this!


 
 The other part I'm still struggling with is about auto types. 
 Can I store the rbtree type in the following class so it can 
 be used from another method?
 
 class Indexer(T, alias pred)
 {


       alias RBType = RedBlackTree!(uint, (a, b) => comp(a, b));

     this(T storage)
     {
        this.storage = storage;


          this.index = new RBType();


     }



 
     void dumpIndex()
     {
         // how to get my dirty hands on the index here?


           // answer: just use it?


     }
 
     bool comp(uint i1, uint i2)
     {
        auto rec1 = storage[i1];
        auto rec2 = storage[i2];
        return pred(rec1, rec2);
     }
 
     private T storage;


       RBType index;


 }
 


 -Steve


Hi Steve, thanks for replying!

I've also noticed that RedBlackTree.opEquals() is like this from 
the initial pull request and was wondering if noone has been 
using a delegate and why...

On the second topic, I've tried that and it doesn't work. I have 
a minimal test program that shows the issue.

https://run.dlang.io/is/WNF78H

onlineapp.d(15): Error: need this for less of type bool(int a, 
int b)
onlineapp.d(15):        instantiated from here: Generic!((a, b) 
=> less(a, b))

If I try using an explicit delegate in the alias:

onlineapp.d(15): Error: delegate `onlineapp.Custom.__dgliteral6` 
cannot be class members
onlineapp.d(15):        instantiated from here: Generic!(delegate 
(a, b) => less(a, b))

That seems reasonable to me, since the delegate needs a frame 
(for the this pointer) and there is no frame at that point.

I think in the end I'll need to plant an interface that RBTree 
will implement and use the interface instead.

The code in question:

class Generic(alias pred)
{
    void add(int a, int b)
    {
        import std.stdio : writeln;
        if (pred(a,b))
            writeln(a);
        else
            writeln(b);
    }
}

class Custom
{
     alias MyGeneric = Generic!( (a,b) => less(a,b) );
     private MyGeneric g;

     this ()
     {
         g = new MyGeneric;
     }

     void test()
     {
         g.add(5, 6);
     }

     bool less(int a, int b)
     {
         import std.stdio : writeln;
         writeln("Yup");
         return a < b;
     }
}

void main()
{
     auto t = new Custom;
     t.test;
}
Mar 19 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/19/18 5:16 AM, Viktor wrote:


 
 Hi Steve, thanks for replying!
 
 I've also noticed that RedBlackTree.opEquals() is like this from the 
 initial pull request and was wondering if noone has been using a 
 delegate and why...


typically, you don't need a delegate, but generally, you CAN use a 
delegate as an alias "less" function. I don't see why it should be 
restricted here.

But this is probably why nobody ever found it -- most people just use 
the default lambda.


 
 On the second topic, I've tried that and it doesn't work. I have a 
 minimal test program that shows the issue.
 
 https://run.dlang.io/is/WNF78H


Oh! I totally missed that comp is a member function (in your first 
example). I thought it was passed in. Sorry for not taking a closer look.

Yes, you need a `this` pointer for it to work. However, we can do this 
by encapsulating the return type with an auto function:

https://run.dlang.io/is/inSzaU

Sorry I didn't get this right away. Interesting chicken-and-egg problem, 
but as usual, D delivers :)

-Steve
Mar 19 2018
parent Viktor <viktor.ivanov gmail.com> writes:
On Monday, 19 March 2018 at 11:30:13 UTC, Steven Schveighoffer 
wrote:

 Yes, you need a `this` pointer for it to work. However, we can 
 do this by encapsulating the return type with an auto function:

 https://run.dlang.io/is/inSzaU

 Sorry I didn't get this right away. Interesting chicken-and-egg 
 problem, but as usual, D delivers :)

 -Steve


That's beautiful! Thanks!
Mar 19 2018