Working on another part of the C++ Standard Library to import.
Continuing the discussion from Computations, and where to save resources, are hard:
The set-subtraction functionality is actually part of a mini-framework. I uploaded it to a Gist.
Sequence.whileMergingSorted(with: do: by:) is the core method. Both the receiver and the sequence passed as the first argument must be sorted according to the predicate passed into the third argument. The second argument is an action closure. The method reads from both sequences and passes to the action closure a value with one element from each sequence if they're equivalent, or a value with one element that's the least-ordered from the current front of the receiver or second sequence. The passed value is of a custom
enum type. If you prefer a pull interface instead of a push one, the
MergeSortedSequence generic type is a lazy sequence (and collection if both sequences are collections too) that walks its input sequences and vends
Segregating by elements that are exclusive to the first sequence, second sequence, or are shared is the key to all of the functions in this framework.
Since I didn't need it for my prime sieve research, I didn't directly provide an analogue to the C++ function
std::merge, but the methods above can be used to make such a method. Just push-out/transform the source values the same order they came in, stripping out the
MergedSetElementSource wrapper. For
.shared values, output two values, the first member, then the second, if you want an interleaved merge-sort. But we usually want to have all the equivalent elements from the second sequence to follow those from the first; you have to output only the values from the first sequence and queue those from the second until the next upcoming element has a greater value. I can write that method if we go further along in the process.
Sequence.overlapIfMergedSorted(with: by:) method is the analogue to the C++
std::includes function. It is more precise than a simple inclusion
Bool; a custom
TwoSetOverlap enumeration type is returned that specifies the exact relationship between the two sequences. Right now, I'm not sure we need to keep its initializer public.
There are two similar functions that came out of the above method. The
Sequence.sourceCountWhileMergingSorted(with: by:) method gives the exact counts of the first-exclusive/shared/second-exclusive elements. The
Sequence.whileMergingSortedConfirmFor method is a quasi-dual where you submit what shape of first-exclusive/shared/second-exclusive layout you want and the method confirms if the sorted merger would match. I'm not sure if either of these should go in our standard library.
All the methods that take a comparison predicate have a default
SetOperation enumeration type is a dual to
TSO is for reading combinations,
SO is for writing them. Those operations are called by the
Sequence.mergeSortedAsSets(with: keeping: by:) method. It has variants for overriding the returned collection, working lazily, or using
Comparable by default. The lazy-sequence version is a collection when both sorted sequences are collections. This
enum and method set combined are analogues to
std::set_union, and then some.
I wanted to use one enumeration type for set combinations, but
TSO have slightly different operations. And the
case names are vastly different, so I don't see how I can merge them and still keep the names making sense.