digitalmars.D.learn - Traverse a DList and insert / remove in place?
- Armando (38/38) Mar 19 2023 Say I have a DList. I am looking for a vanilla way to
- Armando (40/40) Mar 19 2023 ok there is the issue of not knowing how to traverse the list
- Bastiaan Veelo (48/52) Mar 25 2023 This is one way to do that:
- Armando (24/24) Mar 27 2023 Wonderful, that works like a treat, thank you so much! For those
- Gary Chike (2/4) Mar 27 2023 Very cool! Thanks for asking and sharing! :)
Say I have a DList. I am looking for a vanilla way to insert/remove elements in place while traversing that list. ```d import std.container : DList; struct myType{ int id; // [...] other stuff } auto list = DList!myType(); // [...] populate list with elements ``` To remove the element with id=3 I can do: ```d list.linearRemove(list[].find!(a => a.id==3).take(1)); ``` but according to [this post](https://forum.dlang.org/post/mailman.3110.1356864469.5162.digitalm rs-d puremagic.com) linearRemove might be less efficient than remove and remove can't be used. Also in the example above, finding the needle is easy but my case would involve more complicated scenarios that I am relunctant to bury into find's predicate. I would like to do something like traversing a DList, operating on the current element, and potentially removing that element or inserting a new one before/after it - an easy operation if you code a DList yourself. Maybe I missed something? ```d // Traverse and operate on current element foreach(element; list) { // [...] do something long and complicated with m, throw a random number rand if(rand < 0.5) list.removeInPlace(); // remove 'element' else list.insertInPlace(myType(...)); // insert a new element "here" (before/after 'element') } ``` Any way to achieve this simply with D? E.g. is there a way to extract the 'reading head' of a list being traversed and to use that head as a range into the remove, insertAfter, insertBefore functions?
Mar 19 2023
ok there is the issue of not knowing how to traverse the list after removing the current element (=> the one that came after of course). But how about even just keeping a pointer (range) to 'element' that can be used after the list has been traversed in full to use in remove / insertAfter? I think I can achieve this with associative arrays (below) but it seems overkill to use an associative effectively as a DList? ```d struct myType{ int id; int prev, next; // id of prev and next // [...] other stuff this(int id_, int prev_, int next_) { //[...] } } myType[int] list; // key = id int[] to_remove; myType[] to_add; foreach(elem; list) { // [...] do something long and complicated with elem, throw a random number rand if(rand < 0.5) to_remove ~= elem.id; // flag for removal else to_add ~= myType(some_new_id, elem.id, elem.next); // add new elem after current } foreach(elem; to_add) list[elem.id] = elem; foreach(id; to_remove) { // reconnect: prev's next to next, and next's prev to prev list[list[id].prev].next = list[id].next; list[list[id].next].prev = list[id].prev; list.remove(id); } ```
Mar 19 2023
On Sunday, 19 March 2023 at 13:15:58 UTC, Armando wrote:I would like to do something like traversing a DList, operating on the current element, and potentially removing that element or inserting a new one before/after it - an easy operation if you code a DList yourself. Maybe I missed something?This is one way to do that: ```d import std; struct MyType { int id; // [...] other stuff } void main() { auto list = DList!MyType(); // Fill the list. foreach (i; 0 .. 10) list.insertBack(MyType(i)); // Traverse the list, conditionally remove one element. for (auto range = list[]; !range.empty;) if (range.front.id == 3) list.popFirstOf(range); else range.popFront(); // Traverse the list, conditionally insert one element. for (auto range = list[]; !range.empty;) { if (range.front.id == 6) list.insertBefore(range, MyType(66)); range.popFront(); } // Print modified list. foreach (e; list) writeln(e); } ``` Output: ``` MyType(0) MyType(1) MyType(2) MyType(4) MyType(5) MyType(66) MyType(6) MyType(7) MyType(8) MyType(9) ``` https://run.dlang.io/is/kk80FD -- Bastiaan.
Mar 25 2023
Wonderful, that works like a treat, thank you so much! For those who wonder, inserting after works too: ```d for (auto range = list[]; !range.empty;) { if (range.back.id == 8) list.insertAfter(range, MyType(88)); range.popBack(); } ``` which will give ``` MyType(0) MyType(1) MyType(2) MyType(4) MyType(5) MyType(66) MyType(6) MyType(7) MyType(8) MyType(88) MyType(9) ```
Mar 27 2023
On Monday, 27 March 2023 at 15:05:16 UTC, Armando wrote:Wonderful, that works like a treat, thank you so much! For those who wonder, inserting after works too:Very cool! Thanks for asking and sharing! :)
Mar 27 2023