www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - What are the best std algo for testing a range implementation ?

reply "BicMedium" <BicMedium InvalidAddrButItsseriousQ.sk> writes:
Let's say I have a set of containers, using a 
D-unfriendly-semantic. They rather use a kind of ADA vocabulary 
(according to https://en.wikipedia.org/wiki/Deque). I want to 
make them "range-aware".

If the input/output ranges are easy to implement(so it's just 
reading/writing an element, keeping an index for the writer and 
another for the reader, and reseting it, isn't it ? So if 
(isInputRange!MyCont && isOutputRange!MyCont) then it's a 
"Deque", right ?).
The bidirectionnal ranges or the forward ranges become more 
difficult to interpret with the idioms I 
use(Insert,Add,Remove)...Is this a kind of 3rd plane ("time": 
"return to previous state", "make a backup": copy/roll-back - 
undo/redo ?)

Could you recommend me the algos from std.algo to test 
efficiently my implementations ? (example, if you want to be sure 
that the input ranges work then you'd use this...if you want to 
be sure that output ranges work then you'd use that ...Some kind 
of "reference" unit tests ?). At the present time, each time I 
try one I get rejected by the template constraints...
May 27 2014
next sibling parent "Chris" <wendlec tcd.ie> writes:
On Tuesday, 27 May 2014 at 10:50:54 UTC, BicMedium wrote:

 Let's say I have a set of containers, using a 
 D-unfriendly-semantic. They rather use a kind of ADA vocabulary 
 (according to https://en.wikipedia.org/wiki/Deque). I want to 
 make them "range-aware".

 If the input/output ranges are easy to implement(so it's just 
 reading/writing an element, keeping an index for the writer and 
 another for the reader, and reseting it, isn't it ? So if 
 (isInputRange!MyCont && isOutputRange!MyCont) then it's a 
 "Deque", right ?).
 The bidirectionnal ranges or the forward ranges become more 
 difficult to interpret with the idioms I 
 use(Insert,Add,Remove)...Is this a kind of 3rd plane ("time": 
 "return to previous state", "make a backup": copy/roll-back - 
 undo/redo ?)

 Could you recommend me the algos from std.algo to test 
 efficiently my implementations ? (example, if you want to be 
 sure that the input ranges work then you'd use this...if you 
 want to be sure that output ranges work then you'd use that 
 ...Some kind of "reference" unit tests ?). At the present time, 
 each time I try one I get rejected by the template 
 constraints...


I'm not sure, if I understand your question correctly, but I 
think what you need are RandomAccessRange's (cf. 
http://ddili.org/ders/d.en/ranges.html). You can save their state 
and access members randomly. However, as far as I know, the range 
itself should not be modified while you iterate over it.
May 27 2014
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Tuesday, 27 May 2014 at 10:50:54 UTC, BicMedium wrote:

 Let's say I have a set of containers, using a 
 D-unfriendly-semantic. They rather use a kind of ADA vocabulary 
 (according to https://en.wikipedia.org/wiki/Deque). I want to 
 make them "range-aware".

 If the input/output ranges are easy to implement(so it's just 
 reading/writing an element, keeping an index for the writer and 
 another for the reader, and reseting it, isn't it ? So if 
 (isInputRange!MyCont && isOutputRange!MyCont) then it's a 
 "Deque", right ?).
 The bidirectionnal ranges or the forward ranges become more 
 difficult to interpret with the idioms I 
 use(Insert,Add,Remove)...Is this a kind of 3rd plane ("time": 
 "return to previous state", "make a backup": copy/roll-back - 
 undo/redo ?)

 Could you recommend me the algos from std.algo to test 
 efficiently my implementations ? (example, if you want to be 
 sure that the input ranges work then you'd use this...if you 
 want to be sure that output ranges work then you'd use that 
 ...Some kind of "reference" unit tests ?). At the present time, 
 each time I try one I get rejected by the template 
 constraints...


cartesianProduct is a reasonable test of a forward range.

The first step however is to get your range type to pass the 
relevant range checks in std.range (e.g. isInputRange, 
isForwardRange etc)
May 27 2014
prev sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 27 May 2014 at 10:50:54 UTC, BicMedium wrote:

 Let's say I have a set of containers, using a 
 D-unfriendly-semantic. They rather use a kind of ADA vocabulary 
 (according to https://en.wikipedia.org/wiki/Deque). I want to 
 make them "range-aware".

 If the input/output ranges are easy to implement(so it's just 
 reading/writing an element, keeping an index for the writer and 
 another for the reader, and reseting it, isn't it ? So if 
 (isInputRange!MyCont && isOutputRange!MyCont) then it's a 
 "Deque", right ?).
 The bidirectionnal ranges or the forward ranges become more 
 difficult to interpret with the idioms I 
 use(Insert,Add,Remove)...Is this a kind of 3rd plane ("time": 
 "return to previous state", "make a backup": copy/roll-back - 
 undo/redo ?)


Just keep in mind that a container is not a range. A container is 
an object that can hold items, and you can add and remove items 
from said object. The Range is a way to iterate your container.

For example, a range definitely does NOT make insertion, removals 
or duplactes of your items. You can "save" a range, but that's 
NOT the same thing as making a duplicate of your container that 
you can roll back.

I'd suggest you take a look at std.container.array to see what 
I'm talking about.


 Could you recommend me the algos from std.algo to test 
 efficiently my implementations ? (example, if you want to be 
 sure that the input ranges work then you'd use this...if you 
 want to be sure that output ranges work then you'd use that 
 ...Some kind of "reference" unit tests ?). At the present time, 
 each time I try one I get rejected by the template 
 constraints...


If the algos are turning you down, then you must have missed 
something. Check that:
alias Range = YourRangeTypeHere;
static assert(isInputRange!Range);
static assert(isForwardRange!Range);
static assert(isBidirectionalRange!Range);
static assert(hasLength!Range);
static assert(isRandomAccessRange!Range);
static assert(hasSlicing!Range);

At the *very least*, the first 3 should pass for a deque. The 3 
others depend on what primitives you want to offer.
May 27 2014
parent reply "BicMedium" <BicMedium InvalidAddrButItsseriousQ.sk> writes:
On Tuesday, 27 May 2014 at 11:43:12 UTC, monarch_dodra wrote:

 On Tuesday, 27 May 2014 at 10:50:54 UTC, BicMedium wrote:

 Let's say I have a set of containers, using a 
 D-unfriendly-semantic. They rather use a kind of ADA 
 vocabulary (according to https://en.wikipedia.org/wiki/Deque). 
 I want to make them "range-aware".

 If the input/output ranges are easy to implement(so it's just 
 reading/writing an element, keeping an index for the writer 
 and another for the reader, and reseting it, isn't it ? So if 
 (isInputRange!MyCont && isOutputRange!MyCont) then it's a 
 "Deque", right ?).
 The bidirectionnal ranges or the forward ranges become more 
 difficult to interpret with the idioms I 
 use(Insert,Add,Remove)...Is this a kind of 3rd plane ("time": 
 "return to previous state", "make a backup": copy/roll-back - 
 undo/redo ?)


 Just keep in mind that a container is not a range. A container 
 is an object that can hold items, and you can add and remove 
 items from said object. The Range is a way to iterate your 
 container.

 For example, a range definitely does NOT make insertion, 
 removals or duplactes of your items. You can "save" a range, 
 but that's NOT the same thing as making a duplicate of your 
 container that you can roll back.

 I'd suggest you take a look at std.container.array to see what 
 I'm talking about.


 Could you recommend me the algos from std.algo to test 
 efficiently my implementations ? (example, if you want to be 
 sure that the input ranges work then you'd use this...if you 
 want to be sure that output ranges work then you'd use that 
 ...Some kind of "reference" unit tests ?). At the present 
 time, each time I try one I get rejected by the template 
 constraints...


 If the algos are turning you down, then you must have missed 
 something. Check that:
 alias Range = YourRangeTypeHere;
 static assert(isInputRange!Range);
 static assert(isForwardRange!Range);
 static assert(isBidirectionalRange!Range);
 static assert(hasLength!Range);
 static assert(isRandomAccessRange!Range);
 static assert(hasSlicing!Range);

 At the *very least*, the first 3 should pass for a deque. The 3 
 others depend on what primitives you want to offer.


My Q was not accurate enough. Maybe I'll ask something more 
concret in another one. BTW the 2nd and the 3rd assertions are 
exactly what fails when I try to test an algo (isInputRange!Range 
or isOutputRange!Range pass but has the test doesn't know about 
the implementation I can't know If it's really working...I mean 
that those tests are just like testing an interface...).
May 27 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 27 May 2014 at 12:18:15 UTC, BicMedium wrote:

 I mean that those tests are just like testing an interface...).


If your interface isn't complete, than it is irrelevant what your 
implementations are, since the algorithms can't use your ranges 
anyways.


 BTW the 2nd and the 3rd assertions are exactly what fails when 
 I try to test an algo (isInputRange!Range or 
 isOutputRange!Range pass but has the test doesn't know about 
 the implementation I can't know If it's really working...


Probably you are missing `save`, or you implemented it as a 
non-property function (though arguably, it shouldn't be a 
property, but that's another issue).
May 27 2014
parent reply "BicMedium" <BicMedium NowhereButItsSerious.sk> writes:
On Tuesday, 27 May 2014 at 14:05:56 UTC, monarch_dodra wrote:

 On Tuesday, 27 May 2014 at 12:18:15 UTC, BicMedium wrote:

 I mean that those tests are just like testing an interface...).


 If your interface isn't complete, than it is irrelevant what 
 your implementations are, since the algorithms can't use your 
 ranges anyways.


We agree on this point. The template constrains for isInputRange 
or isOutputRange just check, at compile-time, if the methods 
matchings to the prototypes defined in std.ranges (or in 
std.container empty, popFront, etc...) are implemented.

But there could be a templated-unittest for those kind of 
things...Ranges are relatively straightforward in to use, but 
when you want to implement one, it's another thing...So it's just 
about indexes ? And a kind of State machine for indexes 
(push/pop) ?
I hardly get how to make my easy containers range-aware. but I 
want to, because of std.algo.
May 27 2014
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 27 May 2014 at 16:49:42 UTC, BicMedium wrote:

 But there could be a templated-unittest for those kind of 
 things...Ranges are relatively straightforward in to use, but 
 when you want to implement one, it's another thing...So it's 
 just about indexes ? And a kind of State machine for indexes 
 (push/pop) ?


We can't wright a generic unittest to make sure that a range 
"works". Indeed, depending on *what* your range iterates, the 
test would be different.

You just have to test that yourself.


 I hardly get how to make my easy containers range-aware. but I 
 want to, because of std.algo.


The easiest way is to give your container the "Range opSlice()" 
function, where Range is the range you defined to iterate on your 
container. See std.container.array.
May 27 2014