• Jan =?UTF-8?B?SMO2bmln?= (27/27) May 16 2020 I want a simple algorithm.
• Jan =?UTF-8?B?SMO2bmln?= (7/8) May 16 2020 I have another implementation, which should work:

Jan =?UTF-8?B?SMO2bmln?= <hrominium gmail.com> writes:

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 :)

Jan =?UTF-8?B?SMO2bmln?= <hrominium gmail.com> writes:

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.