digitalmars.D.learn - Creating a growable binary heap or priority queue using Phobos?
- SimonM (33/33) Nov 13 2011 Hey, I'm trying to use the BinaryHeap in Phobos, but somehow can't get
- SimonM (5/38) Nov 13 2011 Okay, I might on the wrong track, but part of the reason that the
- Jonathan M Davis (6/10) Nov 13 2011 A std.container.Array is not a range. It's a container. Yes, it uses an ...
- SimonM (31/41) Nov 13 2011 Okay, that makes sense, but it seems that BinaryHeap should be able to
- Jonathan M Davis (6/7) Nov 13 2011 I don't know. I've never used BinaryHeap. I'd have to study it. I just n...
- SimonM (2/9) Nov 13 2011 Well it definitely helps; and now I understand it better as well, so tha...
- bearophile (5/7) Nov 13 2011 See the working version:
Hey, I'm trying to use the BinaryHeap in Phobos, but somehow can't get it working with the Array!(T) container so that the heap can actually be growable. I keep getting this error: Error: template instance BinaryHeap!(myArray,"a > b") does not match template declaration BinaryHeap(Store,alias less = "a < b") if (isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[]))) The documentation (http://d-programming-language.org/phobos/std_container.html#BinaryHeap) says that BinaryHeap should be growable with any container that supports the insertBack function, which Array!(T) does (http://d-programming-language.org/phobos/std_container.html#insertBack). I've found the following questions in the newsgroup that all asked the same question, without really resolving it (without using their own implementation): 2011, 28 March: http://www.digitalmars.com/d/archives/digitalmars/D/learn/Growable_BinaryHeap_use_w_Array_25362.html 2011, 6 March: http://www.digitalmars.com/d/archives/digitalmars/D/learn/How_do_you_use_BinaryHeap_with_Array_or_just_make_a_growable_heap_25928.html 2009, 27 April: http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.html From those threads, I found that the reason might be related to the fact that the isRandomAccessRange template returns false when used with an Array!(T) object, for example this ---------------------------------------- import std.range; import std.container; void main(){ pragma(msg,isRandomAccessRange!(Array!(uint))); } ---------------------------------------- prints out false during compilation. Is there any way to use Array!(T) with a BinaryHeap, or any other way to have a growable BinaryHeap?
Nov 13 2011
On 2011/11/13 22:49 PM, SimonM wrote:Hey, I'm trying to use the BinaryHeap in Phobos, but somehow can't get it working with the Array!(T) container so that the heap can actually be growable. I keep getting this error: Error: template instance BinaryHeap!(myArray,"a > b") does not match template declaration BinaryHeap(Store,alias less = "a < b") if (isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[]))) The documentation (http://d-programming-language.org/phobos/std_container.html#BinaryHeap) says that BinaryHeap should be growable with any container that supports the insertBack function, which Array!(T) does (http://d-programming-language.org/phobos/std_container.html#insertBack). I've found the following questions in the newsgroup that all asked the same question, without really resolving it (without using their own implementation): 2011, 28 March: http://www.digitalmars.com/d/archives/digitalmars/D/learn/Growable_BinaryHeap_use_w_Array_25362.html 2011, 6 March: http://www.digitalmars.com/d/archives/digitalmars/D/learn/How_do_you_use_BinaryHeap_with_Array_or_just_make_a_growable_heap_25928.html 2009, 27 April: http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.html From those threads, I found that the reason might be related to the fact that the isRandomAccessRange template returns false when used with an Array!(T) object, for example this ---------------------------------------- import std.range; import std.container; void main(){ pragma(msg,isRandomAccessRange!(Array!(uint))); } ---------------------------------------- prints out false during compilation. Is there any way to use Array!(T) with a BinaryHeap, or any other way to have a growable BinaryHeap?Okay, I might on the wrong track, but part of the reason that the isRandomAccessRange template fails might be because, while Array!(T) internally uses a Range, it doesn't itself actually provide the save() and popBack() functions that a Range does?
Nov 13 2011
On Sunday, November 13, 2011 23:12:30 SimonM wrote:Okay, I might on the wrong track, but part of the reason that the isRandomAccessRange template fails might be because, while Array!(T) internally uses a Range, it doesn't itself actually provide the save() and popBack() functions that a Range does?A std.container.Array is not a range. It's a container. Yes, it uses an arary internally, which _ is_ a range, but it controls that memory and doesn't given out slices of that internal array. If you want a range over an Array, then slice it. - Jonathan M Davis
Nov 13 2011
On 2011/11/13 23:22 PM, Jonathan M Davis wrote:On Sunday, November 13, 2011 23:12:30 SimonM wrote:Okay, that makes sense, but it seems that BinaryHeap should be able to work with a Range or a Container, as the documentation states: "If Store is a range, the BinaryHeap cannot grow beyond the size of that range. If Store is a container that supports insertBack, the BinaryHeap may grow by adding elements to the container." Yet, nothing I try seems to work: ---------------------------------------- import std.range; import std.container; void main(){ // use dynamic array to create BinaryHeap int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; auto heapA = BinaryHeap!(int[])(a); //heapify(a); // use Array!(T) struct to create BinaryHeap auto b = Array!(int)(a); // The following lines both fail to compile with: // Error: this._store()[this._length()] is not an lvalue //auto heapB = BinaryHeap!(Array!(int))(b); //auto heapB = heapify(b); // Try to use a Range, but the following lines both fail to compile with: //Error: function std.container.Array!(int).Array.Range.opSlice (uint a, uint b) is not callable using argument types () //auto heapB = BinaryHeap!(Array!(int).Range)(b[]); //auto heapB = heapify(b[]); } ---------------------------------------- What am I doing wrong?Okay, I might on the wrong track, but part of the reason that the isRandomAccessRange template fails might be because, while Array!(T) internally uses a Range, it doesn't itself actually provide the save() and popBack() functions that a Range does?A std.container.Array is not a range. It's a container. Yes, it uses an arary internally, which _ is_ a range, but it controls that memory and doesn't given out slices of that internal array. If you want a range over an Array, then slice it. - Jonathan M Davis
Nov 13 2011
On Monday, November 14, 2011 01:25:58 SimonM wrote:What am I doing wrong?I don't know. I've never used BinaryHeap. I'd have to study it. I just noticed that you were trying to use treat Array as a range, which isn't going to work (regardless of whatever BinaryHeap does), so I tried to help you on that count. - Jonathan M Davis
Nov 13 2011
On 2011/11/14 01:55 AM, Jonathan M Davis wrote:On Monday, November 14, 2011 01:25:58 SimonM wrote:Well it definitely helps; and now I understand it better as well, so thanks!What am I doing wrong?I don't know. I've never used BinaryHeap. I'd have to study it. I just noticed that you were trying to use treat Array as a range, which isn't going to work (regardless of whatever BinaryHeap does), so I tried to help you on that count. - Jonathan M Davis
Nov 13 2011
SimonM:2009, 27 April: http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.htmlSee the working version: http://rosettacode.org/wiki/Huffman_coding#D Bye, bearophile
Nov 13 2011
On 2011/11/14 02:10 AM, bearophile wrote:SimonM:Okay, I looked at the example, and it seems that the only reason it works is because that piece of code never requires the array's length to grow larger than it's initial length (at the start of the loop, 2 elements are taken out, and at the end, only one is inserted back in). If I try using a BinaryHeap with a range, then, like the documentation mentions, I can't grow that BinaryHeap any larger than it's initial size, because I got the following error: "Cannot grow a heap created over a range". But somehow I can't get it working with an Array!(T) like the documentation implies it should be capable of?2009, 27 April: http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.htmlSee the working version: http://rosettacode.org/wiki/Huffman_coding#D Bye, bearophile
Nov 13 2011
On Monday, 14 November 2011 at 06:15:18 UTC, SimonM wrote:On 2011/11/14 02:10 AM, bearophile wrote:Is this problem resolved? I cannot produce a growable BinaryHeap myself.SimonM:Okay, I looked at the example, and it seems that the only reason it works is because that piece of code never requires the array's length to grow larger than it's initial length (at the start of the loop, 2 elements are taken out, and at the end, only one is inserted back in). If I try using a BinaryHeap with a range, then, like the documentation mentions, I can't grow that BinaryHeap any larger than it's initial size, because I got the following error: "Cannot grow a heap created over a range". But somehow I can't get it working with an Array!(T) like the documentation implies it should be capable of?2009, 27 April: http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.htmlSee the working version: http://rosettacode.org/wiki/Huffman_coding#D Bye, bearophile
Jun 22 2013
On Saturday, 22 June 2013 at 07:48:25 UTC, qznc wrote:On Monday, 14 November 2011 at 06:15:18 UTC, SimonM wrote:Ok, got it. Instead of using a dynamic array directly, wrapping it into a std.container.Array works. import std.container: Array, heapify; Foo[] arr = ...; auto wrapped = Array!Foo(arr); auto queue = heapify(wrapped); In general, other containers should work as well, since containers provide an insertBack method whereas the builtin arrays/ranges do not.On 2011/11/14 02:10 AM, bearophile wrote:Is this problem resolved? I cannot produce a growable BinaryHeap myself.SimonM:Okay, I looked at the example, and it seems that the only reason it works is because that piece of code never requires the array's length to grow larger than it's initial length (at the start of the loop, 2 elements are taken out, and at the end, only one is inserted back in). If I try using a BinaryHeap with a range, then, like the documentation mentions, I can't grow that BinaryHeap any larger than it's initial size, because I got the following error: "Cannot grow a heap created over a range". But somehow I can't get it working with an Array!(T) like the documentation implies it should be capable of?2009, 27 April: http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.htmlSee the working version: http://rosettacode.org/wiki/Huffman_coding#D Bye, bearophile
Jun 22 2013