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?
