Intersection of two sets

[mipri]

On Tuesday, 3 December 2019 at 18:45:18 UTC, Jan Hönig wrote:
> On Tuesday, 3 December 2019 at 13:55:51 UTC, Alex wrote:
>>
>> This depends on the available accesses on your sets. In terms 
>> of ranges:
>> Are your sets InputRanges, ForwardRange, ... ?
>>
>>
>>> 2) Are there some build-in function for handling such sets?
>>
>> This is maybe what you are looking for: 
>> https://dlang.org/phobos/std_algorithm_setops.html
>
> In terms of ranges, i need to understand ranges properly first.

The top of https://dlang.org/phobos/std_range.html has some
talks and tutorials to consider.

> The std.algorithm.setops have definitely the functionality i 
> need.
> I guess my current implementation would be a simple array.
> I just need to make sure delete, or not create double entries.

A problem with the unittest examples is that they assume the
reader is very familiar with the language :) Here are some
things to keep in mind with setIntersection:

1. setIntersection expects its inputs to be sorted. If they
aren't, it doesn't notice; you just don't get the behavior you
want.

   int[] a = [4, 2, 3, 1], b = [8, 4, 2, 6];

   assert(setIntersection(a, b).array == []); // !
   assert(setIntersection(a.sort, b.sort).array == [2, 4]);

2. setIntersection returns a range, not an array. This probably
lets you return the infinite intersections of two infinite
ranges, for example. If you're looking at this for Advent of
Code you'll probably want to pass the intersections through
some other operators that will accept a range.

(Also, sort mutates *and* returns the array. if you're
depending on the positions of 2 and 4 in the original arrays,
you should get the intersection of a sorted copy of them.)

In general, pay attention to the static constraints:

   if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) &&
   !is(CommonType!(staticMap!(ElementType, Rs)) == void));

In English:

1. if you're getting an intersection of ranges, you need to
provide at least two ranges.

2. all of the ranges need to be input ranges

3. the ranges' element types need to have a common type that
isn't 'void'.

You can use these same constraints in your code if you're not
sure if they apply

     static assert (isInputRange!(typeof(a)));
     assert(setIntersection(a, b).array == []);

or you can test them interactively:

   $ rdmd --eval 'isInputRange!(typeof([1, 2, 3])).writeln'
   true

And you can also check on their documentation and see if it's
what you expect:

   https://dlang.org/phobos/std_range_primitives.html

D doesn't have 500+ line errors for the simplest template
misuse like C does, but its much shorter template error
messages still could be friendlier. Usually they're in terms of
these constraints, or you've a more basic error like having a
range type (like the SetIntersection struct that
setIntersection actually returns) where some other code expects
a simple array, or vice versa.