Thread overview
BinaryHeap as member
6 days ago
balddenimhero
November 13
I need a priority queue of integers whose elements are not ordered by the default `opCmp` but some delegate.

The following gist illustrates the problem I'm having:
https://run.dlang.io/gist/92876b2c4d8c77cdc68f1ca61e7e8e44?compiler=dmd

The `Foo` class is supposed to wrap a binary heap (to be used as priority queue) and order its contents according to `o.isLess`. However I do not manage to initialise the according member variable.

Obviously, with the `h` member having type `BinaryHeap(int[], "a<b")` and the constructor trying to assign a `BinaryHeap!(int[], f)` the types do not quite match (line 18).

Maybe I'm missing something obvious or approaching this in the wrong way. Do you have any suggestions on how to achieve the desired result?
November 13
On Monday, 13 November 2017 at 14:38:35 UTC, balddenimhero wrote:
> I need a priority queue of integers whose elements are not ordered by the default `opCmp` but some delegate.
>
> The following gist illustrates the problem I'm having:
> https://run.dlang.io/gist/92876b2c4d8c77cdc68f1ca61e7e8e44?compiler=dmd
>
> The `Foo` class is supposed to wrap a binary heap (to be used as priority queue) and order its contents according to `o.isLess`. However I do not manage to initialise the according member variable.
>
> Obviously, with the `h` member having type `BinaryHeap(int[], "a<b")` and the constructor trying to assign a `BinaryHeap!(int[], f)` the types do not quite match (line 18).
>
> Maybe I'm missing something obvious or approaching this in the wrong way. Do you have any suggestions on how to achieve the desired result?

In case it helps, here is the functionality I'm trying to port to D https://pastebin.com/CWAiEy40. I'm still struggling with properly defining the member in D though.


November 13
On Monday, 13 November 2017 at 15:43:35 UTC, balddenimhero wrote:
> On Monday, 13 November 2017 at 14:38:35 UTC, balddenimhero wrote:
>> I need a priority queue of integers whose elements are not ordered by the default `opCmp` but some delegate.
>>
>> The following gist illustrates the problem I'm having:
>> https://run.dlang.io/gist/92876b2c4d8c77cdc68f1ca61e7e8e44?compiler=dmd
>>
>> The `Foo` class is supposed to wrap a binary heap (to be used as priority queue) and order its contents according to `o.isLess`. However I do not manage to initialise the according member variable.
>>
>> Obviously, with the `h` member having type `BinaryHeap(int[], "a<b")` and the constructor trying to assign a `BinaryHeap!(int[], f)` the types do not quite match (line 18).
>>
>> Maybe I'm missing something obvious or approaching this in the wrong way. Do you have any suggestions on how to achieve the desired result?
>
> In case it helps, here is the functionality I'm trying to port to D https://pastebin.com/CWAiEy40. I'm still struggling with properly defining the member in D though.

In the course of writing a minimal example I removed more than necessary in the previous pastebin (the passed IntOrder has not even been used). Thus here is the corrected one: https://pastebin.com/SKae08GT. I'm trying to port this to D.
November 14
On Monday, 13 November 2017 at 16:26:20 UTC, balddenimhero wrote:
> In the course of writing a minimal example I removed more than necessary in the previous pastebin (the passed IntOrder has not even been used). Thus here is the corrected one: https://pastebin.com/SKae08GT. I'm trying to port this to D.

 Throwing together a sample involves wrapping the value in a new value. Still the idea is put across...

 Not sure if this is the best way to do this, but only takes a little dereferencing to access the value.

Compiled w/DMD v2.069.2

[code]
import std.container.binaryheap;
import std.range : iota;
import std.array;
import std.stdio;

void main()
{
  int len = 10;
    int[] a = iota(len).array;

    auto foo = new WeightedHeap!int([0,2,4,6,8], a);

  foreach(v; foo.h)
    writeln(v.weight, "\t", *v.v);
}

struct WeightedHeap(T) {
  this(int[] order, T[] arr) {
    foreach(i, ref v; arr) {
      a ~= E(order[i%$], &v);
    }

    h = BinaryHeap!(E[])(a);
  }

  E[] a;
  BinaryHeap!(E[]) h;
//  alias h this;

  static struct E {
    int weight;
    T* v;
//    alias v this;

    int opCmp(E a) const {
      return a.weight-weight;
    }
  }
}
[/code]

Output:
Weight  Value
0       5
0       0
2       1
2       6
4       7
4       2
6       3
6       8
8       4
8       9
6 days ago
On Tuesday, 14 November 2017 at 04:13:16 UTC, Era Scarecrow wrote:
> On Monday, 13 November 2017 at 16:26:20 UTC, balddenimhero wrote:
>> In the course of writing a minimal example I removed more than necessary in the previous pastebin (the passed IntOrder has not even been used). Thus here is the corrected one: https://pastebin.com/SKae08GT. I'm trying to port this to D.
>
>  Throwing together a sample involves wrapping the value in a new value. Still the idea is put across...
>
>  Not sure if this is the best way to do this, but only takes a little dereferencing to access the value.

Thanks for actually implementing the workaround you suggested on the IRC for my minmal example. I'm using this for now as it seems that using delegates as predicates is problematic in my use case.

It still feels kind of dirty though, and maybe I'll eventually just implement a standard min-heap that is templated with a comparator (as in C++).