Linked list as a bidirectional range? I have some questions...
Gary Willoughby via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
Mon Aug 11 13:22:11 PDT 2014
On Monday, 11 August 2014 at 20:02:38 UTC, H. S. Teoh via
Digitalmars-d-learn wrote:
> On Mon, Aug 11, 2014 at 07:35:04PM +0000, Gary Willoughby via
> Digitalmars-d-learn wrote:
>> On Monday, 11 August 2014 at 18:20:51 UTC, H. S. Teoh via
>> Digitalmars-d-learn wrote:
>> >If you make your linked list container the same thing as a
>> >range over
>> >it, then iterating over the range will empty the container as
>> >well,
>> >which generally isn't what you want.
>>
>> Yes but only if it's been implemented purely as an input
>> range. I was
>> wondering if it was implemented as a forward range. Forward
>> ranges
>> allow iteration without destroying the contents. I was
>> wondering how
>> the 'save' method of the forward range could be implemented
>> with a
>> linked list. If my understanding is correct this method yields
>> a copy
>> to iterate over and discard.
>
> Only if you explicitly call .save when you iterate over it. The
> following code does NOT preserve the original range:
>
> auto fwdRange = LinkedList(...);
> foreach (e; fwdRange) {
> ...
> }
>
> while the following does:
>
> auto fwdRange = LinkedList(...);
> foreach (e; fwdRange.save) {
> ...
> }
>
> which is uglier.
>
>
>> >It's much better to separate the container itself from ranges
>> >over
>> >the container. This then allows you to have separate container
>> >methods that return ranges of different types.
>>
>> That does answer it partially. This abstraction could return
>> ranges
>> over the nodes or items. but ultimately these have to expose
>> the
>> underlying data or provide a copy. (i.e. the 'save' method of
>> forward
>> ranges.)
>
> I don't understand your objection here. You just implement your
> .front
> method to return the appropriate type. The dirty details of how
> iteration is implemented need not be exposed.
>
>
>> Also iterating in reverse (which should be possible with a
>> doubly
>> linked list) such ranges will have to be bidirectional ranges.
>
> You could do that, but it's not necessary. Nothing stops you
> from
> implementing, say, a byDataReverse() method that returns a
> forward range
> that just happens to return items from the original list in
> reverse
> order.
>
>
>> These questions are all kind of inter-linked. I want to iterate
>> forward and back through the list and if possible provide a
>> nice
>> public interface. It doesn't seem right to expose the nodes as
>> that
>> smells of a leaking abstraction. Hiding the nodes make it
>> harder to
>> iterate without a nice interface i.e. bidirectional range.
>
> Your original question asked for a range that iterates over
> either data
> items or nodes, so what's the problem with "exposing the
> nodes"? If you
> didn't want the range to iterate over the nodes in the first
> place, then
> don't implement byNodes(), that's all.
>
>
>> Ranges are nice but the (forward range's) 'save' method needs
>> careful
>> consideration.
>
> All you have to do in .save is to return a copy of the range,
> which is
> *not* the same thing as a copy of the container. (Again, this
> shows that
> it's a bad idea to conflate the container with a range over its
> elements.)
>
>
>> opApply is nice but i can't see a way to overload it for
>> reverse
>> iteration.
>
> opApplyReverse.
>
> Anyway, clearly we're not understanding each other, so let me
> present
> some concrete code so that we aren't just talking past each
> other:
>
> // This is the container. It is NOT a range of any sort.
> class LinkedList(T) {
> private class Node {
> T data;
> Node next, prev;
> }
> Node head, tail;
>
> /**
> * Returns: A range over the data in the container in
> * forward order.
> */
> auto byData() {
> // This is the range that the user will use to
> // iterate over the container's contents.
> struct Result {
> Node current;
> @property ref T front() {
> // N.B.: no Node object is
> // exposed to the public, they
> // only see the data.
> return current.data;
> }
> @property bool empty() {
> return current is null;
> }
> void popFront() {
> current = current.next;
> }
> @property Result save() {
> // N.B.: no copying of data
> // needed; no container
> // duplication needed.
> return Result(current);
> }
> }
> static assert(isForwardRange!Result);
>
> return Result(head);
> }
>
> /**
> * Returns: A range over the data in the container in
> * reverse order.
> */
> auto byDataReverse() {
> // Yes I know, most of this code is
> // copy-n-pasted from byData(); but the whole
> // point is to explain what I mean, not to write
> // the most polished code. Factoring out the
> // common parts is left as an exercise for the
> // reader.
> struct Result {
> Node current;
> @property ref T front() {
> // N.B.: no Node object is
> // exposed to the public, they
> // only see the data.
> return current.data;
> }
> @property bool empty() {
> return current is null;
> }
> void popFront() {
> current = current.prev;
> }
> @property Result save() {
> // N.B.: no copying of data
> // needed; no container
> // duplication needed.
> return Result(current);
> }
> }
> static assert(isForwardRange!Result);
>
> return Result(tail);
> }
>
> // ... add whatever other methods you want for
> // manipulating the linked list.
> }
>
>
> T
That..is..awesome! and much more simpler than i thought. I get it
now, thanks. Is this pattern repeated in phobos?
More information about the Digitalmars-d-learn
mailing list