Linked list as a bidirectional range? I have some questions...

[H. S. Teoh via Digitalmars-d-learn]

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

-- 
Trying to define yourself is like trying to bite your own teeth. -- Alan Watts