www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - InsertBefore in DList of structs

reply r-const-dev <r.const.dev gmail.com> writes:
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
Mar 04 2019
parent reply drug <drug2004 bk.ru> writes:
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
Mar 04 2019
parent reply drug <drug2004 bk.ru> writes:
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[]);
}

```
Mar 04 2019
parent reply r-const-dev <r.const.dev gmail.com> writes:
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?
Mar 04 2019
parent reply drug <drug2004 bk.ru> writes:
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
Mar 05 2019
parent r-const-dev <r.const.dev gmail.com> writes:
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.
Mar 05 2019