www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Linked List iterating over and inserting an element around

reply Josh <foo bar.com> writes:
Just started looking at D this weekend, coming from a 
C++/Java/Go/Rust background and it's really not going well.  
Trying to write something to play with the language and need a 
linked list, looking in std.container you have a single or doubly 
linked list...great.

Now how to I iterate over it and look for a value and then modify 
it, and maybe insert a new element before or after that 
element.....After spending way to long on the API realized I need 
to be looking at std.range (I think, maybe not, I'm not sure).

So off to the std.range documentation, which recommended reading 
http://ddili.org/ders/d.en/ranges.html, okay read that, boy if I 
want to display the contents of range I'm ALL set, to bad I would 
like to modify a list, so I seem to be no closer to my goal....oh 
and by the way if you think:

import std.stdio;
import std.range;

void main() {
     int[] slice = [ 1, 2, 3 ];
     int[] slice2 = slice;

     put(slice2, 100);

     writeln(slice2);
     writeln(slice);
}

Resulting in:

[2, 3]
[100, 2, 3]    ← expected result

Is obvious, I have some bad news for you.

Now I'm thinking maybe std.algorithm.comparison, maybe iteration 
or maybe mutation seems promising, at least that's what I want to 
do, mutate a list....hey there is a swap...oh it doesn't deal 
with ranges...

Maybe swapAt but that sounds like I need an index, and indexes 
with linked list don't really perform well...but it does take a 
range....okay I think that is what I need, so in a foreach loop, 
looking at https://tour.dlang.org/tour/en/basics/ranges I would 
call swapAt and pass in __rangeCopy, I think I can update, happy 
days, now to figure out how to add something before or after that 
element......


So in short I guess my complaint is that you show all this stuff 
about displaying ranges and removing items from the front or 
end...so if I want a queue we're set, but nothing about modifying 
them...unless it's so blatantly obvious I'm just missing it, 
which could be the case.
May 19 2019
parent reply Paul Backus <snarwin gmail.com> writes:
On Sunday, 19 May 2019 at 20:55:28 UTC, Josh wrote:

 Just started looking at D this weekend, coming from a 
 C++/Java/Go/Rust background and it's really not going well.  
 Trying to write something to play with the language and need a 
 linked list, looking in std.container you have a single or 
 doubly linked list...great.

 Now how to I iterate over it and look for a value and then 
 modify it, and maybe insert a new element before or after that 
 element.....After spending way to long on the API realized I 
 need to be looking at std.range (I think, maybe not, I'm not 
 sure).


Here's an example using std.container.dlist:

import std.stdio;
import std.container.dlist;
import std.algorithm;

void main()
{
     auto list = make!DList("the", "quick", "brown", "fox");
     auto range = list[].find("quick");
     range.front = "slow";
     list.insertBefore(range, "really");
     list[].each!writeln; // The really slow brown flox
}

Interactive version: https://run.dlang.io/is/j1Qa8y
May 19 2019
parent reply Josh <foo bar.com> writes:
Thank you, that helps big time.

This is just more curiosity, but do you happen to know why I have 
to use DList.linearRemove() instead of DList.remove()?

import std.stdio;
import std.container.dlist;
import std.algorithm;
import std.range;

void main()
{
     auto list = make!DList("the", "quick", "brown", "fox");
     auto range = list[].find("quick").take(1);
     list.remove(range);
     list[].each!writeln; // the brown fox
}

This results in a compiler issue:

onlineapp.d(10): Error: function 
std.container.dlist.Container!string.DList.remove(Range r) is not 
callable using argument types (Take!(Range))
onlineapp.d(10):        cannot pass argument range of type 
Take!(Range) to parameter Range r

Changing "remove" to "linearRemove" fixes it, but both the remove 
and linearRemove functions take a Range object, and linearRemove 
seems to just be a pass through to remove.
May 19 2019
next sibling parent Boris-Barboris <ismailsiege gmail.com> writes:
On Sunday, 19 May 2019 at 22:20:48 UTC, Josh wrote:

 This is just more curiosity, but do you happen to know why I 
 have to use DList.linearRemove() instead of DList.remove()?


These two functions are separate because they differ in 
complexity. remove is O(1), linearRemove on the other hand 
eagerly walks through the Take range, wich makes it 
O(take.walklength).
May 19 2019
prev sibling parent Paul Backus <snarwin gmail.com> writes:
On Sunday, 19 May 2019 at 22:20:48 UTC, Josh wrote:

 Thank you, that helps big time.

 This is just more curiosity, but do you happen to know why I 
 have to use DList.linearRemove() instead of DList.remove()?

 import std.stdio;
 import std.container.dlist;
 import std.algorithm;
 import std.range;

 void main()
 {
     auto list = make!DList("the", "quick", "brown", "fox");
     auto range = list[].find("quick").take(1);
     list.remove(range);
     list[].each!writeln; // the brown fox
 }

 This results in a compiler issue:

 onlineapp.d(10): Error: function 
 std.container.dlist.Container!string.DList.remove(Range r) is 
 not callable using argument types (Take!(Range))
 onlineapp.d(10):        cannot pass argument range of type 
 Take!(Range) to parameter Range r

 Changing "remove" to "linearRemove" fixes it, but both the 
 remove and linearRemove functions take a Range object, and 
 linearRemove seems to just be a pass through to remove.


The documentation for DList.remove says that the range parameter 
"must be originally obtained from this container." A range 
returned from `take` doesn't qualify, since `take` returns a new 
range that wraps the original one. (`find` seems to be the 
exception rather than the rule, here, in that it actually returns 
the same type of range that's given to it.) However, the 2nd 
overload of linearRemove [1] is specifically written to accept a 
Take!Range, so it will work.

Fortunately, it is possible to accomplish what you want using 
DList.popFirstOf: [2]

     auto range = list[].find("quick");
     list.popFirstOf(range);

Full example: https://run.dlang.io/is/DCYtbp

[1] 
https://dlang.org/phobos/std_container_dlist.html#.DList.linearRemove.2
[2] 
https://dlang.org/phobos/std_container_dlist.html#.DList.popFirstOf
May 19 2019