May 16, 2020 Fighting the DList | ||||
---|---|---|---|---|
| ||||
I want a simple algorithm. Given DList (or a Range, Array... I am not constrained by the container type), I want to combine certain elements depending on some condition. In the toy example, the struct and condition are simpler then in my real scenario, but i think it covers my problem: https://run.dlang.io/is/1QGw85 The function `conflate` is the algorithm I want and is currently not working (either it is wrong, or cannot compile). How I imagined it to work in rough pseudo code: outer: traverse the list: inner: traverse the list from the current outer position if condition(current outer position, current inner position) combine(current outer position, current inner position) stableDelete(current inner position) I am convinced that this works. It is really not that hard, all i need is a DoublyLinked list. D's DList however does not provide me with the interface I need for implementing this. Or I am too stupid to see how I should do it. I am not restricted on DLists, I can choose whatever I want. The rest of the code should work with just InputRanges. However doubly linked list should be most efficient for this problem, since all I want to do is delete stuff at random position, i.e. to bend some pointers. Yes I might suffer from premature optimization :) |
May 16, 2020 Re: Fighting the DList | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jan Hönig | On Saturday, 16 May 2020 at 08:11:20 UTC, Jan Hönig wrote: > I am convinced that this works. I have another implementation, which should work: https://run.dlang.io/is/tfBgD0 It is not pretty. It is probably not fast, if the `ignore` is too large. I guess it is in O(n^2) if not O(mn^2), where m is the number of `same` structs. |
Copyright © 1999-2021 by the D Language Foundation