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