www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - BinaryHeap as member

reply balddenimhero <balddenimhero googlemail.com> writes:
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?
Nov 13 2017
parent reply balddenimhero <balddenimhero googlemail.com> writes:
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.
Nov 13 2017
parent reply balddenimhero <balddenimhero googlemail.com> writes:
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.
Nov 13 2017
parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
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
Nov 13 2017
parent balddenimhero <balddenimhero googlemail.com> writes:
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++).
Nov 14 2017