digitalmars.D.learn - Linked list, printing looks destructive.
- Alain De Vod (31/31) Apr 24 2022 Following program is a single linked list.
- =?UTF-8?Q?Ali_=c3=87ehreli?= (33/34) Apr 24 2022 This type violates a fundamental rule: Containers and ranges are
- Salih Dincer (95/98) Apr 24 2022 Dear Ali,
- Alain De Vos (37/137) Apr 25 2022 I implemented an alternative goroot it's called re_init and next
- Alain De Vos (28/28) Apr 25 2022 This program works ok, (but List is no Range)
- Salih Dincer (63/64) Apr 25 2022 It is also possible with the copy constructor of a struct. I
- =?UTF-8?Q?Ali_=c3=87ehreli?= (15/17) Apr 25 2022 Classes don't have language provided construction because nobody needs
- cc (40/44) Apr 25 2022 If you don't need List to be treated as a true range, but just
- Alain De Vos (31/31) Apr 25 2022 Indeed code below works,
Following program is a single linked list.
We expect as output 1 2 3 1 2 3
But the output is only 1 2 3
I think this has something to do with popFront
How to fix it using "class List" ?
```
import std.stdio: write,writeln;
import std.range: empty,popFront,front;
struct Node {
int element;
Node * next;
}
class List {
Node * root=null;
this(int[] AR){foreach(i ; AR)pushfront(i);}
bool empty() const {return !root;}
void popFront() {root=root.next;}
float front() const {return root.element;}
void pushfront(int element) {
Node * newnode=new Node();
newnode.element=element;
newnode.next=root;
root=newnode;
}
}//List
void main(){
List l=new List([3,2,1]);
foreach(element; l) writeln(element);
foreach(element; l) writeln(element);
}
```
Apr 24 2022
On 4/24/22 18:40, Alain De Vod wrote:I think this has something to do with popFrontThis type violates a fundamental rule: Containers and ranges are separate concepts. Your List is a container, not a range. I changed your code by moving the range functions to a Range struct that is created by opSlice(): class List { Node * root=null; this(int[] AR){foreach(i ; AR)pushfront(i);} auto opSlice() { return Range(root); } static struct Range { Node * root_; bool empty() const {return !root_;} void popFront() {root_=root_.next;} float front() const {return root_.element;} } void pushfront(int element) { Node * newnode=new Node(); newnode.element=element; newnode.next=root; root=newnode; } }//List The foreach loop implicitly calls opSlice() and it all works.[1] When you want a range, you can call opSlice indirectly by using [] after the object: import std.algorithm; writeln(l[].map!(e => e * 2)); Ali [1] As reported recently by Steven Schveighoffer, this information is missing in my book: https://bitbucket.org/acehreli/ddili/issues/33/add-additional-foreach-mechanism-to-range
Apr 24 2022
On Monday, 25 April 2022 at 02:19:46 UTC, Ali Çehreli wrote:This type violates a fundamental rule: Containers and ranges are separate concepts. Your List is a container, not a range. I changed your code by moving the range functions to a Range [...]Dear Ali, I implemented a linkedlist over classical logic (*_leaf and const *_root). Now seeing the ranges approach I tried it but without success. The following implementation can work with foreach() though; as long as you call goRoot() :) ```d class List(dType) { struct Node { dType item; Node* next; } bool FIFO; private Node * _leaf; this(bool FIFO = true, dType item = dType.init) { this.FIFO = FIFO; if(FIFO) _leaf= new Node(item, null); _root = cast(const)_leaf; } /* auto opSlice() { return Range(_leaf); } static struct Range {//*/ const Node * _root; auto empty() { return !_leaf; } auto popFront() { return _leaf = _leaf.next; } dType front(Node * node = null) { dType result; if(node) { result = (*node).item; } else result = (*_leaf).item; return result; } //} alias Next = popFront; alias pop = front; alias push = InsertBack; void InsertBack(dType item) { _leaf = new Node(item, _leaf); } void InsertFront(dType item) { (*_leaf).next = new Node(item, null); Next; } auto goRoot() { return _leaf = cast(Node*)_root.next; } } import std.stdio; enum FIFO { False, True } enum end = 20; void main() { int firstNumber = 10; auto FIFO_Stack = new List!int; with(FIFO_Stack) { do { InsertFront(firstNumber); } while(++firstNumber <= end); goRoot(); do pop.writef!" %s"; while(Next); writeln; } FIFO_Stack.goRoot(); foreach(stack; FIFO_Stack) { stack.writeln; } } /* OUTPUT: 10 11 12 13 14 15 16 17 18 19 20 10 11 12 13 14 15 16 17 18 19 20 */ ``` SDB 79
Apr 24 2022
On Monday, 25 April 2022 at 05:17:28 UTC, Salih Dincer wrote:On Monday, 25 April 2022 at 02:19:46 UTC, Ali Çehreli wrote:I implemented an alternative goroot it's called re_init and next program works. Still I don't understand what is really going on. Some state is lost using a class and you have restore it. And the state is not lost using a struct. ``` cat test.d import std.stdio: write,writeln; import std.range: empty,popFront,front; struct Node { int element; Node * next; } class List { Node * root=null; Node * walker=null; this(int[] AR){foreach(i ; AR)pushfront(i);} bool empty() const {return !walker;} void popFront() {walker=walker.next;} float front() const {return walker.element;} void pushfront(int element) { Node * newnode=new Node(); newnode.element=element; newnode.next=root; root=newnode; re_init(); } void re_init(){walker=root;} }//List void main(){ List l=new List([3,2,1]); l.writeln(); l.re_init(); l.writeln(); } ```This type violates a fundamental rule: Containers and ranges are separate concepts. Your List is a container, not a range. I changed your code by moving the range functions to a Range [...]Dear Ali, I implemented a linkedlist over classical logic (*_leaf and const *_root). Now seeing the ranges approach I tried it but without success. The following implementation can work with foreach() though; as long as you call goRoot() :) ```d class List(dType) { struct Node { dType item; Node* next; } bool FIFO; private Node * _leaf; this(bool FIFO = true, dType item = dType.init) { this.FIFO = FIFO; if(FIFO) _leaf= new Node(item, null); _root = cast(const)_leaf; } /* auto opSlice() { return Range(_leaf); } static struct Range {//*/ const Node * _root; auto empty() { return !_leaf; } auto popFront() { return _leaf = _leaf.next; } dType front(Node * node = null) { dType result; if(node) { result = (*node).item; } else result = (*_leaf).item; return result; } //} alias Next = popFront; alias pop = front; alias push = InsertBack; void InsertBack(dType item) { _leaf = new Node(item, _leaf); } void InsertFront(dType item) { (*_leaf).next = new Node(item, null); Next; } auto goRoot() { return _leaf = cast(Node*)_root.next; } } import std.stdio; enum FIFO { False, True } enum end = 20; void main() { int firstNumber = 10; auto FIFO_Stack = new List!int; with(FIFO_Stack) { do { InsertFront(firstNumber); } while(++firstNumber <= end); goRoot(); do pop.writef!" %s"; while(Next); writeln; } FIFO_Stack.goRoot(); foreach(stack; FIFO_Stack) { stack.writeln; } } /* OUTPUT: 10 11 12 13 14 15 16 17 18 19 20 10 11 12 13 14 15 16 17 18 19 20 */ ``` SDB 79
Apr 25 2022
This program works ok, (but List is no Range)
```
class Node {
int data;
Node next;
}
class List {
Node node=null;
this(int[] AR){foreach(i ; AR)pushfront(i);}
bool empty() const {return !node;}
void popFront() {node=node.next;}
float front() const {return node.data;}
void pushfront(int data) {
Node newnode=new Node();
newnode.data=data;
newnode.next=node;
node=newnode;
}
}//List
void main(){
List l=new List([3,2,1]);
Node backupnode=l.node;
l.writeln();
l.node=backupnode;//Restore state destroyed by writeln
l.writeln();
}
```
Apr 25 2022
On Monday, 25 April 2022 at 09:38:05 UTC, Alain De Vos wrote:This program works ok, (but List is no Range)It is also possible with the copy constructor of a struct. I don't know how to do with class... ```d struct Node { int element; Node * next; } struct List { Node * root, walker; this(int[] AR) { foreach(i; AR) { pushfront(i); } } bool empty() const { return !walker; } void popFront() { walker = walker.next; } float front() const { return walker.element; } void pushfront(int element) { Node * newnode = new Node(); newnode.element = element; newnode.next = root; root = newnode; } // shallow copy this(ref return scope List that) { this.walker = that.root; } }//List import std.stdio; void main() { List list = List([3,2,1]); //Node backupnode=l.node; foreach(l; list) l.writeln(); //l.node=backupnode;//Restore state destroyed by writeln foreach(l; list) l.writeln(); } ``` SDB 79
Apr 25 2022
=?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> On 4/25/22 03:48, Salih Dincer wrote:It is also possible with the copy constructor of a struct. I don't know how to do with class...Classes don't have language provided construction because nobody needs it and in fact they have to protect themselves when a language provides it. (See, e.g. C++'s slicing problem: https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rc-copy-virtual ) [1] In case you want to copy a class object, you must provide a function yourself, which may be called anything you want or 'dup' to match with a name used by D. Ali Off-topic rant: It frustrates me when C++ programmers shun D because it is "a language with reference types" as told to me by a well-known C++ speaker. I guess they should attempt to read C++'s core guidelines to understand how a polymorphic class makes it an accident to pass its objects by value.
Apr 25 2022
On Monday, 25 April 2022 at 01:40:01 UTC, Alain De Vod wrote:Following program is a single linked list. We expect as output 1 2 3 1 2 3 But the output is only 1 2 3 ```If you don't need List to be treated as a true range, but just want to iterate, a simple way to do this is with opApply: https://tour.dlang.org/tour/en/gems/opdispatch-opapply ```d import std.stdio: write,writeln; import std.range: empty,popFront,front; struct Node { int element; Node * next; } class List { Node * root=null; this(int[] AR){foreach(i ; AR)pushfront(i);} bool empty() const {return !root;} /*void popFront() {root=root.next;} float front() const {return root.element;}*/ void pushfront(int element) { Node * newnode=new Node(); newnode.element=element; newnode.next=root; root=newnode; } int opApply(int delegate(typeof(Node.element)) dg) { Node* current = root; while (current) { if (dg(current.element)) return 1; // stop iteration if the foreach body asks to break current = current.next; } return 0; } }//List void main(){ List l=new List([3,2,1]); foreach(element; l) writeln(element); foreach(element; l) writeln(element); } // 1 2 3 1 2 3 ```
Apr 25 2022
Indeed code below works,
```
import std.stdio: write,writeln;
class Node {
int data;
Node next;
}
class List {
Node node=null;
this(int[] AR){foreach(i ; AR)pushfront(i);}
void pushfront(int data) {
Node newnode=new Node();
newnode.data=data;
newnode.next=node;
node=newnode;
}//pushfront
int opApply(int delegate(typeof(Node.data)) dg) {
Node current = node;
while (current) {
if (dg(current.data)) return 1;
current = current.next;
}
return 0;
}//opApply
}//List
void main(){
List l=new List([3,2,1]);
foreach(element; l) writeln(element);
foreach(element; l) writeln(element);
}//main
```
Apr 25 2022