www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How should I move in a DList ?

reply Gabriel <noadress noadress.noadress> writes:
Hello,

As I am totally new to D (my background is mainly C++) I am 
having trouble porting an algorithm that simplifies a polyline in 
2D, very similar to this one: 
http://psimpl.sourceforge.net/reumann-witkam.html

Here is what I would like:
1) Use a doubly-linked list, preferably one from a standard 
library (I need fast insertion/removal anywhere inside the list).
2) Have multiple "cursors" (ref to a list node, pointers, 
iterators etc.) that I move forward in my list when needed.
3) Remove and add some elements in the list (at/between "cursor" 
positions).

I am fine with having "unsafe" code for this example (the 
function is 43 lines long in C++, does not have too many cases 
and would be tested on a lot of data).

What "cursor" should I use to get something similar to C++'s 


languages).

Thanks in advance,
May 13 2020
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 5/13/20 5:57 AM, Gabriel wrote:
 Hello,
 
 As I am totally new to D (my background is mainly C++) I am having 
 trouble porting an algorithm that simplifies a polyline in 2D, very 
 similar to this one: http://psimpl.sourceforge.net/reumann-witkam.html
 
 Here is what I would like:
 1) Use a doubly-linked list, preferably one from a standard library (I 
 need fast insertion/removal anywhere inside the list).
 2) Have multiple "cursors" (ref to a list node, pointers, iterators 
 etc.) that I move forward in my list when needed.
 3) Remove and add some elements in the list (at/between "cursor" 
 positions).
 
 I am fine with having "unsafe" code for this example (the function is 43 
 lines long in C++, does not have too many cases and would be tested on a 
 lot of data).
 
 What "cursor" should I use to get something similar to C++'s std::list's 


 
This is one of the things I wanted when I made dcollections [1] (probably not working today due to 10+ years of bitrot). In dcollections, a "cursor" was what you got when you did any operations that would return an iterator normally in C++. A cursor was a one-element range, with only a reference to that one element. It can't be advanced further than "after" the given element, and so is safe like a range. So it's a bit different from C++, because you can't iterate with cursors, you iterate with ranges. But you can convert back and forth from those things easily. For example: auto ll = new LinkList!int(1, 2, 3, 4, 5); auto r = ll[]; // get a range assert(r.front == 1); auto cursor = r.begin; ll.insert(cursor, 5); assert(ll[].equal([5, 1, 2, 3, 4, 5]); r = ll[].find(3); // move back one r = ll[ll.begin .. r.begin]; assert(r.back == 2); Andrei was not keen on incorporating such a concept in Phobos, so it's not really present in the main library, instead you have to do some strange things with range acrobatics. If you want to move forward, you have to use popFront. If you want to move backwards, you are out of luck (unless you are interested in moving back from the end of the list). I would never recommend either DList or SList for actual linked lists (for stacks or queues, they are OK), as they are very unweildy and don't do what most people want linked lists to do. -Steve [1] https://github.com/schveiguy/dcollections
May 13 2020
parent Gabriel <noadress noadress.noadress> writes:
On Wednesday, 13 May 2020 at 14:29:53 UTC, Steven Schveighoffer 
wrote:
 I would never recommend either DList or SList for actual linked 
 lists (for stacks or queues, they are OK), as they are very 
 unweildy and don't do what most people want linked lists to do.

 -Steve

 [1] https://github.com/schveiguy/dcollections
Thanks a lot for this answer, I think the doubly-linked-list I found on Rosetta Code will do the job.
May 13 2020