www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - couple of really noob questions (ranges, toString)

reply Michael Woods <alienhunter3 gmail.com> writes:
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
begin 644 testlist.d
M:6UP;W)T('-T9"YS=&1I;SL*:6UP;W)T('-T9"YR86YG93L*:6UP;W)T(&UW
M8V]L;&5C=&EO;G,N;&EN:V5D3&ES=#L*"G9O:60 ;6%I;BAS=')I;F=;72!A
M<F=S*7L*"B` (`H ("` ;&EN:V5D3&ES="$H:6YT*2!L:7-T(#T ;F5W(&QI

M=70H,BD["B` ("!L:7-T+G!U=" S*3L*("` (`H ("` :6YT6S-=('D /2!;
M-"P -2P -ET["B` ("!L:7-T+G!U="AY*3L*("` (`H ("` +RH*("` (&9O
M<F5A8V H:6YT(&L[>"E[("`O+VIU<W0 =&\ 9&5M;VYS=')A=&4 =&AA="!O
M<$%P<&QY(&ES('=O<FMI;F<N"B` ("` ("` =W)I=&5L;BAK*3L*("` ('T*
M("` ("HO"B` ("`*("` ('=R:71E;&XH;&ES="YT;U-T<FEN9R I*3L ("`O
M+V-O;7!I;&5S"B` ("\O('=R:71E;&XH;&ES="D[("` ("` ("` ("` ("`O
7+V1O97-N)W0 8V]M<&EL90H ("`*?0H`
`
end
begin 644 linkedList.d
M;6]D=6QE(&UW8V]L;&5C=&EO;G,N;&EN:V5D3&ES=#L*"FEM<&]R="!S=&0N
M<W1D:6\["FEM<&]R="!S=&0N<F%N9V4["FEM<&]R="!S=&0N8V]N=CL*"G!U
M8FQI8R!C;&%S<R!L:6YK961,:7-T*$4I(#H 26YP=71286YG92$H12E["B` 
M("`*("` ("\O<')I=F%T92!N;V1E(&-L87-S. H ("` "B` ("!P<FEV871E
M(&-L87-S(&QL3F]D92!["B` ("` ("` "B` ("` ("` <'5B;&EC($4 9&%T
M=6T["B` ("` ("` "B` ("` ("` <'5B;&EC(&QL3F]D92!N97AT.PH ("` 
M("` (`H ("` ("` ('!U8FQI8R!L;$YO9&4 <')E=FEO=7,["B` ("` ("` 
M"B` ("` ("` <'5B;&EC('1H:7,H12!?9&%T=6TL(&QL3F]D92!?;F5X="P 
M;&Q.;V1E(%]P<F5V:6]U<RE["B` ("` ("` ("` (`H ("` ("` ("` ("!D
M871U;2`](%]D871U;3L*("` ("` ("` ("` "B` ("` ("` ("` (&YE>'0 
M/2!?;F5X=#L*("` ("` ("` ("` "B` ("` ("` ("` ('!R979I;W5S(#T 
M7W!R979I;W5S.PH ("` ("` ("` ("`*("` ("` ("!]"B` ("` ("` "B` 
M("!]"B` ("`*("` ("\O:6YT97)N86P =F%R<PH ("` "B` ("!L;$YO9&4 
M:&5A9#L*("` (`H ("` ;&Q.;V1E('1A:6P["B` ("`*("` ('5I;G0 <VEZ
M93L*("` (`H ("` ;&Q.;V1E(&-U<G)E;G0["B` ("`*("` (`H ("` "B` 
M("`O+V-O;G-T<G5C=&]R"B` ("`*("` ('!U8FQI8R!T:&ES*"E["B` ("` 

M(&YU;&P["B` ("` ("` "B` ("` ("` =&%I;"`](&YU;&P["B` ("` ("` 
M"B` ("` ("!C=7)R96YT(#T :&5A9#L*("` ("` ("`*("` ('T*("` (`H 
M("` "B` ("`O+W!U8FQI8R!M96UB97( 9G5N8W1I;VYS"B` ("`*("` ('9O
M:60 <'5T*$4 7VEN<'5T*7L*("` ("` ("`*("` ("` ("!I9BAH96%D(&ES
M(&YU;&PI>PH ("` ("` ("` ("!H96%D(#T ;F5W(&QL3F]D92A?:6YP=70L
M(&YU;&PL(&YU;&PI.PH ("` ("` ("` ("!S:7IE*RL["B` ("` ("` ("` 
M('1A:6P /2!H96%D.PH ("` ("` ("` ("!C=7)R96YT(#T :&5A9#L*("` 
M("` ("` ("` "B` ("` ("` ?0H ("` ("` (`H ("` ("` (&5L<V5["B` 
M("` ("` ("` (`H ("` ("` ("` ("!T86EL+FYE>'0 /2!N97< ;&Q.;V1E
M*%]I;G!U="P ;G5L;"P =&%I;"D["B` ("` ("` ("` (`H ("` ("` ("` 
M("!T86EL(#T =&%I;"YN97AT.PH ("` ("` ("` ("`*("` ("` ("` ("` 
M<VEZ92LK.PH ("` ("` ("` ("`*("` ("` ("!]"B` ("` ("` "B` ("!]
M"B` ("`*("` ('!U8FQI8R!V;VED('!U="A%6UT 7VEN<'5T*7L*("` ("` 
M("`*("` ("` ("!F;W)E86-H*$4 :SL 7VEN<'5T*7L*("` ("` ("` ("` 
M<'5T*&LI.PH ("` ("` ('T*("` ("` ("`*("` ('T*("` (`H ("` <'5B
M;&EC($4 9G)O;G0H*2!["B` ("` ("` <F5T=7)N(&-U<G)E;G0N9&%T=6T[
M"B` ("!]"B` ("`*("` ('!U8FQI8R!%(&UO=F5&<F]N=" I('L <F5T=7)N
M(&AE860N9&%T=6T[?0H ("` "B` ("!P=6)L:6, =F]I9"!P;W!&<F]N=" I
M('L*("` ("` ("!C=7)R96YT(#T 8W5R<F5N="YN97AT.PH ("` ?3L*("` 
M(`H ("` <'5B;&EC(&)O;VP 96UP='DH*2![(`H ("` ("` ("` ("!I9B`H
M8W5R<F5N="!I<R!N=6QL*7L*("` ("` ("` ("` ("` (')E='5R;B!T<G5E
M.PH ("` ("` ("` ("!]"B` ("` ("` ("` (&5L<V5["B` ("` ("` ("` 
M("` ("!R971U<FX 9F%L<V4["B` ("` ("` ("` ('T*("` ('T*("` (`H 
M("` <'5B;&EC(&EN="!O<$%P<&QY*&EN="!D96QE9V%T92AR968 12D 9&<I
M>R`*("` ("` ("`*("` ("` ("!I;G0 <F5S=6QT(#T ,#L*("` ("` ("!L
M;$YO9&4 8W5R<V]R(#T :&5A9#L*("` ("` ("!W:&EL92AC=7)S;W( (6ES
M(&YU;&PI>PH ("` ("` ("` ("!R97-U;'0 /2!D9RAC=7)S;W(N9&%T=6TI
M.PH ("` ("` ("` ("!I9BAR97-U;'0 (3T ,"E["B` ("` ("` ("` ("` 
M("!B<F5A:SL*("` ("` ("` ("` ?0H ("` ("` ("` ("!C=7)S;W(]8W5R
M<V]R+FYE>'0["B` ("` ("` ?2`*("` ("` (')E='5R;B!R97-U;'0["B` 
M("!]"B` ("`*("` ('!U8FQI8R!I;G0 ;W!!<'!L>2AI;G0 9&5L96=A=&4H
M<F5F('-I>F5?="P <F5F($4I(&1G*7L "B` ("` ("` :6YT(')E<W5L="`]


M*7L*("` ("` ("` ("` <F5S=6QT(#T 9&<H8W5R26YD97 L(&-U<G-O<BYD
M871U;2D["B` ("` ("` ("` (&EF*')E<W5L="`A/2`P*7L*("` ("` ("` 
M("` ("` (&)R96%K.PH ("` ("` ("` ("!]"B` ("` ("` ("` (&-U<G-O
M<CUC=7)S;W(N;F5X=#L*("` ("` ("` ("` 8W5R26YD97 K*SL*("` ("` 
M("!]"B` ("` ("!R971U<FX <F5S=6QT.PH ("` ?0H ("` "B` ("`*("` 
M(`H ("` <'5B;&EC($4 ;W!);F1E>"AS:7IE7W0 7VEN9&5X*7L*"B` ("` 
M("` :68 *%]I;F1E>"`\('-I>F4 )B8 7VEN9&5X(#X
M("` ("`*("` ("` ("` ("` ;&Q.;V1E(&-U<G-O<CL*("` ("` ("` ("` 
M:6YT(&-U<DEN9&5X.PH ("` ("` ("` ("`*("` ("` ("` ("` :68 *%]I
M;F1E>"`\('-I>F4O,BE["B` ("` ("` ("` ("` ("`*("` ("` ("` ("` 
M("` (&-U<G-O<B`](&AE860["B` ("` ("` ("` ("` ("!C=7));F1E>"`]

M>PH ("` ("` ("` ("` ("` ("` (&-U<G-O<B`](&-U<G-O<BYN97AT.PH 
M("` ("` ("` ("` ("` ("` (&-U<DEN9&5X*RL["B` ("` ("` ("` ("` 
M("!]"B` ("` ("` ("` ("` ("!R971U<FX 8W5R<V]R+F1A='5M.PH ("` 
M("` ("` ("!]"B` ("` ("` ("` (&5L<V5["B` ("` ("` ("` ("` ("!C
M=7)S;W( /2!T86EL.PH ("` ("` ("` ("` ("` 8W5R26YD97  /2!S:7IE
M+3$["B` ("` ("` ("` ("` ("!W:&EL92AC=7));F1E>"`A/2!?:6YD97 I
M>PH ("` ("` ("` ("` ("` ("` (&-U<G-O<B`](&-U<G-O<BYP<F5V:6]U
M<SL*("` ("` ("` ("` ("` ("` ("!C=7));F1E>"TM.PH ("` ("` ("` 
M("` ("` ?0H ("` ("` ("` ("` ("` <F5T=7)N(&-U<G-O<BYD871U;3L*
M("` ("` ("` ("` ?0H ("` ("` ('T*("` ("` ("!E;'-E>PH ("` ("` 
M("` ("!T:')O=R!N97< 17AC97!T:6]N*"));F1E>"!O=70 ;V8 8F]U;F1S
M+B(I.PH ("` ("` ('T*("` ("` ("`*("` ('T*("` (`H ("` <'5B;&EC
M(&QI;FME9$QI<W0A*$4I(&]P4VQI8V4H*7L*("` ("` ("!L:6YK961,:7-T
M(2A%*2!T96UP(#T ;F5W(&QI;FME9$QI<W0A*$4I*"D["B` ("` ("` ;&Q.
M;V1E(&-U<G-O<B`](&AE860["B` ("` ("` =VAI;&4H8W5R<V]R("%I<R!N
M=6QL*7L*("` ("` ("` ("` =&5M<"YP=70H8W5R<V]R+F1A='5M*3L*("` 
M("` ("` ("` 8W5R<V]R(#T 8W5R<V]R+FYE>'0["B` ("` ("` ?0H ("` 
M("` (')E='5R;B!T96UP.PH ("` ?0H ("` "B` ("!P=6)L:6, ;&EN:V5D
M3&ES="$H12D ;W!3;&EC92AS:7IE7W0 ;&]W+"!S:7IE7W0 :&EG:"E["B` 
M("` ("` "B` ("` ("` :68H;&]W(#X <VEZ92TQ('Q\(&AI9V  /B!S:7IE
M+3$ ?'P ;&]W(#X :&EG:"E["B` ("` ("` ("` ('1H<F]W(&YE=R!%>&-E
M<'1I;VXH(DEN9&5X*&5S*2!O=70 ;V8 8F]U;F1S+B(I.PH ("` ("` ('T*
M("` ("` ("!E;'-E>PH ("` ("` ("` ("!L:6YK961,:7-T(2A%*2!T96UP
M(#T ;F5W(&QI;FME9$QI<W0A*$4I*"D["B` ("` ("` ("` (&QL3F]D92!C
M=7)S;W( /2!H96%D.PH ("` ("` ("` ("!I;G0 8W5R26YD97  /2`P.PH 
M("` ("` ("` ("!W:&EL92AC=7));F1E>#QL;W<I>PH ("` ("` ("` ("` 
M("` 8W5R26YD97 K*SL*("` ("` ("` ("` ("` (&-U<G-O<B`](&AE860N
M;F5X=#L*("` ("` ("` ("` ?0H ("` ("` ("` ("!W:&EL92AC=7));F1E
M>"`\/2!H:6=H*7L*("` ("` ("` ("` ("` ('1E;7`N<'5T*&-U<G-O<BYD
M871U;2D["B` ("` ("` ("` ("` ("!C=7)S;W( /2!C=7)S;W(N;F5X=#L*
M("` ("` ("` ("` ("` (&-U<DEN9&5X*RL["B` ("` ("` ("` ('T*("` 
M("` ("` ("` <F5T=7)N('1E;7`["B` ("` ("` ?0H ("` ("` (`H ("` 
M?0H ("` "B` ("!P=6)L:6, <W1R:6YG('1O4W1R:6YG*"E["B` ("` ("` 
M"B` ("` ("` "B` ("` ("` :68 *&AE860 (6ES(&YU;&PI>PH ("` ("` 
M("` ("!C:&%R6UT ;W5T4W1R:6YG(#T (ELB+F1U<#L*("` ("` ("` ("` 
M;&Q.;V1E(&-U<G-O<B`](&AE860[("`O+VQL3F]D92!I<R!A('!R:79A=&4 
M;F]D92!C;&%S<PH ("` ("` ("` ("!W:&EL92AC=7)S;W(N;F5X="`A:7, 
M(&YU;&PI>PH ("` ("` ("` ("` ("` ;W5T4W1R:6YG(#T ;W5T4W1R:6YG
M('X =&5X="AC=7)S;W(N9&%T=6TI('XB+"`B.PH ("` ("` ("` ("` ("` 
M8W5R<V]R(#T 8W5R<V]R+FYE>'0["B` ("` ("` ("` ('T*("` ("` ("` 
M("` ;W5T4W1R:6YG(#T ;W5T4W1R:6YG('X =&5X="AC=7)S;W(N9&%T=6TI
M('X (ETB.PH ("` ("` ("` ("!R971U<FX ;W5T4W1R:6YG+FED=7`["B` 
M("` ("` ?0H ("` ("` (&5L<V5["B` ("` ("` ("` (')E='5R;B`B6UTB
M.PH ("` ("` ('T*("` ("` ("`*("` ("` ("`*("` ('T*("` (`H ("` 
."B` ("`*"B` ("`*?0H`
`
end
Nov 01 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
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
Nov 01 2010
prev sibling next sibling parent reply Jesse Phillips <jessekphillips+D gmail.com> writes:
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
Nov 01 2010
parent reply Michael Woods <alienhunter3 gmail.com> writes:
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
Nov 01 2010
parent Jesse Phillips <jessekphillips+D gmail.com> writes:
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
Nov 01 2010
prev sibling next sibling parent reply spir <denis.spir gmail.com> writes:
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:
=20
 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 e=


lement 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 fr=
om 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 separ=
ate collection just for that. Typical use is for traversal (iteration). Sin=
ce 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 thi=
rd element -- without creating new lists for that. You can also make an ite=
rator 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 sequent=
ial iterator on a collection. [But I must admit it really does not fit my P=
OV on the topic -- this trio strongly smells functional :-) and actually ba=
sically models a linked list -- I'm certain its designer has a heavy Lisp b=
aggage! I would rather have a hasNext() and next() duo.]
Now, their working is simply to allow moving across elements, so no popFron=
t() does not pop. Examples:
	routine		dynarray	list
	popFront	inc(ptr)	current =3D current.next
	front()		*ptr		current.element	(possibly dereferenced)
	empty()		length =3D=3D 0	length =3D=3D 0 (maintained as field)
On a "true" linked list where every node implements the properties & method=
s of a list, then popFront is returning the second node, meaning the head o=
f the rest: l =3D l.next.

Hope most of this is correct (critics welcome).


Denis
-- -- -- -- -- -- --
vit esse estrany =E2=98=A3

spir.wikidot.com
Nov 01 2010
parent Jesse Phillips <jessekphillips+D gmail.com> writes:
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.
Nov 01 2010
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Nov 01 2010
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
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:=20
 http://www.informit.com/articles/article.aspx?p=3D1407357
=20
 front, popFront(), and empty make perfect sense as they are and work quit=


e well.=20

 hasNext() and next() have the serious drawback of mixing iterating throug=


h the=20

 range and getting an element in it. It's one of the serious flaws in Java=


's=20

 iterators. It's far better to have getting the current or front element b=


e=20

 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 t=
hose 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 drawba=
ck 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 ju=
st follows the next pointer; really complementary to front(). Or is there s=
omething 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 vi=
ew is wrong; the functionality is the same, done the same way, only naming =
reveals a different pov: next() is popFront() seen differently, hasNext() i=
s !empty().

Denis
-- -- -- -- -- -- --
vit esse estrany =E2=98=A3

spir.wikidot.com
Nov 01 2010
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
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 * 

except that they didn't overload * to get the current element but rather used a 

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
Nov 01 2010
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On Mon, 1 Nov 2010 20:40:30 -0700
Jonathan M Davis <jmdavisProg gmx.com> wrote:


 The term "pop" does _not_ mean that an element is returned but that it is=


=20

 removed from the range. This is true for pretty much anything that uses a=


 pop=20

 function in any language - stacks, lists, etc. It _is_ true that many=20
 implementations choose to have pop return the element which is popped, bu=


t=20

 that's an implementation detail. The term pop merely indicates that an el=


ement=20

 is removed from an end of a range or container.


All right, that's where I went wrong. Thank you for the clear explanation. =
(Now, I will continue with the article by Andrei Alexandrescu, 10 pages lef=
t :-)

[But I do not know of any pop not returning the removed value in any lang o=
r library; instead, pop is the favorite example of people arguing against t=
he distinction between actual functions (result, but no effect) and actions=
 (effect, but no result): naughty pop does both.
Maybe call it here remove()? Even if "pop"'s sense was defined by an all-mi=
ghty authority, we could hardly avoid people having different expectations =
born from previous experience, esp when it's so widespread: the two pop exa=
mples at http://en.wikipedia.org/wiki/Stack_%28data_structure%29 return the=
 element.]

I would also find current() much clearer than front(), since from the clien=
t's perspective it looks like shrinking the collection (or view) instead of=
 traversing it; see the confusion expressed by the OP's original question; =
but well...

Denis
-- -- -- -- -- -- --
vit esse estrany =E2=98=A3

spir.wikidot.com
Nov 02 2010
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, November 02, 2010 04:16:58 spir wrote:

 On Mon, 1 Nov 2010 20:40:30 -0700
 
 Jonathan M Davis <jmdavisProg gmx.com> wrote:

 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.


 
 All right, that's where I went wrong. Thank you for the clear explanation.
 (Now, I will continue with the article by Andrei Alexandrescu, 10 pages
 left :-)
 
 [But I do not know of any pop not returning the removed value in any lang
 or library; instead, pop is the favorite example of people arguing against
 the distinction between actual functions (result, but no effect) and
 actions (effect, but no result): naughty pop does both. Maybe call it here
 remove()? Even if "pop"'s sense was defined by an all-mighty authority, we
 could hardly avoid people having different expectations born from previous
 experience, esp when it's so widespread: the two pop examples at
 http://en.wikipedia.org/wiki/Stack_%28data_structure%29 return the
 element.]


C++'s pop functions don't return anything either, but it is true that many 
libraries in many languages choose to have pop functions return the value which 
is being popped. Having popFront() return a value in addition to having front 
look at the first value in the range wouldn't necessarily be a problem, but it 
isn't strictly speaking necessary. In some languages (certainly C++, though I'm 
not sure about D), returning a value which isn't used can mean a wasted copy or 
object construction which can be inefficient (particularly when dealing with
large 
objects on the stack). Whether a pop function returns anything tends to depend 
on how much an efficiency concern the library writer thinks that it is and how 
likely they think that it is that the popped value is going to be wanted. If 
it's expected that someone will always want the popped value, then it can be 
quite nice to have the pop function return it, but if there's a good chance
that 
they won't, then it could be an unwanted inefficiency. It all depends on the
goals 
and concerns of the library writer. In this case, D chose to not have
popFront() 
return anything.


 I would also find current() much clearer than front(), since from the
 client's perspective it looks like shrinking the collection (or view)
 instead of traversing it; see the confusion expressed by the OP's original
 question; but well...


Except that unlike an iterator (which indicates a single element), a range 
indicates a range of elements, so it can have both a front and a back (similar 
to having two iterators indicate a range of elements), so current() would be 
highly confusing once you went beyond input or forward ranges. For instance, bi-
directional ranges have back and popBack(), and random-access ranges have the 
subscript/slicing operator which can access an element or range of elements in 
the range, so current() would become highly confusing. What you have is a range 
of elements which has a clear first element (and assuming it isn't infinite or
of 
indefinite length) a clear last element. So, front and back access them and 
popFront() and popBack() pop them. It is indeed generally a view of a
collection 
of elements, but there is a definite order to them, whereas current() does not 
indicate order.

- Jonathan M Davis
Nov 02 2010
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
Jonathan M Davis wrote:


 In some languages (certainly C++, though I'm
 not sure about D), returning a value which isn't used can mean a 


wasted copy or

 object construction which can be inefficient (particularly when 


dealing with large

 objects on the stack). Whether a pop function returns anything tends 


to depend

 on how much an efficiency concern the library writer thinks that it 


is and how

 likely they think that it is that the popped value is going to be wanted.


The stronger reason why pop() doesn't return the object in C++ is about 
exception safety.

To me this topic is one of the most fascinating stories in C++'s 
history. Very briefly, Tom Cargill noted that exception safety gave a 
false sense of security and invited the C++ community to write an 
"exception-correct version of Stack":

 
http://ptgmedia.pearsoncmg.com/images/020163371x/supplements/Exception_Handling_Article.html

It took the community years to come up with an understanding of C++ 
exception safety. Herb Sutter posted the following "guru of the week" 
puzzle:

   http://www.gotw.ca/gotw/008.htm

which eventually ended up being in his later book "Exceptional C++", 
which turned out to be the biggest eye opener for me. Especially the 
exception safety section must be understood by any C++ programmer.

The solution for Tom Cargill's challenge turned out to be "cohesion", 
where pop() should not return the value; that should be provided by 
top(). The efficiency that came from having top() was a bonus.

Ali
Nov 03 2010