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 test the code due to question #2 below). I've done a 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? 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;
}

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 test the code due to question #2 below). I've done a 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

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 yet to test the code due to question #2 below). I've done a 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;
}

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

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!