www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Why after writeln the binaryHeap become empty?

reply lili <akozhao tencent.com> writes:
Hi Guys:
    see this code
~~~
     int[] ar = [1,2,3,4,52,34,22];
     auto h = heapify(ar);
     assert(h.length() == ar.length);
     writeln("h:",h);
     assert(h.empty());
~~~
dmd v2.086.0  run all assert passed. Why?
Jun 18 2019
next sibling parent reply Johannes Loher <johannes.loher fg4f.de> writes:
Am 18.06.19 um 17:45 schrieb lili:

 Hi Guys:
    see this code
 ~~~
     int[] ar = [1,2,3,4,52,34,22];
     auto h = heapify(ar);
     assert(h.length() == ar.length);
     writeln("h:",h);
     assert(h.empty());
 ~~~
 dmd v2.086.0  run all assert passed. Why?


The result of heapify is a BinaryHeap, which is a range. writeln
basically prints ranges by iterating over them and printing each element
(except for the types which are special cased, such as dynamic arrays
etc.). However, ranges are consumed by iterating over them, which
explains the behavior because writeln is not special cased for BinaryHeaps.

In order to avoid this, you can make a copy of the BinaryHeap before
printing it:

```
import std;

void main()
{
    int[] ar = [1, 2, 3, 4, 52, 34, 22];
    auto h = heapify(ar);
    assert(h.length() == ar.length);
    writeln("h:", h.dup);
    assert(!h.empty());
}
```

Funnily enough, BinaryHeap does not implement a "save" method, which is
the usual way of making ranges copiable, i.e. making them ForwardRanges.
In this case I believe save could even simply be an alias to dup.
Jun 18 2019
parent reply lili <akozhao tencent.com> writes:
On Tuesday, 18 June 2019 at 17:25:51 UTC, Johannes Loher wrote:

 The result of heapify is a BinaryHeap, which is a range. writeln
 basically prints ranges by iterating over them and printing 
 each element
 (except for the types which are special cased, such as dynamic 
 arrays
 etc.). However, ranges are consumed by iterating over them, 
 which
 explains the behavior because writeln is not special cased for 
 BinaryHeaps.

 Funnily enough, BinaryHeap does not implement a "save" method, 
 which is the usual way of making ranges copiable, i.e. making 
 them ForwardRanges. In this case I believe save could even 
 simply be an alias to dup.


Do you known reason for why Dlang Range are consumed by iterating 
over them. I this design is strange.
Jun 18 2019
parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Tuesday, June 18, 2019 10:27:46 PM MDT lili via Digitalmars-d-learn 
wrote:

 On Tuesday, 18 June 2019 at 17:25:51 UTC, Johannes Loher wrote:

 The result of heapify is a BinaryHeap, which is a range. writeln
 basically prints ranges by iterating over them and printing
 each element
 (except for the types which are special cased, such as dynamic
 arrays
 etc.). However, ranges are consumed by iterating over them,
 which
 explains the behavior because writeln is not special cased for
 BinaryHeaps.

 Funnily enough, BinaryHeap does not implement a "save" method,
 which is the usual way of making ranges copiable, i.e. making
 them ForwardRanges. In this case I believe save could even
 simply be an alias to dup.


 Do you known reason for why Dlang Range are consumed by iterating
 over them. I this design is strange.


If you want an overview of ranges, you can watch this:

https://www.youtube.com/watch?v=A8Btr8TPJ8c

You can also read this:

http://ddili.org/ders/d.en/ranges.html

- Jonathan M Davis
Jun 18 2019
parent Mike Parker <aldacron gmail.com> writes:
On Wednesday, 19 June 2019 at 06:00:28 UTC, Jonathan M Davis 
wrote:

 On Tuesday, June 18, 2019 10:27:46 PM MDT lili via



 Do you known reason for why Dlang Range are consumed by 
 iterating over them. I this design is strange.


 If you want an overview of ranges, you can watch this:

 https://www.youtube.com/watch?v=A8Btr8TPJ8c

 You can also read this:

 http://ddili.org/ders/d.en/ranges.html

 - Jonathan M Davis


And this excerpt from Learning D:

https://hub.packtpub.com/understanding-ranges/
Jun 18 2019
prev sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Tuesday, June 18, 2019 9:45:33 AM MDT lili via Digitalmars-d-learn wrote:

 Hi Guys:
     see this code
 ~~~
      int[] ar = [1,2,3,4,52,34,22];
      auto h = heapify(ar);
      assert(h.length() == ar.length);
      writeln("h:",h);
      assert(h.empty());
 ~~~
 dmd v2.086.0  run all assert passed. Why?


Looking at std/container/binaryheap.d, heapify returns the type BinaryHeap
which provides the API for an input range but no toString. As such, writeln
likely uses the range API to read the elements and print them. And that's
going to pop all of the elements off in the process. In general, if you pass
a range to something and you don't want it to be consumed, then you need to
call save on it so that you pass a copy (for many ranges, copying them is
equivalent to calling save on them, but that's not part of the range API,
and it's not true for all ranges). However, from the looks of it, the
BinaryHeap is a just a basic input range, not a forward range, so it doesn't
have save. That means that reading it will always consume it. Looking over
BinaryHeap, I don't think that it's actually possible to iterate through its
elements without removing them from the BinaryHeap. As such, you can't print
them without removing them from the BinaryHeap.

- Jonathan M Davis
Jun 18 2019