I have a DList of structs, DataPoint, ordered by a struct field, time. I'm trying to insert a new entry preserving order, so I'm trying to use `until` to find the insertion point and `insertBefore` with the result.

struct DataPoint {
    immutable ulong time;
    ulong value;
}

void main() {
    DList!DataPoint dataPoints;
    void incrementAt(ulong time) {
        auto dataPoint = until!(dp => dp.time >= time)(dataPoints);
        if (dataPoint.time == time) {
            ++dataPoint.value;
        } else {
            dataPoints.insertBefore(dataPoint, DataPoint(time, 1));
        }
    }
}

But I'm getting:

/dlang/dmd/linux/bin64/../../src/phobos/std/algorithm/searching.d(4898): Error: template instance `onlineapp.main.incrementAt.Until!(__lambda2, DList!(DataPoint), void)` does not match template declaration Until(alias pred, Range, Sentinel) if (isInputRange!Range)
onlineapp.d(14): Error: template instance `onlineapp.main.incrementAt.until!((dp) => dp.time >= time, DList!(DataPoint))` error instantiating

On 04.03.2019 11:14, r-const-dev wrote:
> I have a DList of structs, DataPoint, ordered by a struct field, time. I'm trying to insert a new entry preserving order, so I'm trying to use `until` to find the insertion point and `insertBefore` with the result.
> 
> struct DataPoint {
>      immutable ulong time;
>      ulong value;
> }
> 
> void main() {
>      DList!DataPoint dataPoints;
>      void incrementAt(ulong time) {
>          auto dataPoint = until!(dp => dp.time >= time)(dataPoints);
>          if (dataPoint.time == time) {
>              ++dataPoint.value;
>          } else {
>              dataPoints.insertBefore(dataPoint, DataPoint(time, 1));
>          }
>      }
> }
> 
> But I'm getting:
> 
> /dlang/dmd/linux/bin64/../../src/phobos/std/algorithm/searching.d(4898): Error: template instance `onlineapp.main.incrementAt.Until!(__lambda2, DList!(DataPoint), void)` does not match template declaration Until(alias pred, Range, Sentinel) if (isInputRange!Range)
> onlineapp.d(14): Error: template instance `onlineapp.main.incrementAt.until!((dp) => dp.time >= time, DList!(DataPoint))` error instantiating

dataPoints itself isn't a range, you need to use dataPoints[]. Also
insertStable needs DList.Range, not Until!... one. You can do something like this https://run.dlang.io/is/A2vZjW

On 04.03.2019 13:03, drug wrote:
> insertStable needs DList.Range, not Until!... one. You can do something like this https://run.dlang.io/is/A2vZjW
Oops, it was wrong example, I'd recommend this way - https://run.dlang.io/is/ugPL8j
```
import std.algorithm, std.container, std.stdio;

struct DataPoint {
    immutable ulong time;
    ulong value;
}

void main() {
    auto dataPoints = DList!DataPoint([
        DataPoint(10_000_000, 1),
        DataPoint(30_000_000, 3),
        DataPoint(40_000_000, 4),
    ]);

    auto time = 30_000_000;
    auto r = findSplit!((a, b) => a.time == b)(dataPoints[], [time]);

    auto dp = dataPoints[].find(r[1].front);
    writeln("before: ", dataPoints[]);
    dataPoints.insertBefore(dp, DataPoint(20_000_000, 2));
    writeln("after: ", dataPoints[]);
}

```

On Monday, 4 March 2019 at 10:09:19 UTC, drug wrote:
> On 04.03.2019 13:03, drug wrote:
>> insertStable needs DList.Range, not Until!... one. You can do something like this https://run.dlang.io/is/A2vZjW
> Oops, it was wrong example, I'd recommend this way - https://run.dlang.io/is/ugPL8j
> ```
> import std.algorithm, std.container, std.stdio;
>
> struct DataPoint {
>     immutable ulong time;
>     ulong value;
> }
>
> void main() {
>     auto dataPoints = DList!DataPoint([
>         DataPoint(10_000_000, 1),
>         DataPoint(30_000_000, 3),
>         DataPoint(40_000_000, 4),
>     ]);
>
>     auto time = 30_000_000;
>     auto r = findSplit!((a, b) => a.time == b)(dataPoints[], [time]);
>
>     auto dp = dataPoints[].find(r[1].front);
>     writeln("before: ", dataPoints[]);
>     dataPoints.insertBefore(dp, DataPoint(20_000_000, 2));
>     writeln("after: ", dataPoints[]);
> }
>
> ```

Thanks, seems that using dataPoints[] makes dataPoints usable as an range. How can I learn more about [] operator? I'm not sure I understand how is this documented in DList.

Find does the job! What's the difference between find and until?

On 05.03.2019 2:01, r-const-dev wrote:
> 
> Thanks, seems that using dataPoints[] makes dataPoints usable as an range. How can I learn more about [] operator? I'm not sure I understand how is this documented in DList.
dataPoints is an aggregate type variable, not a range and slice operator opSlice/[] returns a range of this aggregate type. I have no appropriate links unfortunately but these can be useful
https://dlang.org/phobos/std_container_dlist.html#.DList.opSlice - this operator returns a range
https://dlang.org/phobos/std_container_dlist.html#.DList.Range - this is  range that allows to iterate over DList elements
http://ddili.org/ders/d.en/ranges.html - intro to ranges
> 
> Find does the job! What's the difference between find and until?
`find` returns a range that starts from the key
`until` returns a range of all elements before the key
https://run.dlang.io/is/1kpOUx

P.S. `findSplit` returns three ranges, first one contains all elements before the key like `until`, second range contains all elements that are equal to the key and third range contains the rest

On Tuesday, 5 March 2019 at 08:39:56 UTC, drug wrote:
> On 05.03.2019 2:01, r-const-dev wrote:
>> [...]
> dataPoints is an aggregate type variable, not a range and slice operator opSlice/[] returns a range of this aggregate type. I have no appropriate links unfortunately but these can be useful
> https://dlang.org/phobos/std_container_dlist.html#.DList.opSlice - this operator returns a range
> https://dlang.org/phobos/std_container_dlist.html#.DList.Range - this is
>  range that allows to iterate over DList elements
> http://ddili.org/ders/d.en/ranges.html - intro to ranges
>> [...]
> `find` returns a range that starts from the key
> `until` returns a range of all elements before the key
> https://run.dlang.io/is/1kpOUx
>
> [...]

Thank you for clarifications, it makes sense to me now.