Hi.  To describe my background really quickly, I'm a CS student with experience mostly in Java and Python.  (I've done some C++ work, but not a lot.)
Basically, I have two really newbish questions that I haven't been able to figure out from the library and language references, and I'm sure the answers
are perfectly obvious, so apologies in advance.

I'm writing a few collections classes in D (just to get the feel for the language; I realize that there are probably much better implementations available
from the dsource community, or w/e) and right now, I'm writing a linked list template class.  ( 'linkedList(E)' )

First question:  toString().  is this handled exactly the way that it is in Java?  I've written a toString method for my class, I'll post it below.  I can
call this method, and it works perfectly, if called specifically.

linkedList!(int) list = new linkedList!(int)();
writeln(list.toString());  //this works perfectly (if I add elements to the list, the results are the same)

writeln(list);  //this fails(at compile time) with a godawfully long error:

"/usr/local/include/d/phobos2/std/format.d(1455): Error: template std.format.formatValue(Writer,T,Char) if (is(const(T) == const(void[])))
formatValue(Writer,T,Char) if (is(const(T) == const(void[]))) matches more than one template declaration,
/usr/local/include/d/phobos2/std/format.d(1126):formatValue(Writer,T,Char) if (isInputRange!(T) && !isSomeChar!(ElementType!(T))) and
/usr/local/include/d/phobos2/std/format.d(1297):formatValue(Writer,T,Char) if (is(T == class))"

Anyway, my toString method is as follows:

public string toString(){


        if (head !is null){
            char[] outString = "[".dup;
            llNode cursor = head;  //llNode is a private node class
            while(cursor.next !is  null){
                outString = outString ~ text(cursor.datum) ~", ";
                cursor = cursor.next;
            }
            outString = outString ~ text(cursor.datum) ~ "]";
            return outString.idup;
        }
        else{
            return "[]";
        }


    }

I guess that I'm asking if write() calls an object's toString method, or if there's some other behavior going on that I'm ignorant of.


Question 2:

This is more a broad request for clarification, than a specific question.  I'm trying to understand the range interfaces.  I'm trying to make this
linkedList class implement the InputRange interface (among others).  I'm pretty sure that I've got opApply, opIndex, and opSlice figured out, but I can't
for the life of me figure out exactly what front(), popFront(), and empty() are supposed to be doing.  (I realize that the opX functions aren't part of the
InputRange interface.)  Is popFront supposed to delete the actual front element from the list?  Or is it supposed to represent some kind of internal
pointer that is there solely for the purpose of range functionality?  If the latter, how should the pointer get reset after it has gotten to the end once?
Should the pointer even need to be reset, or is popFront supposed to only cycle through once during the entire lifetime of the range object?

I really have tried to answer this question for myself, but I guess that I need more experience to actually be able to understand all of the documentation
the way that it is currently written.  Also, I've attached the d source files in question. One is the linkedList class, one is the test executable that I'm
trying to test it with.  linkedList.d should be in a directory mwcollections (since i'm trying to set up mwcollections as a module).  I'd have just sent an
archive file with this directory structure already in place, but I wouldn't want anyone to think that I was slipping them a virus.  :)  (though 4KB is a
little small to be a virus.)  Feel free to crack jokes at my poor coding style, I'm not really much more than an amateur at this.  I don't know if this is
relevant or not, but I'm using the digitalmars dmd compiler version 2.050, on a gentoo linux system.

Thanks in advance.

Mike W

Michael Woods:

> First question:  toString().  is this handled exactly the way that it is in Java?  I've written a toString method for my class, I'll post it below.  I can
> call this method, and it works perfectly, if called specifically.
> 
> linkedList!(int) list = new linkedList!(int)();
> writeln(list.toString());  //this works perfectly (if I add elements to the list, the results are the same)
> 
> writeln(list);  //this fails(at compile time) with a godawfully long error:

Welcome here. A reduced test case:


import std.stdio: writeln;
import std.range: InputRange;

class LinkedList(T) : InputRange!T {
    T front() { return T.init; }
    T moveFront() { return T.init; }
    void popFront() {}
    bool empty() { return true; }
    int opApply(int delegate(ref T) dg) { return 0; }
    int opApply(int delegate(ref size_t, ref T) dg) { return 0; }
    override string toString() { return "foo"; }
}
void main() {
    LinkedList!(int) list = new LinkedList!int;
    writeln(list);
    //writeln(list.toString());
}


Bye,
bearophile

Hello and welcome.

The toString does work the same as it does in Java,  I suggest using override.

override string toString();

Your error actually indicates a bug in Phobos. It has a special print function for classes and for an input range. These are conflicting with each other and has nothing to do with your toString. Luckily once your container is properly created, you won't have this issue. So I will file the bug sometime.

The first thing to note is that you are creating a container[1] and not an InputRange[2]. The distinction here is that a Range is consumed, you don't iterate over them multiple times. A container on the other hand has different access requirements. (Documentation on Containers is a little messed up.)

Generally opApply is not used if you are building a Range, but does have its uses and I believe has priority in a foreach statement.

To build on the example from bearophile You would have something like this with your selection of Container functions:

import std.stdio: writeln;

class LinkedList(T) {
   override string toString() { return "foo"; }

   struct Range(T) {
      T front() { return T.init; }
      T moveFront() { return T.init; }
      void popFront() {}
      bool empty() { return true; }
   }

   Range!T opSlice() {
      Range!T r;
      return r;
   }
}
void main() {
    LinkedList!(int) list = new LinkedList!int;
    writeln(list);
    //writeln(list.toString());
}


1. http://digitalmars.com/d/2.0/phobos/std_container.html 2. http://digitalmars.com/d/2.0/phobos/std_range.html

Thanks for your replies, bearophile and Jesse Phillips.  :)

Jesse, that makes a lot more sense, now.  Thanks a lot for clearing that up for me.

Mike W

Michael Woods Wrote:

> Thanks for your replies, bearophile and Jesse Phillips.  :)
> 
> Jesse, that makes a lot more sense, now.  Thanks a lot for clearing that up for me.
> 
> Mike W

I kept making the mistake of trying to use containers as a range too (end up creating a reset function to bring it back to the beginning).

Also note that the usage for getting a range will look like:

foreach(item; myData[]) ...


And if you want to track it http://d.puremagic.com/issues/show_bug.cgi?id=5154

On Mon, 1 Nov 2010 20:02:14 +0000 (UTC)
Michael Woods <alienhunter3@gmail.com> wrote:


> I guess that I'm asking if write() calls an object's toString method

Exactly.

> Question 2:
> 
> This is more a broad request for clarification, than a specific question.  I'm trying to understand the range interfaces.  I'm trying to make this
> linkedList class implement the InputRange interface (among others).  I'm pretty sure that I've got opApply, opIndex, and opSlice figured out, but I can't
> for the life of me figure out exactly what front(), popFront(), and empty() are supposed to be doing.  (I realize that the opX functions aren't part of the
> InputRange interface.)  Is popFront supposed to delete the actual front element from the list?  Or is it supposed to represent some kind of internal
> pointer that is there solely for the purpose of range functionality?  If the latter, how should the pointer get reset after it has gotten to the end once?
> Should the pointer even need to be reset, or is popFront supposed to only cycle through once during the entire lifetime of the range object?

I'm not 100% sure because I'm also a D noob, rather projecting knowledge from other PLs -- so take my words with precaution. [Please, D gurus, tell if what follows is ok.]

If I'm right, the point of ranges is to offer kinds of particular views on all, a part, or an aspect of a collection; without having to create a separate collection just for that. Typical use is for traversal (iteration). Since you know python, its iterators (and generators) are kinds of ranges. Eg you can write an iterator to traverse a list in reverse order, or every third element -- without creating new lists for that. You can also make an iterator or generator on a "virtual list", eg generating squares of ints in a given range.

front(), popFront(), and empty() together form a way to implement a sequential iterator on a collection. [But I must admit it really does not fit my POV on the topic -- this trio strongly smells functional :-) and actually basically models a linked list -- I'm certain its designer has a heavy Lisp baggage! I would rather have a hasNext() and next() duo.]
Now, their working is simply to allow moving across elements, so no popFront() does not pop. Examples:
	routine		dynarray	list
	popFront	inc(ptr)	current = current.next
	front()		*ptr		current.element	(possibly dereferenced)
	empty()		length == 0	length == 0 (maintained as field)
On a "true" linked list where every node implements the properties & methods of a list, then popFront is returning the second node, meaning the head of the rest: l = l.next.

Hope most of this is correct (critics welcome).


Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com

On Monday 01 November 2010 18:05:19 spir wrote:
> On Mon, 1 Nov 2010 20:02:14 +0000 (UTC)
> 
> Michael Woods <alienhunter3@gmail.com> wrote:
> > I guess that I'm asking if write() calls an object's toString method
> 
> Exactly.
> 
> > Question 2:
> > 
> > This is more a broad request for clarification, than a specific question.
> >  I'm trying to understand the range interfaces.  I'm trying to make this
> > linkedList class implement the InputRange interface (among others).  I'm
> > pretty sure that I've got opApply, opIndex, and opSlice figured out, but
> > I can't for the life of me figure out exactly what front(), popFront(),
> > and empty() are supposed to be doing.  (I realize that the opX functions
> > aren't part of the InputRange interface.)  Is popFront supposed to
> > delete the actual front element from the list?  Or is it supposed to
> > represent some kind of internal pointer that is there solely for the
> > purpose of range functionality?  If the latter, how should the pointer
> > get reset after it has gotten to the end once? Should the pointer even
> > need to be reset, or is popFront supposed to only cycle through once
> > during the entire lifetime of the range object?
> 
> I'm not 100% sure because I'm also a D noob, rather projecting knowledge from other PLs -- so take my words with precaution. [Please, D gurus, tell if what follows is ok.]
> 
> If I'm right, the point of ranges is to offer kinds of particular views on all, a part, or an aspect of a collection; without having to create a separate collection just for that. Typical use is for traversal (iteration). Since you know python, its iterators (and generators) are kinds of ranges. Eg you can write an iterator to traverse a list in reverse order, or every third element -- without creating new lists for that. You can also make an iterator or generator on a "virtual list", eg generating squares of ints in a given range.
> 
> front(), popFront(), and empty() together form a way to implement a
> sequential iterator on a collection. [But I must admit it really does not
> fit my POV on the topic -- this trio strongly smells functional :-) and
> actually basically models a linked list -- I'm certain its designer has a
> heavy Lisp baggage! I would rather have a hasNext() and next() duo.] Now,
> their working is simply to allow moving across elements, so no popFront()
> does not pop. Examples: routine		dynarray	list
> 	popFront	inc(ptr)	current = current.next
> 	front()		*ptr		current.element	(possibly dereferenced)
> 	empty()		length == 0	length == 0 (maintained as field)
> On a "true" linked list where every node implements the properties &
> methods of a list, then popFront is returning the second node, meaning the
> head of the rest: l = l.next.
> 
> Hope most of this is correct (critics welcome).

The best place to start learning about ranges is probably here: http://www.informit.com/articles/article.aspx?p=1407357

front, popFront(), and empty make perfect sense as they are and work quite well. hasNext() and next() have the serious drawback of mixing iterating through the range and getting an element in it. It's one of the serious flaws in Java's iterators. It's far better to have getting the current or front element be separate from moving or  popping the next one.

In any case, you can use ranges in a manner similar to lisp's slists, but they're definitely more flexible than that, since they're an abstraction rather than a container. And ultimately, there isn't really anything functional about them. They just allow for you to use them in a manner similar to slists which are heavily used in functional languages.

Ranges are extremely powerful and generally are _way_ better than iterators (though there are a few cases where they become more awkward than iterators).

- Jonathan M Davis

On Mon, 1 Nov 2010 18:47:38 -0700
Jonathan M Davis <jmdavisProg@gmx.com> wrote:

> The best place to start learning about ranges is probably here: http://www.informit.com/articles/article.aspx?p=1407357
> 
> front, popFront(), and empty make perfect sense as they are and work quite well. hasNext() and next() have the serious drawback of mixing iterating through the range and getting an element in it. It's one of the serious flaws in Java's iterators. It's far better to have getting the current or front element be separate from moving or  popping the next one.

Thank for the pointer.
Note That I know exactly nothing of Java. In fact, I used this scheme and those names spontaneously to implement traversal of custom structs in Oberon (that has no such notion).
There's a point I don't understand in your argument: "...the serious drawback of mixing iterating through the range and getting an element in it". Isn't this precisely what popFront() does, stepping and returning an element? Or is "pop" in "popFront" misleading? (I've followed your pointer, but the site is so designed that the article is spread over 15 pages!)
To move forward without popping, you'd need a kind of step() method that just follows the next pointer; really complementary to front(). Or is there something I misunderstand? But since typical use is iteration, does it make sense to separate stepping and reading?
I now realise that my previous comment on the method trio vs my point of view is wrong; the functionality is the same, done the same way, only naming reveals a different pov: next() is popFront() seen differently, hasNext() is !empty().

Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com

spir Wrote:

> I'm certain its designer has a heavy Lisp baggage! I would rather have a hasNext() and next() duo.]

To build on what Jonathon wrote. There are three benefits that I have enjoyed having front and popFront instead of the next and hasNext.

The first is simply that if I want to make use of the element multiple times I don't need to find storage for it, I can just call front every time I need it.

The second is when building a range you don't need to look ahead to find out if another element is available. This means I don't have to store the next value along with the current value. For example std.algorithm has a function filter. You provide it with a Range and ask it to only return values that meet some criteria. Since the elements that will be returned aren't going to be the number in the original Range it can't just take its length.

And with that you don't end up with unneeded calculations if the next element isn't needed.

The one annoying thing with this has been the need to initialize the Range (calling popFront after creating the range). Since the first item may not be an item that meets the criteria, or that there are any items, the range needs to be advanced so that it finds the correct element.

On Monday 01 November 2010 19:21:27 spir wrote:
> On Mon, 1 Nov 2010 18:47:38 -0700
> 
> Jonathan M Davis <jmdavisProg@gmx.com> wrote:
> > The best place to start learning about ranges is probably here: http://www.informit.com/articles/article.aspx?p=1407357
> > 
> > front, popFront(), and empty make perfect sense as they are and work quite well. hasNext() and next() have the serious drawback of mixing iterating through the range and getting an element in it. It's one of the serious flaws in Java's iterators. It's far better to have getting the current or front element be separate from moving or  popping the next one.
> 
> Thank for the pointer.
> Note That I know exactly nothing of Java. In fact, I used this scheme and
> those names spontaneously to implement traversal of custom structs in
> Oberon (that has no such notion). There's a point I don't understand in
> your argument: "...the serious drawback of mixing iterating through the
> range and getting an element in it". Isn't this precisely what popFront()
> does, stepping and returning an element? Or is "pop" in "popFront"
> misleading? (I've followed your pointer, but the site is so designed that
> the article is spread over 15 pages!) To move forward without popping,
> you'd need a kind of step() method that just follows the next pointer;
> really complementary to front(). Or is there something I misunderstand?
> But since typical use is iteration, does it make sense to separate
> stepping and reading? I now realise that my previous comment on the method
> trio vs my point of view is wrong; the functionality is the same, done the
> same way, only naming reveals a different pov: next() is popFront() seen
> differently, hasNext() is !empty().

In C++, iterators are effectively pointers. ++ increments, -- decrements, and * dereferences the element that it currently points to. The same goes for C#, except that they didn't overload * to get the current element but rather used a property function (Current IIRC, but I haven't used C# in a while). In both cases, accessing the current element does not move the iterator. Moving the iterator is completely separate from accessing what it points to.

In Java, on the other hand, they have hasNext(), hasPrev(), next(), and previous(), and the iterator doesn't point _at_ a particular element but rather _between_ them. So, hasNext() and hasPrevious() return a bool telling you whether there is a next or previous element respectively. next() returns the next element and moves the iterator whereas previous() returns the previous iterator and moves the iterator backwards. It means that you have to save the element every time that you access the next one rather than being able to use the iterator to get it again. It also makes it essentially impossible (or extremely ugly) to try and designate a range of any kind with iterators, since they don't actually point _at_ elements at using iterators alters them. Of course, Java didn't end up using iterators in a fashion that algorithms could be used for them (like C++ did), but it would be a pain even if you tried due to the lack of separation between moving an iterator and accessing what it refers to.

D uses ranges, which are at their most basic a pair of iterators but which are far more flexible than that, since you don't have to actually use iterators for their implementation. Things like infinite ranges become possible, which aren't really doable in the same way with iterators. They also completely avoid the issues related to passing iterators in the wrong order or which point to different containers.

There are various types of ranges, each with a set of functions that they must have, but the most basic is an InputIterator which has front, popFront(), and empty. front gives the first element in the range without altering the range. popFront() pops the first element from the range, making the next elment (if any) the first element in the range. popFront() is void and does not return what it pops. empty indicates whether there are any more elements left in the range. Using front when a range is empty will generally result in an exception being thrown, because there is no first element in the range.

The term "pop" does _not_ mean that an element is returned but that it is removed from the range. This is true for pretty much anything that uses a pop function in any language - stacks, lists, etc. It _is_ true that many implementations choose to have pop return the element which is popped, but that's an implementation detail. The term pop merely indicates that an element is removed from an end of a range or container.

- Jonathan M Davis